Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations

Elia Cunegatti, Doina Bucur, Giovanni Iacca, Iacca, Giovanni

Abstract

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.

Introduction

Pruning-at-Initialization (PaI) is a popular technique to create efficient, sparse neural networks before training even begins. While researchers have developed many ways to prune (e.g., SNIP, GraSP, Synflow), we still lack a deep understanding of what makes a specific sparse topology "good." Existing attempts to characterize SNNs rely on Bipartite Graph Encodings (BGEs)—representing each layer as a separate graph. However, these have two major flaws: they are input-agnostic, ignoring the actual dimensions of the input data, and they lack global context, analyzing layers in isolation.

The Multipartite Graph Encoding (MGE)

To address these limitations, we propose a novel Multipartite Graph Encoding (MGE). Unlike traditional BGEs, the MGE is "unrolled" and input-aware. Instead of treating convolutional kernels as abstract blocks, we construct a single multipartite graph where nodes represent actual activations (pixels in feature maps) and edges represent unmasked weights. This accounts for the spatial nature of convolutions, strides, and padding, and explicitly links consecutive layers—including complex structures like pooling and residual connections—to provide a holistic view of the network's "skeleton."

Visualization of the MGE process, showing how convolutional operations are unrolled into a graph structure.

Topological Analysis Framework

Using the MGE, we define 16 topological metrics (topometrics) categorized into five key areas: Local Connectivity, Neighbor Connectivity, Strength Connectivity, Global Connectivity, and Expansion. These metrics allow for a much finer-grained analysis of information flow than previous methods.

Key Insights

Our analysis of 1,260 SNNs across various configurations (CIFAR-10/100, Tiny-ImageNet, VGG, ResNet) revealed several critical insights:

  • The Density Trap: Ramanujan-based metrics, previously thought to be sophisticated predictors, are highly redundant with simple layer-wise density when using standard encodings. The MGE is required to extract truly rich information.
  • Sparsity Shifts Importance: The metrics that matter change as the network gets thinner. At lower sparsity (60-80%), "Strength" and "Neighbor" metrics are key. At extreme sparsity (>95%), "Local" and "Global" connectivity (like the number of sink nodes) become the primary predictors of performance failure.
  • Architecture Matters: In ResNets, Local Connectivity is the dominant predictor of accuracy drop. In wider, shallower models like Conv-6, Neighbor and Strength metrics take center stage.

Experimental Results

The proposed MGE significantly outperforms standard rolled encodings in predicting the accuracy drop of SNNs. For example, on Wide-Resnet-28-2, the MGE achieved an Adjusted-$R^2$ of 0.83, compared to just 0.70 for traditional bipartite encodings. Furthermore, a weighted mixture of our topometrics can rank PaI algorithms more effectively than Ramanujan-based metrics on most tested architectures.

Conclusion

This work demonstrates that an input-aware, end-to-end graph representation is essential for understanding the performance of sparse neural networks. By moving beyond layer-wise density and considering the spatial and global topology, we can better predict which pruning strategies will succeed. Future work will explore extending this framework to Transformers and deeper theoretical grounding for these empirical observations.

Summary updated

Abstract

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 \emph{how} to prune, we still do not know \emph{what topological metrics} of the SNNs characterize \emph{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 \emph{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 \emph{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.
BibTeX
@article{cunegatti2024understanding,
  author = {Elia Cunegatti and Doina Bucur and Giovanni Iacca and Iacca, Giovanni},
  title = {{Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations}},
  journal = {Accepted by TMLR},
  year = {2024},
  url = {https://openreview.net/forum?id=Egb0tUZnOY},
}
Figure