The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis

AI summary

Overview

Research area: Deep learning theory — neural network pruning, infinite-width limits, neural tangent kernels, and graph limit theory (graphons).

Technical level: Advanced. The paper assumes familiarity with the neural tangent kernel (NTK), measure-theoretic notions of graph convergence (cut distance, homomorphism densities), and Gaussian process limits of wide networks.

Scope: The paper proposes that pruning masks of increasingly wide networks converge to graphons, derives a Graphon Neural Tangent Kernel from that limit, and empirically links its spectral properties to the training speed of sparse subnetworks. (The provided content is truncated mid-sentence in Section 6, so the concluding section's full details are not available here.)

What This Paper Is About

Pruning can produce two sparse networks with exactly the same sparsity level that train very differently, and no general theory explains why. The authors argue that the answer lies in connectivity structure: as network width grows, the binary masks produced by a given pruning method converge, layer by layer, to a limiting object called a graphon that acts as a structural "fingerprint" of that method. They then use this graphon to build an infinite-width kernel (the Graphon NTK) whose spectrum predicts how fast the resulting sparse network trains.

Key Contributions

1. Graphon Limit Hypothesis. The authors introduce the idea that each Pruning-at-Initialisation (PaI) method defines sequences of binary mask matrices $(M_n^{(l)})$ that converge layer-wise to deterministic graphons $\mathcal{W}^{(l)}$ in cut distance as width $n \to \infty$, and they provide empirical evidence of structural convergence for four pruning methods.

2. Graphon Neural Tangent Kernel (Graphon NTK). They formalise a kernel that combines pruning structure with infinite-width analysis, showing (Proposition 1) that pre-activations converge to centred Gaussian processes with position-dependent covariance, and (Theorem 1) that the Graphon NTK converges to a deterministic kernel shaped by the graphon functions.

3. Recovery of Random Pruning as a special case. For a constant graphon $\mathcal{W}(u,v)=c$ with $c \in (0,1]$, the Graphon NTK reduces to $c^{L},\Theta_{\text{std}}(x,x')$, where $\Theta_{\text{std}}$ is the standard NTK of a fully-connected network with $L$ hidden layers — generalising the earlier result that Random Pruning preserves the NTK up to a scaling factor.

4. Empirical link between kernel spectrum and training dynamics. They show that spectral metrics of the Graphon NTK (eigenvalue decay rate, effective rank, spectral gap, top-5 energy concentration) correlate with the observed convergence behaviour of sparse networks produced by Random, SNIP, and Synflow.

Main Findings

• Each pruning method has a distinct limiting graphon. Across widths $n \in {100, 500, 1000, 2000}$, layers ${4, 5}$, sparsity levels ${70%, 80%, 90%}$, and 100 independent trials per configuration, the estimated graphons become progressively more stable and method-specific.

• Random Pruning converges to a constant graphon. Its limit corresponds to an Erdős–Rényi random graph with uniform connection probability across all node positions.

• SNIP and GraSP produce structured, non-uniform graphons with density gradients that preferentially connect high-centrality nodes.

• Synflow converges to a block-like graphon with sharp transitions, strongly prioritising connections among high-centrality neurons; the authors note this encourages sparse networks with a high number of paths.

• Convergence is monotonic. Using Euclidean distance between density matrices at width $n$ and reference matrices at $n = 2000$ as a proxy for cut distance, all four methods show distances decreasing as width increases.

• Graphon NTK energy concentrates differently by method. Random Pruning keeps relatively consistent spectral properties across sparsity levels (stable decay rate, high effective rank, broad spectral spread), consistent with the constant-graphon analysis where pruning is a global downscaling of the kernel. SNIP and Synflow increasingly concentrate Graphon NTK energy in top eigenvalues as sparsity grows, despite reduced effective rank and spectral gaps.

• Spectral concentration tracks faster early training. In the first 200 gradient update steps, subnetworks generated by SNIP and Synflow show faster convergence than Random across sparsity levels. The authors state that the observed correlation between kernel spectral properties and training dynamics (the sentence is cut off in the provided content) supports the framework.

• Random pruning slows learning but does not reorder modes. Since each eigenvalue scales as $c^{L}\lambda_k$, absolute learning speed decreases while relative dynamics between modes are unchanged, offering a principled explanation for why sparse random networks converge more slowly than dense counterparts.

Methodology in Plain English

The authors reinterpret a pruning mask — a binary matrix saying which weights survive — as the adjacency matrix of a bipartite graph between two adjacent layers. Graph limit theory says that a growing sequence of graphs can converge to a continuous limit object, a graphon, a symmetric function $\mathcal{W}(x,y)$ giving the probability of an edge between nodes at positions $x$ and $y$. To test whether real masks behave this way, they train mask-generating procedures on networks of increasing width, estimate the graphon from repeated samples using the SAS graphon-estimation method (sorting nodes by degree centrality, then averaging edge density over a grid of intervals), and track how close each estimated graphon is to a reference graphon from the widest network.

They then define a network whose weight variances are modulated by graphon values, $W_{ij}^{(l)} \sim \mathcal{N}(0, \mathcal{W}^{(l)}(i/n_l, j/n_{l-1}))$, with $\sigma_w^2 = 1$, no bias terms, and a single output. The weights become independent but not identically distributed, so the authors impose boundedness and average-connectivity assumptions for the Law of Large Numbers, plus the Lindeberg–Feller condition for the Central Limit Theorem. Under these conditions they derive the limiting covariance recursions and the Graphon NTK, then numerically compute the kernel for 4-layer networks of hidden size $n = 1024$ using a batch of 1024 MNIST samples from 10 classes, and compare four spectral metrics against training loss curves for Random, SNIP, and Synflow at sparsity levels from 50% to 95%.

Why This Matters

Impact on research. The work offers a unifying language for pruning methods: instead of comparing heuristics, researchers can compare the graphon — and the resulting kernel spectrum — that each method induces. It generalises prior infinite-width analyses of randomly pruned networks to arbitrary pruning patterns, and it reframes "why is this sparse network hard to train" as a question about connectivity structure that is mathematically tractable. The paper states that no prior work has connected graphons to pruning behaviour in neural networks, and distinguishes its kernel from the graphon NTK studied for graph data by noting that this one concerns the model's own weight graph rather than an input graph.

Real-world applications (these follow the paper's stated motivation around resource-constrained deployment; the paper does not report deployed systems):

• Compressing models for mobile and edge devices.
• Embedded systems with tight memory and compute budgets.
• Real-time applications where inference latency is critical.
• General efficiency-motivated pruning pipelines, where choosing among PaI methods at a fixed sparsity would otherwise be a purely empirical decision.

Industry relevance. Practitioners who must pick a Pruning-at-Initialisation method before training begins can, in principle, use graphon and Graphon NTK spectra as a cheap guide to which structure will train fastest at a given sparsity, rather than running full train-prune-retrain cycles.

Future Directions

• Formal proof of the Graphon Limit Hypothesis. The authors present the hypothesis with empirical support (monotonic convergence of density-matrix distances across widths); a full theoretical guarantee for arbitrary pruning methods remains open.

• Extending the Graphon NTK beyond fully-connected, bias-free, single-output layers. The current derivation assumes Lipschitz nonlinearity, no bias terms, $\sigma_w^2 = 1$, and a single output, so convolutional, residual, and attention-based architectures are outside the analysis as presented.

• Covering pruning regimes beyond Pruning at Initialisation. The empirical graphon study covers Random, SNIP, GraSP, and Synflow at initialisation; whether iterative pruning, post-training pruning, and dynamic sparse training induce stable graphon limits is not established.

• Larger-scale validation. The training-dynamics experiments use 4-layer networks of hidden size $n = 1024$ on MNIST at sparsity levels from 50% to 95%; the paper does not report results on larger or more varied benchmarks.

• Designing pruning methods from graphons. If a pruning method corresponds to a distinct region in graphon space, one could target favourable kernel spectra (for example, higher energy concentration in top eigenvalues) when constructing masks.

Target Audience

Theoretical machine learning researchers working on pruning, sparsity, and infinite-width limits; readers already comfortable with the NTK literature and graph limit theory; and engineers who select pruning methods for efficiency-constrained deployment and want a principled reason why two equally sparse networks behave so differently.

Authors’ abstract

Sparse neural networks promise efficiency, yet training them effectively remains a fundamental challenge. Despite advances in pruning methods that create sparse architectures, understanding why some sparse structures are better trainable than others with the same level of sparsity remains poorly understood. Aiming to develop a systematic approach to this fundamental problem, we propose a novel theoretical framework based on the theory of graph limits, particularly graphons, that characterizes sparse neural networks in the infinite-width regime. Our key insight is that connectivity patterns of sparse neural networks induced by pruning methods converge to specific graphons as networks' width tends to infinity, which encodes implicit structural biases of different pruning methods. We postulate the Graphon Limit Hypothesis and provide empirical evidence to support it. Leveraging this graphon representation, we derive a Graphon Neural Tangent Kernel (Graphon NTK) to study the training dynamics of sparse networks in the infinite width limit. Graphon NTK provides a general framework for the theoretical analysis of sparse networks. We empirically show that the spectral analysis of Graphon NTK correlates with observed training dynamics of sparse networks, explaining the varying convergence behaviours of different pruning methods. Our framework provides theoretical insights into the impact of connectivity patterns on the trainability of various sparse network architectures.