# Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 59 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 30 of 39)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training](https://mlsanity.com/paper/2202.02643/) (2022)
- [Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win](https://mlsanity.com/paper/2010.03533/) (2020)
- [Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology](https://mlsanity.com/paper/1812.09764/) (2018)
- [Graph Structure of Neural Networks](https://mlsanity.com/paper/2007.06559/) (2020)
- [Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot](https://mlsanity.com/paper/2009.11094/) (2020)
- [Progressive Skeletonization: Trimming more fat from a network at initialization](https://mlsanity.com/paper/2006.09081/) (2020)
- [The Difficulty of Training Sparse Neural Networks](https://mlsanity.com/paper/1906.10732/) (2019)
- [Prospect Pruning: Finding Trainable Weights at Initialization using Meta-Gradients](https://mlsanity.com/paper/2202.08132/) (2022)
- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [NTK-SAP: Improving neural network pruning by aligning training dynamics](https://mlsanity.com/paper/2304.02840/) (2023)
- [Why Random Pruning Is All We Need to Start Sparse](https://mlsanity.com/paper/2210.02412/) (2022)

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

- [2SSP: A Two-Stage Framework for Structured Pruning of LLMs](https://mlsanity.com/paper/2501.17771/) (2025)
- [Zeroth-Order Adaptive Neuron Alignment Based Pruning without Re-Training](https://mlsanity.com/paper/2411.07066/) (2024)

## Abstract (arXiv)

Pruning-at-Initialization (PaI) algorithms provide Sparse Neural Networks (SNNs) which are computationally more efficient than their dense counterparts, and try to avoid performance degradation. While much emphasis has been directed towards how to prune, we still do not know what topological metrics of the SNNs characterize good performance. From prior work, we have layer-wise topological metrics by which SNN performance can be predicted: the Ramanujan-based metrics. To exploit these metrics, proper ways to represent network layers via Graph Encodings (GEs) are needed, with Bipartite Graph Encodings (BGEs) being the de-facto standard at the current stage. Nevertheless, existing BGEs neglect the impact of the inputs, and do not characterize the SNN in an end-to-end manner. Additionally, thanks to a thorough study of the Ramanujan-based metrics, we discover that they are only as good as the layer-wise density as performance predictors, when paired with BGEs. To close both gaps, we design a comprehensive topological analysis for SNNs with both linear and convolutional layers, via (i) a new input-aware Multipartite Graph Encoding (MGE) for SNNs and (ii) the design of new end-to-end topological metrics over the MGE. With these novelties, we show the following: (a) The proposed MGE allows to extract topological metrics that are much better predictors of the accuracy drop than metrics computed from current input-agnostic BGEs; (b) Which metrics are important at different sparsity levels and for different architectures; (c) A mixture of our topological metrics can rank PaI algorithms more effectively than Ramanujan-based metrics. The codebase is publicly available at https://github.com/eliacunegatti/mge-snn.