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

The reviewer found the paper “solid and impactful”, the method as “an important advance in the field”, “reasonable”, “effective” and “motivated” by experimental results. They manuscript is also found “well-written".

We address comments below.

---

“There seems to be a large discrepancy between the motivating observations and experiments of Section 3.2, and the proposed method itself. [...] this should be discussed explicitly in the manuscript.”

In Section 3.2 we look at the optimal initial subgraph selection to (i) alter the base MPNN’s graph representation sufficiently and (ii) in a way that correlates with predictive information (e.g. subgraph counts). When only one subgraph is chosen (T=1), this approach exactly aligns with the proposed method, and we disagree there is a discrepancy in this case. Also, T=1 is, by far, the most compelling setting from a complexity perspective and our model attains very strong performance for this.

Overall, we optimized for a sampling strategy that was efficient and non-learnable, and accordingly considered the case where every subgraph selection is made w.r.t. the original graph representation. We acknowledge that further theoretical insights could be gained on partially filled bags; we mention this in line 435 and will emphasize this more.

---

“The subgraph centrality structural encoding proposed in the paper is simply a rescaling of the RWPE, [...] This maybe should be stated more clearly.”

We acknowledge the similarity between RWSEs and CSEs. In fact, we devote Section F.4 to discuss their relation.

Proposing CSEs as a new form of SEs is not the (main) contribution of our manuscript. CSEs emerge from the centrality computations required for subgraph sampling: we propose to retain them and show the benefit of this in terms of discriminative power. We will clarify this point further.

---

“The baseline of GIN + CSE should be added to the experiments on ogb data.”

We agree. We conducted these experiments during the rebuttal period and report the results below:

These results support the effectiveness of our centrality-based strategy. We will include them in Table 2.

---

“The method is benchmarked on relatively few datasets, all of which are molecular ones, except MalNet-Tiny. For a mostly experimental paper like this one, more datasets would be preferred.”

We note that, although effectively molecules, peptides differ substantially from the small drug-like molecules in ogbg datasets—in size, structure, and biological role. Actually, we argue this makes for three different data domains.

That said, we agree broader benchmarking would strengthen our work. To this end, during the rebuttal period we additionally evaluated our method on the Reddit-binary (RDT-B) dataset—a fourth domain (social networks). RDT-B is significantly larger than ogbg graphs and is too large for full-bag Subgraph GNNs. Results, obtained under the setup from [1], are below:

HyMN matches the performance of the learnable POLICY-LEARN, coherently with results obtained on other datasets. We will add the above in the next paper revision.

[1] https://arxiv.org/abs/1810.00826

---

“It would be useful to have a figure to illustrate node-marking-based Subgraph GNNs, with and without a subsampling approach like HyMN.”

Thanks for the suggestion – we have accordingly prepared a figure currently hosted at this anonymous link. We plan to add it in the next paper revision (Section B).

---

“Most real word [sic.] datasets, especially molecular ones, don't really require expressive power higher than 1-WL [...] Do you have an intuitive explanation on why Subgraph GNNs nonetheless show higher predictive performance [...] ?”

This is an open question in graph learning. Higher separation power may not be needed, or even harmful if obtained by spurious features. Yet, expressive models like Subgraph GNNs often generalize better. A reasonable hypothesis is that these form a representation space with “more convenient” graph separation, one that makes solving the downstream task more amenable, e.g. by “aligning” with predictive motif counts. Some of these intuitions are echoed in our approach.

---

We hope our responses clarify the raised concerns. We would kindly ask the reviewer to reconsider their scores in view of them.

We are very pleased to note the positive recommendation made by the reviewer. They have appreciated the proposed application of Network Science results to Deep Learning, and have found the paper “extremely well written”, with claims supported by “clear arguments and empirical evidence”.

The reviewer had a clarity concern pertaining to tackled tasks and result interpretation, along with some questions. We address these points in the following.

---

“I find that the authors should be more explicit regarding how the results of their evaluation should be interpreted. [...] they count sub-structures in Erdős–Rényi random graphs and measure the performance of their scheme in terms of Pearson correlation. But how should we interpret those values? [...] Also, based on the datasets used in Table 2, I guess that the considered task is graph classification [...]”

Substructure counts: in Sections 3 we report results in terms of Pearson correlation. The aim of these experiments is to understand how much substructure counts are recapitulated by the perturbations induced by different marking strategies. We agree that absolute correlations may be difficult to interpret per se, but, in relative terms, it is very valuable to observe how the various marking strategies rank w.r.t. each other.

Eventually, these rankings give us an indication on how the strategy will perform in the actual task of counting substructures, which we study in Section 5. This time, these results are quantified in terms of Mean Absolute Error, and are reported in Figures 3 and 7. We will better highlight these aspects in the next revision. As for results reported in Table 2 – yes, we confirm all the three benchmarks involve graph classification. We will make sure to state this clearly.

---

“Are there any limitations regarding what kinds of graphs the proposed approach can be applied to? [...] is the only requirement that the chosen centrality measure must be able to assign centrality scores to all nodes?”

Yes, this is correct. As long as the centrality measure ranks all the nodes in a graph, the method can be run without any caveat.

Regarding directionality: our focus is mostly on undirected graphs, consistently with virtually all previous works on Subgraph GNNs. As such, our analysis does not specifically discuss the case of directed graphs, but one could clearly consider a centrality measure that is well-defined thereon. An interesting avenue for future research would be to extend perturbation analyses on directed graphs and study whether known centrality measures allow to well capture these effects, similarly to how we proceed in our manuscript.

---

“Why is there a difference between degree centrality and PageRank in Figure 3? [...]”

While it is true that the two centrality measures are often found to produce similar node rankings in undirected graphs, we note that they are not generally equivalent in this setting. The degree centrality only accounts for first-order node interactions, whereas Page-Rank also considers the effect of higher-order neighbours. In the latter case, two nodes with the same degree would, e.g., be ranked differently if they connect to a different number of high-degree neighbours.

---

”What is the reason for the missing values in Table 2?”

We thank the reviewer for pointing this out. We chose these ogbg-molecular benchmarks to capture a good overlapping set of datasets on which previous sampling-based Subgraph GNNs were tested on. The results in Table 2 are directly taken from the original papers and, unfortunately, some methods were not uniformly benchmarked on these datasets. This explains the “missing numbers”. We will be more clear about this in the next revision.

---

”[...] Yes, selecting the nodes with the highest centrality values works better than random selection or selecting those nodes with low centrality values. But is there another set of nodes that should be preferred over those with the highest centrality values? [...] it should be possible to quantify how well the proposed selection scheme works in comparison to the optimal set of nodes of the same size that could be chosen.”

This is an interesting point, and we agree that quantifying optimality could be particularly insightful. We also note, however, that optimality is ultimately defined with respect to a particular learning task. To find an optimal set which also accounts for learning would quickly become computationally challenging. We respectfully believe this experiment could not be run in a thorough manner within the rebuttal period. We will, either way, point out this interesting direction in the next revision.

(W1) “The two experiments use very different types of graphs [...] it would be helpful to standardize.”

We used TU datasets for perturbation analyses aligning with [1], but we agree standardization would be preferred. As suggested, we re-run them on the same ER graphs in the subgraph-count correlation study. The results (link) are consistent with our prior findings, and will be included in the new revision.

---

(W2) “[...] theoretical results rule out low-centrality nodes [...] don't strongly establish that choosing high-centrality nodes is necessarily optimal. [...] analysis interesting but not entirely conclusive.”

We agree that our approach is not necessarily optimal and, in fact, note that an optimal selection would also require access to targets and to account for learning. Our goal is to design an efficient subgraph selection that is run as preprocessing and achieves effective performance.

Although our approach lacks optimality guarantees, it:

• is theoretically grounded via the connection to perturbation analyses (found “interesting”);
• leads to consistent empirical gains with contained overhead.

Also, HyMN always performed at least as well as a learnt selection strategy, indicating its actual effectiveness once more. We think the above already provides an important contribution to the community, and believe further theoretical analyses on optimality warrant interesting future research.

---

(W3) “The discussion on why structural motifs are desirable could be expanded.”

Motif counts are widely recognized as important graph features: in Network Science, motif profiles have been used to compare and classify networks; the GNN community has also explored their utility due to message-passing limitations in detecting them. A seminal paper [2] even proposed to employ them as SEs, showing the significant expressivity and generalization boost they can provide.

Starting from these premises, and provided that node-marking subgraphs enhances expressivity, we argue it would be preferable to choose those subgraphs which, amongst others, better enable the model to capture subgraph counts. We quantify this by studying the correlations between counts and the mark-induced graph perturbations. Our results indicate they are maximized when marking based on the highest Subgraph Centrality (see Table 1). These findings – as well as our more general argument – find supporting evidence in the experimental results reported in Figure 3.

---

“[...] observation 1: why don't node features come into play?”

Because we have to consider the TMD not between two generic graphs, but between a graph and the node-marked version thereof, where node feats. coincide.

---

(W4) “[...] experiments [...] not including the other potentially relevant baselines. [...] POLICY-LEARN is omitted from Tables 3 and 4 [...]”

In fact, Table 2 already includes additional efficient Subgraph-GNNs baselines beyond POLICY-LEARN: OSAN and MAG-GNN. These are in a separate table lane, likely causing confusion. We will improve the layout in the next revision.

Either way, we agree that reporting the performance of other methods would strengthen our claim. In fact, molhiv is a reference test-bed for most full-bag methods. We will add these additional results:

HyMN competes with the best full-bag approaches with only two subgraphs.

As for non-full-bag Subgraph GNNs, we will additionally include results (ROC-AUC) for CS-GNN [3], which we found has been benchmarked both on molhiv, and molbace. Note HyMN’s competitive performance compared to this method.

Peptides, MalNet (Tables 3, 4): POLICY-LEARN was not originally evaluated thereon. We attempted this using the authors’ code.

On MalNet-Tiny, memory usage exceeded our server’s capacity (1TB CPU RAM) due to the full bag materialization required by their implementation. Optimizations may be possible but infeasible within the rebuttal window.

On Peptides, we obtained:

We finally refer to the response to Reviewer d9AX for additional results on Reddit-binary.

---

We hope your concerns are clarified, while we are open to elaborate further.

[1] https://arxiv.org/abs/2210.01906

[2] https://arxiv.org/abs/2006.09252

[3] https://arxiv.org/abs/2406.09291

We are very glad to note the reviewer found the paper “extremely well-written”, that it “picks the right ideas and puts them together nicely” and, importantly, that they believe the underpinning idea “holds promise for spurring on further work in this area”.

The reviewer shared the view that the joint use of both SEs and Centrality-based sampling may weaken the claim for the effectiveness of the latter as an approach on its own. We understand that the hybrid nature of our approach may lead to this perception, but we believe it is important to underscore the effectiveness of the centrality marking alone.

Even without our positional encodings (CSEs), on the ogbg-molecular benchmarks HyMN outperforms MPNN baselines and methods based on random subgraph sampling, while it matches the performance of the learnable approach Policy-Learn (see Table 2). HyMN without CSEs also attains successful results on the larger MalNet dataset, scoring the highest average test score in the configuration T=1 when compared to other HyMN variants and transformer-based baselines (see Table 4).

We conclude by complementarily remarking how baselines methods like GIN and GCN, when augmented with CSEs, fail to match the full HyMN performance. We observe this in Table 3 on the peptides datasets and on the molecular ogbg benchmarks as well. We report, indeed, that we have additionally run GIN with CSEs thereon. We obtained the following results, which we report, for reference, along with the performance attained by HyMN in the configuration T=2:

We hope this clarifies the raised concern. We would kindly ask the reviewer to reconsider their scores in view of our response.