Sparse Neural Architectures via Deterministic Ramanujan Graphs
Authors: Suryam Arnav Kalra
Arindam Biswas
Pabitra Mitra
BISWAJIT BASU
Venue: Accepted by TMLR ()

Abstract: We present a method to construct sparse neural networks using the theory of expander graphs. Expanders are sparse but well connected graph structures that are used for designing resilient networks. A Ramanujan graph is an extremal expander in terms of the spectral gap of its eigenvalues. In this work, bipartite Ramanujan expanders are deterministically constructed and used as connection structures of the convolutional and fully connected layers of a neural network. The Ramanujan graphs occur either as Cayley graphs of certain algebraic groups or as Ramanujan $r$-coverings of the full $(k,l)$ bi-regular bipartite graph on $k + l$ vertices. The proposed sparse networks are found to provide comparable performance to a fully dense network on benchmark datasets achieving an extremely low network density.

Published in Transactions on Machine Learning Research (12/2024)
Sparse Neural Architectures via Deterministic Ramanujan Graphs
Suryam Arnav Kalra
suryomkkamm35@@maal.l
Deportment of Computer Science and Engineering Indian Institute of Technology, Kharagpur
Arindam Biswas
Frin.math@@mmatee com
Polyuom, Pairs, France
Pabitra Mitra
pabitro&ggmadt com
Department of Computer Science and Engineering Indian Institute of Technology, Kharogpur
Biswajit Basu
BASUB @tod.
School of Engineering
Trinity College Dublin, Dublin 2, Ireland
Reviewed OpenReview: https: oppnnevveee. net/ formfo id= asws CCA
Abstract
We present method to construct sparse neural networks using the theory of expander graphs. Expanders are sparse but well connected graph structures that are used for designing resilient networks. Ramanujan graph is an extremal expander in terms of the spectral gap of its eigenvalues. In this work, bipartite Ramanujan expanders are deterministically constructed and used as connection structures of the convolutional and fully connected layers of neural network. The Ramanujan graphs occur either as Cayley graphs of certain algebraic groups or Ramanujan r-coverings of the full (k:, () biregular bipartite graph k + verlices. The proposed sparse nelworks are found to provide comparable performance to a fully dense network on benchmark datasets achieving an extremely low network density.
1 Introduction
Sparse neural networks are structures containing significantly lesser number of connection weights as compared to fully connected network. They have advantages in terms of inference time, memory requirements and generalization capabilities. A sparse neural network should be trainable to achieve high prediction accuracy. Goal of our work is to develop a theoretically justified strategy for constructing sparse neural networks that can be subsequently trained to achieve a good prediction performance.
Expander graphs are networks that are simultaneously sparse and highly connected (Hoory et al. 2006). Expanders are resilient the sense that a large number of their edges noods be delcted to disconnect parts of the graph. A higher spectral gap between the first and the second eigenvalues of graph adjacency matrix points towards a better expansion property. Ramanujan graphs (Lubotzky et al. 1988) expander graphs with maximally high spectral gaps.
class of regular
Path connectedness and regularity are desired characteristics of a neural network both for forward propagation and gradient flow. These properties help even a sparse network to achieve a good prediction performance, It has been empirically shown that the expansion property strongly correlated with the performance of sparse neural networks (Prabhu al., [2018] Pal al. 2022). This motivates the of Ramanujan graph construction algorithms to design sparse neural networks.

---

Published in Transactions on Machine Learning Research (12/2024)
In our approach, bipartite Ramanujan graphs are constructed for each of the convolutional and fully connected layers. These are stacked to form the entire network. The network is then randomly initialized with weight values and trained using backpropagation. Sparsity can be controlled by varying the parameters of the Ramanujan graph. The Ramanujan graphs are constructed either as Cayley graphs of certain algebraic groups or as Ramanujan r-coverings of the full (k; biregular bipartite graph on k ++1 / vertices.
Prior approaches to using Ramanujan expander graphs have relied on iterative weight pruning techniques or random graph generation. This often leads to the formation of random expander graphs. Our approach of constructing deterministic Ramanujan network circumvents this problem. The construction is also data independent and non-iterative. Experimental results on benchmark image classification data sets show that Ramanujan sparse network initialization provides comparable performance with fully dense networks.
The paper is organized as follows. We present a brief literature survey in Section [.1, Contributions of the paper are highlighted Soction A The properties and mathematical formulation of deterministic Ramanujan graphs are then presented in Section 3] The proposed construction techniques of sparse neural network layers is described in Section ! Finally, the experimental results are outlined in Section 5
1.1 Related Work
Sparse neural networks have been previously studied in terms of their graph theoretic properties (Liu et al., 2023). Connectivity properties have been used by several authors to define sparse network topology Vyssogorets & Kempel 2023; You et al. 2020 Chen et al.) 2022 2023a). Tam and Dunson in (Tam & Dunson 2023) gave a technique for regularization of a neural network taking into account the connectivity property of the underlying graph. Lo regularization based training which encourages zero weights has been extensively
studied previously (Louizos el al.] 2018). More sophisticated regularization techniques have also been used (Refael et al. 2024).
Existence of sparse trainable high performing subnetworks of fully connected network is suggested by
the well known lottery ticket hypothesis (Frankle & Carbin 2019 These subnetworks are often identified
using weight pruning techniques (Orseau et al.) 2020). Initial research works in this direction were based on applying established pruming algorithins on a partially trained network (Renda et al.
2020 Fischer &
Burkholz 2022). Recently, a number of approaches has been suggested to obtain a sparse mask for pruming
at initialization (Frankle et al., 2020 Pham et al. 2023 Wang al.] 2021 Sreenivasan et al.!
2022 Cheng
et al. 2023). Robust methods of pruning at initialization have been proposed in (Hayou al. 2021
Expander based sparse network generation has been studied in (Stewart et al. 2023). The methodology is based on generating random d-regular graphs for the bipartite layers and then filtering based on their expansion property. However, it is still a conjecture that random d-regular graphs are Ramanujan. A deep expander sparse network, the X-Nel, is presented in (Prabhu et al. 2018). It is constructed by sampling d-left regular graphs from the space of all bipartite graphs. RadiX-Net (Kepner & Robinett, 2019) is a related deterministic sparse neural architocture defined over diverse layer structures. Ramanujan graph based sparse networks are proposed in (Esguerra et al.] 2023). Spectral sparsification is general method of obtaining expander like neural networks (Laenen 2023). Expander networks used for this purpose are obtained by first generating random bipartite graphs for each layer, and then selecting the ones with a large spectral gap. However, these often favors random networks which are sensitive to reinitializatio (Ma et al.) 2021 Hoang
et al. 2023 Spectral measures have been proposed in (Hoang et al. 2023) to prevent these effects.
2 Research Gap and Contributions
Most of the popular techniques for sparse network construction rely on pruning a partially trained or an untrained network. They usually consider certain heuristic weight importance functions. Expander graph networks are more theoretically justified. Existing expander graph construction methods are based on random graph generation. This does not always guarantce path-connectodness and regularity propertics that are crucial for neural networks. The proposed deterministic Ramamujan graph sparse neural network construction technique circumvents these challenges.
2

---

Published in Transactions on Machine Learning Research (12/2024)
J
K
25
j6
ks
14
8a
K4
1/3
js
K3
1/
j2
122
i1
j1
k1
Figure An example of two consecutive (edge) neural layers where each layer is a bipartite Ramanujan graph. Note that one obtains something stronger than layer-wise path-connectivity. From each vertex of (verlex) layer I one has at least di d2 pathways to reach layer K where d1, d2 denotes the regularities of layers I,J respectively. For instance, to reach layer K from i there are the following 9 pathways: in + ji + k2
i1 + ji + k3, i + j1 + k4, i1 + j2 + k3, i + j2 + Kis is + j2 + ko, it + ja 7 k1, it - ja + k4. i1 + ja + lss
The principal contributions of our paper are:
1. theoretically justified methodology for generating sparse neural networks using Ramanujan graphs.
2. The method is deterministic and is guaranteed to construct well connected and regular expander graphs. It is also non-iterative and data independent.
3. We experimentally show that even extremely sparse networks can be trained to achieve comparable accuracy to a fully dense network.
3 Properties of the Constructed Networks
Path connectedness is a crucial property of neural network graph structures. is necessary both for forward propagation during inference as well for gradient flow during backpropagation (Sporns 2003 Alford et al., 2019). Symmetry and regularity of the layer-wise adjacency matrices is another important property necessary for fast compulation and memory elficiency (Chen et al.] 2023b: Mao el. al. 2017]. We elaborate them in
the context of Ramanujan graphs.
Path-connectedness: The fact that each layer of the bipartite graphs are either regular or biregular with the regularity bigger than ensures that the entire architecture remains path-connected, i.e., starling from any node in the first layer we can reach node in the last layer by a connected path. A proof of this is direct. In Figure 1 suppose there are 3 layers I, K. We wish to reach layer K starting from any point in layer / by connected path. Pick any i,, E 21, 4, 4,5]. Use the fact that there is at least one edge going out from to reach some js and from ja again use the fact of outgoing edges bigger than 1 to reach a point in layer K. The general case follows by induction on the number of layers.
The adjacency matrices of Cayley graphs and of covers Cayley graphs have much more symmetry than those of general regular graphs. For instance they are vertex transitive. Often computations are optimised use such symmetry viz. in the case of the software GAP (Group) 2022) as an example. In the future wish to explore this direction of using the underlying symmetry to obtain fast computations these sparse expander networks. This is also one of the reasons why we prefer deterministic constructions over random ones as the latter loses symmetry. In the graph of Figure [ the adjacency matrix of the first layer (which can be represented as a Cayley graph on the group G Ze x z (( : 0 < x < 1,0 S 4}
High-symmetry:
Zn for denotes the group integers under addition modulo and x the Cartesian product of groups.
3

---

Published in Transactions on Machine Learning Research (12/2024)
with generating set S is
0sx5
Bsx
Adj =
B 5xs
0sxs
where
1
1
0
0
0
1
1
0
B
0
0 0
1
1
0
1 0
0
1
Our goal is to furnish an efficient sparse neural network architecture. If we can describe the architecture for each bipartite layer of neurons then we are done. The adjacency matrix of graph captures the structure of the graph. So we can describe the adjacency matrix or the way vertices of each bipartite layer are connected to other vertices, then it is sufficient to achieve our goal.
Previous approaches based on random network initialization and pruning strategies suffer from the issue of irregularity and not guaranteed to be rigorously Ramanujan. For instance, application of the work of Hoory (Hoory) 2005 mentioned in (Pll et al. 2022 Hoang et al., 2023) etc depends on the important fact that the minimal degrees of the base bipartite graphs need to be 2 2 for the graphs to be Ramamujan Our architecture based on deterministic regular Ramanujan graphs of degree 2 3 ensures that the initialized networks remain Ramanujan, are path-connected and are highly symmetric, being either Cayley graphs of certain algebraic groups to replace the balanced dense bipartite graphs, or the Ramanujan r-covering of full biregular bipartite graphs replace the unbalanced dense bipartite graphs.
4 Formulation of Sparse Neural Ramanujan Graphs
We construct a set of bipartite Ramanujan graphs of specified sparsity and then stack them as convolutional and fully connected layers of the sparse neural network. In this section present the mathematical framework which allows us to construct these bipartite Ramanujan graphs in deterministic manner. This forms the basis of our strategy for sparse network construction. The section proceeds as follows:
1. We shall first present the base graphs on which our sparse neural architectures will be modelled.
These are the bipartite Ramanujan graphs. See Definition 4.1
2. Next we shall give the method of construction of these graphs. These graphs are used to define the neural network layers.
Recall that Ramanujan graph is an extremal expander graph in the sense that its spectral gap is almost as large as possible. Here, we shall be concerned with bipartite Ramanujan graphs. Recall that a bipartite graph is said to be balanced if the number of vertices in each of the partitions are the same and it is said to be unbalanced otherwise.
Definition 4.1 (Bipartite Ramanujan graphs). Let I = (V,E) be a d-regular (d 2 3) balanced bipartite graph. Let the eigenvalues of its adjacency matrix be A, S An-1 S ... I >2 S d1. Then T said to be Ramanujan if |A: < 2/d 1, for i 2....,
For an unbalanced (d, d2) biregular bipartite graph (di, de 2 3), the condition of being Ramanujan changes to |AI < Vdi- II+ vdg- I, for i= 2.... (n (0-1), We see that when d1 d2, it reduces to the usual definition. A representation of an unbalanced biregular bipartite Ramanujan network, see Figure Note that we are considering undirected graphs, so the adjacency matrix is a 0-1 symmetric matrix and the eigenvalues are all real. bipartite graph has adjacency eigenvalues symmetric around 0. detailed description of Ramanujan graphs can be found in (Hoory et al. 2006 sec. 5.3).
Ramanujan graphs are excellent spectral expanders. They are also extremely difficult to construct. In fact, even the question of existence of (infinite families of) Ramanujan graphs non-trivial one and it is not yet.
4

---

Published in Transactions on Machine Learning Research (12/2024)
J
K
26
15
ks
4
fa
K4
1/
ja
k3
1/2
j2
k2
i1
An example of two consecutive neural layers where each layer is a biregular bipartite Ramanujan graph. This can be checked from computing the adjacency eigenvalues of each and comparing with the Ramanujan bound for biregular bipartite graphs. The biregularity of the first layer is (2, and that of the second is (4, Note that if we have an unbalanced biregular, bipartite network with (nI, n2) vertices and biregularity (d,, d2) then they must be related by the following equation: n dj = nzd2.
Figure 2:
fully resolved for the non- min-iiartite case. For the bipartite case it has been resolved by the recent works of Saatuu--Sppiiman-SSiiiiaa
(Marcus et al., 2015 2018) and Gribinski-Markus (Gribinski & Marcus 2021
The first. such construction of graphs are due to Lubolzky Phillips Sarnak (LPS) (Lubolzky al., 1988)
(and independently by Margulis (Margulis) 1988)) We shall define our pruned network according to these constructions.
4.1 Theoretical framework
Let us begin this section by recalling the Cheeger constant and the Cheeger incquality which will help shod light the fact that why good spectral expanding networks elosely related with pruned networks. In the following, graph r = EV is tuple consisting of a vertex set V and edge set E which is subset of V V.
4.1.1 Combinatorial Expansion
Definition 4.2 (Expander and Cheeger constant). graph I' (V, is an e-vertex expander if for every non-emply subset X C V with |X| < [V] 2 we have [6(x)| of X i..., the set of vertices in I which are connected to vertex in X but do not lic in X. As X runs over all subsets of V, the infirmmm of [6(X) satisfying the conditions above is known as the vertex Cheeger constant and is denoted by (T).
TXXT" 2 6, where 5(X) denotes the outer vertex boundary
[X]
Similar to the above, when we consider the edge boundary i.e., the set of edges which have one vertex in X and the other outside of X, we obtain the edge Cheeger constant hg(l') The vertex Cheeger constant hy hy')') and the edge Cheeger constant hg([) related by the following equivalence hy D denotes the maximum degree of the graph. The equivalence allows to speak about vertex expansion and edge expansion interchangeably. In the litcrature, having a high Cheoger constant is also known as having high combinatorial expansion. Intuitively, given a graph with high vertex (or edge) Cheeger constant, it is more difficult to separate any subset of the vertices from the rest of the graph. This allows for free flow of information throughout the network which the graph defines. Idcally, we want our underlying graphs on which the neural layers are based to have high Cheeger constants. In other words, we are targeting for the base graphs of the sparse neural architectures to have layerwise high Cheeger constants. However,
" hT(T) & hy where
5

---

and Published in Transactions on Machine Learning Research (12/2024)
computing the Cheeger constants of graphs is in general an NP-hard problem. To overcome this issue we shall use spectral techniques.
4.1.2 Spectral Expansion
Given finite undirected graph r, the cigenvalues An ... & X1 of its adjacency matrix are all real and À1 < D with equality iff the graph is D-regular. (a graph is said to be d-regular if there are exactly d-edges attached to a vertex.) Thus, d-regular bipartite graph is graph which has the same number of vertices in each partition and every vertex of each partition has exactly d edges attached to it. A graph I' IV, E) is said to be a spectral expander the quantities {[A1] - A2l. Aul k == n the graph is bipartite and k n otherwise.
[ul] are both strictly positive, where
Question 4.3. Why there a need establish strong spectral exponsion?
The answer to this lies in the fact that spectral expansion implies combinatorial expansion via the discrete Cheeger-Buser inequality (see appendix A.2.3) and the bigger the spectral expansion, the more combinatorially expanding the base network graphs are. In general combinatorial expansion (counting the values of the vertex or the edge Cheeger constants) an NP-hard problem. Now the natural question arises that whether there is a limit to the spectral expansion or can it become as large as possible. This leads us to Ramanujan graphs which are the optimal spectral expanders. See appendix for the Alon-Bopanna theorem, Thm A.3
Now, we proceed to the construction of the deterministic Ramanujan networks. We shall need the following notions from arithmetic.
Definition 4.4 (Quadratic residue and Legendre symbol). An integer q is called quadratic residue modulo n if it is congruent to a perfect square modulo n, i.c., if there exists an integer x such that x² = (mod n). Otherwise, is called a quadratic non-residue modulo n. Let p be an odd prime number and a be an integer. The Legendre symbol of a and p is defined as
if is quadratic residue modulo p
and # 0 (mod p),
p
a is a quadratic non-residue modulo p. a = (mod p).
0
Given a prime there are infinitely many primes such that Legendre symbol of a and is -1 (and also there are infinite many primes p such that is +1).
Motivation: The bipartite Ramanujan networks will be constructed as Cayley graphs of certain matrix groups over finite fields. In other words, the vertices will be matrices while the coefficients of the matrices will be elements of certain finite fields. How each matrix element is connected to the other matrix elements (essentially the same thing as saying how each vertex in the graph network is connected to any other vertex) will depend on the Quadratic residue and the Legendre symbols defined above. We shall now see which matrix groups we will be working with.
Definition 4.5 (PGL2(K) projective linear group over a field K). Let K. be any field. Let us denote by GK2(K) the group of invertible 2-by-2 matrices with coefficients in K, ie, the matrices with non-zero determinant. Let PGLz(K) be the quotient group
PGL2(K) = (L)(()/2((3)
where
GTa(K) { (a d d) ad be + 0
Z(K) { { a)
00}
In these definitions it is assumed that all entries are elements of the field K. Remark: If K F,, (the finite field of g elements), then simple computation gives the size of PGL,

---

Published in Transactions on Machine Learning Research (12/2024)
to be [GL2((E,) = 9(9² - 1). In Section 4.3 we shall use this property to construct bipartite - by
-1q2-1)
Ramanujan networks. For more details see appendix, A.3
2
4.2
Regular Ramanujan graphs
Let p, = ((mod 4) be distinct odd primes (the condition of = 1(mod 4) can be removed at the cost of making the analysis more technical and complicated, we shall mention later how is achieved). The graph XP-9 is constructed using the following general method (Lubotzky et al. 1988)).
1. Choice of group: It will be a Cayley graph (for the notion of Cayley graphs, see Appendix A.1) on P. Thus the vertices of the graph will be elements of PFL2(FF)) Next, we need to take care of the edges.
2. Method of selecting certain special matrices within (F Consider the equation as + Jacobi's four square theorem states that there are p+1 solutions to the equation og +a + p with dg > O odd (i.e., an (mod 2)) and 01, 42, 43 even. The role of the finite field F. will now come into play. We have a set of solutions {(00, 01 02 a3)} (in the integers) of size + 1 to the equation
02 + iag) +aद +ā + = p. For each such solution (an, a1, 02 03) consider the matrix ( ag + iaj
(-az + iaz
ag - ia
where is some fixed integer solution to = -1 (mod g). We will obtain a set of (p + 1) matrices each of which belongs PF (can be chocked from the definition of PGL22(F,)), For example, suppose we take q = 5, p 13, and i (where j2 = -1 mod 5).
Let us choose the solution:
ag = 3,
01 = 0,
02 0, 03 = 2,
to the equation a + of + a
a3 13.
Now, we construct the matrix:
ag + iαg
02 + i03 i01
= 33330 0+3.2
3 6
9)
02 + i0z
ag
-0+3-2 3-3-
=
3
Next, we reduce the entries modulo 5 (since g = 5):
(6
3
6 mod 5)
5
3 1
6
mod 5
3
3)
Thus, an example of such a chosen matrix is:
3 1
3)
1
3
This matrix one of the p + = 14 matrices generated from the solutions to the equation oB + as + až a = 13 using the process described.
3. Form the generating set S of the Cayley graph (see Appendix A.1 to be the set of the (p + 1) matrices created above. The vertices are the elements of PGL2( and the edges are given {(x,xs) x E PGL)(FF), s E S}. In other words, XPM Cay((PLLy
cf. A.1
The graphs are bipartite iff p is not quadratic residue modulo q in other words the Legendre symbol ( = -1 The bipartite graphs XP4 will be (p + 1)-regular, of size 2(a²-1)
2 by s(9"-1) and are Ramamjaa.
2
For a proof see (Lubotzky et al. 1988
Remark: If p =3 3 (mod 4), then similar strategy employed, except in this case one looks solutions of af + af + az + az p with og 0 (mod 2). See MMssitell & de la Harpe. 2006 sec. 2).
7

---

Published in Transactions on Machine Learning Research (12/2024)
4.3 Construction for the fully connected layers
For the fully connected layers consisting of balanced bipartite graphs of size and regularity where m is the number of vertices on each side of the graph, we prune them at initialization in accordance with the Ramanujan graph structure of hubotzky-Phiilipe Phillip-SSaaaak Sarnak (Lubotzky et al. 1988).
Select the largest value of prime q (mod 4) such that dda'112
S m.
2
Select a prime p = 1 (mod 4) such that the Legendre symbol (4.4)
= -1 (note that this choice
always possible as given a prime q there are infinite number primes p satislying this properly)
Follow the construction using these values of p and q as given in Section 4.2
Selecting the minimum possible value of p will give us the sparsest possible Ramanujan graph. For example, consider 4096 4096 original fully connected layer, our choice of (p.g) q) (5, 17) gives rise to bipartite sparse Ramanujan graphs of size 2448 2448 with regularity 6.
Note: Here we have taken p 1 (mod 4), but we could have also chosen 3 (mod 4) or even p= 2 (mod 4) (see construction of cubic Ramanujan graphs (Chiu 1992) resulting in even spanser networks.
4.4 biregular Ramanujan graphs
A bipartite graph is said to be (d1, d2) biregular if each bi-partition has fixed regularity d1, d2 respectively. Note that a simple computation reveals that if (2) are the bi-partition sizes, then njd, = n2d2. Thus three parameters are needed to specify these types of graphs. One way to construct biregular Ramanujan graphs is the following, see (Burnwal et al. 2021):
1. Select a prime and create cyclic shift permutation matrix P= [P]g
with [P]s 1 if
j = i i-1 1 (mod q) and 0 otherwise.
ln
lg
La
pl
I
P
2. Select any value of I S q and create the bi-adjacency matrix B
I
p2
p2(1-1)
p4-1
p(a-1)(1-1).
where Ig is the q x identity matrix and is as above.
3. The biadjacency matrix B can be used to generate adjacency matrix of any m X n bipartite graph as Bixn
Adj Omxx
B 0nxn
B is q² lq matrix and the bipartite graph of size q² lg with biregularity (4, The graphs whose bi-adjacency matrices are represented B are Ramanujan. These graphs explicit realisations of the Ramanujan r-coverings of the full (k, biregular bipartite graph on k + vertices as shown in (Hall et al. 2018 cor 2.2).
Note: The condition 2 / is not a necessary requirement. The reason behind this flexibility lies in the specific properties of the bi-adjacency matrix B, which has dimensions q² by lg. The critical insight is that creates a Ramanujan graph, then its transpose, denoted as BT (with dimensions lq by q²), also creates a Ramanujan graph.
4.5 Construction for the convolutional layers
The convolutional layer can be thought of a matrix of dimensions [Nouel x |N |Ka] x [K,] where Nouel is the number of output channels, |Nal is the number of input channels, | is the kernel width and
8

---

Published in Transactions on Machine Learning Research (12/2024)
Kkl is the kernel height. This is considered to be bipartite graph with [Vessl = 1Ne x |K w [K
and
Vright =
|oal where each vertex of Vieft has edge with each vertex of Veight-
Select the largest value of prime such that g² s [eeftl-
2. Select the largest value of I such that 1
S q and 1g S |Vrighel-
3. Follow the construction as given in Section 4.4
The pruning mask thus obtained is a matrix size q² x lq with the effective number of connections being equal to q² x L. The original pruning mask of the convolutional layer has size [Nouel x [[ x [Kwl x [Kal]] By construction the obtained Ramanujan graph is actually a subgraph of the original pruning mask and thus the entries in the original mask not part of the constructed Ramanujan graph are set to 0.
Note: The above construction assumes Vieft 2 Vright. If this is not the case, we can simply swap the roles of and I since from the construction 4.4 we know D also creates Ramanujan graphs.
4.6 Time Complexity of Construction
The time complexity for constructing ramanujan graphs for fully connected layers following Section 4.3 is mainly dominated by the creation of the PGL2 group in which first we need to create the generator matrix and then find the equivalence classes which takes time Og x q). The solution to the four square problem has complexity O(p*) giving an overall complexity of O(q² + p²). Similarly for constructing Ramanujan graphs for convolutional layers as given in Section 4.5 the time complexity comes out to be O4 1q) since we need to create the bi-adjacency matrix B.
4.7 General bipartite networks
In the case of bipartite networks with arbitrary sizes, one can achieve as sparse Ramanujan graphs as possible. It has recently been proven by Marcus, Spiclman and Srivastava that for the regular case, for cach degree d 3, infinite families of bipartite Ramanujan graphs exist. This is also true for the biregular case, for each pair (d1,d2) with d1, d2 2 3, d2 kd1, & 2 2. Further, they showed the existence of these types of graphs of all sizes. Their method of proof is probabilistic and existential in nature. It does not give explicit families of bipartite Ramanujan graphs. However there now exist polynomial time algorithms (Cohen 2016 (for the regular case) (Gribinski & Marcus 2021) (for the biregular case) with which we can extract explicit Ramanujan graphs. For the regular case, we fix an integer n 2 3 and a degree d 2 3 and in the output we shall obtain a d-regular n bipartite Ramamujan graph while for the biregular case, we fix three integers n, d with 2,d k and obtain (d, kd) biregular Ramanujan graph of size kn
5
Experimental Methodology and Results
The goal of our experiments is study the effectiveness of deterministic Ramanujan graph based sparse network construction.
5.1 Datasets and architectures
The datasets used for the experiments are CIFAR-10 and CIFAR-100 (Krizhevsky 2009). The experiments are performed over variety of architectures including VGG13, VGG16, VGG19 Simonyya & Zisserman,
2014), AlexNet (Krizhevsky et al. 2012), ResNet18 and ResNet34 (He et al. 2016 to show the robustness of our method. We procced in two parts. In the first part, we prune the Fully Connected layers by replacing them with sparse Ramanujan Graph which is applicable for VGG13, VGG19 and AlexNet archilectures. In the second part, we prune the whole network including the Convolutional layers and the Fully Connected layers which is applicable for all the architectures considered in our experiment. The performance of the fully dense and the pruned networks are compared in each case. Finally, we compare the performance of our method against various sparse neural networks obtained by state-of-the art pruning at initialisation algorithms
9

---

Published in Transactions on Machine Learning Research (12/2024)
for VGG16 and the ResNet34 architectures. Training parameters for all of the architectures same and are
summarized in Table 1 We report accuracy randomly split 16% test set for all the experiments.
Table 1: Training Parameters for the experiment
Hyperparmeters
Epochs
200
Train Batch Size
256
Test. Batch Size
128
Learning Rate
0.1
LR Decay, Epoch
10x,
[100, 150]
Optimizer
SGD
Weight Decay
0.0005
Momentum
0.9
Weight Initialization
Kaiming Uniform
5.2 Methods compared
The performance of the pruned networks is compared with that fully dense network having similar number of nodes in each layer. Wo also compare our method with other sparse neural networks obtained by state-of-art pruning at initialization techniques. Like our approach, these methods generate sparse connectivity structures which are initialized to random weight values and then trained using backpropagation. The pruning methods compared include, Random (Liu et al.] 2022). ERK (Evci et al. 2020 Mocanu et al. 2018), GraSP (Wang) et al. 2020), and SynFlow (Tanaka et al. 2020). The number of iterations used for SynFlow are 100 and for ERK and GraSP it is 1 keeping the rest of the hyperparameters same as in Table 1
5.3 Network construction parameters
Experiments are conducted two parts: 1) Considering sparse Fully Connected layers only, 2) Considering the entire network to be sparse including the Convolutional and the Fully Connected layers. For the first part, we consider sparse fully connected layers using the construction of Ramanujan graphs given in Section 4.3 We have used a dedicated fully connected layer of size 4096 x 4096 for VGG13, VGG19 and AlexNet architectures and the values used for and (Section 4.3) are given in Table 2 This results in the fully connected layer becoming of size g(9² 1)/2 x q(9² 1)/2 with the effective number of connections between the layer being equal to x (q² 1)/2 (p + 1).
Table 2: Values p and used to generate the sparse fully connected layer VGG13, VGG19, AlexNet.
Model
FC Layer Size
4096 4096
p
29, 109
17
For the second part, we consider sparse convolutional layers using the construction of Ramanujan graphs as given in Section 4.5 in addition to the fully connected layers. The size of convolutional layer being pruned and the values of / and used (Section 4.5) for VGG16 and ResNet34 architectures is given in Table g while for the rest of the architectures is given in Table 7
The network density (ratio of number of edges in a sparse network lo a fully dense nelwork) reported in Section 5.4 is calculated by dividing the number of connections which is equal to the sum of q x (q² 1)/2 x (p +p+1) (number of connections fully connected layer) and q² x (number connections in each of the convolutional layers) divided by the total number of connections present in the fully dense network with the similar number of nodes.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Table Values of q and generate Ramanujan Graphs for layers of VGG16 and ResNet33
VGG16
ResNet34
convolutional layer Size
9
convolutional layer Size
[128 x 64 x 3 x 3] X
11
52
[64 x 64 x x 3] x 6
7
82
128 x 128 x 3 x 3
x
11
104
[128 64 x x 3
x 1
11
52
256 x 128 x 3 x
13
88
[128 x 128 x x
x 7
11
104
[256 x 256 x 3x|
13
177
[256 x 128 x
x
13
88
512 x 256 x x1
19
121
[256 x 256 x x
x 11
13
177
512 512 x x
19
242
[512 256
3
121
[512 512 x 3x
x 5
19
242
5.4 Results and discussion
We study the accuracy of sparse networks obtained by our technique for various architectures and datasets. The accuracy is compared with that of fully dense network with similar number of nodes. Results for the first part of the experiment where only the intermediate fully connected layer is sparse, are summarized in Table By definition, network density is the ratio of number of edges in the sparse network the number of edges in a fuly dense network. can be observed that the Ramanujan graph construction allows extremely sparsify the fully connected layer to network density of 0.43% while still having comparable the accuracy of the similar fully dense model.
Table 4: Accuracy VGG and AlexNet when only the FC layer is sparsified
Dataset: CIFAR-10
Dataset: CIFAR-100
FC layer Size
FC layer Size (Network Density)
Model
(Network Density)
Model
1096 x 4096
2448 x 110
2448 x 30
1096 4096
2448 x
2448 x
(Unpruned)
(1.6%)
(0.43%)
(Unpruned)
(1.6%)
(0.43%)
VGG13
92%
91%
91%
VGG13
66%
66%
63%
VGG19
92%
92%
92%
VGG19
66%
67%
63%
AlexNet
86%
84%
86%
AlexNet
67%
66%
66%
For the second part of the experiment where sparsify the complete network including the convolutional layers and the fully connected layer, we could achieve an overall network density of ~2% to ~5% for VGG, 22.3% for AlexNet and ~5% for the ResNet architectures. The accuracy of the models on the CIFAR-10 and CIFAR-100 datascts are summarized in Table small accuracy drop is observed as compared to the fully dense network.
Table Accuracy of various architectures when the complete network sparsified including the Convolutional and the FC layers
Dataset: CIFAR-100
Dataset: CIFAR-10
Model
Unpruned accuracy
Pruned Accuracy
Network
Unpruned
Pruned Accuracy
Network Density
Density
Model
VGG16
70%
66%
5.3%
accuracy
VGG13
92%
90%
1.7%
ResNet18
55%
54%
5.6%
VGG16
93%
91%
5.3%
ResNet34
57%
56%
5.2%
VGG19
92%
89%
2.4%
Dataset: Tiny- ImageNet
AlexNet
86%
82%
2.3%
Unpruned
Pruned Accuracy
Network
ResNet18
87%
86%
5.6%
Model
accuracy
Density
ResNet34
88%
86%
5.2%
VGG16
43%
40%
5.3%
ResNet34
56%
48%
5.2%
11

---

Published in Transactions on Machine Learning Research (12/2024)
Finally, compare the performance of the proposed Ramanujan sparse network initialization with sparse networks obtained by state-of-art, pruning at initialization techniques. The comparison of accuracy between various pruming at initialization techniques at network density ~5% is shown for the VGG16 and ResNet34 architectures in Table
Table 6: Comparison of method against sparse neural networks obtained by pruning at initialization
Dataset: CIFAR-10
Dataset: CIFAR-100
Dataset: Tiny-ImageNe
VGG16 (Network Density ~5.3%%
VGG16 (Network Density ~5.3%%
VGG16 (Network Density +5.3%
Method
Accuracy
Method
Accuracy
Method
Accuracy
Unpruned
93%
Unpruned
70%
Uupruned
43%
Our Method
91%
Our Method
66%
Our Method
40%
Random
89%
Random
60%
Random
35%
ERK
91%
ERK
62%
ERK
39%
SynFlow
92%
SynFlow
65%
SynFlow
40%
ResNet34 (Network Density m5.2%%
Net34 (Network Density ~5.2%)
RosNet34 (Network Density ~5. ~5.2%%
Method
Accuracy
Method
Accuracy
Method
Accuracy
Unpruned
88%
Unpruned
57%
Unpruned
56%
Our Method
86%
Our Method
56%
Our Method
48%
Random
81%
Random
50%
Random
45%
ERK
86%
ERK
56%
ERK
47%
GraSP
86%
GraSP
56%
GraSP
29%
We can observe that the proposed sparse noural network can achieve comparable accuracy to other sparse networks obtained by iterative pruning at initialization Lechniques. It also siguificantly outperforms the randomly connected sparse network. The accuracy of the Ramanujan graph based sparse networks remains close to that of a similar fully dense network even low network density.
6 Conclusion and Future Work
We presented a technique for constructing sparse neural networks that can be trained to a high accuracy. The method is based on deterministic Ramanujan graph construction technique using Cayley graphs and Ramanujan coverings. The construction is used for gencrating sparse and regular bipartite graphs which are stacked to obtain fully connected and convolutional layers for CNN and ResNets. Experimental results benchmark data sets demonstrate that even very sparse Ramanujan network structure can achieve comparable accuracy to that of fully dense network with similar number of layers and nodes.
With the success of sparse deterministic Ramanujan neural nelworks, our further direction of work is to implement these in the case of transformers and study sparse Ramanujan transformer networks. The proposed deterministic construction tochnique expected to significantly roduce the number of paramcters and training time while maintaining high accuracy.
References
Simon Alford, Ryan Robinett, Lauren Milechin, and Jeremy Kepner. Training behavior of sparse neural network topologies. In 2019 IEEE High Performance Extreme Computing Conference (HPEC), 2019. doi: 10.1009/HPEC.2019..80
Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83 96, Jun 1986. ISSN 1439-6912. doi: URL
Noga Alon and Vitali D Milman. A1, isoperimetric inequalities for graphs, and superconceentrator.. Journal of Combinatorial Theory, Series B, 38(1):73-88 88, 1985.
Goulnara Arzhantsova and Arindam Biswas. Logarithmic girth expander graphs of (F,) Journal of Algebraic Combinatorics, 56(3) Nov 2022. ISSN 1572-9192, doi: 00.1007/110001-002 01128-z. URL ottp::///dda.aoo//o...0//0000000
12

---

Published in Transactions on Machine Learning Research (12/2024)
Arindam Biswas. On Cheeger type incquality in cayley graphs of finite groups. European Journal of Combinalorics, 81:298 308, October 2019. doi: 10. 20.1016/1eec:2219.06.0000 URL https::/doi.orgg// 1016/j.ejc. 2012) 06.006.000 009
Arindam Biswas and Jyoti Prakash Saha. A Cheeger type inequality in finite Cayley sum graphs. Algebraic Combinatorics, (33):517-531, 2021. doi: 10.5802/alco.166 URL https://alco. weentr--ersente orggs 10. 580005882222000 alco.166/
aarticees110.5800
Arindam Biswas and Jyoti Prakash Saha. A spectral bound for vertex-transitive graphs and their spanning
subgraphs. Algebraic Combinatorics, 6(3):689-706, 2023. doi: 10.5802/alco.278. URL https://alco
centre- mersenne. otg/articces//105500000 278/
Emmanuel Breuillard, Ben Green, Robert Guralnick, and Terence Tao. Expansion in finite simple groups of lie type. Journal of the European Mathemalical Sociely, (766):1677-444/ 2015. doi: 10.4171 (0.4111/jjems// //jess/533
URL https://doi.org org/ 10 4171/Jems/533
Shantanu Prasad Burnwal, Kaneenika Sinha, and Mathukumali Vidyasagar. New and explicit constructions of unbalanced Ramanujan bipartite graphs. The Ramanujan Journal, 57(3):1043-1069, April 2021. URL
https://doi.org: 10. http:/o...gg.....oo////11111----
Tianlong Chen, Xuxi Chen, Xiaolong Ma, Yanzhi Wang, and Zhangyang Wang. Coarsening the granularity: Towards structurally sparse lottery tickets. In Proceedings of the 39th International Conference on Machine Learning, volune 162 of Proceedings of Machine Learning Research, pp. 3025 3039. PMLRR 17-25 Jul 2022.
Zhuangzhi Chen, Jingyang Xiang, Yao Lu, Qi Xuan, Zhen Wang, Guanrong Chen, and Xiaoniu Yang. Rgp: Neural network pruning through regular graph with edges swapping. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-13, 2023a. doi: 10.1109/TNNI.S 20211//TTN.S222233388888823 32283888
Zhuangzhi Chen, Jingyang Xiang, Yao Lu,, Qi Xuan, Zhen Wang, Guanrong Chen, and Xiaoniu Yang. Rgp: Neural network pruning through regular graph with edges swapping. IEEE Transactions on Neural Networks and Learning Systems, 2023b. doi: 10.1109 10.1109/TNNIS, 10099/NNNS.20000 2023.328089..
Hongrong Cheng, Miao Zhang, and Javen Qinfeng Shi. A survey on deep neural network pruning-taxonomy, comparison, analysis, and recommendations. arXiv preprinl Xrv: 067667, 2023.
Patrick Chiu. Cubic Ramanujan graphs. Combinatorica, 12:273-288 -277 1992.
Fan Chung. A generalized Alon- Non-Boppana bound and weak Ramamujan graphs. The Electronic Journal of Combinatorics, 23(3), July 2016. doi: 10.37236/557 333236/5333. URL https://doi. //t///00.72/6533333
Michael B Cohen. Ramanujan graphs in polynomial time. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 276-281. IEEE, 2016.
Giuliana Davidoff, Peter Sarnak, and Alain Valette. Elementary Number Theory, Group Theory and Ramanujan Graphs. London Mathematical Society Student Texts. Cambridge University Press, 2003.
Jozef Dodziuk. Difference equations, isoperimetric incquality and transience of certain random walks.
Transactions of the American Mathematical Society, 284(2):787 794, 1984.
Kiara Esguerra, Muneeb Nasir, Tong Boon Tang, Afidalina Tumian, and Eric Tatt Wei Ho. Sparsity-aware orthogonal initialization of deep neural networks. IEEE Access, 2023.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In ArXiV, 2020.
Jonas Fischer and Rebekka Burkholz. Plant'n n'scck: Can you find the winning ticket? In International Conference on Learning Representations, 2022.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR. OpenReview.net, 2019.
URL http::///pppppeeeeee..eee///dddr
13

---

Published in Transactions on Machine Learning Research (12/2024)
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are missing the mark? In International Conference on Learning Regresenlations, 2020.
Aurelien Gribinski and Adam W. Marcus. Existence and polynomial time construction of biregular, bipartite Ramanujan graphs of all degroes, 2021.
The GAP Group. GAP Groups, Algorithms, and Programming, Version 4.12.2, 2022. URL https
7/ //www.ge www.gga--syy. stap-system.ommm org.
Chris Hall, Doron Puder, and William F. Sawin. Ramanujan coverings of graphs. Advances in Mathematics, 323:367 410, 2018. ISSN 0001-8708. doi: https://bbbiorr////.l00//aaaama 201..........002.2. URL https://wwy sciencedirect. www.science//eaeeeecccecceeeeeee http:///sscaaaaaarrrrr/////////.
Soufianc Hayou, Jean-Francois Ton, Arnaud Doucet, and Yec Whye Tch. Robust pruming at initialization. In
International Conference Learning Represendations, 2021. URL http:////oppneeeeeeeeeefrrrrrrre
uc2_4AA
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE conference on computer vision and pottern recognition, 2016.
Duc Hoang, Shiwei Liu, Radu Marculescu, and Zhangyang Wang. Revisiting pruning initialization through
the lens of Ramamuja graph. Tn International Conference on Learning Representations, 2023.
Shlomo Hoory. A lower bound on the spectral radius of the universal cover of graph. Journal of Combinatorial Theory, Series B, 93(1):33 43, Jamuary 2005. doi: 0o.1016/..etbb.2204.00.0000 URL https://doi.onr org/ 10. 1016/1 jctb. 2000.06.0000....00.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439 561, 2006.
J. Kepner and R. Robinett. Radix-net: Structured sparse matrices for deep neural networks. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 268-274. IEEE Computer Sociely, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. In NEURIPS, 2009.
Alex Krizhevsky, Tlya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. In NEURIPS, 2012.
Steinar Lacnen. One-shot neural network pruning via spectral graph sparsification. In TAGML Workshop, ICML, 2023.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pochenizkiy. The unrcasonable effoctiveness of random pruming: Return of the most naive bascline for sparse training. In International Conference on Learning Representations, 2022.
Shiwei Liu, Tiaulong Chen, Zhenyu Zhang, Xuxi Chen, Tianjin Huang, Ajay Kumar Jaiswal, and Zhangyang Wang, Sparsity may cry: Let fail (current) sparse neural networks together! In International Conference Learning Representations, 2023.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through lo regularization. In International Conference on Learning Representations, 2018.
A Lubotzky, R Phillips, and P Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 277, 1988.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? In Advances in Newral Information Processing Systems, vol- ume 34, pp. 12749- 12760, 2021. URL https: httpps://procceddiggs neurips. www.nees...ppppeeeeeeo cctpaper_fiileeeeeeee files/paper/2021/ Enneeecc..0rrrcs00003e5eeeeeeee2
14

---

Published in Transactions on Machine Learning Research (12/2024)
Huizi Mao, Song Han, Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, and William J. Dally. Exploring the
regularity of sparse structure in convolutional neural networks, 2017. URL sottp:://arxiv.orr/aaeee wogg/aba/////
08922
Adamn W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrecs. Annals. Math., 182:307 325, 2015.
Adam W. Marcus, Daniel A. Spiclman, and Nikhil Srivastava. Interlacing familics IV: Bipartite Ramanujan graphs of all sizes. STAM Journal on Compuling, 47(6))2488-25)) 2018. doi: 10.1137/16M1061766. URL https://doi.. 101/100.117/1661006
G. A. Margulis. Explicit constructions of graphs without short cycles and low density codes. Combinatorica, 2(1):71-78, Mar 1982. ISSN 1439-6912. doi: 10.1007 BF0007/222259 URL BF02579283
Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51 60, 1988.
Docebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madcleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. In Nature communications, 2018.
M. Morgenstern. Existence and explicit constructions of + regular Ramanujan graphs for every prime power Journal of Combinatorial Theory, Series B, 62(1):44 62, 1994. ISSN 0095-8956. doi: bttps://doi.ore wtt.:///.o..11/0/////1/1 10..006/jct......././e.. 1994.1054. URL /tt.ittp////s..ceceeeeeeeeeeeeee htt////wwwwinnndderetettttt ctt/s//ic/////rrii//////ii $0095895684710549
Antoine Musitelli and Pierre de la Harpe. Expanding graphs, Ramamujan graphs, and 1-factor perturbations. Bulletin of the Belgian Mathematical Society-Simon Stevin, 13(4):673 680, 2006.
A. Nilli. On the second eigenvalue of a graph. Discrete Mathematics, 91 210, 1991 ISSN 0012-365X. doi: https///60..ogg//0000///0001 111p://000110000001-1120000000 (911122233 URL /attps://ww..stt http::/wwwwwccccnnncrrrccccc wttp://wwt.cooccecee.eeeeeeeceee atticCle/ii10011226x110111
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Bithika Pal, Arindam Biswas, Sudeshna Kolay, Pabitra Mitra, and Biswajit Basu. A study on the Ramanujan graph property of winning lottery tickets. In International Conference on Machine Learning, pp. 17186- 17201, 2022.
Hoang Pham, The Anh Ta, Shiwei Liu, Lichuan Xiang, Dung Lc, Hongkai Wen, and Long Tran-Thanh. Towards data-agnostic pruming at initialization: What makes a good sparse mask? In Advances in Neural Information Processing Systems, pp. 80044-80065, 2023.
Ameya Prabhu, Girish Varma, and Anoop Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 20-35, 2018.
Yehonathan Refael, Iftach Arbel, and Wasim Huleihel. Learning SkS-level structured sparse neural networks using group envelope regularization. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
URL https://openrevierr wwtp://orrruiiiixxxxXXXXXXT
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fino-tuning in neural network
pruning. In International Conference on Learning Representations, 2020. URL forum? forum?id==11$$000ka
15

---

Published in Transactions on Machine Learning Research (12/2024)
Peter Sarnak. Some Applications of Modular Forms. Cambridge Tracts in Mathematics. Cambridge University Press, 1990.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2014.
Olaf Sporns. Graph Theory Methods for the Analysis of Neural Connectivity Patterns, pp. 171-185. Springer US, 2003. ISBN 978-1-4615-1079-6 doi: 10.1007/978-1-4415--10 1007
URL https://aoi.org///
12
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Eric Xing, Kangwook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets at initialization. In Advances in Neural Information Processing Systems, volume 35, pp. 14529-14540, 2022.
James Stewart, Umberto Michieli, and Mete Ozay. Data-free model pruning at initialization via expanders. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4518 4523, 2023.
Edric Tam and David Dunson. Spectral Gap Regularization of Neural Networks. arXiv e-prints, art. XXXx:2304.03096 April 2023. doi: 10.48550/arXiv 230.033....0006
Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. Pruming neural networks without any data by iteratively conserving synaptic flow. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc.
Artem Vysogorets and Julia Kempe. Connectivity matters: Neural network pruning through the lens of effective sparsity. J. Mach. Learn. Res., 24, 2023.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
Huan Wang, Can Qin, Yue Bai, Yulun Zhang, and Yun Fu. Recent advances neural network pruning at. initialization. Xiv preprint ar arXi::2103.06 064606 2021.
Jiaxuan You, Jure Leskovee, Kaiming He, and Saining Xie. Graph structure of neural networks. In International Conference Machine Learning, volume 119, pp. 10881-10891, 2020.
A
Appendix
A.1 Cayley graph
Let G' be group and let S be subset of G' that is closed under inversion i.e., = S-1, The corresponding Cayley graph C(G,S) is graph with vertex set the elements of G and edge set {(z, xs)) E G, S}. As an example of a Cayley graph of a non-abelian group, one can take the group G = D4, the dihedral group of order 8 with elements (e,r, r2,,, ,,, sr, ST sr and generating set = {r,s,r Here the r denotes rotation by & and s is reflection. So r 1, s2 and sr r-
16

---

Published in Transactions on Machine Learning Research (12/2024)
3
89
87
The Cayley Graph C(Da, r3)
A.2 Expander graphs and Ramanujan graphs
An expander graph is a structurally sparse graph that has strong connectivity properties. The connectivity can be quantified in different ways which give rise different notions of expanders such as vertex expanders, edge expanders and spectral expanders. These notions actually interrelated. In the following, graph r = (V, E) is tuple consisting of verlex set V and edge set E which is subset of V x V.
A.2.1 Combinatorial expansion
Definition A.1 (vertex Choeger constant). The infirumm of the quantity [6(X] |X] where 5(X) denotes the outer vertex boundary of X i.e., the set of vertices in I' which are connected to a vertex in X but do not lie in X as X runs over all non-empty subsets of V satisfying the condition with [X] 2 vertex Cheeger constant and is denoted by hy (T).
V is known as the
Definition A.2 (edge-Cheeger constant). The edge boundary of a set S, denoted 85, is 65 = the set of edges going out from S to its complement. The edge Cheeger constant I, denoted by hg([), ; is defined as: he([)- = min 1681 as S satisfies the following: {S + emply set, |S| < ] and D is the maximum degree of DIS
the graph r
The vertex Cheeger constant hy (T) and the edge Cheeger constant hT are related by the following equivalence
hv D
< he & hv
where D denotes the maximum degree of the graph (the degree of each vertex is the number of edges going out from the vertex). This allows one to speak about vertex expansion and edge expansion interchangeably. Having high combinatorial expansion means having high Cheoger constant, a desirable property for our case.
A.2.2 Spectral expansion
Given a finite undirected graph I' the eigenvalues An & ... & a1 of its adjacency matrix are all real and A1 & D with equality iff the graph is D-regular. The spectra, ie., the distribution of the eigenvalues convey a lot of information about the structure the graphs. For instance, the quantity A - Ay (also known in the literature as the one sided spectral gap) quantifies the connectivily and the combinatorial expansion of the graph via the discrete Cheeger-Buss inequality, discovered independently by (Dodziuk 1984) and by AAlon & Milman 1985). A graph I (V, is said to be spectral expander if the quantitics A1 A22, PA D are both bounded away from zero, where A 1 if the graph is bipartite and k hehwwwise.
A.2.3 Discrete Cheeger-Buser inequality
The discrete Cheeger Buser inequality discovered independently by (Dodziuk 1984) and by (Alo & Milman 1985) allows one to pass from spectral expansion to combinatorial expansion. The inequality states that
hg (T)
< 02 < 2h (T),
2
17

---

Published in Transactions on Machine Learning Research (12/2024)
where a2 denotes the second smallest cigenvalue of the normalised Laplacian matrix of I and is related to the eigenvalues of the adjacency matrix via
11-0, & Vi 1.2....... n,
where D and denote the maximal and minimal degrees respectively. See Chuung 2016 for details. From the above, it is easy check that high |^l| |Ag] ensures high hg([) and vice- versa. Thus, the two notions of expansion are inter-connected and every spectral expander remains combinatorial expander. They are actually equivalent for some classes of graphs, for instance bipartite graphs (as the adjacency spectrum is
symmetric about the origin), variants of algebraic graphs e.g., see (Breuillard et al. 2015 Biswas 2019
Biswas & Saha 2021 2023 etc.
A.2.4 Ramanujan graph bounds, Alon-Bopanee Theorem
A d-regular graph is said to be a Ramanujan graph if 1 & 2 In the case of bipartite graphs, An = Å and A=-1 = X2, hence the previous expression reduces to D12l & 2 For fixed degree, with the sizes of the graphs growing larger and larger, these are the best possible expanders, as given by the Alon-Bopanna bound (Alon 1986 Nilli 1991).
Theorem A.3 (Alon-Boppana). For every d regular graph on n vertices,
X 222vd-1- On (1).
The (1) term is quantity that lends to zero for every fixed d as - 00.
The bound requires a bit of technical details. However, if one relaxes a bit the right hand side of the above bound then one can easily show the following,
A -2
The proof goes as follows: Let A be the adjacency matrix of G, then trace(A4) is the number of all walks of length A in G that start and end in the same vertex. In particular, all the diagonal entries A² are 2 d. Thus, (race(A²) 2 rd. On the other hand,
trace(A²) Σ X S de + (n 1)A2.
Thus, (n - 1)x² > dn- d,, which implies that X2 R-d 1-1
See (Hoory et al. 2006) for details.
A.2.5 Expanders and Ramanujan graphs from finite simple groups
The existence and construction of expanders are a deep question and those of Ramanujan graphs are even deeper. Most the constructions of expanders are based on Cayley graphs of finite simple groups of Lie type. The first construction is due Margulis (Margulis 1982). Later Lubotzky-Philippe Phillls--ahllp-sSSaaal Sarnak (Lubotzky et al, 1988) constructed Ramanujan graphs from ST Till 2014 these graphs and variants thereof by (Chiu 1994] were the only known construction of Ramanujan graphs. Recent works of Marcus et al. 2015) have shown the existence of bipartite Ramanujan graphs of all degrees and sizes. Recently, there has also been new research directions on the topic of construction of expanders satisfying other desirable properties such as the diameter-by-girth ratio are bounded, for instance Arzhantseva & Biswas 2022). will be interesting to see if these special expander networks play important roles as architectures for neural networks or not.
1992 and (Morgenstern)
Sarrkus-ppiimann--aa
Question A.4. Why are the LPS grophs Lubotzky et al. 1988 (sec 4.2) and the graphs presented in see 4-4 Ramanujan?
For the LPS graphs, the proof quite involved, a nice exposition on the proof can be found in (Davidoff ct al. 2003), Chapter 4 and also in (Sarnak) 1990) Chapter 3. For the graphs presented see 4.4, a direct computation of the eigenvalues using the propoerties of cyclic shift permutation matrices is enough. See proof of Theorem 3 in (Burnwal et al. 2021
18

---

Published in Transactions on Machine Learning Research (12/2024)
A.3 Projective Linear Groups Over Finite Fields
The projective linear group P. (Fa) is malrix group defined as the group of linear translormations on the projective space over Eg, modulo scalar transformations.
Let Fg be finite field with g elements.
Let GT (F,) denote the general linear group of n x n invertible matrices over Eg-
The projective linear group (G)n((F)) is defined as:
(L))
(F = Z(GLn (FE
where (F,),((F)) is the center of GL,(F,)) which consists of scalar matrices.
Matrix Form of (FL,
The projective general lincar group (FL2(FFg) is the group projective transformations of the projective line over F.. can be expressed in terms of matrices as follows:
The general linear group (L)(F consists of all invertible 2 matrices over Fg. A matrix A E GL2(Fa) is given by:
aa
a b
A =
where a, b, c, d Fg and det(A) ad be + O.
Center of (F2 The center of GL2(FE) consists of scalar matrices of the form:
Z(GL2(B.)) = {M7 A F7
where / is the identity matrix:
> 0
0 )
AI
and F is the multiplicative group of the field Eg. The projective general linear group PGL,(IF,) is defined as the quotient of GL) by its center:
GL2(Fn)
PGL2(F,)) 2(GL2(F,))
In matrix terms, element of PGL2(F,) can be represented by matrix A GLz(Fg); where matrices are considered equivalent if they differ by scalar multiple. Thus, the matrix form of PGL2(F,) is represented by equivalence classes of matrices of the form:
{( 2) Ja,b,c,d E F, and ad be & o)
modulo the scalar matrices.
The distinct elements of (F2) are represented by:
( !) )
1 9
PGI=((F) consists of 24 elements.
19

---

Published in Transactions on Machine Learning Research (12/2024)
A.4 Experimental methodology
The q and values used by the Ramanujan Graph construction for the convolutional layers mentioned in Section 4.5 for various architectures is provided in Table 7
Table 7: Values of and to generate Ramanujan graphs for layers of VGG, AlexNet and ResNet
VGG13
VGG19
Conv Size
q
1
Conv Size
q
256 256 x 3
x
13
177
256 x 256 x 3) x
13
177
512 256 x 3 3
X
19
121
[512 256
3
19
121
[512 x 512 x 3 3 x
19
242
[112 x 512 x x 3 x
19
242
Conv Linear Size
q
1
Conv to Linear Size
q
1
2448 25088
47
533
2448 25088
47
533
AlexNet
ResNet18
Conv Size
q
1
Conv Size
g
[
384 x 256 x 3
3
X
19
121
64 x 64 x 3 x 3
X 4
7
82
384 x 384 x 3
3
X
19
181
[128 x 64 x 3
3
x
11
52
256 x 384 x 3
3
x
13
265
128 x 128 x 3 3
x
11
104
2556 x 128 x x
x
13
88
256 x 256
8
x
13
177
512 x 256 x 3 x
x
19
121
512 x 512 x 3 x
X
19
242
Conv Linear Size
q
1
2448 25088
47
533
20


Reviews:
[{"review_id": "SG9dCtnPxT", "reviewer": "Reviewer_g8Qr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I learned a lot: there are some concepts from graph and group theory that I was unfamiliar with that are quite decently explained in this paper (although I did regularly need Wikipedia or ChatGPT for more intuition). The method has interesting graph-theoretic guarantees, and seems to perform quite well compared to existing methods experimentally, although I'm not knowledgeable enough in this field to judge properly.\n\nWeaknesses: \nThis paper reads more like a mathematics paper than a paper on sparse neural architectures. This need not be a problem - but I suspect a large part of the intended audience may shy away from an abstract and introduction that's this heavy on the presumption that the reader is aware what Ramanujan, Cayley, and bi-regular bipartite graphs are, for example. I think the body of the text, with some adjustments, is reasonably understandable, but the technicality of the abstract and introduction can be toned down to significantly improve readability. \n\nIn particular, the introduction could do a better job by focusing rather on why the properties the algorithm induces are relevant to the task. Why is symmetricity important, for instance? Why is regularity important? What are expander networks, and what is the intuition that it improves empirical performance? \n\nFurthermore, the main algorithm should be elaborated more with proper reference for its claims. \nFinally, the experiments are on fairly small datasets and with small / old models. I'm again not familiar enough to judge if this is significant experimental evidence within the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors define an algorithm for constructing a bipartite graph that is Ramanujan. These have theoretical properties that encourage high 'connectivity' (in an expander sense) while being very sparse. This algorithm is applied to construct weight masks for fully connected and convolutional layers, creating sparse neural networks. Unlike other techniques, this method is deterministic and never looks at the data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical\n- I believe a thorough rewrite with a Machine Learning audience in mind, in particular of the abstract and first couple of sections, is necessary. \n- Hoang 2023 seems like a paper that's very close in both goal and approach, as it also aims to construct Ramanujan graphs. The work currently doesn't make clear what the difference is. Also I wasn't able to follow the argument about Hoory 2006 related to this. \n- The Appendix A.1 and A.2 contains some useful definitions that help with understanding the paper, however the main paper rarely links to them. This would significantly help the reader with understanding. \n- Although the paper is fairly self-contained with background in the appendix, it is missing a lot of background on (projective) linear groups and finite fields. I was not able to understand the construction of PGL_2(F_q). A small example would significantly help\n- The constructions in section 4.2 and 4.4 lack a clear example. It would significantly help the understanding if the steps are explained with a running example. \n- Where does the construction in 4.2 come from? Lubotzky 1988? This is currently unclear.\n- The time complexities given in 4.6 do not have a proof or reference. \n- Why are there no confidence bounds / standard deviations on the experiments? The numbers are close together, so it could be due to randomness. \n\nImprovements\n- Several places uses the term 'multi-shot'. I assume this means data dependency?\n- Symmetry, as discussed in the context of Cayley graphs, isn't well defined. It is shortly mentioned that symmetry helps for computational purposes, but this could be elaborated on a lot more. \n- Section 3: I tried to reproduce the Cayley graph with the generating set S={(1, 0), (1,1), (1,4)}, but I got a different graph than shown in Figure 1. It's possible I misunderstood, but it seems like the generating set is (1, 0), (1,1), (1, 2) or something? But this isn't invertible. \n- 4.1.2: \"The quantities are bounded away from zero\". It wasn't clear to me whether this is > or =>\n- Appendix A.2.3: The quantity d doesn't seem to be defined anywhere\n- Definition 4.5: Mention PGL is the projective linear group\n- Remark below: \\mathbb F_q is never defined.\n- There is no intuition, proof or description why the constructions in 4.2 and 4.4 lead to Ramanujan graphs, except for a reference. This could significantly help understanding. \n- 4.2: It is not clear to me why a complex valued matrix would be an element of this linear group on finite fields. \n- 4.3: \"The Ramanujan graph structure of LPS\". What is LPS?\n- Why is SynFlow not applied to the Resnet?", "broader_impact_concerns": "N/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TQ17yxiYlr", "reviewer": "Reviewer_FLZe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nClarity: The paper is written in a clear and easy to follow manner. \nQuality: The quality and scope of the experiments are sufficiently broad, and they generally support the authors claims. The quality of any mathematical derivation is clear and to the best of my knowledge, sound. \nNovelty: The proposed approach is, to the best of my knowledge, useful. \n\nRelevance to TMLR and audience: I believe that the content and topic of the paper fits the scope of TMLR, and fits the criteria that at least a portion of the audience of TMLR will find this article interesting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present a sparse neural network approach using Ramanujan graphs, taking into account properties like path connectivity and symmetricity. The authors show that the method provide comparable accuracy and sparsity with competing pruning approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The general theme of using spectral graph theory and related CS theory techniques for sparsification of neural networks is interesting. Relevant work by Tam and Dunson (https://arxiv.org/pdf/2304.03096) look at sparsification of neural networks from a spectral gap/regularization perspective that I think would be interesting for the authors to comment on.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3jp0dgOjjr", "reviewer": "Reviewer_j1B5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The problem (sparse and trainable/performant neural architectures) is relevant for TMLR.\n- Appears to contribute results that merit attention of the readership, both 'theory' and empirical evaluations.\n- Interesting to see the constructed sparse networks exhibiting high sparsity (small density) while retaining trainability and good post-training performance in terms of accuracy compared to their 'fully dense' counterparts.\n\n**Weaknesses**\n- Overall the presentation and organisation of the paper need improvement.\n- The introduction section needs a major makeover to clearly frame the problem setting, approach and so on.\n- There are some misconceptions, e.g. conflating initialisation with network topology (connectivity structure), and other.\n- The paper appears to be written for mathematicians, esp. sections 2, 3, 4 which are heavy in mathematical abstractions, with little or no exposition of their connection with neural network architectures.\n- Crucially, the step by step description of the method to construct the sparse networks is not nearly clear enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "As far as I can see, this paper proposes a way to construct sparse neural architectures via the theory of Ramanujan graphs. Each neural layer is represented as a bipartite graph where the partition of vertices consists of the set of nodes of the layer and the set of nodes of the previous layer. Bi-regularity is assumed to ensure connectivity properties. These kinds of layers as described are stacked to produce a deep neural architecture which is sparse by construction. It appears that the proposed construction ensures path connectivity and trainability, which is one of the main claims. Another important claim is that these sparse networks upon training achieve comparable accuracy on classification tasks compared to the corresponding 'fully dense' networks. The numerical experiments demonstrate these claims for several neural architectures on CIFAR-10 and CIFAR-100 datasets, with comparisons to previous methods for constructing sparse networks and pruning. Importantly, the proposed approach is complementary to the literature on pruning at initialisation, since sparsity is achieved *before* training; as opposed methods that achieve sparsity by pruning a trained neural network.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Comments on the whole**\n- The paper needs to be re-written, with a machine learning readership in mind.\n- The abstract needs to be re-done to make it (1) useful, in the sense of highlighting the most important aspects of the paper, (2) aligned with the paper, in the sense of representing faithfully what's done in the paper, and (3) accurate and sound, as in being free of errors or misconceptions which may cause confusions.\n- As mentioned already, the introduction section needs a major makeover to clearly frame the problem setting, motivation for the problem, approach and main results, connection with other works and so on. Make it helpful for readers to understand what the paper is about, why it is a relevant, what unsolved problems or obstacles it overcomes.\n- Similar comments for section 2 which tries to set the lay of the land (research gap) and the contributions. The current list of contributions does not clearly describe what this paper achieves. Keep the list of contributions focused on what this work achieves. Put comparisons to other previous works separately, outside the list of contributions.\n- I think casting this paper within the context of pruning at initialisation is inaccurate and potentially could lead to confusions. The paper is about a method to produce (create, define) sparse neural networks via the theory of Ramanujan graphs. As far as I understand, sparsity of the neural net is achieved by the proposed construction, not by pruning the counterpart 'fully dense' neural net (by counterpart meaning both neural nets have the same sets of nodes). This needs to be clarified. It would be okay to say that this work is complementary to the literature on pruning at initialisation. \n- In section 3, interesting read about Ramanujan graphs, and discussions about guaranteeing rigorous Ramanujan, or that the networks remain Ramanujan; Cayley and so on. These things might be interesting *per se* for a mathematics readership, but for a machine learning readership it is important to explicitly establish the connections with (and implications for) machine learning, theory and practice.\n- A comment on the intended meaning of *initialisation*: I get the impression that the authors conflate 'initialisation' with 'masking' and this confusion needs to be cleared. The way I understand these things, say there is a 'fully dense' neural architecture, then masking defines a subnetwork by setting some weights to zero. This I think is what you have called \"network topology\" in some other parts of the paper. While initialisation is the way to set the initial value of connection weights for a given architecture (a given topology). Then in principle these things are not the same, and this needs clarification in the paper to avoid confusions. Perhaps the authors had in mind some initialisation schemes which favour sparsity? Or initialisations designed for sparse networks?\n- Section 4: This section heavily gives the impression of being written for mathematicians. I don't object mathematical definitions and abstractions when they serve a clear purpose for supporting the presentation of the method(s). Try keeping in mind a machine learning readership; then with this in mind, the mathematical definitions/abstractions need to be motivated and clearly connected with ML. Try writing notes to help readers: Tell readers that next they are going to see the definition of such and such, and why the definition is relevant for the machine learning problem that the paper tackles. Then, after the definition is presented, add short discussions (even at the expense of repetition) connecting the mathematical object just defined with corresponding parts of the neural network architecture, or whatever purpose the mathematical thing serves in the paper. The whole point being to avoid the style that appears to present mathematics for the sake of mathematicians, but rather to present for a machine learning readership.\n- Regarding section 5, my main comment is this: I think the paper is missing sufficient details that are necessary for others to reproduce the results. The authors need to fill in the missing details about the step by step description of their method (Section 4) and how it is implemented in the experiments. Think of all the details that anyone would need in order to implement the method and obtain the numbers shown in the tables. Is the code going to be made available? Wy not make it available during the review?\n- In connection with section 5, I reiterate once again my impression that there is a confusion between the meanings of initialisation, masking and pruning. I ask the authors to clarify whether they are in fact doing pruning (e.g. masking applied to a 'fully dense' architecture), or whether as I believe their method produces a sparse network by construction without needing pruning. \n- References: The titles need to be capital-protected to read e.g. Cheeger, Cayley, Ramanujan (multiple occurrences), Alon-Boppana and so on. The roman numerals in the papers of Marcus, Spielman & Srivastava should be capitals. Paper of Noga Alon & Vitali Milman the title should read $\\lambda_1$ not $\\lambda$1. Check carefully the whole list of references to correct these flaws in paper titles. Also check publication venue names and use consistent format as much as possible. \n\n**Page by page feedback**\n\nHere I write comments for each page of the paper.\n\n**Page 1**\n- An inaccuracy to rectify in the abstract: I don't think you \"present a sparsely connected, neural network architecture\" but rather you present a method to construct such kind of architecture. The method is based on the theory of Ramanujan graphs.\n- Also in the abstract: the reference to winning lottery tickets appeared all of a sudden without context. Perhaps mention the lottery ticket hypothesis before mentioning winning lottery tickets? And better if describing what a wining lottery ticket is in this context. If this is cumbersome, then perhaps avoid mentioning wining lottery tickets in the abstract.\n- First sentence of the introduction is a bit vague. The parameter parsimony (funky way to refer to sparsity) is advantageous in various ways. Reducing training time is one and provided that the sparse network is trainable. Another one is computation cost of a forward pass of the trained network, as in when you want to use it for prediction on a new instance.\n- Perhaps the most accurate way to frame your work is that it enables construction of a sparse network that is guaranteed to be trainable and so on. In general, claims presented here need to be aligned with what is done in the paper.\n- I would suggest deleting \"backbone\" and instead write e.g. 'fully dense' network.\n- I suggest avoiding the acronym \"PaI\" and instead write \"pruning at initialisation\" in words.\n- Explain the meaning of \"multi-shot\" in this context, as per the intended meaning.\n- Then explain the meaning of \"zero-shot\" in this context.\n- Replace \"an initialization topology\" with something that better describes what's intended (perhaps \"an initial network topology\"?)\n- Last sentence of first paragraph: merge it into the second paragraph.\n- First sentence of third paragraph: replace \"a sparse initialization architecture\" with \"a sparse initial architecture\"? Or change as needed to clarify the intended meaning.\n- Previous to last sentence of this paragraph: the meaning is almost completely obscure to me. \n- Last sentence: write something more straightforward than \"arrest\" according to the intended meaning.\n\n**Page 2**\n\n- Top: The meaning of \"initialization\" is again not what is usually called initialization in the literature on neural networks. Change this to describe more accurately what's intended. Or define what you mean by \"network initialization\" (which could conflict with the usual meaning of this, but at least a definition would make it clear what you are trying to refer to).\n- Why is it important to adhere to the rigorous definition of Ramanujan graphs? What's the relevance for ML?\n- Maybe write 'fully dense' network instead of \"dense network\"\n- Description of the organisation of the paper: insert section numbers to improve.\n- Section 1.1 on related works: Appears minimal. Perhaps that's okay but at least acknowledge that you mention only a minimal sample of the extensive literature. Some important missed related works include [1], [2] (see below). If any technical term is mentioned here, its meaning needs to be explained. For instance, what is \"one-shot neural network pruning\"\n- Fist paragraph of section 2: Not clear how the zero-shot implies advantage in generalization capabilities, this needs at least some reference or further comment explaining.\n- Regarding (i): Again, why is ensuring Ramanujan property relevant? Try to improve the connection with ML.\n- In (ii): As suggested, avoid \"PaI\" and write explicitly \"pruning at initialization\" instead.\n- In (iii): Is \"symmetricity\" a word? I think not. Replace with \"symmetry\" which is.\n- Claim that \"This is the first [..]\" needs to be accompanied by a comment explaining why the machine learning readership should pay attention to this. \n\n**Page 3**\n\n- Figure 1: In the caption, better write \"An example of two consecutive neural layers where each layer is a bipartite Ramanujan graph.\" To improve the figure, at the top of the columns of nodes put the labels $I$, $J$ and $K$.\n- Contribution 1: In the absence of a definition of the meaning of \"zero-shot pruning\" earlier in the paper, this contribution is difficult to understand. Also, move \"Previous [..]\" to somewhere outside the list of contributions, perhaps after it in a new paragraph discussing these connections and comparisons to previous works.\n- Contribution 2: Change \"initializing\" with something that better describes the intended meaning.\n- Contribution 3: Move \"Previous [..]\" to somewhere outside the list of contributions, perhaps after it in a new paragraph discussing these connections and comparisons to previous works.\n- Contribution 4: The way it is written, it does not appear to be describing a contribution at all. Perhaps this is something that also needs to be moved to somewhere outside the list of contributions.\n- Contribution 5: This appears to be clarifying that your method works for both kinds of layers, fully connected and convolutional, so this is not a separate contribution but rather a clarification point to add to contribution 1 or contribution 2?\n- Two-line paragraph after the list of contributions: Unclear what's being claimed here. Try expanding and clarifying as per the intended purpose of this sentence. Good place to elaborate on the contributions, including the content that I suggested to be moved outside the list of contributions.\n- First section of section 3: This is again mentioning the not guaranteeing being rigorously Ramanujan, but missing the connection of this point with neural network properties that the machine learning readership would/should care about.\n- Again, clarify the meaning of \"network initialization\" and \"initialized networks\" or reformulate to better describe and avoid the conflation with what's commonly called \"initialization\" in the literature on neural networks.\n- Paragraph at the bottom: For readers to understand this, somewhere earlier in the paper it should have been mentioned that each neural network layer corresponds to a bipartite graph, that the whole deep network consists of stacking (concatenating?) such bipartite graphs and so on. Then this paragraph would be focusing on clarifying the point that regularity assumption ensures path-connectedness.\n\n**Page 4**\n\n- Replace \"High-symmetricity\" with \"High symmetry\"\n- At least mention a lay terms description of $\\mathbf{Z}_5$, that it is the finite group with modulo 5 operations.\n- Related note: Currently it is unclear what's the role of the mathematical technicalities mentioned here about this finite group, generating set, adjency matrix and so on. Could the authors elaborate on the connection to neural networks.\n- Section 4: As I commented before, this section currently appears to be written for a mathematics readership, and the request is to improve it adding comments, pointers, motivations, clarifications etc. to improve the connection to neural networks for the sake of the machine learning readership.\n- A special case of this is the paragraph before section 4.1: What should machine learning readers get from it? Why should they care?\n\n**Page 5**\n\n- Figure 2: In the caption, better write \"An example of two consecutive neural layers where each layer is a biregular bipartite Ramanujan graph.\" To improve the figure, at the top of the columns of nodes put the labels $I$, $J$ and $K$.\n- Perhaps change the notations for vertex Cheeger constant and edge Cheeger constant, using suggestive notation that is easy to hold in the mind? Would the authors consider something like $\\mathbf{h}_v(\\Gamma)$ and $\\mathbf{h}_e(\\Gamma)$?\n- A more important point to resolve is why are these Cheeger constants appearing here? Do they play a crucial role for what's coming next, especially for the description of the method that the machine learning readers would need to have these constants in mind while reading about the method and demonstrations in the experiments and so on?\n- The connections between these mathematical abstractions and the machine learning problem targeted in this paper (I think it is constructing sparse neural architectures) need to be made explicit and clear.\n- Bottom of the page: Insert a clickable cross reference to the corresponding appendix for the Cheeger-Buser inequality.\n\n**Page 6**\n\n- Top of the page: Insert a clickable cross reference to the corresponding appendix for the  Alon-Bopanna theorem.\n- Improve the motivation for the need for Definition 4.4 (quadratic residue, Legendre symbol). Even better if the authors add after the definition a short paragraph elaborating on this and its connection with what is to come next.\n- Similar comments for Definition 4.5. And use $\\mathbb{K}$ here to denote a generic field.\n- Displays defining $GL_2(\\mathbb{K})$ and $Z(\\mathbb{K})$: delete \"(in $\\mathbb{K}$)\" and add a line after the second display saying something to the effect that \"In these definitions it is assumed that all entries are elements of the field $\\mathbb{K}$.\"\n- Remark after Definition 4.5: What is $\\mathbb{F}_q$? Is it not $\\mathbb{Z}_q$?\n- First line of section 4.2: Ensure \"$\\mathrm{mod}$\" instead of the current \"$\\mathit{mod}$ \" (twice)\n- It is necessary to explain with copious details, with the machine learning readership in mind, the meaning of everything in points 1, 2, 3, 4 describing the construction. Is 1 a step of the construction and not just a definition? In step 2, a lot of things need to be explained, especially the intriguing $i^2 = -1 \\pmod q$ when you are supposedly working with finite fields. Step 3 requires definitions of the meaning of generating set and the notation \"Cay\" that appears here for the first time in the paper. Step 4 appears to be stating a theorem or proposition, so I am not sure how to see it as a step in a method to construct sparse networks.\n\n**Page 7**\n\n- Section 4.3 does not contain nearly enough information for others to understand how the construction of fully connected layers goes.\n- Section 4.4 needs to improve with comments on connections/implications for the sparse neural networks.\n- Section 4.5 does not contain nearly enough information for others to understand how the construction of convolutional layers goes.\n\n**Page 8**\n\n- Section 4.7 appears to be of interest for graph theory or mathematics readership. The connection with ML and NNs is missing.\n- First line of section 5: The implied meaning of \"effectiveness\" is unclear. What metric is being implied here?\n- Similar comment for \"robustness\" a few lines down.\n- Once again, try to clarify whether the method is pruning or not. Perhaps the claim is that pruning is implicit by the creation of the sparse neural Ramanujan graph layers by means of the proposed method (but the steps of the proposed method are unclear).\n- \"The performance of the 'fully dense' and the pruned networks\"\n- Once again, write \"pruning at initialization\" instead of \"PaI\"\n- Is the code going to be made available? \n\n**Page 9**\n\n- \"corresponding 'fully dense' networks.\"\n- Section 5.3: For understanding the descriptions, it is necessary once again that Section 4 gives an exposition, with copious details, of the proposed constructions for fully connected layers and for convolutional layers.\n- Paragraph after Table 3: \"the effective number of connections being equal to\"\n\n**Page 10**\n\n- Replace \"upto\" with \"up to\"\n- Table 4: Replace \"(Remaining Edge Percentage)\" with \"(Network Density)\" for both tables.\n- In the paragraph before this table: \"summarized in Table 4. By definition, network density is the remaining edge percentage. It can be observed [..]\" \n-  \"construction allows us to extremely prune the fully connected layer to a network density of 0.43% while still retaining [..]\"\n- Paragraph after Table 4: \"achieve an overall network density of\" (replace \"pruning percentage\" with \"network density\")\n- Paragraph after Table 5: Write \"pruning at initialization\" instead of \"PaI\" (twice)\n\n**Page 11**\n\n- Section 6 (conclusion) is rather vague currently. There is space to expand and improve.\n\n**Global changes**\n- Replace \"symmetricity\" with \"symmetry\"\n- Replace \"PaI\" with \"pruning at initialisation\" (make explicit, everywhere).\n - Maybe write 'fully dense' network instead of \"dense network\"\n- Replace \"convolution layer\" with \"convolutional layer\" as per the usage in the neural networks literature.\n\n**Missed literature**\n\n[1] Soufiane Hayou, Jean-Francois Ton, Arnaud Doucet & Yee Whye Teh. Robust Pruning at Initialization. ICLR 2021.\n\n[2] Laurent Orseau, Marcus Hutter, Omar Rivasplata. Logarithmic Pruning is All You Need. NeurIPS 2020.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors put in a considerable amount of work to improve the clarity and presentation of their work, which was one of the main criticisms of the original submission. All authors, and myself, are in agreement that after these improvements, the work is suitable for acceptance.
Decision: Accept (poster)