Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations

Elia Cunegatti, Matteo Farina, Doina Bucur, Giovanni Iacca

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:

  1. Layer-wise Isolation: They analyze layers individually, ignoring how information flows from the input to the final output.
  2. 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.
Figure 1: Illustration of the proposed unrolled input-aware BGE with I = 3 × 3 × 3 and convolutional parameters (Cout = 2, Cin = 3, wker = 2, hker = 2, P = 0, S = 1). (I) and (II) show, respectively, the first and second convolutional steps and how the graph edges are generated assuming that all the kernel parameters are unmasked. (III) and (IV), respectively, show the complete graph representation after all the convolutional steps have been done in both the (III) dense and (IV) sparse cases.

From this graph, they extract 16 topometrics across five categories:

  1. Local Connectivity: Counting "sink" and "source" nodes (nodes that lead nowhere or receive no input).
  2. Neighbor Connectivity: Measuring how many nodes are reachable within $k$ hops.
  3. Strength Connectivity: Analyzing the "k-core" (maximal subgraphs with a certain degree).
  4. Global Connectivity: Identifying disconnected components.
  5. 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

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 Matteo Farina and Doina Bucur and Giovanni Iacca},
  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