Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

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

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Marking only the one or two most walk-central nodes makes Subgraph GNNs match — and sometimes beat — full-bag models and stronger baselines at a small fraction of the runtime.

desk verdict A practical, well-tested subsampling scheme for Subgraph GNNs whose core intuition is supported empirically; the theoretical story is thinner than the abstract suggests, and the specific choice of Subgraph Centrality is not fully pinned down. read the letter →

arxiv 2501.03113 v2 pith:WNXGVEOK submitted 2025-01-06 cs.LG cs.NE

Joshua Southern , Yam Eitan , Guy Bar-Shalom , Michael Bronstein , Haggai Maron , Fabrizio Frasca This is my paper · ORCID
classification cs.LGcs.NE MSC 68T07
keywords SubgraphGNNsCentralitywalk-basedsamplingstructuralencodingsgraphexpressivenessnodemarkingscalablelearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Subgraph GNNs gain expressive power over plain message passing by processing one subgraph per node, but the bag grows linearly in node count, making the model quadratic in cost. This paper argues that the whole bag is unnecessary: marking only the top-ranked nodes by Subgraph Centrality — a walk-based score counting closed walks through each node — leaves one or two marked subgraphs able to match, and sometimes beat, a full-bag Subgraph GNN on real-world benchmarks. The same walk counts, fed in as per-node structural encodings, recover discriminative power the marking alone does not provide. The strategy is supported by a perturbation bound showing marking shifts a message-passing representation in proportion to the number of walks leaving the marked node, and by experiments showing high-centrality marking produces the largest perturbations and the ones most correlated with substructure counts. If the claim is right, the main obstacle to Subgraph GNNs on large graphs — their quadratic cost — is removable with a cheap preprocessing step and no learned sampling.

What carries the argument

The central object is Subgraph Centrality, $\mathrm{SC}_v=\sum_{k\ge 0}(A^k)_{vv}/k!$, the discounted number of closed walks of every length through node $v$. It carries the argument twice over: as the sampling score, the top-$T$ nodes it ranks are the ones marked, with the paper's bound tying marking-induced perturbation to the number of walks leaving the marked node; and as the structural encoding, its addenda $(A^k)_{vv}/k!$ (proportional to degree at $k=2$, incident triangles at $k=3$) are concatenated onto node features as the CSE. The connection between a bound that counts all walks and a score that counts only closed walks is bridged empirically in Section 3.2. The engineering trick that makes the method cheap is that the bag of subgraphs is never materialized: marks live in a feature tensor processed by a custom equivariant message function, so memory and runtime scale with $T$, not $N$.

What would settle it

A concrete test: construct a graph pair in which the highest-SC node is a task-irrelevant universal hub and the distinguishing substructure lies entirely on low-SC nodes. If HyMN with $T=1$ cannot separate the pair while random marking averaged over seeds can, then the SC ranking — not the marking paradigm — is the load-bearing component; likewise, across real datasets, HyMN's gain over random sampling of equal bag size should track the rank correlation between SC-induced perturbations and task-relevant substructure counts, and a dataset where gain persists at near-zero correlation would refute the stated mechanism.

Watch

Extended reading notes

Core claim

HyMN's central claim is that Subgraph Centrality, $\mathrm{SC}_v=\sum_{k\ge 0}(A^k)_{vv}/k!$, identifies the subgraphs whose inclusion in a node-marking bag matters most, so the bag can be cut from $N$ subgraphs to a fixed small number $T$ by marking the $T$ highest-scoring nodes. The paper justifies the choice in two steps: a perturbation bound (Observation 1) shows that adding a marked subgraph changes an MPNN's output by at most a quantity growing with the total number of walks from the marked node, and experiments on MUTAG, NCI1, and random graphs show that max-SC marking yields the largest representation changes, with perturbation magnitudes most correlated with triangle, 4-cycle, path, and star counts (Pearson correlations around 0.95). Because Subgraph Centrality itself counts only closed walks while the bound counts all walks, the paper treats the alignment as an empirical finding. On the architectural side, HyMN augments node features with Centrality-based Structural Encodings, the power-series addenda $(A^k)_{vv}/k!$, and proves via two incomparability theorems that CSE-enhanced MPNNs and top-SC-subsampled Subgraph GNNs each separate graph pairs the other cannot, so the hybrid strictly extends both. Empirically, HyMN with $T=1$ or $2$ matches or beats full-bag Subgraph GNNs, the learned Policy-Learn policy, and several Graph Transformer baselines on OGB, ZINC, Peptides, MalNet-Tiny, and Reddit-Binary, at a fraction of their runtime.

Load-bearing premise

The method load-bears on the assumption that the nodes with the most closed walks are exactly the nodes whose marking perturbs message-passing representations in ways aligned with task-relevant substructure counts — an alignment demonstrated empirically on synthetic and small real graphs, but not proven for the larger real benchmarks.

Editorial extensions

If this is right

  • Subgraph GNNs become applicable to graphs tens to hundreds of times larger than full-bag methods can process, because runtime and memory now scale with a fixed bag size ($T=1$ or $2$) instead of the node count.
  • On the OGB molecular benchmarks the method beats the full-bag Subgraph GNN and the learned Policy-Learn policy at equal bag size — MOLHIV reaches 81.01 ROC-AUC with $T=2$ — and matches Policy-Learn even without the centrality encodings.
  • On Peptides, MalNet-Tiny, and Reddit-Binary, HyMN ties or beats Graph Transformers and higher-order GNN baselines while being about six times faster in wall-clock training and inference on MalNet-Tiny.
  • Because CSE-augmented MPNNs and top-SC-subsampled Subgraph GNNs are provably incomparable in expressive power (Theorems 4.1 and 4.2), the hybrid strictly extends what either ingredient delivers alone.
  • In substructure-counting tasks, sampling the top-SC subgraphs reaches near-zero test error on triangles with far fewer subgraphs than random or min-centrality sampling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the paper's results suggest the expressive content of a node-marking bag concentrates in a few diagnostic nodes, so similar top-$k$ selection with other cheap scores (motif counts, spectral centrality) could transfer to subgraph architectures beyond node marking.
  • Editorial extension: Observation 1 bounds perturbation by total walks leaving the marked node, while Subgraph Centrality counts only closed walks; a Katz-style total-walk score matching the bound exactly could outperform SC precisely on graphs where open and closed walk counts diverge.
  • Editorial extension: since CSEs are closed-walk counts up to length $K$, task sensitivity to long cycles should track the required $K$; tuning $K$ per dataset instead of fixing it could open a further accuracy-efficiency trade-off.
  • Editorial extension: HyMN's fixed bag is deterministic, which removes variance at the cost of exploration; a natural variant would mark top-SC nodes deterministically and add a few random marks when the centrality ranking is flat, since the paper notes that ties in centrality must sometimes be broken arbitrarily.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes HyMN, a method for scaling Subgraph GNNs by sampling a small number of node-marked subgraphs according to walk-based centrality, specifically Subgraph Centrality (SC), and by augmenting node features with Centrality-based Structural Encodings (CSE). The authors provide a perturbation analysis (Observation 1, Eq. (3)) linking marking-induced representation changes to walk counts, two expressiveness results (Theorems 4.1 and 4.2) on the non-comparability of CSE-augmented MPNNs and subsampled Subgraph GNNs, and a broad experimental evaluation on synthetic substructure-counting tasks, OGB molecular benchmarks, Peptides, MalNet-Tiny, Reddit-Binary, and ZINC. The experiments show that HyMN matches or exceeds the performance of full-bag Subgraph GNNs and learnable sampling policies while using only one or two marked subgraphs, at substantially reduced runtime.

Significance. If the claims hold, HyMN addresses a central scalability bottleneck of Subgraph GNNs, whose bag size grows linearly with graph size, and demonstrates that a simple, non-learnable preprocessing step can match or outperform learned sampling policies. The empirical work is a clear strength: the paper includes reproducible code, timing comparisons across multiple datasets, ablations on the effect of CSEs, comparisons with several centrality measures, and evaluations on graphs with up to thousands of nodes. The theoretical results, however, currently contain a serious defect in the proof of Theorem 4.1 that undermines one of the two expressiveness arguments, and the evidence for the specific choice of SC over other walk-based centralities is weaker than the text suggests. With the proof repaired and the centrality claims appropriately calibrated, the paper would be a solid contribution to efficient and expressive graph learning.

major comments (2)
  1. [Section 4.2 / Appendix D (Theorem D.2, proof of Theorem 4.1)] The proof of Theorem 4.1 contains two invalid steps. First, it states that the graphs Qt15 and Qt19, being 4-regular and of the same size, are 1-WL indistinguishable. This implication is false in general, and no specific justification is given for this particular pair. Second, the proof claims that 'the degree histogram in the 1-hop neighborhood of any node differs between the two graphs'; this is also incorrect because both graphs are 4-regular and vertex-transitive, so every node in both graphs has degree 4 and all its neighbors have degree 4, making these histograms identical. Consequently, the proof does not establish the theorem. Since Theorem 4.1 is one of the two non-comparability results used to motivate the hybrid combination of CSEs and subsampled marking, this is a load-bearing flaw. The authors should either provide a correct proof with a rigorously verified pair of graphs (including a demonstration of 1-WL indistinguishability and a valid distinguishing mechanism for the marked Subgraph GNN) or remove/restate the theorem with an appropriate caveat.
  2. [Section 3.2, Eq. (3), Tables 12 and 14] The theoretical anchor for choosing Subgraph Centrality is Observation 1 / Eq. (3), which upper-bounds the marking-induced perturbation by the row-sum walk count S_l = Σ_j (A^{l-1})_{v,j}. Subgraph Centrality, however, is defined in Eq. (1) via the closed-walk diagonal entries (A^k)_{vv}. The paper explicitly acknowledges this gap in Section 3.2 and bridges it with empirical correlations in Table 1 on 100 synthetic ER graphs. The real-world evidence, however, does not single out SC: Table 14 shows that the Katz Index (a row-sum centrality) performs within one standard deviation of SC on MolHIV, Peptides-Func, and Peptides-Struct, and Table 12 shows that all three walk-based centralities (Katz, Communicability, SC) induce nearly identical average perturbations on MUTAG and NCI1. The statements in Section 3.2 that 'the walk-based SC stands out as a particularly promising candidate' and that SC 'performed as the best one' are therefore overstated. The evidence supports the broader family of walk-based centralities rather than the specific closed-walk form. The authors should temper the SC-specific claims, report significance tests or effect sizes for the Table 14 differences, and discuss the interchangeability of walk-based centralities, or provide a direct theoretical reason for preferring closed-walk counts over row-sum counts.
minor comments (4)
  1. [Section 1 (Introduction)] The final sentence of Section 1 contains a typo: 'empirirical run-times' should be 'empirical run-times'.
  2. [Section 4.2 / Appendix D (Theorem D.2)] There is a mismatch between the statement of Theorem 4.1 in the main text, which says 'top-1 Subgraph Centrality policy', and the appendix Theorem D.2, which says 'top-k Subgraph Centrality policy'. The proof appears to address only the top-1 case; if a top-k version is claimed, its proof should be given explicitly, or the theorem statement should be aligned.
  3. [Equation (1)] The convergence condition for Subgraph Centrality is not made precise. The text writes '0 < α < 1/λ1, β > 0' but does not state the corresponding condition for β (for the exponential series with β=1, convergence holds for all finite graphs; a clarifying sentence would help).
  4. [Algorithm 1] The algorithm computes CSE and estimates SC using a truncated sum over K terms, but the paper does not analyze the effect of the truncation on the top-k selection. A brief comment or sensitivity experiment on K would strengthen the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sampling rule is a fixed, label-free function of the adjacency matrix and the paper explicitly tests rather than assumes the link between the perturbation bound and Subgraph Centrality.

full rationale

The central derivation is not circular. Observation 1/Eq. (3) bounds marking-induced perturbation by row-sum walk counts; the paper does not claim this bound equals Subgraph Centrality. It explicitly states that the bound “only suggests, but does not necessarily entail” that high-SC nodes give the largest perturbations, and bridges the gap with external empirical correlations (Figure 1, Table 1) and with benchmark results. SC and CSE are computed directly from powers of A (Eqs. (1), (4)) with no fitting to labels or to the authors' own constants, so the top-k rule is not a fitted parameter renamed as a prediction. The expressiveness theorems (4.1, 4.2, D.2–D.5) are proved with explicit pairs of graphs and explicit weight constructions, including an independent use of known cospectral vertex-transitive graphs; the propositions citing the authors' earlier DSS-GNN framework are constructive and not load-bearing for the empirical claims. Self-citations (Bevilacqua et al. 2021; Frasca et al. 2022; Bar-Shalom et al. 2024b) appear only as background, baselines, or architectural context. The limitation noted in Section 6 (sampling ignores already-sampled subgraphs) and Appendix E's deferred choice among centrality measures weaken the theoretical justification of SC as the unique optimal selector, but they are correctness or risk concerns, not circularity. The method is benchmarked against external datasets (OGB, ZINC, Peptides, MalNet, Reddit), so performance claims do not reduce to the paper's own equations.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No target-derived constants are fit; SC and CSE are computed from the adjacency matrix. The main free choices are T and K, tuned per dataset. The theoretical results rely on standard WL and MPNN facts plus one incompletely justified WL-equivalence step.

free parameters (3)
  • Bag size T = 1, 2, 5, or 20 depending on experiment
    Number of top-centrality nodes marked; chosen per dataset and experiment, not fitted to labels, but determines the cost-performance tradeoff.
  • CSE walk length K = 16 or 20, with PE dim 16, 18, or 28
    Truncation order of the closed-walk power series; tuned per dataset via validation and affects both the features and the centrality estimate.
  • Subgraph centrality discount beta = 1
    Fixed default from Estrada and Rodriguez-Velazquez; not tuned, but is a chosen constant in the definition of SC.
assumptions (5)
  • standard math Universal approximation of MLPs for continuous functions on compact sets (Hornik 1991, Cybenko 1989)
    Used in Proposition D.1 to claim an MPNN can compute normalized closed-walk probabilities.
  • standard math Tree Mover's Distance stability bounds from Chuang and Jegelka (2022), Theorem 8 and Proposition 11
    Used to derive Observation 1, Equation (3).
  • standard math 1-WL indistinguishability of the specific graph pairs used in Theorems 4.1 and 4.2
    The proof of D.2 infers WL equivalence from 4-regularity and equal size, which is not generally valid; the theorem needs a specific proof for Qt15 and Qt19.
  • domain assumption DS-GNN architecture with an augmented bag containing an unmarked copy and independent message passing is the reference model
    Equations (45) to (48) define the architecture; expressiveness and sampling results are stated for this family, not for all subgraph GNN variants.
  • domain assumption Marking-induced perturbation correlated with substructure counts is a good proxy for task-relevant information
    Section 3.2 uses this assumption to justify sampling; it is empirically motivated on ER graphs, not proven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality." pith.science (2026). https://pith.science/paper/WNXGVEOK

@misc{pith2026250103113,
  author       = {Pith},
  title        = {Pith review of: Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WNXGVEOK}},
  note         = {Machine review of arXiv:2501.03113}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2501.03113 by the authors.

Figure 1
Figure 1. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An overview of the pipeline for HyMN. We calculate the CSE for each node, sample T node-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 k = 2, 3. These considerations suggest retaining the intermediate values that contribute to the SC of each node, and empl… view at source ↗
Figure 3
Figure 3. Comparing sampling approaches for counting triangles (performance metric is Mean Absolute Error, the lower the better). The average graph size is 59.33, corresponding to the average bag-size of a full-bag Subgraph GNN. shows that this approach does not subsume CSE-enhanced MPNNs: Theorem 4.2. There exists a pair of graphs G and G′ such that for any Subgraph GNN model Msub. which uses a top-1 Subgraph Centrality poli… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Depiction of a Subgraph GNN endowed with a subgraph sampling strategy. B.2. Computational Complexity Aspects Consider a Subgraph GNN f in the form of Equation (5), where S stacks neural message-passing layers. For an input graph G with n nodes and a degree bounded by d…
Figure 5
Figure 5. Figure 5: Two quartic vertex transitive graphs which cannot be distinguished with MPNN + CSE but can be distinguished with a Subgraph GNN with a top-1 Subgraph Centrality policy [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]
Figure 6
Figure 6. 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 a hexagon with a global node connected to all other nodes, and another graph which depicts two triangl…
Figure 7
Figure 7. 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) a random marking for both the NCI1 dataset (left) and Erdos-Renyi graphs (right). ¨ F. Ad…
Figure 8
Figure 8. Figure 8: Comparing different centrality measures for counting different substructures on synthetic random graphs [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. 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 = (A, X, E) 12 associated with node…
Figure 10
Figure 10. Figure 10: Evaluating the dependency between the graph size and the number of 4-cycles in the dataset generated from Chen et al. (Chen et al., 2020). G.3.1. HARDWARE All experiments were run on a single NVIDIA GeForce RTX 3080 with 10GB RAM. G.3.2. DATASET SPECIFIC DETAILS Below…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the Expressive Power of Permutation-Equivariant Weight-Space Networks

    cs.LG 2026-02 conditional novelty 7.0 of 10

    Permutation-equivariant weight-space networks are all equally expressive, and universality holds when hidden-layer biases are pairwise distinct.

Reference graph

Works this paper leans on

79 extracted references · 52 canonical work pages · cited by 1 Pith paper

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    \.I ., Grohe, M., and Lukasiewicz, T

    Abboud, R., Ceylan, \.I . \.I ., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence ( IJCAI ) , 2021

    work page 2021

  3. [3]

    u ck, F., K \

    Arvind, V., Fuhlbr \" u ck, F., K \" o bler, J., and Verbitsky, O. On W eisfeiler- L eman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113: 0 42--59, 2020

    work page 2020

  4. [4]

    Subgraphormer: Unifying subgraph gnns and graph transformers via graph products

    Bar-Shalom, G., Bevilacqua, B., and Maron, H. Subgraphormer: Unifying subgraph gnns and graph transformers via graph products. In Forty-first International Conference on Machine Learning, 2024 a

    work page 2024

  5. [5]

    A flexible, equivariant framework for subgraph gnns via graph products and graph coarsening

    Bar-Shalom, G., Eitan, Y., Frasca, F., and Maron, H. A flexible, equivariant framework for subgraph gnns via graph products and graph coarsening. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp.\ 101168--101222. Curran Associates, Inc., 2024 b

    work page 2024

  6. [6]

    and Klymko, C

    Benzi, M. and Klymko, C. Total communicability as a centrality measure. Journal of Complex Networks, 1 0 (2): 0 124--149, 2013

    work page 2013

  7. [7]

    On the limiting behavior of parameter-dependent network centrality measures

    Benzi, M. and Klymko, C. A matrix analysis of different centrality measures. arXiv preprint arXiv:1312.6722, 2014

    work page Pith review arXiv 2014

  8. [8]

    M., and Maron, H

    Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2021

    work page 2021

Show all 79 references
  1. [9]

    Efficient subgraph gnns by learning effective selection policies

    Bevilacqua, B., Eliasof, M., Meirom, E., Ribeiro, B., and Maron, H. Efficient subgraph gnns by learning effective selection policies. In The Twelfth International Conference on Learning Representations, 2024

    2024

  2. [10]

    Biewald, L. et al. Experiment tracking with weights and biases, 2020

    2020

  3. [11]

    F., and Bronstein, M

    Bodnar, C., Frasca, F., Otter, N., Wang, Y., Lio, P., Montufar, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34: 0 2625--2640, 2021 a

    2021

  4. [12]

    F., Lio, P., and Bronstein, M

    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, 2021 b

    2021

  5. [13]

    P., and Bronstein, M

    Bouritsas, G., Frasca, F., Zafeiriou, S. P., and Bronstein, M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022

    2022

  6. [14]

    and Laurent, T

    Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017

    2017 arXiv

  7. [15]

    Brouwer, A. E. and Spence, E. Cospectral graphs on 12 vertices. the electronic journal of combinatorics, pp.\ N20--N20, 2009

    2009

  8. [16]

    Can graph neural networks count substructures? Advances in neural information processing systems, 33: 0 10383--10395, 2020

    Chen, Z., Chen, L., Villar, S., and Bruna, J. Can graph neural networks count substructures? Advances in neural information processing systems, 33: 0 10383--10395, 2020

    2020

  9. [17]

    and Jegelka, S

    Chuang, C.-Y. and Jegelka, S. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. Advances in Neural Information Processing Systems, 35: 0 2944--2957, 2022

    2022

  10. [18]

    Reconstruction for powerful graph representations

    Cotta, L., Morris, C., and Ribeiro, B. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34: 0 1713--1726, 2021

    2021

  11. [19]

    Approximation by superpositions of a sigmoidal function

    Cybenko, G. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2 0 (4): 0 303--314, 1989

    1989

  12. [20]

    Dupty, M. H. and Lee, W. S. Graph representation learning with individualization and refinement. arXiv preprint arXiv:2203.09141, 2022

    2022 arXiv

  13. [21]

    Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021

    2021

  14. [22]

    P., Luu, A

    Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021

    2021

  15. [23]

    P., Ramp \'a s ek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A

    Dwivedi, V. P., Ramp \'a s ek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. Advances in Neural Information Processing Systems, 35: 0 22326--22340, 2022

    2022

  16. [24]

    P., Joshi, C

    Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 0 (43): 0 1--48, 2023

    2023

  17. [25]

    and Rodriguez-Velazquez, J

    Estrada, E. and Rodriguez-Velazquez, J. A. Subgraph centrality in complex networks. Physical Review E, 71 0 (5): 0 056103, 2005

    2005

  18. [26]

    and Weber, M

    Fesser, L. and Weber, M. Effective structural encodings via local curvature profiles. In The Twelfth International Conference on Learning Representations, 2024

    2024

  19. [27]

    and Lenssen, J

    Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric. ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds, 2019

    2019

  20. [28]

    Understanding and extending subgraph gnns by rethinking their symmetries

    Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35: 0 31376--31390, 2022

    2022

  21. [29]

    Freeman, L. C. A set of measures of centrality based on betweenness. Sociometry, pp.\ 35--41, 1977

    1977

  22. [30]

    Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. In Vanschoren, J. and Yeung, S. (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, volume 1, 2021

    2021

  23. [31]

    and Reutter, J

    Geerts, F. and Reutter, J. L. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2023

    2023

  24. [32]

    S., Riley, P

    Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International conference on machine learning, pp.\ 1263--1272. PMLR, 2017

    2017

  25. [33]

    N., Duvenaud, D., Hern \'a ndez-Lobato, J

    G \'o mez-Bombarelli, R., Wei, J. N., Duvenaud, D., Hern \'a ndez-Lobato, J. M., S \'a nchez-Lengeling, B., Sheberla, D., Aguilera-Iparraguirre, J., Hirzel, T. D., Adams, R. P., and Aspuru-Guzik, A. Automatic chemical design using a data-driven continuous representation of mol...

    2018

  26. [34]

    A new model for learning in graph domains

    Gori, M., Monfardini, G., and Scarselli, F. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp.\ 729--734 vol. 2, 2005. doi:10.1109/IJCNN.2005.1555942

    2005

  27. [35]

    J., and Schult, D

    Hagberg, A., Swart, P. J., and Schult, D. A. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008

    2008

  28. [36]

    A generalization of vit/mlp-mixer to graphs

    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

    2023

  29. [37]

    Approximation capabilities of multilayer feedforward networks

    Hornik, K. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 0 (2): 0 251--257, 1991

    1991

  30. [38]

    Graph policy network for transferable active learning on graphs

    Hu, S., Xiong, Z., Qu, M., Yuan, X., C \^o t \'e , M.-A., Liu, Z., and Tang, J. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 33: 0 10174--10185, 2020 a

    2020

  31. [39]

    Open graph benchmark: Datasets for machine learning on graphs

    Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33: 0 22118--22133, 2020 b

    2020

  32. [40]

    Strategies for pre-training graph neural networks

    Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020 c

    2020

  33. [41]

    Boosting the cycle counting power of graph neural networks with I ^2 -gnns

    Huang, Y., Peng, X., Ma, J., and Zhang, M. Boosting the cycle counting power of graph neural networks with I ^2 -gnns. In The Eleventh International Conference on Learning Representations, 2023

    2023

  34. [42]

    and Ribeiro, A

    Kanatsoulis, C. and Ribeiro, A. Counting graph substructures with graph neural networks. In The Twelfth International Conference on Learning Representations, 2024

    2024

  35. [43]

    A new status index derived from sociometric analysis

    Katz, L. A new status index derived from sociometric analysis. Psychometrika, 18 0 (1): 0 39--43, 1953

    1953

  36. [44]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017

    2017

  37. [45]

    Mag-gnn: Reinforcement learning boosted graph neural network

    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

    2024

  38. [46]

    Rethinking graph transformers with spectral attention

    Kreuzer, D., Beaini, D., Hamilton, W., L \'e tourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 0 21618--21629, 2021

    2021

  39. [47]

    Distance encoding: Design provably more powerful neural networks for graph representation learning

    Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33: 0 4465--4478, 2020

    2020

  40. [48]

    D., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, S

    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

    2023

  41. [49]

    Expressive sign equivariant networks for spectral geometric learning

    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

    2024

  42. [50]

    and Hutter, F

    Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019

    2019

  43. [51]

    Invariant and equivariant graph networks

    Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018

    2018

  44. [52]

    Neural network for graphs: A contextual constructive approach

    Micheli, A. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20 0 (3): 0 498--511, 2009. doi:10.1109/TNN.2008.2010350

    2009

  45. [53]

    L., Lenssen, J

    Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp.\ 4602--4609, 2019

    2019

  46. [54]

    M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M

    Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020 a

    2020

  47. [55]

    Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings

    Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 0 21824--21840, 2020 b

    2020

  48. [56]

    M., Grohe, M., Fey, M., and Borgwardt, K

    Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 24 0 (1): 0 15865--15923, 2023

    2023

  49. [57]

    Papp, P. A. and Wattenhofer, R. A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning, pp.\ 17323--17345. PMLR, 2022

    2022

  50. [58]

    A., Martinkus, K., Faber, L., and Wattenhofer, R

    Papp, P. A., Martinkus, K., Faber, L., and Wattenhofer, R. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34: 0 21997--22009, 2021

    2021

  51. [59]

    Pytorch: An imperative style, high-performance deep learning library

    Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019

    2019

  52. [60]

    Ordered subgraph aggregation networks

    Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris, C. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems, 35: 0 21030--21045, 2022

    2022

  53. [61]

    P., Luu, A

    Ramp \'a s ek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 0 14501--14515, 2022

    2022

  54. [62]

    Read, R. C. and Wilson, R. J. An atlas of graphs. Oxford University Press, 1998

    1998

  55. [63]

    Random features strengthen graph neural networks

    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--341. SIAM, 2021

    2021

  56. [64]

    C., Hagenbuchner, M., and Monfardini, G

    Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20 0 (1): 0 61--80, 2009. doi:10.1109/TNN.2008.2005605

    2009

  57. [65]

    and Irwin, J

    Sterling, T. and Irwin, J. J. Zinc 15--ligand discovery for everyone. Journal of chemical information and modeling, 55 0 (11): 0 2324--2337, 2015

    2015

  58. [66]

    S., and He, L

    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 mechanism. In Proceedings of the web conference 2021, pp.\ 2081--2091, 2021

    2021

  59. [67]

    Counting substructures with higher-order graph neural networks: Possibility and impossibility results

    Tahmasebi, B., Lim, D., and Jegelka, S. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv:2012.03174, 2020

    2012 arXiv

  60. [68]

    Where did the gap go? reassessing the long-range graph benchmark

    T \"o nshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. In The Second Learning on Graphs Conference, 2023

    2023

  61. [69]

    Building powerful and equivariant graph neural networks with structural message-passing

    Vignac, C., Loukas, A., and Frossard, P. Building powerful and equivariant graph neural networks with structural message-passing. Advances in neural information processing systems, 33: 0 14143--14155, 2020

    2020

  62. [70]

    Equivariant and stable positional encoding for more powerful graph neural networks

    Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations, 2022

    2022

  63. [71]

    and Leman, A

    Weisfeiler, B. and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2 0 (9): 0 12--16, 1968

    1968

  64. [72]

    How powerful are graph neural networks? In International Conference on Learning Representations, 2018

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018

    2018

  65. [73]

    Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34: 0 28877--28888, 2021

    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: 0 28877--28888, 2021

    2021

  66. [74]

    M., Ying, R., and Leskovec, J

    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

    2021

  67. [75]

    Small relu networks are powerful memorizers: a tight analysis of memorization capacity

    Yun, C., Sra, S., and Jadbabaie, A. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019

    2019

  68. [76]

    A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests

    Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference on Machine Learning, pp.\ 41019--41077. PMLR, 2023 a

    2023

  69. [77]

    Rethinking the expressive power of gnns via graph biconnectivity

    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, 2023 b

    2023

  70. [78]

    and Li, P

    Zhang, M. and Li, P. Nested graph neural networks. Advances in Neural Information Processing Systems, 34: 0 15734--15747, 2021

    2021

  71. [79]

    From stars to subgraphs: Uplifting any gnn with local structure awareness

    Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2022

    2022

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.