mlsanityData to 7 Oct 2026

Convergence of Invariant Graph Networks

arXiv 2201.10129 ↗First posted 25 Jan 2022cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Although theoretical properties such as expressive power and over-smoothing of graph neural networks (GNN) have been extensively studied recently, its convergence property is a relatively new direction. In this paper, we investigate the convergence of one powerful GNN, Invariant Graph Network (IGN) over graphs sampled from graphons. We first prove the stability of linear layers for general k-IGN (of order k) based on a novel interpretation of linear equivariant layers. Building upon this result, we prove the convergence of k-IGN under the model of citetruiz2020graphon, where we access the edge weight but the convergence error is measured for graphon inputs. Under the more natural (and more challenging) setting of citetkeriven2020convergence where one can only access 0-1 adjacency matrix sampled according to edge probability, we first show a negative result that the convergence of any IGN is not possible. We then obtain the convergence of a subset of IGNs, denoted as IGN-small, after the edge probability estimation. We show that IGN-small still contains function class rich enough that can approximate spectral GNNs arbitrarily well. Lastly, we perform experiments on various graphon models to verify our statements.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 37 of its 54 references that are in the map. First posted on arXiv 25 Jan 2022.

Builds on

37 of 54 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2018Neural Ordinary Differential Equationscited by 3,733
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  10. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  11. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  12. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
25 more
  1. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  2. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  3. 2019Provably Powerful Graph Networkscited by 385
  4. 2018Invariant and Equivariant Graph Networkscited by 339
  5. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  7. 2017Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equationscited by 203
  8. 2018Deep Neural Networks Motivated by Partial Differential Equationscited by 187
  9. 2021A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groupscited by 185
  10. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  11. 2021Equivariant Subgraph Aggregation Networkscited by 154
  12. 2019On the Universality of Invariant Networkscited by 151
  13. 2019Stability Properties of Graph Neural Networkscited by 125
  14. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  15. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  16. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  17. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  18. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
  19. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  20. 2020The expressive power of kth-order invariant graph networkscited by 34
  21. 2015Estimating network edge probabilities by neighborhood smoothingcited by 28
  22. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  23. 2019Incidence Networks for Geometric Deep Learningcited by 17
  24. 2017Surface Networkscited by 14
  25. 2016Graphons, mergeons, and so on!cited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 2; 2025: 3; 2026: 2.

8 papers.

  1. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  2. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  3. 2024Graph neural networks and non-commuting operatorscited by 5
  4. 2025Heat Kernel Goes Topologicalcited by 1
  5. 2025From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputscited by 1
  6. 2026Any-Dimensional Invariant Universalitycited by 1
  7. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 0
  8. 2026Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networkscited by 0