# Mean-field theory of graph neural networks in graph partitioning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2018.

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

- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [New Insights into Graph Convolutional Networks using Neural Tangent Kernels](https://mlsanity.com/paper/2110.04060/) (2021)
- [Multi-Factor Spatio-Temporal Prediction based on Graph Decomposition Learning](https://mlsanity.com/paper/2310.10374/) (2023)
- [Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters](https://mlsanity.com/paper/2111.03317/) (2021)
- [Graph-Convolutional Deep Learning to Identify Optimized Molecular Configurations](https://mlsanity.com/paper/2108.09637/) (2021)
- [Identification of Causal Relationship between Amyloid-beta Accumulation and Alzheimer's Disease Progression via Counterfactual Inference](https://mlsanity.com/paper/2307.01389/) (2023)
- [Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant](https://mlsanity.com/paper/2312.14847/) (2023)
- [Understanding and Guiding Weakly Supervised Entity Alignment with Potential Isomorphism Propagation](https://mlsanity.com/paper/2402.03025/) (2024)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Generated Contents Enrichment](https://mlsanity.com/paper/2405.03650/) (2024)
- [Learning to Control the Smoothness of Graph Convolutional Network Features](https://mlsanity.com/paper/2410.14604/) (2024)
- [Towards Comprehensive and Prerequisite-Free Explainer for Graph Neural Networks](https://mlsanity.com/paper/2505.14005/) (2025)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)

## Abstract (arXiv)

A theoretical performance analysis of the graph neural network (GNN) is presented. For classification tasks, the neural network approach has the advantage in terms of flexibility that it can be employed in a data-driven manner, whereas Bayesian inference requires the assumption of a specific model. A fundamental question is then whether GNN has a high accuracy in addition to this flexibility. Moreover, whether the achieved performance is predominately a result of the backpropagation or the architecture itself is a matter of considerable interest. To gain a better insight into these questions, a mean-field theory of a minimal GNN architecture is developed for the graph partitioning problem. This demonstrates a good agreement with numerical experiments.