A Note on Graphon-Signal Analysis of Graph Neural Networks
Not on the map. Why?
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), to 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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 27 of its 41 references that are in the map. First posted on arXiv 25 Aug 2025.
Builds on
27 of 41 references.
References · 27
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2019Graph Neural Networks for Social Recommendationcited by 711
- 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
- 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
- 2022Forecasting Global Weather with Graph Neural Networkscited by 165
15 more
- 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
- 2021Geometric Deep Learning on Molecular Representationscited by 113
- 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
- 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
- 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
- 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
- 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
- 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
- 2023A graphon-signal analysis of graph neural networkscited by 29
- 2023Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problemscited by 24
- 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
- 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
- 2024Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphscited by 13
- 2023PTGB: Pre-Train Graph Neural Networks for Brain Network Analysiscited by 10
- 2024Learning on Large Graphs using Intersecting Communitiescited by 8
Built on by
Citing papers per year: 2026: 1.
1 paper.