Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation

摘要

Pruning at Initialisation methods discover sparse, trainable subnetworks before training, but their theoretical mechanisms remain elusive. Existing analyses are often limited to finite-width statistics, lacking a rigorous characterisation of the global sparsity patterns that emerge as networks grow large. In this work, we connect discrete pruning heuristics to graph limit theory via graphons, establishing the *graphon limit of PaI masks*. We introduce a *Factorised Saliency Model* that encompasses popular pruning criteria and prove that, under regularity conditions, the discrete masks generated by these algorithms converge to deterministic bipartite graphons. This limit framework establishes a novel topological taxonomy for sparse networks: while unstructured methods (e.g., Random, Magnitude) converge to homogeneous graphons representing uniform connectivity, data-driven methods (e.g., SNIP, GraSP) converge asymptotically to heterogeneous graphons that encode implicit feature selection. Leveraging this continuous characterisation, we derive two consequences. First, we prove a universal approximation theorem for sparse networks on active coordinate subspaces. Second, under the Graphon-NTK lazy-training regime, we connect the limiting graphon to NTK-style generalisation bounds and introduce a path-density interpretation of how sparse topology can modulate kernel alignment. Our results transform the study of sparse neural networks from combinatorial graph problems into a rigorous framework of continuous operators, offering a new mechanism for analysing expressivity and generalisation in sparse networks.