mlsanityData to 7 Oct 2026

Limits, approximation and size transferability for GNNs on sparse graphs via graphops

arXiv 2306.04495 ↗First posted 7 Jun 2023cs.LG cs.SIcited by 17

Not on the map. Why?

Abstract (arXiv)

Can graph neural networks generalize to graphs that are different from the graphs they were trained on, e.g., in size? In this work, we study this question from a theoretical perspective. While recent work established such transferability and approximation results via graph limits, e.g., via graphons, these only apply non-trivially to dense graphs. To include frequently encountered sparse graphs such as bounded-degree or power law graphs, we take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. This leads to the recently introduced limit notion of graphops (Backhausz and Szegedy, 2022). We demonstrate how the operator perspective allows us to develop quantitative bounds on the distance between a finite GNN and its limit on an infinite graph, as well as the distance between the GNN on graphs of different sizes that share structural properties, under a regularity assumption verified for various graph sequences. Our results hold for dense and sparse graphs, and various notions of graph limits.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 25 of its 45 references that are in the map. First posted on arXiv 7 Jun 2023.

Builds on

25 of 45 references.

References · 25

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2019Provably Powerful Graph Networkscited by 385
  7. 2020Can Graph Neural Networks Count Substructures?cited by 235
  8. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  9. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  10. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  11. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  12. 2019What Can Neural Networks Reason About?cited by 155
13 more
  1. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  2. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  3. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  4. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  5. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  6. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  7. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  8. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  9. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  10. 2021Transferability Properties of Graph Neural Networkscited by 42
  11. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  12. 2022On Local Distributions in Graph Signal Processingcited by 6
  13. 2022A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 4; 2026: 5.

17 papers.

Sort:

By area:

  1. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  2. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  3. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  4. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
  5. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  6. 2024Graph neural networks and non-commuting operatorscited by 5
  7. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  8. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  9. 2023A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphscited by 1
  10. 2025From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputscited by 1
  11. 2026Manifold limit for the training of shallow graph convolutional neural networkscited by 1
  12. 2026Any-Dimensional Learning by Samplingcited by 1
5 more
  1. 2024The Transferability of Downsamped Sparse Graph Convolutional Networkscited by 0
  2. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 0
  3. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  4. 2026Learning to Approximate Uniform Facility Location via Graph Neural Networkscited by 0
  5. 2026Limit Analysis of Graph Neural Networks with Wireless Conflict Graphscited by 0