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.
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.
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