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
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Subgraphs
Expressivity
Graph Centrality
Primary area: deep_learning->graph_neural_networks
TL;DR: We introduce a framework which drastically reduces the computational cost of Subgraph GNNs by leveraging walk-based centralities, both as an effective subgraph sampling strategy and as a form of powerful Structural Encoding.

Abstract: Subgraph GNNs have emerged as promising architectures that overcome the expressiveness limitations of Graph Neural Networks (GNNs) by processing bags of subgraphs. Despite their compelling empirical performance, these methods are afflicted by a high computational complexity: they process bags whose size grows linearly in the number of nodes, hindering their applicability to larger graphs. In this work, we propose an effective and easy-to-implement approach to dramatically alleviate the computational cost of Subgraph GNNs and unleash broader applications thereof. Our method, dubbed HyMN, leverages walk-based centrality measures to sample a small number of relevant subgraphs and drastically reduce the bag size. By drawing a connection to perturbation analysis, we highlight the strength of the proposed centrality-based subgraph sampling, and further prove that these walk-based centralities can be additionally used as Structural Encodings for improved discriminative power. A comprehensive set of experimental results demonstrates that HyMN provides an effective synthesis of expressiveness, efficiency, and downstream performance, unlocking the application of Subgraph GNNs to dramatically larger graphs. Not only does our method outperform more sophisticated subgraph sampling approaches, it is also competitive, and sometimes better, than other state-of-the-art approaches for a fraction of their runtime.

Fabrizio Frasca <fab- Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk- Baake Centrality
Joshua Southern
Yam Eitan Guy Bar-Shalom
Michael M. Bronstein 34 Haggai Maron 25
Fabrizio Frasca
Abstract
1. Introduction
Graph Neural Networks (GNNs) (Scarselli et al., 2009; Gori et al., 2005; Micheli, 2009) have achieved great success in learning tasks with graph-structured data. Typically, GNNs are based the message passing paradigm (Gilmer et al., 2017), in which node features are aggregated over their local neighborhood recursively, resulting in architectures known as Message Passing Neural Networks (MPNNs). MPNNs have been shown to suffer from limited expressive power: they are bounded by 1-WL. (Xu et al., 2018; Geerts & Reutter, 2023; Weisfeiler & Leman, 1968; Morris et al., 2019; 2023) cannot count certain substructures (Chen et al., 2020; Bouritsas al., 2022; Tahmasebi et al., 2020) or solve graph bi- bi-connectivity tasks (Zhang et al., 2023b).
Subgraph GNNs have emerged as promising ar- chitectures that overcome the expressiveness lim- itations of Graph Neural Networks (GNNs) by processing bags of subgraphs. Despite their com- pelling empirical performance, these methods are afflicted by a high computational complexity: they process bags whose size grows linearly in the number of nodes, hindering their applicability to larger graphs. In this work, we propose ef- fective and easy-to-implement approach to dra- matically alleviate the computational cost of Sub- graph GNNs and unleash broader applications thereof. Our method, dubbed HyMN, leverages walk-based centrality measures to sample a small number of relevant subgraphs and drastically re- duce the bag size. By drawing connection perturbation analysis, we highlight the strength of the proposed centrality-basen subgraph sam- pling, and further prove that these walk-based centralities can be additionally used as Structural Encodings for improved discriminative power. comprehensive of experimental results demon- strates that HyMN provides an effective synthesis of expressiveness, efficiency, and downstream per- formance, unlocking the application of Subgraph GNNs to dramatically larger graphs. Not only does our method outperform more sophisticated subgraph sampling approaches, is also competi- tive, and sometimes better, than other state-of-the- art approaches for fraction of their runtime.
Recently, Subgraph GNNs (Bevilacqua et al., 2021; Frasca et al., 2022; Zhang & Li, 2021; Cotta et al., 2021) have been proposed to overcome some of the expressivity limi- tations of MPNNs. This approach preserves equivariance while relying less feature engineering. First, Subgraph GNN transforms graph into a "bag of subgraphs" based a specific selection policy. These subgraphs are then processed by an equivariant architecture and aggregated to make graph- or node-level predictions. One common ap- proach to generate subgraphs, known as node-marking, to mark a single node in the graph (Papp & Wattenhofer, 2022). In this case, each subgraph is then "tied" to specific node in the original graph, and shared MPNN generates a representation for each subgraph.
In general, Subgraph GNNs show good empirical perfor- mance but come with a high computational cost. For a graph of N nodes and maximum degree dmaxs then Sub- graph GNNs with node-marking based policies have a com- putational complexity O dmax). To reduce compu- tational complexity, it was suggested sampling subgraphs randomly (Bevilacqua et al., 2021; Zhao et al., 2022) or, more recently, learning sampling policies (Qian et al., 2022; Bevilacqua et al., 2024; Kong et al., 2024). However, while random approaches have been shown be subop- timal (Bevilacqua al., 2024; Sar-Shalom et al., 2024b), learnable policies are difficult to train in practice and be- come impractical when sampling larger number of sub-
'Equal technical contribution 'Imperial College London TTechnion Israel Institute of Technology UUniversity of Ox- ford "AITHYRA 'NVIDIA Research. Correspondence to: Joshua Southern xjksl7@ic.ac..a riziof@ campus.teccheee tew.puss.cchiio............
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
graphs, due to the use of discrete sampling and RL-based objectives.
Additionally, HyMN is competitive to (and sometimes better than) Graph Transformers and other state-of-the-art GNNs, while, as we show through extensive wall-clock timing anal- yses, features a dramatically reduced computational run- time.
Summarizing, while Subgraph GNNs have demonstrated promising results on small molecular graphs, their computa- tional requirements make them impractical for graphs larger than a few tens of nodes. This severe limitation needs to be addressed in an effective way to broaden the application of these models.
Our contributions are summarized as follows:
1. We show that walk-based node centrality measures and, in particular, the Subgraph Centrality of Estrada & Rodriguez-Velazque (2005), represent simple and effective indicator of subgraph importance for subsam- pling bags in Subgraph GNNs.
Our approach. In this work, we present an approach that drastically reduces the complexity of Subgraph GNNs while maintaining their competitive performance. We achieve this by identifying rasy-to-compun structural features that unlock a simple yet effective subgraph selection strategy, while providing complementary information enhancing the model's expressiveness.
2. We demonstrate that centrality- based structural fea- tures can be employed as Structural Encodings to en- hance the discriminative power of Subgraph GNNs with subsampled bags of subgraphs.
3. We provide strong experimental evidence showcasing the effectiveness of our sampling strategy and the ef- ficacy of additionally incorporating centrality-based SEs.
We first identify family of node centrality mea- sures (Estrada & Modriguuz-Vellzzqeez 2005; Benzi & Klymko, 2013; 2014) as easy-to-compute scores that: (i) recapitulate well the extent to which a subgraph alters the graph representation; (ii) correlate with relevant substruc- ture counts. In light of this, we propose to leverage these measures to efficiently and effectively reduce the size of bags of subgraphs without requiring additional learnable components. Specifically, we prioritize selecting marked subgraphs associated with the top-ranking nodes accord- ing to these centrality measures and, in particular, to the Subgraph Centrality by Estrada & Rodriguez- Rodriguez-Velazquez (2005). Then, we propose to additionally interpret central- ity scores Structural Encodings (SRs) (Bouritsas al., 2022; Dwivedi et al., 2021; Fesser & Weber, 2024), and to utilize them to augment the node features of the selected subgraphs. This combination of approaches is justified from an expressiveness perspective, as we show neither of the two subsume the other. We demonstrate node marking of (se- lected) subgraphs separates graphs that are not separable by Centrality- based SE (CSE) feature augmentations and, vice- versa, that CSEs allow to separate pairs indistinguishable to our subsampled Subgraph GNNs.
4. We show how our approach enables to scale to substantially larger graphs than previously possible, even tens or hundreds of times larger.
Overall, our results validate our method simple, expres- sive and efficient approach that competes with state-of-the- art GNNs for a fraction of their empirirical run-times.
2. Related Work
Expressive power of MPNNs. The expressive power of MPNNs has become a central research topic since they were shown to be bounded by the 1-WL isomorphism test (Morris et al., 2019; Xu et al., 2018; Morris et al., 2023). This has led to approaches which aim to obtain different representations for non-isomorphie but 1-WL equivalent graphs. These include using random features (Sato et al., 2021; Abboud et al., 2021). higher-order message passing schemes (Bodnar et al., 2021b;a; Morris et al., 2019; 2020b) and equivariant models (Maron et al., 2018; Vignac et al., 2020). One of the most common approaches is to inject positional and structural encodings into the input layer (Bouritsas et al., 2022; Fesser & Weber, 2024; Dwivedi et al., 2021; Kreuzer et al., 2021) using Laplacian PEs (Dwivedi & Bresson, 2021; Kreuzer al., 2021: Wang et al., 2022; Lim et al., 2023; 2024), distance information (Ying et al., 2021; Li al.. 2020), random-walk encodings (RWSE) (Dwivedi et al., 2021).
The resulting method, dubbed HyMN (Hybrid Marking Network), is an approach whereby Subgraph GNNs and Structural Encodings work in tandem to effectively over- come the expressiveness limitations of MPNNs and unlock the application of Subgraph GNNs larger graphs previ- ously out of reach. Our approach is provably expressive, does not require feature engineering or learnable sampling components, and, importantly, maintains low computa- tional cost. The practical value of our approach is confirmed by the strong results achieved over a series of experimental analyses conducted over synthetic and real-world bench- marks. We show HyMN outperforms other subgraph selec- tion strategies, and performs on par or better than full-bag Subgraph GNNs by only sampling one or two subgraphs.
Subgraph GNNs. A recent line of work has proposed representing a graph as a collection of subgraphs obtained by a specific selection policy (Zhang 20,1; Cotta et al., 2021; Papp & Wattenhofer, 2022; Bevilacqua al., 2021; Zhao et al., 2022; Papp et al., 2021; Frasca et al., 2022; Qian et al., 2022; Huang et al., 2023; Zhang et al., 2023a). These
2

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
approaches, jointly referred as Subgraph GNNs, allow to overcome the expressivity limitations of MPNNS without introducing predefined encodings. A powerful, common selection policy termed node marking involves generating a subgraph per node by marking that node in the original graph, with no connectivity alterations. Although can increase expressive power beyond I-WL (Frasca et al., 2022:
clude the Katz Index (Katz, 1953) (KI) and the Subgraph Centrality (Estrada & Rodriguez-
Rodriguez~Velazzuezz Velazquez, 2005) (SC):
gk
KI
= Σ h E(A Amm 8
(4*)a) ja
(1)
k!
k=0
You et al., 2021), this approach has a high complexity as it needs consider and process N different subgraphs, N being the number of nodes in the original graph.
and variants of the above, for appropriate choices of 0 < a < 3 > 0' (Benzi & Klymko, 2013; 2014). By scoring nodes based on the cumulative number of walks that start from them, these centrality measures extend the Degree Centrality beyond purely local interactions, in way that depends on the discounting scheme (a* and g for KI and SC, respectively).
Scaling Subgraph GNNs. Several recent papers have fo- cused on scaling these methods to larger graphs. Beyond random sampling (Bevilacqua et al., 2021; Zhao et al., 2022), Qian et al. (2022) first proposed gradient- based techniques to learn how to subsample the bag of subgraphs. Bevilacqua et al. (2024) introduced Policy-Learn (PL), which iteratively predicts a distribution over nodes in the graph and sam- ples subgraphs from the full-bag accordingly. A similar approach, called MAG-GNN has also proposed to sam- ple subgraphs using Reinforcement Learning (RL) (Kong et al., 2024). Both of these approaches involve discrete sampling which can complicate the training process, often requiring 1, 0,000- 4, 000 training epochs. Another recent ap- proach leverages the connection between Subgraph GNNs and graph products (Bar-Shalom et al., 2024a) to run mes- sage passing on the product of the original graph and a coarsened version thereof (Bur-Shalom et al., 2024b). The control over the computational complexity generally comes from the existence of cluster-like structures in the graph which, however, may not be aligned with the preset number of subgraphs. Additionally, the locality bias afforded by the coarsening may not generally be effective across tasks. In such cases, coarsening approaches that are not learnable and based, e.g., on spectral clustering could lead to sub- optimal results, For an extended background on Subgraph GNNs, the node marking policy and efforts around scaling this family of architectures, we refer readers to Appendix B.
AT
3. Subsampling Subgraph Neural Networks
3.1. Problem Setting
We focus on Subgraph GNNs with mode-marking selection policy (Papp & Wattenhofer, 2022; You et al., 2021). Given an N-node graph G = (A, X), a node-marking Subgraph GNN processes a bag of subgraphs obtained from G, viz. BG = { S2....... Sx B. Here, S. = (A, Xx) and X; = X @ Fuy, where (1 denotes channel-wise concatenation and Tyj is a one-hot indicator vector for node Ui.
Goal. In order to reduce the computational complexity of a Subgraph GNN, we aim to reduce the size of the bag by efficiently and effectively sampling k N subgraphs. The sampling procedure must be efficient in that it should avoid computationally complex operations or the use of learnable components requiring more involved training pro- tocols (Qian et al., 2022; Bevilacqua et al., 2024; Kong et al., 2024). Ideally, it should consist of a simple and lightweight preprocessing step prior to running a chosen Subgraph GNN. The sampling procedure must addition- ally be effective, which means it should closely approach the performance of full-bag Subgraph GNN with as few subgraphs as possible. Put differently, it should prioritize marking those nodes that most quickly lead to performance improvements. As an example, to ground the discussion: randomly selecting subgraphs (Bevilacqua et al., 2021; Papp et al., 2021) is an efficient but not effective strategy; learn- ing which subgraph to mark via RL (Kong et al., 2024) is a more effective approach, but it may not be efficient enough.
Node Centrality. One common way to characterize nodes in a graph is by using the concept of node centrality. A node centrality measure defines a real-valued function on the nodes, c : V + R. which can be used to rank nodes within a network by their "importance". Different con- cepts of importance have led myriad of measures in the Network Science community. They range from the simple Degree Centrality (central nodes have the highest degrees) to bath-based methods (Freeman, 1977) like the Betweenness Centrality (central nodes fall on the shortest paths between many node-pairs). An important family of centrality measures quantifies the importance of nodes based on walk counts. As noted in (Benzi & Klymko, 2014), most of these measures take the form of a power series, where numbers of walks for any lengths are aggregated with appropriate discounting scheme. Prominent examples in-
We start by presenting considerations on effectiveness which will naturally lead us to focus on walk-based centrality mea- sures for our purposes. Upon them, we show we can build an effective strategy that is also efficiently executed as a simple preprocessing step.
'A refers to the first eigenvalue of A, ,3 is typically set to 1.
3

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
3.2. Effective Node Marking
term (A) in Equation (3)) This leads us direct our focus to walk-based centrality measures as promising candidates for selecting which node to mark. Considering we would like to sufficiently alter the graph representation beyond the one from a standard MPNN, Observation I indicates that, among all possible nodes, those associated with small cumulative numbers of walks will be poor marking candi- dates. We propose to summarise this form of information via walk-based centrality measures. Our strategy will be to rank nodes based on their centrality values, and mark the top-scoring ones. Next, we empirically verify the valid- ity of this approach, and defer readers to Appendix E for extensions and more considerations on the above analysis.
What makes node good marking candidate? We propose approaching this question by considering node marking as graph perturbation. Marking node changes the initial node features: this alteration in the input will ultimately be re- flected in the output graph representation, and understanding how node marking impacts the output graph representation is instrumental in designing effective sampling strategies. Beyond binary graph separation, we claim that an effective marking should be able to (i) alter graph representations suf- ficiently; (ii) induce perturbations that correlate with graph targets. Ideally, when marking nodes jointly optimizes (i) and (ii), a Subgraph GNN with small bag can then improve on a standard MPNN by sufficiently separating more graphs and in a way that assists the training objective.
High-centrality marking induces the largest perturba- tions. As a first experiment, we examine the extent to which node centralities recapitulate the amount of perturbation induced by marking their corresponding nodes. We con- sider the same setting discussed above: marking one node to transition from G to S,, where S, is obtained from G by marking node v. For a centrality measure c, we consider three cases: e attains the minimum of e (i), the maximum of (ii), is randomly picked (iii). In each of these cases, we measured the distance (S.) - (GG) on 100 graphs from two different real-world datasets from the popular TU suite: MUTAG and NCI1 (Morris et al., 2020a). Here, f is an untrained 3-layer GIN (Xu et al., 2018). Figure I and Figure 7a show results for the -eelazuue,, 2005), where
Node Marking, perturbations, and centrality measures. To understand how marking node alters graphs represen- tations, we analyze the simplest case: marking single node. In particular, we ask how much the representation of a generic graph G can be changed by single-node marking. As the MPNN, we consider an L-layer GIN (Xu et al., 2018; Chuang & Jegelka, 2022):
-
1 (hg ((-1)+
Σ h 1) yG -G= uEN(2)
Σ ))
BEG
(2)
where "s''ss are update functions and (b(++)) is a predic- tion layer (all are parameterized as MIPs). By applying results from GNN stability studies in (Chuang & Jegelka, 2022) we put forward the following observation (see details in Appendix E):
Subgraph
Centrality (Estrada & horizontal lines indicate the average representation distance, and (i), (ii), (iii) are color-coded, resp., in green, blue, red.
From the plots, it is clearly visible how marking nodes with the lowest centrality leads to the smallest change in graph representation. This result gives direct empirical val- idation to the upper-bound analysis and the consequential observation discussed above. In accordance with our claim, subgraphs associated with low centrality nodes can be in- terpreted as poor marking candidates. Second, we note that marking nodes with the highest centrality induces the highest average perturbations, above random marking. This result is particularly relevant as it complements the above theoretical analysis: the walk-based upper-bound bound (Equa- tion (3) only suggests, but does not necessarily entail, that high-centrality marking associates with the largest pertur- bations. Figure and Figure 7a show that this occurs in practice these datasets, further motivating our proposed sampling strategy. Results for other centrality measures are found in Appendix F; they indicate that high-centrality mark- ing leads, in all cases, to larger perturbations than random marking, with the highest values attained by walk-based centrality measures (see Section 2).
Observation 1. The distance between the MPNN represen- tations of graph G and graph S,, generated by marking node in G, can be apper-boundee as:
L-1
L+1 A
1gG - ys. S
II 1=1
Yos
(3)
(A)
where K! is the Lipschitz constant of MLP s0,11 = 1... L + 1, A is the adjacency matrix of graph G and A E IR+ is an c-dependent layer-wise weighting scheme.
Effectively, the cumulative number (A) of walks starting from node v contributes to upper-bound the perturbation that marking induces on the original graph representation. Hence, marking nodes involved in a lower number of walks will have a more limited influence on altering a message passing-based graph representation.
We note that the above observation uncovers an intriguing alignment with bask- centrality measures: the "most important" nodes associate with the largest (discounted) cumulative numbers of walks (compare Equations with
High-centrality marking aligns with substructure count- ing. We have shown how marking nodes with higher cen-
4

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Balk-Based Centrality
trality can lead larger graph perturbations. However, this may not be sufficient. As an example, consider, two (non- isomorphic but) 1-WL-equivalent graphs. Node marking can alter their message- message-passing-- passing-basse -baed representations, but not necessarily in a way to induce separation: ideally, if the two graphs are associated with different targets we aim to induce dissimilar perturbations so to assist the training goal. In effect, we want our sampling strategy to alter the graph representations in a way that is consistent with the target space. Motivated by the observation that the pres- ence and number of structural "motifs" are often related to graph-level tasks (Kanatsoulis & Ribeiro, 2024), we empir- ically study how marking-inet induced perturbations correlate with counting small substructures, as general, yet relevant, predictor for graph-level targets.
MUTAG
[MPNN(S.) MPNN((G
X0X
Contralitt
20
bi
80
100
Graph
Figure I: Plot showing the amount the graph representation using GIN is altered in the MUTAG dataset by adding an additional node-marked subgraph with (i) the highest centrality, (ii) the lowest centrality and (iii) random marking.
We randomly generate 100 Erdös- Rendsi (ER) graphs, each with N 20 nodes and wiring probability p = 0.3. Simi- larly as above, we experiment with various centrality mea- sures, by marking single node e which attains either the maximum or minimum centrality value, or is randomly picked. Again, we record the perturbation (S.) - [()] given by the same architecture described above. On the same graphs, we count the number of various substructures, and evaluate the correlation between this value and the recorded perturbations. Results are reported in Table I, expressed in terms of the Pearson correlation coefficient. Higher coeffi- cients indicate substructure counts are better recapitulated by the perturbations induced by a certain marking strategy.
Table 1: Pearson correlation between substructure counts and perturbation caused by different more-marking policies.
Method
Tri (1)
4-Cyc
Tailed Tri (f)
Star (?)
Max. Subgraph Centrality
0.947
0.956
0,958
0.972
Min Subgraph Centrality Random
0.644
0.643
0.634
0.698
0.712
0.708
0.723
0.723
Max Degree Centrality Max Closeness Centrality
0.937
0.947
0,948
0.962
0.935
0.937
0,946
0.957
Max Retweenness Centrality
0.803
0.816
0.845
ical performance. More sophisticated sampling schemes could be designed based on extensions of the above analy- ses. These could consider more complex Subgraph GNN architectures (Frasca et al., 2022; Zhang et al., 2023a) or study the effect of multiple node markings, for which a deeper inquiry could take into account wise scores be- yond node-wise centrality measures?. We defer these efforts to future work.
The top section of the table compares the correlations ob- tained by marking randomly or based on the Subgraph Centrality. The perturbations induced by high-centrality marking correlate significantly more with the considered substructures than those induced by www--eetrallty-baeee or random marking. The bottom section of the table presents results for other centralities not based on walks. We note how they all deliver better correlations w.r.t. random mark- ing, but not high those attained by the SC.
4. Combining Subgraph GNNs with SEs
4.1. Our Approach
Discussion. Overall our experiments indicate the following- First, high-centrality sampling shows to be better approach than random sampling, especially when walk-based central- ity measures are employed: on average, it selects marking candidates inducing the largest amount of perturbations over the original graph representations, and way that corre- lates with counts of relevant graph substructures. Second, the walk- walk-based SC stands out as a particularly promising candidate: it is efficient to precalculate this measure and sample subgraphs based on that, while, on average, it per- formed as the best one in the experiments discussed above. In the following, we will focus on this measure in particular. Our strategy will consist of marking only the top-ranking k nodes according to SC, for a small, fixed k. As we will show, this simple approach already delivers strong empir-
Subgraph Centrality as a SE. In Section 3, we introduced the use of walk-based centrality measures, particularly Sub- graph Centrality, as an efficient and effective method for subgraph sampling. These centrality measures can be ex- pressed as power series expansions of the adjacency ma- trix (Benzi & Klymko, 2014) (see Equation (1)). We notice that addenda terms in the series already provide precious discriminative structural information, which could be desir- able to employ for feature augmentations (Rampäšek et al., 2022; Bouritsas et al., 2022; Dwivedi et al., 2021). Precisely, in the case of our chosen Subgraph Centrality, for the de- fault 1, the k-th term (Λ*)ae is (the discounted number of) k-length walked- originating from As notable
k!
FFor example, when selecting multiple nodes to mark one could also account for the distance hetween them.
5

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Basse Based Centrality
10. 0.5, 0.0
1.5
10,15,
2.8
1.0
2.3
2.0,
3.3
10. 0.5 0.0
1.5
1.0 0.5, 0.0
1.5
Centrality Encading
Subgraph Centrality
Figure 2: An overview of the pipeline for HyMN. We calculate the CSE for each node, sample T mode-marked subgraphs with the highest Subgraph Centrality and concatenate the CSE with the initial node features.
examples, these values are proportional to the degree of v and the number of incident triangles for 2, These considerations suggest retaining the intermediate values that contribute to the SC of each node, and employ them à la Structural Encodings beyond sampling purposes.
this point, it is natural to ask whether this combination of techniques is justified from an expressiveness perspective. Put differently, we ask whether enhancing message passing with CSEs already subsumes our high-centrality marking strategy or, vice-versa, whether our marking approach could recover CSEs.
We naturally define the Centrality-basee Structural Encod- ings (CSE) of order K for node v :
We answer these questions with graph separation argu- ments (Xu et al., 2018; Morris et al., 2019) and highlight how, in fact, the two approaches are not generally compara- ble. We demonstrate that subsampling Subgraph GNNs with high-centrality marking does not subsume CSE-enhanced MPNNs. while, at the same time, the discriminative power of the former approach is not fully captured by the latter. Since neither technique alone fully subsumes the other, our analysis emphasizes the advantages of combining them in HyMN for improved expressiveness. Proofs and additional details are reported in Appendix D)
(A) ve
(A)
(A)
(A)
CCSE = 1, 11
(4)
2!
3!
KT
As K -> 0c, the sum of these terms clearly coincides with the SC of the node for the default 8 = 1. We refer readers
to Appendix F.5, for considerations on how CSEs compare with RWSEs.
Hybrid Marking Networks. Our overall method consists in jointly (I) augmenting node features with K Korrder CSEs; (2) subsampling the T marked subgraphs for the nodes attaining the highest centrality values; (3) processing the obtained bag of subgraphs with a Subgraph GNN of choice.
MPNNs with centrality encoding do not subsume sub- sampled Subgraph GNNs. Below, we show that node- marked subgraphs can separate graphs indistinguishable by CSE-enhanced MPNNs, i.c. MPNNs running on graphs whose features are augmented with our centrality- -ased encodings.
In view of (1) and (2), we dub our approach HyMN, as in Hybrid Marking Network. These steps are depicted in Fig- ure 2 and described Algorithm (Appendix C). We note the following. First, for large enough K, centrality val- ues can be approximated by directly summing over the computed K -odder CSEs. Second, node marking does not require any alteration of the original graph topology, making unnecessary to store the subgraph connectivity. We thus opt not to materialize the bag of subgraphs: we only record marking information in the feature tensor and implement custom cessage-function that processes it in equivariant way. From an engineering standpoint, this allows for further memory-complexity enhancement w.r.t. generic Subgraph GNN approaches.
Theorem 4.1. There exists a pair of graphs G and G' such that for any CSE-enhanced MPNN model McsE we have McsE(G) = McsE((") but there exists DS -ubgraaaa GNN model (without CSEs) Mad, which uses top-1 Sub- graph Centrality policy such that Mab. (G) F M (G').
This result is proved, in particular, by considering two 1- WL equivalent graphs which have identical values for CSEs. This makes them indistinguishable by a CSE-enhanced MPNN, contrary to (sampled) DS- DS-Subgraph GNNs (Bevilac- qua et al., 2021), 1), the simplest Subgraph GNN variants which process subgraphs independently. This underscores the ad- vantage of incorporating mode-marking Subgraph GNN alongside structural encoding techniques.
4.2. Expressivity of Subgraph GNNs with CSEs
HyMN effectively marries two distinct Graph Learning ap- proaches: the use of node-marked subgraphs and of SEs. At
Subsampled Subgraph GNNs do not subsume MPNNs with centrality encoding. Processing only a fixed num- ber of subgraphs selected by our high-centrality strategy may limit discriminative power. In particular, the following
We defined CSEs directly the addenda in the power-series in Equation (1), but note that the first terms are dis- criminative and could be dropped.
6

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
Trianglos
Table Results on OGB datasets (Test ROC-AUC). The first
and second best results for each task are color-coded Symbol indicates the method is not (found to have been) benchmarked on the specific dataset.
0.7-
Randomn
Closeness Centrality
Betweeress Centrality
0.5
Degree Centrality
Test
0.4
Subgraph Centrality
Pagerank Centrality
Method
MOLHIV
MOLBACE
MOLTON2I
0.3
GCN
76.06 1:0.97
79.15 4-1.544-1.44
75.29 1:0.8
0.2
GIN
75.58 11.40
::400
74,91 10.51
FULL
76.54
78.41 #1.94
76.25 #1.12
0.0
OSAN (T= 10)
76,30 1:3.00
10
20 30
40
50
Bag Size
Subsompted Subynyt GNNS
MAG-GINN (T
77.12 +1118
RANDOM
77.55 1::24
75:36 1:4.88
76.65 0:0.9
Figure 3: Comparing sampling approaches for counting triangles (performance metric is Mean Absolute Error, the lower the better). The average graph size 59.33, corresponding to the average bag-size of a full-bag Subgraph GNN.
CS-GNN (2)
77.72
1:0.76
1:.00
POLICY-LEARN ()=
79.13
4-0. 60
78.40
4-2.0
77.47
+0.82
HyMN (GIN, T-2) no CSE
79.77 4-0.70
78.22 4 4-4.02
77.68
1:0.72 71
HyMN (GIN, T=2)
81.01
1:111
81.16 1:1:21
77.30 1.035
RANDDM (I=5)
77.30 +-2.6
78.14 4:2.36
76.02 +0.89
CS-GNN (T' (5)=5)
79.09 1:0.90
79.64 4:1.43
POLICYLEARN (T-5)
78.49 +1.01
78.39 4:2.28
77.36 +0.60
HyMN (GIN, T T-5) no CSE
79.62
4-1.4
78.57 4:1.31
77,82 5.0.9
ByMN (GIN, T-5)
80.17
1..40
80.64 4:0.48
76.99 #0.45
shows that this approach does not subsume CSE-enhanced MPNNs:
ability of model to count local substructures is an acknowl- edged way of evaluating its expressive power (Bouritsas et al., 2022; Arvind et al., 2020; Tahmasebi et al., 2020), In order to answer (Q1) and test the efficacy of subgraph sampling with node centrality, we explored the ability of a Subgraph GNN to (learn to) count different small sub- structures as we increase the number of subgraphs in our bag. We closely followed the experimental procedure of (Chen et al., 2020), but modified the data generation process to render the task more challenging and informative". We compared the performance of sampling subgraphs based on different approaches: random sampling and sampling based on the highest values of different centrality measures. No CSEs are employed in this setting. We remark that this experiment is intrinsically different than what explored in Section 3.2. There, we studied the correlation between subgraph counts and marking-inducee perturbations on un- trained models; here, we train models to regress these val- ues (potentially making use of the additionally provided marking information). Figure 3 reports results for triangle counting, expressed in terms of Test Mean Absolute Error (MAE). These results demonstrate the significant improve- ment afforded by high-centrality sampling over random sampling with fewer subgraphs (Q1). Additionally, it shows that SC-based sampling generally outperformed other cen- trality measures, demonstrating the benefits of focusing on bask- centralities, in alignment with our analysis in Section 3. The full set of results for additional substructures is reported in Appendix F.
Theorem 4.2. There exists a pair of graphs G and G' such that for any Subgraph GNN model Mab. which uses a top-1 Subgraph Centrality policy we have Mass (G) = mub. (G'), but there exists an MPNN + centrality encoding model MEsE such that McSE(G) (G) * Mcse(G").
This result exposes a limitation of subsampled Subgraph GNNs in distinguishing between two non-isomorphic graphs with differing closed walks, features which are, in- stead, captured by CSEs. Notably, as discussed in Propo- sition D.5 (Appendix D), a full-bag approach is capable of capturing CSEs. This observation suggests that while CSEs do not universally enhance the expressiveness of any Subgraph GNN, they can be beneficial when subsampling a limited number of subgraphs.
Taken together, Theorems 4.1 and 4.2 indicate that leverag- ing SC both as SE and as means for subgraph sampling is advantageous in terms of discriminative power, justifying the integration of the two techniques in HyMN.
5. Experiments
Our experiments' aim to validate arguments in the previous sections and to empirically answer the following questions:
(Q1) Can SC be used to effectively subsample sub- graphs for Subgraph GNNs?
(Q2) Can HyMN efficiently scale to graphs out of reach for Subgraph GNNs? How does it perform thereon?
OGB. We tested HyMN on several datasets for graph prop- erty prediction from the OGB benchmark (Hu et al., 2020b). We focus, in particular, on molecular graphs, tasked to pre- dict global properties such as their toxicity or their ability
(Q3) How does HyMN perform on real-world datasets w.E.t. strong GNN baselines?
(Q4) What is the impact of incorporating CSEs?
Synthetic experiment for counting substructures. The
$In particular, we considered larger graphs with a similar num- ber of nodes to correct an undesired correlation between the graph size and the task targets observed in the original data (see Ap- pendix G.2).
*Code reproduce experimental results is available at https: / //gi thub. commoo//// jks 1 7/HYMN/.
7

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
Mothod
Precomp.co
Train (slped))
Tost
Popt.-Func
PopteStrrct
Method
Train pigelto
Test so
MaiNer- T. m
GIN
0.00 20.00
2.65 20.01
0,238 2000
0.6555
an ixes
0,2497
200012
GIN
7.16 :0.04
0.70 29.25
91.10 10.35
GIN- CSE
20.50
20.01
0.253
20:00
0,6619
20.0077
0.2479
20.0011
MYMN (GIN. I=1)
23.71 50.34
4.93 so.0
0.420
0.6857
$0.00ss
0.2464
10.0013
MyMN (T=1) car
8.79 g0ot
20.01
92.84 10.52
My (GIN, T=2)
23.75 20.32
6.60 20.r
0,561
0. 6863
ast 2000
0.2457
2000322
HyMN (T=I)
9.31 =0.2
1.02 40.01
92.54 10.75
HyMN (T=2) mo
11.71 20:77
1.38 am.0
92. 18 20.84
GCN
0.00 10.00
2.07 80.04
0,234 n0.005
0.6739
20.0024
0,2505
10.0023
MyMN (T=2)
11.97 20.0
20.00
92.44 10.as
GCN+ CSE
20.19 50.36
2.16 20.04
0.254 20.003
0.6812 20000077
0.2499
20.0030
HyMN (GCN, T=1)
23.88 50
2.94 20:0
0.292
20000
0.6912
20.0120
0,2488
20 0010
GPS (Perf.
59,34 20.2
6.43 20.00
92.14 20:24
My (GCN, T-2)
23.97 20.30
3.83 g0.0t
0.368
56.002
0.69488
g0.0002
0,2477
20.0000
GPS (BigBind)
112.63 20
17.65
20.r6
91.02 10.15
GPS (Transt.)*
162.10 61.37
14.97 10.04
90.85 10.46
GPS
20.87 g0 48
8.39 10
0.611
20:005
0,6535
gr noos
0,2500
10 0006
Gruph VIT
29.12
6.78 20.01
0.709
0.6942
0.2449
20.0046
G-MLP-Mixer
29.52 50.00
6.87 s0.0
0.684 =0.003
0.6921
20.0054
0,2475
20.0015
Table 4: Results and timing comparisons using a GeForce RTX 2080 8 GB for the MalNet-Tiny dataset. The model marked with did not fit in memory with batch size 16, and was trained with batch size 4. Both HyMN and GPS employ a GIN backbone.
Table 3: Results on Peptides datasets with timing comparisons on Peptides-Funee using a NVIDIA GeForce RTX 3080 10GB. Test AP is quoted for Peptides-Func and Test MAE for Peptides-Struce Struct.
to inhibit HIV replication. To further examine (Q1), Ta- ble 2 shows the performance of our approach in relation to MPNNs, a full-hag Subgraph GNN and other subgraph sam- pling policies with the same number of subgraphs. Notably, even without using the centrality-based encoding (HyMN w/out CSE), method matches the performance of a learn- able sampling policy (POLICYLLEARN (Bevilacqua et al., 2024)) and consistently outperform MPNNs and random sampling policies. Additionally, we observe that augment- ing node features with CSEs can significantly increase per- formance on MOLHIV and MOLBACE, outperforming a full-bag Subgraph GNN (Q4). These results suggest that centrality sampling is effective and that additionally incor- porating centrality information can lead to performance improvements on real-world datasets, aligning with our find- ings in Section 3. We last highlight the exceptional result HyMN obtains, with = 2, on the MOLHIV benchmark (81.01 + 1.17). This model outperforms strong GNN base- lines, as reported in Appendix F.2, Table 8 (Q3). Run-time comparisons for this dataset are additionally enclosed in Appendix H.
call graphs with up to 5,000 nodes (Freitas et al., 2021). Models are asked to predict their malware class, or identify them as benign otherwise. As well as being from a signifi- cantly different domain, these graphs are considerably larger than the graph benchmarks considered above, allowing us to showcase HyMN's ability to scale to even larger graphs (Q2). We compare to the GPS architecture (Rampášek et al., 2022), instantiated with various (sparse) variations of its Graph Transformer component and a GIN message-passing backbone, the same we employ for HyMN. The results are shown in Table 4. Whilst, full-bag Subgraph Graph Neural Networks cannot scale to this dataset, our method, HyMN, is able to outperform sparse Transformer- approaches at a fraction of the runtime: our approach is, almost six times faster than the best GPS variant both in training and inference.
Reddit. To further showcase the ability of HyMN to scale to large graphs and to evaluate the effectiveness of the method with different data modality, we experimented with the REDDIT-BINARY (RDT-B) dataset (Morris et al., 2020a). The task involves the classification of social networks that have a high average number of nodes (429), so full-bag ap- proaches cannot be applied. We compare our approach with learnable sampling policy (POLICY-LEARY (Bevilacqua et al., 2024)) and to two expressive higher order GNNs (SIN and CIN) (Bodnar et al., 2021a;b). HyMN exhibits on-par performance with the best pest-performing method (5) which is learnable policy, highlighting the effectiveness of our sampling approach.
Peptides. In order to evaluate the ability of HyMN to scale to larger graphs (Q2), we experimented on the Peptides datasets from the LRGB benchmark (Dwivedi et al., 2022), where the task is to predict global structural and functional properties of peptides, represented as graphs. The average number of nodes in these graphs is 150.94, so it is difficult for full-bag Subgraph GNN to process. Additionally, using the centrality encoding to sample just one or two additional subgraphs can improve performance on both datasets. We also outperform GPS (Rampášek et al., 2022) (a Graph Transformer) and match the performance of Graph- MLP-Mixer (He et al., 2023) (Q3). Our timing experiments on Peptides-Func demonstrate that are significantly more efficient than both of these approaches, only increasing the training time per epoch over a GCN by 42% and the inference time by 25% using 'HyMN (GCN, T=1)' (Q2).
Summary. In reference to the questions enlisted above, we conclude the following. (A1) The results from sub- structure counting and on the OGB benchmarks suggest a positive answer Q1: SC-based sampling significantly out- performed random sampling on both, and matched the per- formance of the learnable POLICY-LEARN. (A2) HyMN was effortlessly applied to the larger Peptides and MalNet datasets, with strong empirical performance and extremely lightweight inference and training run-times. This demon-
MaINet-Tiny- This is a code dataset consisting of function
8

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table Results on RDT-B (Accuracy).
populated bag. More sophisticated selection strategies could combine different walk-based centrality measures con- sider pairwise structural features.
Method
RDT-B
GIN
92.4 22.5
SIN CIN
92.2 1:10
92.4 12
FULL
0OM
RANDOM (T=20)
RANDOM (T=2)
92.4 =1.0
POLICY-LEARN (T=2)
93.0 #0.9
HyMN (T=2)
93.2 22.2
strates that effective subgraph sampling unlocks the appli- cability of Subgraph GNNs to larger graphs, even orders of magnitude larger than those full-bag methods could possibly be applied to. (A3) Beyond these two datasets, HyMN also attained remarkable performance on OGB benchmarks, and performed competitively on ZINC (see Appendix F.2). This suggests positive answer to Q3. (A4) We observe that CSEs can enhance the performance of standard MPNNS (see Table 3) and subsampled Subgraph GNNs (see. e.g.. MOLHIV and MOLBACE in Table 2). We note, however, they were not always beneficial (see MOLTOX21 Table 2 and MalNet Table 4).
6. Conclusions
We introduced novel Subgraph GNN method, termed HyMN, which strikes compelling balance between ef- ficiency and expressiveness by combining a subgraph sam- pling strategy and structural encodings both derived from walk-based centrality measures. HyMN attains strong em- pirical performance with an extremely thin computational overhead, making it applicable stream tasks featuring large graphs, tens or hundreds of times larger than those full-bag Subgraph GNNs can pos- sibly process. In our paper, we showed, in particular, that the Subgraph Centrality by Estrada & Rodriguez- Rodriguez-Velazquez (2005) is a good measure of subgraph importance: for a very limited number of subgraphs it enables competitive performance and outperforms random and learnable selec- tion strategies. We also proved that the additional inclu- sion of -entrality-based SEs is beneficial both theoretically and in practice, allowing to enhance discriminative power and downstream generalization performance on several real- world benchmarks.
wide spectrum of down-
Limitations and future work. Our sampling procedure does not take into account already sampled subgraphs unlike methods such the ones in (Zhao et al., 2022; Bevilacqua et al., 2024). Future work could focus more general per- turbation analyses to give an indication on multi-node mark- ing for higher-order selection policies (Qian et al., 2022) or to quantify (i) the optimality of the designed sampling strategy, (ii) the impact of adding subgraphs to partially

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
Acknowledgments
centrality measure. Journal of Complex Networks, 1(2): 124-149, 2013.
The authors would like to thank Giorgos Bouritsas for in- sightful early-stage discussions and Moshe Eliasof for late stage experimental insights on PolicyLearn. J.S. sup- ported by the UKRI CDT in Al for Healthcare http:// a mi4healthh 1o (EP/S023283/1), Y.E. is supported by the Zeff PhD Fellowship: G.B.S. by the Jacobs Qualcomm PhD Fellowship. M.B. is supported by EPSRC Turing AI World- Leading Research Fellowship No. EP/X040062/1 and EP- SRC Al Hub on Mathematical Foundations of Intelligence: An "Erlangen Programme" for AI No. EP/Y028872/1, H.M. is Robert J. Shillman Fellow and is supported by the Israel Science Foundation through personal grant (ISF 264/23) and an equipment grant (ISF 532/23). F.F. con- ducted this work supported by an Andrew and Erna Finci Viterbi and, partly, by an Aly Kaufman lowship. F.F. partly performed this work while visiting the Machine Learning Research Unit TU Wien led by Prof. Thomas Gärtner.
Benzi, M. and Klymko, matrix analysis of different centrality measures. arXiv preprint arXiv:1312.6722. 2014.
Bevilacqua, B., Frasca, F. Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In Interna- tional Conference Learning Representations, 2021.
Bevilacqua, B., Eliasof, M., Meirom, E.,, Ribeiro, B., and Maron, H. Efficient subgraph gnns by learning effective selection policies. In The Twelsth International Confer- ence Learning Representations, 2024.
Fel-
Biewald, L. al. Experiment tracking with weights and biases, 2020.
Bodnar, C.,, Frasca, F., Otter, N., Wang, Y., Lio, P., Montu- far, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34:2625-2640, 2021a.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bodnar, C.,, Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lio, P., and Bronstein, M. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026- 1037. PMLR, 2021b.
References
Bouritsas, G., Frasca, F., Zafeiriou, S. P., and Bronstein, M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Abboud, R., Ceylan, i. i., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with ran- dom node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence (ICCAI), 2021.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv: 2017.
Arvind, V. Fuhlbrück. F., Köbler, J., and Verbitsky, O. On Weisfeiler- Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-55 59, 2020.
Brouwer, A. E. and Spence, E. Cospectral graphs on 12 vertices. the electronic journal of combinatorics, pp. N20- N20, 2009.
Chen, Z., Chen, L., Villar, S., and Bruna, J. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383- 10395, 2020.
Bar-Shalom, G., Bevilacqua, B., and Maron, H. Sub- graphormer: Unifying subgraph gnns and graph trans- formers via graph products. In Forty-first International Conference Machine Learning, 2024a.
Chuang, C.-Y. and Jegelka, S. Tree mover's distance: Bridg- ing graph metrics and stability graph neural networks. Advances Neural Information Processing Systems, 35: 2944-2957, 2022.
Bar-Shalom, G., Eitan, Y., Frasca, F,, and Maron, H. A flcxible, cquivariant framework for subgraph gnns via graph products and graph coarsening. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J.. and Zhang, C. (eds.), Advances in Neural Informa- tion Processing Systems, volume 37, pp. 101 1168-101222. Curran Associates, Inc., 2024b.
Cotta, L., Morris, C., and Ribeiro, B. Reconstruction for powerful graph representations. Advances in Neural In- formation Processing Systems, 34:1713-1726 2021.
Cybenko, G. Approximation by superpositions of a sig- moidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Benzi, M. and Klymko, C. Total communicability as
10

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Dupty, M. H. and Lee, W. Graph representation learning with individualization and refinement. arXiv preprint arXiv:2203.08 09141, 2022.
Gómez-Bombarelli, R., Wei, J. N., Duvenaud, D., Hermández-Lobato, M., Sánchez-Lengeling B., She- berla, D., agquilera-parraguuire J., Hirzel, T. D., Adams, R. P., and Aspuru-Guzik, A. Automatic chemical de- sign using a data-driven continuous representation of molecules. ACS central science, 4(2):268-2) 276, 2018.
Dwivedi, V. P. and Bresson, X. A generalization of trans- former networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Gori, M., Monfardini, G., and Scarselli, F. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pp. 729-734 vol. 2, 2005, doi: 10.1109/ JJCNN.200..555942
Dwivedi, V. P. Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations, 2021.
Dwivedi, V. P., Rampášek, L.,, Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- tems, 35:22326-22344 2022.
Hagberg, A., Swart, P. J., and Schult, D. A. Exploring network structure, dynamics, and function using net- workx. Technical report, Los Alamos National Labo- ratory (LANL), Los Alamos, NM (United States), 2008.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning, pp. 12724-12745. PMLR, 2023.
Estrada, E. and Velazquz,,, J. A. Subgraph cen- trality in complex networks. Physical Review E, 71(5): 056103, 2005.
Homik,, K. Approximation capabilities of multilayer feed- forward networks. Neural networks, 4(2):251-257, 1991.
Hu, S., Xiong, Z., Qu, M., Yuan, X., Côté, M.-A., Liu, Z., and Tang, J. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 33: 13110-4000185, 2020a.
Fesser, L., and Weber, M. Effective structural encodings via local curvature profiles. In The Twelfth International Conference on Learning Representations, 2024.
Fey, M. and Lenssen, J. E. Fast graph representation learn- ing with pytorch geometric. ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds, 2019.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 11222118-22113 2020b.
Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H. Understanding and extending subgraph gnns by rethink- ing their symmetries. Advances in Neural Information Processing Systems, 35:31376-31390, 2022.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre- pre-training graph neu- ral networks. In International Conference on Learning Representations, 2020c.
Freeman, L. C. A set of measures of centrality based betweenness. Sociometry, pp. 35-41, 1977.
Huang. Y., Peng, X., Ma, J., and Zhang, M. Boosting the cycle counting power of graph neural networks with P2-nnss In The Eleventh International Conference on Learning Representations, 2023.
Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. In Vanschoren, and Yeung, S. (eds.), Proceedings of the Neural Infor- mation Processing Systems Track on Datasets and Bench- marks, volume 1, 2021.
Kanatsoulis, C. and Ribeiro, A. Counting graph substruc- tures with graph neural networks. In The Twelfth Interna- tional Conference Learning Representations, 2024.
Geerts, and Reutter, L. Expressiveness and approxima- tion properties of graph neural networks. In International Conference on Learning Representations, 2023.
Katz, L. A new status index derived from sociometric anal- ysis. Psychometrika, 18(1):39 -..99443,, 1953.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Kipf, T. N. and Welling, M. suprrvupe classifica- tion with graph convolutional networks. International Conference on Learning Representations, 2017.

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Kong, L.,, Feng, J., Liu, H., Tao, D., Chen, Y., and Zhang, M. Mag-gnn: Reinforcement learning boosted graph neural network. Advances in Neural Information Processing Systems, 36, 2024.
leman go machine learning: The story far. The Jour- nal of Machine Learning Research, 24(1):15865-15223 2023.
Papp. P. A. and Wattenhofer, R. A theoretical comparison of graph neural network extensions. In International Con- ference on Machine Learning, pp- 17323-17345 PMLR, 2022.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618 21629, 2021.
Papp, P. A.. Martinkus, K., Faber, L., and Wattenhofer, R. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances Neural Informa- tion Processing Systems, 34:21997-22009, 2021.
Li, P., Wang, Y., Wang, H., and Leskovee, Distance en- coding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 44788 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Lim, D., Robinson, J. D., Zhao, L.,, Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference on Learning Representations, 2023.
Lim, D., Robinson, J., Jegelka, S., and Maron, H. Expressive sign equivariant networks for spectral geometric learning. Advances in Neural Information Processing Systems, 36, 2024.
Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris, C. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems, 35:21030- 21045, 2022.
Loshchilov, and Hutter, F. Decoupled weight decay reg- ularization. In International Conference Learning Representations, 2019.
Rampášek, L.., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. Advances Neural Information Processing Systems, 35:14501-145155 2022.
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. Invariant and equivariant graph networks. In International Conference Learning Representations, 2018
Read, R. C. and Wilson, R. J. An atlas of graphs. Oxford University Press, 1998.
Micheli, A. Neural network for graphs: A contextual con- structive approach. IEEE Transactions on Neural Net- works, 20(3):498-51) 511, 2009. doi: 10.1 10.1109/TNN.AA 2008. 2010350.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333 331..1. SIAM, 2021.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. Pro- ceedings of the AAAI conference on artificial intelligence, 2019.
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-98) 2009. doi: 10. 1..109///NN.200820555555
volume 33, pp.
Sterling, T. and Irwin, J. J. Zinc 15-ligand discovery for everyone. Journal of chemical information and modeling, 55(11):2324-233
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: collection of bench- mark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a.
Sun, Q., Li. J., Peng. H., Wu, J., Ning, Y., Yu, P. S., and He, L. Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mecha- nism. In Proceedings of the web conference 2021, pp. 2081-2091, 2021.
Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and le- man go sparse: Towards scalable higher-order graph em- beddings. Advances in Neural Information Processing Systems, 13:21824-21844 2020b.
Tahmasebi, B., Lim, D., and Jegelka, S. Counting substruc- tures with higher-order graph neural networks: Possibility and impossibility results. arXiv:20/2.03/74 2020.
Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and
12

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. In The Second Learning Graphs Confer- ence, 2023.
Vignac, C., Loukas, A., and Frossard, Building power- ful and equivariant graph neural networks with structural gressage-passing Advances in neural information pro- cessing systems, 13:14143-1415555 2020.
Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neu- ral networks. In International Conference Learning Representations, 2022.
Weisfeiler, B. and Leman, A. The reduction of graph canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? In International Conference on Learning Reprexentations, 2018.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888 2021.
You, J., Gomes-Selman, J. M., Ying, R., and Leskovec, J. Identity-aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10737-10745, 2021.
Yun, C., Sra, S., and Jadbabaie, A. Small relu networks are powerful memorizers: tight analysis of memorization capacity. Advances Neural Information Processing Systems, 32, 2019.
Zhang, B., Feng, G., Du, Y., He, D., and Wang. L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisaeiler-lehman tests. In International Con- ference on Machine Learning, pp. 41019-41077. PMLR, 2023a.
Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the expressive power of gnns via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023b.
Zhang, M. and Li, P. Nested graph neural networks. Ad- vances in Neural Information Processing Systems, 34: 15734-15747, 2021.
Zhao. L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure aware- ness. International Conference on Learning Represen- tations. 2022.
13

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
A. Outline of the Appendix Corpus
The appendix corpus is structured as follows:
Appendix B: we include an extended background section on Subgraph GNNs, their computational complexity and bag sampling approaches to scale these architectures. This section intended to be complementary Section 2, as provides additional context to readers not necessarily familiar with Subgraph GNNs and complexity limitations;
Appendix C: we report a full algorithmic description of our HyMN approach:
Appendix D: we report proofs pertaining to Section 4;
Appendix E: we provide derivations and additional details on the perturbation analysis of Section 3;
we report and discuss further, additional experiments we additionally run HyMN the ZINC dataset, we explore more backbone MPNN architectures, we compare Subgraph Centrality with other centrality measures and with RWSEs, and we further examine the impact of including CSEs in our model, alongside marking;
Appendix F:
Appendix G: we comprehensively describe experimental settings and details, architectural choices and hyper- parameters;
Appendix H: we enclose additional timing comparisons.
B. More on Subgraph GNNs and their Complexity
B.1. The Architectural Family of Subgraph GNNS
The term "Subgraph GNN" refers to broad family of recent Graph Neural Networks sharing a common architectural pattern: that of modeling graphs as sets (bags) of subgraphs. Subgraphs are processed by a backbone GNN, possibly flanked by additional information sharing modules (Bevilacqua et al., 2021). Bags of subgraphs are formed by selection policies, which typically extract subgraphs by applying topological perturbations such as node- (Cotta al., 2021; Papp et al., 2021) or edge-deletions (Bevilacqua et al., 2021), or by marking nodes (You al., 2021; Papp & Wattenhofer, 2022).
In formulac, Subgraph GNN can be deseribed as (Frasca et al., 2022):
G ppopo x)
(5)
where и is the selection policy; S applies the backbone GNN with, potentially, information sharing components; p are pooling and prediction modules.
Various choices for the above terms give rise to different Subgraph GNN variants (Frasca et al., 2022). For non-trivial selection policies and sufficiently expressive backbones, these exceed 1-WL discriminative power (Bevilacqua et al., 2021), thus surpassing standard peessag--passing networks.
The most popular selection policies are node-based: selected subgraphs are in a bijection with nodes in the original input graph. Prominent policies in this class include node-deletion, ego-networks and node-marking. From expressiveness perspective, mode-marking subsumes the first two policies (Papp & Wattenhofer, 2022; Zhang al., 2023a), other than uncovering a connection between node-based Subgraph GNNs and node-individualiiztion algorithms for graph isomorphism testing (Dupty & Lee, 2022). Node-mant marking constructs bags of subgraphs as:
TNM G (A, - (e), (A, X 2 en)),
(6)
where e; E 1 is i-th element of the canonical basis and @ denotes concatenation across the channel dimension.
Node-based Subgraph GNNs encompass several architectures, including ID-GNNs (You et al., 2021), (n - 1)) Re--ossttttutiinn GNNs (Cotta et al., 2021), Nested GNNs (Zhang & Li, 2021), GNN-AK (Zhao et al., 2022), SUN (Frasca et al., 2022) and the maximally expressive GNN-SSW (Zhang et al., 2023a). For 1-WL-expressive backbones, Subgraph GNNs with node-based policies are bounded in their expressive power by 3-WL. (Frasca et al., 2022). Detailed, structured charting of their design space, along with fine-grained expressiveness results, are found in (Frasca al., 2022; Zhang al., 2023a).
"Elements vector e; are 0 except for the one position i, which equals 1.
14

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
selection policy (node marking)
msg-passing
full bag of subgraphs
sampling strategy
(T=1)
Figure 4: Depiction a Subgraph GNN endowed with a subgraph sampling strategy.
B.2. Computational Complexity Aspects
Consider Subgraph GNN f in the form of Equation (5), where stacks neural message- message-passing layers. For an input graph G with nodes and degree bounded by dmax. f exhibits an asymptotic forward-pass, complexity:
msg pass complexity
T(n, dmax: m) = (m
dmax
)
with m being the number of subgraphs generated by policy æ executed on graph G.
Node-based policies are such that the number of subgraphs equals the number of nodes in the original input graph, i.e., m n.. Hence, the complexity node-based Subgraph GNNs scales as:
T(n, dmax) = O(n² dmax).
(8)
Higher-order policies (Qian et al., 2022) may allow larger expressive power, but for heftier complexities. As an example, node-pair marking would induce a complexity of On3 dmax).
The quadratic dependency on the number of nodes in Equation (8) hinders the application of Subgraph GNNs to even mildly-sized graphs. At the time of writing, experimenting on the Peptides datasets (Dwivedi al., 2022) already very challenging on common hardware, despite these graphs having on average Rs 151 nodes and similar number of edges.
B.3. Subsampling Bags of Subgraphs
To mitigate the aforementioned issue, one possibility is reduce the number of subgraphs to process, i.c., to lower the impact of m in Equation (7). A convenient approach is to sample a small set & of subgraphs from the bag generated by predefined policy (Bevilacqua et al., 2021; Zhao et al., 2022; Bevilacqua et al., 2024; Kong et al., 2024; Sun al., 2021) (see Figure 4). Essentially, this requires updating Equation (5) as:
sampling
f G (nopoSo
(G).
(9)
Above, a applies a subgraph sampling strategy to reduce the bag cardinality from m to k:
a: B= (G
Gm) s.t. BCB, 1
(10)
The new cardinality & should scale sub-linearly in m, be chosen an appropriate small constant. The optimal design of strategy a is a non-trivial task at the core of several recent works (Qian et al., 2022; Kong et al., 2024; Bevilacqua et al., 2024; Bar-Shalom et al., 2024b). In the present manuscript, we discuss a simple, effective construction based on walk-based centrality measures. Our design is justified by the theoretical considerations and empirical observations in Section 3.2, which are validated by the complementary experimental results reported Section 5.
15

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
C. Hybrid Marking Networks in Algorithmic Form
Algorithm Hybrid Marking Network
Require: Graph G = (A, X), Subgraph GNN f, Max walk-length K, Number of marks T
1: C f- 0)
Vu E G, k E [K]
>. SE init,
2: M f-D 0
Vu G [T]
D. Mark init,
3: B+1
4: for k [K] do
5: for u E G do
6:
C f- Bee/k!
b Compute SEs
7: end for
8: B+ B A
9: end for
CSC + Σx CCSE
b Estimate SC
11: M select-top( (SSC ,T)
D Select nodes
12: fort [T] do
13: MMBa t
Mark nodes
14: end for
UG + f(A, X < CCSE, M)
Forward-pass
return y/
Algorithm 1 describes our HyMN approach, i.e., how graph representations are obtained starting from an input graph G = (A, X). a backbone Subgraph GNN f. and hyper-parametery K, T", specifying, respectively, the maximum walk-length and the number of marks/subgraphs to select.
D. Claims and Proofs
Proposition D.1. Let G = XA be connected graph (with nodes) with initial node features X; = P There exists an L = k + 1 layered Message Passing Neural Network (MPNN) that processes the graph G and can compute the following structural encodings capturing closed-walk probabilities for walks of size to k for any node i, defined as:
(A)
(A)
(A) Σ
Ci
1
(A)
Σj (A)
(A)
up to arbilrary precision.
Proof. We define Message Passing Neural Network (MPNN) as a composition of layers of the form:
( AX x001) x = (X-!))
(11)
(12)
where W(O: and W00o are learned weight matrices, and f() is an MLP for the 1-th layer. We refer to the layers in Equations (11) and (12) as the MPNN layer and MLP layer, respectively, where the MLP layer is assumed to be a single hidden layer with interleaved ReLU activations.
Note that, as reported in Algorithm 1, we perform select-top operation (line 11). In some cases, which we found to rarely occur in practice, depending on the value of T. this operation has to arbitrarily break ties between nodes with the same exact centrality values. This tie breaking procedure additionally be either side-stepped by marking all nodes with the same centrality value be made equivariant by accounting for ordering between colours from an auxiliary DS-We DS-WL-like refinement (Bevilacqua et al., 2021).
16

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
We recall that the initial node feature matrix, X [ is given follows:
P
P2
X
P
where,
(A)
(A)
(A)
(A)
p =
1,
E
R
1!
2!
3!
kd
Step 1: Recovering the unnormalized CSE. To uncover the unnormalized CSE, we set W(1) 0 and W e ((++))x((+++1)++)) as follows:
1
0
0
0
0
0
0
11
0
0
0
...
0
W())
0
0
2!
0
0
kd
0
0
Thus, the MPNN layer gives:
p unormalized"
unormalized
= X A (P
P2
P unormalized
where,
Pi unoomalizedd
[L. (A) (A)), (A) (A)) 0, 0........... O] (k++1)+
For the MLP fo, identity weight matrix and bias vector, which is all zeros except for the last & values, which ones:
( = (0.0....,0,1 1, ... 1] (++1)++
Thus, we obtain X(), such that:
x = (A) (A) (A).. ..ts.....,AA....
(A) 1,..,, E (k+1)+
Step 2: Compute the matrix of closed-war walk probabilities. We compute the matrix of closed-walk probabilities in sequential steps. For each j-th step, we use the following weight matrices:
I++1
0
w
1j-1
0
Og (j- 1)
0c+1
0
w(+1);
0,-1
0
Ik- (j 1)
Where J, is an identity matrix, and 0,, is an zero matrix (if n. = 0 the corresponding block is omitted). This means:
XWO+1)0
keeps only the first + columns of X, and,
AXW(++)
multiplies by only the last l: (j columns of X.
17

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
By doing this iteratively for j k. and setting the interleaved MLPs identity weight matrices, we obtain the node matrix ( such that:
R
72
n
X x
(A))) (A) (A)...... (A)
Σ (A)
(A)
> (A)
(
5=1
==1
Let F; F 2 + R be the following continuous function:
1, if i=f===0. =0 0,
F(x); =
X if O.
Xk++
Since the graph is connected, the denominator is always non-zero, making the function continuous. Additionally, since we are considering finite graph with nodes, the input to the function F lies within compact set.
Using the universal approximation theorem (Horiik, 1991; Cybenko, 1989), F can be approximated to an arbitrary precision using an MLP. Thus, we use the MLP of layer + 1 to realize F. obtaining the following node matrix,
(A)
(A)
(A)
x (k+1))
1 Σ (A) 1
E ER
(A)
This completes the proof.
Theorem D.2 (Theorem 4.1 in Section 4). There exists a pair of graphs G and G' such that for any CSE-enhanced MPNN model MesE we have Mc) = MC')(G"), but there exists DS-Subgraph GNN model (without CSEs) Maub, which uses top-k Subgraph Centrality policy such that Mant. (G) + Mant (G").
Proof. Using the notation of (Read & Wilson, 1998), let G, G' be the quartic vertex transitive graphs Qt15 and Qt19 respectively (Here vetrex transitive means that for each pair of nodes there exists graph automorphism that maps one node to the other, and quartic refers to 4-regular). As these graphs are 4-regular and of the same size, they are I-WL indistinguishabl. In addition, as they are vertex transitive, for each pair of indices i, we have:
trace(A*)
A A
(13)
12
trace(AA'k)
A/h = 1
(14)
12
Here the last equalities hold because both graphs have 12 vertices. Thus, show that G and G' are indistinguishable by MPNN centrality encoding it is enough to show that trace(A*) trace(A"*). As G and G' were shown in (Brouwer & Spence, 2009) to be co-spectral (i.e. their laplacian has the same eigenvalues) and 4-regular, matrices A and A' have the same eigenvalues. Thus we have:
(A)* = Σ 2x (ra'e
(15)
Here A is the i-th eigenvalue of both A and A'. Thus the central encoding of all nodes either graph is equal, and they are indistinguishable by any any MPNN + CE model. On the other hand, we observe that the degree histogram in the 1-hop neighborhood of any node differs between the two graphs, Qt15 and Qt19. Since an MPNN over graph with marked node can compute the degree distribution of the node's 's 1-hop neighborhood, M Manhgaph can distinguish between the two graphs. This concludes the proof.
Theorem D.3 (Theorem 4.2 in Section 4). There exists a pair of graphs G and G' such that for any Subgraph GNN model Maub. which uses a top-k Subgraph Centrality policy we have Mau. (G) = M (G'). but there exists an MPNN + centrality encoding model MESE such that Mc) # Mc)
18

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Balk-Based Centrality
Proof. We begin by examining the scenario where k 1, meaning that our policy randomly selects subgraphs corresponding to the node with the highest centrality measure. Consider the graph G, which is formed by attaching a global node every vertex of cyclic graph of length 6 Next, define G' as the graph obtained by attaching global node to each vertex of two disconnected cyclic graphs, each of length 3 (The global node is also attached to itself through a self loop). These graphs are displayed in Figure 6. It can be easily seen that G and G' are WL indistinguisaable (e.g. by induction). We first prove that both in G and G' the global node has the highest centrality measure. This implies that for both graphs, the resulting bag of subgraphs is of size one and is thus equivalent to standard message passing on the graphs (here we can ignore marking as the global nodes have unique degree and so they can be uniquely identified by standard message passing). This implies that the two graphs are indistinguishable by any Subgraph GNN model sabgraph which uses a top-1 node centrality policy. We then show that the multiset of values of the centrality encoding of each graph is different, showing that it can be distinguished by an MPNN + centrality encoding model. To show that in both graphs the global node has the higher centrality, we first prove the following lemma:
Lemma D.4. Let A denote the adjacency graph of one of the above graphs. v denote the global node and u1 U2 denote a pair of nodes of the graph such that un # v. For each k E N we have:
A p,uu
> A
u1.u2
A > 0
(16)
0,02
A A A
Proof of lemma. We use induction on k. As is connected to all nodes including itself, for k- = 1, Au,u, 1. Since, disregarding the global nodes, G, G" are simple graphs we have Au = 0, Augia S 1, thus the base case holds. Assuming the induction hypothesis holds for some k; we first notice that
A Ahg.: A. A. A A...
A&+1
(17)
Here, Ab.. A. ta represents the column/row vectors induced by node u respectively and denotes inner product. The inequality above follows from our induction hypothesis and the fact that all entries of the matrix A are nen-negative Next, we notice that
A++1 = Auzii . A 2 Aug.v A > O. u2.0
(18)
In addition, we notice that A$ Ab... we get:
Au
Ahe Abtiin Aun.yy where the last equallity holds because Auymo = 0. Thus,
A 0,0
= Ab 0,00
Aug + E
Al Dias"
Au, > Als . Aur + Σ A Abr
Auau =
1k+1 M1
(19)
ustuu
utuur
This completes the induction step.
As explained before, the last lemma shows that top-1 centrality node marking policy always produces a bag with a single graph where the global node is marked. As the global node can be uniquely distinguished by its degree, this shows that Subgraph GNN with this policy is equivalent to standard message passing and is thus unable to distinguish G and G'. Finally, computing the centrality encoding of order 3 we see the multiset of features of the two graphs are different and so message passing- CE is able to seperate G' and G".
We now address the general case of a top-k centrality mode-marking policy. Let GR, G¹2 denote the graphs consisting of k disjoint copies of G and G", respectively. In each disjoint copy, the global node is replicated independently and maintains a higher centrality than all other nodes within that copy. Thus, in both graphs, the k nodes with the highest centrality are the k copies of the global node.
The bag of graphs generated from Ge and G¹2, using the top-k centrality node-marking policy are then composed of k copies of G1 and G², respectively, where single copy of the global node is marked. Notice that in each one of these bags, all graphs are isomorphic to each other, thus it is enough to show that GR with a single marked global node copy is 1-WL indistinguishable from G²2, with a single marked global node copy. To see this holds, notice that as we have seen above, the connected component of G containing the marked node is 1-WL indistinguishable from the copy of the connected component of G²2 containing the marked node, and the lo - unmarked connected components of G3 are 1-WL indistinguishable from the unmarked connected components of G Thus any subgraph GNN which uses top-k centrality
19

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Q115
QC19
Figure Two quartic vertex transitive graphs which cannot be distinguished with MPNN CSE can be distinguished Subgraph GNN with a top-1 Subgraph Centrality policy.
Figure 6: Two graphs which cannot be distinguished by a Subgraph GNN with a top-1 Subgraph Centrality policy without CSE but can be distinguished by an MPNN CSE. One graph is hexagon with global node connected all other nodes, and another graph which depicts triangles connected global node.
node marking policy unable to distinguish G₃ and G Finally, the centrality encoding values of each node Ucopy in G3 equal the centrality encoding value of the node in G which corresponds Meepy- As have before the set of centrality encoding values of G and G' are different, the set of centrality encoding values of G3 and Gy, are also different, and so message passing CE is able to separate G and G¹p-
Proposition D.5. Let G = (A,X) be finite graph, and let BG be the bag generated from original graph G. Let DSS-GNN be the subgraph-based GNN that processes the bag Bg. There exists a set of weights for DSS-GNN, such that DSS-GNN(Bc) MPNN(G) for any MPNN processing G with centrality-base structural encodings as initial node features.
Proof. Let (X','' represent the node feature matrix X and adjacency matrix A', respectively, for the i-th subgraph the collection of subgraphs. We adopt the binary node-marking technique from (Bevilacqua et al., 2021), where X
20

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality includes one-hot encoded vector for the root node identification, with in the i-th position,"
X with at the i-th position,
(20)
we note that in this case, the adjacencies of all subgraphs, denoted as {A');= are identical to the adjacency of the original graph, A.
We recall that the DSS-GNN architecture applies an MPNN over each subgraph independently, followed by an MLP
Subsequently, MPNN followed by MLP operates shared component, enabling information sharing across subgraphs.
To be more explicit, the architecture is defined as follows:
X = MPNN 41 (f,x'-1:1)
(21)
y1-1: plil (1 (x1-1:))
(22)
n
n
81- MPNN1:2
Σ A Σ X1-1
(23)
yl = (}
(24)
x = yl-1;i + yl-1
(25)
where the MPNN is defined as:
MPNN(X) AXW* + XWO
(26)
The proof proceeds three steps. First, we compute the centrality encoding at the root nodes, recall Equation (4), specifically the shared information component to propagate this root node information across all subgraphs.
at X; Second, Finally, we simulate an MPNN over each subgraph. Since the subgraphs are identical and equipped with the centrality encoding, the proof is complete.
Step We begin by applying the K MPNN layers to each subgraph independently. and setting to the weight matrices of the shared component, effectively enforcing no sharing between the subgraphs.
More specifically, the k-thh layer, the following weight matrices used:
1
0 1
0
0
0
0
0
0
0
0
W
W
0
0/
kx(++1)
kx(++1)
where:
w a x (A: + 1) matrix consisting of a x & identity matrix Iç followed by an extra column of zeros:
w
(Is O 0xx1)
"Although this proof does not consider additional node features, can he easily adapted to incorporate them.
21

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Specifically, when w is multiplied by matrix B B i.e., BWO, it appends column of zeros the right of B, leaving the structure of B unchanged but with additional column of zeros.
w is a k x (k + 1) matrix consisting of l zero matrix 0 Ox followed by column of all zeros except for a in the last row:
W (Oexk ek)
Specifically, when W multiplied by a matrix Bo*k i.e. BW the resulting matrix is composed of the zero matrix and the last column of B. In other words, this operation extracts the last column of B and appends it to a matrix of zeros of size & x k.
In this setup, for each i, the term AX' W the k-th layer propagates the node marking to neighboring nodes and places it in the last column. Meanwhile, the term X XWO copies the propagated marking from the previous is layers.
Thus, by summing the two terms, after K layers, the node features Xj are given by:
[1. A2 vyl
AA for j = i, for j + i,
xj
(27)
where vy holds at its l--th slot the number of marks propagated to node j in subgraph at the step k.
Since each entry in the vectors X for any i E [n] and j E [n]] represents the propagation of a mark over k E [K] steps specifically, the number of walks from the root node of subgraph i to node j (within subgraph i) - the number of possible values for these vectors is constrained. Moreover, because the original graph is finite, the total number of possible values for these vectors must also finite.
By Theorem 3.1 in (Yun et al., 2019),, there exists MLP the K-th layer that can implement the following mappings:
8 a1,,0,,,2,..... ................................ akl) = [,
01
02
aK
(28)
11 2!
K!
g (12,b1, b2..., bk]) 0g+1,
(29)
for any * and a,, b; E R. At this step, the root nodes hold the centrality value, recall Equation (4), while all other nodes hold the feature vector 0g+1-
Step 2. Next, we utilize the shared information component by setting the weights of its MPNN as follows, W = 0 and
W = I, which effectively broadcasts the root node information to the corresponding nodes in all other subgraphs. To prevent the root nodes from receiving double the value, we initialize the MPNN that operates on each subgraph individually with zero weights.
Step 3. At this point, we have n copies of the original graph, each equipped with its corresponding centrality values. Therefore, the MPNN over each subgraph effectively simulate the MPNN over the original graph, now with centrality values assigned to the nodes. Assuming mean readout is used at the conclusion of both the DSS-GNN(BG and the MPNN(G),, their outputs will be identical.
This concludes the proof.
We note that this result also valid for Subgraph GNN architectures that subsume DSS-GNN, e-g., GNN-SSWL-+ (Zhang al., 2023a).
E. On -nnuiee-Inducedd Perturbations and the Number of Walks
In this section, we report more details and comments on our Observation introduced in Section 3.2.
Thiis theorem assumes the output is bounded between 1 and 1. However, we relax this assumption as long the outputs are bounded (and they are since the original graph is finite). To handle this, we can the theorem calculate the normalize values (dividing each value by the upper bound), and then use an additional MI.P to scale the results back to the original values.
22

---

Balancing Efficiency and Expressivenes:: Subgraph GNNs with Walk-Based Centrality
We start by commenting on Equation (3). We recall that we are interested in upper-bounding the amount of output perturbation induced by marking node Effeetively, this corresponds the distance yy ys,l namely, the absolute difference between the predictions backbone MPNN computes for the original graph (G) and the subgraph obtained by marking node u (S,).
For an I--laer MPNN in the form of Equation (2), we obtain Equation (3) by an almost immediate application the results (Chuang & Jegelka, 2022). Indeed, let us rewrite:
lyG vs.l = 10(L+1)
h (.(
((L+1)
Σ
(30)
MEG
NES.
where (.C(L) (,,(1) indicate, respectively, the representations of node u in graph G and its perturbed counterpart S... Now, by Chuang Jegelka (2022, Theorem 8) we have:
L+11 II
1yG yssl S
K
TMD L+1
(G, S.)
(31)
t=1
(A)
where (A) is the L + 1-depth Tree Mover's Distance (TMD) (Chuang Jegelka, 2022) with layer-weighting calculated between the original graph and its marked counterpart.
In the same work, the authors provide upper-bound on the TMD between graph and perturbed version obtained by change in the initial features of a node (Chuang & Jegelka, 2022, Proposition 11). We restate this result.
Proposition E.1. (Chuang Jegelka, 2022, Proposition 11) Let H be a graph and H' be the perturbed version of H obtained by changing the features of node v from nv to s/y. Then:
TMD H. H
d Width:(T!)) || - =x,11
(32)
1=1
where X E R+ is layer-wise weighting scheme dependent w and (Tdth is the width at the I-th level of the L-deep computational tree rooted in e.
We can readily apply Proposition E.1 and leverage the fact that marking only induces unit-norm feature perturbation to get:
L+1
lUG
ys.l <
II
(G,S))
(33)
1=1
L+1
L+1
K
Σ
A (T
(34)
1=1
1=1
Finally, we note that Width; (II++1) corresponds to the number of walks of length / - 1 starting from V. This can be easily seen by noting that the leaves of the computational tree can be put in bijection with all and only those walks of length 1-1 1 starting from 10 This value notoriously computed from row-summing powers of the adjacency matrix A, so that: Width (A'A'1)) We ultimately have:
L+1
L+1 (T
lyG yssl
Σ
A
(35)
1=1
l=1
L+1
II
K
(1)
Σ
X
E(A
(36)
1=1
19This be constructed, e.g., by associating leaf nodes the walks (uniquely) obtained by "climbing up" the computational tree up the root.
23

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
The above bound is easily extended consider closely related analysis: the impact of adding single node-marked subgraph S bag formed by the original graph only. This analysis would enlighten us the impact single subgraph addition in the case of "augmented policies", which we use throughout experiments in Section 5, see Appendix G.I.
B=(G) B= (8,())) |, where these outputs are given by Equation (45), with base
In other words, we would like bound ly
MPNN backbone as per Equation (2). We have:
B=(G) - Uc Vc
[= = 10(L+1)
G + +h5,)) - ((L+1)
h G.
(37)
DEG
DEG
I kL+1,
G,o + +,,,))
G,
(38)
vEG
DEG
where K++1 is the Lipschitz constant of the prediction layer @(L-1) 1), We can rewrite the above as follows by appropriately rearranging terms and by the triangular inequality:
lvG
B=(G)
VG
B=(s.o)
skL+1 0
11 Eng + +
Σ
(L) G
|l
(39)
NEG
VEG
S k((+111
(1) G
+
(L)
G.
(40)
vEG
eEG
VEG
(A)
where, we note, (A) is the distance between the embeddings of the marked and unmarked graphs, before a final predictor applied. This term can be bounded similar to initial analysis for Observation 1:
(1)= = || Σ
Σ
(41)
VEG
VEG
0)
TMDL++ (S,
G)
(42)
(1)
where (B) can be upper-bounded, again, by Proposition E.
Putting things together:
L-1
B=|G)
B=19,0] < k((+1), (1 ( VEG
(L) G
K
(1)
Σ N 1=1
(A(
(43)
[=1
Differently from the above analysis, we observe a contribution given by ErEr G.al This could be upper-bounded, e.g., by the sum of the Stree-norms Chuang & Jegelka (2022) of the computational trees over the original graph. We note that (the presence of) this term is, however, independent on the selection of the specific node to mark.
In future developments of this work we envision to more deeply enquire into the relation between Equation (43) and Equation (1), and into the principled choice of a specific centrality measure among different possibilities.
E.1. Perturbation Analysis on an Additional Dataset
As outlined in Section 3.2, we explore the amount of perturbation from different marking schemes on the output of an untrained GIN model. We have shown in Figure 1, the effect of these marking schemes on the MUTAG dataset. Here, in Figure 7a and in Figure 7b, we additionally show the results for the NCII dataset and for Erdös-Renyi (ER) graphs. The ER graphs are consistent with our correlation analysis experiment Section 3.2, where we randomly generate 100 ER graphs, each with N- 20 nodes and wiring probability p 0.3.
We have allowed little abuse notation here by using S to refer to the "subgraph" obtained by marking node S in G.
24

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
NCI1
ER_gre [R_graphs
3.5
0.030
[MPNN MPNN((G)
IMPNN(S.) MPNN
2.5
0.020
0.015
1.5
0.010
1.0
Max Centrality
Centrality
Random
Random Centrality
0.000
x
Min Centrality
0.0
0
20
40
60
100
100
Graph
Graph
(a) NCII dataset alterations.
(b) Erdös- Re-yi graph alterations.
Figure 7: Plots showing the alteration of graph representations using GIN by adding an additional node-marked subgraph with (i) the highest centrality, (ii) the lowest centrality, and (iii) random marking for hoth the NCT1 dataset (left) and Podöös-Reny graphs (right).
F. Additional Experiments
F.I Additional Experiments with Other Backbones
We have already experimented with GCN as the backbone on the Peptides datasets. Additionally, we run GCN as a backbone on OGB molecular datasets (see Table 6). Interestingly, we find that a GCN backbone achieves the best results on MOLBACE. Moreover, we perform experiments on yet another backbone: GatedGCN (Bresson & Laurent, 2017). This complements backbones used in the Graph Transformer literature such as GPS. The results peptides and MolHIV shown in Table 7. These results further show that the walk-based centrality structural encoding can improve performance over the backbone MPNN, and we can improve performance even further by using it for sampling subgraphs.
Table 6: Results on OGB benchmarks using GCN as the backbone architecture.
Model
MolIIIV
MolBace
MolTox
GCN
76.06 0:0.7
79.15 1.44
+00699 76.07
75.29
MyyM (GCN, T=2)
76.82 1..20
83.21 10.51
10.50
Table 7: Results on the Peptides and MolHTV benchmarks using GatedGCN as the backhone architecture.
Model
MolITIV
Peptides Func
Peptides Struct
GstedGCCN
00.65
0.6558 1000068
0.2497 0007
GatedGCN CSE
80.33 1.0.6
0.6611 1.00058
0.2482 10.0010
HyMN (GatedGCN, Tw2)
79.02
40.0079
40.0013
HyMN (GatedGCN, T=2)
81.07 =0.21
0.6788 #0.0052
0.2471 #0.0007
F.2. Results on ZINC and Additional Model Comparisons on MolHIV
We experimented with the ZINC-122 12K molecular dataset (Sterling & Irwin, 2015; Gómez-Bombarede et al., 2018), where we maintain a 500k parameter budget, in line with previous works.
We compared the test MAE using HyMN to other sampling approaches (Qian al., 2022: Bevilacqua et al., 2024), a full-bag Subgraph GNN, Graph Transformer (GPS) (Rampášek et al., 2022), two expressive GNN baselines (GSN, CIN) (Bouritsas et al., 2022; Bodnar et al., 2021 1a) and the two alternative architectures Graph-ViT and Graph MI.--Mxent by (He et al., 2023). Results are presented in Table 8. We additionally report results on MOLHIV in Table 9, often used as a reference bed for most full-bag methods (Bevilacqua et al., 2021; Frasca et al., 2022: Zhang & Li, 2021; Cotta et al., 2021; Zhao et al., 2022). We observe that our hybrid method can outperform full-bag Subgraph GNNs as well as previously proposed subsampling based approaches. Additionally, we perform competitively with CIN, which takes into account higher-order
25

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 8: Test results on ZINC. The first and second best results are color-coded.
Method
ZINC (4)
GCN
0.321 +0.009
0.163 +0.004
GSN
0,101 40.010
CIN
0.079 #0.006
GPS
0,070 200004
GINE-MLP-MaR
1:0000
GITE-VIT
0.085 10.004
FULL
0.087 10,003
OSAN
0.177 +0
POLICY:LEARN (T
0.120 +0.003
RANDOM 22)
0.136 +0.005
GIN+CSE
0.092 +0 00.002
HyMN (GIN, T=1
0.080 +0 +03003
HyMN (GIN, T=2)
0.083 +0.002
Table 9: Test results on MOLHIV. The first and second best results are color-coded.
Method
MOLHIV
GCN
76.06 +0.97
GIN
75.58 1:144
Reconstr GNN
76.32 = 11.40
DSS-GNN
76.78 1.66
GSN
80.39 10.90
CIN
80.94 1.057
GPS
78.80 1.001
GINE-MLP-Mii
79.97 1.00
77.92
Nested-GNN
78.34 = 1.86
GNN-AK+
79.61 11199
SUN
80.03 10.55
FULL
76.54
POLICY-LEARN 2T=
79.13 +0.00
RANDOM 2I=
77.55 #122
GIN-CSE
77.44 11.87
HyMN (GIN, T:D)
80,36 1.23
HyMN T=2)
interactions and explicitly models ring-like structures. Non-message-pasiine based architectures can perform slightly better in absolute terms, but for higher run-tims (see comparison with GPS in Appendix H). We highlight that additionally using subgraphs can outperform purely using the centrality- encodings (Q4). In particular, the two approaches in tandem deliver exceptional performance on MolHIV, for
F.3. Minimum Centrality Marking for Counting Substructures
As highlighted Section 3.2, low-centrality nodes perturb representations only to a limited extent, causing the method to work in a regime close vanilla 1-WL GNN. We also empirically observe that the perturbations induced by marking high-centrality nodes correlate much more with potentially predictive features, such as subgraph counts. In order further evidence this point, have experiments for counting triangle and 4-cycle substructures, studying the impact of sampling marked subgraphs associated with the minimum values of the Subgraph Centrality (SC). We report the results in Table 10 and Table 11, along with those of random sampling and max-centrality sampling (MAE, the lower the better). We observe that min-centrality sampling is indeed outperformed by the two other strategies on all settings, further suggesting the limitations of marking nodes with low subgraph centrality.
F.4. Comparison to Other Centrality Measures
We compared the impact of using different node centrality measures as node marking scheme on how much they altered the graph representation. For each of these centrality measures, we measured the distance (S.) - f(G)] on 100 graphs from two different real-we world datasets from the popular TU suite: MUTAG and NCI1 (Morris al., 2020a). Here, f an
26

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 10: Performance comparison for different policies on triangle subgraphs.
Policy
10 Subgraphs
20 Subgraphs
30 Subgraphs
Min SC
0.78
0.52
0.43
Random
0.62
0,48
0.40
Max SC
0.20
0.10
0.03
Table 11: Performance comparison for different policics on 4-cycle subgraphs.
Policy
10 Subgraphs
20 Subgraphs
30 Subgraphs
Min SC
0.74
0.63
0.41
Random
0.59
0.45
0.36
Max SC
0.38
0.12
0.08
untrained 3-layer GIN (Xu et al., 2018). 8). We can see from Table 12 that marking the node with using the maximum values of the three walk-based centrality measures (Subgraph, Communicability, Katz) leads to the highest average perturbation and marking the node with the minimum of these centrality measures leads to the lowest. This implies that this family of centrality measures is most aligned with the perturbation distance.
Table 12: Amount of perturbation from the original graph representation MUTAG and NCI1 using 3-layer untrained GIN with 32
hidden dimension by incorporating node-marked subgraph with different marking policies.
Marking Policy
MUTAG Perturhation
NCII Perturhation
Random
0.0648
0.0126
Minimum Degree Centrality
0.0202
0.0075
Maximum Degree Centrality
0.0968
0.0075
Minimum Closeness Centrality Maximum Closeness Centrality
0.0241
0.0073
0.1038
0.0184
Minimum Betweenness Centrality
0.0202
0.0076
Maximum Betweenness Centrality
0.0957
0.0183
Centrality
0.0177
0.0063
Maximum Katz Centrality
0.1051
0.0200
Minimum Communicability Centrality
0,0177
0.0063
Maximum Communicabllity Centrality
0.1056
0.0200
Minimum Subgraph Centrality
0.0177
0.0063
Maximum Subgraph Centrality
0.1055
0.0201
To further assess the benefits of our specific centrality encoding for sampling subgraphs, we compared against using other centrality measures to sample subgraphs in the counting substructure task. We used Closeness centrality, Betweeness centrality, Pagerank centrality and Degree centrality as baselines using the Networkx library (Hagberg al., 2008). From Figure 8, can that using any of the different centrality methods performs better than random sampling across all substructures and number of samples. We also find that the Subgraph Centrality which we use, outperforms all other approaches in counting 3 and 4-cycles for any number of samples and in counting 3 and 4-paths when number of samples 2 5. For 4-cycles and other substructures, we find that Subgraph centrality is best, followed by Degree and Pagerank centrality and then Closeness and Betweenness centralities perform the worst of these centrality measures. This ranking of performance is aligned with how correlated these substructures are with the Subgaph Centrality on these synthetic graphs (as shown in Table 13).
To further compare different centrality measures, we ran additional experiments on the Peptides and MolHIV datasets. We experimented in particular, with the Betweenness Centrality (BC), the Katz Index (KI) and the Subgraph Centrality (SC). We see from Table 14 that the performances achieved by different centrality 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 (Estrada & Rodriguez- Rodriguez-Velazquer, Velazquez, 2005) and Table 13). It is also worth noting that Subgraph Centrality can be more efficient to calculate than these other centrality measures using the Networkx library (see Table 15).
27

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Triangles
4-cycles
0.8
0.8
0.7
Random
Random
0.6
Closeness Centrality
0.6
Claseness Centrality
Betweeness Centrality
Betweeness Contrality
MAE
0.5
Degree Centrality
Test MAB
Degras Centrality
0.4
Pogerank Centrality
Pagerank Contrality
Subgraph Centrality
Subgraph Centrality
0.3
0.3
0.2
0.2
0.1
0.0
10
20
30
40
50
0
10
20
30
40
50
Bag Size
Bag Size
(a) Counting 3-Cycles.
(b) Counting 4-Cycles.
3-paths
4-paths
0.18
0.20
0.16
Random
0.18
Random
Clsseeess Centrality
0.16
Clasaness Centrality
0.24
Betwaeness Contrality
Betweeness Contrality
Test MAE
Degree Centrality
Test MAB
0.14
Degres Centrality
0.12
Pagerank Centrality
0.12
Pagerank Centrality
Subgraph Centrality
Subgraph Centrality
0.10
0.10
0.08
0.06
0.06
0.04
10
20
30
40
50
10
20
40
50
Bag Size
Bag Size
(c) Counting 3-Paths.
(d) Counting 4-paths.
Figure 8: Comparing different centrality measures for counting different substructures synthetic random graphs.
Table 13: Correlation between the different centralities and Subgraph Centrality on the random regular graphs in the substructure counting experiments.
Centrality
Correlation Subyraph Centrality
Pagerank Centrality
0.923 +:0 025
Degree Centrality
0,970 :0.012
Betweeneess Coutrality
0.801 +:0 071
Closeness Centrality
0.786 1:0.067
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 Section 3, we think they constitute particularly strong candidates across use-cases.
F.5. Comparison between Centrality- -Baee Structural Encodings and RWSE
Here we aim outline some of the similarities and differences between our Centrality structural Encoding (CSE) defined in Equation (4) and the Hindom-Wall Structural Encoding (RWSE) introduced in (Dwivedi et al., 2021). The RWSE uses the diagonal of the k-step random-walk matrix defined in Equation (44) defined as:
RWSE [(AD-)) (AD- ... -... "AB...,,AA--" E R p
(44)
These terms show similarity to our CSE as it also stores powers of the diagonal of the adjacency matrix, but it has a different normalization term that depends on the degree. In Proposition D.1, we show that using an MPNN with CSE can compute the the probability, for all possible walks departing from node, that a walk will lead back to the start. RWSE structural encodings are subtly different in that they compute the landing probability of a random walk from a node to itself. In this case, rather than weighting all possible walks equally, the walks are weighted by the degrees of the nodes along the walk; a walk where there are fewer alternative routes (other nodes) for the RW is more likely to occur.
Here we aim to empirically examine this difference to see (i) which one is a more effective Structural Encoding and (ii)
28

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Bascl Centrality
Table 14: Comparison of different centrality measures on real-world molecular datasets.
Centrality for Sampling
MolHIV
Poptides-Fund Func
Peptides-Simue Struct
Betweenness Centrality
78.86 1:0.98
0.6749 0060
0.2478 1000006
Katz lodex
79.58 4.098
0.6756 0000
0.2469 =0 0008
Subgraph Centrality
79.77 70.70
0.6758 =0.0050
0.2466 +0.0010
Table 15: Timing of different centrality measures an Erdös- Renyi graph with 1000 nodes and p=0.5 using the Networkx library.
Centrality
Time (8)
Betweenness Centrality
83.12
Katz Index
1.31
Subgraph Contrality
0.54
which one more effective for subgraph sampling. To show the effect of both CSE and RWSE as SEs, we compared both on the Peptides datasets (Dwivedi et al., 2022) with two different base MPNNS (GCN and GIN). From Table 16, it can be seen that centrality encoding performs similarly to the RWSE encoding; matching almost exactly except with GCN on Peptides-Fune.
To answer (ii) and highlight the benefit of sampling based on CSE over using RWSE, we compared using the sum of these different encodings to sample the subgraphs in the counting substructures experiment. From Figure 9, we see that our sampling method is better for counting all substructures and for all the number of samples in comparison to RWSE sampling.
In conclusion, Appendix G.2 shows that our CSE better for sampling subgraphs and Table 16 shows that CSE is competitive when purely used as Structural Encoding. Therefore, it is well motivated to use the CSE for our hybrid method where we need an SE and to use it as a sampling method. Future work could consider further understanding the expressivity differences between these SEs and the role of the normalization factor.
F.6. Further Examining the Effect of CSEs
In Table 2, we explore the effect of HyMN with and without CSEs. In order to complement these results, we additionally evaluated the effect of CSEs on HyMN and GIN with the Peptides and ZINC datasets. The results are reported in Table 17. 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.
G. Experimental Details
In this section we provide details on the experimental validation described and discussed in Section 5,
Table 16: Results on the Peptides datasets comparing CSE with RWSE.
Method
Peptides: Func (f)
Peprides Strnct (I)
GIN
0.6555 10.0088
0,2497 10.0012
GIN RWSE
0.6621 10.0067
0,2478 10.017
GIN + CSE
0.6619 0077
0,2479 #0.0011
GCN
0.6739 1.00024
0.2505 +0.0023
GCN RWSE
0.6860 - 0050
0,2498 10.001
GCN CSE
0,6812 00.003
0.2499 #0.0010
29

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Balk-Based Centrality
Triangles
4-cycles
0.8
0.8
0.7
RWSE
RWSE
0.6
SC
0.6
SC
Test MAE
0.5
Test MAE
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
0.0
10
20
30
40
50
10
20
30
40
50
Bag Size
Bag Size
(a) Counting Triangles.
(b) Counting 4-Cycles.
3-paths
4-paths
0.20
0.16
0.18
RWSE
RWSE
0.14
SC
0.16
SC
Test MAE
MAE
0.14
0.12
0.12
0.10
0.10
0.08
0.08
0.06
0.06
0.04
10
20
30
40
50
10
20
30
40
50
Bag Size
Bag Size
(c) Counting 3-Paths.
(d) Counting 4-paths.
Figure 9: Comparing our centrality sampling with RWSE sampling for counting different substructures on synthetic random graphs.
G.1. Architectural Form
We always employ a reference Subgraph GNN architecture f whose output, for an input graph G = (4, E)) associated with node-marked bag B, is given by:
8 = f(B(G)) o((+1)
(
k)))))
(45)
h (1)
hg (A, (1-1)
Me (E), M.
(46)
h Ss. (X) CCSE
(47)
where ((L+1) a final prediction module and h 1/ refer to the representations of generic node v on the original graph G and subgraph S. As evident from Equation (45), we employ an "augmented policy" which always includes copy of the original graph in the bag of subgraphs (Bevilacqua al.. 2021). As we only consider node marking policies, this copy only differs from (sub)graphs in B by the fact that no nodes are marked. Representations h hg, are obtained la DS-GNN (Bevilacqua et al., 2021), that is, by running independent message-passing independently (see Equation (46)). Note that μ explicitly processes available edge features (F)) and marking information (M, see Algorithm 1). As it will be specified later on, we always consider either GIN (Xu al., 2018) or GCN (Kipf
on each (sub)graph
12 a tensor storing edge features.
30

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 17; Results on ZINC and Peptides datasets showing the effect of CSEs on both GIN and HyMN.
Method
ZINC (MAE L)
Poptides-Fuus Funn (AP 1)
Poptides-Struct (MAE .)
GIN Xu et al. (2018)
0.163 20.004
0.6558 #0.0068
0.2497 =00001 2
GIN-CSE: My (GIN, T=1) w/out CSE
0.092 1.0002
0,6619 10.0077
0,2479 1000011
0.125 0.0004
0.6758 00.0050
0.2466 10.0010
HyMN (GIN, T=1)
0.080 00.003
0.6857 =0.0055
0.2464 #0.0013
Welling, 2017) as MPNN backbones. Equation (47) specifies initial node features for node v in subgraph S. Finally, 72, Te are -eepedet node- and edge-feature encoders, and that CCSE is computed according to Algorithm
Note that, across all molecular benchmarks, the GIN layer resembles the GINE architecture (Hu al., 2020c), but concatenates the marking information follows:
5 = - ( Mh (111) Mo.s! (
[o(h) + ne()) wEN(v)
Σ
(48)
where My.s is the mark for node subgraph S, 7. (E) refers to the encoded edge features for node-pair v, u, and is a ReLU non-linearity, As for our GCN (Kipf & Welling, 2017) backbones, the marking information is simply provided the input of the network, and edge features discarded.
G.2. Synthetic Experimental Details
G.2.1. DATASET GENERATION
For the synthetic counting substructures experiment, we generated a dataset of random unattributed graphs in a similar manner to (Chen al., 2020). In their experiments, they generate 5000 random regular graphs denoted RG(mm d), where m is the number of nodes in each graph and d is the node degree. Random regular graphs with nodes and degree d are sampled and then m edges are randomly deleted. In their work, Chen et al. (Chen et al., 2020), uniformly sampled (m, d) from (10, 6), (15, 6), (20,3) 5). (30, 5). However, we want to test the effectiveness of our sampling approach for larger sizes of graphs. Additionally, we found that the number of substructures present in the graph was related to the graphs size (see Figure 10). Therefore, we wanted to create a more challenging benchmark with larger graph sizes. Therefore, we set (m, d) to be (60, 5) for all graphs.
G.2.2. SYNTHETIC MODEL PARAMETERS
For our synthetic experiments, we set the base GIN to have batch size of 128, 6 layers of message-passing, embedding dimension 32, and Adam optimizer with initial learning rate of 0.001 as prescribed by (Bevilacqua et al., 2024). We trained for 250 epoch and took the test Mean Absolute Error (MAE) at the best validation epoch.
G.3. Real-World Experimental Details
In this section, we provide further details about our experiments. We implemented our method using Pytorch (Paszke et al., 2019) and Pytorch Geometric (Fey & Lenssen, 2019). For the GIN model (Xu et al., 2018), we use Batch Normalization and the MLP is composed of two linear layers with ReLU non-linearities. Additionally, we use residual connections in each layer. The test performance at the epoch with the best validation performance is reported and averaged over multiple runs with different random seeds. All the benchmarking results, including the extra ablations, are based on 5 executed runs, except for Peptides-func and Peptides-struct which are based on the output of four runs. In all our experiments we used AdamW (Loshchilov & Hutter, 2019), together with linear warm-up increase of the learning rate followed by its cosine decay. Experimental tracking and hyper-parameter optimisation were done via the Weights and Biases platform (wandb) (Biewald et al., 2020). In Table 2, the number of subgraphs used (I") was selected to match the choices made in other baselines, such as PL, making the comparisons as informative as possible. In Table and Table 8, we chose T to be the smallest possible value, i.e., T = This is justified by our focus on efficiency. Specific papammtrrreeter information for each dataset can be found the corresponding subsection.
31

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Number of Nodes
0.25
10
15
20
30
0.20
Density
0.15
0.10
0.05
0.00
5
10
15
20
25
30
Number of cycles
Figure 10: Evaluating the dependency between the graph size and the number of 4-cycles in the dataset generated from Chen et al. (Chen
al., 2020).
G. HARDWARE
All experiments were run on single NVIDIA GeForce RTX 3080 with 10GB RAM.
G.3.2. DATASET SPECIFIC DETAILS
Below, provide descriptions of the datasets which conduct experiments.
OGB datasets (MIT License) (Hu et al., 2020b). These are molecular property prediction datasets which use common node and edge featurization that represents chemophysical properties. MOLHIV, MOLBACE and MOLTOX21 all represent molccule classification tasks. We considered the challenging scaffold splits proposed (Hu et al., 2020a). We set the batch size to 128 for MOLHIV and 32 for the other benchmarks to avoid out-of-memory errors. set the hidden dimension be 300 for all datasets done in Hu al. (2020a) and Bevilacqua al. (2024). We tuned the number of layers 2, 4, 6, 8, 10, the number of layers post message-passing in 2, dropout after each layer in 0.0, 0.3, 0.5, whether perform mean or sum pooling over the subgraphs, and whether apply Batch Normalization after message--pssinng Additionally, for the method with structural encoding, we tune the number of steps i in the encoding in 16, 20 and the dimension after the linear encoding in 16, 28 as done in (Rampäšek et al., 2022). The tuning was done on single run for each set of random seeds. These parameters are shown Table
each dataset.
and the results were outlined for the best performing parameters on the validation set over
The maximum number of epochs is set 100 for all models and the metric computed at the best validation epoch.
Peptides-fune and Peptides-struct (CC-BY-NC 4.0) (Dwivedi al., 2022). These datasets composed of atomic peptides. Peptides-fuu coptides-func is multi-label graph classification task where there are 10 nonexclusive peptide functional classes. Peptides-struct is regression task involving 11 3D structural properties of the peptides. For both of these datasets, we used the tuned param--prsseters of the GINE model from Tönshoff et al. (Tönshoff et al., 2023) which has a parameter budget under 500k and where they use 250 epochs. For both of these datasets we set the number of steps of our centrality encoding to 20, aligned with the number steps used for the random- walk structural encoding. The additional parameter
32

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 18: Best performing hyperparameters Table
Hyperparameter
MOLHIV
MOLBACE
MOLTOX21
#1 aaers
2
10
#Layers readout
Hidden dim
300
300
300
Dropoui
0.5
0.3
Suhgraph pooling
Positional Encuding Steps
PE dim
16
16
28
&Parameters
419,403
1.691.329
2,061,322
tuning which we performed was whether do mean or sum pooling over the subgraphs. We show the best performing hyperparameters from Table in Table 19.
Table 19: Best performing hyperparameters Table
Hyperparameter
Peptides-Fund
Peptides-Strur
#Layers
8
10
#I Hayers readout
3
Hidden dim
160
145
Dropout
0.1
Subgraph paoling
Positional Encoding Steps
PE dim
18
18
#Parameters
498,904
107
ZINC (MIT License) (Dwivedi et al., 2023). This dataset consists of 12k molecular graphs representing commercially available chemical compounds. The task involves predicting the constrained solubility of the molecule. We considered the predefined dataset splits and used the Mean Absolute Error (MAE) both as a loss and evaluaton metric. We chose have 10 layers of maasage-passingg what was done in (Rampášek et al., 2022). We altered the hidden dimension be 148 in order to be closer to the 500k parameter budget. No further parameter tuning done and our best performing parameters are shown in Table 20. The test metric is computed at the best validation epoch.
layers in the readout function, a batch size of 32, 1000 epochs and a dropout of to replicate
Table 20: Best performing hyperparameters in Table 8.
Hyperparameter
ZINC
#Layers
layers rendont
Hidden dim
148
Dropout
Subgraph pooling
macun
Positional Encoding Steps
20
PE dim
18
#Parameters
497,353
MalNet- Faly (CC-BY license) This dataset comprises function call graphs derived from Android APKs. The dataset used is a subset of MalNet and contains 5, 000 graphs of up to 5, 000 nodes, coming from benign software types of malware. The task is classify the type of software based on its structure.
REDDIT-BINARY (CC-BY license) The dataset consists of social networks posts are connected by an edge if the same user comments on both. This dataset is large in size, containing 232,965 posts with an average degree of 429. The task is to predict whether the graph belongs to a question/amswer-baan the evaluation procedure proposed Xu et al. (2018), consisting of a 10-fold cross cross-validend validation and a metric with the best averaged validation accuracy across the folds.
community or a discussion- based community. We used
33

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 21: Best performing hyperparameters Table
Hyperparameter
MalNet-Tiny
e1 layers
#Layers readout
Hidden dim
96
Dropout
0.0
Suhgraph pooling
Positional Encoding Steps
PE dim
28
#Parameters
Table 22: Best performing hyperparameters Table
Hyperparameter
RDT-B
#1 #layeer
2
#Layers readout
1
Hidden dim
300
Dropout
D
Subgraph pooling
mean
Positional Encoding Steps
PE dim
274204
H. Additional Time Comparisons
As well as Table where we compared the runtime of different methods on Peptides datasets, we extend this analyses to both ZINC and MOLHIV, To this end, we provide some results Table 23 and Table 24. We find that our method significantly improves over the baseline GIN on both of these tasks whilst having substantially reduced runtime compared to the GPS which uses a Transformer layer. Again, this highlights both the efficiency and practical utility of our method.
34

---

Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
Table 23: Results the ZINC datasct with timing comparisons using GeForee RTX 2080 8 GB,
Method
Precompute
Train (slepach)
Test (4)
MAF
GIN
0.00
12.65
0.33
0.163
HyMN (GIN, T-1)
21.41
17.95
0.42
0.080
(Rampāšek (2022))
19.13
Table 24: Results on the MOLHIV dataset with timing comparisons using GeForce RTX 2080 8 GB.
Method
Precompute
Train (slepoch)
(4)
ROC-AUC (?)
GIN
0.00
7,50
0.33
75.58
HyMS (GIN, T=1)
67.43
9.09
0.37
80.36
GPS (Rampášek (2022))
35


Reviews:
[{"review_id": "hulde8en5C", "reviewer": "Reviewer_3dVz", "summary": "The paper proposes HyMN (Hybrid Marking Networks), a combination of walk-based structural encodings and centrality-based subgraph marking strategies. The goal is to design a subgraph GNN which is simultaneously effective (sampled bags tend to optimal) and efficient (few operations / no learnable components).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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*”.\n\nThe 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.\n\nEven *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).\n\nWe 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:\n\n|              | molhiv       | molbace      | moltox       |\n|--------------|--------------|--------------|--------------|\n| GIN+CSEs  | 77.44 ± 1.87 | 76.58 ± 2.29 | 75.81 ± 0.39 |\n| HyMN (GIN, T=2) | 81.01 ± 1.17   | 81.16 ± 1.21   | 77.30 ± 0.35 |\n\nWe hope this clarifies the raised concern. We would kindly ask the reviewer to reconsider their scores in view of our response.", "claims_and_evidence": "C1: Centrality Measures can be conceptualized as graph perturbations.\nE: Analysis based on Chuang/Jegelka Tree Mover paper. Experiments to support the hypothesis.\n\nC2: A combination of SE and Centrality Measures works well. \nE: Ablation proofs, in the sense that they extend 1-WL in incomparable ways. Experimental support for HyMN.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. The arguments seem correct.", "experimental_designs_or_analyses": "Yes. The experimental protocol are standard.", "relation_to_broader_scientific_literature": "The paper forms a solid contribution to the existing work on Subgraph Sampling. \nThe nice result of Chuang and Jegelka forms the real engine of the paper, though.", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "Strengths\n1) The paper is extremely well-written. The presentation is thorough. \n2) Even though the paper is a bit light on theory, the paper cherry-picks the right ideas and puts them together nicely: Experimental support is provided wherever necessary. It was quite comfortable to grasp the essential ideas behind the model. \n3) The idea of walk-centrality holds promise for spurring on further work in this area. \n\nWeaknesses\n1) The use of both SE and Centrality Subgraph Sampling really makes HyMN a bit of a Swiss knife. This is not really a criticism, but this weakens the claims for the effectiveness of Centrality Marking as a technique.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZQlHxm4pmM", "reviewer": "Reviewer_cmx7", "summary": "This paper explores subgraph GNNs as a way to overcome the expressivity limitations of standard Message Passing Neural Networks (MPNNs). In a subgraph GNN, a graph is transformed into a \"bag of subgraphs,\" where each subgraph is processed independently using an equivariant architecture, and the results are aggregated for final prediction. While these methods enhance expressivity, they suffer from high computational costs due to the large number of subgraphs that need to be processed.\n\nTo address this challenge, this paper proposes a hybrid subgraph selection and feature augmentation method. The key idea is to sample subgraphs centered around nodes with high Subgraph Centrality, which is a metric introduced in prior work that measures a node's importance based on walk-based connectivity patterns. Moreover, the paper introduces a feature augmentation technique that incorporates centrality scores as structural encodings.\n\nThe paper provides some theoretical analysis to support the use of Subgraph Centrality. In the experiments, the method overall matches or outperforms some other Subgraph GNNs and Graph Transformers on some benchmarks, and is more scalable.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*(W1) “The two experiments use very different types of graphs [...] it would be helpful to standardize.”*\n\nWe 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](https://anonymous.4open.science/r/HyMN-ICML-Rebuttal-8A82/1.png)) are consistent with our prior findings, and will be included in the new revision.\n\n---\n\n*(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.”*\n\nWe 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.\n\nAlthough our approach lacks optimality *guarantees*, it:\n- is theoretically grounded via the connection to perturbation analyses (found “interesting”);\n- leads to consistent empirical gains with contained overhead.\n\nAlso, 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.\n\n---\n\n*(W3) “The discussion on why structural motifs are desirable could be expanded.”*\n\nMotif 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.\n\nStarting 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.\n\n---\n\n*“[...] observation 1: why don't node features come into play?”*\n\nBecause 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.\n\n---\n\n*(W4) “[...] experiments [...] not including the other potentially relevant baselines. [...] POLICY-LEARN is omitted from Tables 3 and 4 [...]”*\n\nIn 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.\n\nEither 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:\n\n| | molhiv |\n|----|----|\n| Reconstr. GNN | 76.32±1.40 |\n| Nested-GNN | 78.34±1.86 |\n| DSS-GNN | 76.78±1.66 |\n| GNN-AK+ | 79.61±1.19 |\n| SUN | 80.03±0.55 |\n| HyMN (T=2) | 81.01 ±1.17 |\n\nHyMN competes with the best full-bag approaches with only two subgraphs.\n\nAs 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.\n\n| | molhiv | molbace |\n|----|----|----|\n| CS-GNN (T=2) | 77.72±0.76 | 80.58±1.04 |\n| HyMN (T=2) | 81.01 ±1.17 | 81.16 ±1.21 |\n| CS-GNN (T=5) | 79.09±0.90 | 79.64±1.43 |\n| HyMN (T=5) | 80.17 ±1.40 | 80.64 ±0.48 | \n\nPeptides, MalNet (Tables 3, 4): POLICY-LEARN was not originally evaluated thereon. We attempted this using the authors’ code.\n\nOn 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.\n\nOn Peptides, we obtained:\n| | peptides-func (AP ↑)  | peptides struct (MAE ↓) |\n|----|----|----|\n| POLICY-LEARN (T=1) | 0.6336 ±0.0071  | 0.2475 ±0.0008|\n| HyMN (T=1) | 0.6857 ±0.0055 | 0.2464 ±0.0013 |\n| POLICY-LEARN (T=2) | 0.6459 ±0.0018 | 0.2475 ±0.0011 |\n| HyMN (T=2) | 0.6863 ±0.0050 | 0.2457 ±0.0012 |\n\nWe finally refer to the response to Reviewer d9AX for additional results on Reddit-binary.\n\n---\n\nWe hope your concerns are clarified, while we are open to elaborate further.\n\n[1] https://arxiv.org/abs/2210.01906\n\n[2] https://arxiv.org/abs/2006.09252\n\n[3] https://arxiv.org/abs/2406.09291", "claims_and_evidence": "(S1) The authors claim that their method overcomes the expressive limitations of MPNNs while remaining scalable. Section 3.2 provides interesting progress toward substantiating these claims by establishing a connection between Subgraph Centrality and perturbation analysis. (However, I think this analysis could be refined/strengthened, as I describe in W1-W3 below.)\n\nSecond the paper claims that the proposed method outperforms other subgraph selection strategies and achieves performance comparable to or better than full-bag Subgraph GNNs while sampling only one or two subgraphs. I'm not fully convinced about this claim, as I elaborate on in (W4) below.\n\n(S2) Finally, the paper claims that the proposed approach is competitive with Graph Transformers and SOTA GNNs while being significantly more computationally efficient. I think this is reasonably substantiated by Tables 3 and 4.", "methods_and_evaluation_criteria": "Section 3.2 presents a combination of theoretical and empirical analyses to motivate the use of Subgraph Centrality. Observation 1 states that if a node has low centrality, training a GIN on its induced subgraph will have little impact on the GIN's prediction. The implication is that to improve expressivity, one should, at minimum, avoid selecting subgraphs centered around low-centrality nodes.\n\nNext, Section 3.2 presents two experiments:\n1. Selecting subgraphs based on high-centrality nodes leads to large variations in the GIN's predictions.\n2. Subgraphs centered on high-centrality nodes contain a higher prevalence of structural motifs, such as triangles and 4-cycles.\n\nHere are a few suggests for developing this section:\n\n(W1) The two experiments use very different types of graphs---real world TU datasets for the first and Erdos-Reyni for the second. It's not clear why there is this discrepancy and it would be helpful to standardize.\n\n(W2) While the theoretical results rule out low-centrality nodes as good candidates, they don't strongly establish that choosing high-centrality nodes is necessarily optimal. This makes this analysis interesting but not entirely conclusive.\n\n(W3) The discussion on why structural motifs are desirable could be expanded. The paper states that the “presence and number of strucutral ‘motifs’ are often related to graph-level tasks” but this doesn't explain why subgraphs with more motifs are desirable for improving GNN performance.", "theoretical_claims": "I have a question about observation 1: why don't node features come into play?", "experimental_designs_or_analyses": "(W4) The paper introduces many related subgraph GNN methods in its citations, but the experiments primarily compare the proposed method against POLICY-LEARN, not including the other potentially relevant baselines. Additionally, POLICY-LEARN is omitted from Tables 3 and 4, while it is included in other results. It would be helpful to provide a more comprehensive evaluation or explain why methods were omitted.", "relation_to_broader_scientific_literature": "I think this paper would be of interest to the community interested in GNN expressivity, but I think the weaknesses I presented should be addressed first.", "essential_references_not_discussed": "None that I'm aware of.", "other_strengths_and_weaknesses": "None beyond those I described above.", "other_comments_or_suggestions": "None.", "questions_for_authors": "Can you please address weaknesses (W3) and (W4)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bJITjAeth3", "reviewer": "Reviewer_Rq9u", "summary": "The authors propose a centrality-based scheme for selecting expressive subgraphs for subgraph GNNs. Essentially, their idea is based on the observation that message passing themes and walks on graphs are the same thing, which makes using walk-based centralities a natural proxy for selecting nodes with high influence on the learning process of GNNs. The authors evaluate their approach on synthetic (Erdős–Rényi random graphs) and real-world graphs and demonstrate that their approach outperforms subgraph-GNN-based and transformer-based baselines both in terms of performance and runtime.\n\n## update after rebuttal\nAs mentioned during the rebuttal period, I am satisfied with the authors' responses and planned revisions to the manuscript. Hence, I maintain my score which I updated during the rebuttal period.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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*”.\n\nThe reviewer had a clarity concern pertaining to tackled tasks and result interpretation, along with some questions. We address these points in the following.\n\n---\n\n*“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 [...]”*\n\nSubstructure 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*.\n\nEventually, 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.\nAs for results reported in Table 2 – yes, we confirm all the three benchmarks involve graph classification. We will make sure to state this clearly.\n\n---\n\n*“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?”*\n\nYes, this is correct. As long as the centrality measure ranks all the nodes in a graph, the method can be run without any caveat.\n\nRegarding 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.\n\n---\n\n*“Why is there a difference between degree centrality and PageRank in Figure 3? [...]”*\n\nWhile 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.\n\n---\n\n*”What is the reason for the missing values in Table 2?”*\n\nWe 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.\n\n---\n\n*”[...] 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.”*\n\nThis 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.", "claims_and_evidence": "The claims made by the authors are supported by clear arguments and empirical evidence.", "methods_and_evaluation_criteria": "I believe that the chosen evaluation datasets and measures are sufficient for supporting the authors' claims. As they point out, their approach focuses on learning graph representations with the intention to provide a basis for various downstream tasks.", "theoretical_claims": "I find that the authors' arguments are clearly formulated and convincing. I have read the proofs in appendix D and did not find any obvious issues, however, I am not trained as a mathematician and may have missed more involved subtleties.", "experimental_designs_or_analyses": "The experimental setup seems sound. However, I find that the authors should be more explicit regarding how the results of their evaluation should be interpreted. Specifically, 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? Obviously a higher correlation is better, but what results do we expect? And what results does their proposed method return? Also, based on the datasets used in Table 2, I guess that the considered task is graph classification, I think it would be better to state the considered task explicitly in the text.", "relation_to_broader_scientific_literature": "As the authors point out, current subgraph GNNs suffer from computational challenges when they consider full bags of subgraphs and, therefore, are limited to applications involving very small graphs. While the network science community has long considered walk-based measures as an extremely useful tool, I am happy to see that they are now also finding broader adoption in the deep learning community.", "essential_references_not_discussed": "I am not aware of any essential references that the authors have missed to include.", "other_strengths_and_weaknesses": "I find the paper extremely well written. The authors' arguments are clearly laid out. They are guiding the reader by asking and answering relevant questions on the reader's behalf. Overall, I found it enjoyable to read the paper.", "other_comments_or_suggestions": "I found the explanation regarding what effectiveness and efficiency are (Section 3.1, paragraph \"Goal\") very intuitive.", "questions_for_authors": "1. Are there any limitations regarding what kinds of graphs the proposed approach can be applied to? For example, do the graphs need to be connected or undirected? What about disconnected graphs or directed graphs that are only weakly connected? Or is the only requirement that the chosen centrality measure must be able to assign centrality scores to all nodes?\n2. Why is there a difference between degree centrality and PageRank in Figure 3? In undirected graphs, the two should select the same nodes as the most central. Is the difference only due to the randomness in the initialisation of GNN weights?\n3. What is the reason for the missing values in Table 2?\n4. The paper title mentions \"balancing efficiency and expressiveness\", but I am wondering to what extent it can actually be claimed that the subgraph centrality addresses the expressiveness goal? 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? My intuition tells me that this should be the case -- and I might be wrong with that. But given the relatively small number of chosen nodes in the empirical experiments, 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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OpzuYEQ3q5", "reviewer": "Reviewer_d9AX", "summary": "This paper proposes a technique to reduce the computational complexity of subgraph-GNNs, which have higher expressivity than 1-WL but are often too computationally expensive to be used in practice. In particular, the method, called HyMN, relies on sampling subgraphs based on some node centralities, which can also be used as a structural encoding, akin to the RWPE. Experiments showcase the applicability of the prosed method, showing that the proposed method obtains a predictive performance that is comparable or better compared to full-bag subgraph GNNS, while having a significantly lower time complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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*\".\n\nWe address comments below.\n\n---\n\n*“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.”*\n\nIn 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.\n\nOverall, 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.\n\n---\n\n*“The subgraph centrality structural encoding proposed in the paper is simply a rescaling of the RWPE, [...] This maybe should be stated more clearly.”*\n\nWe acknowledge the similarity between RWSEs and CSEs. In fact, we devote Section F.4 to discuss their relation. \n\nProposing 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.\n\n---\n\n*“The baseline of GIN + CSE should be added to the experiments on ogb data.”*\n\nWe agree. We conducted these experiments during the rebuttal period and report the results below:\n\n|              | molhiv       | molbace      | moltox       |\n|--------------|--------------|--------------|--------------|\n| GIN+CSEs  | 77.44 ± 1.87 | 76.58 ± 2.29 | 75.81 ± 0.39 |\n| HyMN (GIN, T=2) | 81.01 ± 1.17   | 81.16 ± 1.21   | 77.30 ± 0.35 |\n\nThese results support the effectiveness of our centrality-based strategy. We will include them in Table 2.\n\n---\n\n*“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.”*\n\nWe 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.\n\nThat 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:\n\n| Method                  | RDT-B Accuracy |\n|-------------------------|-----------------|\n| GIN  | 92.4 ± 2.5      |\n| FULL                    | OOM             |\n| RANDOM (T=20)           | 92.6 ± 1.5      |\n| RANDOM (T=2)            | 92.4 ± 1.0      |\n| POLICY-LEARN (T=2)      | 93.0 ± 0.9      |\n| HyMN (T=2)         |  93.2 ± 2.2 |\n\nHyMN 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.\n\n[1] https://arxiv.org/abs/1810.00826\n\n---\n\n*“It would be useful to have a figure to illustrate node-marking-based Subgraph GNNs, with and without a subsampling approach like HyMN.”*\n\nThanks for the suggestion – we have accordingly prepared a figure currently hosted at [this](https://anonymous.4open.science/r/HyMN-ICML-Rebuttal-8A82/2.png) anonymous link. We plan to add it in the next paper revision (Section B).\n\n---\n\n*“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 [...] ?”*\n\nThis 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.\n\n---\n\nWe hope our responses clarify the raised concerns. We would kindly ask the reviewer to reconsider their scores in view of them.", "claims_and_evidence": "The (few) theoretical results on expressivity are correct. The experimental results are backed up by publicly available code.", "methods_and_evaluation_criteria": "The proposed method to select the marked subgraphs for Subgraph GNNs is reasonable and effective, and motivated by some experimental results in section 3.2. However, there is a discrepancy between these observations and the proposed method itself (see W1). \n\nThe 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. The results substantiate the validity of the method.", "theoretical_claims": "The (few) theoretical results on expressivity (Thm 4.1 and 4.2) seem to be correct.", "experimental_designs_or_analyses": "Apart from the lack of a diverse selection of real-world datasets, the experimental methodology is sound. The authors provide results on both synthetic and real-world datasets, they provide confidence intervals, and code for reproducibility.", "relation_to_broader_scientific_literature": "The proposed method seems to produce accuracies on par with subgraph GNNs that consider all subgraphs, at a fraction of the cost. This is an important advance in the field, which was hindered by computational costs. Moreover, the proposed method is simple to implement, which would make it easier to be used by practitioners and to be improved upon by further research.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n1) the proposed method seems to produce accuracies on par with subgraph GNNs that consider all subgraphs, at a fraction of the cost. This is an important advance in the field, which was hindered by computational costs. Moreover, the proposed method is simple to implement, which would make it easier to be used by practitioners and to be improved upon by further research.\n2) the paper is well-written and very well motivated. The observations on which node makings impact the most the GNN output and the subsequent exploitation of these observations make for a compelling story that makes it easy to follow the paper. \n\nWeaknesses:\n1) There seems to be a large discrepancy between the motivating observations and experiments of Section 3.2, and the proposed method itself. Indeed, in the section it is observed that, given a graph G, marking the node with highest walk-based centralities and obtaining a single graph G’ yields the highest change in the GNNs output |f(G) - f(G’)|. This however does not align with subgraph GNNs, where the graph is transformed into a bag of transformed (sub)graphs. I understand that one might want to diversify the embeddings of each of the subgraphs in the bag, and this could be the motivation for your choice, but this should be discussed explicitly in the manuscript. \n2) The subgraph centrality structural encoding proposed in the paper is simply a rescaling of the RWPE, and can hardly be considered a contribution. This maybe should be stated more clearly. \n3) The baseline of GIN + CSE should be added to the experiments on ogb data.\n4) 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.  \n\nThe paper, although somewhat incremental, seems to be solid and impactful, and it can be considered for acceptance.", "other_comments_or_suggestions": "1) It would be useful to have a figure to illustrate node-marking-based Subgraph GNNs, with and without a subsampling approach like HyMN.\n\nRemark: I’d be open to raising my score (which is anyway mostly positive) if all my concern are properly addressed.", "questions_for_authors": "Most real word datasets, especially molecular ones, don't really require expressive power higher than 1-WL, see for example Table 2 in [WL meet VC, ICML'23] or Table 2 in [Graph Neural Networks Can (Often) Count Substructures, ICLR'25]. Do you have an intuitive explanation on why Subgraph GNNs nonetheless show higher predictive performance compared to simpler baselines? It would be interesting to discuss this in the paper.\n\n.\n-----\n### Update\nI believe that during the rebuttal the paper has improved (e.g., new experiments, intuitive figures, and a stronger motivation). Therefore, I raised my score to 4 to suggest acceptance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a technique to accelerate Subgraph GNNs by incorporating walk-based centrality metrics to guide the subgraph sampling process. The approach includes a preprocessing step involving the computation of subgraph centrality scores, selection of the top‑T nodes, generation of structural encodings, and marking of these nodes for use in a full-graph GNN, all without explicit subgraph extraction.

During the rebuttal phase, the authors significantly improved their results in several ways, including additional experiments with the MolHIV dataset, GIN + CSE, the Reddit-Binary (RDT-B) dataset, and simple substructure counting experiments to clarify the impact of sampling node-marked subgraphs with minimal Subgraph Centrality (SC) values. All these additions significantly reinforced the claims and value.

There are three (in my opinion minor) limitations worth noting. First, the novelty may appear limited, given the incremental nature of the proposed approach. Second, the combination of subgraph sampling and structural features makes it difficult to isolate the key factors responsible for performance gains (although this was also partially clarified in the rebuttal). Finally, while selecting nodes with the highest centrality clearly outperforms random or low-centrality choices, the method still retains a heuristic flavor.

However, the contribution is notable, and the benefits clearly outweigh these concerns. The paper makes a solid contribution, and I thus recommend it be accepted.
Decision: Accept (poster)