Graph Neural Networks Can (Often) Count Substructures

Thank you for recognizing the clarity and the importance of our work.

We believe that, by addressing the weaknesses that you pointed out, we made our submission more solid, and we therefore thank you for that. Please let us know if you have any further or follow-up questions so that we can try to address them.

The authors did not reference important works in the field, such as "Counting Graph Substructures with Graph Neural Networks" by Kanatsoulis and Ribeiro, and "Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting" by Bouritsas et al. A more thorough literature review is needed.

Thank you for pointing out these references. We have included a paragraph to discuss these, and other references given by the other reviewers, in Section 1.1 and in Section 5.2. In particular, we discuss the relationship with Kanatsoulis and Ribeiro. The paper also proposes a method for GNNs to count substructures, but it's based on the assumption of the graphs having random features, which does not apply in general to standard GNNs.

Additionally, the paper lacks comparisons with other methods and does not discuss how existing methods could be adapted for their task.

Please note that our work is the first one that discusses sufficient conditions that go beyond the worst-case analysis for standard message-passing GNNs to be able to count subgraphs. Because of this, our comparison with similar works can only be quite limited. Thanks to your suggestions though, we have added an in-depth comparison with the works that are the closest to ours. Indeed, we discuss in Section 1.1 and in Section 3 that the main difference of our work with the negative results of the seminal paper of Chen et al. is that we go beyond the worst-case analysis, which considers arbitrary target graphs. We have also added at the end of Section 5.1 a paragraph on how our results extend the results of Chen et al. (2020, Theorem 3.5) and of Zhang et al. (2024, Theorem 4.5).

Finally, the absence of code limits the reproducibility of their results. I appreciate the provided pseudocode, as it makes the paper easier to follow.

The code and datasets are now available as supplementary material, and will be made public on GitHub.

Thank you for your insightful feedback. We hope that our answers and our paper revisions, which include additional experiments as you requested, adequately address all your comments. Please let us know if you have any further or follow-up questions so that we can try to address them.

In Table 1, only results of four graph patterns are shown. It makes the evaluation stronger if more results of common substructures can be provided, or an explanation of why the current chosen ones are important to consider. For example, 5-cycle is also a common substructure in molecules.

We now provide more comprehensive results in Table 4 in Section D.1. The selected patterns are the most frequent ones across all datasets (using a frequency threshold of 25%) to ensure that subgraph counts are non-zero in a substantial number of graphs. Notably, the 5-cycle pattern is not among this set. Nonetheless we added it among the patterns we consider, for its importance in molecular graphs. Note that the central message, i.e., that GNNs can count substructure quite satisfactorily in practice, remains the same.

The algorithm alignment is largely restricted to tree patterns, which is less interesting especially for molecular graphs.

We agree that the ultimate goal is to understand the mechanisms behind how GNNs count more complex patterns. Note however that our results on $(\ell,k)$-identifiability, substantiated by the results of Section 6.1, already give sufficient conditions for counting small cyclic patterns. We added a remark to make this explicit. Moreover, as we mention in Sections 5.3 and B.2, the DP algorithm and the corresponding GNN alignment can be extended, albeit not perfectly, to cyclic patterns. We believe that pursuing this extension, for which we lay the foundations here, is an interesting research direction, but it would be outside of the scope of this paper.

Though Table 3 shows the high identifiable ratio of Mutagenicity dataset, I wonder why the counting performance (MAE) is poor in Table 1.

Note that the counting performance is not perfect, but it can be hardly described as poor. The GNN achieves on average >$0.9$ AUROC on the counting classification problem, and ~$0.5$ MAE, which means that the count is, on average, less than 1 off from the true count. Indeed, if we normalize the absolute error by the true count, we obtain (for Mutagenicity and the patterns of Table 1) the value ${\rm avg. [ (|estimatedCount - trueCount|)/(true Count)} ] \simeq 0.09$, that is the prediction is less than 10% off from the true value on average.

The worse performance with respect to the other datasets can be explained by the fact that this dataset is the smallest one we consider, which could account for the worse generalization performance.

To let the subgraph counting algorithm 1 work, it requires the graph to have some inherent node colors to satisfy parent-colorful. Does that mean the algorithm (and thus GNNs) cannot perform such counting if the graph has no node attributes?

On the contrary, the algorithm can work also with no node attributes. The coloring of the nodes is achieved via $l$ iterations of color refinement (or, in the case of GNNs, $l$ message passing layers). This is described at the beginning of Section 5.2, and we added a sentence to make explicit that no initial node features are needed.

Note that for two nodes that have the same attribute, if they have neighborhood of different sizes, they would receive different colors after one iteration of color refinement, and this coloring would propagate with more and more color refinement iterations. In fact, Babai et al. showed that random graphs (even without node attributes) will have all nodes with distinct colors after a constant number of iterations with high probability. Therefore, in general, given sufficient irregularity in the graphs, the algorithm can correctly work even if the graphs are initially unattributed.

Thank you for recognizing the novelty, the clarity and the importance of our work. We believe that, by addressing the weaknesses that you pointed out, we made our submission more solid, and we therefore thank you for that. Please find the detailed comments below.

We hope that our revisions adequately address all your comments and positively influences your final score. Please let us know if you have any further or follow-up questions so that we can try to address them.

While the method is shown to work for subgraph counting, there is minimal discussion of its computational complexity, particularly for larger graphs or deeper GNN layers. Insight into time complexity would make the approach more practical.

We added a discussion on the complexity of the algorithm in the paper at the end of Section 5.1, and a more detailed one in Section A.5. Note that for the GNN that simulates this, the complexity would depend on the number of layers and size of the MLP, which we characterize in Theorem 5 via the quantity $\zeta$, which is then upper bounded in the subsequent paragraph.

Adding visual representations of key concepts, such as the identification of -identifiable nodes could enhance reader understanding and engagement.

Thank you for this suggestion, we indeed think visual representations could aid the reader, and we put significant effort in designing simple yet informative examples to put in our figures. We now provide example figures for (i) k-l-identifiable graph sets, (ii) quite-colorful maps and (iii) the execution of the dynamic program.

Missing references:

Thank you for pointing out these references. We have included a paragraph to discuss these, and other references given by the other reviewers, in Section 1.1 and in Section 5.2.

This work mentions WL limitations but does not analyze upper bounds or scenarios where the proposed method may struggle with expressivity. A comparative analysis with existing expressive GNN models would provide a clearer understanding of when this approach is suitable.

Can the authors provide more specific examples or scenarios where the condition of identifiability fails? This could help clarify the limitations of their proposed framework.

The first example of Figure 2 shows a case where the graph set is not (2,1)-identifiable. Interestingly, it is (3,1) identifiable. An example of a case where the condition fails for any $\ell$, is if the graphs in the dataset are all regular graphs. Then, the universal covers rooted at each node are all isomorphic, and the condition on $(\ell,k)$-identifiability would fail. However, as we show in Section 6.1, the conditions to make $(\ell,k)$-identifiability fail are rare in practice. We added a remark on this matter after Definition 2.

Moreover, we added a remark at the and of Section 5.2 to clarify that on adversarial examples, such as regular graphs, also the dynamic programming algorithms, and thus the GNNs, will fail.

How do the authors justify the reliance on WL classes in determining graph indistinguishability? Are there potential edge cases where this might not hold true, particularly in practical applications?

As shown in the classical results of Morris et al. (2019), message passing GNNs cannot distinguish non-isomorphic graphs that belong to the same WL class. Moreover, GNNs can, as shown in Xu et al.(2018) and Morris et al. (2019), distinguish graphs that belong to different WL classes. In practical applications though, GNNs might struggle with distinguishing all pairs of non-isomorphic graphs, but this does not seem to impact too much the task of subgraph counting, as shown in Table 1.

The paper mentions that the GNN may require up to $2^{n-1}$ message passing layers in the worst case. What are the empirical implications of this for large graphs? Are there any optimizations or heuristics that could be discussed to mitigate this?

Note that we mention $2(n-1)$ layers, not $2^{n-1}$. The implications, as we mention in the paper, are that such GNNs would not be able to scale to large graphs. Note thought that we address this problem in the following section with the concept of $(\ell,k)$-identifiability. Indeed, for sets of graphs that satisfy this condition (and we show in Section 6.1 that this holds in practice), only $\ell$ layers are needed. Note that $\ell$ does not depend on the graph size, allowing the models to scale to large graphs. We have added a remark before Section 4.1 to clarify that we develop the concept of $(\ell,k)$-identifiability to use GNNs with number of layers and number of parameters independent of $n$.

If feasible, providing access to the code developed would enable others to replicate your experiments and potentially extend your work.

Absolutely. The code and datasets are now available as supplementary material, and will be made public on GitHub.

We thank you for your insights on how the paper could be improved, and for acknowledging the high relevance of the field of work. Thanks to your feedback, we improved the formalism and incorporated a more thorough comparison with previous work and several experimental results to support our claims, which we believe have strengthened our submission.

Please find below the answers to your comments. We hope that our answers and revisions address your concerns, and we’d be happy to address any additional questions you may have.

The paper is not easy to follow...

Thank you for pointing out how to improve the clarity of our paper. We have modified the manuscript as follows:

• now provide example figures for (i) k-l-identifiable graph sets, (ii) quite- and parent-colorful maps and (iii) the execution of the dynamic program.
• we better describe the notation for the algorithm (lines 354 to 374), clarifying the inputs and the outputs.
• we replaced "pattern nodes" with "pattern graph's nodes"
• the pseudo dimension is formally defined in section A.2.
• We now moved the algorithm for the locally injective homomorphism problem to the appendix and focus on the (quite-colorful) subgraph isomorphism problem, which has a clearer motivation. The condition on quite-colorfulness is needed to go beyond the worst-case analysis, which would allow to count only star-shaped patterns.

However, the paper primarily focuses on WL-distinguishable graphs and tree patterns for its dynamic programming algorithms.

Indeed our paper focuses in the first part on WL-distinguishable or $(\ell, k)$-identifiable graphs, but we also show in Section 6.1 that these conditions hold on several datasets. Our goal is indeed to find sufficient conditions for counting subgraphs, beyond the worst-case analysis. For the second part of the paper, the dynamic programs indeed work for tree patterns. While this result is limited, it is the first extension beyond the worst-case analysis of Chen et al. (2020, Theorem 3.5) and of Zhang et al., (2024, Theorem 4.5), see also reply to W2. Moreover, we discuss briefly in Section 5.3 and B.2 that the algorithms can be extended to work, albeit not perfectly, to cyclic patterns. This however is a major expansion, for which we lay the foundations here, and we are planning to explore this in future work.

Proposition 1 is limited to graphs that are distinguishable by the 1-WL test.

We are a bit confused by this criticism. We indeed state this limitation in Proposition 1. Our goal is indeed to find sufficient conditions that hold in practice for which GNNs can count substructures, and WL distinguishability is one of them. As shown in Section 6.1, most real world graphs are WL distinguishable.

Moreover, Proposition 1 is only the first simple result, what motivates the subsequent contributions. First, $(\ell,k)$-identifiability is a property that can hold even without 1-WL-distinguishability (e.g. for graphs where all k-ego-nets are isomorphic), and we show in Section 6.1 that it also holds in practice. Secondly, Section 5 discusses exactly what you mention in you comment, that is whether GNNs can count trees within general graphs. Our DP restricts the classes of pattern graphs, and can work also on WL-indistinguishable graphs.

The statement, "It is immediate to see...

We have added a formal proof in the Appendix, and refer to it in the main paper. Note also that counting rooted subgraphs on each node of the target graph does not overcount the total number of subgraph isomorphisms. Note that we are counting the number of maps between the two graphs, so we are not dividing by the number of automorphisms of the pattern graph. In this formulation, it is easier to see the node decomposability. However, the result holds also in the formulation where one divides the number of maps by $|Aut(P)|$, by a simple rescaling.

The proof of Theorem 1 relies solely on node-level functions.

Your observation is indeed correct, a GNN would be able to distinguish the two graphs, but we show that it won't be able to distinguish some pairs of nodes. The goal of Section 4 is to understand the scenarios where GNNs can count subgraphs at the node level. As we state in the paper, we do this to obtain GNNs that have a number of parameters independent on the graph size. Indeed, the GNNs that consider graph-level functions in Proposition 1 must have size that depends exponentially on the graph size. We have added a remark to highlight our goals: "This gives hope for a GNN model that relies only on local structures...". Moreover, counting (rooted) subgraphs at the node level is an interesting task itself, and our results help understand its hardness.

Generally, graph isomorphism is a different problem from subgraph isomorphism.

Thank you for pointing this typo out. We meant "solving the (non-induced) subgraph isomorphism problem". We fixed this.

.

We continue answering the questions in the comment below.

Thank you for recognizing the clarity and the potential impact of our work to the graph learning community.

Moreover, we want to thank you for your very thorough and insightful review, which made us spot and address some sections of the manuscript that could be strengthened.

Please find detailed answers to all of your questions below.

W1: A clear area for potential improvement of this work is the empirical analysis. Your results could be more broadly validated empirically. But I appreciate that not all papers need both a substantial theoretical and empirical contribution and the theoretical contribution here is very strong.

We now provide more comprehensive results in Table 4 in Section D.1. Note that the central message, i.e., that GNNs can count substructure quite satisfactorily in practice, remains the same.

W2: In parts the writing is a bit dense and difficult to follow. Some examples may help to make the text more accessible.

2] The paper you presented is one that the reader really has to work through. It is dense and complex. More patient explanation and more frequent examples would make for more pleasant reading. Examples would aid especially in the more advanced concepts in the preliminaries and in Section 5.

Thank you for your suggestion. Wow provide example figures for (i) k-l-identifiable graph sets, (ii) quite- and parent-colorful maps and (iii) the execution of the dynamic program. We indeed think visual representations could aid the reader in understanding the hardest concepts of our paper, and we put significant effort in designing simple yet informative examples to put in our figures.

W3: You should state more explicitly what GNN you used in your experiments.

1] On several occasions in the empirical analysis you are imprecise on what GNN you use to investigate your hypotheses. I think the clarity of the paper would be improved if you stated more precisely what GNN you used. I am in particular referring the Line 59 and the discussion/caption of Table 1, as well as the experiments in Section 6.2, e.g., Line 479.

Thanks for pointing this lack of clarity. We use the GNN specified in Section A.1, which is implemented by, e.g., PyG's GraphConv. We have added remarks on this both in Section 1, in Section D (Additonal rexperimental results, which includes the old Section 6.2).

3] In your list of limitations of the result of Proposition 1, it would be appropriate to add that you require an impractically deep GNN, where the number of layers appears to be equal to the maximal number of nodes in any given graph in the dataset.

We agree. We now mention it in the paper.

4] Your experiments could be improved and extended in a variety of ways.

Thank you for suggesting these improvements. We have, indeed, significantly expanded our experimental section, with several new and extended experiments:

• We now provide comprehensive empirical results for subgraph counting on real-world molecular datasets (see Section D.1), covering 8 datasets and 14 pattern graphs.
• We now include an evaluation on the quite-colorfulness of subgraph isomorphisms for all 8 datasets, validating the assessment on quite-colorfullness in practice when the patterns themselves are not quite-colourful.
• We revised the evaluation of parent- and quite-colorfulness on synthetic graphs and included a more detailed description of the synthetic dataset generation process.
• The appendix now contains a table proving general information on the real-world datasets.
• We now include the code as supplementary material.

5] Minor comments:

Thank you for your insights. We addressed 5.1, 5.2, 5.3 and 5.4. Note that the GNNs in A.1 are from Morrie et al. (2019), and not GraphSage. The difference is that we use a sum instead of a mean, that is needed for ensuring WL expressivty.