Peeking inside Sparse Neural Networks using Multi-Partite Graph Representations

Elia Cunegatti, Doina Bucur, Giovanni Iacca

Abstract

Modern Deep Neural Networks (DNNs) have achieved very high performance at the expense of computational resources. To decrease the computational burden, several techniques have proposed to extract, from a given DNN, efficient subnetworks which are able to preserve performance while reducing the number of network parameters. The literature provides a broad set of techniques to discover such subnetworks, but few works have studied the peculiar topologies of such pruned architectures. In this paper, we propose a novel unrolled input-aware bipartite Graph Encoding (GE) that is able to generate, for each layer in an either sparse or dense neural network, its corresponding graph representation based on its relation with the input data. We also extend it into a multipartite GE, to capture the relation between layers. Then, we leverage on topological properties to study the difference between the existing pruning algorithms and algorithm categories, as well as the relation between topologies and performance.

Introduction

Pruning-at-Initialization (PaI) is a critical technique for finding efficient "winning ticket" subnetworks within large, randomly initialized models. Despite the proliferation of pruning algorithms, our understanding of the topological properties that drive performance remains limited. Traditional graph-theoretic analyses typically rely on "rolled" Bipartite Graph Encodings (BGEs) where nodes represent entire channels. However, these models are often input-agnostic and fail to capture the end-to-end flow of information. Furthermore, existing "gold standard" topological metrics, such as those based on Ramanujan properties, are often highly correlated with simple layer density, offering little additional explanatory power.

Proposed Methodology: Unrolled Multipartite Graph Encoding

To address these limitations, this research introduces an Unrolled Input-Aware Multipartite Graph Encoding (MGE). Unlike traditional methods, this approach "unrolls" the network so that each node represents an individual element in a feature map (e.g., a specific pixel location). This granularity allows the model to account for convolutional strides, pooling operations, and residual connections.

Visualization of the unrolled input-aware graph encoding process, showing how feature maps are mapped to bipartite and multipartite graphs.

By linking these unrolled layers, the authors create a single multipartite graph representing the entire network. From this representation, they derive 16 "topometrics" categorized into five distinct connectivity types: Local, Neighbor, Strength, Global, and Expansion.

Summary of the 16 topometrics categorized by connectivity type and their computational complexity.

Experimental Results and Insights

The researchers evaluated their approach using standard benchmarks (CIFAR-10, CIFAR-100, Tiny-ImageNet) across various architectures (Conv-6, Resnet-20/32, Wide-Resnet-28-2) and pruning methods (SNIP, GraSP, Synflow, ProsPr).

Superior Performance Prediction

The MGE-based topometrics achieved significantly higher accuracy in predicting the performance drop of sparse networks. Their model reached an Adjusted-R² of up to 0.83, a massive improvement over the 0.28 achieved by traditional rolled graph encodings. Additionally, the "topometric mixture" improved algorithm ranking accuracy by approximately 30% on deeper models like Resnet-32.

Key Topological Findings

  • The Density Trap: The study confirms that Ramanujan-based metrics are largely redundant with layer density. The MGE approach avoids this by focusing on the specific spatial distribution of weights.
  • Sparsity-Dependent Metrics: The importance of specific metrics shifts with network density. At 60-80% sparsity, "Strength" and "Neighbor" connectivity are the best predictors. At extreme sparsity (98%+), "Local" and "Global" connectivity become essential to identify networks at risk of topological collapse.
  • Identifying "Dead" Parameters: The MGE successfully identifies "removable" connections—edges that are technically present but functionally useless because they lead to sink nodes or originate from disconnected sources.

Conclusion

By moving to an unrolled, input-aware graph representation, this work provides a more accurate and nuanced understanding of Sparse Neural Network topology. While the computational cost of unrolling is higher than channel-based methods, the resulting topometrics offer unprecedented predictive power for network performance. Future research will focus on extending these principles to dynamic architectures like Transformers.

Summary updated

Abstract

Modern Deep Neural Networks (DNNs) have achieved very high performance at the expense of computational resources. To decrease the computational burden, several techniques have proposed to extract, from a given DNN, efficient subnetworks which are able to preserve performance while reducing the number of network parameters. The literature provides a broad set of techniques to discover such subnetworks, but few works have studied the peculiar topologies of such pruned architectures. In this paper, we propose a novel \emph{unrolled input-aware} bipartite Graph Encoding (GE) that is able to generate, for each layer in an either sparse or dense neural network, its corresponding graph representation based on its relation with the input data. We also extend it into a multipartite GE, to capture the relation between layers. Then, we leverage on topological properties to study the difference between the existing pruning algorithms and algorithm categories, as well as the relation between topologies and performance.
BibTeX
@article{cunegatti2024peeking,
  author = {Elia Cunegatti and Doina Bucur and Giovanni Iacca},
  title = {{Peeking inside Sparse Neural Networks using Multi-Partite Graph Representations}},
  journal = {Accepted by TMLR},
  year = {2024},
  url = {https://openreview.net/forum?id=Egb0tUZnOY},
}
Figure