Year: 2021

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 existing 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 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, 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 modified iterative pruning algorithm which removes edges in only the layers that are Ramanujan graphs thus preserving global connectivity even for heavily pruned networks. We perform experiments on MNIST and CIFAR10 datasets using different established feed-forward architectures to support the criteria for obtaining the winning ticket using the proposed algorithm.

heading: 1 INTRODUCTION AND RELATED WORK
text: Neural Network (NN) and its recent advancements have made a significant contribution to solve various machine learning applications. The power of an over-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 pretraining following the introduction of a remarkable contribution, named the Lottery Ticket Hypothesis (LTH), which hypothesize the existence of a highly sparse subnetwork and weight initialization to reduce the training resources as well (Frankle & Carbin, 2019). It uses a simple iterative, magnitudebased 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 on finding this lottery ticket for more competitive tasks by pruning with weight rewinding(Frankle et al., 2019a), fine tuning the learning rates (Renda et al., 2020), more efficient training (You et al., 2019; Brix et al., 2020; Girish et al., 2021).
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 generalization 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 et al., 1993; Dong et al., 2017; Lee et al., 2018), etc; (ii) whether the pruning is global or local; (iii) how often pruning should be applied like one-shot Lee et al. (2018); Wang et al. (2020), iterative Tanaka et al. (2020). One of the primary goals in the literature has been to reduce the computational footprint at the time of prediction, i.e., during post-training. In recent LTH studies, the victim weights are determined by their value at the ini-
tialization, gradient of the error, and network topology Lee et al. (2019); Tanaka et al. (2020). To understand weight initialization, Malach et al. (2020) show that pruning makes a stronger hypothesis with bounded weight distribution. The sparsity of the network is reduced from polynomial to a logarithmic factor of the number of training variables (Orseau et al., 2020). Mocanu et al. (2018) suggest to consider the topology of the network from a network science point of view. The pruning algorithm starts from a random Erdős Rényi graph and returns a scale-free network of a 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(Evci et al., 2020a).
Various analysis for explaining the LTH have been attempted in the past. Researchers Evci 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 underlying phenomenon associated with the hypothesis still remains ill-understood. All of these studies related to LTH identify that a 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 a 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 a 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 a study to observe the characteristics 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 unweighted 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 a pruned network. It is empirically observed that existence of winning tickets in a 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 CIFAR10 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 a 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 Ramanujan 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 robustness 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. It 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.

heading: 2 THE LOTTERY TICKET HYPOTHESIS AND NETWORK PRUNING
text: The lottery ticket hypothesis states that a randomly initialized, dense neural network contains a subnetwork which when trained independently using the same initialization achieves a test accuracy close to the original network after training for less or at most the same number of iterations Frankle & Carbin (2019). These subnetworks, denoted as ‘winning tickets’, can be uncovered by network pruning algorithms. Weight pruning is one such simple strategy. Let the original dense network be represented as the function N (x; θ), where x is the input and θ are the weights. The weights have an initialization of θ0. Weight pruning generates a mask m ∈ {0, 1}|θ| such that the pruned network can be represented by N (x;m⊙ θ) with initialization m⊙ θ0. 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 to their values in θ0 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 pruning 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 θi, i denoting a small iteration number, rather than their initial values in θ0. This process, as illustrated in Figure 1 (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., 2021) or saliency Tanaka et al. (2020). Magnitude pruning provides a simple method for obtaining the pruning mask by retaining the top p% weights wi ∈ θ that have the highest values of |wi|. The role of the weights in local computation in the network layers is not considered. A higher pruning efficiency may be achieved by algorithms that account for connectivity structures in the individual layers. In the next section we describe graph parameters of the network that determine such connectivity.

heading: 3 EXPANDERS AND RAMANUJAN GRAPHS
text: 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 is the number of half edges emanating from v.
Definition 1 ((n, d, ε)-expander) Let ε > 0. An (n, d, ε)-expander is a graph G = (V,E) on |V | = n vertices, having maximal degree d, such that for every set ∅ ≠ U ⊆ V satisfying |U | ≤ n2 , |δ(U)| ≥ ε|U | holds.
Here, δ(U) denotes the vertex boundary of U . The quantity |δ(U)||U | measures the rate of expansion and the infimum |δ(U)||U | as U varies among the non-empty subsets of V with |U | ≤ |V | 2 is called the (vertex) Cheeger constant h(G) 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 a high value of h(G) signifies that the graph is strongly connected. This ensures that information can flow freely without much bottlenecks.
Definition 2 (Expander family) A sequence of finite, connected graphs {Gi = (Vi, Ei)}i=1,2,··· on Vi vertices and Ei edges is called an expander family if there exists an uniform ϵ > 0 such that each graph in the sequence is an (|Vi|, di, ϵ) expander for some di’s.
The study of expansion properties of graphs is closely related to the study of the spectrum (distribution of eigenvalues) of the adjacency operator defined on them. Given a finite r-regular
graph of size |V | = n, the eigenvalues ti of the adjacency matrix are all real and they satisfy, −r ≤ tn ≤ . . . ≤ t2 ≤ t1 = r. The graph is connected iff t2 < t1 and is bipartite iff ti’s are symmetric about 0 (in particular tn = −r). The quantity t1 − t2 is known as the spectral gap and it is related to the Cheeger constant via the discrete Cheeger-Buser inequality, discovered independently by Dodziuk (1984) and by Alon & Milman (1985). In our context, we consider a stronger notion of the spectral gap (but it is equivalent for bipartite graphs). Let t := max{|ti| : 1 < i ≤ n, |ti| < t1}. In here, the quantity t1 − t will denote the spectral gap. The more connected a graph is, the larger is the spectral gap and ideally, a graph with strong expansion properties has a 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 G be a r-regular graph on n vertices, with adjacency eigenvalues {ti}i=1,2,...n, satisfying −r ≤ tn ≤ . . . ≤ t2 ≤ t1 = r. Let t(G) := max{|ti| : 1 < i ≤ n, |ti| < t1}. Then G is a Ramanujan graph if t(G) ≤ 2 √ r − 1 = 2 √ t1 − 1.
The fact that in a 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), t(G) ≥ 2 √ r − 1− 2 √ r−1−1
⌊m/2⌋ where m denotes the diameter of the graph. As m → +∞ and r is bounded, we obtain the result (this also follows from the Alon-Boppana theorem).
For our applications, we shall encounter not necessarily regular graphs, thus we need a notion of irregular version of Ramanujan graphs. The two ways we shall exploit Definition 3 for irregular graphs will be to:
1. Use the average degree davg in place of the regularity.
2. For weighted graphs, use t1, 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 a 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 a graph satisfying t(G) ≤ ρ(G̃) where ρ(G̃) denotes the spectral radius of G̃. See also Marcus–Spielman–Srivastava (Marcus et al., 2015, sec. 2.3). A result of Hoory, see Hoory (2005) implies that 2 √ davg − 1 ≤ ρ(G̃). Thus, it makes sense to consider t(G) ≤ 2 √ davg − 1 ≤ ρ(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 davgL on the left and davgR on the right, we can further consider the sharper estimate t(G) ≤ √ davgL − 1 + √ davgR − 1 ≤ ρ(G̃) see Hoory (2005). Upto now, we had only discussed about unweighted graphs. A weighted graph is a graph with a weight function w : E → R≥0 attached on the edges. It can be looked upon as a 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 to 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 is no bottleneck to the free flow of information. This forms the theoretical basis of our work.

heading: 4 RAMANUJAN GRAPH CHARACTERIZATION OF NEURAL NETWORKS
text: We can represent any neural network using graphs (possibly weighted, depending on the context) and in this article, we will be dealing with a sequence of finite, bipartite graphs. This is because if N denotes a neural network having l layers N1,N2, . . . ,Nl respectively, then each Ni (i = 1, 2, . . . , l)
is a 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 Spielman (2018). The notion of Ramanujan graphs allow us to quantify the pruning limit, and we empirically justify our technique.
In Figure 2, we present examples of three small feed-forward networks with a single hidden layer and four neurons in each layer. The networks consists of two bipartite graphs corresponding to the input-hidden and hidden-output layers. The sparsity of all the three networks, as measured by the number of edges present, are the same. However, in the first network none of the layer-wise bipartite graphs satisfy the expander property and thus information flow from a significant number of input nodes to output nodes are disrupted. For the second network, the input-hidden layer bipartite graph is an expander, while the hidden-output 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 as a disconnected one, the second network as 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).

heading: 4.1 BIPARTITE GRAPH STRUCTURE
text: 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 of 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, we argue that for studying their connectivity properties only the magnitudes need to be considered.
Fully Connected Layers (FC): For a fully connected layer Ni, with ni−1 number of inputs and ni number of outputs the weighted bi-adjacency matrix of the corresponding graph is Wi ∈ R[ni−1×ni], and the corresponding pruning mask is Mi ∈ {0, 1}[n i−1×ni].
Convolution Layers (Conv): Here, we consider the kernel size, the number of input and output channels to unfold the layer into a complete bipartite graph. For a convolution layer Ni with the kernel of size k, ni−1 input, and ni output channels, the weighted bi-adjacency matrix of the corresponding graph will be Wi ∈ R[(n
i−1.k.k)×ni], and the corresponding pruning mask is Mi ∈ {0, 1}[(n i−1.k.k)×ni]. An example is shown in Figure 3.
Now, the bounds are analyzed for both unweighted (Mi) and weighted (Wi) bipartite graphs at each layer Ni. Table 1 describes different bounding constraint depending on the type of the considered graph and bound type. We consider the bound differences (∆S and ∆R) for the eigenvalue and average degree respectively. A transition of the ∆ 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.

heading: 4.2 RAMANUJAN GRAPH PROPERTY PRESERVING PRUNING ALGORITHM
text: In this section, we describe a modification of the iterative pruning algorithm that preserves the Ramanujan graph property of a 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 is trained again with its initial weight values to perform the next pruning iteration. The magnitude of a score function θ 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 et al., 2020), SNIP (Lee et al., 2018).
Algorithm 1: LAYER-WISE CONNECTIVITY BASED PRUNING Input: Trained Network N, Score function θ, Pruning percentile p, pruning level K Output: Pruned Network N⋆
1 N⋆ ← N 2 for i← 1 to l do 3 k ← 1 4 while k ≤ K do 5 Ntempi ← PRUNEBYPERCENTILE(p/2k,Ni, θi) // Prune
using the score function
6 CALCULATE davgL AND davgR OF N temp i 7 if min(davgL, davgR) < 2) then 8 N⋆i ← Ni // To avoid layer collapse 9 BREAK
10 end 11 CALCULATE ∆S ,∆R FOR N temp i 12 if max(∆S ,∆R) > 0 then 13 N⋆i ← N temp i // Satisfy Ramanujan Property on the unweighted graph 14 BREAK 15 else 16 CALCULATE ∆θS FOR N temp i USING θi 17 if ∆θS ≥ 0 and tθ1 ≥ 1 then 18 N⋆i ← N temp i // Satisfy Expansion Property Ni using θi as weights 19 BREAK 20 end 21 end 22 k ← k + 1 23 end 24 end 25 nure return N⋆
We propose a modification to the above method. If a weight is identified as a victim based on the above score function based scheme; we check the Ramanujan property of the layer Ni to which this weight belongs. First, we verify the connectivity property of the layer using the bounds on the unweighted graph as defined in Table 1(∆S ,∆R > 0). If the unweighted graph bounds are not satisfied, we consider a weighted graph with score function values as the edge weights. The bounds using the eigenvalues of this weighted graph is used to verify the spectral expansion property (∆S > 0) for a particular layer. If the pruned network Ntempi follows the Ramanujan graph property given by the bounds, then the algorithm simply proceeds to the next level of pruning operation.
If the bound is not satisfied for a particular layer i, the weights are simply reset to the values before pruning and the pruning percentile p is halved and search for a better approximation of Ni is resumed. The target pruning level k ∈ [K] is a controlling parameter to limit the search iteration.
The proposed algorithm attempts to preserve Ramanujan property for as many layers as 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 1. It takes the trained network N, score function θ, pruning percentile p, pruning level K as 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⋆i = Ni,∀i. 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.e., (i) eb- based on the largest eigenvalue(t1) and (ii) db- based on the average degree (davgL and davgR). Here, G for a bipartite neural network layer Ni is either the unweighted graph or a weighted graph with score functions as the weights. In order to avoid ‘layer collapse’ we stop pruning for a layer if the bipartite graph has a node with degree less than two in either of the parts.
The top-2 largest magnitude eigenvalues at layer i are computed from the symmetric matrix NTi Ni with implicitly restarted Arnoldi methods (Lehoucq et al., 1998) and, the average degree is computed from the connected component of the bipartite-graph. Hence, the computational complexity is 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 as the size of the convolution kernel which is usually small. Also, the usually the number of fully connected layers are not very high.

heading: 5 EXPERIMENTAL RESULTS
text: We have used the MNIST and CIFAR10 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 σ 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 3 in the Appendix.

heading: 5.1 EXPERIMENTAL SETUP
text: We study the variation of classification accuracy with the network density as measured by the remaining weights percentile 100 − p, where p is the pruning percentile. For different layers the percentile can be different, as denoted by pfc for fully connected (FC) layers, pconv for convolution layers, and pout for the output layers. We study the two cases for the bound specific to unweighted (Mi) and weighted graph (Wi). For each of the studies, we plot four parameters; (i) eigenbound bound difference (∆S), (ii) average degree bound difference (∆R),(iii) network density for each layer, and (iv) test accuracy on both clean and noisy data. The degree and eigenbound differences are defined in Table 1.
Relationship between Ramanujan graph properties and LTH The primary goal of our study is to identify the LTH regimes, determined by the spectral properties of the bipartite-network layers. The existence of LTH regime is illustrated for two representative established networks. The results for Lenet on MNIST dataset is shown in Figure 4; and for Conv4 on CIFAR10 is shown in Figure 5. In each of the plots, we show the variation of classification accuracy on clean and noisy test sets (having various noise levels (σ)), with the remaining weights percentile. The spectral properties are characterized by eigenbound difference ∆S for both the weighted and unweighted graph representations, and the degree bound difference ∆R for only the unweighted graph representation. A transition of ∆S and ∆R from positive to negative values denotes the loss of Ramanujan graph property 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.e., ∆ > 0,∀Ni, (ii) partially Ramanujan, where some of the layers maintain the property, and (iii) non-Ramanujan, where none of the layers retain the property. For the Conv4 network which has more number of layers we
show results for the unweighted graph representation only. Similar results for other networks and different pruning settings are discussed in the Appendix.
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 even on noisy data. For very low network densities it is seen that the ∆ values become positive again. This is a boundary effect owing to the in-applicability of Ramanujan graph bounds for disconnected graphs.
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 (2019), (ii) the iterative verion of Singleshot Network Pruning based on Connection Sensitivity (SNIP) Lee et al. (2018), (iii) Synaptic flow based pruning SynFlow Tanaka et al. (2020) and show the results of test accuracy achieved with similar densities with and without the bound condition. To do this experimentation, we choose the a fix compression ratio α to achieve the desired density of the pruned network as 10−α × 100, and observe the difference in accuracy due to the network connectivity. The results are presented in Table 2 for Lenet/MNIST and Conv4/CIFAR10. 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-Bound). The bounds are considered as two types of bounds - first it tries to maintain the bounds on 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 to stop at a density where the accuracy is comparable with its original network. These values are marked in bold in Table 2. The highest improvement is achieved by SynFlow algorithm for the Lenet architecture on MNIST dataset. While the usual SynFlow algorithm results in an accuracy of 49.11% at the density of 1.0, the SynFlow-Bound algorithm has an accuracy of 93.82% for a 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 it 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 as a whole in the entire network.

heading: 6 CONCLUSION
text: In this work, we study the validity of the lottery ticket hypothesis (LTH) based on structural connectivity 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 a 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 region. 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.

heading: A APPENDIX
text: 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.

heading: A.1 MORE RESULTS FOR LENET ARCHITECTURE ON MNIST DATASET

heading: A.2 MORE RESULTS FOR CONV2 ARCHITECTURE ON CIFAR10 DATASET

heading: A.3 MORE RESULTS FOR CONV4 ARCHITECTURE ON CIFAR10 DATASET

heading: A.4 MORE RESULTS FOR CONV6 ARCHITECTURE ON CIFAR10 DATASET

heading: A.6 HYPER-PARAMETERS DESCRIPTION

heading: A.5 RESULTS FOR VGG19

heading: A.7 DIFFERENT PARAMETERS VALUES WITH RESPECT TO THE RAMANUJAN GRAPH BASED PRUNING ALGORITHM

Review summaries:
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.  The 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.  Finally, 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.

In this paper, the authors study the properties of the subnetworks in lottery ticket hypothesis (LTH) from the perspective of the spectral graph theory. They argue that the pruned network in LTH remains a Ramanujan graph. The performance of the subnetworks begins to degrade with the loss of Ramanujan graph property. To this end, they propose an eigen-bound based network pruning algorithm to preserve the graph property. Extensive experiments are conducted to demonstrate the effectiveness of the proposed method.