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

“The comparison between the adopted subgraph centrality, SC, and other centralities is not sufficient to prove SC's superiority [...] centrality measures often complement each other [...] 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.”

It was not our intention to claim the absolute superiority of the Subgraph Centrality measure w.r.t. others, but we understand that our choice of experimenting with this measure in particular could have inadvertently conveyed this message.

In general, we agree that different centrality measures may deliver more or less competitive performance in different contexts. Our experiments in Appendix D.1 constitute, in fact, a first inquiry into this possibility: we asked whether specific centralities excel more than others in counting certain substructures. These are, however, synthetic benchmarks and we acknowledge they may not necessarily give a satisfactory indication on real-world tasks.

Accordingly, we ran additional experiments by comparing different centrality measures on the real-world peptides and molhiv datasets. We experimented in particular, with the Betweenness Centrality (BC), the Katz Index (KI) and the Subgraph Centrality (SC), obtaining the following results:

We see that the performances achieved by different measures are not dramatically different from each other, with those by the KI and SC being closer. In fact, centrality measures often exhibit a degree of correlation with each other, especially if from the same family, as it is the case of the walk-based KI and SC (see [1] and our Table 6). It is also worth noting that Subgraph Centrality can be more efficient to calculate than these other centrality measures using the networkx library. For example, for an Erdös-Renyi graph with 1000 nodes and p=0.5, we have

Overall, we believe that specific centrality measures could work better than others depending on the task at hand, but, at the same time, our current ensemble of observations indicate that walk-based centrality measures – and, in particular, the Subgraph Centrality – offer the most competitive results for the lightest precomputation run-time. Given the additional support provided by the bound discussed in Observation 1, we think they constitute particularly strong candidates across use-cases.

We would be happy to articulate this discussion in a new revision of the manuscript should the reviewer find it relevant.

“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.”

While we are grateful to the reviewer for bringing this point to our attention, we respectfully note that we do not see it as constituting a weakness of our work. First, we remark that our objective is to enhance the efficiency of Subgraph GNNs rather than to propose a new SE scheme that could surpass RWSEs in their generalization performance. Second, it is pivotal to highlight that, to the best of our knowledge, no previous work has suggested employing RWSEs for node ranking and/or subgraph sampling purposes. Thus, we do not think the relative superiority of one measure w.r.t. the other could anyhow impact the novelty, relevance or importance of our contribution. The focus on walk-based centralities arose naturally from our analysis in Section 2; it is then, by observing the resemblance between the terms involved in the calculation of these measures and the terms in RWSEs, that we believed a more comprehensive discussion would be informative for readers. This justified our articulated comparison in Appendix D.2.

We would like to deeply thank the reviewer for their outstanding effort. The review is comprehensive and constructive and we profoundly appreciate the provided inputs.

Here in the following we specifically respond to the points they raised above.

“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 [...] their practical value in enhancing graph learning remains uncertain, there is no guarantee on the usefulness and attainability of such modifications.”

Generally speaking, theoretical analyses can provide us with indications that a certain method could be practically beneficial, but, ultimately, experimental results will be critical in determining the practical value of a certain approach. As an example from adjacent literature: theoretical analyses on the ability of a GNN to discriminate (often exotic pairs of) non-isomorphic graphs do not give theoretical guarantees on generalization performance; experimental results, however, complement these analyses to demonstrate the utility of the method. In our work we followed a similar approach, in that we gathered helpful indications from theoretical and empirical observations and complemented these with experimental validations.

More specifically, the theoretical observation reported in Section 3 takes the form of an upper-bound. It shows that the perturbation node marking induces w.r.t. the representation of a standard message-passing procedure is upper-bounded by a figure that is a function of the cumulative number of walks. What this implies is that marking nodes with the lowest such values may not guarantee to alter such representations enough. Aiming at conceiving an effective sampling strategy, we thus build upon this observation and complement it with experiments whose results are reported in Figure 1 and Table 1. There, we empirically explore the behavior of perturbations when marking nodes with low and high values for (walk-based) centrality values (as well as random sampling strategies). First, the results in Figure 1 show that high-centrality marking tends to produce higher perturbations, something not necessarily entailed by the aforementioned bound-analysis. Second, the results in Table 1 further indicate that these higher perturbations better correlate with counts of various substructures.

Complementary to Table 1 and Figure 1, we further explore how larger perturbations induced by higher-centrality marking can eventually be beneficial in enhancing the method’s performance after training. The results in Figure 3 and Appendix D already provide us with an indication of this, as marking nodes with highest centrality values performs better than random markings. We extended these experiments by also evaluating the performance of marking nodes with minimum centrality values. These results – expressed in Mean Absolute Error – further complement our findings:

Triangles

4-cycles

Taken together, all these theoretical and empirical observations provided us with an indication that marking nodes with higher centrality values represents a (simple and) valid sampling strategy. Let us conclude by remarking that the practical value of our approach is then eventually verified through the comprehensive set of experimental results on real-world datasets reported in Section 5.

Dear Reviewer pVQU,

We hugely appreciate the time and effort you have made on our paper and believe that you have contributed greatly to the manuscript's improvement.

Comparison of Centrality Measures

We agree that the manuscript could be improved by better outlining our comparison between centrality measures. As you have suggested, we have added figure 6 to the main paper in order to show the advantages of centrality measures in general and, in particular, subgraph centrality. To further show this point, we have made a comment about their empirical advantages in lines #427-429 of the main paper. Here, we also reference the Appendix where we have performed a more extensive comparison between centrality measures and added the real-world experiments outlined in our initial rebuttal. We additionally provide remarks and indications about the choice of the centrality measure in accordance with our discussion (see lines #1286-1290)

Hyperparameter T

We are sorry for not being clearer about this parameter selection in the original text. In Appendix E.3 (lines #1516 - 1518), we have now specifically outlined the reasoning behind our choice of T on the different datasets in the manuscript. As discussed in the rebuttal, this was done to either match the choices made in other baselines, such as PL (i), or as the smallest possible value, i.e., T=1 (ii). Choice (i) contributed to making comparisons as informative as possible, (ii) is justified by our focus on efficiency.

Typo in proposition

Thanks for pointing this out! Indeed, we have changed this to $k − (j − 1)$ in the revision

We would like to again thank the reviewer for the efforts they have made in reviewing and discussing our manuscript

We thank the reviewer for their feedback. Here, we respond to the weaknesses and questions point by point.

“Incomplete abstract? [...]”

In order to add further contextualization, and in accordance with the reviewer’s suggestion, we propose to rephrase the first sentences of the abstract as follows:

Popular extensions of Graph Neural Networks (GNNs) are Subgraph GNNs, which enhance expressiveness by processing bags of subgraphs obtained from predefined selection policies. Although more powerful, these networks suffer from a problematic computational complexity. Addressing this issue, we propose an expressive and efficient approach which leverages walk-based centrality measures, both as an effective subgraph sampling strategy for Subgraph GNNs and as a powerful form of Structural Encoding (SE). [...]

We hope that this new version improves clarity in regards to the addressed problem, but we are open to further changes should the reviewer have additional comments/suggestions.

“Experimental Validation of CSEs: I noticed that experiments on the effect of CSEs in the Peptides and Zinc datasets were not conducted.”

We thank the reviewer for suggesting important comparisons which can improve the paper. We have now run some further experiments to appreciate the effect of CSEs on Zinc and Peptides, see below:

These results further show that adding even one subgraph with our approach can be beneficial and that additionally using the centrality measure as a structural encoding can also improve performance. This is in line with what is argued in the paper and we hope these further experiments provide additional clarity to the manuscript. We have added these results to the manuscript in Appendix D.3 and reserve to further extend these experiments to larger values of $T$.

“Exploration of selection strategies: the paper would benefit from exploring more complex selection strategies and different walk-based centrality measures.”

Our main goal is to develop an effective, simple and, importantly, efficient sampling strategy, as opposed to more complex techniques requiring lengthy and more sophisticated training protocols. Given our focus on efficiency, in our paper we further explored the impact of strategies based on different centrality measures or based on Random Walk Structural Encodings. All these results can be found in Appendix D.

We agree however that more experiments on real-world datasets and by other walk-based centrality measures could be informative and improve our manuscript. Here we report additional results obtained by the Betweenness Centrality (BC), the Katz Index (KI) and the Subgraph Centrality (SC), on the peptides and molhiv datasets. Both KI and SC are walk-based centrality measures.

We observe that, even on these real-world tasks, the two walk-based centrality measures tend to outperform the BC, while we still could not find empirical evidence of a measure outperforming SC. These results are in line with those in Appendix D and provide further indication that walk-based approaches could be more suited to subgraph sampling when combined with message-passing backbones.

“Typos and formatting issues”

Thank you for pointing this out. We have made our best to improve on this aspect: our paper revision fixes typos and related issues in order to improve clarity (see corrections in red).

“Section 2: clarification of content – though Section 2 is titled “PRELIMINARIES AND RELATED WORK,” it primarily focuses on related work without adequately presenting the foundational definitions”

In agreement with the reviewer, in our next revision: (i) we change the title of Section 2 to “Related Work” and include a new supplementary Appendix F, titled “More on Subgraph GNNs and their Complexity”. This appendix introduces Subgraph GNNs and discusses in detail aspects related to our present contribution: node marking policies, computational complexity aspects and the approach of subgraph sampling.

We thank the reviewer for their feedback and their positive response. Here, we respond to the weaknesses and questions point by point.

“The sampling strategy does not consider interactions between sampled subgraphs that are already sampled, which can lead to potential redundancy. The analysis focus primarily on single-node marking. While mentioned in the limitations, extending the analysis to multi-node marking could provide addiitonal [sic.] insights.”

These are very important and interesting points which you make. Indeed, future work should consider the effect of incorporating information from previously sampled subgraphs, similar to Policy-Learn [1]. We also note that the example provided by the reviewer to highlight the importance of multi-node marking (“Alice, Bob, Carol”) could also be addressed by considering interactions with already sampled subgraphs; the sampling strategy could, for example, refrain from marking nodes with small shortest-path-distances w.r.t. already marked nodes.

Here we note that, when empirically comparing against Policy-Learn on a small number of subgraphs, our simpler strategy can match and sometimes outperform this method. This leads us to hypothesize the aforementioned interactions may be less practically impactful when considering very small bags. It is also important to remark that more sophisticated strategies accounting for interactions with already sampled subgraphs would likely lead to more complex and less computationally efficient approaches, against our main high-level desiderata.

We hope that, in any case, this paper and the connection provided to perturbation analysis provides a “solid foundation” which can be extended in future work to more sophisticated sampling strategies which could also consider concurrently marking multiple nodes.

“The approach can be less effective on graphs where walk-based centrality measures don’t align with task objectives. [...]”

This is another relevant observation and is, in fact, a difficulty encountered by all graph learning architectures which use “pre-defined features”, e.g. Structural Encodings. However, we do find notable benefits with our approach. It is a simple and efficient measure that we observed can match or outperform learnable policies (Table 2). In Tables 3 and 4, we found our method to work well when compared against many strong baselines on a set of experiments you also positively highlighted to be comprehensive.

In reference to the provided drug-discovery example, we note that, although the acetyl group may not necessarily be the object of marking, its representation can in any case be altered and potentially be improved by marking other more central molecular sites, provided enough message-passing layers.

Overall, we found that the walk-based centralities are fast to precompute, arise from our perturbation analysis and perform well on a range of tasks, indicating that they are strong candidates for our model. However, we note that more specific measures for particular applications could be explored.

“Have you investigated how the performance of your sampling strategy varies with graph density?”

The real-world datasets we used in the paper are all sparse. Zinc (mean #nodes: 23.2 , mean #edges: 24.9), MOLHIV (mean #nodes: 25.5 , mean #edges: 27.5), Peptides (mean #nodes: 150.9 , mean #edges: 307.3) all demonstrate the performance improvements of using our walk-based centrality on sparse graphs. Additionally, our counting substructure experiments are performed on much denser graphs (mean #nodes: 60 , mean #edges: 240) giving us evidence that our approach can work well across graph densities.

“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?”

We do not clearly see an obvious way to improve the tightness of the upper-bound based on characteristics of the graph distribution at hand. However, it could be interesting to derive more specific – and perhaps tighter – upper-bounds for recent GNN architectures that are tailored to specific graph distributions such as planar graphs [2][3].

We appreciate feedback and response received by the reviewer. Below, we specifically address the concerns and questions raised.

“The two main components (subsample subgraph using centrality measure, and centrality-based structural encoding) are similar with previous work.”

Our contribution is, in fact, orthogonal to these works. Indeed, in [1], the authors use Reinforcement Learning to pool representations of subgraphs of the original graph. In GraphGPS [2], the authors propose design strategies for Graph Transformers (GTs), including the use of a random-walk based structural encoding. Effectively, neither of these works consider walk-based centralities and neither of these works subsample subgraphs tied to specific nodes in the original graph to improve expressivity in an efficient way. While these papers may discuss somewhat related ideas, our work substantially differs both in its technical contributions and in the problem it addresses, and we believe it clearly provides novel inputs and methodologies to the community. Either way, we have added [1] as a citation to improve completeness in our new background section in the Appendix which we discuss below.

“A more detailed introduction to the key background of this work would be helpful”

We agree with the reviewer that adding a more detailed background would improve the quality of our manuscript. We include such an extended discussion in a new supplementary Appendix F, namely: “More on Subgraph GNNs and their Complexity”. This section introduces Subgraph GNNs in general and discusses, more in detail, those aspects which pertain more to our present contribution: node marking policies, computational complexity aspects and the approach of subgraph sampling.

“More backbone (except GIN) and more baselines should be considered”

We report that, beyond GIN, we have already experimented with GCN as the backbone on the Peptides datasets, which proved very successful. GCN and GIN are not only the two most popular MPNN architectures, but also, the most widely adopted Subgraph GNN backbones. Due to this, we believe our experiments are particularly informative for the community. In any case, in agreement with the reviewer’s suggestion, we have performed further comparisons that can help improve the quality of our manuscript. In particular, we have additionally run GCN as a backbone on OGB molecular datasets, with results reported below.

Interestingly, we find that a GCN backbone achieves the best results on MOLBACE. We will ensure that all of the substantial comparisons with GIN and GCN as backbones will be added to the paper. We would like to further report that we have run experiments with yet another backbone: GatedGCN [3]. This complements backbones used in the Graph Transformer literature such as GPS. The results on Peptides and MolHIV are shown below.

Again, these results empirically strengthen the findings already reported in the paper. The walk-based centrality structural encoding can improve performance over the backbone MPNN, and we can improve the performance even further by using it for sampling subgraphs.

As for the baselines, we selected those that were either directly comparable to our approach (Policy-Learn, Full-bag) or popular, prototypical SOTA methods such as Graph Transformers (GPS) or higher-order methods (CIN). Our method clearly demonstrated its utility across all experiments and against both categories of approaches as it either outperformed or worked equally well with reduced run-time.

Either way, to improve on uniformity and completeness, we have added two additional baselines on the Zinc and MolHIV datasets: “Graph ViT” and “G-MLP-Mixer” which can be seen in Table 4 of the revision.