Pith

open record

sign in

arxiv: 2605.25452 · v1 · pith:Q46DHJ5G · submitted 2026-05-25 · stat.ME · cs.LG· stat.ML

Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks

Nil Ayday , Mahalakshmi Sabanayagam , Debarghya Ghoshdastidar This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 reserved 2026-06-29 21:01 UTCgrok-4.3pith:Q46DHJ5Grecord.jsonopen to challenge →

classification stat.ME cs.LGstat.ML
keywords Graph Neural NetworksGeneralizationLearning TheoryNeural Tangent KernelGraphonStochastic Block ModelStatistical Learning
0
0 comments X

The pith

Three frameworks organize existing statistical analyses of generalization in graph neural networks.

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

The paper surveys mathematical approaches to understanding when and why graph neural networks perform well on unseen graph data. It groups the literature into three distinct frameworks: one based on learning-theoretic uniform convergence bounds that tie performance to hypothesis class complexity and graph isomorphism expressivity; a second that simplifies analysis by taking limits of infinite parameters or infinite graph size to obtain Gaussian process or kernel approximations; and a third that assumes data generated from random graph models such as the contextual stochastic block model and derives explicit finite-sample error rates via high-dimensional statistics. A reader would care because GNNs are already deployed in social networks and drug discovery yet lack clear performance guarantees, and mapping these perspectives reveals both what is known and where theory remains incomplete.

Core claim

Statistical generalization in GNNs is currently studied from three broad perspectives. The first relies on uniform convergence bounds and the complexity of specific GNN hypothesis classes, often connected to expressivity results from graph isomorphism tests. The second simplifies the architecture by studying infinite-parameter or infinite-graph limits, yielding approximations via Gaussian processes, neural tangent kernels, or graphon operators that enable statements about generalization and stability. The third framework assumes data arise from random graph models, typically the contextual stochastic block model, and obtains non-asymptotic error rates using tools from high-dimensional statis

What carries the argument

The division of the literature into three frameworks: learning-theory bounds on hypothesis complexity, infinite-parameter asymptotic approximations, and random-graph model analyses.

If this is right

  • Learning-theory bounds connect generalization directly to the width, depth, and aggregation functions of concrete GNN architectures.
  • Infinite approximations convert questions about trained GNNs into analyses of associated kernel or operator limits.
  • Random-graph analyses produce explicit non-asymptotic rates that depend on graph size, feature dimension, and community structure.
  • Each framework carries distinct limitations that future work must address separately.

Where Pith is reading between the lines

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

  • The survey structure itself suggests that combining elements from more than one framework could address gaps left by any single approach.
  • Practitioners choosing GNN architectures for new domains may use the three-way map to decide which theoretical guarantee is most relevant to their data-generating process.
  • Open questions listed in the paper point to the need for results that hold uniformly across finite and infinite regimes.

Load-bearing premise

That these three frameworks together cover the main statistical approaches used to study GNN generalization.

What would settle it

A substantial body of theoretical work on GNN generalization whose methods and results cannot be placed in any of the three described frameworks.

read the original abstract

Graph Neural Networks (GNN) are currently the most popular approach for learning and prediction on graph-structured data and are deployed in various fields, from social network analysis to drug discovery. However, there is limited mathematical understanding of the performance of GNNs. We discuss the various perspectives used to study statistical generalisation in GNNs. We identify three broad frameworks. The first approach, rooted in learning theory, relies on uniform convergence bounds and the complexity of the hypothesis class of specific GNN architectures. This approach also builds on the expressivity of GNNs, typically studied through the lens of graph isomorphism tests. The second principle is to simplify the neural architecture by analysing GNNs under the asymptotics of infinitely many parameters or infinite graph size. This approach approximates GNNs using Gaussian processes, neural tangent kernels or graphon neural network operators, which allow studying the generalisation or stability of trained GNNs. The third framework studies GNNs under random graph models, often the contextual stochastic block model, and derives non-asymptotic error rates using tools from high-dimensional statistics. We highlight some key theoretical results and discuss a few limitations and open research questions for each perspective.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript is a survey on statistical perspectives for generalization in Graph Neural Networks. It identifies three broad frameworks: (1) learning theory relying on uniform convergence bounds, hypothesis class complexity, and expressivity studied via graph isomorphism tests; (2) infinite-parameter or infinite-graph asymptotics approximating GNNs via Gaussian processes, neural tangent kernels, or graphon operators to analyze generalization and stability; and (3) random graph models (e.g., contextual stochastic block model) deriving non-asymptotic error rates via high-dimensional statistics. Key theoretical results, limitations, and open questions are discussed for each framework.

Significance. If the taxonomy accurately organizes the literature, the paper provides a useful synthesis for researchers working on GNN generalization, a topic with limited mathematical understanding. The manuscript is credited for explicitly addressing limitations and open research questions within each perspective, which strengthens its value as a survey. No new derivations, machine-checked proofs, or empirical claims are advanced; the contribution is organizational.

minor comments (2)
  1. [Abstract] Abstract: the phrasing 'we discuss the various perspectives' followed by identification of exactly three frameworks could be clarified to indicate whether overlaps between frameworks are addressed or if additional perspectives exist outside this taxonomy.
  2. The manuscript would benefit from a summary table or figure comparing the three frameworks along dimensions such as asymptotic regime, main technical tools, and type of generalization guarantee obtained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of our manuscript. The referee's summary accurately captures the scope and contributions of our survey. We are encouraged by the recommendation for minor revision and will incorporate any suggested improvements in the revised version.

Circularity Check

0 steps flagged

No significant circularity: survey with no derivations or self-referential predictions

full rationale

The paper is a literature survey that identifies and discusses three existing frameworks for GNN generalization (learning theory bounds, infinite-parameter approximations, random graph models) without advancing any new technical derivation, theorem, fitted parameter, or prediction. The central claim is organizational and explicitly flags limitations and open questions per framework. No equations, self-citations, or ansatzes are load-bearing in a way that reduces the taxonomy to its own inputs by construction. This matches the default expectation for non-circular survey papers.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper with no new mathematical derivations, empirical claims, or modeling assumptions introduced by the authors.

pith-pipeline@v0.9.1-grok · 5753 in / 994 out tokens · 31264 ms · 2026-06-29T21:01:32.723164+00:00 · methodology

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

41 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    In: International Conference on Learning Representations

    Chen, Z., Li, L., Bruna, J.: Supervised community detection with line graph neural networks. In: International Conference on Learning Representations. Openreview.net (2019)

    2019

  2. [2]

    Journal of Machine Learning Research18(177), 1–86 (2017) 12

    Abbe, E.: Community detection and stochastic block models: Recent develop- ments. Journal of Machine Learning Research18(177), 1–86 (2017) 12

    2017

  3. [3]

    Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges

    Bronstein, M.M., Bruna, J., Cohen, T., Velickovi, P.: Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv:2104.13478 (2021)

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  4. [4]

    IEEE Transactions of Neural Networks and Learning Systems32(1), 4–24 (2021)

    Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Yu, P.S.: A comprehensive survey on graph neural networks. IEEE Transactions of Neural Networks and Learning Systems32(1), 4–24 (2021)

    2021

  5. [5]

    arXiv preprint (arXiv:2502.16533) (2025)

    Yuan, C., Zhao, K., Kuruoglu, E.E., Wang, L., Xu, T., Huang, W., Zhao, D., Cheng, H., Rong, Y.: A survey of graph transformers: Architectures, theories and applications. arXiv preprint (arXiv:2502.16533) (2025)

    work page arXiv 2025

  6. [6]

    In: International Conference on Learning Representations (2017)

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

    2017

  7. [7]

    In: International Conference on Learning Representations

    Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Li` o, P., Bengio, Y.: Graph attention networks. In: International Conference on Learning Representations. Openreview.net (2018)

    2018

  8. [8]

    Journal of Machine Learning Research (in press) (2026)

    Vasileiou, A., Jegelka, S., Levie, R., Morris, C.: Survey on generalization theory for graph neural networks. Journal of Machine Learning Research (in press) (2026)

    2026

  9. [9]

    The MIT Press, (2024)

    Bach, F.: Learning Theory from First Principles. The MIT Press, (2024)

    2024

  10. [10]

    Journal of Machine Learning Research21(11), 1–34 (2020)

    Cai, T.T., Liang, T., Rakhlin, A.: Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information. Journal of Machine Learning Research21(11), 1–34 (2020)

    2020

  11. [11]

    In: International Conference on Machine Learning

    Garg, V.K., Jegelka, S., Jaakkola, T.: Generalization and representational limits of graph neural networks. In: International Conference on Machine Learning. PMLR (2020)

    2020

  12. [12]

    Nauchno-Technicheskaya Informatsia Ser

    Weisfeiler, B., Leman, A.A.: A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Technicheskaya Informatsia Ser. 2(N9), 12–16 (1968)

    1968

  13. [13]

    AAAI Press, vol

    Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., Grohe, M.: Weisfeiler and leman go neural: Higher-order graph neural networks. AAAI Press, vol. 18, pp. 4602–4609 (2019)

    2019

  14. [14]

    In: International Conference on Learning Representations

    Geerts, F., Reutter, J.L.: Expressiveness and approximation properties of graph neural networks. In: International Conference on Learning Representations. Openreview.net (2022)

    2022

  15. [15]

    In: International Conference on Machine Learning

    Morris, C., Geerts, F., T¨ onshoff, J., Grohe, M.: WL meet VC. In: International Conference on Machine Learning. PMLR, pp. 25275–25302 (2023)

    2023

  16. [16]

    Journal of Artificial Intelligence Research35, 193–234 (2009) 13

    El-Yaniv, R., Pechyony, D.: Transductive rademacher complexity and its appli- cations. Journal of Artificial Intelligence Research35, 193–234 (2009) 13

    2009

  17. [17]

    In: Advances in Neural Information Processing Systems (2021)

    Esser, P.M., Vankadara, L.C., Ghoshdastidar, D.: Learning theory can (some- times) explain generalisation in graph neural networks. In: Advances in Neural Information Processing Systems (2021)

    2021

  18. [18]

    In: Advances in Neural Information Processing Systems (2022)

    Keriven, N.: Not too little, not too much: a theoretical analysis of graph (over)smoothing. In: Advances in Neural Information Processing Systems (2022)

    2022

  19. [19]

    arXiv preprint (arXiv:2509.10337) (2025)

    Ayday, N., Sabanayagam, M., Ghoshdastidar, D.: Why does your graph neu- ral network fail on some graphs? insights from exact generalisation error. arXiv preprint (arXiv:2509.10337) (2025)

    work page arXiv 2025

  20. [20]

    Proceedings of the National Academy of Sciences121(8), 2309504121 (2024)

    Shi, C., Pan, L., Hu, H., Dokmani´ c, I.: Homophily modulates double descent gen- eralization in graph convolution networks. Proceedings of the National Academy of Sciences121(8), 2309504121 (2024)

    2024

  21. [21]

    In: International Conference on Learning Representations

    Oono, K., Suzuki, T.: Graph neural networks exponentially lose expressive power for node classification. In: International Conference on Learning Representations. Openreview.net (2020)

    2020

  22. [22]

    In: Advances in Neural Information Processing Systems (2020)

    Oono, K., Suzuki, T.: Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. In: Advances in Neural Information Processing Systems (2020)

    2020

  23. [23]

    Transactions of Machine Learning Research (Openreview.net) (2023)

    Sabanayagam, M., Esser, P.M., Ghoshdastidar, D.: Analysis of convolutions, non-linearity and depth in graph neural networks using neural tangent kernel. Transactions of Machine Learning Research (Openreview.net) (2023)

    2023

  24. [24]

    arXiv preprint (arXiv:2603.17569) (2026)

    Ayday, N., Yang, L., Ghoshdastidar, D.: Gaussian process limit reveals structural benefits of graph transformers. arXiv preprint (arXiv:2603.17569) (2026)

    work page arXiv 2026

  25. [25]

    In: International Conference on Learning Representations

    Lee, J., Bahri, Y., Novak, R., Schoenholz, S.S., Pennington, J., Sohl-Dickstein, J.: Deep neural networks as gaussian processes. In: International Conference on Learning Representations. Openreview.net (2018)

    2018

  26. [26]

    In: International Conference on Learning Representations

    Niu, Z., Anitescu, M., Chen, J.: Graph neural network-inspired kernels for gaussian processes in semi-supervised learning. In: International Conference on Learning Representations. Openreview.net (2023)

    2023

  27. [27]

    In: Advances in Neural Information Processing Systems (2020)

    Liu, C., Zhu, L., Belkin, M.: On the linearity of large non-linear models: when and why the tangent kernel is constant. In: Advances in Neural Information Processing Systems (2020)

    2020

  28. [28]

    In: Advances in Neural Information Processing Systems (2018)

    Jacot, A., Hongler, C., Gabriel, F.: Neural tangent kernel: Convergence and gen- eralization in neural networks. In: Advances in Neural Information Processing Systems (2018)

    2018

  29. [29]

    In: Advances in Neural Information Processing Systems (2019)

    Du, S.S., Hou, K., Salakhutdinov, R., P´ oczos, B., Wang, R., Xu, K.: Graph neural 14 tangent kernel: Fusing graph neural networks with graph kernels. In: Advances in Neural Information Processing Systems (2019)

    2019

  30. [30]

    In: International Conference on Learning Representations

    Sabanayagam, M., Gosch, L., G¨ unnemann, S., Ghoshdastidar, D.: Exact cer- tification of (graph) neural networks against label poisoning. In: International Conference on Learning Representations. Openreview.net (2025)

    2025

  31. [31]

    Colloquium Publications

    Lov´ asz, L.: Large Networks and Graph Limits. Colloquium Publications. Ameri- can Mathematical Society, vol. 60 (2012)

    2012

  32. [32]

    In: Advances in Neural Information Processing Systems (2020)

    Keriven, N., Bietti, A., Vaiter, S.: Convergence and stability of graph convo- lutional networks on large random graphs. In: Advances in Neural Information Processing Systems (2020)

    2020

  33. [33]

    In: Advances in Neural Information Processing Systems (2020)

    Ruiz, L., Chamon, L.F.O., Ribeiro, A.: Graphon neural networks and the transfer- ability of graph neural networks. In: Advances in Neural Information Processing Systems (2020)

    2020

  34. [34]

    In: International Conference on Machine Learning

    Krishnagopal, S., Ruiz, L.: Graph neural tangent kernel: Convergence on large graphs. In: International Conference on Machine Learning. PMLR (2023)

    2023

  35. [35]

    In: International Conference on Machine Learning

    Baranwal, A., Fountoulakis, K., Jagannath, A.: Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In: International Conference on Machine Learning. PMLR, pp. 684–693 (2021)

    2021

  36. [36]

    Journal of Machine Learning Research24(246) (2023)

    Fountoulakis, K., Levi, A., Yang, S., Baranwal, A., Jagannath, A.: Graph attention retrospective. Journal of Machine Learning Research24(246) (2023)

    2023

  37. [37]

    In: Annual Conference on Learning Theory

    Abbe, E., Adser` a, E.B., Misiakiewicz, T.: SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. In: Annual Conference on Learning Theory. PMLR, pp. 2552–2623 (2023)

    2023

  38. [38]

    In: International Conference on Learning Representations

    Sabanayagam, M., Vankadara, L.C., Ghoshdastidar, D.: Graphon based clustering and testing of networks: Algorithms and theory. In: International Conference on Learning Representations. OpenReview.net (2022)

    2022

  39. [39]

    arXiv preprint (arXiv:2602.20844) (2026)

    Ghosh, S., Karmakar, R.N., Lahiry, S.: Maximum entropy based testing in network models: ERGMs and constrained optimization. arXiv preprint (arXiv:2602.20844) (2026)

    work page arXiv 2026

  40. [40]

    In: Advances in Neural Information Processing Systems (2022)

    Zhou, Y., Kutyniok, G., Ribeiro, B.: OOD link prediction generalization capa- bilities of message-passing gnns in larger test graphs. In: Advances in Neural Information Processing Systems (2022)

    2022

  41. [41]

    The Annals of Statistics43(6), 2624–2652 (2015) 15

    Gao, C., Lu, Y., Zhou, H.H.: Rate-optimal graphon estimation. The Annals of Statistics43(6), 2624–2652 (2015) 15

    2015