Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality

Authors: Joshua Southern, Yam Eitan, Guy Bar-Shalom, Michael M. Bronstein, Haggai Maron, Fabrizio Frasca
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Subgraph GNNs, Subgraphs, Expressive power

Abstract:
We propose an expressive and efficient approach that combines the strengths of two prominent extensions of Graph Neural Networks (GNNs): Subgraph GNNs and Structural Encodings (SEs). Our approach leverages walk-based centrality measures, both as a powerful form of SE and also as a subgraph selection strategy for Subgraph GNNs. By drawing a connection to perturbation analysis, we highlight the effectiveness of centrality-based sampling, and show it significantly reduces the computational burden associated with Subgraph GNNs. Further, we combine our efficient Subgraph GNN with SEs derived from the calculated centrality and demonstrate this hybrid approach, dubbed HyMN, gains in discriminative power. HyMN effectively addresses the expressiveness limitations of Message Passing Neural Networks (MPNNs) while mitigating the computational costs of Subgraph GNNs. Through a series of experiments on synthetic and real-world tasks, we show it outperforms other subgraph sampling approaches while being competitive with full-bag Subgraph GNNs and other state-of-the-art approaches with a notably reduced runtime.

Decision: reject
Reviewer scores: 6, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730308936171

thread_type:
official_review

<thread_object>
creator: reviewer_pvqu

<content>
summary:
The proposed work mainly addresses concerns regarding the temporal complexity of Subgraph GNNs. It proposes a mechanism based on subgraph centrality to sample the graphs that will be part of the bag. Furthermore, it demonstrates that adding centrality encoding to nodes can enhance the discriminative power of sampled Subgraph GNNs while limiting the added computational overhead.

Main Contributions:
1. Adoption of centrality-based sampling for Subgraph GNNs.
2. Clear statement and results regarding incorporating structural encoding as means to improve expressivity of sampled Subgraph GNNs without much computational overhead.

strengths:
1. **Relevance and Contextualization**: The proposed work addresses an issue (computational complexity of Subgraph GNNs) that is extremely relevant for the community. It clearly identifies gaps in existing methods and situates the research well within the current state of the art.
2. **Centrality-based Sampling**: The decision of sampling based on centrality measures has some theoretical backing. The analysis based on perturbations is well founded and creative.
3. **Structural Encoding**: The decision of incorporating structural encodings with subsampling is well motivated and has sufficient theoretical backing.

weaknesses:
1. **Theoretical Concerns**: The analysis based on perturbation is not sufficient to justify using the highest centrality nodes to guide the sampling procedure. Even though they will tend to produce the highest perturbation in the graph representation, this alone does not fully justify their selection for the sampling procedure. These nodes may cause the highest perturbation in graph representations, but their practical value in enhancing graph learning remains uncertain, there is no guarantee on the usefulness and attainability of such modifications. Additionally, the assumption that high-centrality nodes capture the most relevant information is limited by the specific centrality metric used, which may not capture all essential features.
2. **Comparison of Centrality Measures**: The comparison between the adopted subgraph centrality, SC, and other centralities is not sufficient to prove SC's superiority. Moreover, centrality measures often complement each other rather than subsumming one another. SC may be more effective for certain tasks but not necessarily for all graph learning tasks. Rather than claiming SC's superiority, it would be better to show in which tasks SC excels and acknowledge that other centrality measures may outperform it in different contexts. Otherwise, stronger results linking the superiority of SC over every other centrality for graph learning, would be necessary.
3. **RWSE vs CSE**: While the proposed method (CSE) shows some advantages over RWSE, particularly from a sampling perspective as seen in Figure 7, its benefits appear limited. The experiments focus primarily on counting substructures, a relevant task but one that may not fully demonstrate CSE's broader applicability due to its inherent predisposition toward this type of task.
4. **Inconsistencies in Experiments**: The experimental results lack consistency, as the models used for comparison vary across datasets. It is understandable that in many cases the results for all datasets are not available in the original works. However, this inconsistency can raise confusion and concerns of cherry-picking. It would strengthen the results to ensure uniformity in model comparisons.
5. **Missing Runtime Comparisons**:  The efficiency of the proposed method is emphasized throughout the paper, yet runtime comparisons are not provided for all datasets. Since computational efficiency is a key focus, these comparisons should be included in every experiment to give a more comprehensive view of the method’s benefits.
6. **Confusing Proof**: The presentation of Theorem 4 lacks clarity. Specifically, in line 910, it is stated that Lemma 1 will be used to demonstrate that the multiset of values in the centrality encoding for each graph will be distinct. However, unless I am overlooking something, Lemma 1 does not seem to establish this. Rather, it appears to indicate that the global node is consistently selected for top-1 sampling, which does not sufficiently ensure distinguishability between the centrality multisets of the two graphs. This interpretation seems supported by the statement in line 963. Moreover, the topic of centrality encoding does not reappear until line 966.

Furthermore, considering that $A$ represents the adjacency matrix and $A^k$ denotes its $k$th power, the assertion in Equation 11 raises concerns regarding its mathematical validity and intuitive clarity. For example, the expression $A^{k+1}\_{u\_1,v} = A^{k+1}\_{u\_1, ;} \\cdot A^{k+1}\_{;, v}$ appears to be problematic.

From a path interpretation perspective, the original statement suggests that the number of paths of length $k+1$ between nodes $u_1$ and $v$ can be derived by aggregating information from $A^{k+1}\_{u_1, ;}$, which accounts for all paths of length $k+1$ originating from $u_1$, and $A^{k+1}{;, v}$, which encompasses all paths of length $k+1$ terminating at $v$ from any other node. Would it not be more accurate to represent this relationship as $A^{k+1}\_{u_1,v} = A^{k}\_{u_1, ;} \cdot A^{1}\_{;, v}$?

Additionally, I would like to point out the presence of redundant statements, such as $A^{k+1}\_{u_1, v} \geq A^{k+1}\_{u_1, v}$ found in line 961, which could benefit from clarification or removal.

questions:
1. Could you clarify what new insights are brought by the results in Table 1 compared to those in Figure 6 and Figure 3? The distinction between these results is not immediately clear to me.
2. In line 247, you mention that the sampling strategy should "(...) alter the graph representations in a way that is consistent with the target space." This aligns with the theoretical concerns in point 1. However, the experimental study performed pertains to counting substructures, a task where the information extracted by SC is expected to be relevant. How do you expect this sampling method to compare to other centralities in tasks where SC may not encode the most relevant information, such as network flow characterization?
3. The results under OSAN represent 1-OSAN?
4. Proposition 2 - Appendix B relates MPNNs with SE to DSS-GNN. The complete proposed method shows better results than 1-OSAN (assumed, see above) which is upper-bounded by the 2-WL, and better results than policy-learn which is expected to be more expressive than 1-WL but less than 4-WL. Where is the complete proposed method positioned in the WL framework for expressivity?
5. In line 424, it is stated that Figure 3 compares random sampling with SC. However, earlier (line 51), you state that random sampling is suboptimal. Why were other sampling strategies not tested to fully validate SC?
6. What was the method used to select the hyperparameter T? A brief explanation in the text would provide more clarity.
7. It was not addressed why a higher T, meaning more subgraphs, meaning more information leads to worse results. Is the information not useful? Is it connected to the sampling procedure not taking into account already sampled subgraphs? This is unclear to me.
8. For proposition 1, Step 2, the block matrix $W^{(j+1)\_0}$ seems to select the first $k+j$ columns not $k+j+1$? Consider $k=3$ for $j=1$. The block matrix will have dimensions $7 \times 7$, with only the block in the first spot of the diagonal performing a selection since the second block $I_{j-1}$ is omitted.
9. For the same proposition, I would like to seek clarification regarding the explanation provided for $AXW^{(j+1)_1}$. Specifically, the identity matrix is described as having dimensions $k - (j - 1)$, yet the reference appears to describe the selection of the last $j$ columns. Additionally, the process by which the iterations from $j = 1$ to $j = k$ contribute to the formation of the final vector is not entirely clear. I would greatly appreciate any further elaboration on these points to enhance my understanding.
10. Considering choices of T > 1 in the experiments, for theorem 4, what is the impact of k>1 for top-k Subgraph GNN compared to MPNN+CSE?

Minor:
1. The phrase starting in line 214, "If instrumental (...)",  is confusing, consider rewriting it.
2. Quartic is often misspelled as "quatric".
3. Line 890, the expression "1-hop neighborhood" is imprecise, I recommend 1-hop induced subgraph.
4. Line 836, misspelled "the" as "he".
5. Missing subscript on line 952?
6. No identification of what $m$ denotes in equation 15.

Suggestions (Optional):
1. Line 228, "(...) untrained 3-layer GIN". By untrained I assume the weights were initialized at random. If this is the case, for GIN, different random initialization should lead to some variance, even if small, in the results, leading to variance in the perturbations. It would be more robust to report the mean difference in perturbations across multiple random initializations, as this would account for variance in the results.
2. There is no direct comparison with some relevant network architectures like $I^2$-GNN that are not captured by 1-OSAN. I understand that $I^2$-GNN was used as a comparison point in MAG-GNN, but the results were quite close in the referred work, hence, I believe it would be useful to add such comparison. More importantly, works like ESC-GNN introduce a faster alternative to $I^2$-GNN. Since the presented work also focuses on efficiency, I believe a comparison with ESC-GNN would be interesting.
3. Since much of the code used is based on GraphGPS, the configs could be more carefully described to be easier to match the experiments in the paper.

The paper presents contributions that may be of limited novelty while having some inconsistencies. However, I am **very** open to revisiting and potentially increasing my evaluation score, provided the authors effectively address the identified weaknesses and respond to the questions posed. I encourage the authors to consider these aspects to enhance the manuscript's impact and clarity.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730453402800

thread_type:
official_review

<thread_object>
creator: reviewer_8uxd

<content>
summary:
This paper introduces a novel method called Hybrid Marked Network (HyMN), aimed at balancing 
computational efficiency and model expressiveness. The approach combines subgraph GNNs 
with structure encodings (SEs) based on walk centrality measures. The main innovation lies in 
utilizing subgraph centrality for subgraph sampling and structure encoding, allowing for the 
maintenance of prediction accuracy while reducing the required number of subgraphs, thus 
lowering computational costs while preserving the model's expressive capacity. Experimental 
validation on synthetic and real world tasks demonstrates that HyMN outperforms other state-of
the-art GNN methods while reducing computational demands

strengths:
1. The walk centrality-based subgraph selection method achieves efficient subgraph sampling, 
simplifying the model while ensuring performance, making it suitable for larger subgraphs.
 2. Experiments on various tasks showcase HyMN's adaptability and performance.
 3. By ranking nodes based on their centrality values, and mark the top-scoring ones, the model 
reduces computation time, making it applicable to a wider spectrum of downstream tasks.

weaknesses:
Abstract and Background Information:
The abstract is incomplete, as it lacks essential background information. This omission leaves me confused about the specific problem the paper aims to address. A well-defined problem statement is crucial for understanding the motivation behind the research and its significance.

Experimental Validation of CSEs:
I noticed that experiments on the effect of CSEs in the Peptides and Zinc datasets were not conducted. This absence raises questions about the impact of incorporating CSEs (Q4). Clarifying this point is essential for understanding how CSEs contribute to the overall findings of the study. Consider including experimental results or justifications for their omission.

Exploration of Selection Strategies:
The paper would benefit from exploring more complex selection strategies and different walk-based centrality measures. This exploration could provide deeper insights into the dynamics at play and strengthen the overall analysis.

Typos and Formatting Issues:
While typos and formatting are not the most critical issues, there are several areas that require attention. For instance, the indentation of the abstract does not align with the template requirements. Additionally, line 194 contains a grammatical error with "is are" used simultaneously, which should be corrected. Some equations lack punctuation at their end, where it is needed, leading to inconsistencies. Lines 206-210 stray from the scope of Definition 1 and should not be italicized. Furthermore, Algorithm 1 lacks a title, which is necessary for clarity and organization.

Section 2 - Clarification of Content:
Although Section 2 is titled “PRELIMINARIES AND RELATED WORK,” it primarily focuses on related work without adequately presenting the foundational definitions necessary for understanding the subsequent content. It would be beneficial to include a clearer explanation of the definitions and concepts that readers should be familiar with before delving into the related literature.

questions:
Refer to Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730591709100

thread_type:
official_review

<thread_object>
creator: reviewer_i9zd

<content>
summary:
To balance efficiency and expressiveness in subgraph GNNs, this paper proposes a novel framework that utilizes walk-based centrality measures for subgraph subsampling and structural encoding. The necessity of using centrality measures is demonstrated through theoretical analysis and experimental validation. Experimental results show the effectiveness of HyMN across various tasks and datasets.

strengths:
1. The paper proposes a novel framework that balances the efficiency and expressiveness of subgraph GNNs.
2. This paper provides a comprehensive theoretical analysis and experimental validation of why the simple subgraph centrality measure is needed for subgraph GNN.
3. The experiment results demonstrate the effectiveness and efficiency of the proposed method.

weaknesses:
1. The two main components (subsample subgraph using centrality measure, and centrality-based structural encoding) are similar with previous work.[1,2]
2. A more detailed introduction to the key background of this work would be helpful(i.e. the background and method of the node marking)
3. More backbone(except GIN) and more baseline should be preferred to be considered by authors.

[1] Sun, Qingyun, et al. "Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism." *Proceedings of the web conference 2021*. 2021.

[2] Rampášek, Ladislav, et al. "Recipe for a general, powerful, scalable graph transformer." *Advances in Neural Information Processing Systems* 35 (2022): 14501-14515.

questions:
1. Could the author provide more evidence to support the validity of the two claims in line 182?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730591746457

thread_type:
official_review

<thread_object>
creator: reviewer_bwnw

<content>
summary:
The paper proposes a model termed Hybrid Marketing Network (HyMN), which is designed based on two intuitions which may potentially improve the GNN performance. First, marking the nodes included in Subgraph GNNs using walk-based subgraph centrality measures as an efficient strategy. Second, augmenting the node features with the same centrality measures as Structureal Encodings (SEs).  The key insight is that walk-based centrality measures serve both as effective indicators for subgraph importance and as infrmative structrual features. The authors theoretically analysed the node marking strategy with graph perturbation theory and demonstrate that their approach effectively balance expressiveness and efficiency.

strengths:
1. the theoretical analysis provide a solid foundation for their proposed method. The utilization of perturbation theory and expressive theory looks correct for me.
2. This method is neat in design, which only requires minimal computation overhead compared with baselines while maintaining competitive performance.
3. The experimental validation is comprehensive, besides comparing their method with SOTAs, they conduct synthetic experiments for counting substructures, detailed ablations and experiment time analysis.

weaknesses:
1. The sampling strategy does not consider interactions between sampled subrgaphs that are already sampled, which can lead to potential redundancy.
2. The analysis focus primarily on single-node marking. While mentioned in the limitations, extending the analysis to multi-node marking could provide addiitonal insights. Imagine a social network representing employees in a company. In this network, there's a team of three senior managers (say Alice, Bob, and Carol) who work closely together and have very similar connections to other employees. They all interact with the same team members, attend the same meetings, and collaborate on similar projects. According to your approach, since all three managers have high centrality scores due to their positions, the algorithm might select both Alice and Bob for marking. However, because their network positions and connections are so similar, marking both of them provides largely redundant information. It would be more informative to mark Alice (representing the management team's perspective) and then perhaps mark someone from a different department or organizational level, like a developer or a project coordinator, to capture a different aspect of the company's structure.
3. The approach can be less effective on graphs where walk-based centrality measures don't align with task objectives. Consider a drug discovery task where we're trying to predict whether molecules will bind to a specific protein receptor. The binding activity often depends on specific functional groups located at the periphery of the molecule. Take acetylsalicylic acid (aspirin) as an example. The molecule's binding properties are largely determined by its acetyl group at the edge of the molecule, but the walk-based centrality measure would give more importance to the central benzene ring because it participates in more walks through the molecular graph. In this case, marking nodes based on centrality would emphasize the structurally central but functionally less relevant parts of the molecule, while potentially overlooking the peripheral functional groups that actually determine the binding behavior. This mismatch between structural centrality and functional importance could lead to suboptimal performance on specific prediction tasks.

questions:
1. Have you investigated how the performance of you sampling strategy varies with graph density? Intuitively, in very sparse graphs, walk-based centrality might be less informative.
2. In the perturbation analysis, could the bound be tightened by considering specific graph properties or structures? For instance, does the bound become tighter for trees or graphs with bounded degree?
3. Is there any strategies to extend the perturbation analysis to handle edge features or different types of marking strategies?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731959543480

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
We are very grateful to all reviewers for their comprehensive responses which, we gladly note, have highlighted several positive traits of our presented work.

The proposed framework has been found _“neat in design”_ (bWnw), _“novel”_ (i9ZD), _adaptable_ (8UxD) and to be addressing _“an issue [...] that is extremely relevant for the community”_ (pVQU).

Reviewers have appreciated our provided theoretical analyses, which they believe provide _“a solid foundation”_ for our method (bWnw), are _“comprehensive”_ (i9ZD), _“well founded”_, _“creative”_ and _well motivate the design decisions_ (pVQU).

Reviewers bWnw, i9ZD and 8UxD commend the _simplicity of the solution_ and its ability to attain _competitive performance with computational efficiency_. They have praised the _comprehensiveness_ of our experimental validation, with its _“detailed ablations and experiment time analysis”_ (bWnw).

The reviewers have also kindly provided interesting points of discussion and raised relevant questions which we address specifically below.

We finally remark that, following the reviewers’ suggestions we have run additional experiments:
1. Additional run-time analyses on zinc and molhiv;
2. Additional experiments on Subgraph GNN backbones;
3. Experiments on real-world datasets with other centrality measures, including timing their precomputation;
4. Min-centrality marking on substructure counting;
5. Additional ablations on the impact of CSEs on the Peptides and ZINC datasets.

Overall, the above confirm that:
- Our approach is efficient both in its precomputation and forward pass (1., 3.,), is robust to the choice of the backbone architecture (2.);
- Sampling via (larger values of) walk-based centrality measures and, in particular, the Subgraph Centrality is a robust strategy across benchmarks (3., 4.)
- Both marking and (centrality-based) structural encodings provide benefits when used jointly over using either in isolation (5.)

A new revision has been posted. It includes improvements based on reviewers’ comments as well as salient additional results from the above experiments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732389812235

thread_type:
official_comment

<thread_object>
creator: area_chair_ikx2

<content>
title:
Reminder: Please Review Author Responses

comment:
Dear Reviewers,

As the discussion period is coming to a close, please take a moment to review the authors’ responses if you haven’t done so already. Even if you decide not to update your evaluation, kindly confirm that you have reviewed the responses and that they do not change your assessment.

Thank you for your time and effort!

Best regards, AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a method aimed at improving the efficiency of Subgraph GNNs. The approach leverages walk-based subgraph centrality measures to guide subgraph sampling and proposes using centralities that may highlight structurally sensitive nodes as the centers for subgraph sampling. Experimentally, the method demonstrates reasonably good performance compared to baseline methods across various graph-related tasks.

The main strength of this work lies in its efficiency improvements for Subgraph GNNs while maintaining competitive performance on multiple datasets. The key concern is the limited novelty, as the proposed method is primarily a heuristic for incrementally improving existing subgraph GNN pipelines. It remains unclear whether these heuristics are applicable to a broader domain or some critical applications, such as drug discovery, where the most relevant nodes may correspond to important functional groups rather than structurally sensitive ones, as mentioned by two reviewers. After reading the paper by myself, I would like to raise a minor question: As the goal is to have more expressive yet computationally efficient graph learning, the authors may consider comparing with other methods that directly incorporate other structural features into GNNs or adopt faster architectures such as those in [1,2]. These methods seem to have shown practical efficiency and strong performance. The authors are suggested to compare with these efficient and expressive pipelines to demonstrate the necessity of accelerating subgraph GNNs.

Overall, while this paper achieves some valid findings, I consider it a borderline submission. Given the high bar for ICLR, I lean toward recommending rejection.

[1] Recurrent Distance-Encoding Neural Networks for Graph Representation Learning, Ding et al., ICML 2024
[2] What Can We Learn from State Space Models for Machine Learning on Graphs? Huang et al., arxiv 2024