Revisiting the Lottery Ticket Hypothesis: A Ramanujan Graph Perspective
Authors: BITHIKA PAL
Arindam Biswas
Pabitra Mitra
BISWAJIT BASU
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Neural Networks
Network Pruning
Ramanujan Graphs
Eigenvalue bounds
Spectral Gap

Abstract: Neural networks often yield to weight pruning resulting in a sparse subnetwork that is adequate for a given task. Retraining these `lottery ticket' subnetworks from their initialization minimizes the computational burden while preserving the test set accuracy of the original network. Based on our knowledge, the existing literature only confirms that pruning is needed and it can be achieved up to certain sparsity. We analyze the pruned network in the context of the properties of Ramanujan expander graphs. We consider the feed-forward network (both multi-layer perceptron and convolutional network) as a series of bipartite graphs which establish the connection from input to output. Now, as the fraction of remaining weights reduce with increasingly aggressive pruning two distinct regimes are observed: initially, no significant decrease in accuracy is demonstrated, and then the accuracy starts dropping rapidly. We empirically show that in the first regime the pruned lottery ticket sub-network remains a Ramanujan graph. Subsequently, with the loss of Ramanujan graph property, accuracy begins to reduce sharply. This characterizes an absence of resilient connectivity in the pruned sub-network. We also propose a new magnitude-based pruning algorithm to preserve the above property. We perform experiments on MNIST and CIFAR10 datasets using different established feed-forward architectures and show that the winning ticket obtained from the proposed algorithm is much more robust.

Under review as a conference paper at ICLR 2022
REVISITING THE LOTTERY TICKET HYPOTHESIS: A RAMANUJAN GRAPH PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks for machine learning applications often yield to weight pruning resulting in a sparse subnetwork that is adequate for a given task. Retraining these 'lottery ticket' subnetworks from their initialization minimizes the computational burden while preserving the test set accuracy of the original network. The exist- ing literature only confirms that pruning is needed and it can be achieved up to a certain sparsity. We analyze the pruned network in the context of the proper- ties of Ramanujan expander graphs. We consider the feed-forward network (both multi-layer perceptron and convolutional network) as a series of bipartite graphs which establish the connection from input to output. Now, as the fraction of re- maining weights reduce with increasingly aggressive pruning, distinct regimes are observed: initially, no significant decrease in accuracy demonstrated, and then the accuracy starts dropping rapidly. We empirically show that in the first regime, the pruned lottery ticket sub-network remains Ramanujan graph. Subsequently, with the loss of Ramanujan graph property, accuracy begins reduce sharply. This characterizes an absence of resilient connectivity in the pruned sub-network. We also propose modified iterative pruning algorithm which removes edges only the layers that are Ramanujan graphs thus preserving global connectivity even for heavily pruned networks. We perform experiments on MNIST and Ci- FARIO datasets using different established feed-forward architectures to support the criteria for obtaining the winning ticket using the proposed algorithm.
INTRODUCTION AND RELATED WORK
Neural Network (NN) and its recent advancements have made a significant contribution to solve var- ious machine learning applications. The power of an over- wer-parameterized NN lies in its capability to learn simple patterns and memorize the noise in the data (Neyshabur et al.) 2018). However, the training of such networks requires enormous computational resources, and often the deployment onto low-resource environments such as mobile devices, or embedded systems becomes difficult. Recent trend in research to reduce training time of deep neural networks has shifted towards pre- training following the introduction of a remarkable contribution, named the Lottery Ticket Hypothe- sis (I.TH), which hypothesize the existence of highly sparse subnetwork and weight initialization to reduce the training resources as well (Frankle & Carbin 2019). It uses a simple iterative, magnitude- based pruning algorithm, and empirically shows that even after removing approximately 90% of the weights, the subnetwork can preserve the original generalization error. In the subsequent studies, the focus goes finding this lottery ticket for more competitive tasks by pruning with weight rewind- Frankrek et al. 2019a), fine tuning the learning rates (Renda et al. 2020), more efficient training You al. 2019 Brix et al. 2020 Girish et al. 202T).
Neural network pruning involves sparsification of the network (LeCun et al.
1990 Blalock et al.
2020 It identifies the weight parameters, removal of which incurs minimal effect on the general- ization error. There exists different categories of pruning based on (i) how the pruning is performed, for instance based on the weight magnitude (Han et al. 2015 Zhu & Gupta 2017), gradient in the
backpropagation, hessian of the weight (Hassibi al.) 1993 Dong et 2011 Lee et al. 2018), etc; (ii) whether the pruning is global or local; (ii) how often pruming should be applied like one-shot
Lee al. (2018); Wang et al. (2020), iterative Tanaka et al. (020).. One of the primary goals in the literature has been to reduce the computational footprint at the time of prediction, i.c., during post-training. In recent LTH studies, the victim weights are determined by their value the ini-

---

Under review as a conference paper at ICLR 2022
tialization, gradient of the error, and network topology Lee et al. understand weight initialization, Malach et al. (2020) show that pruming makes a stronger hypoth- esis with bounded weight distribution. The sparsity of the network is reduced from polynomial to
(2019): Tanaka et al. (2020) To
a logarithmic factor of the number of training variables (Orseau et al. 2020). Mocanu et al. (2018) suggest consider the topology of the network from network science point of view. The pruning algorithm starts from a random Erdós Rényi graph and returns a scale-free network of high sparsity factor based on the number of neurons in each layer. The method is further evolved for convolution layers considering both the magnitude and gradient of the weights(Evcl et al. 2020a).
Various analysis for explaining the LTH have been attempted in the past. Researchers EEei et al. (2020b) explain empirically why the LTH works through gradient flow at different stages of the training. Despite previous attempts to explain why the Lottery Ticket Hypothesis works, the under- lying phenomenon associated with the hypothesis still remains ill-understood. All of these studies related to LTH identify that sparse sub-network can be trained instead of a complete network and the network needs to be connected from input to output layers. However, none of them try to explain the LTH and the properties of the pruned network through the lens of spectral graph theory. The network connectivity can be described from the graph expansion point of view, where any subset of vertices of size less than or equal to half of the number of vertices in a graph, is adjacent to at least fraction of the number of vertices in that set; for details, see (Lubotzky 2010). Graphs satisfying this property are known as expander graphs. The Ramanujan Graph is special graph in a bounded degree expander family, where the eigenbound is maximal (Nilli 1991). This leads to a maximum possible sparsity of a network while preserving the connectivity.
In this paper, we initiate study to observe the characteristies of a pruned sub-network from the spectral properties of its adjacency matrix, which, has not been reported previously. We represent a feed-forward neural network as a series of connected bipartite graphs. Both weighted and un- weighted bi-adjacency matrices are considered. The Ramanujan graph properties of each of the bipartite layers are studied. We use the results of Hoory (2005) on the bound of spectral gap for the weight matrix of pruned network. It is empirically observed that existence of winning tickets in pruned network is dependent on the Ramanujan graph properties of the bipartite layers. As network sparsity increases with more aggressive pruning, we obtain regions where test set accuracy do not decrease much and the bipartite layers satisfy Ramanujan graph property. Subsequently we obtain regions where the Ramanujan graph properties are lost for all the layers and test accuracy decreases sharply. Also, we observe that the impact of noise in the data, on test set accuracy is more adverse when some of the layers lose their Ramanujan graph properties. Experimental results are presented for the Lenet architecture on the MNIST dataset and the Conv4 architecture on the CIFAR 10 dataset. Results for other popular feed-forward network are presented in the Appendix.
We suggest that preservation of Ramanujan graph properties may benefit existing network pruning algorithms. We propose a modified pruning algorithm that uses the spectral bounds. The algorithm identifies network layers that may still be pruned further, while avoiding pruning in layers that have already lost their Ramanujan graph property. Neural network weight score functions suggested by various pruning algorithms are used to represent the bipartite layers as weighted graphs. Spectral bounds for these graphs are used to verify the Ramanujan property. For number of popular pruning algorithms, we experimentally demonstrate significant improvement in accuracy for sparse networks by using these connectivity criteria.
Contributions: The contributions of the paper are the followings:
1. We propose a methodology for analyzing winning lottery tickets with respect to their spectral properties.
2. We empirically observe that winning lottery tickets often satisfy layerwise bipartite Ramanu- jan graph property representing a sparse but resiliently connected global network. The property is checked using spectral bounds that generalize to irregular networks. We also notice better noise ro- bustness when all the layers of the pruned sparse networks preserve the Ramanujan graph property. 3. Based on the above property we propose a modified iterative network pruning algorithm that attempts to preserve Ramanujan graph property for all the layers even at low network densities. identifies layers that are still amenable to pruning while avoiding further pruning in layers that have lost their Ramanujan graph property. We report significant performance improvement for a number of popular pruning algorithms modified using this criteria.
2

---

Under review as a conference paper at ICLR 2022
2 THE LOTTERY TICKET HYPOTHESIS AND NETWORK PRUNING
The lottery ticket hypothesis states that a randomly initialized, dense neural network contains a subnetwork which when trained independently using the same initialization achieves test accuracy close to the original network after training for less or at most the same number of iterations |Franlle & Carbin (2019). These subnetworks, denoted as 'winning tickets', can be uncovered by network pruning al algorithms. Weight pruning is one such simple strategy. Let the original dense network be represented as the function (z; 0), where x is the input and 6 are the weights. The weights have an initialization of lo. Weight pruning generates a mask m {0, 13101 can be represented by (2;; m @ 0) with initialization m @ 0o-
|0| such that the pruned network
Pruning algorithms that are used to obtain the winning tickets can be either one-shot or iterative. In one-shot pruning the original network is trained to convergence, then p% of weights are pruned and the surviving weights are re-initialized their values in 8g followed retraining/fine tuning the subnetwork. Here, the network training and pruning are not simultaneously performed and pruning occurs only after convergence is reached. Iterative pruning repeats one-shot pruning over several iteration. This often leads to higher pruming percentage while retaining test set accuracy. However, iterative pruning is more time consuming than one-shot pruning. After pruning the surviving weights may alternately be initialized to their values in 0,, i denoting small iteration number, rather than their initial values in 0g. This process, as illustrated in Figure [ Frankle et al. 2019b), is denoted as rewinding and is effective for large networks. We adopt this in our study.
Various scoring functions are used to prioritize the weights for pruning. They may be based on weight magnitudes, gradient, information flow (Blalock et al. 2020 Hoefler et al., (021) or saliency TTanaka et al. 22000) Magnitude pruning provides a simple method for obtaining the pruning mask by retaining the top p% weights Wi E 0 that have the highest values of jwy]- The role of the weights in local computation in the net- work layers is not considered. A higher pruning effi- ciency may achieved by algorithms that account for connectivity structures in the individual layers. In the next section we describe graph parameters of the net- Figure 1: Iterative Network Pruning with work that determine such connectivity.
Prakig
Tueday
ThE
Rewinding Frankle et al. (2019b)
EXPANDERS AND RAMANUJAN GRAPHS
Expanders are highly connected, and yet sparse graphs. In this work, we shall be considering finite, connected, undirected, but not necessarily regular graphs. Recall that the degree of a vertex v in a graph the number of half edges emanating from v.
Definition 1 ((n, d, exxpande)))) Let > O. An (n, d, e)-exaander is graph G = (V. E) on
[V| = n vertices, having maximal degree such that for every set 0 + U C satisfying |0| < 2' |8(U)) 2 e holds.
Here, 8(U) denotes the vertex boundary of U. The quantity and the infimum (8(E)
[((')) D
measures the rate of expansion
[ as U varies among the non-empty subsets of with |U| S [V] is called the (vertex) Cheeger constant h()) of the graph g. The higher the value of h(g), the more expansion property it exhibits and vice versa. Expansion and the Cheeger constant quantifies the connectivity properties of a graph as high value of h()) signifies that the graph is strongly connected. This ensures that information can flow freely without much bottlenecks.
2
Definition 2 (Expander family) A sequence of finite, connected graphs {G, = (V,, E.) E.)=,,,,.. on V. vertices and E, edges is called an expander family if there exists an uniform e such that each graph in the sequence is an ([Vi), d,, e) expander for some d, 's.
The study of expansion propertics of graphs is closely related to the study of the spectrum (dis- tribution of eigenvalues) of the adjacency operator defined on them. Given finite r-regular
3

---

Under review as a conference paper at ICLR 2022
graph of size [V] n, the eigenvalues t, of the adjacency matrix are all real and they satisfy, -r S tn S ... S 12 S t = 7. The graph is connected iff t2 < t and is bipartite iff t, are sym- metric about 0 (in particular t, = -r). The quantity t t2 is known as the spectral gap and it is related to the Cheeger constant via the discrete Cheeger-Bure
inequality, discovered independently by Dodziuk (1984) and by AAlnn & Milman (1985). In our context, we consider stronger notion of the spectral gap (but it is equivalent for bipartite graphs). Let t == max : 1 < i S n, |t,] < f1). In here, the quantity 1 - will denote the spectral gap.
The more connected a graph is, the larger is the spectral gap and ideally, a graph with strong expan- sion properties has very large spectral gap. However, for a bounded degree expander family, this spectral gap cannot be arbitrarily large. This brings us to the notion of Ramanujan graphs.
Definition 3 (Ramanujan graph) Let 9 be a r-regular graph on n vertices, with adjacency eigen-
values (f. (4)):=1,2....) satisfying -r in ... S l/2 S 1 = Let ((g) == max max(44] <is n, [t]] < 3. Then G is a Ramanujan graph ift - 2 2 2 I.
The fact that in bounded degree expander family, the eigenvalue bound in Ramanujan graphs is maximal can be deduced from the following result due to Alon, see Nilli 1991). (()) 2 2/r -
2-r-I-1 [m//2] where denotes the diameter of the graph. As m + too and is bounded, obtain the result (this also follows from the Alon- Mlon-Boppana theorem).
For our applications, we shall encounter not necessarily regular graphs, thus we need notion of irregular version of Ramanujan graphs. The two ways we shall exploit Definition for irregular graphs will be to:
1. Use the average degree davy in place of the regularity.
2. For weighted graphs, use 11, the largest eigenvalue of the adjacency matrix.
Note that a motivation for considering the above bounds comes from the following generalisation of the definition of Ramanujan graphs to irregular graphs. For finite, connected graph G (not necessarily regular) consider its universal cover G. for details see (Hoory et al. 2006, sec. 6). A Ramanujan graph is graph satisfying t(G) S p(g) where p(ğ) denotes the spectral radius of ğ. (Mareus et al., 2015, sec. 2.3). A result of Hoory, see Hoory 2005) implies that 2./davg - S p(9). Thus, makes sense to consider ((g) S 2 p(G). The above consideration also result in extremal families, Hoory (2005). Further, for irregular bipartite graphs, with minimal degree at least two and an average degree daegr. on the left and dangR on the right, we can further consider the sharper estimate t(G) I /davgL- - II+ v /daggR - I S p(g) see Hoory 2005).
See also Banrus-Spielman-Sriveee
Upto now, we had only discussed about unweighted graphs. weighted graph is a graph with a weight function w E - R20 attached on the edges. It can be looked upon as generalisation of unweighted graphs, in the sense that in the unweighted case, the function w takes values in the set {0, 1}. In the case of weighted networks, we shall use the absolute values of the weight functions according to the architecture for the corresponding dataset. This also means that in the case of weighted graphs, we need modify the definition of the edge set of the graph to incorporate multiple (as well as fractional) edges. The theory of characterisation of weighted Ramanujan graphs is not well developed. However, characterisation of weighted expanders (with positive weights) exist, due to the Cheeger inequality for such graphs, see (Chung) 1996) sec. 5) and we use the largest eigenvalue of the adjacency matrix in place of the regularity. In the case of regular graphs, it coincides with the notion of Ramanujan graphs and even in the general case, by the Cheeger inequality, it ensures a large expansion which in turn implies that there no bottleneck to the free flow of information. This forms the theoretical basis of our work.
4 RAMANUIAN GRAPH CHARACTERIZATION OF NEURAL NETWORKS
We can represent any neural network using graphs (possibly weighted, depending the context) and in this article, we will be dealing with a sequence of finite, bipartite graphs. This is because if N denotes neural network having layers N,, N2,..., ,N respectively, then each N (i 1,2.....)
4

---

Under review as a conference paper at ICLR 2022
is complete bipartite graph to start with. A pruned subnetwork results in edge sparsification of the underlying graphs. For that purpose, we need to approximate complete, bipartite graphs by sparse, proper subgraphs. The motivation to study pruning based on expander characteristics stems from the fact that complete graphs can be approximated using expanders, see S The notion of Ramanujan graphs allow to quantify the pruning limit, and we empirically justify technique.
In Figure we present examples of three small forwad networks with a single hidden layer and four neurons in each layer. The networks con- sists of two bipartite graphs corresponding to the input-hidden and hidden-output layers. The spar- sity of all the three networks, as measured by the number of edges present, are the same. How- ever, in the first network none of the layer-wise Figure 2: Examples of small feed-forward net- bipartite graphs satisfy the expander property and works having same sparsity but different connec- thus information flow from a significant number tivity properties; (a) disconnected network, (b) of input nodes to output nodes are disrupted. For partially connected (c) strongly connected. When the second network, the input-hidden layer bipar- all of them are scaled to larger networks, (c) has large spectral gap compared to (a) and (b) signify- tite graph is an expander. while the hidden-output ing a high rate of expansion.
layer bipartite graph is not an expander.
Here few of the flow paths from input to the output nodes are disconnected. Both the bipartite graphs for the third network are expanders, thus all the inputs nodes are connected to all the output nodes. We denote the first network
disconnected one, the second network partially connected, and the third one as fully connected. The example illustrates that layer-wise sparse bipartite expander graphs ensures global information flow across layers. While connected but non-expander sparse bipartite layers do not necessarily lead to global connectivity across layers. It is known in literature that sparse but resiliently connected neural networks not only have good generalization performance but also achieve noise robustness (Liu et al. 2018
4.1 BIPARTITE GRAPH STRUCTURE
In this work, we focus on the fully-connected layers, and convolution layers of the feed-forward neural network only. Since, pruning is a part of network compression, we only consider the trainable layers here. We consider both unweighted and weighted representations
the bipartite graphs. We ignore signs of the weight values and consider only the magnitudes for the weighted graph representation. Even though sign of the weights are important for determining the neural network functionality, argue that for studying their connectivity properties only the magnitudes need to be considered.
Fully Connected Layers (FC): For fully connected layer N with n=11 number of inputs and n' number of outputs the weighted bi-adjacency matrix of the corresponding graph is W, E Rin *xn'l, and the corresponding pruning mask is M, {0, 1 'xn').
Convolution Layers (Conv): Here, we consider the kernel size, the number of input and output channels to unfold the layer into complete bipartite graph. For a convolution layer N with the kernel of size k, n² imput, and n' output channels, the weighted bi-adjacency matrix of the corresponding graph will be W; E glin xn*))xn)) and the corresponding pruning mask is M, E {0. 1 |](re= -kk))='), An example is shown in Figure
3
ourputs ar, Tayer
bi-parttite graph
ioputs laver
Figure 3: An example of bipartite graph computation for particular convolution layer with kernel size 2 x 2, 2 input channels, and 3 output channels
5

---

0) for par- Under review as a conference paper at ICLR 2022
Now, the bounds analyzed for both unweighted (M,) and weighted (W;) bipartite graphs each layer N,. Table I describes different bounding constraint depending on the type of the considered graph and bound type. We consider the bound differences (Aş and Ax) for the eigenvalue and aver- age degree respectively. A transition of the A values from positive to negative denotes a violation of the bounds, and thus loss of Ramanujan graph property of the bipartite graph for the corresponding pair of layers in the feed-forward neural network.
Table I: Different bound criteria on the second largest eigenvalue to of the bi-adjacency matrices
BI-ADIACENCY
EIGENVALUE (eb)
AVERAGE DEGREE (db)
Unweighted (M;)
(2,)) E (M,
UD: 12 (M.) S Vurye (M.) - v (aaog((M.))
Weighted (W,)
WE: (W,,) 22/4(,
difference on bound
As (2/41 12)/t2
AR (Vdavot davan t2)/t2
4.2
RAMANUIAN GRAPH PROPERTY PRESERVING PRUNING ALGORITHM
In this section, we describe a modification of the iterative pruning algorithm that preserves the Ramanujan graph property of pruned neural network. In iterative pruning algorithms, pruning is employed once the training is complete (i.e. after it converged to an optimum or it reached certain epochs). The pruned network trained again with its initial weight values to perform the next pruning iteration. The magnitude of a score function 0 is used to identify the victim weights. The weights are made to zero if their score function values lie in the bottom p percentile. In the Iterative Magnitude Pruning (IMP) Frankle & Carbin (2019), magnitude of the weight is used as the score function. More sophisticated score functions are used in SynFlow (Tanaka al., 2020). SNIP (Lee al. 2018).
Algorithm LAYER-WEEL WISE CONNECTIVITY BASED PRUNING
Input: Trained Network N, Score function H, Pruning percentile p. pruning level
We propose modification the above method. If weight is identified victim based the above score function based scheme: we check the Ramanu- jan property of the layer N, to which this weight belongs. First, we verify the connectivity prop- erty of the layer using the bounds on the unweighted graph as de- fined Table [[s, Ar > 0). If the unweighted graph bounds are not satisfied, we consider a weighted graph with tion values as the edge weights. The bounds using the eigenval- ues of this weighted graph is used verify the spectral expansion property (As ticular layer. the pruned net- work Neemp follows the Ramanu- jan graph property given by the bounds, then the algorithm simply proceeds to the next level of prun- ing operation.
Output: Pruned Network N N*
for
1o
k
while k S K do N. <- PRUNEBYPERCENTIEEPY" (,, using the score Cunction
1/ Prune
CALCULATE dangL dougR OF Niemp if min(ddagg, dargit) 2) then
N < N
/1 To avoid layer collapse
BREAK
end
CALCULATE As. Ag N Nompp if im (uun(A,,Ad, Ag) then
func-
N N Satisfy Ramanujan Property the unweighted graph
BREAK
else
CALCULATE AS N USING if A 0 and f. then
N + N temp // Satisfy Expansion Property N, using 8; as weights
BREAK
20
end
11
end
k
13
end
24 end
23 nure return
If the bound is not satisfied for particular layer the weights simply reset to the values be- fore pruning and the pruning percentile p is halved and search for a better approximation of N, is resumed. The target pruning level & [K] is controlling parameter to limit the search iteration.

---

Under review as a conference paper at ICLR 2022
The proposed algorithm attempts to preserve Ramanujan property for many layers possible by using the spectral bound criteria to determine the layers which are still amenable to pruning. It avoids further pruning of the layers that have lost their connectivity property. We experimentally show that the approach is effective when used with IMP, SNIP, SynFlow pruning algorithms with their designated score functions.
The method is described in Algorithm I It takes the trained network N, score function 6, pruning percentile p. pruning level K inputs and returns the pruned network N as output. This algorithm is called at each pruning iteration, and continued till the stopping criterion is met, i.e., N = N,, vi. As discussed in Section 3 we mainly study two types of bounds on the second largest eigenvalue of the bipartite graph t2 = t(G). i.c. (i) eb- based on the largest cigenvalue(t1) and (ii) db- based on the average degree (daugt. and davgR). Here, G for a bipartite neural network layer N; either the unweighted graph or weighted graph with score functions as the weights. In order to avoid "layer collapse' we stop pruning for layer the bipartite graph has a node with degree less than two in either of the parts.
The top-2 largest magnitude eigenvalues at layer are computed from the symmetric matrix N N; with implicitly restarted Arnoldi methods (Lehoucq et al. 1998) and, the average degree is com- puted from the connected component of the bipartite-grann grapt. Hence, the computational complexity mainly driven by the pruning level K, the number of input and output neurons at each layer, and the number of layers. The additional space will be required to store the bipartite graph of a layer. For the convolutional layers the size of the adjacency matrix is effectively same the size of the convolution kernel which is usually small. Also, the usually the number of fully connected layers are not very high.
EXPERIMENTAL RESULTS
We have used the MNIST and CIFARIO datasets in our study. As an evaluation measure we use the classification accuracy for both clean and noisy test sets. Noisy test sets were generated by adding zero mean a variance Gaussian noise to the image pixels. We report results for the Lenet, and Conv4 network architectures following the methodology adopted in Frankle Carbin (2019). We also perform the studies on other networks which are presented in the Appendix. Hyperparameter values used in our experiments are reported in Table in the Appendix.
5.1 EXPERIMENTAL SETUP
We study the variation of classification accuracy with the network density as measured by the re- maining weights percentile 100 p. where is the pruning percentile. For different layers the percentile can be different, as denoted by pfc for fully connected (FC) layers, Prone for convolution layers, and Pout for the output layers. We study the two cases for the bound specific to unweighted (M,) and weighted graph (W.). For each of the studies, we plot four parameters; (i) eigenbound bound difference (As). (ii) average degree bound difference (ii) network density for each layer, and (iv) test accuracy on both clean and noisy data. The degree and eigenbound differences are defined in Table
Relationship between Ramanujan graph properties and LTH The primary goal of our study is identify the LTH regimes, determined by the spectral properties of the bipartite-networkk layers. The existence of LTH regime is illustrated for two representative established networks. The results for Lenet on MNIST dataset shown in Figure and for Conv4 on CIFARIO shown in Figure In each of the plots, we show the variation of classification accuracy on clean and noisy test sets (having various noise levels (o)), with the remaining weights percentile. The spectral properties are characterized by eigenbound difference Ag for both the weighted and unweighted graph repre- sentations, and the degree bound difference ÅR for only the unweighted graph representation. A transition of As and ÁR from positive to negative values denotes the loss of Ramanujan graph prop- erty of the corresponding layer bipartite graph. Accordingly. the plot is divided into three regimes- (i) fully Ramanujan, where all the layers maintain the Ramanujan property i.c., A > 0, VN,, (ii) par- tially Ramanujan, where some of the layers maintain the property, and (iii) non- non-Ramanujan, where none of the layers retain the property. For the Conv4 network which has more number of layers
7

---

Under review as a conference paper at ICLR 2022
show results for the unweighted graph representation only. Similar results for other networks and different pruning settings are discussed in the Appendix.
clean
0.25
o=0.40
07
0.50
0=0060
1.0
1.2
1.0
1.2
1.0
0.8
-unweiggnte
0.8
0.8
0.6
welghted
0.6
0.4
0.6
Test
0.5
4,01
0.5
0.2
4p-11
0.0
4,42
4.41
0.3
0.3
-0.2
Network 2.9
Network Density
(a) unweighted graph representation
(b) weighted graph representation
Figure 4: Results for MNIST dataset on Lenet architecture; (a) considering unweighted bi-adjacency matrices, (b) considering weighted bi-agjacency matrices. Variation of accuracy with network den- sity is plotted for the clean and noisy test sets with increasing noise variances a. Error bars for the accuracy values computed over 5 runs are shown. For the layers L1, L2, and L3 the values of As are plotted for both unweighted and weighted representations, and AR for only the unweighted representation. As mentioned in Table D As and AR denote the difference bounds the eigen- values and average degrees. Transition of the A values from positive to negative denote the loss of Ramanujan graph property. The plot divided into three regimes- fully Ramanujan (gray shade), where the Ramanujan graph property holds for all the layers, partially Ramanujan (pink shade), where the property holds for some of the layers, and non- aon-Ramanujan (no shade) where none of the layers retain the property.
1.0
1.0
clean
clean
#=0.10
ow0.10
6-0.20
0=0.20
0:0.30
0.8
0:30.0
0.8
6o. As unweighted
Luwwerg
Test Accuracy
0.8
Accuracy
0.6
0.6
0.4
0.2
0.4
0.0
Ba
Bg
-16
-0.0
0.0
100.0 63.4 40.7
26.4 17.1
7.3 Network Density
11.2
4,9
3.1
2.1
1.3
0.0
100.0 63.4 40.7 26.4 17.1
11.2
7. Density
4.8
3.1
2.1
1.3
(a) Convolutional layers
(b) Fully-connected layers
Figure 5: Results for CIFARIO dataset on Conv4 architecture considering unweighted graph. Re- sults for the convolution layers (L2,3,4) is shown in (a), while for the FC layers (L5,6) is shown in (b). We exclude the first and last layers in this study, due to the low cardinality of one of the parts in the bipartite graph for these layers. These layers are usually not pruned by the pruning algorithms.
In all the figures, we observe that the accuracy values start dropping sharply beyond the partially Ramanujan graph property boundary (pink shade) when all the layers loose their Ramanujan graph property. Accuracy also starts reducing slowly from the fully Ramanujan boundary (gray shade). The accuracy on clean data falls sharply when the layers do not satisfy the bounds for the weighted graphs. The bounds for the unweighted graph allow only the robust winning tickets, having high accuracy
noisy data. For very low network densities it is that the A values become positive again. This is a boundary effect owing to the in in-appliaability of Ramanujan graph bounds for disconnected graphs.
8

---

Under review as a conference paper at ICLR 2022
Table 2: Results of different pruning algorithms under the Ramanujan Graph property preservation
Pruning
Leneu/NIST
ConyA/CTFARTO
Algorithm
a
Density
Test Accuracy
a
Densily
Test Accuracy
Without Pruning
0.0
100.0
97.16
0.0
100.0
85.86
IMP
1.5
3.16
93.88
1.0
10.0
81.91
IMP
2.0
1.0
45.39
2.0
1.0
IMP-Bound
3.6
96.74
10.4
81.8
SNIP
1.5
3.16
79
1.0
10.0
80.3
SNIP
2.0
1.0
49.8
2.0
1.0
64,26
ENIP-Bound
7.64
95.41
10.0
79,8
SynFlow
1.5
3.16
95.92
1.0
10.0
82.5
SynFlow
2.0
1.0
49.11
2.0
1.0
69.2
SynFlow- Bowud
1.33
93.82
1.15
64.5
Comparison of pruning approaches We show that consideration Ramanujan graph properties benefits network pruning algorithms. We consider three popular network pruning algorithms (i) Iterative Magnitude Pruning (IMP) Frankle & Carbin 2209), (ii) the iterative verion of Single- shot Network Pruning based on Connection Sensitivity (SNIP) et al. (2018), (iii) Synaptic flow based pruning SynFlow Tanaka et al.] (2020) and show the results of accuracy achieved with similar densities with and without the bound condition. To do this experimentation, we choose the fix compression ratio a to achieve the desired density of the pruned network as 10 x 100, and observe the difference in accuracy due to the network connectivity. The results are presented in Table 2 for Lenet/MNIST and Conv4/CIFARI0 10. For each of the algorithm we consider two cases (i) the network is pruned to very low densities using existing algorithms, (ii) network pruning is stopped when there is loss of Ramanujan graph properties (#AlgoName- -ooundd..dd. The bounds are considered as two types of bounds- first it tries maintain the bounds the unweighted graph. Next, if the unweighted graph looses the Ramanujan property it tries to preserve the information flow by considering the spectral bounds for the weighted graphs with score function. We use layer-wise pruning for all the algorithms.
Here, adding the bound criteria guides the pruning algorithm stop a density where the accuracy is comparable with its original network. These values are marked in bold in Table 2 The high- est improvement is achieved by SynFlow algorithm for the Lenet architecture on MNIST dataset. While the usual SynFlow algorithm results in an accuracy of 49.1 19%11% at the density of 1.0. the SynFlow-Bound algorithm has an accuracy of 93.3 82% for network density of 1.33. For the Conv4 architecture on CIFAR10, the scope of improvement using the bound criteria is limited since the existing algorithms preserve the unweighted graph connectivity property for most of the layers. We have also studied the spectral properties of all the layers the results are presented in the Appendix.
We can also observe the difference of an arbitrary non-expander graph with an expander one of similar density. As an example, we see the result for Conv4/CIFAR10, With density of 3.16 the IMP achieves accuracy of 60.61% while SynFlow meets 77.18% accuracy. By analyzing the detail has been found that the Ramanujan property is lost in FC layer-1 only for SynFlow where the same is observed in IMP for both Conv Layer-4 and FC layer-1. Hence, IMP loses more Ramanujan graph property whole in the entire network.
6 CONCLUSION
In this work, we study the validity of the lottery ticket hypothesis (LTH) based on structural con- nectivity properties of the neural network. Ramanujan graph properties of the bipartite layers are studied in terms of certain spectral bounds. As test accuracy varies with decreasing network density as result of pruning, three distinct regions are demarcated using these bounds. In the first region, all the bipartite layers are Ramanujan graphs, in the second region some of them are, and in the third low network density regions none of the layers are Ramanujan graphs. We empirically demonstrate the validity of the lottery ticket hypothesis robustly in the first region and partially in the second re- gion. We propose a modification of existing iterative pruning algorithms that preserves Ramanujan graph property. Further refinement of this approach of pruning can result in more efficient winning ticket search, which will be the basis of future research.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
N. Alon and V. D. Milman. A1. isoperimetric incqualities for graphs, and superconcentratons. J. Combin. Theory Ser. B, 38(1):73-88, 1985. ISSN 0095-8956. 90092-9. httpsttt:/// / doi. wtt.://.............11.11111.11. 101.//10..11100353330 8956 (85) 90092-9
doi: 10.1016/0095-8956(35)
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv preprint arXiv:2003.03033, 2020.
Christopher Brix, Parnia Bahar, and Hermann Ney. Successfully applying the stabilized lottery ticket hypothesis the transformer architecture. arXiv preprint arXiv:2005.03454, 2020.
R. K. Chung. Laplacians graphs and Cheeger's inequalities. Combinatorics, Paul Erdōs is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pp. 157-172. János Bolyai Math. Soc., Budapest, 1996.
Jozef Dodziuk. Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc., 284(2)787-794, 1984. ISSN 0002-9947, doi: 10.2307/1999107. URL /tttts:///oi..oooo
10 913/0/...000111133333999999911
Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning to prune deep neural networks via layer- wise optimal brain surgeon. arXiv preprint arXiv:1705.07563 2017.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference Machine Learning, pp. PMLR, 2020a.
Utku Evei, Yani A Ioannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural net- works and how lottery tickets win. arXiv preprint arXiv:2010.03533, 2020b.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural net- works. In International Conference on Learning Representations (ICLR), 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv:1903.0161 2019a.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. The lottery ticket hypothesis at scale. CoRR, abs//900.00111. 2019b.
Sharath Girish, Shishira R Maiya, Kamal Gupta, Hao Chen, Larry S Davis, and Abhinav Shrivastava. The lottery ticket hypothesis for object recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 762-771, 2021.
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:1 133-1143, 2015.
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, IEEE, 1993.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training neural networks, 2021.
Shlomo Hoory. A lower bound on the spectral radius of the universal cover of a graph. J. Combin. URL
Theory Ser. B, 93(1):33 43, 2005. ISSN 0095-8956. doi: 10. j...116/.ett..204..66 http:////bo..0010......0000 1ct. 2004. 06.0001
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their ap-
plications. Bull. Amer. Math. Soc. (N.S.), 43(4):439 561, 2006. ISSN 0273- 0979.
doi: 10. 00.1999/0227--9999.0---1001111
URI hotps: :/tbs:://ooo worg/10...... 105/010.100000 10907
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, pp. 598-605, 1990.
10

---

Under review as a conference paper at ICLR 2022
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv:1810.02344 2018.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Torr. A signal propagation perspective for pruning neural networks at initialization. arXiv preprint vrxivv1906.. 0906006377, 2019.
Richard B Lehoueq, Danny C Sorensen, and Chao Yang. ARPACK users' guide: solution of large- scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, 1998.
Mengchen Liu, Shixia Liu, Hang Su, Kelei Cao, and Jun Zhu. Analyzing the noise robustness of deep neural networks. CoRR,
2018. URL
wwwpxxivv..orr..ooo abs/
03913
Alex Lubotzky. Discrete groups, expanding graphs and invariant measures. Springer Science & Business Media, 2010.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning all you need. arXiv preprint arXiv:2002.00585, 2020.
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2), 182()):307-325 2015. ISSN 0003-486X. doi: 10.4007/ammls.2015.1822 1.7
URL https: http::::/doc.oggg//o// /004/0000/aaa//// 2015.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature communications, 9(1):1-12, 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of over-paramettizztion in generalization of neural networks. arXiv preprint arXiv: 12076, 2018.
A. Nilli. On the second eigenvalue of a graph. Discrete Math., 91(2):207-210 1991. ISSN 0012-365X. doi: 10. 02210166000233661199110011111 (012)3655(911)01122
URL. htttps:///ci..o/ .orii.or//// worg//100 10. 10167
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Ad- vances Neural Information Processing Systems, 33, 2020.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint arXiv:2003.02338 2020.
Daniel A. Spielman. Properties of expander /
cs
spie 1allmmm/////mmtii pdd 2018.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.055: 05467, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing carly-bird tickets: Towards more efficient training of deep networks. arXiv preprint arXiv: 1957, 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878, 2017.
11

---

Under review as a conference paper at ICLR 2022
A APPENDIX
We present additional results to supplement those given in the paper. The results for corresponding to the LTH hypothesis is presented. Then detailed results concerning the pruning algorithms are described.
A.1
MORE RESULTS FOR LENET ARCHITECTURE ON MNIST DATASET
La Aomoeii
La Aamovii
(a)
(b)
(c)
Figure The results for Lenet using MNIST dataset with pruning percentile Pfc 0.2 and Pout 0.1 syyyer-wse-ppuning (a) eigen factors for the unweighted graph, (b) eigen factors for the weighted graph, (c) test accuracy
Unelp heand
Limd doond
Lolenbes)
Ghopeplooed
Londe
Text Accurary
0003 3t2 282
223 ES Danalty
McDwork Denaity
123
106. 313 132
324
Denaity
(b)
(c)
Figure 7: The eigen factors for global pruning with pruning percentile = 0.2 on MNIST dataset using Lenet architecture
Laarbes) Bhwilgrenod
Tect
Network Banuity
Metwork Doscity
Meleers Beadly
(b)
Figure 8: The eigen factors for layer-wise pruning with pruning percentile p 0.2 MNIST dataset using Lenet architecture
12

---

Under review as a conference paper at ICLR 2022
4858
Medwvok Denetty
206
Networt Dundity
28 12.8 Miceor Density
Kede Deaaty 1904
(h)
(d)
(c)
(h)
Figure 9: The eigen- fageorfactor results for the proposed pruning algorithm on MNIST dataset using Lenet architecture and different types of bound criteria, mentioned in Table [ (a-b) for UE, (c-d) for UD, (e-f) for WE, (g-h) for WD (with average degree 1)
140m NOSTINC
Methetek Seaiit
(a)
(b)
(c)
(d)
Figure 10: The test accuracy results of the proposed pruning algorithm on MNIST dataset using Lenet architecture with different noise levels in the input image using and bound criteria, mentioned in Table I. (a) for UE, (b) for UD (c) for WE, (d) for WD (with average degree 1)
13

---

Under review as a conference paper at ICLR 2022
A.2 MORE RESULTS FOR CONV2 ARCHITECTURE ON CIFARIO DATASET
4011
Deadyy
Beland Deauty
Belwork Deasiyy
23
XL4 133
Figure 11: The results for Conv2 architecture using CIFARIO dataset with pruning percentile Prone = 0.1, Pfe = 0.2, and Pout = 0.1 Soayer-wise-aa wise-pruningg;; (a-c) eigen factors for the unweighted graph, (d-e) eigen factors for the weighted graph, (f) test accuracy
Eigan Factors (onweighted)
Conv13
Eigen Factors (Unweigghe toh
POAR- FCLL--01)
Elgan Factore (Ulveen (itweighted))
PCAR6
ColvLi-bl)
120
FCLL-5X)
(b1))-bbl)
100
FCAS-
12-
105
41
164
0.6
28
1.5
0.5
0.2
100
16.8
69
0.2
160
16.8
6.6
2.8
0.6
43
Density
Density
Density
Eigon Factors (Wogghod)
Comvilii conviss m-t))
(Weighttdd)
12-
FCLLS
1CSA-01)
Conv- dae)
1C48-6011
Com-
100
2/8
Network Density
Matwork (e)
(d)
(f)
Figure 12: The eigen factors for the IMP pruning algorithm on CIFAR10 dataset using Conv2 archi-
tecture; (a-e) Global Pruning with p 0.2
14

---

Under review as a conference paper at ICLR 2022
A.3 MORE RESULTS FOR CONV4 ARCHITECTURE ON 10 DATASET
Fauture
Figure 13: The results for Conv4 architecture using CIFARIO dataset with pruning percentile Peone = 0.1, Pyc = 0.2, and Pout = 0.1 (layer-wise-puuning): (a-c) eigen factors for the unweighted graph, (d-e) eigen factors for the weighted graph, (I) test accuracy
Pactors (Unwelghtted
Canv [ar)
Conet116
ComvL3-4b))
Factors (Unweighted)
PCAS-1
FCLL-4BC)
Elgen Factorn Unwwelghtdd
20
PCLB
FC186
PCAP6 #CA7
24
Commi2 ear)
24
Conmi12 abr)
ConvLA-bb
68-
68-
20-
26.2
167 26a
Network Density
Metwork Density
Network Density
(a)
(c)
Ergan Pactors (Weighted)
Consitl-n -001
Commet3-4
401113-4b1)
(Weighted)
FCAS-4011
FCLS-
rcas-b11
TC474,
Canvill da(-)
Conei3-b//
1C47-60)
Conn-12 dbco
Conwi22 wbd)
Con-16-00) ab!1
ComeL4-bb))
12-
Tocr Rccurrry
Network Denaity
Natwork Denaity
XEX (f)
XET EXT
(d)
(c)
Figure 14: The cigen factors for the IMP pruning algorithm on CIFARIO dataset using Conv4 archi- tecture; (a-e) Layer-wise Pruning with Pcone 0.1, Pfc 0.2, and Pout 0.2
15

---

Under review as a conference paper at ICLR 2022
Eigen Factors (Unveighted))
Coneti-d
Conetivabi)
Conetad,
Elgen Factors (Unweighted
RC45-1
FC45-40()
Elgen (Unweighted)
FC4G6
FC46-00)
RCA26
FCAT-a0l
Convi3-mi1
PCALB-WN13
PCLD
FCLT
Conei2 abco
Conet4 4b71
Network Denuty
Network Demity
Netwark Donnity
(a)
(b)
(c)
Eigen Pactorrs (Weighted)
20-
Conwil1 ebr1
Connitbe
Convl34,
(Waighted)
FC45-4011
1c474
Comv abi1
FC43-0h1)
TC47-001
Canei2-6
Con-lety
dbc)
ConvLe-bh:
Word Accuursrryy
100 ww0. c1..77.. 4.8
3:2 23 3.5
159.834400
1--437-333 33.2
3.3
Density
(d)
Figure 15: The eigen factors for the IMP pruning algorithm on CIFARIO dataset using Conv4 archi- tecture; (a-e) Laser-wise Pruning with Peone 0.1, Pfc 0.2, and Pout 0.1
16

---

Under review as a conference paper at ICLR 2022
A.4
MORE RESULTS FOR CONV6 ARCHITECTURE ON CIFARIO DATASET
Elgen Pactors (Umweigitted
GERALL SH0g
Erpen Facturs (Unwelghted)
Eigen Eigen Pactors (Unweiighed)
FC
PCAB PCAB--0C)
20-
12
16.0
22.0 Network Density (c)
Network Density
Density
(a)
(b)
Eigan Pactors (Weighted)
Elpan Pactoors (Weigited)
Ture
Network Density
Network Density
(d)
(c)
(I)
Figure 16: The cigen factors for the IMP pruning algorithm on CIFARIO dataset using Conv6 archi-
tecture; (a-e) Layer-wise Pruning with Pconr 0.1, Pfc 0.2, and Pout 0.2
Eigun Pactors (Inweightedd)
-0-
Eggnn pacters Unweiiited
Uignn Factore (Unwwaighted
FC4D-6011
30
100.09..330 os60 Network Density
Network Denstty
Network Density
Eigen Pactors (itd)
Etgon Factors (ood))
12
Tue Acturey
ww..9..3..222..0. o Metwork Density
Network Denuity
(d)
Figure 17: The eigen factors for the IMP pruning algorithm on CIFARIO dataset using Conv6 archi-
tecture; (a-e) Layer-wise Pruning with Poons = 0.1, Pfc 0.2, and Pout = 0.1
17

---

Under review as a conference paper at ICLR 2022
A.5
RESULTS FOR VGG19
Metwort Den0
Desiit
Retwerk Denaly (h)
Figure 18: The eigen factors for the IMP pruning algorithm CIFARIO dataset using VGG19 architecture and Global Pruning with = 0.2 and 0.01
100
Natwork Density
Figure 19: Results for the test accuracy VGG19 on different noise level
A.6 PYPER-PARAMETERS DESCRIPTION
Table 3: Hyper-paramen settings for experimenting LTH using iterative magnitude based pruning
Lenet (on MNIST)
Conv4 (on CIFARIO)
Optimizer
Adam
Adam
Training Iterations
20000
25000
Batch size
60
60
Learning Rate
0.0012 50
0.0003
Pruning epochs
50 Kaiming Normal
Model initialization
Kaiming Normal
64,64, pool
Conv Layers
128, 128, pool
FC layers
300, 100, 10
256, 256. 10
pruning epochs(in comparison)
60
60
18

---

Under review as a conference paper at ICLR 2022
A.7 DIFFERENT PARAMETERS VALUES WITH RESPECT TO THE RAMANUJAN GRAPH BASED PRUNING ALGORITHM
Table 4: Representative result of the parameters found in the last pruning epoch of SynFlow-Boud Bound Algorithm on Lenet/MNIST
(29.83, 0.00, 89.00, 10.00. 10:74, 12.38. 10356908.99 93, 1190044..77)
(31.84. 14.32, 235.20, 235.20, 3,07. 11.11, 16.74, -0.22, 0.17)
(12.41, 5.75, 5,75, 3,37. 30.00, 6.76, 6.92, 0.17, 0.20)
(43.27. 21.31, 11.23 99.93, 13.00. 13.14, -0.9
(14.07, 6.96. 99.4, 1.30, 7.23, 10.47, 0.04)
(19.59, 1.37, 31.63, 12.10. 8.62, 8.87, 5.29)
(11.40. 1.34, 19.66, 6.55, 6.45, 6.68. 3.82)
(3.54, 1.01. 10.90, 1.09. 3.19, 3.1.. 3.45, 3,45,..,..16 2.16)
12.74. 7.83, 9,72, 7.29. 6.85, 6.8665.46. 5.46, -0.12
(0.01, 2352 0 235200)
(0.01, 300.0/ 30000)
(0. (0.89, 890 1000)
(layer wise densily, remaining/ total parameters)
(layer-wise densily, remaining/ total parameters)
wiie density, remaining/tora parameters)
(f1. t2, davp davgR, eb, db, As. Ag)
(1,, 11, dang. daugRt eb, db, As, AR)
(f1, 12, davg dangR, eb. db. As. Ax)
(11 12, daugL, davgit. eb, db. As)
(f1, f2, davgL, davglt eb, db, As)
(f1, f2, davgl, davgit, cb, db, As)
(f1. t2. davgL. dargR. eb, db, Ag)
(f1. f2. davgL. davglt: eb, db, As)
(11. 82. daveL, davgR. eb, db, Ag)
unweighted
unweighted
unweighted
weighted
weighted
weighted
weighted
Score
Score
L1
Li
L2
L2
L2
L2
L3
L3
L3
L.3
19


Reviews:
[{"review_id": "tMR1E9h-UQB", "reviewer": "Reviewer_GGCK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Strengths:\n- as far as I know, the connection from the LTH to expander graphs is both novel and very interesting\n- the exposition and algorithm definition are clear and easy to read\n- judging from the provided experiments, the analysis seems to be well-supported by data\n\nWeaknesses:\nThe main weakness is in the experiments section, which is very hard to parse. Problems include:\n- very small graphs requiring constant zooming in and out, especially since some curves are only distinguished by line and marker style\n- too many curves per graph, some being borderline unreadable (e.g. Figure 5.d)\n- the color schemes are confusing: the same colors are used for distinguishing Lenet layers (Figure 3.a, b) and noise levels (Figure 3.c)\n- the loss of the ramanujan property should be present on the testing accuracy graphs\n- the legend scheme for the curves should be explained more clearly: as of now, they are quite hermetic and require good knowledge of the studied networks' architecture.\n\nRemarks:\n- in some cases (e.g. below Figure 1), $p$ switches between the proportion of edges pruned and the proportion of edges kept\n- I understand why you wouldn't want a rigorous definition of a universal cover, but you should add a reference\n- the theory of Ramanujan graphs is only stated for positive weights, yet this is not the case for neural networks: how is the ramanujan bound defined?\n- typo below def. 3: it is the Alon-Boppana theorem", "summary_of_the_paper": "This paper revisits the Lottery Ticket Hypotheis (LTH), where aggressively pruning a neural network in a smart way allows it to retain its convergence properties, at a lesser computational cost.\n\nThe authors advance an explanation relating this LTH to expanders, graphs that have the property that information circulates really well between the vertices, and then to Ramanujan graphs. They then propose an algorithm built on this premise, that prunes the graph as long as the ramanujan property is still satisfied.\n\nFinally, a wealth of experiments is shown, showing the relation between the Ramanujan property and the performance of the pruned network. The authors also test the performance of their Ramanujan pruning algorithm against the same datasets.", "summary_of_the_review": "The idea of the paper is novel, interesting, and clearly exposed. However, a wealth of clarity issues in the experiments section hinder the clarity of the paper overall.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "b6hhuD1pmz", "reviewer": "Reviewer_u9fu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "While the connection of Ramanujan expander graphs to lottery tickets is interesting, the experiments are not convincing and leave doubt that this is even a relevant property for network pruning. The practical relevance of the stopping criterion is doubtfull. Detailed points of critique follow below.\n\nStrengths:\n+ The idea to measure the potential of a pruned network to serve as lottery ticket based on the eigenspectrum is novel and interesting.\n+ The idea that the Ramanujan graph property could be beneficial for sparse network structures could be also useful (but this remains open to show). \n\nWeaknesses:\n- The introduction into Ramanujan graphs is lengthy and only motivational, as the results on maximality hold only for regular graphs and not for the lottery tickets (which are usually irregular).\n- The authors claim that they introduce a new pruning algorithm, while in fact they only propose a stopping criterion for iterative magnitude pruning (IMP), which requires the repeated computation of the two largest eigenvalues of potentially large weight matrices. The original IMP is computationally expensive already, which leaves the question what the added value of the eigen-bound based stopping criterion should be?\n- As a stopping criterion for pruning, it is not relevant, as the validation set performance (or even training set performance) is in fact more indicative.\n- Is the contribution should be the insight that graphs with the Ramanujan property are better suitable as lottery tickets than other structures, I would expect different experiments that test this hypothesis. \nFor instance, I would expect that random graphs are sampled or otherwise constructed that have comparable properties (like density, degree distribution, flow preserving, etc.)\nwhich either have the Ramanujan graph property or not (but are otherwise comparable). Or through rewiring of edges the Ramanujan graph property can be gained or lost...\nFor both these sets (Ramanujan or not) one could then test whether they are suitable lottery tickets (or at least preserve information flow).\n- For real practical impact, I would then expect an algorithm that repairs a pruned network to gain back the Ramanujan graph property (by edge rewiring that preserved the overall network density) and then would want to see experiments that suggest a superior performance of this pruning algorithm with repair.\n- Different from the made claims, the Figures 3, 4, 5 do not even seem to indicate a strong link between the loss of the Ramanujan graph property and a loss of accuracy.\nI would expect to see a sharp phase transition and complete loss of network accuracy at the point where the Ramanujan graph property is lost if the made claims were true.\n- Or is simply the connectivity of the graph the relevant property?\nI would expect at least a comparison with methods like Synflow or layerwise pruning approaches that try to prevent layer collapse and preserve information flow through the network or orthogonal repair as in \"A Signal Propagation Perspective for Pruning Neural Networks at Initialization\", ICLR 2020.\n\nPoints of minor critique and open questions:\n- Definition 3 for irregular graphs: Two replacements of the same quantity (the regularity r) are proposed, which is contradictory in this form. This could be explained more precisely.\n- Multiple symbols, abbreviations, figure legends, etc. are nowhere defined. For instance, \\sigma shall probably refer to the standard deviation of the applied Gaussian noise?\n- Figure 7: It is impossible to compare which pruning algorithms perform best. They all look very similar.\n- No error bars are reported anywhere.\n", "summary_of_the_paper": "The authors state the hypothesis that the Ramanujan graph property is necessary or at least beneficial for pruned networks to serve as lottery tickets. Motivated by this claim, they propose a stopping criterion for iterative magnitude pruning, which is based on the two largest eigenvalues of the weight (or adjacency) matrices of neural networks and should (approximately) preserve the Ramanujan graph property. \n", "summary_of_the_review": "As the merit of the proposed eigen-bound based pruning is unclear, I believe the work is not suitable for publication at ICLR in this form.\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "T9vXae7fze", "reviewer": "Reviewer_M3ko", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "**Pros**: The proposed pruning method is based on the spectral graph theory, which is novel and interesting.\n\n**Cons**:\n1. **Significance of the method**.\n    - What is the practical significance of the proposed pruning method in this work? \n    - Whether the proposed method can effectively improve the pruning performance, such as alleviating the performance degradation? \n    - Whether the winning lottery ticket can be found more effectively?\n    -  For pruning the neural network, what is the significance of robustness against the noise in the dataset? Maybe we should focus on pruning instead of robustness.\n\n2. **More comparisons are needed**.\n    -  This paper does not show the performance of other state-of-the-art pruning methods, such as IMP or gradient-based pruning.\n    -  How robust are other pruning methods to noise?\n    -  Authors should also make more ablation studies to demonstrate the roles or impact of different components of the proposed method.\n\n3. **Other issues**.\n    -  The experiment section in this paper is too single. The results shown in Figures 3, 4, and 5 are all similar, except that different datasets and models are changed.  This section should include more important results to demonstrate the proposed arguments. Please put the insignificant results or curves to the appendix.\n    -  The experiment section frequently shows the curves of eigen factors. What does this indicate? What kind of enlightenment does this changing trend provide us?\n    -  Why does the proposed method establish robustness against the noise?", "summary_of_the_paper": "In this paper, the authors study the properties of the subnetworks in lottery ticket hypothesis (LTH) from the perspective of the spectral graph theory.\nThey argue that the pruned network in LTH remains a Ramanujan graph.\nThe performance of the subnetworks begins to degrade with the loss of Ramanujan graph property.\nTo this end, they propose an eigen-bound based network pruning algorithm to preserve the graph property.\nExtensive experiments are conducted to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "In general, the paper is well written. I hope the authors should first answer the aforementioned questions cautiously and carefully.\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DDSR2f_ioHr", "reviewer": "Reviewer_rGMS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "\nStrengths:\n- The paper builds upon a nice premise by introducing expander graphs to describe connectivity between neural network layers.\n- Choosing the pruning termination criterium based on on the extended spectral gap (Algorithm 1) is a good idea and novel to my knowledge.\n\nWeaknesses:\n- The experiments are not able to convince me that the chosen bound leads to good pruning results. In some experiments they seem to fit, in others they do not.\n- There is also no solid theoretical justification, why the termination criterium should fit (except for the already known correlation between the spectral gap and density).\n- The work is lacking comparisons to previous pruning methods, showcasing the usefulness and significance of the proposed algorithm.\n- The experiment section is confusing (see below)\n\nIssues in Experiments section:\n- I have trouble following the figures. The labels in the figures are not consistent with the names in the text (lambda vs t, L1-L3 not defined). Minor: the figure labels are way too small.\n- UE, UD, WE, WD only defined in a Table and the text is lacking clear discussions and conclusions for the results in the different scenarios.\n- It would help alot if the test accuracy figures would show the point in which Algorithm 1 would stop the pruning.\n- If I understood correctly, it should be easy to apply Algorithm 1 to the networks and present the resulting test accuracy in comparison to previous pruning techniques. However, that is not done.\n", "summary_of_the_paper": "The work proposes to utilize the spectral gap of the bipartite network connectivity graphs between neural network layers to terminate an iterative weight pruning algorithm.", "summary_of_the_review": "All in all, while I like the general idea of utilizing spectral graph information of bipartite network connectivity graphs for pruning decisions, I find the paper is lacking a clear message and the required experimental evidence to back it up. There are no comparisons to previous pruning techniques, which would allow to showcase significance. Therefore, I tend to vote for rejection.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. However, the current consensus suggests the paper requires another round of revisions before it gets accepted.

In particular:

- There were still some gray areas regarding comparison to simple techniques. E.g., one reviewer raised the question how it compares to simply stopping based on validation accuracy for example. The reviewer was missing the justification why stopping at the loss of Ramanujan graph property is preferable in comparison to other criteria. 
- Several reviewers found the general idea interesting, but all felt that more reasonings about the impact/insights/relationship of Ramanujan graph property with pruning need to be found to get accepted.
- Reviewers appreciate that the authors corrected many parts of the submission (see increased scores). However, reviewers felt that the paper requires more data/evidence to get accepted at this level, based on the discussions made during the rebuttal period. 

Best AC
Decision: Reject