Fast Local Subgraph Counting

Download PDF

Abstract

We study local subgraph counting queries,𝑄=(𝑝,𝑜),to count how many times a given 𝑘-node pattern graph 𝑝 appears around every node 𝑣 in a data graph 𝐺 when the given center node 𝑜 in 𝑝 maps to 𝑣. Such local subgraph counting becomes important in GNNs (Graph Neural Networks), where incorporating such counts for every node in 𝐺 into the GNN architecture enhances the model’s ability to capture complex relationships within the graph 𝐺 . It is challenging to count by subgraph isomorphism, which is known to be NP-hard. In this paper, we propose a novel approach by tree-decomposition-based counting. For a complex pattern graph 𝑝 in 𝑄 , we find its best tree decomposition 𝑇 , where a node in 𝑇 represents a subgraph of 𝑝, and a node in 𝑝 may appear in multiple nodes in 𝑇. Let 𝑝(𝑇) be the pattern represented by 𝑇. Our approach is to count 𝑝(𝑇 ) by homomorphism with a constraint to count the subgraph in every tree node by subgraph isomorphism. We apply symmetry-breaking rules to reduce the cost of counting by subgraph isomorphism for every node in 𝑇 , and we develop a new multi-join algorithm to compute such counts. We confirm that our approach on a single machine using a single core can outperform the others significantly.