Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new method to prune neural networks at initialization. By analogy to previous work which used sparse random subnetworks to speed up training, this paper instead uses Ramanjuan graphs, which are well-studied and known to be favorable with respect to expansion. It relaxes the eigenvalue condition of Ramanujan graphs to a new property (IMDB) which empirically correlates to increased performance when the network is trained on image classification tasks.
strength_and_weaknesses: General comments
-

- Why use the third largest eigenvalue of the adjacency matrix? Usually the spectral gap is taken to be the difference between the first and second largest eigenvalues, which is guaranteed to be positive if the graph is connected.

Strengths
-

- The idea of using expander graphs to guide pruning is interesting and unifies existing work.

Weaknesses
-

- The decision to not use existing measures of spectral expansion is not entirely convincing. You mention that the Ramanujan condition is too pessimistic for non-regular graphs when $d_{max}$ is used, but why not use something like the second eigenvalue of the normalized Laplacian?
- The decision to pass to all $K$-regular subgraphs seems somewhat arbitrary and possibly expensive to compute. 
- The pruning measure proposed does not leverage the weights of the network at initialization, since it does not sparsify the network based 
 on sensitivity of the loss function.

clarity,_quality,_novelty_and_reproducibility: The paper provides a new perspective on pruning using the theory of spectral expanders, which are more general than simply using random graphs. The writing in some parts is confusing. For example, Lemma 1 reads "The value of $\mu_0$ for any adjacency matrix is said to be $d_{avg} \leq \mu_0 \leq d_{max}$." This looks like it's stating a definition even though it is part of the lemma statement, and there is no separation between the lemma statement and its proof.
summary_of_the_review: The idea of measuring performance of pruning in terms of spectral properties of the adjacency matrix is a good idea. However, the choices made in deciding upon the IMDB measure seem arbitrary in comparison to existing measures of spectral expansion. The choice of comparing to $\delta r$ is not entirely fair as a baseline, since that particular bound was designed around regular graphs.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes to interpret the (un)success of Pruning neural networks at initialization (PaI). through the lens of the Ramanujan Graph - a class of expander graphs that are sparse while being highly connected. Despite the intuitive belief that PaI and Ramanujan Graph should be naturally related, their underlying relationships are shown to be more sophisticated and non-trivial as the authors analyzed. The authors supposed their analysis with ample experiments. 
strength_and_weaknesses: 
Strength
-	Most prior works on PaI focus on “training signals” such as gradients. This paper studies a complementary angle of graph theory
-	Although there exist prior work connecting Ramanujan Graph and PaI, they did not consider the pseudo-randomness and irregular bi-graphs in practical sparse NNs, and may prefer “collapsed” naïve random graphs (overly expansive)
-	The authors rigorously analyzed the limitation of Ramanujan Graph in modeling irregular graphs (practical DNNs) at high sparsity, and propose to relax the assumption on the eigenvalue upperbound
-	The authors further proposed another metric to detect and avoid “trivial randomness” at high sparsity, by characterizing the same eigenvalue’s lower bound. 
-	Together, the authors demonstrate the novel finding, that a valid and desirable sparse NN architecture only exists when its graph adjacency matrix satisfies certain spectrum condition, e.g., its third-largest eigenvalue is both upper- and lower-bounded properly
-	The authors experimentally validated their findings on SOTA PaI methods including ERK, SNIP, and SynFlow. 


Weakness
-	The paper does not construct any new PaI approach, only observing how PaIs are correlated with their graph properties. It would be great if the authors could briefly share future insights of improvements.
-	Only CIFAR-10 dataset is used in experiments. I’d suggest the authors to report on 1-2 more datasets in order to make their empirical evidences more consistently convincing. 

clarity,_quality,_novelty_and_reproducibility: Clarity: very well written and easy to follow
Novelty: high (spotting important issues of Ramanujan Graph in analyzing PaI, which were overlooked before)
Reproducibility: seems good, but no code was submitted.

summary_of_the_review: Overall, I would tend to accept this paper. If the author can address my concerns. I would be more convinced.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: It is believed there should be a strong correlation between the Ramanujan graph and PaI since both are about finding sparse and well-connected neural networks. This paper digs deep and rigorously establishes their non-trivial relationships in fine-granularity, e.g., ranking of difference sparse structures at the same specific global sparsity.
strength_and_weaknesses: Strength
1.	This paper went beyond intuition and builds a new mathematical framework for understanding PaI. The differences from previous PaI studies (gradient- and graph-based) are clearly elaborated.
2.	This paper also went beyond simply pulling off-the-shelf Ramanujan graph metrics to analyze DNN architectures (like prior art did). Instead it did several important modifications tailored for irregular bi-graphs and high sparsity levels, both are demanded in the PaI situation.
3.	The authors are the first to identify a crucial limitation of Ramanujan property in analyzing irregular graphs, i.e., we could dismiss valid expanders due to the overly limiting requirements while retaining only graphs with random sparse-graph structures when analyzing high sparsity. They proposed a new metric called Iterative Mean Difference of Bound (IMDB) to mitigate the gap. This finding could be of independent interest to other applications where Ramanujan graph is relevant.
4.	The authors also highlight the danger of being overly expansive, which risks graphs deteriorating into randomness. They proposed a lower constraint to avoid the danger of randomness.
5.	Overall, the authors show the key knob to be relaxing the strong upper bound constraint on the third large affinity matrix eigenvalue µ(G), such that the resulting graph’s connectivity correlates strongly with its final performance. Further checking the lower bound for µ(G) could indicate whether a sparse structure deteriorates into randomness. Experiments align well with their theories.

Weakness
1.	I did not follow what differences the authors were referring to, between “trivial random sparsity” and “structurally meaningful masks”. What’s the criteria?
2.	Experiments are relatively limited. For example, only CIFAR-10 dataset is used as the testbed. Will the observations scale up to larger datasets? Also, could the authors find out whether some PaI methods can be obvious winners under their proposed metrics?

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The novelty is listed above. Experiments are straightforward (proof-of-concept level) and should be easy to reproduce. 
summary_of_the_review: See the strength and Weaknesses.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This is a very compelling paper that provides a valuable new perspective on pruning at initialization and its relation to graph connectivity measures. In particular, it proposes to interpret the (un)success of pruning neural networks at initialization (PaI) through the lens of the Ramanujan Graph – a renowned class of expander graphs that are sparse while being highly connected. While connecting expansive graph theory to NN architectures has been briefly studied before, this paper extended the depth of study much, by taking the pseudo-randomness and irregular bi-graphs in practical sparse NNs into account for the first time, as those may prefer “collapsed” naïve random or overly expansive graphs. After rebuttal discussions, all reviewers unanimously offer their strong support, and the AC fully echoes. Hence, it clearly makes a strong acceptance case.
justification_for_why_not_lower_score: From a rigorous graph theory perspective, the authors revised the fundamental limitation of Ramanujan Graph in modeling irregular graphs at high sparsity. They proposed two fixes, i.e., relaxing the assumption on the eigenvalue upper-bound, and meanwhile characterizing the same eigenvalue’s lower bound. Together, the authors demonstrate that a good sparse NN exists only when the spectrum of its graph adjacency matrix satisfies the upper- and lower-bounded conditions on the third-largest eigenvalue. 

Initially the experiments were only demonstrated on CIFAR-10, which some reviewers expressed concerns about. But after rebuttal the authors presented more experiments which add to satisfactory empirical credibility.
Decision: Accept: notable-top-5%