Mean-field theory of graph neural networks in graph partitioning

Abstract

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.

arXiv comment16 pages, 6 figures, Thirty-second Conference on Neural Information Processing Systems (NIPS2018)

References in corpus (23)

• Adam: A Method for Stochastic Optimization
• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Semi-Supervised Classification with Graph Convolutional Networks
• Finding community structure in networks using the eigenvectors of matrices
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Spectral Networks and Locally Connected Networks on Graphs
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Learning Convolutional Neural Networks for Graphs
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Exponential expressivity in deep neural networks through transient chaos
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Estimating the number of communities in a network
• Modeling Relational Data with Graph Convolutional Networks
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Deep Information Propagation
• Algorithmic detectability threshold of the stochastic block model
• Detectability of the spectral method for sparse graph partitioning

Cited by in corpus (5)

• Applying Convolutional Neural Networks to Data on Unstructured Meshes with Space-Filling Curves
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant
• Graph-Convolutional Deep Learning to Identify Optimized Molecular Configurations
• Detectability threshold in weighted modular networks
• New Insights into Graph Convolutional Networks using Neural Tangent Kernels