Pith. sign in

REVIEW 3 major objections 5 minor 35 references

This paper claims that any graph neural network whose expressive power is bounded by a graph coloring has empirical Rademacher complexity at most √(p/m), where p is the number of color classes in the training sample — making expressivity it

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 10:19 UTC pith:7BRDMLYN

load-bearing objection The upper bound is real and worth knowing; the tightness claim is false as stated, and the abstract oversells results the paper does not contain. the 3 major comments →

arxiv 2510.10101 v4 pith:7BRDMLYN submitted 2025-10-11 cs.LG

On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry

Martin Carrasco , Caio F. Deberaldini Netto , Vahan A. Martirosyan , Ehimare Okoyomon , Caterina Graziani This is my paper
classification cs.LG MSC 68T0768Q3205C60
keywords graph neural networksRademacher complexitygeneralization boundsexpressivityWeisfeiler-Lemangraph coloringWL hierarchyempirical Rademacher complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper sets out to explain, in quantitative terms, why more expressive graph neural networks tend to generalize worse. The authors use the empirical Rademacher complexity — a data-dependent measure of how well a model class can fit random labels — and show that whenever a coloring scheme such as the Weisfeiler–Leman test bounds a GNN's expressive power, that coloring splits the sample into p equivalence classes and every learnable function must be constant on each class. Under this constraint, the Rademacher complexity is at most √(p/m), and at least √(p/(2m)) when the classes are equally sized, so the order is exact. Since finer colorings accompany more expressive architectures, expressivity directly raises the complexity term in the generalization bound. The result is architecture-agnostic, extends to any invariant that partitions graphs, and is stable under small changes in color counts across datasets.

Core claim

The central discovery is a partition-controlled bound on empirical Rademacher complexity. For a sample of m graphs partitioned into p classes by any coloring that upper-bounds an architecture's expressive power, every [-1,1]-valued function in the class is constant on each class, and the empirical Rademacher complexity satisfies R_S(F) ≤ √(p/m). When the classes have equal size, the same quantity is at least √(p/(2m)), so the bound is tight up to a constant. The argument groups the Rademacher sum by color class and applies Cauchy–Schwarz and Jensen's inequality, converting the count of colors into the complexity measure. The paper further proves that the complexity is Lipschitz in the color

What carries the argument

The load-bearing object is the coloring partition. A graph coloring (for example, the Weisfeiler–Leman test) upper-bounds a GNN's expressivity by assigning each graph a color; graphs sharing a color form an equivalence class on which every hypothesis in the class must be constant. The proof identity re-expresses the Rademacher sum as a sum over classes, R_S(F) = (1/m) E_σ sup_Θ Σ_j f_j(Θ) Σ_{i∈I_j} σ_i, then uses Cauchy–Schwarz to separate the function-dependent norm from the Rademacher variables and Jensen's inequality to evaluate the expectation, leaving the √(p/m) factor. This identity is what lets the number of colors, rather than parameter count or architecture details, control the gene

Load-bearing premise

The bound holds only when the coloring is a true upper bound on expressivity: every pair of graphs sharing a color must receive the same output from every function in the class, so any architecture that distinguishes graphs within a color class — through continuous features, readouts, or non-partitioning similarities — falls outside the theorem.

What would settle it

Compute the exact empirical Rademacher complexity of a verified color-constant GNN class on a small sample by enumerating all 2^m labelings; any value above √(p/m) refutes the central upper bound. On a sample with equal-sized color classes, a value below √(p/(2m)) would refute the claimed tightness.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Architectures with finer partitions — higher-order Weisfeiler–Leman, subgraph, or path-based GNNs — inherit a larger p and therefore a weaker generalization guarantee than coarser, less expressive models on the same sample.
  • Because the complexity term scales as 1/√m, adding training data can only counteract expressivity at a square-root rate.
  • The bound is data-dependent: two samples can give different p for the same architecture, so the same model may be tightly or loosely controlled depending on the color diversity of its data.
  • The stability result means datasets with similar color histograms yield similar complexity bounds, so the generalization analysis is robust to sampling variation.
  • The improved Dudley integral carries the covering-number analysis in p dimensions rather than m, tightening classical entropy-based bounds whenever the coloring partitions the sample.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bound suggests a model-selection heuristic the authors do not state: among architectures that reach the required expressive power, prefer the one inducing the fewest color classes on the training sample, because parameter count never enters the bound.
  • Because p alone controls the ceiling, the result predicts that a low-expressivity but heavily parameterized GNN should generalize better than a high-expressivity one at fixed sample size — a comparison that could be tested empirically.
  • The partition assumption excludes continuous node attributes and pseudometric similarities; a natural extension would replace p with a covering or quantization number at scale ε, producing bounds that interpolate between the discrete color regime and the smooth input geometry the abstract advertises.
  • The Lipschitz stability inequality can be read as a map from color-count vectors to complexity, suggesting that the distance between training and test color histograms could serve as a practical predictor of the generalization gap.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes a data-dependent generalization analysis for GNNs by linking the number of equivalence classes induced by a graph coloring (e.g., WL) to the empirical Rademacher complexity of a color-constant hypothesis class. The main results are: (i) an upper bound R_S(F) ≤ sqrt(p/m) for [−1,1]-valued functions constant on each of p color classes (Prop. 3.1, Cor. 3.2); (ii) a claimed matching lower bound R_S(F) ≥ sqrt(p/(2m)) under uniform color-class sizes (Prop. 3.3); (iii) a Dudley-type bound exploiting the p-dimensional structure (Prop. 3.4); (iv) a Lipschitz-stability result for R_S under perturbations of color counts (Prop. 3.5); and (v) an extension to arbitrary architecture/coloring pairs. The paper argues that more expressive GNNs, having larger p, incur higher Rademacher complexity and thus weaker generalization guarantees.

Significance. The upper bound of Cor. 3.2 is a clean and potentially useful observation: for any GNN class whose expressivity is captured by a partition into p equivalence classes on the training sample, the empirical Rademacher complexity is O(sqrt(p/m)). This is a valid contribution and may serve as a baseline for more refined bounds. The stability result (Prop. 3.5) is also a useful technical lemma. However, the advertised central claim — that greater expressivity leads to higher complexity, i.e., that the upper bound is tight — relies on Prop. 3.3, which is false as stated. The paper also contains no experiments, and the Dudley-type bound has a proof gap. The valid upper bound alone establishes only that a coarser partition yields a smaller upper bound, not that actual Rademacher complexity grows with expressivity. Thus the paper's headline conclusion is not supported, although a weaker form of the result is correct and potentially publishable after revision.

major comments (3)
  1. [Prop. 3.3 / Appendix D.2] Proposition 3.3 is false as stated. The assumptions only require F to be color-constant and [−1,1]-valued; they do not require F to contain the sign functions used in the proof. The proof asserts 'The sup is obtained for f_j(Θ)=sign(∑_{i∈I_j} σ_i)' and then applies Khintchine, implicitly assuming F realizes every sign pattern on the p classes independently. A concrete counterexample: m=2, p=2, each class of size 1, and F={f≡0.5}. This class satisfies all stated assumptions, but R_S(F)=0, while the claimed lower bound is sqrt(2/(2·2))≈0.707. This is load-bearing because the paper uses Prop. 3.3 to claim tightness and to conclude that 'more expressivity leads to higher complexity'. Without a corrected lower bound (e.g., under an explicit richness assumption on F), the central trade-off claim is unsupported.
  2. [Prop. 3.4 / Appendix D.3] The proof of Proposition 3.4 assumes that the cover vectors v_k[f] are constant on color classes, so that residuals f|S − v_k[f] inherit the partition structure. However, an arbitrary minimal ℓ2-cover of F|S need not have this property; the statement 'GN inherits the partition structure from F' is not justified. This can be fixed by noting that F|S lies in the subspace of color-constant vectors, so one may project any cover onto that subspace without increasing covering numbers (orthogonal projection is nonexpansive and fixes F|S). The authors should state this projection argument explicitly; as written, the proof has a gap.
  3. [Abstract, Section 5] The abstract claims that 'greater expressivity leads to higher complexity and thus weaker generalization guarantees,' and the introduction/conclusion repeatedly state that expressivity 'comes at the cost' of generalization. What is actually proved (once Prop. 3.3 is removed) is that a finer partition leads to a larger upper bound on the empirical Rademacher complexity. An upper bound that grows with p does not imply that the true Rademacher complexity grows with p; the bound could be loose for small p or tight for large p. The authors should either repair the lower bound with adequate assumptions or substantially temper the claims to 'more expressivity leads to larger upper bounds on R_S,' which is a weaker, but valid, statement.
minor comments (5)
  1. [Section 3 / Eq. (12)] In Prop. 3.1, the quantity sup_Θ L(Θ) is not explicitly defined in the statement; it is introduced in the proof. For clarity, define L(Θ) = (∑_{i=1}^m f(G_i;Θ)^2)^{1/2} in the statement and note that it may be unbounded unless the output space is bounded.
  2. [Appendix D.3] The notation N(F|S, ε, ||·||_2) is used with an extra comma in places (e.g., 'N(F |S, ϵ,|| · ||2)'). Please standardize the notation. Also, the statement of Prop. 3.4 says 'the bound is reduced due to the p-dimensional structure' — this is only an improvement when p < m; the authors may want to state this explicitly.
  3. [Appendix E.1] The cross-entropy loss in Prop. E.1 is written as a sum over m samples inside a single-sample loss definition; this is confusing and likely a typo. The proof should use a single-sample loss ℓ_CE(f(G), y) = −[y log f(G) + (1−y) log(1−f(G))].
  4. [Figure 1] The figure caption states 'Smaller upper bound' near the 'More expressivity' arrow, which could be misread. Since the paper argues that more expressivity yields a larger upper bound, the label should be clarified (e.g., 'larger upper bound for the finer partition').
  5. [NeurIPS Checklist, Item 1] The checklist answer [Yes] for 'Claims' states that the abstract and introduction accurately reflect the paper's contributions. Given the issues with Prop. 3.3 and the overclaim in the abstract, this answer should be revisited after revision.

Circularity Check

0 steps flagged

No significant circularity: the Rademacher bound is a direct calculation and the trade-off claim is an interpretation of the proved upper bound.

full rationale

The derivation chain is self-contained. Corollary 3.2 follows from the definition of R_S (Eq. 7) by grouping the sum over color classes and applying Cauchy–Schwarz and Jensen (Appendix D.1); no parameter is fitted from data and no prior result by the authors is invoked as authority. The bound is an upper bound on the empirical Rademacher complexity of color-constant classes, so the conclusion that a larger number of classes p can make the upper bound looser is a direct consequence of the proof, not an input assumed into the theorem. Section 3.2 extends to arbitrary coloring functions conditionally on the existence of a coloring T with A ⊑ T, and simply substitutes p_T for p; this is not a circular reduction because color-constancy is an explicit premise, not the target conclusion. The stability result (Prop. 3.5) is also proved directly from the definition and Lemma D.4. The only noteworthy issue is that Prop. 3.3's lower-bound proof assumes that F realizes sign(Z_j) on each color class, an assumption not stated in the proposition; this is a correctness gap, not a circularity, since the upper-bound claim does not depend on it. A minor self-citation ([12]) appears only as an example of a path-based GNN and is not load-bearing. Hence no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No free parameters are fitted; the paper is purely analytic. The main axioms are standard learning-theoretic and expressivity results. The two ad-hoc entries correspond to unstated assumptions in the lower-bound and improved-Dudley proofs, and are the main correctness risks.

axioms (5)
  • domain assumption WL coloring is an upper bound on MPGNN expressivity: same color implies same embedding (Eq. 5).
    Inherited from Xu et al. 2018 / Morris et al. 2019; used throughout §2–3 to justify that F is constant on color classes.
  • domain assumption Hypothesis class is F={f:G→[-1,1]} with bounded outputs, and 0∈F for Prop 3.4.
    Defines the setting; boundedness is needed for sqrt(p/m) and the Dudley bound.
  • ad hoc to paper In Prop 3.3, F is rich enough to contain sign functions f_j(Θ)=sign(Z_j) on each class.
    Not stated in the theorem; without it the lower bound is false (F={0}).
  • ad hoc to paper In D.3, cover vectors v_k[f] can be taken constant on color classes, so residuals inherit the partition structure.
    Unsupported; a minimal cover in R^m need not lie in the p-dimensional class-constant subspace.
  • standard math Standard Rademacher generalization bound (Mohri et al. Thm 3.3) and Talagrand contraction.
    Used to convert R_S(F) into a generalization bound (Prop 2.3).

pith-pipeline@v1.3.0-alltime-deepseek · 20689 in / 16155 out tokens · 137948 ms · 2026-08-04T10:19:30.982156+00:00 · methodology

0 comments
read the original abstract

Understanding the interplay between generalization, expressivity, and the geometry of the input space is a central challenge in graph learning. The expressivity of Graph Neural Networks (GNNs) is typically characterized through their correspondence with graph invariants, such as those from the Weisfeiler-Leman (WL) hierarchy. While more expressive GNNs can distinguish a richer set of graphs, they are also associated with weaker generalization guarantees. Previous works have addressed this trade-off using the VC dimension, a purely combinatorial measure, independent of the training data. In this work, we adopt a data-dependent measure of generalization, the empirical Rademacher complexity, and derive tight generalization bounds that jointly consider the expressive power of GNNs and the geometry of the underlying input space. Specifically, any graph invariant that upper-bounds a GNN's expressive power partitions the input space into equivalence classes, and we show that the empirical Rademacher complexity is controlled by the distribution of training samples across these classes. Moving beyond discrete partitions, we incorporate the geometry of the input space and derive covering-number bounds under Lipschitz continuity, showing that the complexity cost can be mitigated when the hypothesis class remains smooth over the data geometry. In addition, we prove that the empirical Rademacher complexity is Lipschitz continuous with respect to the Wasserstein distance between empirical measures supported on different datasets. This yields robustness and generalization guarantees under sampling variability. Importantly, our framework is not restricted to message-passing GNNs or WL, but extends to arbitrary GNN architectures and their associated invariants, providing a step toward a unified theory of GNN generalization.

Figures

Figures reproduced from arXiv: 2510.10101 by Caio F. Deberaldini Netto, Caterina Graziani, Ehimare Okoyomon, Martin Carrasco, Vahan A. Martirosyan.

Figure 1
Figure 1. Figure 1: Two function classes Fk-WL and FWL, constrained respectively by 1-WL and k-WL expressivity, induce different partitions of a sample S. The more expressive function class Fk-WL distinguishes more graphs, leading to a finer partition of the sample and a larger number of equivalence classes. Since Rademacher complexity depends on the number of partitions of the input space, the coarser partition induced by FW… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 8 linked inside Pith

  1. [1]

    Shortest path networks for graph property prediction

    Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest path networks for graph property prediction. InLearning on graphs conference, pages 5–1. PMLR, 2022. 2

    2022

  2. [2]

    Spectrally-normalized margin bounds for neural networks

    Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. InAdvances in Neural Information Processing Systems 30 (NIPS 2017), pages 6240–6249, 2017. 6, 12, 17

    2017

  3. [3]

    Equivariant subgraph aggregation networks.arXiv preprint arXiv:2110.02910, 2021

    Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks.arXiv preprint arXiv:2110.02910, 2021. 2

    Pith/arXiv arXiv 2021

  4. [4]

    Weisfeiler and lehman go cellular: Cw networks.Advances in neural information processing systems, 34:2625–2640, 2021

    Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks.Advances in neural information processing systems, 34:2625–2640, 2021. 2, 7

    2021

  5. [5]

    Weisfeiler and lehman go topological: Message passing simplicial networks

    Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. InInternational conference on machine learning, pages 1026–1037. PMLR, 2021. 2

    2021

  6. [6]

    Graph similarity and homomorphism densities.arXiv preprint arXiv:2104.14213,

    Jan Böker. Graph similarity and homomorphism densities.arXiv preprint arXiv:2104.14213,

    Pith/arXiv arXiv

  7. [7]

    Improving graph neural network expressivity via subgraph isomorphism counting.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022

    Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022. 2

    2022

  8. [8]

    Vc dimension of graph neural networks with pfaffian activation functions.Neural Networks, 182:106924,

    Giuseppe Alessio D’Inverno, Monica Bianchini, and Franco Scarselli. Vc dimension of graph neural networks with pfaffian activation functions.Neural Networks, 182:106924,

  9. [9]

    Weisfeiler-leman at the margin: When more expressivity matters.arXiv preprint arXiv:2402.07568, 2024

    Billy J Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-leman at the margin: When more expressivity matters.arXiv preprint arXiv:2402.07568, 2024. 11

    Pith/arXiv arXiv 2024

  10. [10]

    Generalization and representational limits of graph neural networks

    Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. InInternational conference on machine learning, pages 3419–3430. PMLR, 2020. 2, 4, 6

    2020

  11. [11]

    Message passing neural networks

    Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Message passing neural networks. InMachine learning meets quantum physics, pages 199–214. Springer, 2020. 1

    2020

  12. [12]

    The expressive power of path-based graph neural networks.Proceedings of the 41st International Conference on Machine Learning, 235:16226–16249, 2024

    Caterina Graziani, Tamara Drucks, Fabian Jogl, Monica Bianchini, Franco Scarselli, T Gartner, et al. The expressive power of path-based graph neural networks.Proceedings of the 41st International Conference on Machine Learning, 235:16226–16249, 2024. 7

    2024

  13. [13]

    The best constants in the Khintchine inequality.Studia Mathematica, 70(3): 231–283, 1981

    Uffe Haagerup. The best constants in the Khintchine inequality.Studia Mathematica, 70(3): 231–283, 1981. 14 8

    1981

  14. [14]

    Geodesic graph neural network for efficient graph representation learning.Advances in neural information processing systems, 35:5896– 5909, 2022

    Lecheng Kong, Yixin Chen, and Muhan Zhang. Geodesic graph neural network for efficient graph representation learning.Advances in neural information processing systems, 35:5896– 5909, 2022. 2

    2022

  15. [15]

    A graphon-signal analysis of graph neural networks.Advances in Neural Information Processing Systems, 36:64482–64525, 2023

    Ron Levie. A graphon-signal analysis of graph neural networks.Advances in Neural Information Processing Systems, 36:64482–64525, 2023. 11

    2023

  16. [16]

    Multi-class learning: From theory to algorithm.Advances in Neural Information Processing Systems, 31,

    Jian Li, Yong Liu, Rong Yin, Hua Zhang, Lizhong Ding, and Weiping Wang. Multi-class learning: From theory to algorithm.Advances in Neural Information Processing Systems, 31,

  17. [17]

    Towards bridging generalization and expressivity of graph neural networks.arXiv preprint arXiv:2410.10051, 2024

    Shouheng Li, Floris Geerts, Dongwoo Kim, and Qing Wang. Towards bridging generalization and expressivity of graph neural networks.arXiv preprint arXiv:2410.10051, 2024. 11

    Pith/arXiv arXiv 2024

  18. [18]

    American Mathematical Soc.,

    László Lovász.Large networks and graph limits, volume 60. American Mathematical Soc.,

  19. [19]

    Cross-entropy loss functions: Theoretical analysis and applications

    Anqi Mao, Mehryar Mohri, and Yutao Zhong. Cross-entropy loss functions: Theoretical analysis and applications. InInternational conference on Machine learning, pages 23803–23828. pmlr,

  20. [20]

    Graph representational learning: When does more expressivity hurt generalization?arXiv preprint arXiv:2505.11298, 2025

    Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, and Johannes F Lutzeyer. Graph representational learning: When does more expressivity hurt generalization?arXiv preprint arXiv:2505.11298, 2025. 7, 11

    Pith/arXiv arXiv 2025

  21. [21]

    MIT Press, 2012

    Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.Foundations of machine learning. MIT Press, 2012. 3, 4, 7

    2012

  22. [22]

    Weisfeiler and leman go neural: Higher-order graph neural networks

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. InProceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019. 1, 3, 7

    2019

  23. [23]

    WL meet VC

    Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WL meet VC. InInterna- tional conference on machine learning, pages 25275–25302. PMLR, 2023. 2

    2023

  24. [24]

    Weisfeiler and leman go loopy: A new hierarchy for graph representational learning.Advances in Neural Information Processing Systems, 37:120780–120831, 2024

    Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and leman go loopy: A new hierarchy for graph representational learning.Advances in Neural Information Processing Systems, 37:120780–120831, 2024. 2

    2024

  25. [25]

    Generalization, expressivity, and univer- sality of graph neural networks on attributed graphs.arXiv preprint arXiv:2411.05464, 2024

    Levi Rauchwerger, Stefanie Jegelka, and Ron Levie. Generalization, expressivity, and univer- sality of graph neural networks on attributed graphs.arXiv preprint arXiv:2411.05464, 2024. 11

    Pith/arXiv arXiv 2024

  26. [26]

    The graph neural network model.IEEE transactions on neural networks, 20(1):61–80, 2008

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model.IEEE transactions on neural networks, 20(1):61–80, 2008. 1

    2008

  27. [27]

    Autobahn: Automorphism-based graph neural nets

    Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. Advances in Neural Information Processing Systems, 34:29922–29934, 2021. 2

    2021

  28. [28]

    Survey on generaliza- tion theory for graph neural networks.arXiv preprint arXiv:2503.15650, 2025

    Antonis Vasileiou, Stefanie Jegelka, Ron Levie, and Christopher Morris. Survey on generaliza- tion theory for graph neural networks.arXiv preprint arXiv:2503.15650, 2025. 7, 11

    Pith/arXiv arXiv 2025

  29. [29]

    A Reduction of a Graph to a Canonical Form and an Algebra arising during this Reduction

    Boris Weisfeiler and AA Lehman. A Reduction of a Graph to a Canonical Form and an Algebra arising during this Reduction. InNauchno-Technicheskaya Informatsia, pages 2(9):12—-16,

  30. [30]

    How powerful are graph neural networks?arXiv preprint arXiv:1810.00826, 2018

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?arXiv preprint arXiv:1810.00826, 2018. 1, 3

    Pith/arXiv arXiv 2018

  31. [31]

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

    Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. InInternational Conference on Machine Learning, pages 41019–41077. PMLR, 2023. 7 9

    2023

  32. [32]

    Nested graph neural networks.Advances in Neural Information Processing Systems, 34:15734–15747, 2021

    Muhan Zhang and Pan Li. Nested graph neural networks.Advances in Neural Information Processing Systems, 34:15734–15747, 2021. 2

    2021

  33. [33]

    sup f∈F ⟨σ,f |S −v N [f]⟩ # + N−1X k=1 Eσ

    Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications.AI open, 1:57–81, 2020. 1 10 A Additional Related works The fundamental trade-off between expressivity and generalization in GNNs is attracting increasing attention within the ...

    2020

  34. [35]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or ...

    2025

  35. [2025]

    doi: https://doi.org/10.1016/j.neunet.2024.106924

    ISSN 0893-6080. doi: https://doi.org/10.1016/j.neunet.2024.106924. URL https: //www.sciencedirect.com/science/article/pii/S0893608024008530. 2

    arXiv 2024