REVISITING PRUNING AT INITIALIZATION THROUGH THE LENS OF RAMANUJAN GRAPH
Authors: Duc N.M Hoang
Shiwei Liu
Radu Marculescu
Zhangyang Wang
Venue: ICLR 2023 notable top 5% (2023)
Keywords: pruning at initialization
graph theory
Ramanujan Graph
sparse neural networks

Abstract: Pruning neural networks at initialization (PaI) has received an upsurge of interest due to its end-to-end saving potential. PaI is able to find sparse subnetworks at initialization that can achieve comparable performance to the full networks. These methods can surpass the trivial baseline of random pruning but suffer from a significant performance gap compared to post-training pruning. Previous approaches firmly rely on weights, gradients, and sanity checks as primary signals when conducting PaI analysis. To better understand the underlying mechanism of PaI, we propose to interpret it through the lens of the Ramanujan Graph - a class of expander graphs that are sparse while being highly connected. It is often believed there should be a strong correlation between the Ramanujan graph and PaI since both are about finding sparse and well-connected neural networks. However, the finer-grained link relating highly sparse and connected networks to their relative performance (i.e., ranking of difference sparse structures at the same specific global sparsity) is still missing. We observe that not only the Ramanujan property for sparse networks shows no significant relationship to PaI’s relative performance, but maximizing it can also lead to the formation of pseudo-random graphs with no structural meanings. We reveal the underlying cause to be Ramanujan Graph’s strong assumption on the upper bound of the largest nontrivial eigenvalue (µˆ) of layers belonging to highly sparse networks. We hence propose Iterative Mean Difference of Bound (IMDB) as a mean to relax the µˆ upper bound. Likewise, we also show there exists a lower bound for µˆ, which we call the Normalized Random Coefficient (NaRC), that gives us an accurate assessment for when sparse but highly connected structure degenerates into naive randomness. Finally, we systematically analyze the behavior of various PaI methods and demonstrate the utility of our proposed metrics in characterizing PaI performance. We show that subnetworks preserving better the IMDB property correlate higher in performance, while NaRC provides us with a possible mean to locate the region where highly connected, highly sparse, and non-trivial Ramanujan expanders exist. Our code is available at: https://github.com/VITA-Group/ramanujan-on-pai.

Published as a conference paper at ICLR 2023
REVISITING PRUNING AT INITIALIZATION THROUGH THE LENS OF RAMANUJAN GRAPH
Duc Hoang, Shiwei Liu, Radu Marculescu & Zhangyang Wang
Department of Electrical and Computer Engineering University of Texas Austin, Austin, TX 78712, USA (hoangd, radum, a (aw.aaageuteexsss....... edu shiwei. liu@austin, utexas.
ABSTRACT
Pruning neural networks initialization (Pal) has received an upsurge of inter- est due to its end-to-end saving potential. Pal is able to find sparse subnetworks at initialization that can achieve comparable performance
the full networks. These methods can surpass the trivial baseline of random pruning but suffer from a significant performance gap compared to post-training pruning. Previous ap- proaches firmly rely on weights, gradients, and sanity checks as primary signals when conducting Pal analysis. To better understand the underlying mechanism Pal, we propose to interpret through the lens of the Ramanujan Graph class of expander graphs that are sparse while being highly connected. It is often believed there should be strong correlation between the Ramanujan graph and Pal since both are about finding sparse and well-connected neural networks. However, the finer-grained link relating highly sparse and connected networks to their relative performance (i.e., ranking of difference sparse structures at the same specific global sparsity) still missing. We observe that not only the Ramanujan property for sparse networks shows no sigmificant relationship to Pal's relative performance, but maximizing can also lead the formation of pseudo-randon graphs with no structural meanings. We reveal the underlying cause to be Ramanujan Graph's ' strong assumption on the upper bound the largest nontrivial eigenvalue (î) layers belonging to highly sparse networks. We hence propose Iterative Mean Difference of Bound (IMDB) as a mean to relax the á upper bound. Likewise, we also show there exists lower bound for ü. which we call the Normalized Random Coefficient (NaRC), that gives us an accurate assessment for when sparse but highly connected structure degenerates into naive randomness. Finally, we systematically analyze the behavior of various Pal methods and demonstrate the utility of our proposed metries in characterizing Pal performance. We show that subnetworks preserving better the IMDB property correlate higher in performance, while NaRC provides us with a possible mean to locate the region where highly connected, highly sparse, and non trivial Ramanujan expanders exist. Our code is available at: https: / / thub. com / /VITA Group/ jaw.ae//...aaaaaaaaaaaaaaaa.aaaa on-aan-----p....
INTRODUCTION
Deep neural networks (DNN) have demonstrated remarkable performance as they increase in size, i.e. test accuracy scales as a power law regarding model size and training data size (Hestness et al., 2017: Kaplan et al., 2020; Brown et al., 2020; Srivastava et al., 2022). Yet, the memory requirements and computational costs associated with the increased model size also grow prohibitively. Modern DNNs are widely recognized to be over- wer-ppraaetteiize, and it has been shown that eliminating significant number of parameters
performance (Han et al., 2015c; trained DNN does not compromise He et al., 2017). This over-paree parameterization property enables researchers to continually propose increasingly effective DNN pruning approaches that can dramatically shrink the model size while maintaining performance. The resultant sparse models can then be used with software and hardware that is optimized for sparsity, leading to faster training and inference.
Neural network pruning can generally be divided into three categories: post-training pruning (Mozer & Smolensky, 1989; Han et al., 2015a), traiinnttrinngggggg pruning (Gale et al., 2019; Louizos et al., 2018), and pre-training pruning (Lee et al., 2019; Wang et al., 2020), depending the timing of

---

Published as a conference paper at ICLR 2023
the pruming relative to the training phase. For instance, post-training pruming methods are generally effective when the primary goal is to reduce inference cost. However, these methods require training the dense model fully first, potentially multiple times if iterative pruning and retraining are used. With the prevalence of powerful foundation models such as GPT-3 (Brown et al., 2020), PM (Chowdhery al., 2022), and DALL-F. (Ramesh al., 2022), the prohibitively high cost of training these large models makes post-training pruning impractical. Therefore, pre-training pruning or pruning at initialization (PaI) is becoming increasingly attractive due to its potential to save time and resources end-to-end, by using sparse DNN architecture from the outset.
The concept of pruming at initialization (Pal) was first introduced in SNIP (Lee et al., 2019), which removes the structurally unimportant connections at initialization via the proposed connection sensitivity. Follow-up works (Wang et al., 2020; Tanaka et al., 2020; Patil & Dovrolis, 2021) propose advanced pruning criteria to improve the performance of Pal. GraSP (Wang et al., 2020) aims to maintain the weights that can maximize the gradient flow. SynFlow (Tanaka et al., 2020) finds that previous Pal methods are prone to layer collapse and adopt iterative pruning to address it. Despite these advances, Pal still lags behind post-training pruning in terms of performance. A study by Frankle et al. (2021) suggests that connection ambiguity may explain the performance deficit, based on the finding that Pal exhibits surprising resilience against layerwwise random mask shuffling and weight re-initialization..
Prior works on Pal mainly focus on "training signals" such as gradient flow (Wang et al., 2020), layer collapse (Tanaka al., 2020), or sanity check (random weight shuffling and re-initializationn) (Frankle et al., 2021). I). Since the limited information (e.g., magnitude, gradient, and Hessian) that Pals have access to can be very noisy (Frankle et al., 2020), pruning criteria based on such information are often ineffective. We conjecture that the graph topology of sparse neural networks, being relatively overlooked, can be an essential source of information for pruning at initialization. Graph theory has recently emerged as particularly advantageous tool for analyzing DNN architectures. For example, You et al. (2020) offers a new efficient graph representation of DNN using relation graphs to formulate an efficient model generator. Liu et al. (2020) analyzes sparse neural networks with graph distance and shows a plenitude of sparse sub-networks with very different topologies while achieving similar performance. Vooturi et al. (2020); Pal et al. (2022); Bhardwaj et al. (2021); Prabhu et al. (2018) show that maximizing good graph connectivity, i.e. by maximizing a graph's 's expansion ratio, correlates to higher performance in hardware-efficient structured masks and lottery tickets (Frankle & Carbin, 2019). Unfortunately, prior efforts did not consider the pseudo- seeudoranddomess that naturally emerges from very good expander graphs. Therefore by maximizing sparse graph connectivity, they are unwittingly prioritizing the formation of naive random graphs with no intrinsic structure meaning.
In this paper, we study Pal from the perspective of the Ramanujan bipartite graphs. The Ramanujan graph is a special graph in the bounded degree expander family, where the eigenbound is maxi- mal (Nilli, 1991), thus leading maximum possible sparsity of network while preserving the connectivity. The Ramanujan graph is intuitively well aligned with the main goal of Pal, i.e., finding sparse and well-connected neural networks. However, we find that there is still a missing link correlating the degree of connectivity to relative performance ranking at a particular sparsity. In addition, we also show that in situations where highly sparse and highly connected structures are demanded, it can be easy to generate pseudo-random graphs with no structural meanings unwittingly.
We reveal the underlying cause for such undesirable situations to be Ramanujan Graph's strong assumption the upper bound of the largest nontrivial eigenvalue (ß) of layers belonging to highly sparse networks. We hence propose Iterative Mean Difference of Bound (IMDB) as a mean to relax f upper bound. Likewise, we also show there exists a lower bound for P., which we call the Normalized Random Coefficient (NaRC), that gives us an accurate assessment for when sparse but highly connected structure deteriorates into randomness. Leveraging our (adjusted) Ramanujan graph-based framework, we then extensively investigate (1) whether the generated sparse structures by existing Pal approaches follow the Ramanujan characteristics, (2) if there exists correlation between the Ramanujan graph property and the inference performance of the sparse structure, and (3) if the sparse structure is also random graph. Ultimately, we aim to shed light on new perspective on PAI effectiveness independent of weights, gradients, and losses.
Our contributions are summarized as follows:
We are the first to reveal that the utility of the Ramanujan property is largely limited in analyzing irregular graphs at high sparsity, which is often the case in analyzing Pal-generated
2

---

Published as a conference paper at ICLR 2023
architectures. We identify the root cause to be its strong assumption the upper bound of the largest nontrivial eigenvalue f of the adjacency matrix and propose Iterative Mean Difference of Bound (IMDB) as effective fix.
We devise another novel metric to assess whether a Ramanujan graph is also random, which becomes increasingly likely with higher sparsity. We prove the existence of this metric by inferring from the definition of the expander mixing lemma. Our NormAlized Random Coefficient (NaRC) assesses the randomness of graphs, by characterizing the lower bound of for which can no longer distinguish expanders from randomly generated graphs.
. Our analysis shows that IMDB correlates strongly with the relative performance for different Pal's s sparse masks at high sparsity. It further illustrates how NaRC can spot random structures, and provide interesting observations on the relationship between randomness and expansion.
RELATED WORK
Pruning methods (Mozer& & Smolensky, 1989; LeCun et al., 1989; Hassibi et al., 1993; Molchanov et al., 2016; Han et al., 2015b) traditionally aim to remove the unnecessary components of DNNs, resulting in a subnetwork that can be efficiently deployed at inference. As the sizes of the modern DNNs have exploded, a vast amount of attention has been shifted to pruning them before training, targeting both training and inference efficiency. Lee et al. (2019) explicitly learn connectivity importance score for weights and eliminate weights with the lowest scores. Wang et al. (2020) leverage the Hessian gradient product to discover the importance of weight to the gradient flow. Iterative pruning approaches (Tanaka et al., 2020; de Jorge et al., 2021) show their efficacy to prevent layer collapse, ending up with pruned networks with very small width (Patil & Dovrolis, 2021). Although existing Pal methods surpass the naive baseline of random pruning, they are only able to identify useful layerwise sparsity levels rather than the specific weight patterns (Frankle et al., 2021; Su et al., 2020). As Pal only accesses very limited and noisy information (e.g., magnitude, gradient, and Hessian) from initialization, pruning criteria based on such information may not be effective.
On the other hand, the topology of sparse DNNs the configuration of nodes and connections among them can be another essential source of information. Mocanu al. (2018) initialize sparse networks with a Erdōs-Rényí graph and dynamically optimize the graph towards a scale-free network, Evei et al. (2020b) further expand the Erdös-Rénn Rényí graph to convolution neural networks, demonstrating large performance improvements. Liu et al. (2020) analyze sparse DNN with graph edit distance and show that there exists plenty of sparse sub-networks with distinct topologies that perform equally well. You et al. (2020) study the relationship between the graph structure and the neural networks from the relation graphs point of view. Vooturi et al. (2020); Pal et al. (2022); Bhardwaj et al. (2021) show that maximizing the graph connectivity of sparse networks correlates to higher performance in the structured masking and lottery tickets (Frankle & Carbin, 2019).
Recently, Ramanujan graphs have been linked sparse structures (Pal al., 2022; Vooturi et al., 2020) as naturally appealing criteria to produce sparse yet well-connected DNN models. We draw inspiration from two prior works: Vooturi al. (2020) applies the Ramanujan bipartite graph products for efficient, structured sparsity. In short, they achieve run-time efficiency by decomposing dense matrix into tiled multiplication and utilizing the Ramanujan principle to maximize connectivity between the decomposed tiled matrices. The more recent work by Pal et al. (2022) evaluates whether a lottery ticket's masks exhibit Ramanujan property. If they do not, then sparsity will repeatedly be halved until the generated masks are all Ramanujan graphs.
Besides the obvious difference that we uniquely work on pruning at initialization with end-to-ent sparsity (no dense pre-training is involved), our work also differs from these prior arts in our tackling of irregular bi-graphs that arise from practical sparse DNNs: we are the first to identify a crucial limitation of Ramanujan property in analyzing irregular graphs under high sparsity, which seems to be overlooked by prior arts. We also highlight the danger of being overly expansive, which risks graphs deteriorating into randomness. We then propose ways to relax the upper constraint to mitigate the critical gap between theory and practice and a lower constraint to avoid the danger of randomness, which leads to more rigorous analysis of sparse DNNs initialization.
3

---

Published as a conference paper at ICLR 2023
3 METHODOLOGY
Before we start, we want explain some nomenclature that will be used excessively in our definitions. First, a "regular" graph refers to a graph where all its vertices have the same number of in/out edges; We refer the number of edges as d. Analogously, when we talk about regular graphs, we refer to any dense DNN, such Linear or Convolutional layers once. An "irregular" graph, on the other hand, refers to a graph with mixed number of edges for every vertex. Likewise, when speaking of irregular graphs, we refer to the resulting unstructured pruning of DNN layers with Pal. Later, will explain how the DNN's layers are represented as graphs.
3.1 PRELIMINARY: BIPARTITE EXPANDER GRAPHS
In this work, we focus mainly on the bipartite case of expander graphs. However, before giving a formal definition, we state the following intuition: expander graphs are graphs where every subset of vertices is not "too large" and has "many connections" to other vertices that do not belong to the same subset. Typically, these graphs are regular; however, we shall extend the definition consider finite, connected, and irregular graphs for our DNN analysis purpose.
Definition 1. A bipartite graph or bi-graph G = (L U R, E) is graph consisting of two disjoint sets of vertices L and R such that every edge from E' connects one vertex of L and one vertex of R.
Many definitions will make use of G (V, where V L U R instead, For most cases, is trivial to extend them to bipartite graphs. However, in case of extension ambiguity, we will clarify these definitions specifically for bi-graphs.
Definition 2. Let S S V for G = (V, E); we denote ((S) = {u E V e S, (u, E E} to be the neighborhood set consisting of all adjacent vertices not in |S].
Since we are working with bipartite graphs, S S L and N(S) S R, and there are no edges between any two vertices in S.
Definition 3. A (n, m. d, -expanderr is d-left-regular' bipartite graph G = (L R. E). where [L] n. R| m (m S n) and 45 C I s.t |S| S 7 . the neighhorhood set of S satisfies [N(S) 2 [S]. Here E (0,1) and a E [0
The a and y parameters control the expansion ratio of the expander and are dependent on one another. For example, by letting = d the regularity of L, then 7 S since if [S|] > 3. then we violate the
neighborhood constraints namely [N()) 2 a. | > n > m. The expansion ratio, [N())] is related S to the Cheeger constant h(G), whereby small ratio signifies information bottleneck and large h(G) indicates the graph is strongly connected. A good bipartite expander graph should ensure a large Cheeger constant so that information can flow freely.
Let us denote A | ||ctmm as the adjacency matrix of some d-regular bipartite graph G L, E) with cigenvalues z(G') s.t #g 2 2 11 where d = Ho = |4,- l. and corresponding eigenvectors Φb. We define AG)) max (a [14] to be the largest nontrivial eigenvalue. Due to the nature of bipartite graphs where [μо] |ui| d, we will often refer to ji(G) as our third-largest eigenvalue. The expansion property of any is represented by its spectral gap Ho (iG) (see Hoory & Linial (2006)). A large gap indicates G is more "spread out" which is the hallmark trait of the expander graph. Since μo á 2 0, need determine threshold on the spectral gap for which G can be considered as a good expander. This brings us to the notion of Ramanujan graph property.
Definition& 4. A d-regular graph is said to be a Ramanujan graph if (G) < 2/d-1, where d is graph regularity. Alternatively, following the previous discussion, Ramanujan graph can also be expressed as j(G) < 2 V - I, since = d.
Thus, all Ramanujan graphs are good expanders due the convenient upper bound of (GG). However, after Pal not all graphs are regular. Therefore, we need to generalize Definition 4 for all cases. To do so, we combine two inequalities: The first inequality states that the universal cover graph G of G satisfies p(() 2 2* * /deg - I, where (()) denotes the spectral radius of & and dang represents the average degrees of G (for details see Hoory (2005)). The second inequality, following the results
delefttregular means all vertices in T. have d number of edges.
4

---

Published as a conference paper at ICLR 2023
of Hoory& & Linial (2006), defines graph to be Ramanujan iff ((G) S p(O). We relate these two inequalities form ja()) * /day - S P()).
As direct result, we can estimate any graph's expansion property as the difference between ji(G) and its estimated Ramanujan's 's upper bound.
Definition 5. We denote the difference of bound as: Ar 2* dawg - 1 (G) value Ar 0.0 indicates a violation of the Ramanujan property and therefore the graph may not be a good expander.
In the case of bi-graphs, we rewrite Definition 5 as Ar -d I++ vd -I and dp are the average degree of R and L respectively. Additionally, because j(G) is the third largest eigenvalues by magnitude, a Ramanujan graph is only defined when min(dr, dR) 2 3.
Gi(G), where dR
3.2 ITERATIVE MEAN DIFFERENCE BOUND
In this subsection, we focus on discussing the value μo of irregular graphs, something we glossed over in the discussion of the previous subsection and it is also largely overlooked by prior works. Primarily, we want address cases where Mo & and assess the effect it can have on determining graph G' satisfies the Ramanujan property. Here, we explicitly define the general range of μuo on all graphs, explain its negative effects on our analysis of high, and propose a way to mitigate the effects.
Lemma 1. The value of μl for any adjacency matrix A is said to be daøy I no S dmaa- If G' is connected graph, 140 dmaa therefore G is reguuar We first prove dawn S No by using the Rayleigh quotient. We have:
h Ah
AT
Evev d.
H4
max HERn
h h
1'1
n2
davg
(1)
To prove μro I dmazi let do be the corresponding eigenvector of ns and say that v arg max, ((u).
Without loss of generality, we have @u(v) * So, we show:
(HO00)(0) (A)o)(o) E(un)e Po(u) (b(v))
no (0(2)
Φ0(v))
Σ
1= du S dmaz.
(2)
(M,N)E
Finally, we show that if po dmar. then EGnEE du(u) do(v)
((, 1 = d = dmaa. In this way, Φn is constant vector with value d, for all vertices that are connected to v. By repeating the way v was chosen then applied to u for all such vertices u, we yield the result that G is dmaz-regulan
Ar's limitation for irregular graphs at high sparsity: Now that we have proven the range of poo we can extend it to the following inequality: (GG) < 2 /daug
S 2 v/o -I. I. This inequality shows that Ramanujan's 's apper-bound estimation for (aG) is conservatively small.
Because of our interest in analyzing high sparsity (which often the pursuit of Pal methods), dmaz- davg is possibly very large. By following Ar, we only qualify those graphs with tiny (a()) as Ramanujan graphs. We refer to the expander mixing lemma (see detail in Sauerwald Sun (2011)), which relates to the relative degree of ju(G) and the smaller ju(G) (the more G appears to be random). Consequently, in the irregular graph case, we could dismiss valid expanders due to the overly limiting requirements while retaining only graphs with random sparse- graph structures when analyzing high sparsity.
IMDB. We propose a new metric called Iterative Mean Difference of Bound (Arimab) as way to relax the Ar's constraint. Let G be our irregular graph, we define a set K to be (K&(V, E, E. C G|d, 2 3} the set of d-regular subgraphs in G, Arimdt is formally defined as:
|K]
Ar A Lindb
Σ (2+ (2+v - i(K:))
(3)
K
Since every graph in K are regular, we do not have to estimate the upper bound of their ft. Intuitively, we say irregular graph G is good expander if its regular subgraphs are good expanders. Finally, we extend Eq 3. for bi bi-graphs as:
K (Vd.-1
AT Arrmmab
dd -A((K))
(4)
|K|
5

---

Published as a conference paper at ICLR 2023
where dæ is the average degree of R since only care about d-left-regular bi-graphs for settings. Our ablation study shows smsd effectively correlates relative performance to relative connectivity for highly connected highly sparse structures.
3.3 NORMALIZED RANDOM COEFFICIENT
In the previous section, we mentioned the expander mixing lemma and its relation (G). but did not go into much detail about it. In this section, we define this relation and show how it can be used to prove the existence of our NormAlized Random Coefficient (NaRC).
Definition 6. Given d-regular GVV, E), the expander mixing lemma is given as:
[ 7) d|S|TT] S (I)G)
(5)
where S, T S VV VV,STT=
(0), [V] μu (G) is the second largest eigenvalue of G, and EESS I)
the total number of edges between and T. The intuition behind it is that the smaller μl N1(), the more G appears to be random. For more explanations, please refer to Sauerwald & Sun (2011).
For our irregular bi-graph case, we exchange μal and since they are equivalent, and replace d with d,, the average left degree. We also exchange the definition of S to that of Definition 2, with
S C L, likewise replace ' with N(S) [ R and with m = [f]. The expression now reads as:
|| ((()) dz [s)))
S
(6)
From Lemma 1, we know that davg is the smallest possible value can be for G. thus the following inequality is true:
davg (E(S,
de (((SS)
S No dmax
VISIN(S)
Eq 7 further highlights our earlier argument for IMDB, but we can now take it a step further. With this inequality, we can rewrite the Ramanujan upper bound to include the random expander graph subsets. This means:
||E(S,((S)) (2ISS m
(GG) S 2
(8)
VISIN(S)
By subtracting the right-hand side, arrive at our definition for NaRC:
a=( (
(G)² + +1V NN(S) |E(SS N(S))
dr
[S] [N(S) 0
(9)
m
la denote our normalized degree of and we say that G' is a random expander if a S 0, and [. randomness. From now on, when we refer a, we will use its normalized version ПП[ From the above inequality, we can now clearly see how expander mixing lemma relates to (G()), and the smaller it is, the more random the graph becomes.
One reason we do not want our graphs to be reduced to randomness is that it conflicts with our desire for "specific connections" as stated by Frankle et al. (2021). Compared trivial random sparsity, non-random and structurally meaningful masks are expected to provide an interpretation of where and how performance is derived. Our experiments show under the right cireumstance, a network can learn to overcome randomness, and those with meaningful masks achieve significantly better performance on average.
3.4 BIPARTITE EXPANDER GRAPIS ON PRUNING AT INITIALIZATION
All models can be viewed as a sequence of computing graphs. Let M denote the set of a I-layer model, obtain M [G..... G.) graphs, where G, (L U R. E) is the i-th layer's graph representation with and indicates the input and output layer respectively. M initially starts as set of complete bipartite graphs. Pruning is then process of edge sparsification on M with the

---

Published as a conference paper at ICLR 2023
resulting sub-grae -ub-gggass considered irregular expander graphs. The expander property appeals to network sparsification analysis because it can approximate a complete graph, as shown in Spielman (2018). However, approximating complete graphs using irregular graphs is still an open question. For our study, we consider only the convolution and linear layers of any given model.
Convolution layer. A convolutional weight consists of four dimensions namely the input channels, output channels, kernel width, and kernel height. To represent the convolution layer as a bipartite graph, we can unfold the input and kernels dimension to get W E IR F. x [R], where L = Cin * K * KR and [R] Cout- The resulting weighted graph is written as G (L R. E, W). Note that the number of edges | = |W]-
Linear Layer. A linear weight consists of only the input and output channels, and bipartite conversion is trivial. We directly express its weight as W E [ where |L| = C.n and [R] Cous- The resulting weighted graphs similarly written as = (LU
Prumning at initialization. For each network, let W denotes the set of weights {w) E R E }}} where ny is the number of parameters at layer l. Pruning is the process of generating binary masks my 1 A pruned subnetwork has weights wy O my, where @ is the element-wise product. Most Pal methods have two stages: First, they issue scores 2 E IR to all weights. Second, they remove the score into mask my with overall sparsity Pruning may occur iteratively or in one shot depending on the methods. We study the following representative Pal techniques:
Random (Liu al., 2022) is the most basic Pal method that uniformly prunes every layer with the same pruning ratio assigned globally. Each parameter is randomly assigned a score based on the normal distribution. ERK (Evci al., 2020a; Mocanu et al., 2018) initializes sparse networks with a Erdās-Rényí graph where small layers are usually allocated more weights. SNIP (Lee et al., 2019) issues scores 8t = |gi O w/| where Jr and wt are gradients and weights respectively. The weights with the lowest scores after one iteration are pruned before training. GraSP (Wang et al., 2020) removes weights that impeded gradient flows, by computing the Dessian-gradiens product h; and issue scores 81 W @ hy. SynFlow (Tanaka et al., 2020) iteratively prunes model with its weights replaced with |urr/. Each time, it propagates an input of I's and computes the gradients based on the task's 's loss function ry. It issues score st |r) wy| and removes the parameters with the smallest scores.
4 EXPERIMENTS
In this section, we examine our carlier claims with empirical results and see how they fare; furthermore, with supporting evidence, answer questions regarding relationships between Ramanujan to performance, randomness to performance, and Ramanujan to randomness. Finally, we point out intuitions and what they imply for Pal under the lens of the Ramanujan perspective.
Experimental settings. We conduct our experiments with two different DNN architectures: Resnet- 34 (He al., 2016) and Vgg-16 (Simonyan & Zisserman, 2014) on CIFAR-10 (Krizhevsky, 2009). We run our experiments with three random seeds and initialize all Pal methods identically with three different initial weights generated by each seed to ensure fairness. Table summarizes our standardized training configurations. We include additional results on CIFAR- 100 in the Appendix.
Table 1: Summary of architectures and hyperparameters that we study in this paper.
Model
Data
#Epoch
Batch Size
Optimizer
LR LR Decay, Epoch Weight Decay
Resnet-31
CIFAR-10
250
256
SGD
0.1 10x, [160, 180)
0.0005
VGG-16
CIFAR-10
250
256
SGD
0.1
10x. [160, 180]
0,0005
4.1 OBSERVATIONS, INTUITIONS AND ABLATIONS
Relationship between Ramanujan and performance: In Figure 1, we confirm that Ramanujan Ar indeed correlates with performance as a function of density (denser equates wider in general). However, this observation is already known (Pal et al., 2022), so it is not very exciting. The left column of Figure 1, which visualizes Definition 5, can only show that connectivity correlates strongly with density, but it cannot claim whether strong connectivity is related to relative performance. We attribute this missing link to the strong upper bound of (G)). While (G)) ensures that graphs that satisfy the inequality potential of the network. This brings us to our first contribution, which is the Iterative Mean Difference of Bound Aramdb-
expanders, see that it holds little correlation with the actual performance
7

---

Published as a conference paper at ICLR 2023
Pert'll Dendty &
Pert Deratty IND0
6.90
190
0.6
0.53
180
94
Seformacc
Crsth
-2
Cre5h
Bent
Fand
0.0
Network Derdity
Network Derskt
Perl'v. Density V. or v9916
Perf V. Density v. IMB vf
025
0.6
Peffumgacce
-225
-250
0.2
-2.35
SkiP
-1.00
0.0
SysFow
SytPoy
0.20 hetwork Denalty
3.20
Networn Dorstt
Figure 1: In these figures, solid lines always refer to the left y-axis, while dash lines refer to the right y-axis. Here, we illustrate the relationship between network density (x-axis), accuracy (left-y), and Ramanujan property (Ar (left column) and Arimdb (right column)) for Resnet-34 (top-row) and Bgg-166bbttommroww First, we show in all cases Ramanujan graphs correlate strongly with performance (upward trend). Second, we show that Arimdt also strongly correlates to relative performance between different Pal methods at different sparsity. Note that for Vgg-16, we dropped GrASP due to its inability to generate feasible mask.
Correlating relative performance with Arimat Figure right column shows that Arimas resolves the missing link stated early on. We demonstrate that Arimdl is able to correlate the degree of connectivity of individual sparse structures with their final ranking in performance at specific density levels. While its effectiveness lessens with increasing density, is undeniable that Arsmd mirrors the performance trend of various sparse structures. Intuitively speaking, can extend Arimab to be a performance ranker for unstructured sparse masks. Ultimately, the results prove our intuition that an irregular graph G is good expander if its regular subgraphs good expanders too.
On the relationship between performance and σ: When show that there exists ratio that provide ran- domness estimation on the graph, we are naturally curious about its relationship with performance. But first, need to perform a sanity check on a to see if it works. We can confirm, using our two random methods (Rand and ERK) on Figure 3, that they always yield o < O, no matter the settings. Now we observe from the left column Figure 3 that there seems to be little correlation between perfor- mance and the randomness
futuranca Deatty's Maddaniaal manaec
405
the graph first glance. The lack of correlation would support previous observa- tions made by Frankle et al. (2021); Liu et al. (2022) on the sufficiency of random pruning given the right sparsity. However, Figure quickly dispels these notions, which neatly brings to next point.
Figure 2: The relationship between per- formance and for Resnet-34 with and without skip. We observe starts to correlate with performance without skip- connections.
The value of o: We observe an interesting inverse relationship between o and Arimat for Resnet- 34 and 19. In Figure 3 right columns, observe Resnet-34 to have mutual correlation
8

---

Published as a conference paper at ICLR 2023
Fertormance Deraity RandemmCat monett
Performance Santom monet33
6.92
2.5
0.53
-10
Seformacc
0.83
922
Type
CruS
-0.-
Rard
2NP
46
0.84
Network Networkddorsky
Perfomanne
Performance V. Dendty V. Cn
1908 Perferrance Sandennedd
22-
Peffumgacce
1.0
0.5
-3
SysFhve
86-
3.00
Network
0.89 0.80
0.11 6:90 0.9
6.04
Figure 3: Identically formatted as Figure 1, on the left column, we illustrate the relationship between model's performance and network's 's randomness over global density for Resnet-34 and Vgg-16, 16. On the right column, we try to correlate the Ramanujan characteristic (Arimdt) with our Normalized Random Coefficient (NaRC) over performance. The observation is interesting because the relationship are perfectly inverted between our two models.
between its degree of expansion and randomness that somehow yield increasingly better performance. Mcanwhile, for Vgg-16, see that a higher degree of expansion correlates a lower degree of randomness, producing better performance. The second observation follows our specific intuitions, while the first observation seemingly contradicts them. How can randomness contribute to better performance? The answer turns out to be straightforward. In Figure 2, we compare the performance of Resnet-34 with and without skip connections various densities. We observe that (1) as the model gets more sparse without skip connections, its masked structure becomes more specific (less random) to ensure gradient flows; (2) skip connections help carry information and act as a crutch to overcome the random nature of the model; (3) without skip connections, Resnet-34 becomes more specifie; however, relying on gradients alone is not enough to recover the performance achieved by the model with skip connections. It all means that negatively affects performance for both models, and skip connections can help alleviate the symptoms while exacerbating the problem as they effectively hide randomness.
Overall, we have shown a way to relax the strong constraint on (a(G) such that the resulting graph's connectivity correlates strongly with its final performance. Further checking the lower bound for ((()) could indicate whether sparse structure deteriorates into randomness. Tying all together, we now have the necessary tool to locate the region where highly connected, highly sparse, and non-trivial expanders exist. While not our primary objective, we foresee future Pal works utilizing our metries as "checkers" guide the design of their new criteria in selecting sparse structures.
CONCLUSION
This work delved into quantifying Pal from the perspective of Ramanujan graphs. Firstly, we introduced Arimat as a novel way to relax the strong upper bound of Ar in cases highly sparse, highly connected networks. Secondly, we proved that there existed random coefficient called NaRC that could reliably estimate the degree of randomness for any given irregular sparse graph, which served lower bound for ji(G) beyond which sparse structure deteriorated into randomness. Ultimately, we provided a new perspective on the effectiveness of PAI that independent of weights, gradients, and losses. This work was purely scientific and no negative impact was anticipated.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors thank Peihao Wang for his valuable insights offered during the project discussions. Z. Wang is in part supported by NSF Scale-MoDL (award number: 2133861) and the NSF Al Institute for Foundations of Machine Learning (IFML).
REFERENCES
Kartikeya Bhardwaj, Guihong Li, and Radu Mareulescu. How does topology influence gradient propagation and model performance of deep networks with densenet-type skip connections? 2021 IEEF/CVE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 13493-13502, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877- 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Pau de Jorge, Amartya Sanyal, Harkirat Singh Behl, Philip H. S. Torr, Grégory Rogez, and Puneet Ku- mar Dokania. Progressive skeletonization: Trimming more fat from network initialization. ArXiv, abs/2006.09081, 2021.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners, ArXiv, abs/1911. 2020a.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952.
PMLR, 2020b.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, 2019. URL https:
//tpenreview.no./. net/ wtt.://nnne/oofotdtmeeee...
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning. pp. 3259-3269. PMLR, 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021. URL https: openreview net/ forum? I--o-i- -MK.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09577. 2019.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. International Conference on Learning Representations, 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015b.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural network. ArXiv, abs/1506 026666, 2015c.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pp. 293-299, IEFF, 1993.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
10

---

Published as a conference paper at ICLR 2023
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE international conference on computer vision, pp. 1389-1397, 2017.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang. and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: /tti::77120000000 2017.
Shlomo Hoory. A lower bound on the spectral radius of the universal cover of a graph. J. Comb. Theory, Ser. B, 93:33-43, 2005.
Shlomo Hoory and Nathan Linial. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43:439-561, 20999561,200000 2006.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alee Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Single-shot network pruning based on connection sensitivity. In International Conference Leurning Representutions, 2019. URL https:/ http:////ppeeevieeeeeeeeee
net/ wow.ffidd-1112gggeiii
Shiwei Liu, TT van der Lee, Anil Yaman, Zahra Atashgahi, Ferrar, Ghada Sokar, Mykola Pech- enizkiy, and DC Mocanu. Topological insights into sparse neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, ECMLPKDD, 2020.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. In International Conference on Learning Representations, 2022.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. International Conference on Learning Representations, 2018
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9()::2383, 2018.
Pavlo Molchanov, Stephen Tyree. Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. International Conference on Learning Represen- tations, 2016.
Michael Mozer and Paul Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3-16, 1989.
Alon Nilli, On the second eigenvalue of graph. Discrete Mathematics, 91(2):207-210, 1991.
Bithika Pal, Arindam Biswas, Sudeshna Kolay, Pabitra Mitra, and Biswajit Basu. A study on the ramanujan graph property of winning lottery tickets. ICMI,, 2022.
Shreyas Malakarjun Patil and Constantine Dovrolis. Phew Constructing sparse networks that learn fast and generalize well without training data. In ICML, 2021.
Ameya Prabhu, G. Varma, and Anoop M. Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In ECCV, 2018
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.06125, 2022.
Thomas Sauerwald and He Sun. Lecture 3: Expander mixing lemma, October
101 URL utLpttps::/ ws w
11

---

Published as a conference paper at ICLR 2023
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 ICLR., 2014.
Daniel A. Spielman. Properties of expander graphs, October 2018. URL httpt::t////. /wws:ss/www..... htt.:////oooeeeiiiiaaaa/a//////a
pdf.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonsse et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.04615, 04611, 2022.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. Advances in Neural Information Processing Systems. arXiv:2009. 1094, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. ArXiv, abs/2006.05467, 2020.
Dharma Teja Vooturi, G. Varma, and Kishore Kothapalli. Ramanujan bipartite graph products for efficient block sparse neural networks. ArXiv, abs/2006. 13486, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL https:
//tppree//ppeeeeeeew ew. net/ htw.eeeeooouumiidd33//eer.. d=s.umm/ksssssscc
Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. In ICML, 2020.
12

---

Published as a conference paper at ICLR 2023
A ADDITIONAL EXPERIMENTS ON CIFAR-100
Perl'v Density V. air resvet3
Pert Deraity winn of resnetii
0.85
300
6.75
0.0
3.75
-92
0.73
1.70
SysRiv
Sysftw
0.20 Network Dersity
Networrt
Herf
0.94-
2.5
6.92
1.2
6.90
1.50
0.33
2.00
0.55
2.55
0.54
2.54
0.52
Synt
BerShP
3.52
Syet
barSh
3.00
0.05
8:13
0.35
0.20
3.25
2:30
0.35
0.40
0.00
0.05
0.30
0.15
3.20
3.25
0.30
2.35
5.00
Figure 4: On these figures, solid lines always refer the left y-axis, while dash lines refer the right y-axis. Here we are illustrating the relationship between network density (x-axis), accuracy (left-y), and Ramanujan property (Ar (left column) and Aramdt (right column)) for Resnet-34 (top- row) and Vgg-16(bottom-roww) First, we show in all cases Ramanujan graphs correlate strongly with performance (upward trend). Second, we show Aramdt also strongly correlates relative performance between different Pal methods at different sparsity.
13

---

Published as a conference paper at ICLR 2023
Parformance Dersiy V. fandomcieal of nonet54
1908 V. Purformance fandombood of resnet54
6.-
6.85
0.0
0.0
0.33
prune Syps
p1ute, Iype
-1.
2M7
Systton
-3.
Cre5p
-066
ketwork denstty
Perforaanee
Nelormnnc's V. Demily BandomCCal
IN3B Neriomaane Randomiooll vgip5
0.24
2.0
ptune Type
0.72
SyrTow
0.95
1.0
-3.5
0.5
0.2
000
-00
3.0
SyrFow
6.30
0.10
2.43
Ketwark
Figure 5: Identically formatted as Figure 1, on the left column, we illustrate the relationship between model's 's performance and network's 's randomness over global density for Resnet-34 and Vgg- 16. On the right column, we try to correlate the Ramanujan characteristic (Arimas) with our Normalized Random Coefficient (NaRC) over performance. The observation is interesting because the relationship perfectly inverted between two models.
14


Reviews:
[{"review_id": "zg5MHpgvDJl", "reviewer": "Reviewer_Bf71", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new method to prune neural networks at initialization. By analogy to previous work which used sparse random subnetworks to speed up training, this paper instead uses Ramanjuan graphs, which are well-studied and known to be favorable with respect to expansion. It relaxes the eigenvalue condition of Ramanujan graphs to a new property (IMDB) which empirically correlates to increased performance when the network is trained on image classification tasks.", "summary_of_the_review": "The idea of measuring performance of pruning in terms of spectral properties of the adjacency matrix is a good idea. However, the choices made in deciding upon the IMDB measure seem arbitrary in comparison to existing measures of spectral expansion. The choice of comparing to $\\delta r$ is not entirely fair as a baseline, since that particular bound was designed around regular graphs.", "strength_and_weaknesses": "General comments\n-\n\n- Why use the third largest eigenvalue of the adjacency matrix? Usually the spectral gap is taken to be the difference between the first and second largest eigenvalues, which is guaranteed to be positive if the graph is connected.\n\nStrengths\n-\n\n- The idea of using expander graphs to guide pruning is interesting and unifies existing work.\n\nWeaknesses\n-\n\n- The decision to not use existing measures of spectral expansion is not entirely convincing. You mention that the Ramanujan condition is too pessimistic for non-regular graphs when $d_{max}$ is used, but why not use something like the second eigenvalue of the normalized Laplacian?\n- The decision to pass to all $K$-regular subgraphs seems somewhat arbitrary and possibly expensive to compute. \n- The pruning measure proposed does not leverage the weights of the network at initialization, since it does not sparsify the network based \n on sensitivity of the loss function.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ezT5zJ8u2NV", "reviewer": "Reviewer_pUbu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "It is believed there should be a strong correlation between the Ramanujan graph and PaI since both are about finding sparse and well-connected neural networks. This paper digs deep and rigorously establishes their non-trivial relationships in fine-granularity, e.g., ranking of difference sparse structures at the same specific global sparsity.", "summary_of_the_review": "See the strength and Weaknesses.", "strength_and_weaknesses": "Strength\n1.\tThis paper went beyond intuition and builds a new mathematical framework for understanding PaI. The differences from previous PaI studies (gradient- and graph-based) are clearly elaborated.\n2.\tThis paper also went beyond simply pulling off-the-shelf Ramanujan graph metrics to analyze DNN architectures (like prior art did). Instead it did several important modifications tailored for irregular bi-graphs and high sparsity levels, both are demanded in the PaI situation.\n3.\tThe authors are the first to identify a crucial limitation of Ramanujan property in analyzing irregular graphs, i.e., we could dismiss valid expanders due to the overly limiting requirements while retaining only graphs with random sparse-graph structures when analyzing high sparsity. They proposed a new metric called Iterative Mean Difference of Bound (IMDB) to mitigate the gap. This finding could be of independent interest to other applications where Ramanujan graph is relevant.\n4.\tThe authors also highlight the danger of being overly expansive, which risks graphs deteriorating into randomness. They proposed a lower constraint to avoid the danger of randomness.\n5.\tOverall, the authors show the key knob to be relaxing the strong upper bound constraint on the third large affinity matrix eigenvalue µ(G), such that the resulting graph’s connectivity correlates strongly with its final performance. Further checking the lower bound for µ(G) could indicate whether a sparse structure deteriorates into randomness. Experiments align well with their theories.\n\nWeakness\n1.\tI did not follow what differences the authors were referring to, between “trivial random sparsity” and “structurally meaningful masks”. What’s the criteria?\n2.\tExperiments are relatively limited. For example, only CIFAR-10 dataset is used as the testbed. Will the observations scale up to larger datasets? Also, could the authors find out whether some PaI methods can be obvious winners under their proposed metrics?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-gDJXlOYQA", "reviewer": "Reviewer_wCJu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to interpret the (un)success of Pruning neural networks at initialization (PaI). through the lens of the Ramanujan Graph - a class of expander graphs that are sparse while being highly connected. Despite the intuitive belief that PaI and Ramanujan Graph should be naturally related, their underlying relationships are shown to be more sophisticated and non-trivial as the authors analyzed. The authors supposed their analysis with ample experiments. ", "summary_of_the_review": "Overall, I would tend to accept this paper. If the author can address my concerns. I would be more convinced.", "strength_and_weaknesses": "\nStrength\n-\tMost prior works on PaI focus on “training signals” such as gradients. This paper studies a complementary angle of graph theory\n-\tAlthough there exist prior work connecting Ramanujan Graph and PaI, they did not consider the pseudo-randomness and irregular bi-graphs in practical sparse NNs, and may prefer “collapsed” naïve random graphs (overly expansive)\n-\tThe authors rigorously analyzed the limitation of Ramanujan Graph in modeling irregular graphs (practical DNNs) at high sparsity, and propose to relax the assumption on the eigenvalue upperbound\n-\tThe authors further proposed another metric to detect and avoid “trivial randomness” at high sparsity, by characterizing the same eigenvalue’s lower bound. \n-\tTogether, the authors demonstrate the novel finding, that a valid and desirable sparse NN architecture only exists when its graph adjacency matrix satisfies certain spectrum condition, e.g., its third-largest eigenvalue is both upper- and lower-bounded properly\n-\tThe authors experimentally validated their findings on SOTA PaI methods including ERK, SNIP, and SynFlow. \n\n\nWeakness\n-\tThe paper does not construct any new PaI approach, only observing how PaIs are correlated with their graph properties. It would be great if the authors could briefly share future insights of improvements.\n-\tOnly CIFAR-10 dataset is used in experiments. I’d suggest the authors to report on 1-2 more datasets in order to make their empirical evidences more consistently convincing. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%