Zeroth-Order Topological Insights into Iterative Magnitude Pruning

Aishwarya H. Balwani, Jakob Krzyston

Abstract

Iterative Magnitude Pruning (IMP) is a cornerstone of neural network compression, yet the theoretical justification for why weight magnitude serves as an effective proxy for importance remains elusive. This paper provides a mathematically rigorous explanation using Topological Data Analysis (TDA). By focusing on zeroth-order homology, the authors demonstrate that IMP succeeds because it preserves the "topological skeleton"—the Maximum Spanning Tree (MST)—of a network's connectivity. This preservation ensures that essential information flow remains intact even under extreme pruning ratios. We explore the theoretical bounds of this connectivity and introduce Topological-IMP (T-IMP), a method that explicitly protects these critical structures.

1. Introduction

Deep Neural Networks (DNNs) are characterized by significant over-parameterization, which, while beneficial for optimization, results in prohibitive memory and energy costs. Pruning techniques, particularly Iterative Magnitude Pruning (IMP), have emerged as the standard for reducing model size. IMP operates on a simple heuristic: train a network, remove weights with the smallest absolute values, and repeat.

Despite its empirical dominance, the relationship between weight magnitude and functional importance is not fully understood. This research bridges that gap by applying tools from Topology to analyze the "shape" of information flow within a network. The authors argue that the success of IMP is not coincidental but is rooted in the preservation of the network's fundamental connectivity.

2. Theoretical Framework: Zeroth-Order Topology

The study leverages Persistent Homology, a branch of TDA, to quantify structural complexity. The analysis specifically focuses on Zeroth-Order Topology, which describes the connectivity of components within a graph.

By treating a neural network layer as a weighted graph and applying a "filtration" process—gradually adding edges from the strongest weights to the weakest—the authors can track how connected components emerge and merge. A key theoretical contribution of this work is the proof that all zeroth-order topological information of a layer is encapsulated in its Maximum Spanning Tree (MST). The MST represents the minimal set of the strongest weights required to keep all neurons in a layer connected, serving as the functional "skeleton" of the architecture.

3. Why Magnitude Pruning Works

The most significant insight of this research is that high-magnitude weights are statistically much more likely to be members of the MST. When IMP removes low-magnitude weights, it inadvertently (but effectively) protects the MST.

As long as this topological skeleton is preserved, the network maintains a "sufficiently informative initialization." This allows the pruned model to be retrained to high accuracy even after losing more than 90% of its original parameters. The authors demonstrate that the overlap between high-magnitude weights and the MST is far beyond what would be expected by chance; for certain layers, the probability of such an overlap occurring randomly is as low as $10^{-79}$, suggesting that the training process actively forces functionally critical weights to attain higher magnitudes.

4. Quantifying Redundancy and T-IMP

The paper introduces the Topologically Critical Compression Ratio ($\eta_\tau$), a metric defining the maximum pruning limit a layer can sustain while guaranteeing the preservation of its MST. This metric reveals a stark contrast in redundancy across different layer types:

  • Fully Connected (Dense) Layers: These layers exhibit massive redundancy. In architectures like VGG11, dense layers can often be compressed by over 80x (and in some simulations, up to 500x) without losing zeroth-order topological features.
  • Convolutional Layers: These are significantly more sensitive. For the same VGG11 model on CIFAR-100, convolutional layers could only be compressed by approximately 4x before risking topological breakdown.

Based on these findings, the authors propose Topological-IMP (T-IMP). Unlike standard IMP, T-IMP explicitly identifies and protects the weights forming the MST, ensuring connectivity is maintained regardless of magnitude, and then prunes the remaining weights based on their absolute values.

5. Experimental Validation

The researchers validated their hypotheses using standard benchmarks including MNIST, CIFAR-10, CIFAR-100, and Tiny-ImageNet across various architectures (FCN, CNN, VGG11, and ResNet-18/20). The experiments confirmed that:

  1. IMP consistently preserves the MST better than random pruning.
  2. The MST is a reliable indicator of the pruning limit beyond which accuracy drops precipitously.
  3. T-IMP provides a more principled approach to pruning, especially in regimes of extreme compression.

6. Limitations and Future Directions

While this work provides a robust foundation for understanding pruning through connectivity, it focuses primarily on 0-dimensional homology. It does not yet account for higher-order topological features, such as 1D "loops" or 2D "voids," which may capture more complex functional dependencies within the network. Additionally, the current analysis is largely local (per-layer); extending these topological insights to global pruning—where weights are compared across the entire network—remains an open challenge.

Future research may apply this topological lens to other deep learning phenomena, such as the "Lottery Ticket Hypothesis" or "weight rewinding," to determine if these also rely on the preservation of the underlying MST skeleton.

Summary updated

BibTeX
@inproceedings{balwani2022zeroth,
  author = {Aishwarya H. Balwani and Jakob Krzyston},
  title = {{Zeroth-Order Topological Insights into Iterative Magnitude Pruning}},
  booktitle = {Tag-ml},
  year = {2022},
}
Figure