Towards Data-Agnostic Pruning At Initialization: What Makes a Good Sparse Mask?
Authors: Hoang Pham
The-Anh Ta
Shiwei Liu
Lichuan Xiang
Dung D. Le
Hongkai Wen
Long Tran-Thanh
Venue: NeurIPS 2023 poster (2023)
Keywords: Pruning Neural Network
Sparsity
Neural Architecture Search
TL;DR: Our paper gives new perspectives on pruning at initialization from the configuration of subnetwork (particularly effective paths and nodes) to better design pruning algorithms.

Abstract: Pruning at initialization (PaI) aims to remove weights of neural networks before training in pursuit of training efficiency besides the inference. While off-the-shelf PaI methods manage to find trainable subnetworks that  outperform random pruning, their performance in terms of both accuracy and computational reduction is far from satisfactory compared to post-training pruning and the understanding of PaI is missing.  For instance, recent studies show that existing PaI methods only able to find good layerwise sparsities not weights, as the discovered subnetworks are surprisingly resilient against layerwise random mask shuffling and weight re-initialization.
In this paper, we study PaI from a brand-new perspective -- the topology of subnetworks. In particular, we propose a principled framework for analyzing the performance of Pruning and Initialization (PaI) methods with two quantities, namely, the number of effective paths and effective nodes. These quantities allow for a more comprehensive understanding of PaI methods, giving us an accurate assessment of different subnetworks at initialization. We systematically analyze the behavior of various PaI methods through our framework and observe a guiding principle for constructing effective subnetworks: *at a specific sparsity, the top-performing subnetwork always presents a good balance between the number of effective nodes and the number of effective paths.*
Inspired by this observation, we present a novel data-agnostic pruning method by solving a multi-objective optimization problem. By conducting extensive experiments across different architectures and datasets, our results demonstrate that our approach outperforms state-of-the-art PaI methods while it is able to discover subnetworks that have much lower inference FLOPs (up to 3.4$\times$). Code will be fully released.

Towards Data-Agnostic Pruning At Initialization: What Makes a Good Sparse Mask?
Hoang Pham', The-Anh Ta², Shiwei Li Lichuan Xiang', Dung D. Le², Hongkai Wen', Long Tran-Thanh' FPT Software Al Center, CSIRO's Data61, University of Texas Austin, 4 University of Warwick, 5 VinUniversity Eindhoven University of Technology hoang, pv1602@gmail........mmmmm.m....m com, theanh. ta@csiro. au, {L. Xiag.. 2, Hongkai Wen, Long. Tran Thanhh@wwawwihe ac.uk dung. ld@vinuni edu. vn, shiwei. liu@austin. utexas. edu
Abstract
Pruning at initialization (Pal) aims remove weights of neural networks before training in pursuit of training efficiency besides the inference. While off-the-shelf Pal methods manage to find trainable subnetworks that outperform random prun- ing, their performance in terms of both accuracy and computational reduction is far from satisfactory compared to post-training pruning and the understanding of Pal is missing. For instance, recent studies show that existing Pal methods only able to find good layerwise sparsities not weights, as the discovered sub- networks surprisingly resilient against layerwise random mask shuffling and weight re- re-initialization. In this paper, we study Pal from a brand-new perspective the topology of subnetworks. In particular, Pal methods with two quantities, namely, the
propose a principled framework
for analyzing the performance number of effective paths and effective nodes. These quantities allow for more comprehensive understanding of Pal methods, giving us an accurate assessment of different subnetworks initialization. We systematically analyze the behavior of various Pal methods through our framework and observe guiding principle for constructing effective subnetworks: at a specific sparsity, the top-peryy op-performing subnetwork always presents a good balance between the number of effective nodes and the number of effective paths. Inspired by this observation, we present novel data-agnostic pruning method by solving multi-objective optimization problem. By conducting extensive experiments across different architectures and datasets, our results demonstrate that our approach outperforms state-of-the-an Pal methods while able to discover subnetworks that have much lower inference FLOPs (up to 3.4 3.4x). Code is available at: https:: //gi thub. com com/pvh1602/NPB
Introduction
Deep neural networks have achieved ofate-of-the-ar art performance wide range of machine learning applications 13, 39 38) However, the huge computational resource requirements limit their applications, especially in edge computing and other future smart
systems [3] 48 37
27
To overcome this issue, number of approaches have been proposed to reduce the size of deep neural networks without compromising performance, among which pruning has received voluminous attention 100
24 g Traditional pruning approaches mainly focus on accelerating inference, which
usually require a pre-trained dense network (33 20 31].
As large language models (LLMs) 3
continue to gain popularity, endeavors start to explore the possibility prune models before training while matching the dense performance. Lottery Ticket
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Hypothesis (LTH) [1 4 5 provides empirical evidence for this research goal by discovering sparse subnetworks that can be trained from scratch to the comparable performance of the dense network. However, LTH typically involves the costly iterative pruning and re-training process, whose overall cost much more than training a dense network.
This issue raises an intriguing research question: How to identify sparse, trainable subnetworks at initialization without pre-training? Specifically,, a successful pruning before training method can significantly reduce both the cost of memory and runtime, without sacrificing performance
much [46]. This would make neural networks applicable even in scenarios with scarce computing
resources [ 47 As such, many methods for Pal have been proposed (26 42
9 45
I 29]. While
these methods are based on number of intuitions (e.g., leveraging the gradient information [2] (45)
they typically measure the importance of network parameters. Their performance in terms of both accuracy and computational reduction is far from satisfactory compared to post-training pruning and the understanding of Pal is missing. More recently, Frankle et al. [17], Su et al. 40 observe rather surprising phenomenon: for Pal methods, layerwise shuffling connections of pruned networks does not reduce the network's 's performance, which suggests that layerwise sparsity ratios might be more important than weight-level importance scores. This indicates that in searching for good subnetworks at initialization, the topology of subnetworks, particularly, the number of input-output paths and active nodes, plays a vital role and should be investigated more extensively.
In this paper, we first present a counter-argument against the previous findings: while Frankle et al. 17 show that Pal methods are insensitive to random shuffling, we find this is not true the extreme sparsity regime (> 99%), as the number of effective paths heavily suffers from random shuffling. In layerwise shuffling experiments (see Section (.3), shuffling connections results in more effective nodes but substantially fewer input-output paths. In normal sparsity levels, shuffling weights in regular sparsities can maintain and even increase effective parameters [17] and the number of activated nodes (36). This increases representation capacity and performance of the subnetwork. However, at extremely sparse levels, shuffling still preserves roughly the same number of effective nodes, but the performance of shuffled subnetworks drops significantly compared to their unshuffled counterparts. This is because random weight shuffling damages effective paths and hampers information flow within the subnetwork. These findings suggest that separately considering effective paths or nodes is insufficient to fully capture the behavior of subnetworks generated by Pal methods.
To underscore the critical importance of nodes and paths designing network architecture, we conduct analysis of their quantities in the
Architectures with parameters 2150K-2450k
The number of eeeective pathrilog (1ogg-00g zato
92
context of Neural Architecture Search (NAS).
For instance, Figure [ illustrates the relation- ship between candidate's 's performance, nodes and paths in NAS- BaS-Bench-MMcro [41] which has 6, 561 models (more in Section To ensure faimeess in terms of model size, we compare networks with similar number of parameters (i.e., in a range of 300k parameters in Figure I). Remarkably, architectures exhibiting a higher number of input-output paths and active neurons concurrently yield superior performance. This highlights the crucial role of simultaneously con- sidering both node and path in the successful design of networks at initialization.
550
46
40
35
9.25
9.10
9.35
9.60
9,65
5.50
9.55
The number of offective nodos (In scolc)
Figure 1: The accuracy of architectures in NAS- Macro benchmark along with the number of effective nodes and paths.
To improve upon the current understanding of Pal methods, we introduce a novel framework from the perspective of subnetwork topology to provide more accurate and comprehensive explanation of the performance of different approaches. In particular, we propose the joint usage of both the number of input-output paths (a.k.a. effective paths) and activated (i.e., effective) nodes interpret behaviors of different Pal methods in a more comprehensive way (see Section 3.3 for more details). Inspired by the guiding principle observed through our framework, we further introduce NPB, a novel pruning at initialization by solving a node-path balancing objective. We show that NPB outperforms state-of-the-ad -hrerrrrttrrt Pal methods in almost all settings, while achiveing much lower inference FLOPs. In summary, our main contributions are:
2

---

We propose unified effect node- path perspective to understand the behavior of Pal, particu- larly considering metries of effective nodes and paths as proxies for the performance of Pal methods (Section] 3). We revisit the layerwise shuffling sanity check on Pal methods and provide unified explanations for their behaviors based on these metrics in a wide range of sparsities (Section 3.3
We discover new relation between the proposed metrics and the performance of sub- networks, termed the Node-Path Balancing Principle, that suggests a non-trivial balance between nodes and paths is necessary for optimal performance of Pal (Section 4
We present a novel data-agnostic pruner, NPB, by solving multi-objective optimization problem to give a proof-of-coneep for our principle. With extensive experiments, we show that NPB outperforms the best sate-of-the-an Pal methods, PHEW, on 11 out of 12 settings while ours produces more efficient subnetworks with much fewer inference FLOPs (up to 3,4x) and faster in pruning time than PHEW (up to 14.5x) (Section
2 Related Work
Neural Network Pruning. Neural network pruning methods (25 21 20 12 32 traditionally focus on pruning trained models based on pre-defined criteria, and then resulting subnetworks will be fine-tuned to converge. Recently, [15] 16 4 5 empirically show the existence of randomly initialized subnetworks (lottery tickets) which when trained from scratch or in early training iterations, that can achieve competitive performance with their dense counterparts. Unfortunately, finding lottery tickets is computationally expensive due to the train and prune cycle [16] 13). Gradual pruning methods [4] interleave the pruning and training, which are usually cheaper than pruning after training. but the network still needs to be trained to choose the ideal sparse subnetwork. Other methods 6 7 apply one-shot pruning during training to further reduce the computational cost. 28 27 on the other hand, start with (random) sparse network and update network connectivity during training. While pruning before training methods [26 45 36 [
Dynamic sparse training 30 14
determine subnetworks by the network initialization, gradient information, and network topology. However, experimental results done by Frankle et al. [17]. Su et al. [40] show that current criteria of PaI methods may not be sufficient obtaín a subnetwork with good performance.
Pruning and Network Shape. Since Pal methods do not utilize training data 442 36) use only negligible portions of data [26 45 to obtain gradient information without training, the configuration of nodes and connections is essential source of information for optimizing the performance of pruned networks. It turns out that some Pal methods implicitly optimize certain aspects of network preserves the number of input-output paths synaptic strength,
shape. In particular, SynFlow but often creates more isolated neurons in pruned networks. The works of Patil and Dovrolis (36) and Gebhart et al. [19] aim preserve proxies in terms of path kernels which are also directly related to the shape of subnetworks. Furthermore, while PHEW (36) additionally implements random walks to increase the number of effective nodes, it unintentionally decreases the number of input-output paths. Our new point of view on node-path balancing would be helpful to systematically optimize network configuration for better performance. Other works also consider the number of effective nodes and effective paths to capture the capacity of pruned subnetworks 45 are considered separately.
22
34 where these numbers
3 Methodology
3.1 Pruning at Initialization Methods
Given L layer neural network, we denote w (Wi...., WL) as the set of vectorized weights. Pruning generates binary mask vectors my E (0, 11dt (dN is the number of connections in layer f) yielding sparse neural networks with sparse weights m, W/ the elementwise product of masks and weights Sparsity is defined the fraction of weights being removed: s 1 2 E [0, 1].
Ede
A pruning method usually consists of two operations: score and remove, where score takes as input weights of the network and outputs an important score for each weight: ž = score(wr) E Rí; then remove takes as input the scores z = (ZI....,Zy) 21) and the sparsity and outputs the masks my with
3

---

overall sparsity s. Pruning can be done in one-shot or iteratively. For one-shot pruning, we only generate the scores once, then prune the network up to sparsity s. For iterative pruning, we repeat the processes of the score, then prune from sparsity 50-1)/ to s/r repeatedly 7' times.
Random.
This method assigns each connection with random score from uniform distribution U(O, 1). Random pruning empirically prunes each layer to target sparsity [29].
SNIP. SNIP was introduced by Lee et al. [26 with the pruning objective of reducing connection sensitivity to the training loss. One passes a mini-batch of data through the network and computes the score for weight of SNIP as |w O W..
Iterative SNIP. This is an iterative variant of SNIP
p with the same important score. But, iterative
SNIP gradually prunes the remaining weights with lowest scores from sparsity s to sparsity s iteratively T times for / I.
SynFlow. SynFlow
is an iterative and data- aata-agnostic Pal method. The pruning objective of SynFlow is to make the network remains connected until the most extreme possible sparsity. The weight scores are computed follows. One first replaces all weights the network by their absolute values. Then, an input tensor is passed through the network, and one computes the sum of the logits as R 1T (T [wr)). Finally, the score of weight computed as z |w W R. SynFlow prunes the network iteratively 7' times.
PHEW. PHEW 33) is also an iterative and data-independent Pal method. selects set of input- output paths to be preserved. These paths are chosen through random walks, biased towards higher- weight magnitudes. The selection starts with unit that selected through round robin procedure. This process continues until the subnetwork achieves the predefined sparsity.
ERK. Erdōs-Réón Rényi (ER) first used by Mocanu al. [30] to sparsify Multilayer Perceptron (MLP)
networks using a random topology that allocates higher sparsity to larger layers. Evei et al. [14] extends ER to convolutional version called Frads--ééni-KKemed (ERK) which scales the sparsity of the convolutional layer in proportion to the number neurons/channels in a layer.
3.2 Metric Definition
5
6
0.0
0
0
0
0
0
0
0
0
0 0
0
Effective node
Ineffective mode
Pruned mode
Effective path
Figure 2: An example of effective paths and effective nodes.
In sparse network, is intuitively clear that one should arrange the connections into a configuration neither too thin nor too spread-out to have good information propagation during training. For a better measurement, we propose using two metries to evaluate the quality of subnetworks. Please refer to Appendix for detailed discussions and Python code for calculating the metrics.
Effective Path. We define path to be effective if it connects input node interruption (see Figure 2 Metrics based on paths are mentioned in [42 19 as I and /2 path norms, respectively. In this paper, we only take into account the number of paths.
output node without
Effective Node/Channel. A node/channel is effective at least one effective path goes through it (demonstrated the right part in Figure 2). This concept is also considered in [36] [7]. For convolutional layers, we consider a kernel as a connection, and a channel as a node, and then convert the convolutional layer into fully connected layer (see the left part in Figure 2
3.3 Layerwise Shuffling Phenomenon
In this section, we investigate the intriguing phenomenon that layer-wise reshuffling the subnetwork found by Pal methods still produces competitive accuracy [1 40). Based on metrics, provide

---

SNNP
20.00 20.00 5064
55.00 53.44
53.06
00.02
08.50
08.38
50.00
9004
55.06
00.44
90.50
19.00
90.00
00.30
33.8
50334
90.00
53.44
55.03 59.02 55.50
1.0
SynF
00.22 P21E Milt 2A.0 1697
13.00
18.28 5322 sa51 sEAce 15.00
$6.00
16.55 Aidt PARI 1A32
1850
131
NC. 9131
1939
18:38
10.00
100
99.93
91ST TE4E BESE 5932 19.55
Figure 3: Layerwise shuffling results on various sparse subnetworks ResNet20 produced by SNIP, SynFlow, and PHEW CIFAR-10.
new way to understand why reshuffling subnetworks work and when they fail. We first use three Pal methods, i.e., SNIP (26). SynFlow [42]. and PHEW [36), to find the subnetworks. Then, we randomly shuffle the pruning mask my. All the subnetworks (both unmodified and shuffled) are trained same setting. Finally, compute the ratio of the number of active paths and nodes after and before pruning and visualize the average scores Figure
In SNIP and SynFlow, the number of effective nodes drops significantly as sparsity increases (blue lines second columns Figure B). After reshuffling. the connections are distributed uniformly in each layer leading to wider subnetworks while the number of effective paths decreases. In contrast, PHEW focuses on increasing the number of effective nodes by gradually adding new paths such that the network is as wide as possible. Consequently, reshuffling hurts the concrete network configuration and then reduces both the number of effective nodes and effective paths as sparsity higher.
At sparsity levels below 99%, layerwise shuffled subnetworks demonstrate competitive performance even better than unmodified counterparts, especially with SynFlow and SNIP. In addition to effective connection preservation as discussed in prior work (17), the representation capacity of shuffled sparse networks is enhanced with SynFlow and SNIP, attributed to the increase in the number of effective nodes [35] while maintaining considerable input-output paths. In more details, Figure shows that these two metrics for SynFlow and SNIP shuffled versions closely resemble to unmodified subnetworks of PHEW with corresponding sparsities.
However, when the network becomes substantially (along with the reduction of effective parameters see Appendix D). Even though layerwisely shuffled networks become wider, the limited number of effective paths damages the information flows in the subnetworks. These explain why the accuracy of shuffled subnetworks is reduced significantly compared to the unmodified ones in intensive sparsities.
sparse, the number of onput- paths decreases
These observations indicate that increasing the number of active paths or nodes alone might not be sufficient in the design of Pal methods. We hypothesize that to have good subnetworks, the number of effective paths and effective nodes should be concurrently considered. we balance these two metrics well, the performance after the training of subnetworks will be enhanced.
3.4 NAS Observations
Our research delves into the fundamental aspects of network architecture design by investigating the interplay between nodes and paths. Going beyond the realm of pruning literature, we conduct an analysis of node and path metrics in the NAS benchmark. NAS are dense networks. In particular, we focus NAS-Bench-Macro [41. macro benchmark comprising 8 searching layers. Each layer offers three candidate blocks, resulting in a staggering 6,561 distinct networks with parameter counts ranging from 300k to 3M. To ensure a fair comparison
noteworthy that networks in
5

---

among candidates, we specifically consider networks with similar parameter counts within the 300k range. We compute metries across four different parameter ranges and visualize them Figure
In the context of NAS, it's important to consider that other aspects beyond node-path balance can contribute to final classification accuracy. For instance, in the case of MAS-Bench-Macco,, net- works with similar node-path balance but vary- ing classification accuracies can affected by other architectural configurations, such as differ- ences pooling layers, kernel sizes, and expan- sion ratios in the MobileNet-v2 block. These architectural variances often result in different numbers of parameters, influencing the overall network performance. However, the sparse neural network context, pruning methods focus on maintaining the same network structure while pruning connections within the network based on specific sparsities. Consequently, our exper- iments did not explore other architectural ele- ments beyond node and path balance. In general, can that networks with larger numbers of nodes and paths tend exhibit higher performance. Our findings unveil a strong correlation between the two metrics (node, path) and the final performance of network candidates, both playing pivotal roles in achieving superior performance. This highlights the critical significance of both nodes and paths in the initial stages of designing subnetworks that yield exceptional results.
eparamiterrs CSBl 653c
#caramaterr 952x1356k
epu aomarr 1250k 3052k
#porumbers
33
13
Figure 4: The accuracy of network candidates in -AS-Bench-Macco benchmark along with the number of activated nodes and paths in different parameter ranges.
4 Node-Path Balancing Principle
4.1 Node-Path Balancing Principle
From observations in Section 3.3 and NAS observations Section 3.4 both effective paths and nodes have shown their critical roles in the performance of subnetworks. We now formally state the Node-Path Balancing Principle (NPB): The combination of both the numbers of effective nodes and effective paths is a proxy for the potential performance of subnetworks under pruning. A pruning initialization method which produces pruned subnetworks with too many effective paths (resp. effective nodes) will have less than necessary the number of effective nodes (resp. effective paths) and consequentially has suboptimal performance. is necessary to balance the number of effective nodes and effective paths for better performance of pruned subnetworks.
4.2 Proposed Method: NPB
Building upon the aforementioned principle, we elegantly transform the pruning problem into multi-objective optimization problem. Specifically, our objective is to maximize both the number of effective nodes and effective paths concurrently given architecture and desired sparsity ratio. We formulate this intriguing problem as follows:
Given an architecture A with parameter W e R where N is the total number of parameters and sparsity ratio Denote fp as the total number of input-output paths, fa as the number of activated nodes, and consider the mask for parameter M {0, 1P" as variable solve.
Maximize M
a + a)
s.t [M]] s N(1 -)
where is coefficient. Solving node-pati path balancing objective globally over the whole neural networks non-trivial problem. We sidestep this challenging issue by solving a sequence of easy problems to obtain good approximated solutions. In particular, we propose an approximation for solving this problem by doing layer by layer through convex optimization. The approximation problem is solved efficiently via the available convex optimization library.

---

To be simple, we consider a linear layer as an example, in which, v denotes the node, / is the layer index, m "d"""" is the mask for layer / in which 4 the number of neurons in layer I. We denote P(v)") the number of path go to node V; in layer I (e.g., at input layer )(r = 1). We formulate the pruning problem in layer as an optimization problem in which we maximize the number of paths from input to layer ++1 fp and the total activated nodes fn ((l-1) in two layers and /+ 1. For brevity, we denote them as fp and fa. We set m as:
{
if pruned
if not pruned
The number of paths to ((+1)) layer [+1 is sum of all paths to nodes in layer connecting to v/-t)
4a
P(
P(
mi 19
P(
Then the total number of effective paths to layer 1 is:
N4+1) fp(m) = P(oftin
(1)
A node in layer / is activated if and only if there are paths pass through it and edges connect from it to nodes in layer + 1, which is formulated as below:
Allll
W
P(
Σ
my
I e min(P()))
Σ
m 1)
And node v, in layer ++ 1 is effective when there exist attached nodes in layer / that connect to it,
60
mm
1 e min( f m 1(,
The layer-wise objective for the node becomes:
1! fi(m) Σ min(P() (
N
Σ min Σ mi m P(("):1)
1)+
(2)
In convolution layers with kernel of height h and width w, let the variable m, have the value from 0 to hw representing this kernel. After solving m, in each kernel, we assign (myl parameters to entries whose initialized weights have the highest magnitude.
Along with two objectives, we also consider a regularization term which aims to encourage activating many kernels as possible in each layer. Besides, since optimize the node and path per layer, the solution will not be the global one. We can view the regularizer as an adjustment term, which moves the local solution around to figure out the better ones.
R ΣΣ min(m - 0)
(3)
From Equations 2 and 3 the final objective becomes:
Maximize mll af (1 (1-a)fp BR
(4)
S.f |lm (lmh s (1)
(5)
where a is a coefficient to control the balance, B is a hyperparameter, and the constraint is the number of unpruned parameters that satisfies the sparsity. To ensure the same scale hetween elements in the main objective function, we normalize the number of paths, nodes, and the regularizer in each layer with their maximum possible values, respectively. Note that, optimizing nodes much easier than paths so we select small values of alpha which can be prior knowledge. In particular, in Section [ we fix 0.01 and 3 to all settings. We optimize I the network structure sequentially layer by layer from input to output in which the layer-wis sparsity level is found by ERK method [14, 29]. We describe our method in Algorithm [ and the pseudo code for optimizer Appendix C
We use the default mixed integer programming solver in CVXPY library
7

---

Algorithm 1 Node-Path Balancing Pruner
1: Inputs: Final sparsity S, weights Wo = 1, balancing coefficient a, and hyperparameter B
2: Obtain layer-wise sparsity , by using ERK method
3: Define unit input x = pib
4: for I O..... do
m optimize(m 50h p0) solve Eq
6: Set w m
7: Extract layer + output when put x to the network with wo to obtain pi+t))
8: end for
9: Return: Mask M
5 Evaluation
5.1 Experimental Settings
We conduct experiments three standard datasets: CIFAR-IO. CIFAR-I00, and Tiny-Imagenet. Following 42). we use ResNet-20 for CIFAR-10, VGG-19 for CIFAR- 100, and a variant ResNet-18 with 18 layers for Tinyeemagenet. We treat weights of all convolutional and linear layers as prunable, but we do not prune biases and weights in batch normalization layers. We run five seeds with experiments on CIFAR-10, CIFAR- 100, and three seeds on used for visualizations. Since the number of active paths is orders of magnitude larger than that of active nodes, and both numbers are of exponential scales, we take logarithm base 10 of the number of active paths, and logarithm base e (natural logarithm ) of the number of active nodes to visualize the results. To ensure the fair comparison between NPB and other baselines, we fix a 0.01 and B = in NPB for all settings. More details our experimental setting are in Appendix A
The average results are
35%
Sporsity
84%
RosNet21 en CIEAR-10 etweeteeeteeooo poth
AU.55
$1.95
15:44
VGG19 CIFAR-100
11.11
36
15T
14
7/5
Muroor of aheccive eode
Rurber (ithdhereee roder 31 3o
Numzer offect (raodl
Number whhthh nece: (1acena
ResNeel8 on Thoy- Amagenet
Sparsity 68.3%%
Sparsity 90.00%
Sparsity 56 66.8
Sparsity 59.00%
www.ectcee patta pug
45.
2.
310
122
16
14
532 4.% 130 235 24 #33 475 51d
Figure 5: The number of effective paths (log scale), nodes (In scale), and the corresponding accuracy of different Pal methods on three datasets in different sparsity levels. Best accuracy is in blue.
5.2 Comparison with Pal Methods
SigureBishow the experimental results for different Pal methods: Random, SNIP, Iter-SNIP, SynFlow, PHEW, and our NPB, with different sparsities on three settings: VGG-19 on CIFAR-100, ResNet- 20 on CIFAR-10, and ResNet- 18 on Tmay-em Overall, our method NPB shows significant improvements standard Pal methods, both data-dependent like Iter- SNIP (improve up to
8

---

14%) and data- intepeendeeendntt like SynFlow (increase up to 7%) in all three settings. Notably, NPB achieves better results than state-of-the the-art Pal method PHEW in almost all settings (11 out of 12 settings). Importantly, we set the same alpha and beta kyperparameters for NPB across all three settings, thereby eliminating the need for extensive hyperparameter search. This demonstrates the robustness and generalizability of our method, making it easily applicable to various settings with consistently high performance. Ablation studies on alpha and beta can be found in Appendix [
We discuss the experimental results from the point of view of the Node-Path Balancing principle and network shape optimization. In Figure SynFlow and Iter-SNIP produce sparse networks with large number of input-output paths, which results from iterative pruning procedures. These methods gradually remove nodes of low connection degree, which makes the subnetworks become narrower while maintaining the high number of paths. As a consequence of a very high number of input-output paths, the width of resulting subnetworks is significantly reduced, limiting the representation capacity of the subnetworks R5 36). leading to suboptimality.
Random pruning is a Pal method which produces subnetworks with the very high number of active nodes. On average, it distributes parameters uniformly to all layers and kernels, creating subnetworks of large width yet low number of active paths. At sparsities below 90%, with an adequate number of input-output paths, subnetworks of Random pruning still perform well and are even competitive with more sophisticated Pal methods. This phenomenon is exhibited clearly in experiments on the more complex dataset Tiny- -magenet. However, when sparsity increases over 90%. Random pruning creates a huge number of ineffective paths and parameters. Consequently, the performance of subnetworks drops significantly. We again observe the necessity to balance the optimization of the number of nodes and paths.
In Figure 5 our method NPB and PHEW produce sparse networks which, in visualization, lie in specific areas which have higher paths than Random and greater nodes than SynFlow, or Iter-SNIP. We call these are balancing regions. Subnetworks in these regions have broader widths and considerably many paths, which provides good representation capacity and preserves the information flow of the network. These two factors together contribute to better training of pruned subnetworks leading to superior performance. This illustrates the effectiveness of our principle.
One drawback of one-shot pruning methods like SNIP is creating a large number of ineffective parameters, which decreases the capacity and performance of subnetworks. Although our method is also one-shot, it efficiently distributes the parameters by direct optimization. Consequently, NPB enjoys better node-path balancing level and better performance (up to 14%) compared to SNIP.
Results of all settings in Figure 5 evidence to support our Node-Path Balancing principle and the existence of specific balancing region between nodes and paths at given sparsity levels. Particularly, we posit that when the number of active neurons and input-output paths of a sparse network fall within this balancing range, it will probably have good performance after training.
5.3 Pruning Time and FLOPs Reduction
Table 1:
Accuracy, pruning time (in seconds) and FLOPs of subnetworks for different pruning methods and compression ratios on Resnet18 - -mage-ma
Accuracy (5)
Pruning time (scconds)
FLOPs (10*)
Sparsity (8)
68.38
90.00
96.84
99.00
68.38
90:00
96.84
99.00
68.38
90.00
96.84
99.00
SNIP
56.99
53.43
48.77
36.02
5.14
4.95
5.55
5.64
11.35
5.77
3.04
1.55
Iee-SNIP
56.73
53.60
48.55
36.42
229.16
235.34
233.19
231.23
10.73
7.05
3.98
1.9
SynPlow
56.71
54.68
49.03
39.79
108.17
96.18
91.15
92.60
14.71
8.91
4.24
1.50
PHEW
58.09
55.93
50.81
40.54
5511.20
1342.03
471.23
324.78
14.29
8.35
3.92
1.50
NPB
58,39
56.82
51.37
41.05
380.52
375.65
384.32
387.89
14.37
5.21
1.74
0.59
Since NPB optimizes layer by layer, the complexity of NPB depends on network architecture (i.e., the number of layers and the size of each layer). With large layers, we sidestep the time-consuming issues by making a further step where we divide the layer into chunks with the same sparsity constraint. In particular, we split nodes in the next layer into equal parts while the input node is fixed. Then, optimizing chunks in layer can be solved in parallel. Thank to the available convex optimization libraries we can find subnetworks more efficiently and quickly. We have computed the pruning time of our proposed method and compared it with other Pal methods in Table T Our pruning time is not

---

significantly slow compared to those iterative approaches (e.g., Iter-SNIP, SynFlow) while it is much faster (up to 14.5x) than PHEW in lower sparsity levels.
Besides pruning time, we find that the FLOPs reduction of subnetwork after pruning is more important in the context of pruning before training. We have measured FLOPss of subnetworks produced by different methods in Table[] The result indicates that our NPB can produce subnetworks with lower FLOPs than other baselines while NPB outperforms Pal methods. More details are in Appendix
6 Conclusion
In this paper, we present a novel framework for studying Pal methods that systematically employs the configuration of pruned subnetworks based on two different metrics: the number of effective paths and the number of effective nodes. Through our framework, we discover a new relationship between these metrics, called the Node-Path Balancing Principle, which provides guidance for understanding and optimizing Pal methods. Our framework offers unified explanations for the intriguing layerwise connection reshuffling phenomenon 40 I7 of subnetworks produced by Pal methods in normal pruning sparsity regime, as well as the failure of this phenomenon in extreme sparsity levels. Furthermore, we propose a novel pruning method based on optimization approach, namely NPB, that demonstrates the potential of balancing the numbers of effective paths and nodes to improve the performance of Pal methods. Extensive experiments conducted on various model architectures and datasets show that NPB outperforms the best baseline, PHEW, almost settings while ours produces more efficient subnetworks with much fewer inference FLOPs and faster in pruning time then PHEW. Our new perspective the configuration of subnetworks, in terms of effective nodes and effective paths, provides new insights into the working mechanism of Pal methods and opens new research directions on neural network pruning methods, well as designs of sparse neural network.
Acknowledgement
Part of this work was done while Hoang Pham was visiting University of Warwick. Dung D. Le was funded by Vingroup Innovation Foundation (VINIF) under project code VINIF:2022.DA00087.
References
[1] M. Alizadeh, S. A. Tailor, L. M. Zintgraf, J. van Amersfoort, S. Farquhar, N. D. Lane, and Y. Gal. Prospect pruning: Finding trainable weights at initialization using meta-gradient In International Conference on Learning Representutions, 2022.
[2] P. Bithika, B. Arindam, K. Sudeshna, M. Pabitra, and B. Biswajit. A study on the ramanujan graph property of winning lottery tickets. In International Conference on Muchine Learning, volume 162, pages 17186-17201, 2022.
[3] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901, 2020.
[4] T. Chen, J. Frankle, S. Chang, S. Liu, Y. Zhang, 7.. Wang, and M. Carbin. The lottery ticket hypothesis for pre-trained bert networks. Advances in neural information processing systems, 33:15834-15588 2020.
[5] T. Chen, J. Frankle, S. Chang, S. Liu, Y. Zhang, M. Carbin, and 7. Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16306-16316, 2021.
[6] T. Chen, B. Ji, T. DING, B. Fang, G. Wang, Z. Zhu, L. Liang, Y. Shi, S. Yi, and X. Tu. Only train once: A one-shot neural network training and pruning framework. In A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
jrCZq
10

---

[7] T. Chen, L. Liang, T. DING, Z. Zhu, and I. Zharkov. OTOv2: Automatic, generic, user- friendly. In The Eleventh International Conference on Learning Representations. 2023. URL net./Horum?dd-yyoollljPP.
[8] Y. Cheng, D. Wang, P. Zhou, and T. Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 35(1):126-136, 2018.
[9] P. de Jorge, A. Sanyal, H. Behl, P. Torr, G. Rogez, and P. K. Dokania. Progressive skeletonization: Trimming more fat from a network at initialization. International Conference on Learning Representations, 2021. URL http:://pppeeeeeeeeee///ooo///o
[10] L.. Deng. G. Li, S. Han, L. Shi, and Y. Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(())485-55) 2020.
[11] S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[12] X. Dong, S. Chen, and S. Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in Neural Information Processing Systems, 30, 2017.
[13] A. Dosovitskiy, L.. Beyer, Kolesnikov, D. Weissenborn, Zhai, Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL htttt:://opprreeeeeeee
[14) U. Evei, T. Gale, Menick, P. S. Castro, and E. Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages 2943-2952. PMLR, 2020.
[15] Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint a 1803. 03635, 2018.
[16] J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, pages 3259-3269. PMLR, 2020.
[17] J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin. Pruning neural networks at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021. net/forum?id-Ie URL/https://oppnrevvies
VyQc-MLK
[18] T. Gale, F. Elsen, and S. Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09577 099.79992..994,.. 2019.
[19] T. Gebhart, U. Saxena, and P. Schrater. A unified paths perspective for pruning at initialization. ArXiv, abs/2101. 2021.
[20] S. Han, J. Pool, J. Tran, and W. Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
[21] B. Hassibi, D. G. Stork, and G. Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299. IEEE, 1993.
[22] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[23] G. Hinton, O. Vinyals, J. Dean, et al. Distilling the knowledge in neural network. arXiv preprint arXiv: 1503.0253303311 2(7), 2015.
[24] Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and Peste. Sparsity deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(1), jan 2021.
[25] Y. LeCun, J. Denker, and S. Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.

---

[26] N. Lee, T. Ajanthan, and P. Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019. URL https //openrevies net het/Horum"iddBBVZqjAAY
[27] S. Liu, T. Chen, X. Chen, Z. Atashgahi, L. Yin, H. Kou, L. Shen, M. Pechenizkiy, Z. Wang, and D. C. Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34:9908-999 2021.
[28] S. Liu, L. Yin, D. C. Mocanu, and M. Pechenizkiy. Do we actually need dense over- parameterization? in-time over-parameetriizatinn in sparse training. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6989-7000. PMLR, 18-24 Jul 2021. URL mlr. wwtpp//1ee/sse/eeeeee
html
[29] S. Liu, T. Chen, X. Chen, L. Shen, D. C. Mocanu, Z. Wang, and M. Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. In International Conference on Learning Representations, 2022. URL https //openreview. sapenreview.net/forurffe met/forum?id-vBBI 3tz-tt
[30] D. C. Mocanu, E. Mocanu, P. Stone, P. H. Nguyen, M. Gibescu, and A. Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 91): 2018.
[31] P. Molchanov, S. Tyree, T. Karras, T. Aila, and J. Kautz. Pruming convolutional neural networks for resource efficient inference. arXiv preprint 1.XXx:6611.064/// 2016.
[32] Molchanov, S. Tyree, T. Karras, Aila, and J. Kautz, Pruning convolutional neural networks for resource efficient inference. In International Conference Learning Representations, 2017. URL httptttt:///eereeiiiiiiie
[33] M. C. Mozer and P. Smolensky. Using relevance to reduce network size automatically. Connec- tion Science, 1(1):3-16, 1989.
[34] S. M. Naji, A. Abtahi, and F. Marvasti. Efficient sparse artificial neural networks. ArXiv, abs/2103.07674, 2021.
[35] Q Nguyen, M. C. Mukkamala, and M. Hein. Neural networks should be wide enough to learn disconnected decision regions. In International conference on machine learning, pages PMLR, 2018
[36] S. M. Patil and C. Dovrolis. Phew: Constructing sparse networks that learn fast and generalize well without training data. In International Conference on Machine Learning, pages 8432-84 8442. PMLR, 2021.
[37] I. Price and J. Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via subspace offset. In International Conference on Machine Learning, pages 8620-8800 8629. PMLR, 2021.
[38] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 8748-88888 1768-876. PMLR, 2021.
[39] A. Ramesh, M. Pavlov, G. Goh, S. Gray, C. Voss, A. Radford, M. Chen, and Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 8821-8831. PMLR, 2021.
[40] J. Su, Y. Chen, T. Cai, T. Wu, R. Gao, L. Wang, and J. D. Lee. Sanity-checking pruning methods: Random tickets win the jackpot. Advances in Neural Information Processing Systems, 33: 20390-20401, 2020.
[41] X. Su, T. Huang, Y. Li, S. You, F. Wang, C. Qian, C. Zhang, and C. Xu. Prioritized architecture sampling with monto-carlo tree search. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 10968-10977, 2021.
12

---

[42] H. Tanaka, D. Kunin, D. L. Yamins, and S. Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33:6377-6388, 2020.
[43] R. Taylor, M. Kardas, G. Cucurull, T. Scialom, A. Hartshorn, E. Saravia, A. Poulton, V. Kerkez, and R. Stojnic. Galactica: A large language model for science. arXiv preprint wwXiv:2211.0908. 2022.
[44] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13377 2023.
[45] C. Wang, Zhang, and R. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL https // //openreiier www. net/ htt///ommmddikssSatSss HSSSgSACV
[46] H. Wang, C. Qin, Y. Bai, Y. Zhang, and Fu. Recent advances on neural network pruning at initialization. In L. D. Raedt, editor, Proceedings of the Thirty- First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 5638- 5645. ijcai.org org, 2022. doi: 10. 00224963ijccai.222227666 URL
ijcai 2eaai22022/86
[47] G. Yuan, X. Ma, W. Niu, Z. Li, Z. Kong, N. Liu, Y. Gong, Z. Zhan, C. He, Q. Jin, et al. Mest: Accurate and fast memory-econome sparse training framework the edge. Advances in Neural Information Processing Systems, 34:20838-20850, 2021.
[48] R. Zhao, Y. Hu, J. Dotzel, C. De Sa, and Z. Zhang. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pages 7543-7552 PMLR, 2019.
[49] M. 7hu and S. Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression, arXiv preprint arXiv: 11X.x0171000877 2017.
13

---

A Experiment details
In this section, along with pruning at initialization (Pal) methods in the main text, we provide experimental results with GraSP [45]. In particular, GraSP is another gradient-base based pruning Pal that aims to preserve the gradient flow of sparse networks obtained by pruning. The score z of weight w in GraSP is computed as z -w @ (HV L_), where H is the Hessian of the training loss after passing a mini-batch of data through the network.
We describe our experiment settings on architectures and datasets. We use Pytorch library and single GTX 3090Ti A 100 (depend their available). We adapt from Tanaka et al. [42] source code for SNIP, GraSP, SynFlow, and Random, and change the prune epochs 100 for Iterative SNIP instead of in SNIP. And we use the official code _ of Patil and Dovrolis [36] for PHEW. For NPB method in the main experiments, we set a = 0.01 and B I for all settings.
conduct experiments
Datasets, Our main experiments are conducted with CIFAR-10, CIFAR-100, and Tiny- Imagenttt datasets, where:
CIFAR-I0 is augmented by normalizing per-channel, randomly flipping horizontally.
CIFAR-100 is augmented by normalizing per-channel, randomly flipping horizontally.
Tiny-ImageNet is augmented by normalizing per channel, cropping 64x64, and randomly flipping horizontally.
Architectures. We use three different networks:
VGG-19 is CIFAR-100 network used in SynFlow 42 version.
We choose a batch-normalization
ResNet-20 is a 20-layer CIFAR-10 version of ResNet created by added batch normalization layers before each activation function.
22 This version has
ResNet-18 is a ImageNet version with 18 layers adapted from SynFlow (42). The first convolution has kernel size 3x3 (instead of 7x7) and max-pooling layer that follows has been removed.
We treat all of the weights from convolutional and linear layers these networks are prunable parameters, but we do not prune the biases nor the weights in the batch normalization layers. The weights in convolutional and linear layers are initialized with Kaiming normal, while biases are initialized to be zero. We run five seeds with CIFAR experiments and three seeds with experiments on Imay-em
Training details With Iterative pruning methods SNIP and SynFlow. we use 100 pruning epochs. With methods using training data like SNIP. GraSP, and IterativeSNNIP, we randomly select 10 samples for each class, particularly, 100 data points for CIFAR-10, 1000 data points for CIFAR-100, 2000 data samples for Tiny-em Other hyperparameters are chosen as follow:
Table 2: Summary of the architectures, datasets, and hyperparameters used in experiments.
Network
Dutaset
Epochs
Batch
Optimizer
Momentum
LR
LR Drop. Epoch
Weight Decay
VGG-19
CIFAR- 100
160
128
SGD
0.9
0.1
10x, [60, (60]
0.0001
ResNet-20
CIFAR-10
160
128
SGD
0.9
0.1
10x. [60, 120]
0.0001
ResNet-18
Tiny- Imageee
128
0.01
10x. [30,60,80]
0.0001
hhatss//pytorch..og
14

---

B Effective metrics calculation
Efffettive path. To exactly compute the number of effective paths, we remove the batch normaliza- tion layers, we initialize all the remaining parameters to 1. Then, we put the input vector one to the network, and the number of effective paths is the sum of logits on the output layer 1 Ww)).
More precisely, we face problems with pooling layers in convolutional neural networks. With max pooling layer, we simply do modify the output of this layer. At that time, the result is the maximum number of paths in subnetworks. With average pooling layer, since all inputs this layer contribute the output, we change the average operator the operator exactly compute the number of effective paths. We all use ReLU activation functions in computing this metric since this function does not affect the results of calculations.
Effective parameter. We follow 17 when identifying which is effective parameter. Similar to computing effective paths, we make further steps. After having the sum of logits. we compute the gradients of this sum with respect to weights v. Then, if an unpruned weight has a non-zero gradient, it effective and vice versa. Effective parameters dense edges that connect effective nodes as visualized in Figure 2
Effective node/channel. With fully connected layers, all connections to one node or of one node are pruned, this node is pruned node. If there exist connections to node but all of these connections are ineffective, then this node becomes ineffective In convolutional layers, instead of nodes, we have channels. We consider kernel as connection, channel node, and then convert the convolutional layer into a fully connected layer. The connection is pruned if and only if all parameters in the corresponding kernel are removed. Finally, identifying the effective nodes/channels similar to the way fully connected layers.
def
(model, mask)
model: network architecture
mask: mask for subnetwork
n_eff_pathe =
n_eff_nodes
_.eff_params
10
# Initialize network with pruned weight = 0 and kept weight for name, param in model.named__prreee pamed__ara param.. copy_ (mask[nane [name])
11
13
14
x torch. ones ((1,
c: channel h: height w: width
15
y = model(x)
ham_logits_> sum
n_eff_pathe
sum wloglossiitete
18
sum lum_logits.. backward()
19
with torch. no ()
for name, param in model, named__prannteess ():
eff_param torch. where (param grad data!=0, 1,
22
n_eff_params
torch. sum(eff_param)
23
24
eff eff_in_nodd = torch. where (torch. sum (eff n_eff_nodes += torch. # with output layer
sefffchhaaaauaaaaaaaaeeaaeeea -arffppaamm.._ d=0)>0, 1, 0)
27
eff_ off_out_node torch. (y>00 0)
28
n_eff_nodes += torch. sum (eff_out_nodee
return n_eff_paths, n_eff_nodes, n_eff_params
Listing Metric calculation example in fully connected neural networks
15

---

C Layer-wise Mask Optimization
We provide the pseudo code solving the mask optimization problem based on the evxpy library [1]] We use the default solver provided in this tool.
import math
import cvxpy as cp import numpy as np import torch
def optimize__ (mask, inp, sparsity, alpha=0.1, beta=0.1, max_ pax_param.per_.emeelloooo u..
mask: mask of this layer
inp: input of this layer
10
sparsity: the sparsity of this layer alpha: is the balancing coefficient beta: is the regularizer coefficient
11
12
"e_pprra__per_kenne max param in a kernel
15
16
if len (mask ) == 4: # Convolution layer ouut, C_in, K, и mask shape
17
kernel ker_eereeeeelllllll P_in torch. sum Sunp,, dim=(1.2)) numpy ()
max_param_pent per_pper_kee
19
20
else: Linear layer Cout, C_in ttt_param_per_eeme
21
shape
P_in inp. numpy
24
25
# Params in layer
26
n_params- = int (math, ceil ((1- ((1-sparsity) mask. ()) # This has to be integer
27
28
Define variable
29
M = cp. Variable(CC_in, C_out), integer=True)
sum_in sum (N, axis=1) P_in P_in \sum M_{ij} shape: C_in
32
sum_ out cp PMMMMP axis=0) \sum_ (iM M_(ij} P_in[i]
=> shape: C_out
If eff_node_in in is small which means there is large number of input effective node sum_eff_node___ = Cin cp sum sum
35
sum_in))
36
= Cou cp. sum (cp. p1s sum_out))
38
Optimize nodes max
39
nodes max_nodes
C_in + C_out + sum_eff_node_outt / max_nodes # Scale to 1
40
A =
Optimize paths
43
max pat_hath compute_man max (ttpeaaaaappppppaaeeeeeeeeeee (P_hh__in)) n_params, C_out, max max_param_pel peara_per__erne]] kernel)
44
B (cp. sum iP @ M)) / max_path
Regulaziration
47
Reg (n_params-cp. sum (cp. n_params
encourage number
of edges
Constraint the total activated params constraint sum (1) n_params, max_param_pa pearammpper..e kernel,,,, 0]
50
Objective function
16

---

obj =cp Maximize (alpha A + (1-alpha) B beta Reg)
55
Init problem
56
prob = cp. Problem constraint)
57
prob.sovves
# Solving
return M. value
Listing 2: Layer-wise mask optimization
17

---

D Layerwise Shuffling Experiments
With each setting, each sparsity ratio, seek subnetworks with different seeds, and with each seed, we randomly shuffle the subnetwork two times. In addition to effective path ratios and effective node ratios, we compute the number of effective parameters after pruning and the actual remaining ones, then calculate the ratio between these two values.
Similar 17 results, the performance and the number of effective parameters of high-density subnetworks after permuting the connections are similar to or even higher (in SNIP) than the unmodified ones. However, when the sparsity level becomes subnetworks is more concrete. Randomly rearranging connections within layers destroys this strict structure by detaching important edges, which drastically reduces the number of effective paths. The shuffled subnetworks lack input-output paths to transfer information during training, leading to drop performance compared with unmodified ones.
intensive, the configuration of
pleare pab 1883
SNIP
92
ShaPidd
Steefed
Unt c4
1877 c4
Unmodfed fid
UnTodffad
49.69
29.00
Synt Saven
04
Steffed
Staftid
aftettte
Stuffed
2.
UrmosTee
10.50
18.4
1010
10.00
24.44
18
48
18.20
10.20
30
80
102.00
29.54
301
19.60
OP OW-220 2413 1400
0125
PHEN
8
thethee
2060
0005
19.00
2010
89.00
Sanna
Figure 6: Layerwise shuffling results on various sparse subnetworks of ResNet20 produced SNIP
SynFlow, and PHEW at initialization CIFAR-10.
18

---

E
Pruning Time and FLOPs Reductions
Since NPB optimizes layer by layer, the complexity of NPB depends on network architecture (i.e., the number of layers and the size of each layer). With large layers, we sidestep the time-consuming issues by making a further step where we divide the nodes in the next layer into chunks with the same sparsity constraint, and optimizing chunks in layer can be solved in parallel. Particularly, we consider layer I with mask m e **x""** in which 40) and 4(++1) are the number of nodes in layer and + We divide 10+1) nodes into K equal chunks. Instead of directly solving for m we solve K problems [m] m ..... mx where m E R "x Thank for available convex optimization libraries we can find subnetworks more efficiently and quickly. We have computed the pruning time of our proposed method and compared it with other Pal methods in Tables 3 and
Besides pruning time, find that the FL.OPs reduction of subnetwork after pruning is more important in the context of pruning before training. We have measured FLOPs of subnetworks produced by different methods in Tables and The result indicates that our NPB can produce subnetworks with lower FLOPs than other baselines while NPB outperforms Pal methods.
Table 3:
Accuracy, pruning time (in seconds) and FLOPs of subnetworks for different pruning methods and compression ratios on Resnet18 Siny-ImageNes
Accuracy (%)
Pruning time (seconds)
FLOPs (10")
Sparsity (%)
68.38
90.00
96.84
99.00
68.38
90.00
96.84
99.00
68.38
90.00
96.84
99.00
56.99
53.43
48.77
36.02
5.14
4.95
5.55
5.64
11.35
5.77
3.04
1.55
Iter-SNIP
56.73
53,60
48.55
36.42
229.16
235.34
233.19
231.23
10.73
7.05
3.98
1.97
SyaFlow
56.71
$4.68
49.03
39.79
108.17
96.18
91.15
92.60
14.71
8.91
4.24
1.50
PHEW
58.09
55.93
50.81
40.54
5511.20
1342.03
471.23
324.78
14.29
8.35
3.92
1.50
NPB
58.39
56.82
51.37
41.05
380.52
375.65
384.32
387.89
14.37
5.21
1.74
0.59
Table 4: Accuracy, pruning time (in seconds) and FLOPs of subnetworks for different pruning methods and compression ratios on VGG19 CIFAR-100.
Accuracy (%)
Pruning time (seconds)
(10")
Sparsity (%)
68.38
68.38
99.00
SNIP
71.31
70.65
67.82
61.77
5.15
4.96
5.12
17,952
3.686
1.816
Iter-SNIP
72,84
70.86
67.72
63.13
115.91
115.52
116.83
117.60
18.465
9.479
4.951
2.529
SynFlow
71.63
69.18
66.98
62.11
96.55
100.33
101.90
104.67
22.998
12.702
6.306
2.605
PHEW
73.18
70.70
68.18
64,43
6928.59
1699.80
605.65
417.25
22.108
11.746
5.611
2.340
NPB
74.05
71.76
68.87
64.82
430.52
438.20
412.16
425.33
22.035
8.773
2,874
1.046
Table 5: Accuracy, pruning time (in seconds) and FLOPs of subnetworks for different pruning methods and compression ratios on Resnet20 CIFAR-10.
Accuracy (%)
Pruning time (seconds)
FLOPs (10")
Sparsity (%)
68.38
90.00
96.84
99.00
68.38
90.00
96.84
99.00
68.38
90.00
96.84
99.00
SNIP
87.88
84.02
76.72
62.03
1.42
1.40
1.87
1.68
17.952
8.323
3.470
1.709
Iter-SNIP
88.17
84.22
77.05
64.95
58.21
54.60
52.02
57.61
18.465
9.698
4.510
2.022
SynFllw
88.64
84,94
78.22
66.05
57.46
56.24
53,43
54.13
22,998
11.549
4.263
1.633
PHEW
90.38
87.41
81.05
70.44
78.31
18.09
4.78
2.58
22,108
10.690
4.110
1.640
NPB
90.69
87.61
80.55
70.70
20.10
23.91
21.51
21.13
22,035
7.642
2.645
1.122
19

---

Additional Results with Pal comparison
ResNet20 CIFAR-10
90
Accuracy (%6
PHEW
75
SNIP
SynFlow
70
Magnitude
65
NPB
Derde
60
43.77
68.38
90.00 Sparsity
96.84
99.00
ResNet18 TinylmageNet
60
Accuracy (%6)
45
PHEW
Random
SNIP
40
Rer-SNIP
GraSP
35
NPB
43.77
68.38
90.00
96.84
99.00
Sparsity
Figure 7: Accuracy of subnetworks found by different Pal methods and LTH at various sparsity levels on two settings ResNet20 on CIFAR-10 10 and ResNet18 on Tinylmagencl
20

---

G Additional Results with Ablation Studies
In this section, we conduct experiments with different balancing coefficients (alpha) and regularization coefficients (beta) in setting R8 8 on Tiny- Iny-Imagenet and visualize results in Figure [ We run NPB with alpha in {0.01, 0.05, 0.5, 0.75, 0.9) and beta in 0..1, 0.75, 1.0, 1.5, 2.0). In the first row, we visualize the performance of subnetworks generated by different alpha beta hyperparameters. In addition, to illustrate the correlation between subnetworks of NPB and Pal methods terms of the number effective nodes and paths, we visualize alpha and beta subnetwork variants of NPB and Although NPB's variants have difference performance, they still outperform baselines. When visualize NPB variants with different Pal methods (SynFlow, Random, and PHEW) together, we can see that NPB variants concentrate around a specific region near PHEW which we hypothesize results compared with SynFlow or Random, and have competitive performance with each others. This strengthens Node-Pate Balancing Principle.
Pal methods in the second row of Figure g
balancing area. Besides, networks in this region show a better
Sparsity 68.38%
Sparsity 90.00%
Sparsity 96.2455
57.
52.0
-05.80
51.00
$7.04
56
23
05:42
58:34
55.71
57.07
37.50
16.50
50
54
57.0
50
5352
51:35
11.34
52.17
52.07
51.5
6.75
20.23
$5.34
28.29
$8.54
38.4
-57.64
25.07
57.29
56.14
42
1122
53.13
23.32
12.36
14
5100
50
-35.99
38.54
56.70
55.00
55.15
5994
53.74
53.76
51.87
50.5
50,02
35.20
18.04
58.02
29.04
57:02
- -5.77
57.19 37.00
26.45
17:24
57.12
56.0
55
$1.00
52.47
31.30
12.37
52.02
56.83
$7.8
-5.06
55.
0.0%
0.1
0.5
6.75
6.9
8.61
6.06
6.1
0.5
5.75
0.9
0.51
5.64
51
6.5
0.75
0.9
Apphs
Alsta
Alpta
Sparsity
Sparsity
Sparsity 95.84%
45
50
44
484
45
12
38
PrEM
Prip
32 Upt
Number effectuve
Number steflettive roder
Nammer eflect sral))
Figure 8: Ablation study on alpha and beta hyperparameter with setting ResNet18 on Tiny- Tiny-Imagenet
NPB depends on the layer-wise sparsity ratios, disparate ratios guide the pruner to diverse set of solutions. Then, it is essential to investigate the effect of sparsity initializers on NBP's performance. We follow Liu et al. [29] to use ERK [14), Uniform, Magnitude ratio, SNIP ratio found by applying SNIP (6). and GraSP ratio by using GraSP [45 as five methods to produces layer-wise sparsity levels. Figure P illustrates results with these sparsity initializers for ResNet18
Imay-em with different sparsity levels. With the same value of a and B, we observe that different layer-wise sparsifiers produce different network structures and performances well. This difference raises question for further work how we can specify ratios that help obtaining promising solutions.
Spansity
Sparsity 90
Sparsity
47
$4.53
$3.07
50.31
66
36.33
45
44
08:0
Sype oat's
43
3N7 ralo
35
Number affostive nockss Iin scals)
Nunner eillliiive redes
Mamber affost rodes
Figure 9: Ablation study different layerwise sparsity initializer with setting ResNet18 on Tiny-
Imagenet
21

---

H NAS-Bench-Macro Experiments
MAS-Bench-Maue
macro benchmark which used in Neural Architecture Search.
includes 8 searching layers, each having three candidate blocks which construct 6, 5611 different
networks with the parameter varying from 300k to 3M. The network structure is presented in Table The structure is inspired from MobileNetV2 search space. In particular, candidate blocks are (i) Identity connection, (ii) MB3_K, _3 which is MobileNetV2 block with kernel size 3 and expansion ratio 3, and (iii) MB6_K* KS which is MobileNetV2 block with kernel size 5 and expansion ratio 6. To make a fair comparison between candidates, we only compare networks with a similar number of parameters (i.e., in range of 300k parameters). Note that, each candidate here is dense network. We compute metrics in four different parameter ranges and visualize them in Figure [0]
Table 6: Macro structure of search space on MAS-Bench-Mee
n
input
block
channel
stride
1
32 32 x
3 x 3 conv
32
1
2
32 x 32 x 32
Choice Block
64
2
3
16 x 16 64
Choice Block
128
2
3
x 8 x 128
Choice Block
256
2
1
x x 256
1 I conv
1280
1
4 x 4 x 1280
global avgpool
1
1280
FC
10
Thenumber paramale's 22522222231
The 1550011514
Tueber 2000
5o sis
126 modee
The number deperaneie's tom 24536
The rumbore promearatoor 2400027524
The rumbar of ciramoion from 27506-3353
212
20-
635 1.5 315
5.10
1.00
675
670
Figure 10: The accuracy of network candidates in NAS-Bench-Macro benchmark along with the number of activated nodes and paths in different parameter ranges.
22


Reviews:
[{"review_id": "G6M9JLysip", "reviewer": "Reviewer_a28p", "summary": "The authors propose a Pruning at Initialization (PaI) method that considers the balance between the number of effective nodes and effective paths. This design principle is based on the observations on the NAS benchmark as well as layer-wise reshuffling. The pruning problem is nicely formulated as a multi-objective optimization problem. The experiment results show that the proposed method NPB outperforms the state-of-the-art method PHEW in some configurations.", "questions": "See the weak points mentioned above.", "limitations": "The authors did not discuss the limitations and potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* A new Pruning at Initialization (PaI) method is developed considering both the number of effective nodes and the number of effective paths.\n* A lot of analyses and experiments have been conducted to show the superiority and motivation of the proposed method. \n* The pruning problem is formally transformed into a multi-objective optimization problem.\n* In some settings, the proposed method NPB is shown to outperform the state-of-the-art method PHEW.", "weaknesses": "The motivation and technical details are not very clear in several places, as follows.\n\n**Overall:**\n* The sweet spot of the proposed framework seems to be the extreme sparsity regime (> 99%).  I am really wondering if we need to prune a network to the extreme. My impression is that the sweet spot is a corner case.\n\n**Section 3.3:**\n* Line 187: Why does reshuffling make subnetworks wider?\n* Line 205: How is the hypothesis derived from reshuffling?  PaI actually does *not* involve reshuffling.  \n\n**Section 4.1:**\n* Figure 4 (and Figure 1): It seems that, in typical architectures, the number of effective nodes and the number of effective paths are strongly correlated.  Then, why do we need to balance these two metrics?\n* Line 223: Along the same lines, the strong correlation between the two metrics indicates that one of them is redundant. Thus, the overall claim cannot be supported by the observation.\n* Figure 4 (and Figure 1): What's the meaning of each value in the x- or y-axis?  For example, what do you mean by $9.0$ in the x-axis?\n\n**Section 4.2:**\n* Due to the strong correlation between the number of effective nodes and the number of effective paths, it may be unnatural to produce subnetworks with too many effective paths (or nodes) and too few effective nodes (or paths).\n\n**Section 4.3:**\n* Even though it is reasonable to balance these two metrics, their ranges significantly differ. Actually, they have completely different scales (natures). This *incompatibility* between the two metrics would explain a very small value of $\\alpha$=0.01. Syntactically, Equation (4) does not achieve the balance, but mainly considers only $f_p$. Also, $\\alpha=0.01$ is indeed arbitrary and does not provide any insight on the optimal balance. \n* Appendix G (Ablation Study): Figure 8 shows that the accuracy is not that sensitive to $\\alpha$. I am still very confused why the balance between the two metrics is indeed important. Figure 8 directly shows that the optimal balance may not be important.\n\n**Section 5.2:**\n* It is not clear how the sparsity levels were chosen for the datasets in Figure 5. That is, how are the 12 settings chosen? I believe that a wider range of sparsity levels should be analyzed.\n* In contrast to Figure 4 (and Figure 1), it is not clear why most of the circles are not placed on the diagonal. \n* Line 316: Many cases of NPB do not lie in the so-called balancing regions. It would be better to mark the balancing regions in the figures.\n\nOverall, I believe the proposed framework is interesting and has some potential. However, the main contribution is neither well motivated nor rigorously presented. It seems that my concerns may not be sufficiently addressed by the rebuttal process. Therefore, I would like to give my rating as a reject.\n\n--\n\n**After Rebuttal**\n\nSome of the concerns and questions are resolved by the authors' rebuttal. However, the observational motivation and the need for careful optimization are not convincingly presented. Thus, I am a little reluctant to give a high score and would like to increase my rating to 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review our work. We would like to address all the weaknesses pointed out by you point-by-point below:\n> The sweet spot of the proposed framework seems to be the extreme sparsity regime (> 99%)\n>\nA1: We respectfully disagree with the reviewer. Our experiments have been conducted across a range of sparsity levels, all of which are lower than 99%. The results demonstrate superior performance compared to baseline methods.\n> Why does reshuffling make subnetworks wider?\n>\nA2: Iterative pruning prioritizes high-scoring nodes, which are typically determined by gradient/weight information. When nodes have edges pruned, their scores tend to decrease, making them more susceptible to further pruning. This can lead to slender subnetworks (eg., SynFlow, Iter-SNIP). When shuffling layer-wise, connections are redistributed uniformly, widening the subnetwork. Similar findings have been illustrated in [1].\n\n[1] https://arxiv.org/abs/2009.08576\n> How is the hypothesis derived from reshuffling? PaI actually actually does *not* involve reshuffling.\n>\nA3: In general, PaI approaches do not involve reshuffling. However, we use reshuffling to emphasize the balance between effective nodes and paths. Good sparse NNs should have enough effective nodes to ensure good representation capacity and enough effective paths to guarantee good signal propagation during training. With limited number of parameters, shuffling can intuitively widen subnetworks, but it can decrease the number of effective paths, which can impede information flow (good signal path can be destroyed after shuffling). The empirical results perfectly align with our intuition: While shuffling can sometimes boost performance, accuracy drops as sparsity increases. Stemming from the above observation, we propose to balance two metrics, enhancing optimal sparse NNs design.\n> Figures 1, 4: in typical architectures, the number of effective nodes and paths are strongly correlated, which indicates that one of them is redundant.\n>\nA4: We disagree with the reviewer for two reasons:\n\n- In NAS, networks are dense. Correlations between nodes and paths exist depending on specific design aspects like the number of channels. However, components like skip-connect or pooling layers may affect either nodes or paths. Different block configurations (Appendix H) results in variable node and path counts.\n- Node-path relationship is totally different in pruning. All subnetworks are pruned from the same dense network, which have a strong constraint of the fixed number of connections. The relationship is now based on the remaining connections. Therefore, the way we prune the network can significantly affect this relationship.\n\n> Then, why do we need to balance these two metrics? Thus, the overall claim cannot be supported by the observation.\n>\nA5: It's important to emphasize that in typical architectures, nodes and paths are related and used to monitor the network's performance.\nA notable node-path balancing scenario is preventing uniformly distributing connections to nodes to enhance the representation capacity (Random pruning), which implicitly limits information flow.\nReversibly, the node-path balancing also prevents pruning out most of the channels but greatly keeps the connections between nodes (SynFlow), which makes networks have a poor number of linear-regions to distinguish features.\nThe node-path mechanism aids us in identifying the optimal subnetwork that is determined by both metrics. This approach results in superior performance compared to the use of a single metric as we have shown in our paper.\n> Figures 1, 4: What's the meaning of each value in the x- or y-axis?\n>\nA6: The x- and y-axis are the number of effective nodes (in ln scale) and paths (in log scale). We mentioned these numbers in lines 284-286.\n> Due to the strong correlation between nodes and paths, it may be unnatural to produce subnetworks with too many paths (or nodes) and too few nodes (or paths).\n>\nA7: In pruning as explained in A4, it is natural that we can make the network slender with a many paths (like Synflow) or broader with fewer paths (like PHEW) as shown in Figure 5.\n> Different scales of metrics in Eq-4. $\\alpha=0.01$  is indeed arbitrary and does not provide any insight on the optimal balance.\n>\nA8: Due to limited space, we refer Reviewer to lines 269-274 for details.\n> Appendix G, Figure 8 shows that the accuracy is not that sensitive to $\\alpha$ and optimal balance may not be important.\n>\nA9: In Figure 8, with low sparsity levels (<90%), optimizing node is easy because there are many connections, and differences in $\\alpha$ only affect the number of paths. However, as sparsity increases and $\\alpha$ varies, the limited number of weight directly impacts the number of nodes in subnetworks. By fixing $\\beta$ and varying $\\alpha$, subnetworks’ performance changes accordingly. Thus, identifying an optimal balance point is crucial for pruning neural networks.\n> How sparsity levels were chosen? Wider range of sparsity should be analyzed\n>\nA10: The choice of sparsities was guided by the compression rate r which is computed as follows #Remaining_weight / #All_weight = 10^(-r) [2]. Sparsity levels are derived from $r\\in$ {0.5, 1, 1.5, 2}. While wider sparse range is important, we believe that the chosen sparsity settings are common and effectively demonstrate the efficiency of our proposed method.\n\n[2] https://arxiv.org/abs/2006.05467\n> In contrast to Figures 1, 4, it is not clear why most of the circles are not placed on the diagonal.\n>\nA11: Please refer to A4 and A7.\n> Many cases of NPB do not lie in the so-called balancing regions. It would be better to mark the balancing regions in the figures.\n>\nA12: We recognize the need to clarify effective nodes and paths' balancing regions. Balancing these factors is complex due to their mutual impact. Our proposed proxy method addresses this challenge, yielding strong empirical balancing outcomes across various experiments."}, {"review_id": "cL9ZPMd779", "reviewer": "Reviewer_8roE", "summary": "Given the numerous pruning-at-initialization (PaI) methods, the performance of them are still far from satisfactory compared to the post-training pruning methods. In this work, the authors provide a novel perspective to understand the relationship between the performance and the architecture of the subnetworks generated by PaI methods. In particular, this work studies the topology of the subnetwork and observed a positive correlation between the PaI performance and the balance between the effective nodes and effective paths. Further, the authors propose a new PaI method, named Node-Path Balancing Pruner (NPB) to explicitly balance effective nodes and paths. The empirical results demonstrate the effectiveness of the proposed method.", "questions": "1. It would help the readers to understand the details of the motivation studies if the authors could explain how the \"effective sparse ratio\" is calculated. Is it done by traversing? Or is there any effective algorithm to calculate that automatically?\n2. I am very surprised by the results of the motivation studies. Thus, I am curious if the same rules can be applied to post-training pruning?\n3. In the algorithm of NPB, the layer-wise sparsity is obtained through ERK. Is there a particular reason for this choice? Will other methods also be applicable?", "limitations": "I do not have additional comments on the limitation of this work. Please refer to the \"Weaknesses\" and \"Questions\" sections.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper studies the PaI methods from a novel perspective of model topology. This is a very interesting but also challenging perspective. \n2. The figures and graphs in this paper are very delicately plotted and are of high quality. They help the readers better understand the methods proposed. \n3. This work made enough literature review, which has covered the most important PaI literature.\n4. This work is written in a very coherent manner, which shows clear the motivation, the method, the rationale behind the method, as well as the logic of the empirical studies. \n5. The empirical results of the proposed method are indeed very impressive. ", "weaknesses": "I listed several weaknesses below from different perspectives. I will consider to raise my score if they are properly addressed.\n* [Method] Based on my understanding of the NAS observation, the reason for balancing the effective nodes and the effective paths is to maximize the usage of the limited parameter quota. However, if this is true, wouldn't directly cutting down the width of the network a perfect option for NPB? Correct me if I missed anything.\n* [Method] Mathematically, the formulation of the optimization objective in Eq. (0) (between Line 243 and Line 244) and Eq. (4~5) are not standard. The to-be-optimized variables should be clearly stated beneath the maximization symbol.\n* [Method] It is not very clear to me, how the optimization is carried out through the objective Eq. (4~5). Are there back-propagations involved? It seems not.\n* [Experiments] For Fig. 5, the information conveyed is not as clear as I expected. Probably this is because the performance of each method in each setting is annotated with numbers. I would suggest the authors to plot a normal figure showing the performance change (y-axis) vs. the sparsity level (x-axis) as many pruning paper does (there are too many and thus I spare the references here). It can help the readers compare the final accuracy of different methods if they do not care the intermediate results too much (e.g. the effective paths/nodes).\n* [Experiments] In the experiments, the $\\alpha$ is set to $0.01$. However, the word \"balanced\" claimed in the abstract seems a bit deceptive. To me, the value of $\\alpha$ is very crucial in the proposed method, but the authors fail to demonstrate its role through some ablation studies. I would suggest the authors either explain their choice of $\\alpha$ and/or conduct some ablation studies on $\\alpha$.\n* [Experiments] In Fig. 5, will it be better to add a reference line such as $y = \\alpha x$ to help judge the balance of the nodes/paths? Correct me if I missed anything.\n* [Experiments] This is not a must but I think the baselines compared in this paper are a bit old. Some methods like ProsPr (already cited in the paper) are recommended to be compared. The lack of this result will not change my evaluation on this paper.\n* [Minor] Rephrase: \"An effective node/channel is one that at least one effective path goes through it\" ==> \"A node/channel is effective if at least one effective path goes through it\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the time to review our work and are glad that you find our work is well-written with sufficient experiments. We would like to address all the weaknesses pointed out by you point-by-point below:\n\n> Q1. Wouldn't directly cutting down the width of the network a perfect option for NPB?\n>\nA1: We appreciate your engagement with our work. While it's true that balancing effective nodes and paths aims to maximize the utilization of a limited parameter budget, directly cutting down the network's width might not be the ideal solution for pruning tasks.\nDrastically reducing the network's width can lead to a significant drop in representation capacity, potentially causing a performance decline. For example, Synflow, which reduces width to some extent, often sees performance improvements after reshuffling subnetworks. This effect suggests that simply narrowing the network might not fully capture the intricate trade-offs between nodes and paths.\nThe balancing of effective nodes and paths is about finding the right equilibrium to maintain an adequate representation capacity while also ensuring information flow. Our proposed approach acknowledges these complexities and seeks to strike a more refined balance to achieve competitive performance within parameter constraints.\n> Q2. The formulation of the optimization objective in Eq. 0,4,5 are not standard. \n>\nA2: We appreciate you pointing out our mistake. We will review and revise the formulations in the updated version.\n> Q3. It is not very clear to me, how the optimization is carried out through the objective Eq. (4~5). Are there back-propagations involved? It seems not.\n>\nA3: Solving node-path balancing objective globally over the whole neural networks seems to be a hard problem, one can conjecture that it is even NP-hard. However, one of our main contributions is to sidestep solving this hard problem by solving a sequence of easy problems to obtain good approximated solutions. In particular, we propose an approximation for solving this problem by doing layer by layer through convex optimization. The approximation problem is solved efficiently via the available convex optimization library (CVXPY library) in which we use the default solver for mixed integer programming named SCIPY [1].\n\n[1] https://www.cvxpy.org/tutorial/advanced/index.html#setting-solver-options\n> Q4. I would suggest the authors to plot a normal figure showing the performance change (y-axis) vs. the sparsity level (x-axis) as many pruning paper does.\n>\nA4: We have already visualized the figure like your suggestion in Appendix F. Please refer to the Appendix F in supplementary for more details.\n> Q5. The choice of $\\alpha$ and/or conduct some ablation studies on $\\alpha$.\n>\nA5: It's important to mention that optimizing nodes is relatively simpler compared to optimizing paths (we can simply assign parallel edges connecting nodes in the current layer to nodes in the next layer); hence, we deliberately choose small values of alpha, which can be considered as prior knowledge. We set the small alpha ($\\alpha = 0.01$) to all settings to ensure fair comparison with other baselines. In Appendix G, we have presented an ablation study on $\\alpha$ and $\\beta$.\n> Q6. In Fig. 5, will it be better to add a reference line such as $y=ax$ to help judge the balance of the nodes/paths?\n>\nA6: It is challenging to identify the specific balancing line. Balancing between node and path is indeed a complex endeavor and non-trivial due to their mutual impact on each other. We propose a practical proxy method to address the complex balancing issue which simply offers strong empirical balancing results across a range of experiments. Our goal with the proxy method is to offer a practical solution that strikes a balance while being easily applicable.\n> Q7. Comparison with recent baselines such as ProsPr\n>\nA7: We appreciate your recommendation and understand your perspective on including more recent baselines. While ProsPr belongs to PaI approach, it's worth noting that ProsPr employs multiple gradient descent steps to identify important weights. Thus, we believe that ProsPr has certain advantages over PaI methods like our NPB (which does not use information from the dataset).\n> Q8. [Minor] Rephrase: \"An effective node/channel is one that at least one effective path goes through it\" ==> \"A node/channel is effective if at least one effective path goes through it\"\n>\nA8: Thank you for your suggestions, we will edit it in the next version.\n> Q9. How the \"effective sparse ratio\" is calculated.\n>\nA9: We follow the algorithm in Appendix M of [2], The effective sparse ratio = #Effective parameters / #Unpruned parameters\n\nWe determine effective parameters as follow:\n\n1. Set each weight in the network to 1 if it is unpruned or 0 if it is pruned.\n2. Forward-propagate a single example comprising all 1’s.\n3. Compute the sum of the logits.\n4. Compute the gradients with respect to this sum.\n5. Prune any unpruned weight with a gradient of 0. Since these weights did not receive any gradient, they are disconnected from the output of the network.\n\n[2] https://arxiv.org/abs/2009.08576\n> Q10. I am curious if the same rules can be applied to post-training pruning?\n>\nA10: We consider LTH as a representative method for post-training pruning approach. Through the additional experiments shown in Figure 1 in the attached file, we observe that LTH’s subnetworks are also in the same rules. The gap in performance between LTH and PaI methods is due to LTH leveraged information from the dataset and model training to produce subnetworks. Overall, we strongly believe these results align with our principle and further support our principle as a necessary condition for good PaI.\n> Q11. Why choose ERK to obtain layer-wise sparsity? Will other methods also be applicable?\n>\nA11: We have mentioned this ablation study in Appendix G. Due to limited 6000 words, we refer reviewer to Appendix G in the supplementary for more details."}, {"review_id": "q3de4Cah0g", "reviewer": "Reviewer_qyia", "summary": "This paper posits that the performance of (neural network) pruning at Initialization methods depends on a balance between effective nodes and paths. With this framework, authors explain why randomly shuffled subnetworks are sometimes more effective than subnetworks found by pruning at initialization methods. Finally, using the Node-Path balancing principle, the authors propose a pruning at initialization scheme by solving a linear program that optimizes pruning mask to balance effective path and nods, which outperforms other pruning at initialization methods.  \n\n\nEmpirical experiments are done on image datasets (CIFAR and TinyImagenet) with VGG and Resnet-20 models. Further empirical evidence for the node-path balancing principle is demonstrated through NAS benchmarks. ", "questions": "- Please see the weaknesses section. \n- Shouldn't Eq 4/5 consider the mask M as binary? As such, M is a real value; how is the solution converted to a pruning mask?\n- Line 262: Should M vary from 0 to hw instead of kw for convolution masks?\n", "limitations": "None, that are not discussed or addressed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, and generally content is well-organized. \n- The proposed node-path balancing principle is used to explain an existing phenomenon (random shuffling) as well as present a new pruning at initialization scheme, which is quite interesting. \n- The convex program-based pruning method (NPB) outperforms other pruning at initialization methods and requires fewer FLOPs. PHEW is close in performance to NPB. However, the node-path balancing framework can also explain that, is interesting. \n\nOverall, the paper does a good job of introducing the node-path balancing principle and provides several empirical evidence in its support. ", "weaknesses": "\n- The NAS experiments are interesting, but it wasn't clear to me to connect them with pruning at initialization or data-agnostic pruning, as NAS experiments are data-dependent. \n- The term balance may be vaguely used. \n   - The proposed principle states that at a particular sparsity, the best-performing subnetwork has to strike a balance between the effective nodes and paths. However, it does not predict the right balance.\n    - It would be interesting to see if this balance depends on sparsity, model, and dataset or model and datasets only. Could the best-performing subnetwork network be maximizing average effective paths per node?\n- The experiments are limited to image datasets and two neural network architectures. However, I appreciate the authors reporting results over three random seeds though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for recognizing that our proposed method is technically sound and yielding commendable empirical results. We would like to address all the weaknesses pointed out by you point-by-point below:\n\n> Q1. The NAS experiments are interesting, but it wasn't clear to me to connect them with pruning at initialization or data-agnostic pruning, as NAS experiments are data-dependent.\n> \n\nA1: The intuition behind NAS experiments is that we would like to show that there is a strong correlation between the two metrics (node, path) and the final performance of network candidates. In particular, networks which are designed to have higher node and path tend to superior performance after training. We link this problem with sparse network configuration design.\n\n> Q2. The proposed principle states that at a particular sparsity, the best-performing subnetwork has to strike a balance between the effective nodes and paths. However, it does not predict the right balance.\n> \n\nA2: Precisely pinpointing the precise balancing point is indeed a complex challenge. In our research, we initiate by identifying these balancing regions. With the aid of a straightforward proxy method, we endeavor to address this issue, achieving notable empirical balancing and superior performance outcomes. The intricacies of achieving the ideal balance necessitate ongoing exploration, and we believe our work serves as a stepping stone towards this pursuit.\n\n> Q3. It would be interesting to see if this balance depends on sparsity, model, and dataset or model and datasets only. Could the best-performing subnetwork network be maximizing average effective paths per node?\n> \n\nA3: Indeed, the interplay of balance can be influenced by factors such as sparsity, model architecture, and dataset characteristics. Although explicitly pinpointing this balance is intricate and non-trivial, a core contribution of our work is the introduction of an approximation method (NPB) that empirically navigates subnetworks within these balancing regions across diverse sparsities and model types.\nMaximizing average effective paths per node would be an interesting direction. Indeed, a simplistic approach could lead to uniformly distributed connections, resembling the outcomes of Random pruning. To truly achieve a meaningful and effective balance, we believe a more sophisticated strategy is likely necessary.\n\n> Q4. The experiments are limited to image datasets and two neural network architectures. However, I appreciate the authors reporting results over three random seeds though.\n> \n\nA4: Thank you for your suggestions. We would like to clarify that ResNet20 is another version of ResNet which is defined for CIFAR-10/100 tasks. These CIFAR versions are significantly lower in the number of parameters compared to the ImageNet version (ResNet18) and are usually used in pruning literature. Regarding to more network architecture, we have conducted more experiments on two other ResNet versions which are ResNet32 and Wide-ResNet32 on CIFAR-10. These two versions are deeper and wider than ResNet20. We visualize results in Figure 4 in attached file.\n\n> Q5. Shouldn't Eq 4/5 consider the mask M as binary? As such, M is a real value; how is the solution converted to a pruning mask?\n> \n\nA5: We treat M as an integer variable. The optimization problem is solved efficiently via the available convex optimization library (CVXPY library) in which we use the default solver for mixed integer programming named SCIPY [1].\n\n[1] https://www.cvxpy.org/tutorial/advanced/index.html#setting-solver-options\n\n> Q6. Line 262: Should M vary from 0 to hw instead of kw for convolution masks?\n> \n\nA6: Thank you for addressing the error, indeed, M should vary from 0 to hw. We will edit this typo in the next version."}, {"review_id": "hlZKRl8qVP", "reviewer": "Reviewer_HuF1", "summary": "This paper examines Pruning at Initialization (PaI) methods using two novel metrics: the number of effective paths and the number of effective nodes. The authors find that layer reshuffling negatively impacts the performance of sparse neural networks obtained through PaI methods in the extreme sparsity regime. Based on the previous finding, authors present a novel data-agnostic PaI method, Node-Path Balancing Principle (NPB), which achieves the SOTA performance by effectively balancing the two proposed metrics.", "questions": "- In equation 3, what is the purpose of “min” operation? Or is it just a typo of $\\min(m_{ij}^l - 1, 0)$?\n- What kind of optimizer is implemented in the code as to approximating the original integer programming formulation?", "limitations": "The paper presents a future research direction in lines 706-707, which is included in the Appendix. However, it is equally important for the authors to acknowledge and discuss the limitations of their proposed method.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- This paper provides a clear rationale for introducing the two proposed metrics; the authors empirically demonstrate the importance of the metrics via two experiments. First, experiments conducted on the NAS benchmark reveal a strong correlation between the two metrics and the final performance of sparse networks. Secondly, through layer shuffling experiments, the authors illustrate that simply increasing the number of effective nodes in the extreme sparsity regime is insufficient to prevent performance degradation due to the sharp decline in the number of effective paths.\n- The proposed method demonstrates superior performance compared to the baselines, and the paper covers a fair amount of relevant previous studies.\n- The paper is effectively structured and exhibits clear and concise writing\n", "weaknesses": "- While many previous PaI methods prioritize the weight magnitude as the importance metric, the main motivation behind NPB focuses on the topology of the sparse network. Thus, the ablation study with respect to different weight initialization would strengthen the paper. Further, is NPB robust to *weight reinitialization*?\n- While the layer shuffling experiments are well-justified, it is confined to a single configuration (CIFAR-10, ResNet20). I wonder if similar observations can be made under different experimental settings. Also, does layer-wise shuffled NPB exhibit similar behavior as to layer-wise shuffled PHEW?\n- There are two points in need of clarification. First, in lines 332-333, the term \"chunks\" is unclear, and it is not apparent how the parallel computation can be effectively achieved. Second, in the case of convolutional layers mentioned in lines 261-263, it is unclear whether equations 3-5 are still applicable when the mask vector is not boolean.\n- Although the authors claim that NPB generally outperforms PHEW, the standard deviation with respect to random seeds should be included in the paper for fair comparison. For instance, the performance gain depicted in Fig. 7 seems marginal. Additionally, in lines 694-695, it is stated that NPB consistently outperforms the baselines regardless of the hyperparameter configuration. However, it should be noted that certain choices may lead to worse performance compared to the baselines (refer to Table 1).\n\nI am willing to raise my score if above concerns are well addressed during rebuttal.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the time to review our work. We would like to address all weaknesses pointed out by you point-by-point below:\n> Q1. While many previous PaI methods prioritize the weight magnitude as the importance metric, the main motivation behind NPB focuses on the topology of the sparse network. Thus, the ablation study with respect to different weight initialization would strengthen the paper. Further, is NPB robust to weight reinitialization?\n>\nA1: We appreciate your suggestion for enhancing our paper. In response, we conducted experiments with different weight initializations for NPB on setting ResNet20 on CIFAR-10 and visualized it in Figure 2 in attached file. In our paper, we use Kaiming Normal initialize network weight. The result shows that different weight initializations only affect the performance of subnetworks. While the number of effective nodes remains relatively consistent across different initializations, a minor variation can be observed in the number of effective paths between subnetworks. This discrepancy is attributed to the distribution of remaining weights within the convolutional layers' kernels. This experiment demonstrates that NPB exhibits robustness to different weight reinitializations.\n> Q2. While the layer shuffling experiments are well-justified, it is confined to a single configuration (CIFAR-10, ResNet20). I wonder if similar observations can be made under different experimental settings.\n>\nA2: We have run additional layer-wise shuffling experiments with VGG19 on CIFAR-10 with SynFlow and SNIP. We visualize the results on Figure 3 in the attached file. In general, this experiment shows the same behavior with which in setting ResNet20 on CIFAR-10.\n> Q3. Also, does layer-wise shuffled NPB exhibit similar behavior as to layer-wise shuffled PHEW?\n>\nA3:  We have run shuffling experiments for NPB with setting ResNet20 on CIFAR-10 and reported in Table 1 in attached file. After shuffling subnetworks found by NPB, the subnetworks' width broaden while the figure for paths drops significantly as the level of sparsity increases. However, similar to PHEW, the performance of unmodified subnetworks is better than the shuffled counterparts.\n> Q4. There are two points in need of clarification. First, in lines 332-333, the term \"chunks\" is unclear, and it is not apparent how the parallel computation can be effectively achieved. Second, in the case of convolutional layers mentioned in lines 261-263, it is unclear whether equations 3-5 are still applicable when the mask vector is not boolean.\n>\nA4: To be more specific, we consider layer $l$ with mask $\\mathbf{m}^{(l)} \\in \\mathbb{R}^{h^{(l)} \\times h^{(l+1)}}$ in which $h^{(l)}$ and $h^{(l+1)}$ are the number of nodes in layer $l$ and $l+1$. We divide $h^{(l+1)}$ nodes into $K$ equal chunks.\nInstead of directly solving for $\\mathbf{m}^{(l)}$, we solve $K$ problems $[\\mathbf{m}^{(l)}_1, \\mathbf{m}^{(l)}_2,  ..., \\mathbf{m}^{(l)}_K ]$ where $ \\mathbf{m}^{(l)}_k \\in \\mathbb{R}^{h^{(l)} \\times h^{(l+1)}_k}$.\n\nWith convolutional layers, we consider a kernel as a connection in linear layer (please refer to Figure 1). The mask $\\mathbf{M} \\in \\mathbb{R}^{c_{in}, c_{out}, h, w}$ with binary entries will transform to $\\mathbf{M}’ \\in \\mathbb{R}^{c_{in}, c_{out}}$ with an entry $m_{i,j} \\in \\mathbb{N}$ with values from 0 to hw. Then, we treat M as an integer variable, and we leverage an available optimization library (CVXPY library) to solve the mixed integer programming problem.\n> Q5. Although the authors claim that NPB generally outperforms PHEW, the standard deviation with respect to random seeds should be included in the paper for fair comparison. For instance, the performance gain depicted in Fig. 7 seems marginal. Additionally, in lines 694-695, it is stated that NPB consistently outperforms the baselines regardless of the hyperparameter configuration. However, it should be noted that certain choices may lead to worse performance compared to the baselines (refer to Table 1).\n>\nA5: We appreciate your feedback. We will incorporate standard deviation in the next version. Regarding the statement in lines 694-695, we appreciate your observation. We intend to clarify our claim to accurately reflect that NPB generally outperforms the baselines, and while certain hyperparameter configurations might lead to slightly reduced performance compared to PHEW. Overall, we believe that our findings still highlight the competitiveness and effectiveness of NPB.\n> Q6. In equation 3, what is the purpose of “min” operation? Or is it just a typo of $min(m_{i,j}^l - 1, 0)$\n>\nA6: The \"min\" operation in Eq. 3 serves the purpose of transforming the formulation to a version that is compatible with convex optimization library. We acknowledge the error, it indeed should be $min(m_{i,j}^l - 1, 0)$. We will rectify it in the next version.\n> Q7. What kind of optimizer is implemented in the code as to approximating the original integer programming formulation?\n>\nA7: The optimization problem is solved efficiently via the available convex optimization library (CVXPY library) in which we use the default solver for mixed integer programming named SCIPY [1].\n\n[1] https://www.cvxpy.org/tutorial/advanced/index.html#setting-solver-options\n> Q8. It is equally important for the authors to acknowledge and discuss the limitations of their proposed method.\n>\nA8: We appreciate your feedback. We would like to acknowledge the following limitations of our approach:\n- Global Optimization of Node-Path Balancing: Our method has not achieved global optimization of node-path balancing. The intricate relationship between effective nodes and paths presents a complex optimization challenge that remains a subject of ongoing exploration.\n- Discrete Optimization: The current form of our method involves discrete optimization. This can potentially limit applications such as applying NPB as a criterion in prune during training, or in Neural Architecture Search problems."}, {"review_id": "1b8E8e64Yk", "reviewer": "Reviewer_ygEG", "summary": "The authors perform a large-scale empirical analysis of models from the NAS-Bench-Macro benchmark which motivates to the development of (1) the node-path balancing principle and (2) Node-Path Balancing Pruner (NPB) -- a data-agnostic pruning-at-initialization (PAI) scheme. At a high level, the node-path balancing principle suggests that networks that have a good balance between the number of nodes and edges on a continuous/unbroken path from the neural network input to the neural network have a higher capacity for performance (i.e. classification accuracy). Their pruning algorithm, NPB, then solves a constrained optimization problem to strike this node-path balance for a given sparsity level. The driving factor for this research is to design advanced PAI algorithms for producing efficient models with better performance (i.e., classification accuracy) than existing PAI schemes.\n\n**Main contributions:**\n\n* Node-path balancing principle: Empirical analysis of NAS-Bench-Macro benchmark yields new perspective and principle for guiding design of pruning-at-initialization (PAI) schemes.\n* NPB: A novel data-agnostic PAI scheme designed using the node-path balancing principle which outperforms existing PAI methods at lower FLOPs during inference.\n\n**Post-rebuttal revision:**\n\nFollowing the rebuttal, I feel that the authors have clarified my questions and concerns. Accordingly, I am increasing my rating to weak accept with the expectation that they will accommodate my requested minor revisions.\n", "questions": "1. How did you compute/measure the FLOPs presented in Table 1? I may have missed something, but I did not see an explanation in the main body or in the appendix. \n2. Did you observe training/inference speedup due to reduced FLOPs? If so, it would be worth mentioning as NPB tends to require fewer FLOPs than other methods (at least at sparsity >= 90%).\n3. In some instances, models appear to have very different balance of nodes and paths but comparable accuracy (e.g., ResNet20 on CIFAR-10 sparsity 99%, VGG19 on CIFAR-100 sparsity 90%) or similar balance of nodes and paths but very different accuracy (VGG19 on CIFAR-100 sparsity 68.38%, ResNet18 on Tiny-Imagenet sparsity 90%). How would your principle in its current form explain this?\n\nComments about figures:\n\n* **Figure 3**: I had to stare at this for a while to figure out what the takeaway was. It seems that more effective nodes can help improve accuracy, but it is not enough on its own. I’m not sure if there is a different way to present the data to make it more readily apparent (and I’m not counting it against you) but I just wanted to mention it.\n* **Figure 4**: I think the scale of the accuracy colormap should be the same across all 4 plots (i.e. darkest blue is min accuracy across all 4 plots ~65% and yellow is max across all 4 plots ~93%). Then accuracy diversity across the four groups would be more apparent (i.e. more params -> higher accuracy) and you could just have a single colorbar.\n* **Figure 5**: For each dataset (i.e. row) I think the x- and y-axis range should be the same across the four plots. This revision should better highlight trends/changes in node-path balance with increasing sparsity. \n", "limitations": "Repeating a weakness here as I believe it is a limitation that is not acknowledged/discussed:\n\n* **Looseness/inexactness of the node-path balancing principle**: I found the statement/rigor of this guiding principle (which was used to inform the design of NPB) to be very inexact. The motivating plots in Figure 4 suggest that there is nuance between this node-path balance and the resulting classification accuracy, but this was not further explored. Specifically, some networks with similar node-path balance in Figure 4 appear to have large variations in classification accuracy.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Large scale analysis of NAS-Bench-Macro benchmark models suggesting connection between model performance and balance of effective nodes and paths.\n* **NPB pruning-at-initialization algorithm**: Produces results comparable to state-of-the-art PAI scheme PHEW with fewer FLOPs during inference.\n", "weaknesses": "* **Looseness/inexactness of the node-path balancing principle**: I found the statement/rigor of this guiding principle (which was used to inform the design of NPB) to be very inexact. The motivating plots in Figure 4 suggest that there is nuance between this node-path balance and the resulting classification accuracy, but this was not further explored. Specifically, some networks with similar node-path balance in Figure 4 appear to have large variations in classification accuracy.\n* **Lack of theory for node-path balancing principle**: Developing theory to study the principle would help design/inform a more exact guiding principle for PAI schemes.\n* **Figure clarity**: It was not always evident what the takeaway is from certain figures and I feel that the presentation of certain figures could be improved. I found myself staring at some figures for a while trying to decipher what was important/meaningful as there is a lot of data. This isn’t to say there is not meaningful information in the figures but I feel like more careful curation/design of the figures could be enacted. For suggestions/specific figures, see comments under “Questions”.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the time to review our work. We would like to address all weaknesses pointed out by you point-by-point below:\n> Q1. Looseness/inexactness of the node-path balancing principle\n>\n\nA1: In Neural Architecture Search (NAS) context, it's important to consider that other aspects beyond node-path balance can contribute to final classification accuracy. In the case of NAS-Bench-Macro, networks with similar node-path balance but varying classification accuracies can be affected by other architectural configurations, such as differences in pooling layers, kernel sizes, and expansion ratios in the MobileNet-v2 block. These architectural variances often result in different numbers of parameters, influencing the overall network performance.\n\nHowever, in pruning context, pruning methods focus on maintaining the same network structure while pruning connections within the network based on specific sparsities. Consequently, our experiments did not explore other architectural elements beyond node and path balance.\n\nWe emphasize that our experiments with NAS demonstrated that networks with balanced nodes and paths tend to exhibit superior performance. Based on these findings, we have taken the step to use the balance between two metrics as a fundamental criterion for designing pruning methods.\n\n> Q2. Lack of theory for node-path balancing principle.\n> \n\nA2: We agree that our paper is not a theoretical study. However, the underlying motivations for our method are justified and easy to understand. Let us recall that focusing on optimization of either nodes or paths will lead to a loss on the remaining quantity, which leads to suboptimal performance. This statement is intuitive and we think that unnecessary theoretical analysis would add little to our paper at this stage. The key theoretical challenge here is the problem of identifying the balancing points and the precise relation between node-path and performance. These are difficult research problems in their own rights, and we postpone them to future work.\n\n\n> Q3. How did you compute/measure the FLOPs presented in Table 1?\n> \n\nA3: We appreciate your inquiry regarding the computation of FLOPs presented in Table 1. To derive the FLOPs values, we adopted the methodology outlined in [1]. It's worth noting that the FLOPs calculation is performed on a layer-by-layer basis. At each layer, the FLOPs are computed by considering the number of parameters, the input size of the layer, and the layer's sparsity.\nWe will incorporate the explanation of the FLOPs measurement methodology in the revised version of the paper.\n\n[1] https://github.com/Eric-mingjie/rethinking-network-pruning/blob/master/cifar/weight-level/count_flops.py\n\n> Q4. Did you observe training/inference speedup due to reduced FLOPs? If so, it would be worth mentioning as NPB tends to require fewer FLOPs than other methods (at least at sparsity >= 90%).\n> \n\nA4: We appreciate your interest in the potential speedup resulting from reduced FLOPs in our proposed method. In the case of NPB, which employs unstructured pruning similar to other PaI methods, we currently provide theoretical FLOPs measurements rather than real-world speedup figures. This limitation arises from the constrained support available from off-the-shelf GPUs for unstructured pruning techniques.\n\nHowever, it's important to note that while unstructured pruning may not exhibit real-time speedups presently, it remains a valuable mathematical framework and an empirical testbed for exploring novel Sparse Neural Network algorithms. Furthermore, there is a growing trend of improved practical support for unstructured pruning in the field [2].\n\n[2] https://arxiv.org/abs/2302.02596\n\n> Q5. In some instances, models appear to have very different balance of nodes and paths but comparable accuracy (e.g., ResNet20 on CIFAR-10 sparsity 99%, VGG19 on CIFAR-100 sparsity 90%) or similar balance of nodes and paths but very different accuracy (VGG19 on CIFAR-100 sparsity 68.38%, ResNet18 on Tiny-Imagenet sparsity 90%). How would your principle in its current form explain this?\n> \n\nA5: The disparities in accuracy, as you noted, can stem from various factors such as the number of effective parameters (as defined in Appendix B), the distribution of unpruned weights within kernels, and more. These intricacies can lead to differences in performance despite comparable or dissimilar node-path balances.\n\nHowever, a general trend can still be discerned. We find that when the number of active neurons and input-output paths of a sparse network align within the balancing range, there tends to be a likelihood of achieving superior performance after training.\n\n> Q6. Figure 3: I had to stare at this for a while to figure out what the takeaway was. It seems that more effective nodes can help improve accuracy, but it is not enough on its own.\n> \n\nA6: Thank you for your time and consideration. Indeed, Figure 3 shows more nodes can help enhance performance but it is not always the case. Apart from nodes, paths play an important role in the quality of subnetworks. These two metrics mutual impact on each other. Therefore, we conjecture that to create optimal subnetwork, we should take both nodes and paths into account.\n\n> Q7. Figure 4: I think the scale of the accuracy colormap should be the same across all 4 plots. Then accuracy diversity across the four groups would be more apparent (i.e. more params -> higher accuracy) and you could just have a single colorbar.\n> \n\nA7: Thank you for your suggestions to improve our paper. We will revise the figure and update it in the next version.\n\n> Q8. Figure 5: For each dataset (i.e. row) I think the x- and y-axis range should be the same across the four plots. This revision should better highlight trends/changes in node-path balance with increasing sparsity.\n> \n\nA8: Thank you for your suggestions to improve our paper. We will revise the figure and update it in the next version."}]

Author rebuttal:
Thank you for your valuable and constructive feedbacks. We have performed the additional experiments as requested by the reviewers and have provided the results in this pdf file. 
We hope that our responses address your concern. If you have any additional questions, uncertainties, or areas you would like us to elaborate on, we are happy to engage in a continued discussion and provide any additional information you may require. 

Meta-review: The paper provides a technique for pruning networks at initialization (PaI). The method provided relies on an observation that there exists a correlation between the performance of a network and the balance between the effective nodes and effective path. The reviews agree that this approach is novel, and furthermore, that the main hypothesis is explained well along with convincing arguments and experiments for its correctness. Given the large amount of works dealing with pruning, having a novel technique makes this paper appealing. The main concern raised for the paper is the quality of its writing. This was explicitly mentioned in some reviews and implicitly in others that had many clarification questions. This being said, the required edits are listed in the discussion here, and the task of integrating these changes towards a final version seems feasible to me. Given this and the mentioned strengths of the paper, I recommend its acceptance.
Decision: Accept (poster)