# Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 11 Oct 2023.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Improving Graph Neural Networks with Simple Architecture Design](https://mlsanity.com/paper/2105.07634/) (2021)
- [Representation Learning of Histopathology Images using Graph Neural Networks](https://mlsanity.com/paper/2004.07399/) (2020)
- [Stochastic Blockmodels meet Graph Neural Networks](https://mlsanity.com/paper/1905.05738/) (2019)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Grale: Designing Networks for Graph Learning](https://mlsanity.com/paper/2007.12002/) (2020)
- [Graph Neural Networks Use Graphs When They Shouldn't](https://mlsanity.com/paper/2309.04332/) (2023)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Configuring Random Graph Models with Fixed Degree Sequences](https://mlsanity.com/paper/1608.00607/) (2016)

## Abstract (arXiv)

We analyze the performance of graph neural network (GNN) architectures from the perspective of random graph theory. Our approach promises to complement existing lenses on GNN analysis, such as combinatorial expressive power and worst-case adversarial analysis, by connecting the performance of GNNs to typical-case properties of the training data. First, we theoretically characterize the nodewise accuracy of one- and two-layer GCNs relative to the contextual stochastic block model (cSBM) and related models. We additionally prove that GCNs cannot beat linear models under certain circumstances. Second, we numerically map the recoverability thresholds, in terms of accuracy, of four diverse GNN architectures (GCN, GAT, SAGE, and Graph Transformer) under a variety of assumptions about the data. Sample results of this second analysis include: heavy-tailed degree distributions enhance GNN performance, GNNs can work well on strongly heterophilous graphs, and SAGE and Graph Transformer can perform well on arbitrarily noisy edge data, but no architecture handled sufficiently noisy feature data well. Finally, we show how both specific higher-order structures in synthetic data and the mix of empirical structures in real data have dramatic effects (usually negative) on GNN performance.