Research map / Graph learning / GNN architectures
Almost Surely Asymptotically Constant Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that outputs of real-valued GNN classifiers (MeanGNN, GAT, GPS+RW) converge almost surely to a constant on large random graphs (dense/sparse ER, SBM, Barabási-Albert), via a term language with weighted-mean aggregation and empirical validation.
Problem
Understanding how real-valued GNN classifiers behave as graph size grows on random graph models, and what they can uniformly express in the limit.
Approach
Introduces an aggregate term language with weighted-mean aggregation and proves an almost-sure elimination of aggregates (to Lipschitz functions of features and graph types or local neighbourhood types), implying that MeanGNN, GAT, and GPS+RW outputs become a.a.s. constant on ER, SBM, and BA random graphs.
Key results
- Every term in the Wmean+RW term language converges a.a.s. to a constant over dense/sparse ER, BA, and SBM random graph models, implying MeanGNN, GAT, and GPS+RW class probabilities converge a.a.s.
- Empirically, class probabilities of five randomly initialized MeanGNN, GAT, and GPS+RW models converge as graph sizes grow up to 10,000 nodes on ER, log-ER, sparse ER, BA and SBM graphs.
- Attention-based models (GAT, GPS+RW) show delayed convergence and higher standard deviation than MeanGNN; convergence also appears on the real-world TIGER-Alaska dataset, though slower.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply MeanGNN, GAT, or GPS+RW to increasingly large graphs | MeanGNN, GAT, and GPS+RW · Erdős–Rényi dense, logarithmic-growth, and sparse | class probability convergence | Helped |
| Use attention-based aggregation instead of regular mean aggregation | GAT and GPS+RW compared with MeanGNN · Random graph models | convergence speed | Hurt |
| Use attention-based aggregation instead of regular mean aggregation | GAT and GPS+RW compared with MeanGNN · Random graph models | standard deviation | Hurt |
| Change the graph distribution from dense or logarithmic-growth ER to sparse ER | MeanGNN, GAT, and GPS+RW · Erdős–Rényi graph models | eventual class probabilities | Mixed |
| Apply MeanGNN to graphs of increasing size | MeanGNN · TIGER-Alaska | standard deviation of class-probability distances | Helped |
Surprising findings
- Converged output is the same for dense and logarithmic-growth ER but differs for sparse ER.
- For arbitrary ER growth p(n) going to zero, convergence fails: a term can diverge in distribution.
Limitations
- Assumes i.i.d. bounded initial node features; loosening this would need further analysis.
- Convergence does not hold for sum aggregation or non-smooth functions, and not for ER with arbitrary p(n)->0.
- Experiments use randomly initialized, untrained models; real-world evidence on TIGER-Alaska is limited and converges more slowly.
Experimental setup
Datasets: TIGER-Alaska Erdos-Renyi random graphs Barabasi-Albert random graphs stochastic block model graphs
Benchmarks: TIGER-Alaska
Metrics: class probabilities convergence standard deviation of Euclidean distances to mean class prob
Builds on: Message passing neural networks Graph attention networks GPS graph transformer Zero-one laws for logic on random graphs
Closest papers by meaning
- On the Universality of Graph Neural Networks on Large Random Graphs (NeurIPS 2021 · similarity 0.93)
- What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding (NeurIPS 2023 · similarity 0.93)
- Position: Future Directions in the Theory of Graph Machine Learning (ICML 2024 · similarity 0.91)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.89)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.89)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.