DeSCo: Towards Scalable Deep Subgraph Counting
Authors: Tianyu Fu
Yu Wang
Zhitao Ying
Venue: Submitted to ICLR 2023 (2023)
Keywords: subgraph counting
graph neural network
graph mining

Abstract: Subgraph counting is the problem of determining the number of a given query graph in a large targe graph. Despite being a #P problem, subgraph counting is a crucial graph analysis method in domains ranging from biology and social science to risk management and software analysis. However, existing exact counting methods take combinatorially long runtime as target and query sizes increase. Existing approximate heuristic methods and neural approaches fall short in accuracy due to high label dynamic range, limited model expressive power, and inability to predict the distribution of subgraph counts in the target graph. Here we propose DeSCo, a neural deep subgraph counting framework, which aims to accurately predict the count and distribution of query graphs on any given target graph. DeSCo uses canonical partition to divide the large target graph into small neighborhood graphs and predict the canonical count objective on each neighborhood. The proposed partition method avoids missing or double-counting any patterns of the target graph. A novel subgraph-based heterogeneous graph neural network is then used to improve the expressive power. Finally, gossip correction improves counting accuracy via prediction propagation with learnable weights. Compared with state-of-the-art approximate heuristic and neural methods. DeSCo achieves 437x improvement in the mean squared error of count prediction and benefits from the polynomial runtime complexity.


Under review as a conference paper at ICLR 2023
DESCo: TOWARDS SCALABLE DEEP SUBGRAPH COUNTING
Anonymous authors Paper under double-blind review
ABSTRACT
Subgraph counting is the problem of determining the number of given query graph large target graph. Despite being a #P problem, subgraph counting is crucial graph analysis method in domains ranging from biology and social sci- ence to risk management and software analysis. However, existing exact counting methods take combinatorially long runtime target and query sizes increase. Ex- isting approximate heuristic methods and neural approaches fall short in accuracy due high label dynamic range, limited model expressive power, and inability predict the distribution of subgraph counts in the target graph. Here we propose DeSCo, a neural deep subgraph counting framework, which aims to accurately predict the count and distribution of query graphs any given target graph. De- SCo uses canonical partition to divide the large target graph into small neigh- borhood graphs and predict the canonical count objective on each neighborhood. The proposed partition method avoids missing or double-counting any patterns of the target graph. A novel subgraph-base basddd heterogeneous graph neural network is then used to improve the expressive power. Finally, gossip correction improves counting accuracy via prediction propagation with learnable weights. Compared with state-of-the-arr approximate heuristic and neural methods. DeSCo achieves x37x improvement in the mean squared enror of count prediction and benefits from the polynomial runtime complexity.
INTRODUCTION
Given a query graph and a target graph, the problem subgraph counting is to count the num- ber of patterns, defined as subgraphs of the target graph, that graph-isomorphic the query graph Ribeiro et al. (202T).
Subgraph counting is crucial for domains including biology Takigawa & Mamitsuka (2013) ; Solé & Valverde (2008) AAdamsek et al. (2006); Bascompte & Melián (2005); Bader & Hogue 20033) social science Uddin al. (2013); Prell & Skvoretz (2008); Kalish & Robins (2006); Wasserman ct al. (994). risk management Ribeiro et al. (2017) Akoglu & Faloutsos (2013). and software
analysis Valverde & Solé (2005): Wu al. (2018).
While being an essential method in graph and network analysis, subgraph counting is a #P-complete problem Valiant (1979). Due to the computational complexity, existing exact counting algorithms are restricted to small query graphs with no more than 5 vertices Pinar et al. (2017): Ortmann & Brandes (2017) Ahmed al. (213)). The commonly used VF2 Cordella et al. (2004) algorithm fails to even count a single query of 5-node chain within a week's 's time budget on large target graph Astro Leskovec et al. (2007) with nineteen thousand nodes.
Luckily, approximate counting of query graphs is sufficient in many real-world use cases [yer et al. (0188;; Kashtan et al. (2004); Ribeiro & Silva (2010). Approximation methods can scale to large targets by substructure sampling, random walk, and color-based sampling, allowing estimation of the frequency of query graph occurrences. Very recently, Graph Neural Networks (GNNs) are employed deep learning-bai based approach to subgraph counting Zhao al. (2021): Liu et al. (2020); Chen eet al. (2020). The target graph and the query graph are embedded via a GNN, which predicts the motif count through regression task.

---

Under review as a conference paper at ICLR 2023
hotspot example
hotspot example
query
query
1.0
0.8
0.6
044
0.2
ground truth
prediction
ground truth
prediction
normalized count
The ground truth and predicted count distributions of different query graphs over the target graph CiteSeer, citation network. The hotspots are where the patterns appear most often in the target graph. The hotspots of k-chains represent overlapped linear citation chains, indicating original publications that motivate multiple future directions incremental contributions. The hotspots of k-cliques indicate research focuses, containing publications of small subdivision that builds upon all prior publications.
Figure 1:
However, there exist several major challenges with existing heuristic and GNN approaches: 1) The number of possible query graph structures and subgraph counts both grow combinatorially with respect to the graph size Sloane (2014); Read & Wilson (1998), resulting in large approximation error Ribeiro et al. (2021). The count can have high dynamic range from zero to millions, making the task much harder than most graph regression tasks which only predict single-digit number with a small upperbound. 2) The expressive power of commonly used message passing GNNs is limited by the Weisfeiler-Lehman (WL. test|Leman & Weisfeiler 1968); Chen et al. (2000) Xu et (2018). Certain structures are not distinguishable with these GNNs, let alone counting them, resulting in the same count prediction for different queries. 3) Furthermore, most existing approximate heuristic and GNN methods only focus on estimating the total count of query in the target graph Bressan et al. 2019 ; Liu al. (2020): Chen al. (2020), but not the distribution of occurrences of the patterns, as shown in Figure 1 Yet such distribution information is crucial in various applications Yin et al. 2019 Tsourakakis et al. (2017); Benson et al. (2016); Faust] (2010); Holland & Leinhard (1976).
Proposed work. To resolve the above challenges, we propose DeSCo, GNN-based model that learns to predict both pattern counts and distribution on any target graph. The main idea of DeSCo to leverage and organize local information of neighborhood patterns to predict query count and distribution in the entire target graph. DeSCo first uses canonical partition to decompose the target graph into small neighborhoods without missing and double-counting any patterns. The local infor- mation is then encoded using a GNN with subgraph-basee heterogeneous message passing. Finally, perform gossip correction improve counting accuracy. Our contributions three-fold.
Firstly, we propose a novel divide-and--onquer scheme called canonical par- tition decompose the problem into subgraph counting for individual neighborhoods. The canon- ical partition ensures that no pattern will be double counted or missed over all neighborhoods. The algorithm allows the model make accurate predictions even with the high dynamic range of labels and enables subgraph count distribution prediction for the first time. Figure [egurre[mmmosstratee DeSCo's predictions on the query graph count distribution of citation network. The count hotspots of differ- ent queries can indicate citation patterns of different scientific communities Gao & Lafferty (2017); Yang et al. (2015), which shed light on the research impact works this network.
Canonical partition.
Subgraph-based heterogeneous message passing. Secondly, we propose general approach to enhance the expressive power of any MPGNNs by encoding the subgraph structure through hetero- geneous message passing. The message type determined by whether the edge presents in certain subgraph, e.g., a triangle. We theoretically prove that its expressive power can exceed the upper bound of that of MPGNNs. We show that this architecture outperforms expressive GNNs, including GIN Xu et al. (2018) and ID-GNN You et al. (2021).
Gossip correction. We overcome the challenge of accurate count prediction by utilizing two induc- tive biases of the counting problem: homophily and antisymmetry. Real-world graphs share similar patterns among adjacent nodes, shown in Figure Furthermore, since canonical count depends
2

---

Under review as a conference paper at ICLR 2023
given Bed prodicted
given Bod
over Ged
C
(a) Canonical Partition
(b) Neighborhood Counting
(c) Gossip Correction
Σ =7
decompose to G.
predict canonical
correct error and aggregate EI
AigerG; G,
on each G2
0
count query graph in targel graph
canonical neighborhoods Ge
directed largel with predicted counts
subgraph count
Given query and target, decomposed target into multiple node-induce subgraphs, i.c., canonical neighborhoods, based on node indices. Each neighborhood contains a canonical node that has the greatest index the neigh- borhood. (b) Step 2. Neighborhood Counting: Predict the canonical counts of each neighhorhood via an expressive GNN, and assign the count of the neighborhood to the corresponding canonical node, Neighborhood counting is the local count of queries.
Figure 2: DeSCo Framework in 3 steps. (a) Step 1. Canonical Partition:
(c) Step 3. Gossip Correction: Use GNN prediction results to estimate canonical counts on the target graph through learnable gates.
on node indices, there exists antisymmetry due to canonical partition. Therefore, we propose a gossip correction phase, featuring learnable gate for propagation to leverage the inductive biases.
To demonstrate the effectiveness of DeSCo, we compare it against state-of-the-art exact and approx- imate heuristic methods for subgraph counting as well as recent GNN-based approaches Cordella et al. (2004); Bressan et al. (2019;; ( Chen et al. )2020): Liu et al. 2020), in terms of both performance and runtime efficiency. Experiments show that DeSCo enables large-scale subgraph counting that was not possible for exact methods. Compared with heuristic and neural methods, DeSCo achieves more than orders of magnitude improvement in the mean squared error of count prediction. To the best our knowledge, it is also the first method to enable accurate count distribution prediction. Furthermore, the model excels in both accuracy and runtime efficiency for larger queries, with the highest percentage of valid predictions and up to two orders of magnitude speedup over heuristic methods. Our code available alttpps: /no.ymoonnmmmuumoo/mo/ 4open. wwwencc/://eeeeeeec
RELATED WORKS
There has been an extensive line of work to solve the subgraph counting problem.
Exact counting algorithms. Exact methods generally count subgraphs by searching through all possible node combinations and finding the matching pattern. Early methods usually focus on im- proving the matching phase Wernicke & Rasche (2006); [ordella et al. (2004); Milo al. (2002) Recent approaches emphasize pruning the search space and avoiding double counting Demeyer et al. (213): Mawhirter et al. (2019); (Shi et al. (2020); Mawhirter & Wu (2019). However, exact methods still scale poorly in terms of query size (often no more than five nodes) despite much efforts Pinar al. (2017): Chen & Qian (2020).
Approximate heuristic methods. To further scale up the counting problem, approximate count- ing algorithms sample from the target graph to estimate pattern counts. Strategies like path sam- pling Wang et al. 2017);]l Tha et al. (2015), random walk Yang et al. (2018); Saha & Hasan 2015). substructure sampling Fu et al. (2020) Lyer al.) (2018), and color coding Bressan al. (2021 2018) are used to narrow the sample space and provides better error bound. However, large and rare queries are hard to find in the vast sample space, leading to large approximation error Bressan et al. 2019).
GNN-based approaches. Recently, GNNs have also been used to attempt subgraph counting. Liu ct al. (2020) uses GNNs to embed the query and target graph, and predict subgraph counts via embeddings. Chen et al. (2000) theoretically analyzes the expressive power of GNNs for counting and proposes expressive GNN architecture. Zhho et al. (2021) proposes active learning scheme for the problem. Unfortunately, large target graphs have extremely complex structures and a high dynamic range of pattern count, accurate prediction remains challenging.
3

---

Under review as a conference paper at ICLR 2023
Set each node Target graph
Rule1: ID
4 e.g.
Count pattern with O in the neighborhood
the canonical node O
Queryo-o choose d=2
6
5
Rule2: O's d-hop neighborhood, lee d=2
0
2
canonical neighborhood
C. of
(a) Target
Canonical Partition
(c) Canonical Count
Figure 3: An example of canonical partition and canonical count. (a) Choose node 5 from the tar- get graph as the canonical node (red circle). (b) Canonical partition generates the corresponding canonical neighhorhood graph. It performs an ID-restricted breadth-fisst search to find the induced neighborhood that complies with both Rulel and Rule2. (c) The corresponding canonical count is defined by the number of patterns containing the canonical node in the canonical neighborhood. De- SCo's s neighborhood counting phase predicts the canonical count for each canonical neighborhood.
PRELIMINARY
Let G. = (V, Ee) be large target graph with vertices V, and edges E, Let G. (Vg: Fig) be the query graph of interest. The subgraph counting problem C Gt) is to calculate the size of the set of patterns p = {Gp GG C G. in the target graph G2 that are isomorphic to the query graph Gg. that is, 3 bijection f Vp > Vg such that (f(v), f()) E Egg iff (u,u) u) E Ep. denoted as Gp G..
Subgraph counting includes induced and non- non-in induced counting depending on whether the pattern Gp restricted to induced subgraph Ribeiro et al. (202I). A G, (Vp. Ep) is induced subgraph of G, if Ve E E, ++ E Ep. denoted as Gp S G.. Without loss of generality, we focus on the connected, induced subgraph counting problem, following modern mainstream graph processing frameworks Hagberg et al. (2008); Peixoto (2014) and real-world applications WWog et al. (2012); Milo et al. (2002). It is also possible to obtain non-induced occurrences from induced ones with a transformation Floderus et al. (2015). Our approach
easily support graphs with node features and edge directions. But to compare with heuristic methods that only support simple graphs, we use undirected graphs without node features to investigate the ability to capture graph topology.
DESCO FRAMEWORK
In this section, we introduce the pipeline of DeSCo. To perform subgraph counting, DeSCo first per- forms canonical partition to decompose the target graph to many canonical neighhorhood graphs. Then, neighborhood counting uses the subgraph-based heterogeneous GNN to embed the query and neighborhood graphs and performs regression task predict the canonical count on each neighborhood. Finally, gossip correction propagates neighborhood count predictions over the tar- get graph. We will first introduce the model objective before elaborating on each step.
4.1 CANONICAL COUNT OBJECTIVE
The canonical count is used as a local count prediction objective for the GNN and gossip correction, after decomposing the target into small neighborhoods without missing double-counting patterns.
Canonical node. We use randomly assigned node indices on the target graph to break the symmetry of patterns. We assign the match of a k-node pattern to its canonical node based the index. Formally, the canonical node v is the node with the largest node index in the pattern: V. = max Vp-
The number of patterns that share the same canonical node is called the canonical count C, on this node as shown in Figure 3 (c). Note how the match of k-node pattern only attributed to the canonical node, since the other k-1 nodes do not satisfy
max, Vg. It also suggests that the node with a relatively larger node index will result in a larger canonical count. This characteristic will be
utilized by gossip correction discussed in Section 4.4
4

---

Under review as a conference paper at ICLR 2023
Definition 4.1 (canonical count).
CG Gt, Ue) 1[G GrIGp = Gq. max v
We prove the following Lemma in Appendix A.1
Lemma 4.1. The subgraph count of query in target equals the summation of the canonical count of query in target over all target nodes.
c(Gg. Gi)
E V.EV
Co Gt, Ue)
(2)
Lemma a.1 allows the decomposition of the counting problem into multiple neighhorhood canonical counting objectives. We use the following canonical partition for the decomposition.
4.2
CANONICAL PARTITION
Based on Lemma we define canonical partition that decomposes the target graph. Figure (a),
(b) shows an example of the canonical neighborhood, obtained by partition function P defined as:
P(Gr, Ve, d) Ge, 8. L. Ge S Gt, V. (mr V.|D(Ge, Us ve) S d, o2 S ve)
D(G,, Ui,, ve) means the shortest distance between U; and Ue on G,- We further prove:
Theorem 1. The subgraph count of query in target equals the summation of the canonical count of query in canonical neighborhoods over all target nodes. Canonical neighborhoods are acquired with partition P, given any d greater than the diameter of query.
C(Gg, Gi) ColGgg P(Gr, Vo: d), max D(Gg: Us 0z)
e.o,EV,
Definition 4.2 (Canonical partition). Given target graph Gr, canonical partition iterates over all nodes of the target G, and partition it into a of canonical neighborhoods G
G. + (G = P(Gr, Ue, d). ve E Vt}
(5)
Missing count or double counting are avoided with Theorem and Definition which is de- tailedly proven in Appendix A.2 In practice, we set d as the maximum diameter of query graphs to meet the requirements of Theorem See Appendix [A.3 for implementation of P(G Ve, d). Ap- Ae.3 shows that canonical partition reduces the complexity of the problem by dozen orders of magnitude. After canonical partition, DeSCo uses a GNN to predict the canonical count for each decomposed neighborhood. This divide-and-conquer scheme not only greatly reduces the complex- ity of each GNN prediction, but also makes it possible to predict the count distribution over the entire graph.
4.3 NEIGHBORHOOD COUNT PREDICTION
After canonical partition, GNNs are used predict the canonical count Co Gr,, ve) on any canonical neighborhood Ge.- The canonical neighborhood and the query separately embedded using GNNs. The embeddings are passed to multilayer perceptron to predict the canonical count.
To strengthen the expressive power of the GNN used in neighborhood count, propose general Subgraph- based Heterogeneous Message Passing (SHMP), which incorporates topological informa- tion through node and edge types. The canonical node of the neighborhood is treated special node type. SHMP further uses small subgraph structures to categorize edges into different edge types, and different learnable weights for each edge type.
5

---

Under review as a conference paper at ICLR 2023
type
x0.5
x0.1
P=0.5
P=0.9
xO. 5
x0.9
type
G1
undirected for homophily for antisymmetry
directed
(a) SHMP for neighborhood counting
(b) Learnable gate for gossip correction
Figure 4: (a) Proposed SHMP. Embedded with regular MP, graphs G1 and G2 are indistinguishable. While embedded with SHMP, G2 is successfully distinguished with six type II node embeddings, demonstrating better expressive power of SHMP. (b) Proposed learnable gates in the gossip model balance the influence of homophily and antisymmetry by controlling message directions.
Definition 4.3 (subgraph-based heterogeneous message passing). The SHMP uses the following equation 6 to compute each node's 's representation at layer k. Here of, denotes the message function of the h-th edge type. (i) denotes nodes that connect to node i with the h-th edge type. AGG and AGG' are the permutation invariant aggregation function such as sum, mean, or max.
x (k) =110)
x 1 AGGREH (AcdhEH(AGG)NNOO (xx (x((-11 x) (( eg,i))
(AGG,EN.(
(6)
Note that MP defined by major GNN frameworks Fey & Lenssen (0099) Wang et al. (0119) is just special case of SHMP if only one edge type is derived with the subgraph structure. We theoretically prove that SHMP can exceed the upper bound of MP in terms of expressiveness in Appendix [B.]
For example, Figure 4 demonstrates that triangle-based heterogeneous message passing has bet- ter expressive power. Regular MPGNNs fail to distinguish different d-regular graphs G1 and G2 because of their identical type messages and embeddings, which is common problem of MPGNNs You et al. (202I). SHMP, however, can discriminate the two graphs by giving different embeddings. The edges are first categorized into two edge types based whether they exist in any triangles (edges are colored purple if they exist in any triangles). Since no triangles exist in G2, all of its nodes still receive type messages. While some nodes of G1 now receive type II messages with two purple messages and one gray message in each layer. As result, the model acquires not only the adjacency information between the message sender and receiver, but also information among their neighbors. Such subgraph structural information improves expressiveness by incorporating high-order information in both the query and the target.
4.4 GOSSIP CORRECTION
Given the count predictions Č. output by the GNN, DeSCo uses gossip correction to improve the prediction quality, enforcing different homophily and antisymmetry inductive biases for different queries. Gossip correction uses another GNN to model the error of neighborhood count. It uses the predicted C. as input, and the canonical counts C. as the supervision for corresponding nodes in the target graph.
Two different inductive biases are used to improve the accuracy. 1) Homophily. Since the neighborhoods of adjacent nodes share much common graph structure, they tend have similar canonical counts as shown in Figure]] I This is called the homophily of canonical counts. 2) Antisym- metry. As mentioned in Section[4.1 for nodes with similar neighborhood structures, the one with larger node index has a larger canonical count, resulting in antisymmetry of canonical counts. See the example target graph in Figure which satisfies the inductive biases. Appendix Appendix[[further further shows that homophily and antisymmetry are mutually exclusive for different queries, which corresponds to our gossip model design in Figure (b).
Motivation.
Gossip correction with learnable gates. As shown in Figure 4b). The proposed gossip model multiplies a learnable gate for the message sent from the node with the smaller index, and 1 P from the reversed one. P is learned from the query embedding. For different queries, P ranges from 0 to 1 to balance the influence of homophity and antisymmetry. When + 0.5, messages from the smaller indexed node and the reversed one are weighed equally. So simulates undirected message

---

Under review as a conference paper at ICLR 2023
passing that stress homophity by taking the average of adjacent node values. When the gate value moves away from 0.5. the message from a certain end the edge is strengthened. For example, when P - 1, the node values only accumulate from nodes with smaller indices to nodes with larger ones. So that it simulates directed message passing that stress antisymmetry of the transitive partial order of node indices.
The messages of MPGNNs are multiplied with 9jz on both edge directions. With the learnable gates, the model now better utilizes the mutually exclusive inductive biases for better error correction.
x; x =)())) (xx" (x((-1)) AGGJEN()95 ((h)) (x!6-1) x) ,e;))) 9ji P
(P
U U
Final count prediction. The gossip-corrected neighborhood count is more accurate estimation of the canonical count and distribution. The summation of the (corrected) neighborhood count is the unbiased estimation of subgraph count the whole target graph as Theorem T states.
EXPERIMENTS
We compare the performance of DeSCo with state-of-the-we approximate heuristic and neural sub- graph counting methods. The runtime advantage also demonstrated with popular exact methods. Extensive ablation studies further show the benefit of each component of DeSCo.
5.1
EXPERIMENTAL SETUP
*gruphs
Avg.
Avg. Redges
Dataset
CiteSeer
Cora
MUTAG
188
17.93
19.79
Query-Size
COX2
ENZYMES
600
32.63
62.14
LRP
GPU out of memory
overflow
DIAMNet
1.110
1.282
1.101
1.074
1.108
1.037
CITESEER
3.3K
4.5K
2.7K
5.4K
DeSCo
0.006
0.133
0.125
0.302
0.249
0.676
Table Graph statistics of datasets used in experiments.
Table 2:
Normalized MSE performance of neural methods on large targets with standard queries.
Datasets. We use real-world datasets from various domains as the target graphs, including chem- istry(MUTAG Debnath et al. (1991). COX2 Rossi & Ahmed (2015)) biology(NNZYMESS |Brg- wardt et al. (2005)), and citation networks(CiteSeee Giles et al. (1998), Cora McCallum et al. (2000). We also generate large synthetic dataset with mixed graph generators Holme & Kim 2002): ; Albert & Barabási 20000; Watts Strogatz (1998); Erdos et al. (1960) to cover diverse graph characteristics. All the datasets are treated undirected graphs without node edge features in alignment with the setting of the approximate heuristic method Bressan et al. (2019). The stan- dard query graphs include all non-isomorphic, connected, undirected graphs with node size 3 - 5. The ground truth total counts and canonical counts of these queries are generated with the exact counting method all the target graphs from the above datasets.
Pretraining. To perform subgraph counting on any target graph, we first pre-train all the neural methods with the target-query pairs from the synthetic dataset and the standard queries of size 3 5. The neural baselines are trained and tested with the total subgraph count objective. After pre- training. DeSCo can be evaluated by predicting the total count in alignment with the baselines. Unless specified, the trained models are directly tested with standard queries and the targets from unseen, real-world datasets. Therefore, our evaluation, DeSCo only needs to trained once from scratch across common datasets and tasks.
Baselines. For neural-based approaches, we adopt state-of-the-art subgraph counting GNNs, LRP Chen et al. (2020) and DIAMNet Liu et al. (2020). For the approximate heuristic count- ing method, we choose the oftte-o-thhe-e art color-based sampling method MOTIVO Bressan et al. 2019). It uses color coding to greatly narrow the sample space with efficient c++ implementation. For exact counting methods, we consider V/2 et al. (2004) and IMSM Sun & Luo 2020
VF2 is widely used in major graph processing frameworks Hagberg al. (008
Peixoto 2014
7

---

Under review as a conference paper at ICLR 2023
MUTAG
ENZYMES
MOTIVO
percentago
DIMN
0.8
0.8
0.8
DeSCorzero-hog
DaSCo
2
normalized
normalized square
normalized
The accumulative distributions of normalized square error of large query-target pairs. The x-axis is clipped at 5. Given any square error tolerance bound (x-axis), DeSCo has the highest percentage of predictions that meet the bound (y-axis). DeSCo(zero-shon generalizes to unseen queries with competitive performance over specifically trained baselines.
Figure 5:
IMSM is common framework that combines optimizations from multiple exact counting meth- ods He & Singh (2008; [onnnci et al. (2013); Bhattarai et al. (2019); Han et al. (2019). Refer to Appendix D.3 and foror the configuration details of the baselines.
Evaluation metric. We follow the previous works Chen et al. ; Liu et al. (2020) and use mean square error (MSE) of total subgraph count prediction each query size are normalized by dividing the variance of the ground truth counts.
evaluation metric. The MSE values of
5.2 NEURAL COUNTING
Table summmrrzes the normalized MSE for predicting the subgraph count of twenty-nine standard query graphs on datasets consisting of many target graphs. With canonical partition, neighborhood counting, and gossip correction, DeSCo demonstrates 437x improvements against the best baseline on average. This demonstrates that neural subgraph counting is truly reliable in real-world problems, even for smaller queries of size 5. The relative count error under the q-error metric is also discussed in Appendix [.I] DeSCo also highlights the accurate count distribution prediction for the first time. The distribution prediction realizes 0.23 normalized MSE as discussed in Appendix
Dataset
MUTAG
COX2
ENZYMES
Query-Size
3
5
3
5
3
5
MOTIVO
1.1E+2
7,5E+2
4.8E+3
3.4E+2
2.9E+3
3.2E+4
1,3E+2
6.0E+2
3.6E+3
LRP
1.6E+0
1.1E+0
1.0E+0
1,9E+0
1,3E+0
1.1E+0
2,0E+0
1.3E+0
1.1E+
DIAMNet
1.7B-1
1.1E-
3.5E-1
3.0B-1
2.4E-1
5.0E-1
7.2E-1
5.6E-1
8.9E-1
DeSCo
7.3E-5
5.2F-4
1.1E-2
2.3E-5
9.5E-
7,2E-3
1.1E-3
2.0E-3
1.0E-2
Table 3: Normalized MSE of approximate heuristic and neural methods on subgraph counting of twenty-nine standard queries.
5.3 SCALIBILITY
Generalization. Obtaining ground truth for large queries and targets via exact counting is extremely expensive and can take months, only scalable queries and targets with the following setting in Section 5.3 Here we demonstrate that with minimal pre-training, the model is able to generalize and make reliable predictions for larger queries and targets.
Large queries. For each query size between 6 to 13, we select two queries that frequently appear ENZYMES. A smaller synthetic dataset with 2048 graphs is used generate the ground truth for these sixteen queries. All the models are pre- traitrined with standard queries. All the models, except for DeSCo(zero-shot) are fine-tuned with larger queries on the small synthetic dataset. DeSCo(zero- shot) is used to show the generalization power of DeSCo for unseen queries. The distributions of the square error of each query-target pair are shown in Figure The square errors are normalized with the variance of all ground truth counts.
Large target. We also test the models on large target graphs shown in Table 2. The maximum ground truth count of standard queries goes up to 3.8 x 10 and 3.3 x 10" on CiteSeer and Cora, thus a hard task. When directly tested, LRP and DIAMNet overflow normal float precision. So we tune all the models from the same domain. LRP either exceeds 32GB GPU memory in tuning, or predicts infinite caused by overflow.
graph and test the other to simulate transfer learning between graphs
8

---

Under review as a conference paper at ICLR 2023
5.4 ABLATION STUDY
We explore the effectiveness of each component of DeSCo through the ablation study by removing each component.
Ablation of canonical partition. We remove the canonical partition of DeSCo and train it with the objective of subgraph count on the whole target, the same as other neural baselines. This demon- strates the effectiveness of the divide-and-conquce scheme of canonical partition.
Dataset Query-Size
MUTAG
COX2
ENZYMES
3
w/o P W P
1.8E-2
1.0F-2
6.4E-2
2.1E-2
1.5E-2
2.5E-2
7.3E- 1
1.7E+0
3,9E+0
4.2E-5
1.4E4
7.8E-3
1.8E-5
2.3E-5
1.5E-
9.6E-
3.0E-3
1.2E-2
Table 4: Normalized MSE performance with or without canonical partition. Since gossip correction relies on the output of neighborhoods, it's also removed for both for a fair comparison.
Ablation of subgraph-based heterogeneous message passing. We use our proposed SHMP to improve the performance of GraphSAGE by transforming its standard message passing to heteroge- neous message passing. We use triangle as the subgraph to categorize heterogeneous edges as shown in Figure a). Note how SHMP outperforms expressive GNNs, including GIN and ID-GNN.
Dataset
MUTAG 4
COX2
ENZYMES
Query-Size
5
3
GCN
1.7E+1
7.5E+0
8.2E-1
1,6E+01
6.6E+0
5.1E-1
8.7E-1
3.6E-1
7.7E-
SAGE
9.2E-4
4.8E-3
1.5E-2
2.6B-5
3.5E-
6.0E4
3.0E-2
9.6E-2
2.4E-1
GIN
1.4H-4
3.0E-3
3.0E-2
6.6H-5
4.8E-
1.0E-2
4.0H-2
1.4E-1
3.0E-
ID-GNN
4.2E-5
3.7E-4
7.4E-3
1.6E-5
1.4E-4
2.2E-3
8.8E-4
5.5E-3
2.0E-2
SAG
4.2E-5
1.4E-4
7.8E-3
1.88-5
2.3E-5
1.5E-
9.6E-4
3.0E-3
1.2E-2
Table 5: Normalized MSE performance with different GNN models for neighborhood counting.
Ablation of gossip correction. The normalized MSE of direct summation of neighhorhood counts and the summation after gossip correction are compared to show the effectiveness of gossip correc- tion. We use ENZYMES and Cora to do the ablation study since the error of other graphs is already very low with only canonical partition and neighborhood counting.
Dataset
ENZYMES
Cora
Query-Size
5
w/o gossip
9.6E-4
3.0E-3
1.2E-2
3.0E-1
2.5E-1
6.8E-1
w gossip
1.1E3
2.0E-3
1.0E-2
2.9E-
1.8E-
6.3E-1
Table 6: The normalized MSE performance with and without gossip correction.
5.5 RUNTIME COMPARISON
DeSCo benefits from polynomial time complexity: O(F + (V, + + O(F3/2 + V₁)- In contrast, both the exact methods VF2, IMSM, and the approximate heuristic method MOTIVO suffer from exponentially growing runtime with regard to the query size in practice. Experiments show that DeSCo scales much larger queries than the exact methods and achieves up 120x speedup over the approximate heuristic method for large queries. The detailed runtime comparison discussed in Appendix
CONCLUSION
We propose DeSCo, neural network based framework for scalable subgraph counting. With canon- ical partition, subgraph-basee heterogeneous message passing, and gossip correction, DeSCo aceu- rately predicts counts for both large queries and targets. It demonstrates two magnitudes of improve- ments in mean square error and runtime efficiency. It additionally provides the important locational distribution of patterns that previous works cannot.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Balázs Adamcsek, Gergely Palla, Illés J. Farkas, Imre Derényi, and Tamás Vicsek. Cfinder: locating cliques and overlapping modules biological networks. Bioinformatics, 222)):1021 2006.
Nesreen K Ahmed, Jennifer Neville, Ryan Rossi, and Nick Duffield. Efficient graphler counting for large networks. In 2015 IEEE International Conference Data Mining, pp. 1-10. IEEE, 2015.
Leman Akoglu and Christos Faloutsos. Anomaly, event, and fraud detection in large network datasets. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 773-774, ACM, 2013.
Réka Albert and Albert-László Barabási. Topology of evolving networks: local events and univer- sality, Physical review letters, 85(24):5234, 2000.
Gary D. Bader and Christopher W. V. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(1):2-2, 2003.
Jordi Bascompte and Carlos Melián. Simple trophic modules for complex food webs. Ecology, 86 (11):2868-288) 2873, 2005.
Jacob Benesty, Jingdong Chen, Yiteng Huang, and Israel Cohen. Pearson correlation coefficient. In Noise reduction in speech processing, pp. 1-4. Springer, 2009.
Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex net- works. Science, 353(6955):133-66. 2016.
Bibek Bhattarai, Hang Liu, and H Howie Huang. Ceci: Compact embedding cluster index for scal- able subgraph matching. In Proceedings of the 2019 International Conference on Management of Data, pp. 1447-1462, 2019.
Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A sub- graph isomorphism algorithm and its application biochemical data. BMC bioinformatics, 14 (7):1-13, 2013.
Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppL.I;: i47-i56, 2005.
Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data (TKDD), 12 (4):1-25, 2018.
Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Motivo: fast motif counting via succinet color coding and adaptive sampling. Proceedings of the VLDB Endowment, 12(11):1651-1663 2019.
Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Faster motif counting via succinct color coding and adaptive sampling. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(6):1-27, 2021.
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, and Hadrien Mélot. House of graphs: database of interesting graphs. Discrete Applied Mathematics, 161(1-2):31131444 2013.
Jingji Chen and Xuehai Qian. Dwarvesgraph: A high-performance graph mining system with pattern decomposition. arXiv preprint arXiv:2008. 09682, 2020.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count
substructures? ArXiv, abs/2002.00005, 2020.
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelli- gence, 26(10):1367-133 2004.
10

---

Under review as a conference paper at ICLR 2023
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activitn relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2)788-777, 1991.
Sofie Demeyer, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, and Piet Demeester. The mndex-based subgraph matching algorithm (isma): fast subgraph enumeration large net- works using optimized search trees. PloS one, 8(4) 183, 2013.
Evan Donato, Ming Ouyang, and Cristian Veguero-Isalgues Triangle counting with multi-core computer. 2018 IEEE High Performance extreme Computing Conference (HPEC), pp. 1-7, 2018.
Paul Erdös, Alfred Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):1(6 1960.
Katherine Faust. A puzzle concerning triads in social networks: Graph constraints and the triad census. Social Networks, 32(3):221-233, 2010.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Peter Floderus, Mirostaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Induced subgraph isomorphism: Are some patterns substantially easier than others? Theoretical Computer Science, 109:119-128, 2015.
Tianyu Fu, Ziqian Wan, Guohao Dai, Yu Wang, and Huazhong Yang. Lessmine: Reducing sam- ple space and data access for dense pattern mining. In 2020 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1-7. IEEE, 2020.
Chao Gao and John Lafferty. Testing for global network structure using small subgraph statistics. 2017.
arXiv preprint arXiv:
Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pp. 89-98, 1998.
Aric Hagherg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and func- tion using networkx. Technical report, Los Alamos National Lab(LLNN), Los Alamos, NM (United States), 2008
Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook-Shin Han. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the 2019 International Conference on Management of Data, pp. 1429- 1446, 2019.
Huahai He and Ambuj K Singh. Graphs-at-a-timer query language and access methods for graph databases. Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 405-418, 2008
Paul W Holland and Samuel Leinhardt. Local structure in social networks. Sociological methodol- ogy, 7:1-45, 1976.
Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Physical review E, 65(2):026107, 2002.
Alon Itai and Michael Rodeh. Finding a minimum circuit in graph. In Proceedings of the ninth annual ACM symposium on Theory of computing, pp. 1-10, 1977.
Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. (ASAP): Fast, approximate graph pattern mining at scale. In 13th USENIX Sympo- sium Operating Systems Design and Implementation (OSDI 18), pp. 745-761, 2018.
Madhav Jha, C Seshadhri, and Ali Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Proceedings of the 24th international conference on world wide web, pp. 495-505, 2015.
11

---

Under review as a conference paper at ICLR 2023
Yuval Kalish and Garry Robins. Psychological predispositions and network structure: The relation- ship between individual predispositions, structural holes and network closure. Social networks, 28( (8(1))56-844 84, 2006.
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimat- ing subgraph concentrations and detecting network motifs. Bioinformatics, 20(11):1746-177) 2004.
AA Leman and Boris Weisfeiler. A reduction a graph to a canonical form and an algebra arising during this reduction. Neuchno-TTcchnichssaay Informatsiya, 2(9): 1968.
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007.
Xin Liu, Haojie Pan, Mutian He. Yangqiu Song, and Xin Jiang. Neural subgraph isomorphism counting. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Daniel Mawhirter and Bo Wu. Automine: harmonizing high-level abstraction and high performance for graph mining. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pp. 509-523, 2019.
Daniel Mawhirter, Sam Reinehr, Connor Holmes, Tongping Liu, and Bo Wu. Graphzero: Breaking symmetry for efficient graph mining. arXiv preprint urXivv:9111 12877, 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594)8824 827, 2002.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. ArXiv, abs/ abs/1810.02224, 2019.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural networks: the official journal of the International Neural Network Society, 130:195-205, 2020.
Mark Ortmann and Ulrik Brandes. Efficient orbit-aware triad and quad census in directed and undirected graphs. Applied network science, 2(1):1-17, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Tiago P. Peixoto. The graph-tool python library. figshare, 2014. doi: wtt.000//m...isshaaae 164194.
URL http:://figsharree http://ghharee....aaaaaaaaaaa httpa//rw..cc....aacc/eee/aaaapa
Ali Pinar, Seshadhri, and Vaidyanathan Vishal. Escape: Efficiently counting all 5-vertex sub- graphs. In Proceedings of the 26th international conference world wide web, pp. 1431-1440, 2017.
Christina Prell and John Skvoretz. Looking at social capital through triad structures. Connections, 28(2):4-16, 2008.
Ronald Read and Robin Wilson. An atlas of graphs, volume 21. Clarendon Press Oxford, 1998.
Bernardete Ribeiro, Ning Chen, and Alexander Kovacec. Shaping graph pattern mining for financial risk. Neurocomputing, 2017.
12

---

Under review as a conference paper at ICLR 2023
Pedro Ribeiro and Fernando Silva. Efficient subgraph frequency estimation with g-tries. In Interna- tional Workshop on Algorithms in Bioinformatics, pp. 238-249. Springer, 2010.
Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2):1-36, 2021.
Ryan Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. hts/attp:///etttooepessssss
com
Tanay Kumar Saha and Mohammad Al Hasan. Finding network motifs using meme sampling. In Complex Networks VI. pp. 13-24. Springer, 2015.
Tianhui Shi, Mingshu Zhai, Yi Xu, and Jidong Zhai. Graphpi: High performance graph pattern matching through effective redundancy elimination. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEEE, 2020.
Neil James Alexander Sloane. A handbook of integer sequences. Academic Press, 2014.
Ricard V Solé and Sergi Valverde. Spontaneous emergence of modularity in cellular networks.
Journal of The Royal Society Interface, 5(18): 2008
Shixuan Sun and Qiong Luo. In-memory subgraph matching: An in-depth study, In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1083-1098, 2020.
Ichigaku Takigawa and Hiroshi Mamitsuka. Graph mining: procedure, application drug discovery and recent advances. Drug discovery today, 18(1-2):50-57, 2013.
Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. Proceedings of the 26th International Conference on World Wide Web, pp. 1451-1460, 2017.
Shahadat Uddin, Liaquat Hossain, et al. Dyad and triad census analysis of crisis communication network. Social Networking, 2(01):32, 2013.
Leslic G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Com- puting, 1979.
Sergi Valverde and Ricard Solé. Network motifs in computational graphs: A case study in soft- ware architecture. Physical Review E, 72(2):026107, 2005.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis. Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint /909.0999..00 155 2019.
Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John CS Lui. Don Towsley, Jing Tao, and Xiaohong Guan. Moss-5: A fast method approximating counts 5- node graphlets in large graphs. IEEE Transactions on Knowledge and Data Engineering, 30(1):
73-86, 2017.
Stanley Wasserman, Katherine Faust, et al. Social network analysis: Methods and applications. 1994.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks nature, 393 (6684):440 442, 1998.
Melanie Weber. Curvature and representation learning: Identifying embedding spaces for relational data. 2019.
Sebastian Wernicke and Florian Rasche. Fanmod: tool for fast network motif detection. Bioinfor- matics, 22(9): 152-1153, 2006.
13

---

Under review as a conference paper at ICLR 2023
Elisabeth Wong, Brittany Baur, Saad Quader, and Chun-Hsi Huang. Biological network motif de- tection: principles and practice. Briefings in bioinformatics, 13(2):20--215, 2012.
Peng Wu, Junfeng Wang, and Bin Tian. Software homology detection with software motifs based on function-call graph. IEEE Access, 6:19007-19017, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810.0000 2018.
Chen Yang, Min Lyu, Yongkun Li, Qianqian Zhao, and Yinlong Xu. Ssrw: scalable algorithm for estimating graphlet statistics based on random walk. In International Conference on Database Systems for Advanced Applications, pp. 272-288. Springer, 2018
Guan-Can Yang, Gang Li, Chun-Ya Ya Li, Yun-Hua Zhao, Jing Zhang, Tong Liu, Dar-Zen Chen, and Mu-Hsuan Huang. Using the comprehensive patent citation network (cpe) to evaluate patent value. Scientometrics, 105(3)1319-1146, 2015.
Hao Yin, Austin Benson, and Jure Leskovec. The local closure coefficient: new perspective on network clustering. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 303-311, 2019.
Jiaxuan You, Jonathan Gomes Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. arXiv preprint arXiv:2101.10320 2021.
Kangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. A learned sketch for subgraph counting. Proceedings of the 2021 International Conference on Management of Data, 2021.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11168-11176, 2021.
14

---

Under review as a conference paper at ICLR 2023
A CANONICAL PARTITION
A.1 PROOF OF LEMMA 4.1
Proof. Following the notions from Section 3 given a query graph Gg and a target graph Gt, the node-induced count defined the number of G,'s node-induced subgraph, pattern, G, that is isomorphic to Gg. We denote the set of all Gp as M.
M [G, - G. Gg} c(G G,)= [M]
(8)
(9)
Assuming that G2 has k nodes. Then, under the inde-eddueed definition, given G₁, we can use the k-node set V [ole E Gp} of Gp to represent the pattern.
We can decompose the set of all patterns MI into many subsets M. based on the maximum node index of each Gp M.
Mc = GGp S GGGGp Gq max V c}
(10)
This maximum-ines index decomposition is exclusive and complete: every Gp has single corresponding maximum node index. So we have the following properties:
Ve # j, M. n M, = Ø
(11)
MV-
M Me
(12)
Thus, the node-induced count in Equation can be rewritten using the inclusion-exclusion principle.
-
CiG
Me
IV|-1
[Mal
+
Σ
(-1)*
Mi, n. n Mull
(13)
k=1
S
Σ
[Mal
According to the definition of canonical count in Equation Lemma 4.1 is proven with Equation 13
Co vo) = MMl. Thus,
A.2 PROOF OF THBOREM 1
Proof. By the definition of M. in Equation 10 have corollary.
Corollary 1.1. Denote v 's index as c, D as the shortest path length between two nodes. Any graph in M. has node and has the same graph-level property with Gap. e.g,, diameter.
VGp Mc, E Vp, max. D(Gps D1, v..eVV v.o.EV,
max D(G U/, Uz)
(14)
15

---

Under review as a conference paper at ICLR 2023
The distance between ve and any nodes of G2 in M. is bounded by ma D 22 U2) as shown in corollary [.I ve '' d-hop ego-graph.
So we can further know that graphs in Mc are mode-induced subgraphs of
GGp E M,. Gdd-ego C Gt, Va-ego = {uz E VV) vi ve) S
&d) ddys.t. s. Gp Gd-ego (15)
Given Equation 10 it is also clear that all graphs in M. have smaller node indices than c.
GGp E Mc, small S Gt, Vsmall = {u, E vil4 - s. = Gsmail
(16)
With Equation
15 and 16 we know that all the graphs in M, are subgraphs of P(G,, Vo: d) defined Equation 3 Thus, with respect to Equation we can redefine M, as follows.
Mc (Gp S P(G,, Ne. d)|G, , Gg. max c}
(17)
Vp
Combining Equation 13 with Equation 17
Theorem
iis proven.
A.3 IMPLEMENTATION OF CANONICAL PARTITION
Algorithm Index-restricted breadth-fire first search
V. + {ueh. Vfront f {ve) while depth < <d do
Vodd < {uly E Un,eVeronne (0y((1,) E Eij.u v S ve}
Virant Vada \ Ve
V. - V.U S.UVsrom front
end while
Ge + +Ve, t.). S.
The canonical partition is implemented using an index-restricted breadth-first search (BFS), Com- pared with regular BFS, it restricts the frontier nodes to have smaller indices than that of the canon- ical node. The time complexity of canonical partition equals the BFS each neighborhood Gn = (Vn, En), which is > OVV, + Ex) = OVV, x (Vn En)).
A.4 COMPLEXITY BENEFIT OF CANONICAL PARTITION
We discuss the computational benefit of the canonical partition method in this section.
Search space reduction. Canonical partition uses the divide-and-conquer scheme to bring about drastic search space reduction. We denote the complexity of searching and counting all subgraphs on size Vi target graph as S(V).. Canonical partition divides the original problem into subproblems with the total search space of Eiv, S(Vn.). where Vn,, stands for the size of canonical neighborhoods. Thanks to the sparse nature of real-world graphs, Vn,5 are generally small, even for huge target graphs. So with canonical partition, the search space is drastically reduced.
We conduct experiments on real-world graphs to show how canonical partition fundamentally re- duces the search space. Figure shows the computational complexity with different assumptions on the form of S. VF2 Cordella et al. (2004) claims that the asymptotie complexity for the problem ranges from ( O(V!x V) in best and worst cases. Under such assumptions of S, the average worst-case complexity reduced by a factor of 1/1070 with canonical partition, while the average observe exponential runtime growth of the subgraph counting problem. Thus, under the assumption that S(V) = 2 the average complexity is also reduced drastically by factor of 1/10'1 with canonical partition.
best-case complexity stays in the same magnitude. Empirically,
Redundant match elimination. Canonical partition, along with the canonical count definition, eliminates the redundant automorphic match of the query graph. Previous works Mawhirter &
16

---

Under review as a conference paper at ICLR 2023
1E+200
VF2 complexity range
1E+175
wlo P W P
complexity (big O)
1E+150
2 complexity w/o P w '
1E+125
1E+100
1E+75
1E+50
1E+25
1E+00
MUTAG
COX2 target dataset
ENZYMES
Figure 6: The complexity of subgraph counting with and without canonical partition on different target datasets. The complexity for the VF2 exact subgraph counting method is O(V2) to O(VxxV). The O(2%) complexity estimates the empirically observed average complexity.
Wu 2019);; Shi et al. (2020) have shown that the automorphism of the query graph can cause a large amount of redundant count. For example, the triangle query graph G, has three sym- metric nodes. We denote the triangle pattern Gp S G, and the bijection R R as (Upo: Upp Upp) + (Ngo Ugg Ug2). ). For the same pattern, there exist six bijections {f (U/a Upr Upz) ) + (Fgrr Mays U/ (1, e (,, where Perm(x, y, denotes all 3! per- mutations of (Ir, y, z).
Canonical partition eliminates such redundant bijections by adding asymmetry, the canonical node. As discussed in Equation 1 by attributing the count to only one canonical node, the bijection fa can be rewritten as a R + R function, fe (Upo Up Up2) + maxy(U,, 19 2g means that each query corresponds to only one bijection instead of six, thus preventing double counting and reducing the computational complexity.
Reduction in the dynamic range of labels. Canonical partition also reduces the dynamic range of the subgraph count labels, which makes the regression task easier for the neural network as discussed in Section I The detailed statistics of the dynamic range shown in Appendix D.2 The canonical
partition reduces the dynamic range of labels to 1 1/3 on average in Figure 9
B EXPRESSIVE POWER OF SHMP
triangle-edge
regular-edge
Figure 7: Examples of 1-SHMP distinguishable graphs. Any graph pair of each row cannot be distinguished by the 1-WL test. While with one layer of triangle-based SHMP, the histogram of the triangle-edge can distinguish all these graph pairs.
17

---

Under review as a conference paper at ICLR 2023
B.1 THEORETICAL COMPARISON WITH REGULAR MESSAGE PASSING
Previous work Xu et al. (0118) has shown that the expressive power of existing message passing GNNs upper-bounded by the 1-WL test, and such bound can be achieved with the Graph Isomor-
phism Network (GIN). We prove the expressive power of SHMP with the following Lemma.
Lemma B.I. The SHMP version of GIN has stronger expressive power than the 1-WL test.
By setting Vo = o² and AGG' = AGG, SHMP from Equation 6 becomes an instance GIN, which proves that SHMP-GIN is least as expressive GIN the 1-WL test. The examples Figure 7 and Table further prove that one layer of triangle-based SHMP-GIN can distinguish certain graphs that the I-WL test cannot. Thus, SHMP-GIN has stronger expressive power than the 1-WL test, exceeding the upper bound of regular message passing neural networks.
B.2 EXPERIMENTS ON REGULAR GRAPHS
To further illustrate the expressive power of SHMP, we show the number of graph pairs that are WL indistinguisaable but SHMP distinguishable in Table 7 We collect all the connected, d-regular graphs of sizes six to twelve from the House of Graphs Brinkmann et al. (2013). Among these 157 graphs, 654 pairs of graphs are indistinguishable by the I-WL test, even with infinite iterations. In comparison, only 208 pairs are indistinguishable by the triangle-based SHMP with single layer. So
68% of typical fail cases of the 1-WI. test are easily solved with SHMP. Some examples are shown in Figure
Graph Size
7
8
10
11
12
Number of Graphs
5
4
15
10
30
88
Number of Graph Pairs
10
6
105
45
435
10
3828
WL Indistinguishable SHMP Indistinguishable
1
19
64
555
0
1
4
4
26
173
Error Reduction
100.0%
0.0%
78.9%
69.2%
59.4%
100.0%
68.8%
Table 7: The number of indistinguishable d-regular graph pairs for the WL-test and SHMP.
B.3 DISCUSSION ON SUBSTRUCTURE ENILANCED GNNS
Previous substructure enhanced GNNs Morris et al. (2019) Nikolentzos et al. (2020) focus on the idea of high-order abstractions of the graph. However, the direct instantiation of all high-order substructures poses significant runtime overhead. which is unfriendly for the large-scale subgraph counting problem. For example, MMoris et al. (2019) has add k-combinatorially many nodes to represent the corresponding k-order substructure. This results in massive memory overhead and heavy message passing computation. Though both of them use the three-node substructure informa- tion, experiments show that the five-layer DeSCo is 3.51 x faster than the five-layer 1 1-2-3-GNN Mor-| ris et al.] (2019) when embedding the same COX2 dataset. In contrast, DeSCo's subgraph-bas heterogeneous message passing (SHMP) focuses on the idea of distinguishing different local graph structures. By categorizing the messages on the original graph, DeSCo efficiently uses the same amount of message passing computation traditional MPGNNs. while providing better expressive power.
C HOMOPHILY AND ANTISYMMETRY ANALYSIS
Example and observation. The homophily and the antisymmetry are two important inductive biases for the canonical count. The target graph in Figure serves as a vivid example. The numbers the green square indicate the canonical count value of each node. On the one hand, note that the adjacent nodes 3, 5, and have the same count value of Adjacent nodes 0, 1, and 2 also have the same value, O. This homophily inductive bias suggests that taking average of the adjacent node values can reduce the prediction error of individual nodes. On the other hand, though node and node have similar neighborhood graph structures, node 5 with larger node index has higher canonical
18

---

Under review as a conference paper at ICLR 2023
0.5
index-count correlation
0.4
0.3
0.2
0.1
0.0
0.2
0.4
0.6
0.8
1.0
homophily ratio
Figure 8: The quantification of homophily and antisymmetry of standard queries on the ENZYMES target graph. The extent homophily and the antisymmetry are measured by the homophily ratio and the index-count correlation, respectively. The color corresponds the x-coordinate (homophily) minus the y y-coordinate (antisymmetryy) Note how different queries emphasize one of the two induc- tive biases.
count value. It corresponds to the definition of canonical count as discussed in Section 4.1 This antisymmetry inductive bias suggests that the embedding phase for two structurally similar nodes with different node indices should also be different.
Quantization. We quantify the homophily and the antisymmelry inductive biases. For homophily, we treat the canonical count as the node label and use the homophily ratio from /hhu al. (202T) to quantify how similar the count is between adjacent nodes. The homophily ratio ranges from 0 to 1. The higher the homophily ratio is, the more similar the labels will be between adjacent nodes. For antisymmetry,
the Pearson correlation coefficient Benesty et al. (2009) between the node index and its canonical count as the quantification metric. We quantify the different homophily and antisymmetry for different queries the ENZYMES target graph.
Key insight. As shown in Figure 8 the key insight is that homophily and the antisymmetry generally should suppress the other. Based on
have negative correlation such observation, we design the gossip correction model with learnable gates to imitate the mutually exclusive relation between the two inductive biases for different queries. As shown in Figure (b), the proposed learnable gate balances the influence of homophily and antisymmetry by controlling the direction of message passing. The gate value is trained to adapt for different queries imitate different extents of homophily and antisymmetry.
0.82. So the emphasis
D EXPERIMENTAL SETUP
D.I SYNTHETIC DATASET
The DeSCo can be pre-trained once and be directly applied to any targets. So we generate synthetic dataset with 6400 graphs, along with the ground truth count of all twenty-nine standard queries (queries of sizes 3. 4, 5).
The synthetic dataset generates each graph with generator from the generator pool. The pool con- sists of four different graph generators: the Frdös-Rényi (ER) model Frdōs et al.) (T960), the Watts- Strogatz (WS) model Watts & Strogatz (1998), the Extended Barabási-Alber Albert (Ext-BA) model bert Barabási 2000), and the Power Law (PL) cluster model Holme Kim (0022). The expected graph size of each generator is uniformly chosen from 5 to 50. An additional 2% PL model is used to generate very large graphs with 50 to 250 nodes.
To generate n-node graph, for the ER model, the edges are added with Beta probability dis- tribution p ~ 0.8Beta( 1.3, 1.3n/ log, n 1.3). For the WS model, each node connects to K nBBtaa113, 1.3n/ log, 1.3) neighhorhoods, with rewiring probability Beta(2,
19

---

Under review as a conference paper at ICLR 2023
For the Ext-BA model, the edges attached each node with uniform probability distribution m ~ U(1, 2 log, n). The probability of adding edges and rewiring both conform to the clapped exponential distribution p max(0..2, E(20)). For the PL model, the edges are attached to each node with uniform distribution m ~ U(1, 2ogg n). The triangle is added with p ~ U(0, 0.5).
D.2 QUERY GRAPHS
They form the complete set of all non-isomorphic, connected, undirected graphs with three to five nodes. Figure [00 shows all sixteen large query graphs discussed in Section 5.3 They are frequent subgraphs with six to thirteen nodes in the ENZYMES dataset.
Figure D shows all twenty-nine standard queries discussed Section 5.1
The figures also show the dynamic range (DR) of the ground truth count of these queries on the target graphs from the ENZYMES dataset. The canonical counts' dynamic range the corre- sponding neighborhoods is also shown. Note how canonical partition reduces the dynamic range of the regression task for GNNs.
Gg
DR Gr
DR Ge
Gg
DR Gr
DR Ge
Gg
DR Gt
DR Ge
339
33
1773
288
37
15
61
12
195
48
37
19
282
48
391
71
19
12
778
107
499
121
62
25
244
42
386
86
23
13
67
15
44
13
24
14
67
17
115
28
9
5
16
5
156
51
203
80
52
16
1766
301
86
21
Figure 9: The standard query graphs, along with the dynamic range (DR) of the counts of target graphs G, and the dynamic range of the canonical counts of neighborhoods Ge. The statistics are from the ENZYMES dataset.
20

---

Under review as a conference paper at ICLR 2023
Gq
DR G
DR Ge
Gg
DR Gr
DR G.
Gq
DR Gr
DR Ge
3573
688
1631
453
6
615
150
804
318
16
16
5223
1035
2071
732
3
1543
448
526
330
9
8
4049
930
41
17
1725
595
928
296
Figure 10: The large query graphs, and the dynamic range (DR) of counts of the whole target graphs G. and canonical neighborhoods Ge in ENZYMES.
D.3 HYPER-PARAMER CONFIGURATIONS
DeSCo configurations. For DeSCo's canonical partition stage, we set d 4 for all the tasks For DeSCo's neighborhood counting stage, it contains two GNNs to encode
according to Theorem I target and query graphs into embedding vectors, and a regression model to predict canonical count based the vectors. For the GNN encoders, we use the triangle-based message passing variant of GraphSAGE as shown Table g The SHMP GNN has 8 layers with a feature size of 64. The canonical node of the neighborhood is marked with special node type. The adjacent matrix A is used to find the triangle and define the heterogeneous edge type with Equation [8
Etriante = (ii.))(AA 13), > 0}
(18)
For the Multilayer perceptron (MLP) of neighborhood counting, use two fully-connected linear layers with 256 hidden feature size and LeakyReLu activation.
For the gossip correction stage, we use two-layer GNN with 64 hidden feature size and a learnable gate as described in Equation [ The learnable gate is two-layer, 64-hidden-sie MLP that takes the query embedding vector from the neighborhood counting stage and outputs the gate values for each GNN layer. The neighborhood counting prediction is expanded to 64 dimensions with Linear layer and concatenated with the query embedding the input for the two-layer GNN.
Neural baseline configurations. We follow the configurations of the official implementations of neural baselines and adapt them settings. They both contain two GNN encoders and a regres- sion model like DeSCo's neighborhood counting model.
For LRP, follow the official configurations for the ZINC dataset embedding layer with 8 layers and hidden dimension 8. The regression model is the same as DeSCo.
deep LRP-7-1 graph
For DIAMNet, follow the official configurations for the MUTAG dataset size 128 as GNN encoders. The number of GNN layers is expanded from 3 to 5. The regression model is DIAMNet with recurrent steps, external memories, and 4 attention heads.
GIN with feature
Training details. We use C. + Jogz(C.+1] normalization for the ground truth canonical count C, the high dynamic range problem. When evaluating the MSE of predictions, Ć. -2c.
21

---

Under review as a conference paper at ICLR 2023
is used to undo the normalization. We use the SmoothL with 3 = 1.0 from PyTorch Paszke
al. (2019) as the loss function to perform the regression task of neighborhood counting and gossip conrection.
C(C,, Cc) = 0.5 - [ - Cel 0.5 otherwise
C C.l <1
(19)
We use the Adam optimizer for neighhorhood counting and gossip correction and set the learning rate to 0.001. We align the computational resources when training different neural methods. DeSCo and DIAMNet have similar training efficiency, so DeSCo's neighborhood counting model and DI- AMNet are both trained for 300 epochs. After training the neighborhood counting model, DeSCo's gossip correction model is trained for 50 epochs with little resource consumption. In contrast, LRP much slower. Even given twice training time, can only be trained for 50 epochs.
Approximate heuristic configurations. For the MOTIVO baseline. we follow the official setting and use 10" samples for each dataset. If the dataset has many graphs, the samples are evenly dis- tributed on each target graph.
E RUNTIME COMPARISION
We use Intel Xcon Gold 6226R CPU with 2.90GHz frequency and NVIDIA GeForce RTX 3090 GPU for runtime tests.
Method configurations. For the exact method Cordela et al. (2044), we use the Python imple- mentation from the graph processing framework Hagberg al. (2008) and use Python's 's concurrent standard library to enable multiprocessing on four CPU cores. For the exact method IMSM Sun the official c++ implementation with four CPU cores. We the IMSM- recommended method configurations: GQL He & Singh](2008) as the filtering method, RI Bonnici ct al. (2013) as the ordering method, and LFTJ [Bhattarai et al. (2019); Han et al.j (2019) as the enumeration method. The failing set pruning optimization is also enabled. For the heuristic ap- proximate method MOTIVO Bressan et al. (2019), we use the official c++ implementation with four CPU cores. For the neural method DeSCo, we use the Python implementation with one CPU core and one GPU core.
& Luo 22020),
Experiment setup. All the methods are set to count the induced subgraphs in the ENZYMES dataset. Note that IMSM can only perform non-induced subgraph counting. So VF2, MOTIVO, and DeSCo are set to perform induced subgraph counting tasks, while IMSM performs non-induced tasks for runtime comparison. For query sizes no larger than five nodes, the standard queries from Section 5. are used. For query sizes larger than five, the same thirty queries of each size are selected for VF2 and DeSCo. We cannot assign specific queries for MOTIVO, so it is set to output the count of any thirty queries of each size.
Runtime results. Figure aa shows the runtime of each method with four minutes' noun-b The data loading and graph format conversion time is ignored for all methods. For the exact methods, VF2 and IMSM, the runtime grows exponentially because of the exponentially growing possible matches of each query size. For the approximate heuristic method MOTIVO, the exponential growth is mostly because of the build-up phase before sampling. While greatly reducing the sampling space, MOTIVO's build-up phase needs color the nodes of the target graph and count colorful trees for each node, which has exponential time complexity with regard to the query size. For DeSCo, the queries and targets are independently embedded, and queries are relatively small compared with targets. Thus, DeSCo can easily scale for large queries. For example, scaling the query size from 3 to 13 only poses 57% additional overhead on the total runtime. We further extend the time budget for MOTIVO to 60 minutes and find that DeSCo achieves 15x, 53x, and 120x speedup over MOTIVO for size 13 to 15 queries, respectively. As Figure bb shows, currently DeSCo's 's triangle finding in neighborhood counting takes the majority of the runtime, which be easily substituted with other efficient implementations, e.g., Donato et al. (2018). to further speed up DeSCo.
Asymptotic complexity. For the proposed DeSCo's three-step pipeline, assuming the average canonical neighborhood G, of the target graph G, has V,, nodes and E, edges. The time com- plexity for canonical partition is the index-restricted breadth-first search starting from all the target
22

---

Under review as a conference paper at ICLR 2023
canonical partition findd triangles
go ssip correction oSHMP
neighborhood counting
VF2
IMSM
MOTMVO
DeSCo
240
runtime (second)
%
38%
120
67%
80
22%
29%
3
5
6
7
8
10
12
13
query size
(a) runtime comparison
(b) runtime breakdown
Figure 11: The runtime comparison of different size queries and the runtime breakdown of DeSCo
vertices shown in Appendix A.3 which is O(V, (V, F.,)) The time complexity for neighbor- hood counting consists of triangle counting and heterogeneous message passing on G2 and G.- The complexity of triangle counting is ((E3/2) on the target and query graph Itai & Rodeh (1977). The heterogeneous message passing has the complexity of regular GNNs Maron et al. (2019) on the Vi neighborhoods and the queries, which is O(V, x (V, + En)) + +VV Eg). For gossip correction, the time complexity also equals to a regular GNN, which O Vi).
So the overall time complexity of DeSCo is O + (V, + En)) O E3/2 Vg). In real- world graphs, the common contraction of neighborhoods) Weher (2019) makes V, and Fr, relatively small. So the major asymptotic complexity comes from the triangle counting on the target graph, which only has polynomial time complexity.
In contrast, for the heuristic approximate method MOTIVO, the build-up phase alone has time com- plexity Oaa V x E₂) for some > 0. So it suffers from exponential runtime growth. For exact method VF2, the time complexity O(V2) to O(V! V) where V = max(V,, VgJ. In practice, we generally observe exponential runtime growth. Experiments of Figure IT confirms the above analysis.
F COUNT DISTRIBUTION PREDICTION
To the best of our knowledge, DeSCo is the first approximate method that predicts the subgraph count distribution ground truth for the distribution prediction accuracy analysis. The canonical count represents the number of patterns in each node's neighborhood while avoiding missing double counting as discussed in Section 4.1 Following the setup in Section 5.1 we use all the size 3 3 standard query graphs test the distribution performance of DeSCo different target graphs. The normalized MSE is the mean square error of the canonical count prediction of each (query, target graph node) pair divided by the variance the (query, target graph node) pair's 's true canonical count. The MAE is the mean absolute eтror of the canonical count prediction of each (query, target graph node) pair.
the whole target graph. We use the canonical count of each node as the
Datuset
MUTAG 4
COX2 4
ENZYMES
Query-Sizz Size
3
5
3
Norm. MSF 7.51F-2
2.36E-1
1.71++0
4.94F-4
5.63F-4
1.44F-2
4.74F-5
5.69R-5
5.66E-4
MAE
2.97E-4
1.19E-3
1.90E-2
3,90E-4
5.19E-4
1.71E-2
7.60E-2
1.51E-1
3.15E-1
Table 8: DeSCo's count distribution prediction error under normalized MSE and MAE, Use the canonical count of each target graph node as the ground truth.
Experiments show DeSCo achieves a low 0.23 normalized MSE for the count distribution prediction task. A visualization of DeSCo's distribution prediction on the CiteSeer dataset is also shown in
23

---

Under review as a conference paper at ICLR 2023
Figure Note how DeSCo accurately predicts the distribution while providing meaningful insight on the graph.
G ADDITIONAL RESULTS ANALYSIS FOR LARGE QUERIES
To give an even more in-depth understanding of the performance for large queries, we additionally provide the results with more evaluation metrics.
G.1 Q-ERROR ANALYSIS
Definition. Given the ground truth subgraph count C of query Gg in target G,, as well as the estimated count Ć. We the definition of q-error from previous work Zhao al. (022))
c è Ey E +if
eq (G:: G.) = max
(20)
The q-error quantifies the factor that the estimation differs from the true count. The more it is close to 1, the better estimation. In Zhao et al. (2021), there is also alternative form of q-error used in figures to show the systematic bias of predictions.
(G c. (0f+
(21)
We follow the previous settings and use Equation 21 in our visualization.
Experimental results. We reassess the performance of DeSCo large queries from Figure and show the box plot in Figure 12 The data that C O is ignored for mathematic correctness. The box of MOTIVO on MUTAG closest to with minimal spread. It shows how DeSCo excels in systematic error and consistency compared with the baselines.
close zero be shown in the figure. DeSCo's q-error the
107
207
20a
10a4
13a9
COX2
Figure 12: The q-error box plot of large query-target pairs. The q-error (y-axis) is clipped at 10-2 and 102. For q-error, the closer the better.
Limitations of q-error. Despite the advantage of demonstrating relative error, the q-error metric also has obvious limitations, thus not being chosen as the major evaluation metric. In Zhao et al. 2021), the authors assume 2 and 1. However, this assumption may not hold, given that the query graph may (or is predicted to) exist in the target graph, especially for larger queries. The zero or near-zero denominators greatly influence the average q-error. It causes the overestimation of the subgraph existence problem instead of the subgraph counting problem.
G.2 MSE ANALYSIS
Definition. We follow the same setting in Figure 5 and show the normalized MSE for predicting the subgraph count of large queries. Note that in few cases, the tested large queries of a certain size may not exist in the target graph. For example, the two size-thirteen queries in Figure 10 not
24

---

Under review as a conference paper at ICLR 2023
exist in the CiteSeer dataset. To prevent divide-by-zero in normalization, the MSE is normalized by the variance of ground truth counts of all large queries, instead of being normalized for each query size.
Experimental results. The experimental results are shown in Table lowest MSE all tested target graphs.
DeSCo demonstrates the
Dataset
MUTAG
COX2
ENZYMES
MOTIVO
1.2E+01
3.2E+00
1.4E+00
LRP
7.6E-01
1.1E+00
6.7E-01
DIAMNet
2.3E+00
2.4E-01
8.9E+01
DeSCo
1.5E-01
1.2E-01
4.0E-01
Table 9: Normalized MSE of approximate heuristic and neural methods on subgraph counting of sixteen large queries.
25


Reviews:
[{"review_id": "k_ae9pXoO4", "reviewer": "Reviewer_Eqk2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors designed a GNN-based framework for subgraph counting. Previous exact/heuristic methods are often slow, given  an NP hard problem. There are several key ideas: 1. canonical partition, 2. heterogeneous message passing, and 3. gossip correction. Extensive experiments are conducted to evaluate the effectiveness of the proposed approach.", "summary_of_the_review": "In short, i think the strengths slightly outweigh the weaknesses. ", "strength_and_weaknesses": "Strength:\n\n1. Experimental analysis (including those in appendix) is extensive. Additional scalability study / q-error analysis present new insights.\n\n2. The idea of canonical partitioning is novel to me.\n\nWeakness:\n\n1. Apart from exact methods, there are also many recent sampling based estimation methods. Sampling-based methods are not exact, but are significantly faster and often have theoretical guarantees. Some discussion or even comparison to this line of work is needed.\n\n[1] Bressan, Marco, Stefano Leucci, and Alessandro Panconesi. \"Faster motif counting via succinct color codingand adaptive sampling.\" ACM Transactions on Knowledge Discovery from Data (TKDD) 15.6 (2021): 1-27.\n[2] Wang, Pinghui, et al. \"Efficiently estimating motif statistics of large networks.\" ACM Transactions onKnowledge Discovery from Data (TKDD) 9.2 (2014): 1-27.\n\n2. Traditional methods like VF2 runs on CPU, which is not exactly a fair comparison to GNN methods which runs on GPUs. There are also some GPU-based exact methods [3]\n\n[3] Lin, Wenqing, et al. \"Network motif discovery: A GPU approach.\" IEEE transactions on knowledge and dataengineering 29.3 (2016): 513-528.\n\n3. There are also some newer GNN-based baseline [4].\n\n[4] Liu, Xin, and Yangqiu Song. \"Graph convolutional networks with dualmessage passing for subgraph isomorphism counting and matching.\" Proceedings of the AAAI Conference onArtificial Intelligence. 2022.\n\n4. It would be more beneficial if the authors can demonstrate some case work--- how reduced error translate to accuracy in downstream tasks that makes use of such counts? While it is certainly good that MSE is reduced, e.g. from 1 to 0.6, it is not intuitive how significant is such reduction.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SQZOGu5OtTn", "reviewer": "Reviewer_eb8f", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a deep learning model for the task of subgraph counting. This is a challenging algorithmic problem and a well-known #P problem with applications in biology and social science. Deep learning approaches for subgraph counting have been proposed before, but the model presented by the authors improves both in the accuracy and, most notably, in scalability over existing approaches.", "summary_of_the_review": "See my comments above. Overall, I believe this paper would make a fine addition to the conference and to the subgraph counting literature.", "strength_and_weaknesses": "Strengths:\n- Improved performance for a well-studied, relevant problem in the graph theory / network analysis literature\n- There is some novelty on the proposed SHMP module\n- Paper is well-organized and the visuals are very useful for understanding the proposed method\n\nWeaknesses:\n- It is not clear how the improved performance in MSE translates to better results in practice. Why should a practitioner care that the proposed method is more accurate? Is there, for instance, a case study where the proposed approach leads to new biological insights?\n- It is not clear why the authors decided to present squared error as a distribution in Figure 5. I think it would be more informative to see raw squared error numbers, as they present in the rest of the paper.\n- No comparison in terms of runtime to DIAMNet\n- Many typos across the paper ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "79b0CJMfl3", "reviewer": "Reviewer_Gava", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of solving the subgraph counting problem using approaches based on neural networks. The proposed method leverages canonical partition to decompose the considered problem into subproblems, and the entire counting is further calibrated by gossip correction balancing homophily and antisymmetry. Experimental studies are provided to support the proposed designs.\n", "summary_of_the_review": "This paper has some interesting ideas, but the overall contribution is not significant. The experiments need to be more convincing. \n", "strength_and_weaknesses": "Strength:\n\nThe proposed ideas are reasonable. The identified example for showing the expressiveness of SHMP is particularly interesting. Most of the sections are well-written and easy to follow. Source codes are provided through external links. \n\n\nWeaknesses:\n\n- W1: The proposed method is reasonable but does not address the fundamental challenge in subgraph counting: the problem is still computationally hard after fixing a pair of nodes or a certain order of the nodes. That is, the acquired subproblems are in general as hard as the original problem. In this regard, the methods of canonical partition and gossip correction seem simplistic. \n\n- W2: The theoretical contribution is not strong enough, as there is no formal analysis other than one example. It would be better to justify the model expressiveness in a formal way. In addition, the results in Sec 4.2 are pretty straightforward. \n\n- W3: The experiments could be improved in the following aspects:\n  - Given the nature of the proposed method, the performance seems to depend on the node indexing schemes. Such an issue should be investigated at least in experiments.\n  - To justify the statistical significance of the learning performance, one should provide the robustness over the testing set (e.g., std) as well as the robustness over multiple individual trainings (e.g., cross-validation), which are required to rule to out the cases where a) the average error is low but the standard deviation is overly high and b) the trained model is accidentally good. \n  - To make it possible to have an in-depth understanding of the results, it is better to show the exact counting results rather than MSE. \n  - The hyperparameter P seems important, and therefore, it would be better to carefully study its impacts in experiments.\n  - One of the common practices is to select fixed query graphs, and then examine the performance; this paper lists a collection of query graphs, but it is not completely clear to me how they form the training-testing sets. Since this paper involves existing methods in experiments, it could be better to follow the exact settings in those papers, which will make the comparison clearer.\n  -The paper mentions pretraining but not training, which is a little bit confusing.\n\n- W4: Some minor comments:\n  - What does it mean by “combinatorially long runtime”?\n  - The paper claims that their approach can easily support graphs with node features, which, however, seems non-trivial. A small experiment can be included to support such a claim.\n  - Some notations in Sec 4.1 are not well-defined.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject