An Efficient Subgraph GNN with Provable Substructure Counting Power

Thank you for your valuable feedback and insightful suggestions. Your comments have been diligently considered, and we will integrate your suggestions into our revised manuscript.

Importance of substructures. We have incorporated an ablation study to show the importance of substructures in real-world tasks. The substructures, as detailed in Table 1, include 3-6 cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths, and triangle-rectangles. We first report the number of these substructures at graph-level and node-level. Specifically, we report the average number of these substructures per graph (denoted as "graph") and the average number of these substructures that pass each node (denoted as "node"). The statistics are shown below.

Note that 6-cycles are commonly observed within these two graphs. On average, a graph contains approximately two 6-cycles, and there is an average incidence of 0.5 6-cycles that pass a node. This observation underscores the significance of 6-cycle, whose presence may potentially be attributed to the existence of benzene rings.

We then evaluate the significance of these substructures. In particular, we use a base GIN framework as the backbone network, and adopt the count of substructures that pass each node as the augmented node features. In the table, “all” denotes adding all these substructures as the augmented node feature. Due to the time limit, we only run the experiment twice and report the mean result.

Analysis on the real-world benchmarks.

We observe that in most cases, the number of substructures does not boost the performance either on ZINC or on OGBG-HIV. The only exception is that the number of 6-cycles boosts the performance on ZINC (maybe due to the information of benzene rings), and the number of all these substructures boosts the performance on ZINC. We present potential illustrations for the observation:

Firstly, in these molecule graphs, it is imperative to incorporate not only structural but also semantic information to enhance the model. For instance, it is well-established that molecular fingerprints can significantly elevate performance on the OGBG-HIV dataset (Refer: https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv). In particular, the fingerprints contain the number of specific molecule structures, encompassing both the graph structures of molecules and the semantic information of atom types and bond types.

Secondly, the general distance information contains more structural information than the number of specific substructures, thus contributing more to real-world performance. For instance, we have proven that the number of 4-cycles can be computed using the distance information. Conversely, deducing distance information solely from the count of 4-cycles is impracticable, given the multiplicity of configurations that can form a 4-cycle.

Based on the observation, we extract further information from the distance encoding by refining the original method. In our original implementation, we solely employ an embedding layer for the extraction of distance information. During the rebuttal stage, we integrate a 2-layer MLP, supplemented with two batch normalization layers and two ELU activation layers, subsequent to the embedding layer. As shown in the table below, the implementation of this enhanced model structure on both ZINC and OGBG-HIV datasets has yielded a significant amplification in performance, providing empirical evidence that the distance encoding contains valuable information which includes but is not limited to the number of substructures.

We are grateful for the time spent reading our comments, and deeply appreciate your suggestions.

On significance of substructures for real-world experiments. It is still unclear where this approach would be practically strong, and where the benefit of this model lies beyond simply including relevant sub-graphs based on the target task, e.g., ZINC. The new model variation also does not fundamentally change the above point.

We note that the proposed framework demonstrates superior performance over all baseline methods on ZINC, whose prediction relies on local information such as the synthetic accessibility and cycles. Furthermore, the framework has also achieved the best result across various properties in the QM9 benchmark. This serves as empirical evidence underscoring the framework's capability to enhance performance in molecular benchmarks, particularly those that rely on local structural features for attribute prediction.

As for OGBG-HIV, we note that the inhibition of HIV replication involves a complex interplay of both local attributes (such as the structure and function of specific molecules and their enzyme active sites) and global attributes (such as the overall graph structure of both the virus and the molecule components within cells and their intersections). Therefore, the SOTA methods integrate global information (such as graph pooling models or graph transformers) with local information (such as the fingerprint, which contains the count of various specific molecules and may possess a degree of domain-specificity).

On structure detection. I understand the current capabilities of ESC-GNN. I was instead alluding to providing alternative analyses beyond finite-size structure detection and the k-WL connection, which mostly builds on existing work, to strengthen the paper's contribution.

We are pleased to extend our analyses to encompass additional structures. However, to ensure computational efficiency and focus, we kindly request that you specify particular types or classes of structures for analysis. As shown in the previous response, the exhaustive enumeration of all substructures presents a significant computational challenge and may not be feasible within the scope of this study.

We sincerely thank you again for your insightful suggestions and constructive reviews.

Q3. Does Theorem 4.4 hold for both induced and non-induced substructures?

A4. It holds both for induced subgraph counting and subgraph counting. We will clarify it in the paper.

Q4. The experimental section can be improved: a. Why do you focus on node-level tasks? I understand that node-level implies graph-level but the contrary is not true. Since you focus on graph-level tasks in the theoretical part, I don't understand why you test on node-level tasks.

A5. The experiments follow the setting of (Huang et al.). We choose it instead of the graph-level counting task since it is more challenging, i.e., we can compute the number of substructures within the graph by the weighted sum of the number of substructures that pass each node. However, the reverse does not necessarily hold. Although our proof mostly focuses on graph-level counting, it can be potentially transferred to node-level counting. We briefly illustrate it below.

Our proof has shown that the 2-tuple level counting of the mentioned substructures can be done. For a substructure $s$, assumes the number of $s$ that passes the 2-tuple $(u,v)$ as $n_{uv}$, and the number of automorphism of the 2-tuple starting at node $u$ as $p$, i.e., the number of 2-tuples starting from $u$ that has the same isomorphic type as $(u,v)$ in $s$. Then the number of $s$ that passes node $u$ is $\sum_{v \in N(u)}n_{uv} / k$. Take the counting of 3-cycles $s = \\{u, v, w\\}$ that passes $u$ as an example, $k$ is 2 since in $s$, $(u, v)$ and $(u, w)$ have the same isomorphic type as $(u,v)$ ($(u,w)$, resp.). Considering that there is a cycle that passes $(u, v)$ ($(u, w)$, resp.), the number of 3-cycles that passes $u$ is $(1+1)/2=1$.

Q4. $\dots$ Furthermore, I noticed there is an additional counting experiments on ZINC in the appendix, but why is it limited to cycle counting?

A6. We report the number of these substructures in ZINC. Specifically, we report the average number of these substructures per graph (denoted as "graph") and the average number of these substructures that pass each node (denoted as "node"). The statistics are shown below.

We observe that ZINC may not be optimally suited for substructure counting tasks. A significant limitation is (1) the absence of certain substructures, such as 4-cliques, chordal cycles, and triangle-rectangles; (2) many substructures seldom exist in ZINC, such as the 3-cycles and 4-cycles. Therefore we put it in the appendix and do not report the performance on graphlets.

b. The time comparison on ZINC and OGB is presented in the main paper without reporting the results on those datasets in the main paper. Please move the results on these datasets in the main paper.

A7. Thanks for your suggestion. It is temporarily not added due to space limits. We will add it to the main paper in the revised manuscript.

c. Why results on ZINC do not include the std or average across seeds? And why do you use a graph transformers? What are the results with a GNN as a backbone model?

A8. Actually, the reported result is the mean MAE score across ten individual runs. We will add the std score in the revised manuscript. Specifically, ESC-GNN reaches an MAE score of 0.086$\pm$0.003 on ZINC with the graph transformer as the backbone network ((now an MAE score of 0.078$\pm$0.004, after adding an MLP layer after the initial embedding layer. A detailed analysis is available in “Analysis on the real-world benchmarks” in our response to Reviewer aWFU)). In addition, it reaches an MAE score of 0.096$\pm$0.006 with GIN as the backbone network. Note that the proposed encoding can significantly boost the performance for both backbone models.

The reason for choosing the graph transformer as the backbone is based on empirical evidence. Previous works have shown that densely connected models such as the graph transformers (Ramp´aˇseketal.,2022.) or global information such as the laplacian eigenvectors (Lim et al. 2022) can boost the performance on ZINC. Since laplacian-based eigenvectors may violate permutation equivariance, we adopt the graph transformer without laplacian-based positional encoding as the backbone model.

Thank you for your valuable feedback and insightful suggestions. Your comments have been diligently considered, and we will integrate your suggestions into our revised manuscript.

W1. I think the major weakness is that it seems that the model loses permutation equivariance due to the order of the encodings in . Specifically, consider the node-level distance encoding: for the subgraph rooted at edge $\dots$ If the edge is undirected no ordering should be preferred so choosing according to the node id leads to a choice that is not permutation equivariant.

Q1. Please expand on the order of the two node-level distance encoding, as well as on Proposition 4.5, as explained in the Weaknesses.

A1. Actually, our model satisfies permutation equivariance (PE). For your question, the information for node $u$ will be first in the concatenation. This is because our distance encoding is based on $k$-tuples which rely on the sequence of nodes rather than undirected edges that do not preserve the node sequence. Therefore, $s_{uv}$ and $s_{vu}$ can be different since $(u,v)$ and $(v,u)$ are different 2-tuples.

We provide an intuitive illustration of why ESC-GNN satisfies PE. When computing the node representation for $u$, ESC-GNN aggregates the information from its neighbors $\\{v | v \in N(u)\\}$. In this aggregation, the model sums over all $s_{uv}$ instead of $s_{vu}$. The approach ensures that the sequence remains consistent and unaffected by any permutations.

W2. The second main weakness is that Proposition 4.5 does not seem to follow from previous work, and it is not proven in the paper. I think that the claim on page 5 $\dots$ Therefore Proposition 4.5 is not immediate. I think it should be related to Proposition 2 in Qian et al 2022, which proves the same for any k and m=1

A2. Thanks for your suggestion very much. We will add a formal proof in the revised manuscript, and provide a brief proof below. Huang et al. (2023) show that the distance information within subgraphs preserves the same representation power as the node marking policy, i.e., gives the rooted nodes an identity marking. We will then show that the subgraph GNN based on node marking policy can be implemented by $(k+m)$-IGN. (the word “implement” follows from Definition 3 in (Frasca et al.)).

First, the node marking policy can be implemented by the $(k+m)$-IGN following the proof of Lemma 4 in (Frasca. et al.). Assume that for a graph $G$, its input to the $m$-IGN is a $n^m * c_1$ matrix $X$, where $n$ is the number of nodes, and $c_1$ is the feature dimension. For the corresponding subgraphs, the input to the $(k+m)$-IGN is a $n^{(m+k)} * c_2$ matrix $H$, where $c_2$ is the feature dimension. For the $k$-tuple $(v_1, v_2, \dots, v_k)$, we have $H[v_1, v_2, \dots, v_k, v_i, \dots, v_i] = X[v_i, \dots, v_i]$ $\bigoplus$ $\mathbb{1}_{i, k}$ for each $i \in \\{1, \dots, m\\}$. In the equation,

$\mathbb{1}_{i, k}$ denotes the one-hot $k$-dimensional vector being $1$ in dimension $i$ and 0 elsewhere and $\bigoplus$ denotes the concatenation between vectors. For other entries, $H[v_1, v_2, \dots, v_k, :, \dots, ] = X$ $\bigoplus$

$\mathbb{0}_{k}$ (the space is left since markdown will produce a wrong formula without the space), where $\mathbb{0}_k$

denotes a zero vector of dimension $k$. Since the subgraph GNN models the permutation equivariant operations within $n^{m+k}$, it can be implemented by the $(m+k)$-IGN. An example can be found in Lemma 5 in (Frasca et al.)). Specifically, in the message passing period of (Frasca et al.), the node representation $X_{iii}$ can be updated by $X_{iij}$ and $X_{ijj}$, the node representation $X_{iji}$ can be updated by $X_{iji}$ and $X_{iii}$, and $X_{ijk}$ can be represented by $X_{ijk}$ and $X_{ijj}$. In a more general situation, we can replace the first node $i$ with the $k$-tuple, and the latter two nodes with the $m$-tuple that can implement the operation of $m$-WL (Geerts, 2020). As for the message aggregation period, the subgraph pooling followed by a global pooling can be represented by a non-adjacent-to-adjacent pooling followed by a global summation. Therefore the subgraph GNN can be implemented by $(m+k)$-IGN, and thus is bounded by $(m+k)$-WL.

Q2. On page 7, the claim ``As shown in Proposition 5.1, ESC-GNN is less powerful than subgraph MPNNs rooted at 2-tuples" does not seem correct, as according to Proposition 5.1 they can be as powerful as subgraph MPNNs. Please clarify.

A3. For example, subgraph MPNNs rooted at 2-tuple can count 5-cycles (Huang et al. 2023), while ESC-GNN cannot. Together with Proposition 5.1, ESC-GNN is less powerful than subgraph MPNNs rooted at 2-tuples. We will clarify it in the revised manuscript.

Thanks for your suggestions on clarifying the permutation equivariance of the proposed model. We totally agree that it is very important and will integrate your suggestions into our revised manuscript. An example figure is available in the revised manuscript.

Thank you for your valuable feedback and insightful suggestions. Your comments have been diligently considered, and we will integrate your suggestions into our revised manuscript.

W1. The bulk of the paper advocates higher-order GNNs but then the proposed method is the application of a standard GNN on an augmented graph? There is a bit of a mismatch between theory and the proposed method.

Q1 Please explain how Section 4 and Section 5 connect to each other.

A1. In Section 4, we show that subgraph GNNs are nearly as powerful as $k$-WL in terms of counting substructures, and the key reason is the integration of distance information within the subgraph framework. However, a notable limitation of subgraph GNNs is their suboptimal efficiency. To address the limitation, in Section 5, we accelerate them by pre-computing the distance information and enhancing MPNNs with the information. We then theoretically (Section 5) and empirically (Section 6) evaluate the proposed model and observe that it preserves the representation power of subgraph GNNs. In other words, the proposed model can be viewed as an efficient subgraph GNN which successfully preserves the representation power of classic subgraph GNNs.

W2. The proposed method seems very related to approach by Bouritsas et al and Barceló et al in which subgraph information is used (isomorphism, homomorphism) alongside classical GNNs.

Q3 The proposed method uses handcrafted features (as part of encoding). How does it related to the work by Bouritsas et al in which edges carry counts of subgraphs?

A2. It is important to note that (Bouritsas et al) and (Barceló et al) explicitly encode the number of substructures to enhance GNNs. The approach heavily relies on domain-specific knowledge and the desired substructures may significantly vary across different tasks. In contrast, we encode the more general distance information of subgraphs, which enables plain GNNs to count many substructures without the need to manually determine which substructures to include. In addition, the general distance information contains more structural information than the number of specific substructures. For instance, we have proven that the number of 4-cycles can be computed using the distance information. Conversely, deducing distance information solely from the count of 4-cycles is impracticable, given the multiplicity of configurations that can form a 4-cycle. The superiority is also justified by empirical evidence.

Regarding the real-world dataset, (Bouritsas et al) achieves an MAE score of 0.115 on ZINC, whereas ESC-GNN attains an MAE score of 0.086 (now an MAE score of 0.078, after adding an MLP layer after the initial embedding layer. A detailed analysis is available in “Analysis on the real-world benchmarks” in our response to Reviewer aWFU). Similarly, utilizing the same backbone (GIN), (Bouritsas et al) records an AUCROC score of 77.99 on OGBG-HIV, whereas ESC-GNN demonstrates a higher AUCROC score of 78.62 (now an AUCROC score of 79.21). These results highlight the superiority of our proposed model.

W3. It is unclear what theoretical justifications of the proposed encoding method.

Q2 What is the rationale behind the structural encoding presented in section 5. What guarantees does it give? Or other encoding methods possible? (a la molecular finger printing).

A3. The proposed encoding is directly motivated by the theoretical results in Section 4, where we prove that the distance information within subgraphs is the key to boosting the counting power of subgraph GNNs. Building upon this theoretical foundation, we design the proposed encoding, as detailed in Section 5, and prove that it preserves essential structural information. This includes the ability to count substructures and differentiate between non-isomorphic graphs, thereby preserving the representation power of subgraph GNNs. It accelerates subgraph GNNs since it does not need to run message passing among all subgraphs.

To provide an intuitive example, consider the task of counting 3-cycles. Subgraph GNNs rooted on nodes can first compute the number of triangles that pass each node $u$ as the number of edges whose both endpoint nodes are with distance “1” to $u$. It then aggregates the numbers of all nodes and computes the number of 3-cycles within the graph. Notice that the distance information is actually contained in our proposed encoding.

In terms of the fingerprint (e.g., the one that boosts the performance on OGBG-HIV), we note that this fingerprint encompasses numerous molecular structures, a collection of which are identifiable (or countable) by subgraph GNNs. While it is feasible to incorporate these molecular structures within our proposed encoding framework, we do not include the information in our initial experiments since such information is excessively domain-specific, which could potentially limit the general applicability of the proposed model.

Thanks for your suggestions and time one reading the response. We will integrate both your suggestions and the suggestions from other reviewers into our revised manuscript.

Thank you for your valuable feedback and insightful suggestions. Your comments have been diligently considered, and we will integrate your suggestions into our revised manuscript.

W1. It is not true that all subgraph-enhanced GNNs suffer from scalability issues. Currently, there exist subgraph-enhanced GNNs which do not brute-force search over all subgraphs, instead trying to learn which subgraphs are relevant for enhancement: see Qian (2022). Of course, sampling may not lead to "theoretically provable" counting power, but such theoretical results about counting power have limited relevance since the subgraphs being counted are really small and hence this is mainly a question of practical nature.

Q1. Have the authors compared their results to more efficient subgraph-enhancement algorithms such as Qian (2022)?

A1. As you mentioned, the subgraph sampling strategy accelerates subgraph GNNs while losing the theoretical counting power/expressiveness. To assess the practical implications of this trade-off, we conduct an empirical evaluation of the performance and efficiency of OSAN on ZINC and OGBG-HIV, and report the results in the table below. In the table, “Preprocess” denotes the time (second) to preprocess the data (generate subgraphs), and “Run” denotes the total time (second) to train and test. For the configuration of the subgraph sampling strategy, we adopt the official config file from https://github.com/chendiqian/OSAN/blob/master/configs/ogbg-molhiv/node_select/sel25_subgraph3_imle.yaml (OGBG-HIV) and https://github.com/chendiqian/OSAN/blob/master/configs/zinc/imle_with_esan_model/khop3_subgraph_10.yaml (ZINC).

We observe that despite employing a subgraph sampling strategy, OSAN is still not faster than ESC-GNN. This is because ESC-GNN only needs to run message passing on the whole graph, while OSAN needs to run message passing on a collection of subgraphs (even if the number of subgraphs is restricted). In addition, ESC-GNN and even MPNN outperform OSAN on both datasets, showing that the subgraph sampling strategy not only compromises theoretical counting power but also empirically diminishes the representational power of the model. The evidence from these comparisons underscores the superior efficiency and effectiveness of ESC-GNN in handling graph data.