# A Graph Sufficiency Perspective for Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 55 references that are in the map.
- First posted on arXiv 14 Jul 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [Understanding Deep Convolutional Networks](https://mlsanity.com/paper/1601.04920/) (2016)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Rethinking Minimal Sufficient Representation in Contrastive Learning](https://mlsanity.com/paper/2203.07004/) (2022)
- [The Information Bottleneck Problem and Its Applications in Machine Learning](https://mlsanity.com/paper/2004.14941/) (2020)
- [Convolutional Neural Networks Analyzed via Convolutional Sparse Coding](https://mlsanity.com/paper/1607.08194/) (2016)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery](https://mlsanity.com/paper/2405.12797/) (2024)
- [Deep Sufficient Representation Learning via Mutual Information](https://mlsanity.com/paper/2207.10772/) (2022)
- [Neural Networks Perform Sufficient Dimension Reduction](https://mlsanity.com/paper/2412.19033/) (2024)
- [Principal Graph Encoder Embedding and Principal Community Detection](https://mlsanity.com/paper/2501.14939/) (2025)

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

- [Decision Tree Embedding by Leaf-Means](https://mlsanity.com/paper/2512.01819/) (2025)

## Abstract (arXiv)

This paper analyzes neural networks through graph variables and statistical sufficiency. We interpret neural network layers as graph-based transformations, where neurons act as pairwise functions between inputs and learned anchor points. Within this formulation, we establish conditions under which layer outputs are sufficient for the layer inputs, that is, each layer preserves the conditional distribution of the target variable given the input variable. We explore two theoretical paths under this graph-based view. The first path assumes dense anchor points and shows that asymptotic sufficiency holds in the infinite-width limit and is preserved throughout training. The second path, more aligned with practical architectures, proves exact or approximate sufficiency in finite-width networks by assuming region-separated input distributions and constructing appropriate anchor points. This path can ensure the sufficiency property for an infinite number of layers, and provide error bounds on the optimal loss for both regression and classification tasks using standard neural networks. Our framework covers fully connected layers, general pairwise functions, ReLU and sigmoid activations, and convolutional neural networks. Overall, this work bridges statistical sufficiency, graph-theoretic representations, and deep learning, providing a new statistical understanding of neural networks.