# A graphon-signal analysis of graph neural networks

arXiv: https://arxiv.org/abs/2305.15987 · HTML: https://mlsanity.com/paper/2305.15987/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 25 May 2023.

## Builds on (most cited first, 23 of 23)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Geometric Deep Learning on Molecular Representations](https://mlsanity.com/paper/2107.12375/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Graphon Signal Processing](https://mlsanity.com/paper/2003.05030/) (2020)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Graph and graphon neural network stability](https://mlsanity.com/paper/2010.12529/) (2020)

## Built on by (most cited first, 30 of 30)

- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Almost Surely Asymptotically Constant Graph Neural Networks](https://mlsanity.com/paper/2403.03880/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Generalization of Graph Neural Networks is Robust to Model Mismatch](https://mlsanity.com/paper/2408.13878/) (2024)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Bridging Input Feature Spaces Towards Graph Foundation Models](https://mlsanity.com/paper/2605.04834/) (2026)
- [Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters](https://mlsanity.com/paper/2406.01249/) (2024)
- [Efficient Learning on Large Graphs using a Densifying Regularity Lemma](https://mlsanity.com/paper/2504.18273/) (2025)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [Learning graphons from data: Random walks, transfer operators, and spectral clustering](https://mlsanity.com/paper/2507.18147/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities](https://mlsanity.com/paper/2409.11618/) (2024)
- [A Note on Graphon-Signal Analysis of Graph Neural Networks](https://mlsanity.com/paper/2508.18564/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks](https://mlsanity.com/paper/2604.10553/) (2026)
- [A Spectral Framework for Graph Neural Operators: Convergence Guarantees and Tradeoffs](https://mlsanity.com/paper/2510.20954/) (2025)
- [Neural Networks With Dense Weights Are Not Universal Approximators](https://mlsanity.com/paper/2602.07618/) (2026)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [A Topological Characterization of Graph Neural Networks via Stochastic Block Model Embeddings on the n-Sphere](https://mlsanity.com/paper/2606.07598/) (2026)
- [Warm-starting PDE solvers with any-dimensional machine learning](https://mlsanity.com/paper/2609.38916/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

We present an approach for analyzing message passing graph neural networks (MPNNs) based on an extension of graphon analysis to a so called graphon-signal analysis. A MPNN is a function that takes a graph and a signal on the graph (a graph-signal) and returns some value. Since the input space of MPNNs is non-Euclidean, i.e., graphs can be of any size and topology, properties such as generalization are less well understood for MPNNs than for Euclidean neural networks. We claim that one important missing ingredient in past work is a meaningful notion of graph-signal similarity measure, that endows the space of inputs to MPNNs with a regular structure. We present such a similarity measure, called the graphon-signal cut distance, which makes the space of all graph-signals a dense subset of a compact metric space -- the graphon-signal space. Informally, two deterministic graph-signals are close in cut distance if they ``look like'' they were sampled from the same random graph-signal model. Hence, our cut distance is a natural notion of graph-signal similarity, which allows comparing any pair of graph-signals of any size and topology. We prove that MPNNs are Lipschitz continuous functions over the graphon-signal metric space. We then give two applications of this result: 1) a generalization bound for MPNNs, and, 2) the stability of MPNNs to subsampling of graph-signals. Our results apply to any regular enough MPNN on any distribution of graph-signals, making the analysis rather universal.