Don’t just prune by magnitude! Your mask topology is a secret weapon
Authors: Duc N.M Hoang
Souvik Kundu
Shiwei Liu
Zhangyang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Pruning at Initialization
Pruning at Training
LTH
DST
Ramanujan
graph

Abstract: Recent years have witnessed significant progress in understanding the relationship between the connectivity of a deep network's architecture as a graph, and the network's performance. A few prior arts connected deep architectures to expander graphs or Ramanujan graphs, and particularly,[7] demonstrated the use of such graph connectivity measures with ranking and relative performance of various obtained sparse sub-networks  (i.e. models with prune masks) without the need for training. However, no prior work explicitly explores the role of parameters in the graph's connectivity, making the graph-based understanding of prune masks and the magnitude/gradient-based pruning practice isolated from one another. This paper strives to fill in this gap, by analyzing the Weighted Spectral Gap of Ramanujan structures in sparse neural networks and investigates its correlation with final performance. We specifically examine the evolution of sparse structures under a popular dynamic sparse-to-sparse network training scheme, and intriguingly find that the generated random topologies inherently maximize Ramanujan graphs. We also identify a strong correlation between masks, performance, and the weighted spectral gap. Leveraging this observation, we propose to construct a new "full-spectrum coordinate'' aiming to comprehensively characterize a sparse neural network's promise. Concretely, it consists of the classical Ramanujan's gap (structure), our proposed weighted spectral gap (parameters), and the constituent nested regular graphs within. In this new coordinate system, a sparse subnetwork's L2-distance from its original initialization is found to have nearly linear correlated with its performance. Eventually, we apply this unified perspective to develop a new actionable pruning method, by sampling sparse masks to maximize the L2-coordinate distance. Our method can be augmented with the "pruning at initialization" (PaI) method, and significantly outperforms existing PaI methods. With only a few iterations of training (e.g 500 iterations), we can get LTH-comparable performance as that yielded via "pruning after training", significantly saving pre-training costs. Codes can be found at:  https://github.com/VITA-Group/FullSpectrum-PAI.

Don't Just Prune by Magnitude! Your Mask Topology is Another Secret Weapon
Duc Hoang University of Texas at Austin hoangduc@utexas. edu
Souvik Kundu
Intel Labs souvikk. www.ukintel.c..o
Shiwei Liu Eindhoven University of Technology University of Texas at Austin s.liu3@tue.ne
Zhangyang Wang Univerity of Texas at Austin at atlaswang@utexas. edu
Abstract
Recent years have witnessed significant progress in understanding the relationship between the connectivity of deep network's architecture graph, and the network's performance. few prior arts connected deep architectures to expander graphs or Ramanujan graphs, and particularly, [7] demonstrated the use of such graph connectivity measures with ranking and relative performance of various obtained sparse sub-networks (i.e. models with prune masks) without the need for training. However, no prior work explicitly explores the role of parameters in the graph's connectivity, making the traph-based understanding prune masks and the seepiiudd/ggadient-baae
pruning practice isolated from one another. This paper strives to this gap, by analyzing the Weighted Spectral Gap of Ramanujan structures in sparse neural networks and investigates its correlation with final perfor- mance. We specifically examine the evolution of sparse structures under popular dynamic paare-to-sparse network training scheme, and intriguingly find that the generated random topologies inherently maximize Ramanujan graphs. We also identify strong correlation between masks, performance, and the weighted spee- tral gap. Leveraging this observation, we propose to construct a new "full-spectrum coordinate" aiming to comprehensively characterize sparse neural network's 's promise. Concretely, it consists of the classical Ramanujan's 's gap (structure), our proposed weighted spectral gap (parameters), and the constituent nested regular graphs within. In this new coordinate system, a sparse subnetwork's fa-distance from its original initialization is found to have nearly linear correlated with its per- formance. Eventually, we apply this unified perspective to develop new actionable pruning method, by sampling sparse masks maximize the f-- cy-ooondinate distance. Our method can be augmented with the "pruning at initialization" (Pal) method, and significantly outperforms existing Pal methods. With only a few iterations of training (e.g 500 iterations), we can get LTH-comparable performance as that yielded via "pruning after training". significantly saving pre- training costs. Codes can be found at: https:: https://github com Cttp//TTTA--rroouulSsetrerr
Introduction
Pruning [21] reduces the size of deep neural networks (DNNs) by generating sparse models suitable for compute and memory-limited applications while still preserving comparable accuracy as their dense counterparts. Existing research in this area can broadly be divided into three main components. Firstly, pruning after training (PaT) that involves creating sparse DNNs by leveraging information
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

from a trained dense model. The Lottery Ticket Hypothesis (LTH) 4 a notable work in PaT. suggests a sparse subnetwork within dense trained model can achieve comparable performance. Based on this hypothesis, they propose iterative magnitude pruning (IMP) to identify such "lottery" subnetwork at an expensive cost. Secondly, Dynamic Sparse Training (DST) [4 1 starts with training a sparse network from scratch instead of using a pre-trained dense model. Here, the sparsity mask keeps on updating throughout the training to reach maturity while maintaining the target sparsity during each epoch, often referred to as "sparse-to-sparse" training [2]. The mask update in DST primarily
relies on pruning and regrowing operations. Finally, Pruning at Initialization (Pal) g 20 8 keeps
the sparsity mask frozen throughout the training Various proxies have been proposed [9 20 18 2 to
identify the sparsity mask before training, although the Pal-yielded performance so far falls clearly below LTH and other PaT methods [6] despite the former's appealing low overheads.
Despite the significant overlap between these methods, particularly in their use of various proxies like magnitude, they differ in their beliefs on the origin of the inherent knowledge represented by the proxy used to create the sparsity mask. Pal assumes that the knowledge emerges during the initialization phase, while PaT and DST hypothesize that the knowledge is acquired from fully or partially trained model. Empirical studies (16), (6]) have demonstrated the effectiveness of PaT over Pal under high sparsity conditions. However, such performance benefits often come at the cost of high training requirements due to the iterative nature of PaT. Interestingly, a recent work [IO] highlighted that even randomly pruned subnetworks can achieve similar performance as the dense model, further raising questions about the applicability of different proxies. These often conflicting and counter-inte innuutr-nnuiiivee results intensify the debate of proxy knowledge generation through matured training vs. that identified at the beginning.
To unravel this mystery, we draw inspiration from a complementary perspective of graph theory to precisely understand the relationship between the connectivity of a neural network's 's architecture as graph and the network's 's performance. Specifically, we focus a subset of the expander graph family, namely the Ramanujan graphs. Ramanujan graphs have a maximal eigenbound. allowing the network to be highly sparse and highly connected. This aligns with the primary objective of pruning to find a sparse yet highly connected network. Previous works [19 15
I 17 7 have provided
empirical evidence supporting this intuition by utilizing the Ramanujan property to guide existing sparse generators. However, to our understanding, there exists several missing links:
1. Is the formation of the Ramanujan characteristic in sparse structures a natural occurrence during training? If so, how can we observe and quantify it?
2. What is the role of weight magnitudes in Ramanujan graph and can they have relation with the graph topology? If so, can there be a unified representation to encompass both?
Towards closing this gap, we first investigate the evolution of sparse structures under In-Time Over- Parameterization (ITOP) [13), a popular DST regime using magnitude pruning and random growth. Interestingly, we observe that DST's random growth is inherently a maximizer of Ramanujan graphs (though not a very efficient one). We then discover negative correlation between the performance and the weighted spectral gap (A). To further leverage this observation, we propose to construct a new "full-spectrum coordinate" aiming to comprehensively characterize a sparse neural network's promise, by combining Ramanujan's 's bound Ar (structure), weighted spectral gap À (parameters). and the constituent nested regular graphs within (as in the case of Aremds 77).. Most strikingly, in the resultant coordinate system, we find that a sparse sub-networks ' fz-moving distance from its original initialization has nearly linear correlation with the network's performance. Inspired by this, we maximize this fddisttacce in the coordinate by greedily sampling sparse masks initialization, yielding a new PaI approach. We empirically verify that our new Pal method, dubbed Pruning at Initialization as Graph Sampling (PAGS), can create significantly better "zero-shot" masks than the existing Pal methods. Our contributions are outlined as:
We first uncover how a sparse topology is evolved in a representative dynamic sparse training scheme (ITOP) by analyzing the weighted spectral gap of Ramanujan structures. We discover that this mechanism is an inherent yet inefficient Ramanujan maximizer.
We then establish a full-spectrum coordinate to jointly measure the structure and weight dis- tance by combining the Ramanujan perspective with the weighted spectral gap, demonstrat- ing a sparse subnetwork's f2-mo distance from its initialization in the new coordinate strong (linear) performance indicator.
2

---

We propose Pruming at Initialization as Graph Sampling (PAGS) by greedily maximizing the aforeementioned fz-moving distance. PAGS can organically applied "zero-shot" Pal method and outperforms existing Pal methods with large margins. With only a few iterations of training (e.g. only 500 iterations), we can get LTH--oopprrbll performance as that yielded via IMP in PaT,, significantly saving pre-training costs.
2 Observing Weight and Topology Evolution via Dynamic Sparse Training
2.1 Notations and Definitions
We first introduce two important concepts that are used to explain key observations made later on in this section. We also summarized the various notations in Table for easy reference.
Ramanujan gap: Belonging subset of the expander graphs, Ramanujan graphs distin- guished by their sparse yet highly interconnected nature. High connectivity in a graph implies smoother information flow, a trait coveted in sparse neural networks. Previous research [19 15 [7
interpreted DNNs as a series of bipartite compute graphs (check the appendix for more details). Here, each layer takes the form properties, aim widen the gap between Ramanujan's upper-bound, 2 / - 1, where is the average number edge per node, and the non-trivial eigenvalue of the compute adjacency matrix, ((A). This gap can be viewed in two ways:
square adjacency matrix A. Pruning strategies, inspired by Ramanujan
Canonical perspective: Ar Vd (((A)
Iterative perspective: Arimdb = A
Σ |K| (2//22241111 -1A((x.)
While the canonical perspective, Ar, indicates the ease of information propagation by measuring network's degree of connectivity, a more recent take by (7] introduces the iterative perspective, Arimdb- This measures the average connectivity limit across all subgraphs K within A, potentially offering more comprehensive insight into the network's connectivity. Note that "imdb" stands for "iterative mean difference of bound", following the same naming scheme in 77].
Weighted spectral gap: Of our own devise, the weighted spectral gap, denoted as X, quantifies the separation between the trivial (16) and non-trivial (ń) eigenvalues of the weighted adjacency matrix, W. À provides insights analogous to the Cheeger constant, which evaluates if graph possesses "bottleneck". Mirroring the two previous perspectives for Ramanujan gap, the weighted spectral gap similarly dual-formed:
Canonical perspective: À = ( W W(W.)
Iterative perspective: Ximag = K
|K| ΣM
1= (po(IW I. (( k.))
In this context, W stands for the layer-specific weight elements. However, unlike Ar and Arsmdb the interpretations of À and Ximag are not universally settled in relation to the network's sparsity and their performance correlation. However, later on in this section, reveal them be reliable indicators for performance. Note, here "imsg" stands for "iterative mean spectral gap."
Table 1: Important graph notations, their equations, and descriptions.
Notation
Equation
Deseription
Ar
2 * Vd i((A)
Measure graph's 's degree of connectiv- ity using Ramanujan bound
Arimdb
A
I (2 -A(Ak)))
Iterative mean of Ramanujan gap for set of subgraphs K in A Spectral gap of weight matrix W Iterative mean of spectral gap for set of subgraphs K W
[
X
Ho W -A((W))
I!K| (HO k. A(( k.
K]
Ximag
[K
3

---

2.2 The Role of Dynamic Sparse Training in Pruning with Ramanujan
Limitations of Ramanujan theory in model pruning: Recently Hoang et al. 7 extended the Ramanujan theory to Pal, achieving notable success in ranking Pal Pal-pruned subnetworks with Aramdt- Yet, their reliance on graph spectrum properties introduces pressing challenges. These encompass the absence of a direct pruning strategy, an oversight of weight magnitude, and the inherent non- differentiability of graph spectrum properties. Such limitations substantially restrict the wider applicability of the Ramanujan theory to the straightforward pruning approaches.
Foundational assumption: This study is anchored two pivotal hypothesis. Firstly, we posit that graph-based metrics can be strategically used as a sampling criterion, allowing for heuristic optimization and sidestepping issues related to non-diiferentiabiiity Secondly, we believe that the topology and weights of a sparse subnetwork jointly and complementarily influence performance. To substantiate these hypotheses, we aim to identify a correlation between mask's 's topology, its corresponding weight, and the ensuing performance of the sparse subnetwork. Ultimately, our goal is to develop an actionable pruning method that can be leveraged to improve Pal as well as PaT.
Dynamic sparse training an observational tool: DST 14 13 22 g is efficient sampler that (i) can swiftly navigate the mask-weight space through training dynamics evolution and (ii) is known to specialize at the "good performance" subspace (since DST always evolves to lower the training loss), rather than attempting to fit the full space. This saves the sampling burden considerably. Note that, focusing the "good performance" subspace suffices for our scenarios since most pruning methods deliver "reasonably good" sparse masks. By using DST as an observational tool, we further provide tantalizing evidence on the natural formation of the graph properties (e.g., Ramanujan characteristic) during training.
2.3 Observing Temporal Evolution of Sparse DNN using DST
Sctup: To generate and evaluate results in this section, we utilize the ITOP framework [13 for its reliable performance in monitoring sparse structures and their evolving graph characteristics. Using magnitude pruning and random growth (initial renewal rate of 50%), we sample model masks and weights every 1500 iterations over 250 epochs. After training these unique sparse models, we assess their graph characteristics to base our subsequent observations. Notably, all our sparse subnetworks maintain a 99% % unstructured sparsity (only 1 1 trained weights remain non-zero).
2.3.1
Correlation between Performance and Sparse Topology
From T we distill the distinctions between the canonical Ramanujan bound Ar and its iterative variation Arimab- The correlation between these and performance in image classification across evolving sparse structures visually captured Figure I. with time-sampled data color-coded on gradient scale. Key takeaways include:
Effectiveness over time: Our findings show that the performance of fully fine-tuned sparse DNNs improves over time when sampled during the ITOP process. This reaffirms ITOP's (and DST's overall) capability in pinpointing the "good performance" subspace, as discussed in Section 2.2.
The bottom row of displays narrowing trend for Ar with increasing performance, challenging previously held beliefs from [19 [5]. This narrowing suggests that the paths for information flow between layers become progressively more constrained.
Contradiction to convention:
Patterned random- random-growth: Contrary to the notion that random growth is entirely unpredictable, Figure innicaaess structured trends between accuracy and both Ar and Ar This min-max pattern suggests maximizing minimizing the expansion property, contingent on the chosen informational boundary metric. Interestingly, the increasing expansion of regular sub-graphs within each layer aligned with the intuitive link between information flow rate and performance.
2.3.2 Complementary Relationship between Weight and Topology Graphs
Table Titemizes one of our contributions in this paper, namely the proposal for a weighted spectral gap. À and Ximsg comprehensive and reliable performance indicator. Figure prrseetssreeeents heatmap that combines information from both the weight magnitudes and graph topology. This heatmap highlights the region of highly performative models in red, while other regions are shown in blue. By

---

31.0
11.5
970
13.0
90.2
65.0
20.0
59.5
Toretae Moan JuwannjenBBo Bound
faretwn, Moon /tw.enjjeeBao Bound
fanethve BaaoeeeMMoorrrrrrreeeeee Www.onaaanneeaaaaa Bound
31.5
$3.0
$1.
41.0
940
52.0
902
$4.0
330 5.2 0.0
8.3
350
075
1.0
172
1.00
-225
1.00
0.73
-930
0.23
1.75
1.30
3.23
3.39
0.73
0.30
(a) VGG16
(b) ResNet18
ResNet34
Figure 1: The evolution of Arimai and Ar over time as performance function using ITOP.
correlating the graph's "unweighte" topology with proposed weighted counterparts, make the following observations:
Pareto curvature:
Figure Showw a mutual dependency between the structure of the graph and corresponding weights. particular, it depicts the Pareto curvature lines between Ar and A, as well
shows
as Arimab and Ximsg.
We identify the region of highly performative sparse models that lies within a range optimizing the forward expansion characteristic represented by Arimds while minimizing the average weight magnitude of sub-graphs represented by Ximsg. Conversely, for the relationship be- tween Ar and X, improved performance is often associated with narrowing the canonical information flow while increasing the layer-wise weight average.
Area of performance:
These observations emphasize the interplay between the structure of the graph and the weights in achieving optimal performance. The analysis in Figure Souurepproo provides valuable insights into the trade-off between graph topology and weight magnitudes, shedding light on the relationship between these factors and performance outcomes. This complex interplay among multiple factors emphasizes the need for unified coordinates to describe the performance relations in sparse DNNs.
2.4 Full-Spectrum Coordinate Distance Strong, Linear Performance Indicator
In Section 2.3, we identified robust intercomnection between the Ramanujan gap and the weighted spectral gap, from both canonical and iterative angles. Figures ! and Pandrorrtray portray the combined influence of sparse topology and weights in optimizing sparse DNN performance, prompting us to investigate the central question:
possible to allow them co-exist the same representation?
To this end, we introduce novel coordinate system, the "Full-spectrum". integrating Ar, Arsmdh X, and Aimat as its four layer-wise axes, given their ties to both weights and topology. Formally, it's represented as 4x4 with denoting the # layers of a model. Navigating this space entails navigating a complex trade-off landscape. We gauge its utility by assessing its linear correlation with overall performance via Pearson correlation. Figures 3 and 4 visualize the efficacy of the "Full-spectrum" in contrast to existing graph metrics. From these, deduce:
Consistent linear correlation with performance: As evidenced by Figure 3 under ITTO''s random growth regime, the mo-nn distance from a sparse subnetwork's original position within the "Full-spectrum" aligns almost linearly with performance.

---

41.75
650
90.
10.25
60.33
90.
Ant cis sae san e37 oatu gao cin
con ses cola col selo sci soe 1e13
Spectal
11.00
714
714
(a) VGG16
(b) ResNet18
(c) ResNet34
Figure 2: Performance landscape between the structure and weights under graph perspective. top panel, we examine the correlation between Arimab and Ximag. In the bottom panel, we explore the correlation between Ar and The landscape represents the classification performance, with gradients coloring from dark blue to dark red, indicating the worst to best performance.
09.
31.8
11.0
27.
01.0
850
912
34.
41.5
58 11,oeetron.
1.25
111 mpa.pmm
14 10.0emmun
(a) (p 0.71)
(b) ResNet18 (p 0.96)
(c) ResNet34 (p 0.91)
Figure 3: Full-spectrum di-dtttnnce against classification performance on CIFAR-10 across different models. We denote the associated Pearson correlation (p) performance in the parentheses.
Superiority over current graph metrics: Figure 4 confirms that, relative to Ar and X, our "Full-spectrum" perspective offers more direct linear correlation performance. This affirms the harmonious co-existence of these metrics within a unified representation, and the potency of this integrated indicator paves the way for its application in tangible pruning scenarios.
3 Pruning Graph Sampling
We now present our actionable pruning methodology as graph sampling, which essentially leverages the proposed my-mnn distance metric associated with the "full-spectrum" coordinate, which shows to be strong, linear performance predictor. Note that our proposed methodology applicable to any pruning setting since it makes no specific assumption the weight (e.g., randomly initialized or pre-trat pre-trained weights) nor the mask (e.g., local layer-wise or global pruning mask). This makes our methodology generic that be augmented with various "off-the-shelf" pruning methods.
In this section, two specific variants are introduced, one for Pruning at Initialization (Pal), and the other for Pruning after Training (PaT), which requires only few training iterations.

---

ResNet18
A
Full spectrum (0 = 0.99)
(0 0.85)
(0 0.95)
ResNet34
060
120
<.590 8-100 000 4U4E
3200 0.51
0.00
0.50
6.00
1:40
5300
0203
0:00 0.20
Ar
Full spectrum
(p 0.85)
(0 = 0.95)
(p = 0.97)
Figure 4: Illustration of the correlation between topology (Ar), weights (2), and the combined "full spectrum" with respect the classification performance CIFAR-100 with ResNet18 (top row) and ResNet34 (bottom row). indicates the Pearson correlation.
3.1 Pruning at Initialization as Graph Sampling (PAGS)
Pruning Initialization as Graph Sampling (PAGS) is a lightweight pruming method that does not require any pre-training and aims to maximize the layer-wise full-spectrum b-- moving distance. It directly "augments" any existing Pal method, by oversampling the Pal mask generator and selecting the top mask that tends to maximize the fz-moving distance cri- teria. In other words, PAGS can be viewed "meta-framework" applicable on top of (and to improving) any existing Pal method.
Algorithm 1: Pruning Initialization Graph Sampling (PAGS)
1: Initialize the weights 0 population size
2:
3: k + mini-batch size
4: i + sampling rate
5: A. W GenerateMasz(data, k. 0)
6: // generate sparse topology and weights
while 1 1 do
8:
Å, W GenerateMasin ateerattMMasxttt.. k. 8)
// sampling mask
10:
A. w CompareMerge((A, W), ( (A. W )
For proxy-driven Pal methods such as 9 18), first generate population of sparsity masks: to create each mask, we simply leverage
20
11:
I/ compare and merge if conditions are satisfied
12:
if n % = and A, W are modified then
randomly selected small minibatch of training
13:
Save A, W
data (GenerateMask(,
For non- non-proxy con--rxxy-driven
14:
end if
Pal like random pruning or ERK (10), the mask
15:
population is created by randomly assigning the non-zero values to random weight locations for each mask. From the population, we sample mask, perform a layer-wise comparison to the current best mask, and update the best in case it improves the fg-moving distance (Mepee))Merge()). For population size of n, the process is repeated times. During these iterations, we periodically save the current best mask at an interval of steps. Algorithm| [ illustrates this process.
16:
end while
PAGS is computationally inexpensive, as each mask sampling requires only a forward pass over a minibatch. In all our experiments, we adopt the default 1,000, i 20, and minibatch size 128.
7

---

Table 2: Results on CIFAR-10 of PAGS (with different Pal methods), in comparison to vanilla Pal methods and LTH (as empirical performance "ceiling"). Baseline refers to the Pal-found sparse mask (at initialization) without modification by PAGS. v means no pre-training needed (i.e., ideal Pal). X, XX, and XXX, represent low, high, and very high pre-training costs, respectively.
Method
Baseline acc. %
with PAGS
No Pretraining
(Best acc %)
(Avg, acc %)
needed
ResNet18
SNIP
89.54
90.17
89.80 0.14
GraSP
91.39
92.01
91.68 0.16
ERK
88,92
90.42
91.051 0.17
Random
85,43
86.03
85.72.1 0.16
LTH
91.22
XXX
ResNet34
SNIP
91.30
91,80
91.58= 0.13
GraSP
91.27
91.85
91.48= 0.16
ERK 91.18
92.29
91.98= 0.13
Random
88.23
88.73
88.56++0.10
LTH 92.76
XXX
3.2 Pruning Early as Graph Sampling (PEGS)
To further improve the classification accuracy reduced compute, extend the zero-shot PAGS, to present Pruning Early as Graph Sampling (PEGS), which incurs only a small amount of pre-training cost. In PEGS, we "pre-train" the dense network only for a small number of iterations (by default, for 500 iterations in all our experiments) and then apply PAGS to this lightly trained network. This draws similar inspiration LTH rewinding (5) or early-bird (EB) ticket 23 in literature.
Compared the Pal case, we note that it is not as straightforward to directly "sample" masks using LTH/EB or any other PaT method, since generating a different mask from those methods would require re-taking an expensive training process: otherwise, the pruning is deterministic on trained weights and there is no way to inject randomness. Hence, we do not treat PEGS as "meta- framework" on top of PaT methods. Instead, we discover that light enough pre- pre-training, followed by cheap Pal-based sampling, can yield sparse masks with comparable quality to the top- top-performing PaT masks such as LTH, at a significantly cheaper cost. For example, compared to LTH with M rounds of iterative training, N epochs per training round, and / iterations each epoch (1 500 in CIFAR-10), PEGS in the same setting would only cost 500 iterations of pre-training, which is roughly MNx more compute-efficient and faster. For example, in CIFAR- experiments we have M 23 and N 250, hence PEGS would yield >> 5000 times saving over LTH.
4
Experiments
4.1 Experiment setup
We leverage four Pal generators to facilitate our experiments (both PAGS and PEGS): Random [0] uniformly prunes every layer with the same pruning ratio assigned globally. Each parameter is randomly assigned score based on the normal distribution. ERK B 14] initializes sparse networks with a Erdös-Rény graph where small layers are usually allocated more budget, while bigger layers are assigned fewer parameter budget. Random pruning then performed following those layer-wiss wise ratios SNIP [9] for any layer it issues scores 81 !gt ② wrl where gi and are gradients and weights respectively. The weights with the lowest scores after one iteration are pruned before training, GraSP (20) removes weights that impeded gradient flows by computing the Hessian- Hessian-gradient product h; and issue scores si = W O h4, for a layer l.
We also compare with two PaT methods: Lottery Ticket Hypothesis (LTH) iteratively prunes the lowest 20% of weights and rewind the remaining weights to some values in the past. To achieve the desired 99% sparsity, LTH would necessitate 23 rounds of full training and pruning. * Early Bird (EB) 23 utilizes one-shot "early pruning", with a "mask-similarrty" signal to automatically terminate pre-training as cost-saving mechanism (typically happening around the first 15%-20% epoches). The original EB was implemented for structured pruning; for fair comparison, the results shown in Table are our re- re-implementation of EB onto unstructured pruning.
8

---

Table Results on CIFAR-10 of PEGS (with light pre-training followed by different Pal methods), in comparison to vanilla Pal methods, LTH and EB (the later two come with much heavier pre- pre-training costs). Baseline refers to the Pal-found sparse mask (after light pre-training) without modification by PEGS. X, XX, and XXX, represent low, high, and very high pre-training costs, respectively.
Method
Baseline %
with PEGS
No pre-training needed
(Best %) (Avg. acc %)
ResNet18
SNIP
91.05
91.53
91.22+ 0.14
X
GraSP
89.97
91.50
91.251 0.23
X
ERK
89.87
91.31
91.05.1 0.17
Random
85.37
86.03
90.1311 0.19
X
EB
90.10
XX
LTH
91.22
XXX
ResNe134
SNIP
92.38
92.75
92.51 0.10
X
GraSP
92.84
92.90
92.70.1 0.40
X
ERK
91.10
92.01
91.49.1 0.23
Random
87.86
88.91
88.41=0.25
EB 92.00
XX
LTH 92.76
XXX
Table 4: Results on CIFAR-100 on ResNet18 using PAGS/PEGS in comparison vanilla Pal methods, LTH and EB. Baseline refers to the Pal-found sparse mask. x, xx, and XXX, represent low, high, and very high pre-training costs, respectively. 100 and @500 refer to different "pre-training" iterations using PEGS. @0 means start from random initialization using PAGS.
Method
Baseline
with PAGS/PEGS
No pre-training needed
acc.
(Best ace %) (Avg. acc %)
ResNet18@0
SNIP
64.60
65.39
64,89 0.26
GraSP
65.25
66.05
65.54 0,21
ERK
64.54
64.84
64.69 0.12
ResNet18 @ 100
SNIP
63.22
64.92
64.34+t 0.34
GraSP
63.27
65.17
64.35:1 0.33
ERK
64.06
64.82
64.41 0,22
X
ResNet18
6 500
SNIP
62.60
64.27
63.46: 0.30
GraSP
61.34
63.95
62.91 0.59
ERK
64.06
65.05
64.56 0.27
X
EB
62.45
XX
LTH
65.50
XXX
Unless otherwise stated, use high target sparsity of 99% in all our experiments. We demonstrate results on CIFAR- 10/ CIFAR-100 100 the main text. We use two representative models, Resnet18 and ResNet34, the main backbones in this section[] Additional training details and results Tman-ImangeNet are deferred to the Supplementary due to the space limit.
4.2 Comparison of PAGS and PEGS with Existing Pal methods
Tables 2 and detail our pruning results for CIFAR-10 10 using PAGS and PEGS, while Tables 4 and do for CIFAR-100. As PAGS/PEGS operate on sampling basis, we list both the peak performance of the best mask (Best acc) and the mean performance across all sampled masks (Avg. acc). The
latter supplemented by the standard deviation. From the presented results, we deduce the following:
① In CIFAR-10/ trials, our methods consistently surpass the baseline Pal generators in PAGS. standout instance is the 2.12% advantage over ERK for ResNet18 using Pal, as seen in Table 2
② With light pre-training, our methods still hold an edge against reference generators. For instance, Tables 4 and indicate about 1% enhancement over the top-performing generator at both the 100 and
VVGG16 is not included since some Pal methods and EB fail on it 99% high sparsity ratio.

---

Table 5: Results on CIFAR- 100 on ResNet34 using PAGS/PEGS in comparison vanilla Pal methods, LTH and EB. Baseline refers to the Pal-found sparse mask. x. xx, and XXX, represent low, high, and very high pre-training costs, respectively. @100 and @500 refer to different "pre-training" iterations using PEGS. @0 means we start from random initialization using PAGS.
Method Baseline acc. %
with PAGS/PEGS
No pre-training
(Best %) (Avg. acc %)
needed
ResNet34@0
SNIP
69.48
70.73
69.83+ 0.27
GraSP
67.88
70.59
69.64 0.74
ERK
68.64
69.90
69.77 0.11
ResNet34
@ TO0
SNIP
68.04
69.41
68,6411 0.33
X
GraSP
62.47
66.61
64.43 + 1.03
ERK
68.91
69.92
69,50 = 0.16
X
ResNet34
@ 500
SNIP
67.41
69.23
68.531 0.36
X
GraSP
67.18
68.95
68.03 + 0.41
ERK
68.99
69.92
69.451 0.22
X
EB
65.22
XX
LTH
68.05
XXX
500 iteration marks. 3 Interestingly, optimal outcomes typically manifest during the initialization phase, implying that light pre-training doesn't 't instantancously refine the weight distribution.
4.3 Comparison with (Much More Expensive) LTH and the Early Bird Ticket
We further compare PAGS/PEGS with the two PaT methods, LTH and EB, and note that the latter two significantly costlier. Overall, for Pal setting (table 2). we intend to include LTH as the "performance ceiling" and show PAGS can get close to or even outperform it often times. For example, Table shows that ResNetl 8 utilizing GraSP marginally outperforms LTH, without any pre-training.
For PaT setting (table 3 table and table (5). we show that with a small fraction of pre-training costs, our PEGS could solidly outperform both LTH and EB, using either SNIP or GRASP mask generators. Interestingly, in ResNet18, even the random ERK mask generator can be turned into LTGG level performance with the aid of PEGS. Our findings suggest that maximizing the full-spectrum' 's fz-moving distance can significantly improve performance by optimizing both the graph's 's structure and weights. This approach allows us to achieve performance levels comparable to LTH but at significantly lower cost. By leveraging the insights the Ramanujan perspective provides, we can achieve notable performance improvements across the board of pruning, while incurring minimal computational overheads.
5
Conclusion
Recent years have seen the rise of graph theory in analyzing and understanding sparse subnetworks. However, still lack crucial understanding of the role parameters play in graph connectivity. To fill this gap, in this paper, we study the weighted spectral gap of Ramanujan structures in sparse neural networks and investigate its correlation with the final performance. By examining the evolution of sparse structures under DST, we identify strong correlation between Ramanujan bound, weighted spectral gap, and performance. Leveraging these observations, we proposed new "full-spectrum coordinate" which comprehensively characterizes the complex interplay between various graph characteristics that further leads to actionable pruning methods both at initialization and after light pre-training. This unified perceptive is expected to invoke more future exploration into the complex interplay between topology and weights, not just for sparse NNs but for generic DNNs as well.
Acknowledgment
Z. Wang is in part supported by NSF Scale-MoDI. (award number: 2133861) and the NSF AI Institute for Foundations of Machine Learning (IFML).
10

---

References
[1] K. Bhardwaj, G. Li, and R. Marculescu. How does topology influence gradient propagation and model performance of deep networks with densenet-type skip connections? 202/ IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 13493-13502, 2021.
[2] U. Evci, T. Gale, J. Menick, P. S. Castro, and E. Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages 2943-202 9943.2952. PMLR, 2020.
[3] U. Evci, I. Gale, J. Menick, P. S. Castro, and E. Elsen. Rigging the lottery: Making all tickets winners, ArXiv, abs/1911. 11134, 2020.
[4] J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks, arXiv: Learning, 2018.
[5] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv: I 1903. 1,, 2019.
[6] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. Pruning neural networks at initialization: Why are we missing the mark? ArXiv, abs/2009.08577 2020.
[7] D. N. Hoang, S. Liu, R. Marculescu, and Z. Wang. Revisiting Pruning at Initialization Through the Lens of Ramanujan Graph. In The Eleventh International Conference on Learning Repre- sentations, 2023.
[8] S. Kundu, M. Nazemi, P. A. Beerel, and M. Pedram. Dnr: A tunable robust pruning framework through dynamic network rewiring of dnns. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pages 344-350, 2021.
[9] N. Lee, T. Ajanthan, and P. H. S. Torr. Snip: Single-shot network pruning based on connection sensitivity. ArXiv, abs/ 0tss/1810.or 1bb///800000340, 2018.
[10] S. Liu, T. Chen, X. Chen, L. Shen, D. C. Mocanu, Wang, and M. Pechenizkiy. The unreasonable effecttivneess of random pruning: Return of the most naive baseline for sparse training. ArXiv, abs/2202.02644 2022.
[11) S. Liu, D. C. Mocanu, A. R. R. Matavalam, Y. Pei, and M. Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neurons on commodity hardware. Neural Computing and Applications, 33:2589-2604, 2021.
[12] S. Liu and Z.. Wang- Ten lessons we have learned in the new" sparseland": A short handbook for sparse neural network researchers. arXiv preprint arXiv:2302.002556, 2023.
[13] S. Liu, L. Yin. D. C. Mocanu, and M. Pechenizkiy. Do we actually need dense over- parameterization? in-time over paramcterization in sparse training. ArXiv, abs/2102.02887, 2021.
[14) D. C. Mocanu, E. Mocanu, P. Stone, P. H. Nguyen, M. Gibescu, and A. Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 91):23383, 2018.
[15] B. Pal, A. Biswas, S. Kolay, P. Mitra, and B. Basu. A study on the ramanujan graph property of winning lottery tickets. In /CMI, 2022.
[16] M. Paul, F. Chen, B. W. Larsen, J. Frankle, S. Ganguli, and G. K. Dziugaite. Unmasking the lottery ticket hypothesis: What's encoded in a winning ticket's mask? ArXiv, abs/2210.030444, 2022.
[17] A. Prabhu, G. Varma, and A. M. Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In ECCV, 2018
[18] H. Tanaka, D. Kunin, L. K. Yamins, and S. Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. ArXiv, 0ass22006.05467. 2020.
11

---

[19] D. T. Vooturi, G. Varma, and K. Kothapalli.. Ramanujan bipartite graph products for efficient block sparse neural networks. ArXiv, abs/2006. 1100006..34800 13486, 2020.
[20] C. Wang, C. Wang, G. Zhang, and R. B. Grosse. Picking winning tickets before training by preserving gradient flow. ArXiv, abs/2002.07376, 2020.
[21] H. Wang. C. Qin, Y. Bai, Y. Zhang, and Y. Fu. Recent advances on neural network pruning at initialization. In International Joint Conference on Artificial Intelligence, 2021.
[22] L. Yin, V. Menkovski, M. Fang, T. Huang, Y. Pei, and M. Pechenizkiy. Superposing many tickets into one: A performance booster for sparse neural network training. In Uncertainty in Artificial Intelligence, pages 2267-2277. PMLR, 2022.
[23] H. You, C. P. Xu, Y. Fu, Y. Wang, X. Chen, R. G. Baraniuk, Z. Wang, and Y. Lin. Draw- ing early-bird tickets: Towards more efficient training of deep networks. arXiv preprint 1rXiv:1909.119571 2019.
A DNN as bipartite graphs
A bipartite graph is graph consisting of two distinct sets of vertices L and R that connected with E edges as GLL R, E). Let denote the total number of vertices both sets, the more common way to represent G is as binary adjacency matrix A E Ruxe
DNN is series of bipartite graphs, one for each layer, to represent all of its compute graphs. For convolutional layer with parameter tensor 0 E R xCoai x xk,,, K we unfold the dimensions so that L Can hig Kowt and R Cout- For linear layer with parameter tensor f RR mCCx.Com CCott we can directly adapt its parameters where T. Cin and R = Cout-
An interesting and relevant property of bipartite graph, that when each node has the same number
of d out-edges, its adjacency matrix A has eigenvalues ((A) such that μo 2 ... 2 f4-11 where yo and | are equaled d. We define ((A) = max un (idd |pa] as the largest nontrivial eigenvalue. In the context of unstructured pruning, we often find G to be irregular, in which case Hoang et al. showed that daug < |pol S dmaax.
B Supplementary results for PAGS and PEGS
B.1 Additional Experiments on CIFAR-10
We expanded experiments the CIFAR-10 dataset by utilizing weights pre-trained for 100 iterations with a batch size of 128 per iteration. The CIFAR-I0 dataset consists of 50,000 training images and 10,000 testing images, divided into 10 different classes. The results of these experiments are summarized in Table
We observed performance improvement relative to baseline. However, compared to other modes of pre-training for CIFAR-10. 10, certain Pal generators exhibited ceaieerttha--eppeett standard de- viation and lower average performance, indicating Specifically, we observed this trend with GraSP in ResNet18 and SNIP in ResNet34.
instability in generating sparse structures.
B.2 Additional Experiments on Tmmy-ema
We expanded our experiments on the Tiny-Imagened dataset by utilizing weights pre-trained for 100 iterations with a batch size of 128 per iteration. The Tiny-Imagenet dataset consists of 100,000 images, divided into 200 different classes. The results of these experiments are summarized in table and table
C Limitations and Societal Impacts
This work studies the effect of weights under the Ramanujan settings through observation using ITOP. By gaining insights from these observations, we empirically improve the performance of pruning methods using PAGS, We do not expect any negative socictal impact from this work.
12

---

Table Results on CIFARIO on ResNet18 and Resnet34 using PEGS in comparison vanilla Pal methods, LTH and EB. Bascline refers to the Pal-found sparse mask. X, xx, and XXX, represent low, high, and very high pre-training costs, respectively. @ 100 refers to weight pretraining 100
iterations with batch size 128.
Method
Baseline %
with PEGS
No pre-training needed
(Best %)
(Avg. %)
ResNet18@ 100
SNIP
90.39
91.30
90.06 0.17
GraSP
86.09
91.11
80.38 3.14
ERK
90.07
90.41
90.11 0.22
EB
90.10
XX
LTH
91.22
XXX
ResNet34 T00
SNIP
92.91
93.22
90.01 1.70
GraSP
92.66
93.11
92.91 0.11
ERK
92.04
92.19
91.88+ 0.18
EB
92.00
XX
LTH
92.76
XXX
Table 7: Results on Tiny-ImageNet on ResNet18 using PAGS/PEGS in comparison to vanilla Pal methods, LTH and EB. Baseline refers to the Pal-found sparse mask. X, XX, and XXX, represent low, high, and very high pre-training costs, respectively. @100 and @500 refer to different "pre-training" iterations using PEGS.
Method
Baseline acc. %
PAGS/PEGS
No pre-training needed
(Best ace %) (Avg. acc %)
ResNetI8@ @ 100
SNIP
47.13
49.00
48.45 1 0.44
X
GraSP
48.31
49.43
48.82
+ 0.32
ResNet1
500
SNIP
45.83
47.83
47.11
10.42
X
GraSP
48.89
50.26
49.48 = 0.29
EB
47.43
XX
LTH
49.81
XXX
Table 8: Results on Imag--ma on ResNer34 using PAGS/PEGS in comparison to vanilla Pal methods, LTH and EB. Baseline refers to the Pal-found sparse mask. X, XX, and XXX, represent low, high, and very high pre-training costs, respectively. @100 and @500 refer to different "pre-training" iterations using PEGS.
Method Baseline acc. %
with PAGS/PEGS
No pre-training needed
(Best ace %)
(Avg. acc %)
ResNet34 100
SNIP GraSP
53.07
54.91
53.65 + 0.4
52.71
53.71
52,80
+ 0.41
X
ResNet34@500
SNIP GraSP
53.57
$4.65
54.16 + 0.25
53.83
55.48
54.84 + 0.35
EB
53.40
XX
LTH
54.00
XXX
13


Reviews:
[{"review_id": "BSAD2C7rj6", "reviewer": "Reviewer_i7oA", "summary": "This work studies network pruning in a way that takes into account both the graph topology and values of weights. This connects purely magnitude-based and purely graph-based pruning methods. In particular, the authors find correlations between performance of masks and 4 properties derived per layer of the neural network that account for graph structure and weight magnitude. The authors then use these properties to propose a new method that augments existing pruning at initialization methods.", "questions": "Page 3, the use of \"tantalizing\" is hard to understand for me here. What did you mean by this?\n", "limitations": "There is a limitations section in Appendix B, but it does not actually discuss any limitations.\n", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. Sampling after a light pretraining is a good, efficient approach.\n2. Proposed PAGS method is simple in a good sense, and can be used with any other pruning at initialization method.\n3. Empirical contribution of measurements of various network properties during ITOP.\n", "weaknesses": "1. Page 5's \"physics intuition\" is hard to understand and unrigorous, and does not seem to do much to alleviate the mentioned \"lack of theory\" from the Pal et al. approach.\n2. [1] also uses weighted graph regularization to sparsify neural networks weights.\n3. I generally find the paper hard to read. It seems like there is a lot of content and jargon / abbreviations introduced very rapidly.\n4. Use of weighted spectral gap is not so novel.\n5. Experimental improvements are quite modest in Tables 1 and 2.\n6. It would be interesting to more directly optimize for the 4 properties of the coordinate system, instead of simplying sampling and choosing masks that improve on those properties.\n\n[1] Tam and Dunson. Fiedler Regularization: Learning Neural Networks with Graph Sparsity. ICML 2020.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1) Page 5's \"physics intuition\" is hard to understand and unrigorous, and does not seem to do much to alleviate the mentioned \"lack of theory\" from the Pal et al. approach.\n\n> We appreciate the reviewer's feedback. In our paper, we describe $\\Delta r$ in graph theory as the degree of connectivity within a graph, with a higher value signifying increased connectivity due to a smaller non-trivial eigenvalue. This is a commonly held interpretation in graph theory[4]. However, $\\lambda$ lacks a universally accepted interpretation. To establish a parallel with $\\Delta r$, we interpret $\\lambda$ as potential energy, following the approach in [2]. Likewise, similar work such as [3] also implies strong correlation between spectral gaps in estimating the ground-state energy.\nThus, we interpret a higher $\\Delta r$ to  imply a lower overall potential energy, due to smaller non-trivial eigenvalues. As demonstrated in Figure 1 and 2, our goal is to reveal that, even in random architecture searches like our DST, there's a propensity towards architectures that promote expansive models with lower potential energy. This key insight forms the foundation of our paper.\n\n> We highlighted this important limitation of Pal et al. in having insufficient insight and interpretation that acted as a bottleneck to apply Ramanujan bound onto weight adjacency matrix.In hindsight, we recognize that our interpretive efforts may have distracted readers from our main hypothesis. We will clarify these in the final draft.\n\n\n2) [1] also uses weighted graph regularization to sparsify neural networks weights / Use of weighted graph gap is not so novel.\n\n> We thank  the reviewer for pointing out this work that we will be happy to include in the future revision of this draft. As for the latter point, we have never claimed to be the first  in using weighted graph gap to sparsify neural network weights. For instance, we cited Pal et al. [7], who previously employed weighted graphs  for the similar purpose. \n\n> We thus want to emphasize the contributions of our work: A) the observation that in the context of Ramanujan graph, random evolution of sparse topology is not random; B) the establishment of an almost linear correlation between accuracy and the combined coordinates of the Ramanujan and weighted spectral gap; and C)proposal of new methods, namely PAGS and PEGS,that reliably sample performative masks at initialization, stemming from observations made in points A) and B). \n\n> In specific, **we are the first to link the propensity of sparse neural networks toward Ramanujan expander and weighted spectral gap even when under random growth**. We further empirically demonstrate that maximizing the combined full-spectrum coordinates at initialization can correlate to higher performance. \n\n> We now highlight the key differences between our work and [1]:\n> * [1] uses the weighted spectral gap as a regularizer during training for dense parameters, while we apply our insights at initialization with random weights to identify a performative mask without training. This is an important distinction between Pruning at Training and Pruning at Initialization (PaI).\n> * [1] proposed a conjecture with some proofs relating weighted spectral gap to performance, and utilizing small MLP models in their empirical evidence. We showed in observations of real models that this phenomenon is tangible, and can occur without any specific guidance.\n> * [1] relies on basic MLP layers, and while they argue that their approach can extend to conventional networks, from experience we find this to be technically impractical. Typical linear algorithms, such as those found in Scipy, rely on LAPACK (an efficient and fast linear algorithm package), which utilizes the standard QR algorithm [6] for eigenvalue decomposition. This method involves a series of matrix multiplications, leading to exceedingly high cost while computing  eigenvalues for large dense weight matrices like those in ResNet or VGG. These high costs makes the training time consuming while inflating the memory requirements, thus potentially hindering the applicability of such method. We address these challenges by employing sparse weight matrices proposed by PaI for sparse eigenvalue decomposition, thereby substantially improving the efficiency and scalability. \n\n\n3) I generally find the paper hard to read. It seems like there is a lot of content and jargon / abbreviations introduced very rapidly.\n\n> Please refer to our global responses.\n\n4) Experimental improvements are quite modest in Tables 1 and 2.\n\n> Please refer to our global responses.\n\n5) It would be interesting to more directly optimize for the 4 properties of the coordinate system, instead of simplifying sampling and choosing masks that improve on those properties.\n\n> We appreciate the reviewer's suggestion. However, direct optimization would necessitate full-training, which is beyond the scope of this paper as our interest lies in procuring sparse masks at initialization or with minimal pre-training.\n\n\n6) Page 3, the use of \"tantalizing\" is hard to understand for me here. What did you mean by this?\n\n> We use the adjective \"tantalizing\" to describe our observations, indicating that they are highly interesting and engaging.\n\n\n[1] Tam and Dunson. Fiedler Regularization: Learning Neural Networks with Graph Sparsity. ICML 2020.\n\n[2] https://arxiv.org/abs/1502.04573 \n\n[3] https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.3.040327\n\n[4] https://math.uchicago.edu/~may/REU2019/REUPapers/Walchessen.pdf\n\n[6] https://en.wikipedia.org/wiki/QR_algorithm \n\n[7]B. Pal, A. Biswas, S. Kolay, P. Mitra, and B. Basu. A study on the ramanujan graph property of 374 winning lottery tickets. In ICML, 2022.\n"}, {"review_id": "OXWT1CHgmy", "reviewer": "Reviewer_9NeG", "summary": "This paper proposes a new approach to deep network pruning based on graph theory, specifically the use of Ramanujan graphs. The authors argue that their approach, which focuses on optimizing both the graph's structure and weights, can achieve notable performance improvements across various pruning methods while incurring minimal computational overheads. Empirical results demonstrate that their approach outperforms existing methods such as LTH and EB, even with a small fraction of pre-training costs.", "questions": "Please check questions enlisted above.", "limitations": "The authors have not explicitly discussed any limitation. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tThe paper proposes a new approach to deep network pruning based on Ramanujan graphs, which are highly sparse yet highly connected graphs that align with the primary objective of pruning. Although prior arts have connected Ramanujan graphs with pruning/PaI quality assessment, this is first work deriving an actionable pruning method based on such.\n\n-\tThe approach focuses on optimizing both the graph's structure and weights, which can achieve notable performance improvements across various pruning methods while incurring minimal computational overheads. \n\n-\tEmpirical results demonstrate that the proposed approach outperforms existing methods such as LTH and EB, even with a small fraction of pre-training costs. It also significantly improve the previous random sampling-based pruning, e.g. ERK.\n\n-\tThe paper also sheds light on the relationship between the connectivity of a neural network's architecture as a graph and the network's performance, providing a complementary perspective to understand the effectiveness of different pruning methods. \n\n\n", "weaknesses": "I have two major critiques: (1) poor readability, and (2) unimpressive, sometimes confusing experiments.\n\nReadability: This paper is, at very least, quite hard to follow. That is partially owing to the dense content – the authors tried to pack too many observational stuff in one submission (sections 2-4, before finally reaching their “actionable pruning” results in section 5). That is along with a lot of self-defined jargons and unnecessary notations. I suggest merging sections 2-4 into two sections, one on observation and the other on pruning method, both being significantly shorter in length.\n\nExperiments: there are several presented results confusing me. \n\n-\tWhy VGG shows much poorer linear correlation in Figures 1-4, compared to ResNets? Also the authors didn’t report VGG results in Section 5. I wonder: is the proposed method only specifically effective on ResNets?\n\n-\tI am not sure I understand how to read Figure 3. There is no detailed analysis in main text either.\n\n-\tIn Table 2, the improvements are veryminor, usually within error bar. I am not convinced the improvement of PEGS is evident. Can you show more dataset results like ImageNet?\n\n-\tIn Tables 1 and 2: do you suggest it’s fairer to compare baseline acc with “Best acc”, or “Average acc”? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1) I have two major critiques: (1) poor readability, and (2) unimpressive, sometimes confusing experiments.\n* Poor readability\n\n* Experiments: there are several presented results confusing me. Why VGG shows much poorer linear correlation in Figures 1-4, compared to ResNets? Also the authors didn’t report VGG results in Section 5. I wonder: is the proposed method only specifically effective on ResNets?\n\n> For issue with readability please refer to our global responses.\n\n> For experiments, the reason why VGG exhibited a weaker correlation compared to ResNet lies in its unstable nature, stemming from the absence of skip-connections. In our Dynamic Sparse Training (DST)  settings, we perform unstructured pruning on all the models at 1% of their original parameter size using a random-growth policy. For VGG, lacking skip connections, this can lead to poorly aligned layer-wise sparsity masks, potentially affecting information flow and thus disrupting performance. Since Figures [1-4] depict the performance of masks we sampled over time, VGG is more prone to producing outliers with infeasible masks, thereby diminishing its correlation to performance.\nWe chose not to include VGG methods in Section 5, as indicated in our footnote, due to the propensity for PaI methods to fail in generating feasible masks for sampling. Our sampling approach, which relies on PaI for mask proposal, is notably more reliable for networks with some form of residual skip-connection. We recognize this constraint and will ensure to address it in the limitations section of our paper.\n\n\n2) I am not sure I understand how to read Figure 3. There is no detailed analysis in main text either.\n\n> Figure 3 provides visual representation of three essential metrics: the x-axis shows the Ramanujan-bound (topology), the y-axis depicts the spectral gap (weights), and the colored landscape illustrates performance (accuracy). The objective of this figure is to swiftly convey the inherent relationship between topology, weights, and performance. Notably, the region of peak performance (highlighted in bright red) is concentrated in a specific area. This distinct region is the target we seek to optimize in our sampling method. We highlight this interdependency between the metrics in Observation 1. In the next revision, we will ensure to clarify the meaning and observations related to Figure 3.\n\n3) In Table 2, the improvements are very minor, usually within the error bar. I am not convinced the improvement of PEGS is evident. Can you show more dataset results like ImageNet?\n\n> Please refer to our global responses.\n\n\n4) In Tables 1 and 2: do you suggest it’s fairer to compare baseline acc with “Best acc”, or “Average acc”?\n\n> We utilize average accuracy to show  confidence in our sampling process, showing that the average performance over the entire sampling window exceeds that of the original mask. However, we find it reasonable to compare the best sampled results with baseline performance, as the average calculation includes both fully optimized and partially optimized masks.\n"}, {"review_id": "KiBfDwKxbv", "reviewer": "Reviewer_QXrC", "summary": "This paper proposes a new method for pruning deep neural networks that optimizes both the network's structure and weights. The experimental results show that it can be naturally applied as a “zero-shot\" PaI method and outperforms existing PaI methods with large margins. Alternatively, it can be applied after light pre-training to get LTH-comparable performance.", "questions": "This is overall an interesting and theoretically sound paper, but several important concerns remain as discussed in “weakness”. Please address each of them.", "limitations": "no", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed approach to deep network pruning based on Ramanujan graphs is a technically innovative and interesting method that optimizes both the graph's structure and weights, achieving notable performance improvements across various pruning methods while incurring minimal computational overheads. As connecting graph theory to sparse network architecture is a recently emergent idea, this paper fills in a timely and important research gap. \n\nThe authors leveraged DST as an organic tool to sample sparse masks and observe its co-evolution with weights. The research observation sheds light on the relationship between the connectivity of a neural network's architecture as a graph and the network's performance, providing a complementary perspective to understand the effectiveness of different pruning methods. \n\nThe algorithm novelty lies in the use of a new \"full-spectrum coordinate\" that characterizes a sparse neural network's promise, consisting of the classical Ramanujan's gap, the proposed weighted spectral gap, and the constituent nested regular graphs within.\n\nThe experimental findings suggest that maximizing the full-spectrum's l2-moving distance can significantly improve performance by optimizing both the graph's structure and weights. The empirical evidence also shows that even the random ERK mask generator can be turned into LTH-level performance with the aid of PEGS.\n", "weaknesses": "Despite the appeal of theory, I don’t think the current experiments are sound enough. In general, all pruning methods in-use tend to perform similarly on CIFAR-10/100. As seen in Tables 1 and 2, different methods’ numbers are often within each other’s error bar, making it hard to judge whether one “outperforms” others with true statistical significance or just by chance/ random noise. \n\nNoteworthily, while the authors highlighted their success that “ResNet18 utilizing GraSP (+ PAGS) even marginally outperforms LTH, without any pretraining”, the GRASP baseline in Table 1 (top) and Table 2 (bottom) already outperformed LTH, hence disapproving LTH as “empirical performance ceiling” as authors assumed (or otherwise, implying there exists an unfair comparison among baselines).\n\nI also don’t feel the “Full-Spectrum Coordinate” is convincing nor sound enough. An ad-hoc construction by authors, it has two “topology-only” coordinates and two other “weight-topology” coordinates. So at least, the four two groups of coordinates are redundant, one dependent of the other. Why one cannot expect a better linear predictor via more “orthogonalized” coordinates, such as two “topology-only” and two “weight-only” coordinates combined?\n\nLastly, the experiment part contains many hyperparameters that were barely discussed or justified. For example, “I = 50”, “N = 250”, etc. How are they chosen and are they sensitive?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1) Despite the appeal of theory, I don’t think the current experiments are sound enough. In general, all pruning methods in-use tend to perform similarly on CIFAR-10/100. As seen in Tables 1 and 2, different methods’ numbers are often within each other’s error bar, making it hard to judge whether one “outperforms” others with true statistical significance or just by chance/ random noise.\n\n> Please refer to our global responses.\n\n\n2) Noteworthily, while the authors highlighted their success that “ResNet18 utilizing GraSP (+ PAGS) even marginally outperforms LTH, without any pretraining”, the GRASP baseline in Table 1 (top) and Table 2 (bottom) already outperformed LTH, hence disapproving LTH as “empirical performance ceiling” as authors assumed (or otherwise, implying there exists an unfair comparison among baselines).\n\n> In smaller datasets such as CIFAR, we observe PaI methods can yield competitive results, even compared to LTH. However, this phenomenon quickly diminishes with larger datasets like Tiny-ImageNet (please refer to global response for results). We will revise the draft to update based on this observation.\n\n3) I also don’t feel the “Full-Spectrum Coordinate” is convincing nor sound enough. An ad-hoc construction by authors, it has two “topology-only” coordinates and two other “weight-topology” coordinates. So at least, the four two groups of coordinates are redundant, one dependent on the other. Why one cannot expect a better linear predictor via more “orthogonalized” coordinates, such as two “topology-only” and two “weight-only” coordinates combined?\n\n> We thank the reviewer for their criticism. From our understanding, the reviewer is questioning our decision to use four separate criteria (two for weights and two for topology) instead of just two (one for topology and one for weights), as they believe the two metrics for either weights or topology are fundamentally interdependent.\n> We argue that these metrics should not be combined as they measure different forms of information flow and are not fundamentally dependent on one another. In support of our decision, we have cited prior work such as [1] that clearly demonstrates the differences in effectiveness in using the Ramanujan gap to predict performance between the iterative and non-iterative versions. Similarly, we have described their distinctions between lines 155-169.\n> In summary, the non-trivial eigenvalue gauges the general information boundary of the entire compute graph, without considering its regular sub-graphs, and can sometimes be overly strict for irregular graphs. On the other hand, the iterative version evaluates the average information boundary of sub-graphs within a larger structure, a criteria shown to be more effective by [1]. Our decision to use both stems from our observation of potential trends exhibited by both measures in random sparse networks in DST. These differences in what they measure justify our approach of using separate criteria. We will ensure that our revision includes a clear explanation to avoid any confusion.\n\n\n\n\n4) Lastly, the experiment part contains many hyperparameters that were barely discussed or justified. For example, “I = 50”, “N = 250”, etc. How are they chosen and are they sensitive?\n\n> We selected these parameters to match LTH's default parameters in the OpenLTH repository[2]. This alignment was intentional to ensure a fair and consistent comparison with the benchmark. We will emphasize this point in the experimental settings section in future revision.\n\n[1] D. N. Hoang, S. Liu, R. Marculescu, and Z. Wang. Revisiting Pruning at Initialization Through 355 the Lens of Ramanujan Graph. In The Eleventh International Conference on Learning Representations, 2023.\n\n[2]https://github.com/facebookresearch/open_lth\n"}, {"review_id": "wevdAZTzmu", "reviewer": "Reviewer_62wf", "summary": "The paper suggests two pruning strategies: pruning at initialization as graph sampling (PAGS) and pruning early as graph sampling (PEGS). The PAGS approach is one of those that doesn't call for any pre-training dietary intake. The mask is oversampled each time, and the masks with the greatest l2 movement distance are chosen. With the PEGS approach, which is a slight enlargement of PAGS, the dense network undergoes very little pre-training. The article experiment performs SOTA on CIFAR10.", "questions": "Please see the weakness part.", "limitations": "No limitations discussed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The context of the paper is very logical.\n* This paper is rich in theoretical analysis.", "weaknesses": "* The actual method suggested is relatively naive, and too much length in the paper is devoted to analysis and introduction.\n\n* The experimental part only contains the CIFAR-10/100 dataset, and such a small number of experiments cannot accurately reflect the effectiveness of the method. It is highly recommended that the author increase the validity experiments such as ImagNet.\n\n* \"only 500 iteration\" does not support the statement of \"a few iteration\" on small datasets like CIFAR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1) The actual method suggested is relatively naive, and too much length in the paper is devoted to analysis and introduction.\n\n> We thank the reviewer for their comment. We understand that both PAGS and PEGS can be considered as simple greedy algorithms. However, we consider this to be an advantage of our method to apply these techniques in a \"plug-and-play\" way on top of existing SOTA low-cost pruning methods as discussed. Additionally, we would like to highlight that these methods are the outcome of our important and novel observations. In particular, we first showed the directed nature of  random evolution in sparse topology which follows the Ramanujan perspective. We further  illustrated the existence of an almost linear correlation between performance and the combined coordinates of the Ramanujan and weighted spectral gap. And finally, we derived simple methods that reliably sample performative masks at initialization, stemming from these observations. \n\n> We apologize for the insufficient readability of our paper. In our next revision, we'll simplify both our observations and the methods as suggested by the reviewer (while incorporating all the readability improvement suggestions of other reviewers as well). Additionally, in the global rebuttal, we have summarized the major take-away from each section which we will follow in the revised draft to improve readability.\n\n\n2) The experimental part only contains the CIFAR-10/100 dataset, and such a small number of experiments cannot accurately reflect the effectiveness of the method. It is highly recommended that the author increase the validity experiments such as ImageNet.\n\n> Please see our global responses \n\n3) \"only 500 iteration\" does not support the statement of \"a few iteration\" on small datasets like CIFAR.\n\n> We appreciate the reviewer's feedback. We concur that our choice of 500 iterations with a batch size of 128 might raise questions; however, this equates to approximately one epoch on CIFAR-10. The rationale behind this choice was to align with the default pre-training parameters set by Lottery Ticket Hypothesis (LTH) in OpenLTH repository [1], ensuring a fair comparison of results. We will make certain to clarify this aspect in our revised version.\n\n[1]https://github.com/facebookresearch/open_lth\n"}]

Author rebuttal:
We thank all our reviewers for their feedback and will try to address each concern individually. While the reviewers tend to have consensus on the novelty and contribution of our work,  there are two common criticisms that we wish to respond globally, namely:
* Insufficient experimentation
* Readability

To address the first concern, we've expanded our experimentation to Tiny-ImageNet. Our results show that PaI, as a baseline, typically underperforms its LTH counterpart. Additionally, we demonstrated efficacy of sampling with PEGS that can significantly enhance performance.

To address the second concern of insufficient readability, primarily due to dense text, excessive jargon, and numerous observations, we will make the following revisions:
* Introduce a table for quick reference to notation definitions and cut-down on number of notations.
* Combine sections 2-4 into "Observations" and "Methodology."
* Clarify our interpretation, describing more simply the relation between performance, topology, and weights.

Within "Observations," we will enhance readability by:
* Streamlining our motivation for using DST to study temporal weight/topology evolution in random fashion.
* Creating a dedicated subsection to clearly describe various metrics and notations, including a summary table, in the context of deep neural networks.
* Adding a section to analyze figures 1-4 and their significance to our central hypothesis.



Meta-review: This paper improves the Ramanujan graph theory towards analyzing deep network pruning-at-initialization (PaI), by viewing a network layer as a weighted graph.

Compared to the prior work (Hoang et. al. 2023), the main improvements made by this paper are: (i) optimizing both the graph’s connection topology and weights (rather than only topology) and proposing the new analytical tool of weighed spectral gap; (ii) turning the weighted graph perspective into a new actionable PaI method, that outperforms previous PaIs and can be on par with LTH at a small fraction of its cost; and (iii) observing how the graph structure evolves in dynamic sparse-to-sparse training, and showing the common routine (pruning by magnitude, then growing randomly) implicitly maximizes Ramanujan graphs. AC also takes an in-detail read of this paper, and personally feels the third point (while very intriguing) had not been dig deep enough in this paper, and only referred to as empirical supporting evidence for the first point. However, the first two points are indeed interesting and well-justified.

After rebuttal, the paper receives four scores of 7, 7, 5, 3. Almost all reviewers agreed that this paper has very rich theoretical contributions as well as analyses; and is written quite logically. Reviewer i70A, who scores the lowest 3, explicitly stated that “…with the caveat that I note that my confidence level is only a 2... this may be in part because I am less familiar with this field.”

The other three reviewers (who scored 7, 7, and 5 after rebuttal) found the common issue of in that the original submission reported only CIFAR-10/CIFAR-100 experiments, hence suggesting a lack of experimental sufficiency. The authors expanded their experimentation to Tiny-ImageNet, during rebuttal. However, Reviewer 62wf still thought ImageNet experiments should have been reported; and in general, all PaI methods underperform other post-training pruning or sparse training methods in practice. The authors also strike back with their arguments.

Reading through the whole discussions, AC is personally familiar with PaI and has the following thoughts. For empirical post-training pruning, upholding experimental validation at ImageNet-level and above is a “must” that AC also agrees on. However, this paper, as well as the generic field of PaI, is more theory-flavor by exploring the “optimal sparse neural architecture" that is independent of any training. Hence, PaI has its unique value, and shall not need outperform more expensive post-pruning pruning methods.

Many PaI papers are published in recent top-tier conferences, such as SNIP (ICLR 2019), SynFLow (NeurIPS 2020), and the unweighted Ramanujan Graph (ICLR'23, which this paper is based on). All those papers meanwhile report experiments on CIFAR-10, CIFAR-100, Tiny-ImageNet; that is because they more prioritize theoretical contributions over extensive experiments. This paper followed the established convention by those PaI papers.

Therefore, by putting it in the context, AC decides that this paper has already done a good job, in delivering what it promised: a solid theoretical foundation for PaI and many meaningful observations. While this paper could be strengthened further by reporting more and larger-scale experiments, the current shape shall suffice to warrant its NeurIPS acceptance.
Decision: Accept (poster)