Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper revisits the Lottery Ticket Hypotheis (LTH), where aggressively pruning a neural network in a smart way allows it to retain its convergence properties, at a lesser computational cost.

The authors advance an explanation relating this LTH to expanders, graphs that have the property that information circulates really well between the vertices, and then to Ramanujan graphs. They then propose an algorithm built on this premise, that prunes the graph as long as the ramanujan property is still satisfied.

Finally, a wealth of experiments is shown, showing the relation between the Ramanujan property and the performance of the pruned network. The authors also test the performance of their Ramanujan pruning algorithm against the same datasets.
main_review: Strengths:
- as far as I know, the connection from the LTH to expander graphs is both novel and very interesting
- the exposition and algorithm definition are clear and easy to read
- judging from the provided experiments, the analysis seems to be well-supported by data

Weaknesses:
The main weakness is in the experiments section, which is very hard to parse. Problems include:
- very small graphs requiring constant zooming in and out, especially since some curves are only distinguished by line and marker style
- too many curves per graph, some being borderline unreadable (e.g. Figure 5.d)
- the color schemes are confusing: the same colors are used for distinguishing Lenet layers (Figure 3.a, b) and noise levels (Figure 3.c)
- the loss of the ramanujan property should be present on the testing accuracy graphs
- the legend scheme for the curves should be explained more clearly: as of now, they are quite hermetic and require good knowledge of the studied networks' architecture.

Remarks:
- in some cases (e.g. below Figure 1), $p$ switches between the proportion of edges pruned and the proportion of edges kept
- I understand why you wouldn't want a rigorous definition of a universal cover, but you should add a reference
- the theory of Ramanujan graphs is only stated for positive weights, yet this is not the case for neural networks: how is the ramanujan bound defined?
- typo below def. 3: it is the Alon-Boppana theorem
summary_of_the_review: The idea of the paper is novel, interesting, and clearly exposed. However, a wealth of clarity issues in the experiments section hinder the clarity of the paper overall.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The work proposes to utilize the spectral gap of the bipartite network connectivity graphs between neural network layers to terminate an iterative weight pruning algorithm.
main_review: 
Strengths:
- The paper builds upon a nice premise by introducing expander graphs to describe connectivity between neural network layers.
- Choosing the pruning termination criterium based on on the extended spectral gap (Algorithm 1) is a good idea and novel to my knowledge.

Weaknesses:
- The experiments are not able to convince me that the chosen bound leads to good pruning results. In some experiments they seem to fit, in others they do not.
- There is also no solid theoretical justification, why the termination criterium should fit (except for the already known correlation between the spectral gap and density).
- The work is lacking comparisons to previous pruning methods, showcasing the usefulness and significance of the proposed algorithm.
- The experiment section is confusing (see below)

Issues in Experiments section:
- I have trouble following the figures. The labels in the figures are not consistent with the names in the text (lambda vs t, L1-L3 not defined). Minor: the figure labels are way too small.
- UE, UD, WE, WD only defined in a Table and the text is lacking clear discussions and conclusions for the results in the different scenarios.
- It would help alot if the test accuracy figures would show the point in which Algorithm 1 would stop the pruning.
- If I understood correctly, it should be easy to apply Algorithm 1 to the networks and present the resulting test accuracy in comparison to previous pruning techniques. However, that is not done.

summary_of_the_review: All in all, while I like the general idea of utilizing spectral graph information of bipartite network connectivity graphs for pruning decisions, I find the paper is lacking a clear message and the required experimental evidence to back it up. There are no comparisons to previous pruning techniques, which would allow to showcase significance. Therefore, I tend to vote for rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors state the hypothesis that the Ramanujan graph property is necessary or at least beneficial for pruned networks to serve as lottery tickets. Motivated by this claim, they propose a stopping criterion for iterative magnitude pruning, which is based on the two largest eigenvalues of the weight (or adjacency) matrices of neural networks and should (approximately) preserve the Ramanujan graph property. 

main_review: While the connection of Ramanujan expander graphs to lottery tickets is interesting, the experiments are not convincing and leave doubt that this is even a relevant property for network pruning. The practical relevance of the stopping criterion is doubtfull. Detailed points of critique follow below.

Strengths:
+ The idea to measure the potential of a pruned network to serve as lottery ticket based on the eigenspectrum is novel and interesting.
+ The idea that the Ramanujan graph property could be beneficial for sparse network structures could be also useful (but this remains open to show). 

Weaknesses:
- The introduction into Ramanujan graphs is lengthy and only motivational, as the results on maximality hold only for regular graphs and not for the lottery tickets (which are usually irregular).
- The authors claim that they introduce a new pruning algorithm, while in fact they only propose a stopping criterion for iterative magnitude pruning (IMP), which requires the repeated computation of the two largest eigenvalues of potentially large weight matrices. The original IMP is computationally expensive already, which leaves the question what the added value of the eigen-bound based stopping criterion should be?
- As a stopping criterion for pruning, it is not relevant, as the validation set performance (or even training set performance) is in fact more indicative.
- Is the contribution should be the insight that graphs with the Ramanujan property are better suitable as lottery tickets than other structures, I would expect different experiments that test this hypothesis. 
For instance, I would expect that random graphs are sampled or otherwise constructed that have comparable properties (like density, degree distribution, flow preserving, etc.)
which either have the Ramanujan graph property or not (but are otherwise comparable). Or through rewiring of edges the Ramanujan graph property can be gained or lost...
For both these sets (Ramanujan or not) one could then test whether they are suitable lottery tickets (or at least preserve information flow).
- For real practical impact, I would then expect an algorithm that repairs a pruned network to gain back the Ramanujan graph property (by edge rewiring that preserved the overall network density) and then would want to see experiments that suggest a superior performance of this pruning algorithm with repair.
- Different from the made claims, the Figures 3, 4, 5 do not even seem to indicate a strong link between the loss of the Ramanujan graph property and a loss of accuracy.
I would expect to see a sharp phase transition and complete loss of network accuracy at the point where the Ramanujan graph property is lost if the made claims were true.
- Or is simply the connectivity of the graph the relevant property?
I would expect at least a comparison with methods like Synflow or layerwise pruning approaches that try to prevent layer collapse and preserve information flow through the network or orthogonal repair as in "A Signal Propagation Perspective for Pruning Neural Networks at Initialization", ICLR 2020.

Points of minor critique and open questions:
- Definition 3 for irregular graphs: Two replacements of the same quantity (the regularity r) are proposed, which is contradictory in this form. This could be explained more precisely.
- Multiple symbols, abbreviations, figure legends, etc. are nowhere defined. For instance, \sigma shall probably refer to the standard deviation of the applied Gaussian noise?
- Figure 7: It is impossible to compare which pruning algorithms perform best. They all look very similar.
- No error bars are reported anywhere.

summary_of_the_review: As the merit of the proposed eigen-bound based pruning is unclear, I believe the work is not suitable for publication at ICLR in this form.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors study the properties of the subnetworks in lottery ticket hypothesis (LTH) from the perspective of the spectral graph theory.
They argue that the pruned network in LTH remains a Ramanujan graph.
The performance of the subnetworks begins to degrade with the loss of Ramanujan graph property.
To this end, they propose an eigen-bound based network pruning algorithm to preserve the graph property.
Extensive experiments are conducted to demonstrate the effectiveness of the proposed method.
main_review: **Pros**: The proposed pruning method is based on the spectral graph theory, which is novel and interesting.

**Cons**:
1. **Significance of the method**.
    - What is the practical significance of the proposed pruning method in this work? 
    - Whether the proposed method can effectively improve the pruning performance, such as alleviating the performance degradation? 
    - Whether the winning lottery ticket can be found more effectively?
    -  For pruning the neural network, what is the significance of robustness against the noise in the dataset? Maybe we should focus on pruning instead of robustness.

2. **More comparisons are needed**.
    -  This paper does not show the performance of other state-of-the-art pruning methods, such as IMP or gradient-based pruning.
    -  How robust are other pruning methods to noise?
    -  Authors should also make more ablation studies to demonstrate the roles or impact of different components of the proposed method.

3. **Other issues**.
    -  The experiment section in this paper is too single. The results shown in Figures 3, 4, and 5 are all similar, except that different datasets and models are changed.  This section should include more important results to demonstrate the proposed arguments. Please put the insignificant results or curves to the appendix.
    -  The experiment section frequently shows the curves of eigen factors. What does this indicate? What kind of enlightenment does this changing trend provide us?
    -  Why does the proposed method establish robustness against the noise?
summary_of_the_review: In general, the paper is well written. I hope the authors should first answer the aforementioned questions cautiously and carefully.
review_title: null

Meta-review: Dear Authors,

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

In particular:

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

Best AC
Decision: Reject