# Convergence of Invariant Graph Networks

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

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (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)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations](https://mlsanity.com/paper/1710.10121/) (2017)
- [Deep Neural Networks Motivated by Partial Differential Equations](https://mlsanity.com/paper/1804.04272/) (2018)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020)

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

- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Graph neural networks and non-commuting operators](https://mlsanity.com/paper/2411.04265/) (2024)
- [Any-Dimensional Invariant Universality](https://mlsanity.com/paper/2605.23156/) (2026)
- [Heat Kernel Goes Topological](https://mlsanity.com/paper/2507.12380/) (2025)
- [On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks](https://mlsanity.com/paper/2510.03923/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks](https://mlsanity.com/paper/2605.00725/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## 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.