Sparse neural networks (SNNs) are the "lean" version of deep learning, offering massive efficiency gains by removing unnecessary weights. While we have plenty of algorithms to create these networks—specifically through Pruning-at-Initialization (PaI)—we’ve lacked a deep understanding of what makes one sparse topology better than another.
This paper, published in TMLR, introduces a new way to look at these networks: not as a collection of weight matrices, but as a single, end-to-end Multipartite Graph Representation.
TL;DR
The authors propose a novel Multipartite Graph Encoding (MGE) that represents sparse neural networks in an input-aware, end-to-end manner. By moving beyond simple layer-wise metrics, they develop "topometrics" that significantly outperform existing methods in predicting accuracy drops and ranking pruning algorithms.
What Problem Does This Paper Address?
Pruning-at-Initialization (PaI) is a "holy grail" in efficiency because it identifies the "winning ticket" subnetwork before training even begins. However, researchers haven't been able to pinpoint exactly which topological features lead to high accuracy.
Existing state-of-the-art metrics, often based on Ramanujan graph theory, suffer from two major flaws:
- Layer-wise Isolation: They analyze layers individually, ignoring how information flows from the input to the final output.
- Input Agnosticism: They ignore the actual dimensionality of the input data. For Convolutional Neural Networks (CNNs), the connectivity depends heavily on the input resolution and stride/padding.
The authors discovered a startling "aha moment": current Ramanujan-based metrics are often no more informative than simply measuring the layer density (the percentage of remaining weights). If a metric doesn't tell you more than a simple count of weights, it isn't capturing the "topology" in a meaningful way.
Methods
The core innovation is the Multipartite Graph Encoding (MGE). Unlike standard bipartite encodings that just map input channels to output channels, MGE "unrolls" the entire network.
- Input-Aware Unrolling: Every pixel in a feature map becomes a node. Edges are created based on the actual convolutional kernel's application.
- End-to-End Connectivity: The output nodes of layer $l$ are the input nodes of layer $l+1$. This creates a continuous graph from the input image to the final classification.
- Handling Complexity: The authors developed specific ways to encode pooling layers and residual connections (skips), which are vital for modern architectures like ResNet.
From this graph, they extract 16 topometrics across five categories:
- Local Connectivity: Counting "sink" and "source" nodes (nodes that lead nowhere or receive no input).
- Neighbor Connectivity: Measuring how many nodes are reachable within $k$ hops.
- Strength Connectivity: Analyzing the "k-core" (maximal subgraphs with a certain degree).
- Global Connectivity: Identifying disconnected components.
- Expansion: Spectral properties of the graph's adjacency and Laplacian matrices.
Datasets
The authors evaluated their approach using a massive pool of 1,260 sparse architectures across:
- Datasets: CIFAR-10, CIFAR-100, and Tiny-ImageNet.
- Architectures: Conv-6, ResNet-20, ResNet-32, and Wide-ResNet-28-2.
- Pruning Algorithms: Four PaI methods (SNIP, GraSP, Synflow, ProsPr) and three random baselines (Uniform, ER, ERK).
Key Insights and Ideas
- Connectivity Shifts with Sparsity: At lower sparsity (more weights), "Strength" and "Neighbor" connectivity are the best predictors of performance. However, as networks become extremely sparse (98%+), "Local" and "Global" connectivity become dominant. Essentially, at high sparsity, the main problem is simply keeping the graph connected.
- Architecture Matters: Shallow networks (like Conv-6) are less sensitive to these end-to-end metrics, likely because their "path" is too short for complex topology to emerge. In contrast, deep ResNets are highly dependent on these global topological features.
- The "Topometric Mixture": No single metric explains everything. The authors found that a weighted combination of their metrics (a "mixture") is required to accurately rank which pruning algorithm will perform best in a given scenario.
Key Results
The MGE-based metrics proved to be far superior to existing baselines:
- Predictive Power: In regression tasks to predict the "accuracy drop" of an SNN, MGE metrics achieved an Adjusted-$R^2$ of ~0.59, compared to just ~0.19 for standard bipartite encodings at 90% sparsity.
- Algorithm Ranking: Their "topometric mixture" outperformed all other strategies (including Ramanujan metrics and layer density) in ranking PaI algorithms on 3 out of 4 architectures, improving ranking accuracy by roughly 30% for deeper models.
Limitations and Future Work
- Computational Cost: Generating these unrolled graphs is memory-intensive. The space complexity is $O(L + R + E)$, which grows with the number of pixels and weights.
- Scope: The current work focuses on CNNs and PaI. The authors note that extending this to Transformers and Dynamic Sparse Training (where the topology changes during training) is a necessary next step.
- Theoretical Gap: While the results are empirically strong, a formal theoretical link between these graph metrics and generalization bounds remains an open research question.
For those interested in the implementation, the authors have released their codebase at github.com/eliacunegatti/mge-snn.
Summary updated