Research map / Architectures and efficiency / RNNs and normalization
The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis
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.
Proposes the Graphon Limit Hypothesis that pruning masks of increasingly wide networks converge to pruning-specific graphons, and derives a Graphon NTK whose spectrum is linked (empirically, on MNIST MLPs) to faster early training of SNIP and Synflow subnetworks.
Problem
Understanding why some sparse subnetworks are more trainable than others at the same sparsity, since standard NTK/large-width limits are ill-defined for sparse networks whose size grows.
Approach
Model pruning masks as bipartite graphs whose sequences converge to graphons in cut distance as width grows; weights are then sampled with graphon-modulated variances, yielding a Graphon NTK that generalises the standard NTK (random pruning gives a constant graphon and a scaled NTK, c^L times the standard NTK).
Key results
- Random pruning converges to a constant graphon, and its Graphon NTK equals c^L times the standard NTK, so relative eigen-dynamics are unchanged.
- At the start of training, SNIP and Synflow subnetworks converge faster than Random subnetworks across sparsity levels on MNIST.
- SNIP and Synflow concentrate increasing NTK energy in top eigenvalues as sparsity grows, while Random keeps stable spectral properties.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SNIP instead of Random pruning at the same sparsity | 4-layer sparse networks · MNIST | early training loss reduction | Helped |
| Use Synflow instead of Random pruning at the same sparsity | 4-layer sparse networks · MNIST | early training loss reduction | Helped |
| Increase network width | Random, SNIP, GraSP, and Synflow pruning masks · Graphon-limit experiments | Euclidean distance to the reference density matrix | Helped |
| Increase sparsity level | SNIP and Synflow graphon NTKs · MNIST | energy concentration in top eigenvalues | Helped |
| Increase sparsity level | SNIP and Synflow graphon NTKs · MNIST | effective rank | Hurt |
| Use Random pruning rather than structured SNIP or Synflow pruning | 4-layer sparse networks · MNIST | early training loss reduction | Hurt |
| Use Random pruning, producing a constant graphon | Sparse networks · MNIST | Graphon NTK spectral properties across sparsity levels | No clear effect |
Surprising findings
- Random pruning's Graphon NTK is only a global downscaling of the standard NTK, so it reduces absolute learning speed without changing relative mode dynamics.
Limitations
- Graphon limit hypothesis is supported only empirically, without a formal proof of existence or uniqueness of limits.
- Analysis restricted to pruning at initialisation with fixed masks on MLPs; no dynamic pruning, CNNs or Transformers.
- Gap between infinite-width predictions and finite-width practice; no prescriptive pruning algorithm derived.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: training loss eigenvalue decay rate effective rank spectral gap top-5 energy concentration Euclidean distance between density matrices
Baselines: Random pruning SNIP GraSP Synflow
Builds on: neural tangent kernel graphon theory SAS graphon estimation lottery ticket hypothesis
Closest papers by meaning
- Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation (ICML 2026 · similarity 0.96)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.89)
- How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective (NeurIPS 2024 · similarity 0.88)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.88)
- Sparsest Models Elude Pruning: An Exposé of Pruning’s Current Capabilities (ICML 2024 · similarity 0.88)
- When narrower is better: the narrow width limit of Bayesian parallel branching neural networks (ICLR 2025 · similarity 0.87)
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.