# A Note on Graphon-Signal Analysis of Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 25 Aug 2025.

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

- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [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)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [Forecasting Global Weather with Graph Neural Networks](https://mlsanity.com/paper/2202.07575/) (2022)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Geometric Deep Learning on Molecular Representations](https://mlsanity.com/paper/2107.12375/) (2021)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs](https://mlsanity.com/paper/2411.05464/) (2024)
- [PTGB: Pre-Train Graph Neural Networks for Brain Network Analysis](https://mlsanity.com/paper/2305.14376/) (2023)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)

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

- [Neural Networks With Dense Weights Are Not Universal Approximators](https://mlsanity.com/paper/2602.07618/) (2026)

## Abstract (arXiv)

A recent paper, ``A Graphon-Signal Analysis of Graph Neural Networks'', by Levie, analyzed message passing graph neural networks (MPNNs) by embedding the input space of MPNNs, i.e., attributed graphs (graph-signals), into a space of attributed graphons (graphon-signals). Based on extensions of standard results in graphon analysis to graphon-signals, the paper proved a generalization bound and a sampling lemma for MPNNs. However, there are some missing ingredients in that paper, limiting its applicability in practical settings of graph machine learning. In the current paper, we introduce several refinements and extensions to existing results that address these shortcomings. In detail, 1) we extend the main results in the paper to graphon-signals with multidimensional signals (rather than 1D signals), 2) we extend the Lipschitz continuity to MPNNs with readout with respect to cut distance (rather than MPNNs without readout with respect to cut metric), 3) we improve the generalization bound by utilizing robustness-type generalization bounds, and 4) we extend the analysis to non-symmetric graphons and kernels.