Understanding Pruning at Initialization: An Effective Node-Path Balancing Perspective
Authors: Hoang Pham
Anh Ta
Shiwei Liu
Dung D. Le
Long Tran-Thanh
Venue: Submitted to ICLR 2023 (2023)
Keywords: Pruning Neural Network
Sparsity

Abstract: Pruning at initialization (PaI) methods aim to remove weights of neural networks before training in pursuit of reducing training costs. While current PaI methods are promising and outperform random pruning, much work remains to be done to understand and improve PaI methods to achieve the performance of pruning after training. In particular, recent studies (Frankle et al., 2021; Su et al., 2020) present empirical evidence for the potential of PaI, and show intriguing properties like layerwise random shuffling connections of pruned networks preserves or even improves the performance. Our paper gives new perspectives on PaI from the geometry of subnetwork configurations. We propose to use two quantities to probe the shape of subnetworks: the numbers of effective paths and effective nodes (or channels). Using these numbers, we provide a principled framework to better understand PaI methods. Our main findings are: (i) the width of subnetworks matters in regular sparsity levels (< 99%) - this matches the competitive performance of shuffled layerwise subnetworks; (ii) node-path balancing plays a critical role in the quality of PaI subnetworks, especially in extreme sparsity regimes. These innovate an important direction to network pruning that takes into account the subnetwork topology itself. To illustrate the promise of this direction, we present a fairly naive method based on SynFlow (Tanaka et al., 2020) and conduct extensive experiments on different architectures and datasets to demonstrate its effectiveness.

Under review as a conference paper at ICLR 2023
UNDERSTANDING PRUNING AT INITIALIZATION: AN EFFECTIVE NODE-PATH BALANCING PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
Pruning at initialization (PaI) methods aim to remove weights of neural networks before training in pursuit of reducing training costs. While current Pal methods are promising and outperform random pruning, much work remains to be done to understand and improve Pal methods to achieve the performance of pruning after training. In particular, recent studies (Frankle et al.) 1021 Suu et al. 2020) present empirical evidence for the potential Pal, and show intriguing proper- ties like layerwise random shuffling connections of pruned networks preserves or even improves the performance. Our paper gives new perspectives on Pal from the geometry of subnetwork configurations. We propose to use two quantities probe the shape of subnetworks: the numbers of effective paths and effective nodes (or channels). Using these numbers, we provide a principled framework to better understand Pal methods. Our main findings are: (i) the width of subnet- works matters regular sparsity levels (< 99%) this matches the competitive performance of shuffled layerwise subnetworks; (ii) node-path balancing plays a critical role in the quality of Pal subnetworks, especially in extreme sparsity regimes. These innovate an important direction to network pruning that takes into account the subnetwork topology itself. To illustrate the promise of this direction, we present a fairly naive method based on SynFlow ęTanaka et al. 2020) and con- duct extensive experiments different architectures and datasets to demonstrate its effectivvness.
INTRODUCTION
Deep neural networks have achieved state-of-the-art performance in wide range of machine learn- ing applications (Brown et al., 2020: Dosovitskiy et al. [202]] Ramesh et al., 2021 Radford et al., 2021). However, the huge computational resource requirements limit their applications, especially
in edge computing and other future smart physical systems (Hinton et al., 2015 Zhao et al. 2019 Price & Tanner 2021; Yuan et al. [02T Bithika et al., 2022). To overcome this issue, there has been a number of attempts to reduce the size of such networks without compromising their performance, among which praming enjoys sigmificant interest (Hoetler et al.) [022T] Deng et al.) 2020 Cheng et al. 2018). rationale for this direction is the work of Frankle & Carbin (2018), in which the authors provide empirical evidences on the existence of sparse subnetworks that can be trained from scratch and achieve similar performance to the original network, referred to as the Lot- tery Tickets. However, standard methods for finding such subnetworks typically involve the costly pre-training and iterative magnitude pruning process.
This issue raises an intriguing research question: How to identify sparse, trainable subnetworks at initialization without traininn? Specifically, a successful pruning before training method can sig- nificantly reduce both the cost of memory and runtime, without sacrificing performance much (Wang et al. 2022). This would make neural networks applicable even in scenarios with scarce comput- ing resources (Alizadeh al. 20222 Yuan et al. 2021). As such, many methods for Pal have been proposed Lee et al.] 2019); Tanaka et al.) 2020 de Jorge et al. 2021 Wang et al., 2020: Alizadeh et al. 2022). While these methods are based on a number of intuitions (e.g., leveraging the gradient information), they typically measure the importance of network parameters. More recently, |Frnnkee et al. (202T): Su et al. (2020) observe a rather surprising phenomenon: for Pal methods, layerwise shuffling connections of pruned subnetworks does not reduce the network's 's performance. A surpris- ing consequence is that layerwise sparsity ratios are more important than weight-level importance scores of the subnetwork (Frankle al. 2021). This indicates that in searching for good subnet-

---

Under review as a conference paper at ICLR 2023
works at initialization, the topology of subnetworks, in particular the number of input-output paths and active nodes, plays a vital role and should be investigated more extensively.
While the findings of previous works Frankle et al. (222]) Su et al. (2020) indicate that Pal methods are insensitive to random shuffling, we find this is not true in the extreme sparsity regime (> 99%) in which the number of effective connections in subnetworks are vulnerable to changes to shuffling. In layerwise shuffling experiments (see Section (.3) shuffling connections results in more effec- tive nodes but substantially fewer input-output paths. In normal sparsity levels, shuffling weights in regular sparsities can maintain and even increase effective parameters (Frankle et al. 2021 and the number of activated nodes (Patil Dovrolis (02T). Having more effective nodes after shuf- fling helps the representation capacity of subnetworks enhance while the number of effective paths enough for preserving the information flow, leading competitive or even better performance of shuffled subnetworks (Section 3.3). However, we empirically show that in the extreme sparsity levels, while shuffling still more or less preserves the number of remaining attached nodes, the per- formance of shuffled subnetworks may drop significantly, compared to the unshuffled counterpart. This is because the information flow is hampered due to the significant decrease of the input-output paths. These findings suggest that separately considering effective paths or nodes is inadequate to fully capture behaviors of subnetworks generated by Pal methods.
In addition, we design a simple toy experiment in which an MIP network is considered as a base architecture. We then randomly generate 100 subnetworks at the same sparsity level 95% while ensuring that all nodes input and out- put layers are activated, all networks are trained to converge with the same setting and tested on MNIST dataset (more details in Appendix IT). As depicted in Figure D these subnetworks have different effective nodes and paths. We observe that subnetworks with higher in both the number of nodes and paths tend to have bet- ter performance. This highlights the essential role of simultaneously considering both node and path in the success of designing subnetworks at initialization.
Sparsity 95%
Accuraicy (16)
40000
35000
38000
35000
850
8.00
870
880
850
500
910
The number of offfecttiv nodes
Figure 1: Toy experiment with 100 subnetworks randomly generated from the base MLP network.
To overcome this issue, we introduce a novel framework that combines metrics mentioned in pre- vious works (Tanaka et al., 2020 Patil & Dovrolis 2021 Frankle et al., 2021) to provide more accurate explanation of the performance of different approaches. In particular, we propose the joint usage of both the number of input-output paths ka. effective paths) and activated (i.c., effective) nodes to explain different behaviors of Pal methods in more comprehensive way (see Section 3.3 for more details). We also demonstrate the usefulness of this framework as follows: With simple modification in the base of the iterative pruning algorithm, we show that if maintain both the effective path and node level high simultancously, the quality of subnetworks will be enhanced.
In summary, main contributions are:
We propose to systematically use the topology of subnetworks, particularly the number of effective nodes and paths, as proxies for the performance of Pal methods (Section 3 We revisit the layerwise shuffling sanity check on subnetworks produced by existing Pal methods and provide unified explanations for their behaviors based on these metrics in a wide range of sparsities (Section 3.3
We discover a new relation between the proposed metrics and the performance of sub- networks, termed the Node-Path Balancing Principle, that suggests a nontrivial balance between nodes and paths is necessary for optimal performance of Pal methods (Section 4. We introduce a simple modification of SynFlow (Tanaka et al. 2020) to give a proof-of- concept for our principle. We perform extensive experiments to show that better balancing this tra in pruned networks leads to improved performance (Section
Our framework opens novel research direction that advocates taking into account both paths and nodes in the design of Pal methods. More precisely, while the regular sparsity regime places effective nodes in a higher priority than effective paths, extremely sparse subnetworks demand more delicate balance between these two metrics (Section 5).
2

---

Under review as a conference paper at ICLR 2023
2 RELATED WORK
Neural Network Pruning. Neural network pruning methods (LeCun et al. 1989; Hassibi et al.
1993 Han et al. 2015) traditionally focus on pruning trained models based on pre-defined criteria, and then resulting subnetworks will be fine-tuned to converge. Recently, |Frankle & Carbin (2018);
Frankle al. (2020) 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 highly overhead due to the train and prune cycle. Gradual pruning methods (Zhu & Gupta 2017; Gale et al. 2019)
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. Pruning before training methods (Lee et al. 2019 Wang et al. [020 Patil & Dovrolis 2021; Tanaka et al. [020;] Allizddhh
al., (022) determine subnetworks by the network initialization, gradient information. and network topology. However, experimentally results done by [rranlle et al. (202T); (Su et (2020) show that
proposed Pal criteria are not essential for obtaining subnetwork with good performance.
Pruning and nefwork shape. Since Pal methods do not utilize training data or use only negligible portions of data to obtain gradient information without training, the configuration of nodes and con- nections 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 shape. In particular, SynFlow Tanaka et al. 2020) preserves the number of input-output paths as synaptic strength, but TynFlowTTanaka
often creates more isolated neurons in pruned networks. The works Patil & Dovrolis (202I) and Gebhart et al. (2021) aim to preserve proxies in terms of path kernels which are also directly related to the shape of subnetworks. Furthermore, while PHEW (Patil & Dovrolis 202T) additionally im- plements 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 capture the capacity of pruned subnetworks (Wang et al. 2020 Naji et al. 202T) where these numbers are considered separately.
Extreme Sparse Network. In the context of extreme sparsity (Cho et al. 2021 Price & Tanner 2021). the network density is less than 1%. Cho al. (2021) associate two works from Lee et al. (2019) Zhou et al. al.] (2019) for learning the masking during training. Tanaka et al. (2020): de Jorge et (202 Vysogorrss & (2021) leverage iterative pruning keep subnetworks from layer collapse in super sparsity cases. [Price Tanner (202T) only require an extremely small amount of trainable parameters associated with a freeze fully connected network, which helps the model performs well on extreme sparsity settings. This suggests that preserving information flow through network connections plays a crucial role in intense sparse networks.
METHODOLOGY
3.1 PRUNING AT INITIALIZATION METHODS
Given a neural network, we first devide the network into layers: é= 0 is the input layer, then for each layer E 21, L}. we flatten the weights on the connections from layer & to layer E into a weight vector Wy E Rdd, where de the number of connections from layer é- to layer f. Let w (W1, ...., ) denote the set of weights. Pruning generates binary mask vectors my E {0, 1 yielding sparse neural networks with sparse weights my @ We the elementwise product of masks Σ mi E [0. 1]. and weights Sparsity is defined as the fraction of weights being removed: s = Ed
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 weights: 2t score(ws) R then remove takes as input the scores z = (21,..., =1) and the sparsity s, and outputs the masks m with overall sparsity Pruning can be done in one-shot iteratively. For one-shot pruning, we only generate the scores once, then prune the network upto sparsity s. For iterative pruning, we repeat the processes of score, then prune from sparsity 1t-T to sparsity s*/T iteratively T times.
Random. This method assigns each connection with a random score from a uniform distribution (( 1). Random pruning empirically prunes each layer target sparsity s (Liu et al. 2022
3

---

Under review as a conference paper at ICLR 2023
b
d
0
0
1
2
0
0
5
Effective node
Ineffective node
Pruned node
Effective path
Figure 2: An example of effective paths and effective nodes.
SNIP. SNIP was introduced by Lee et al. (2019) with the pruning objective of reducing connection sensitivity to the training loss. One passes mini-batch of data through the network and compute the score for weight w of SNIP as z w @ V W..
This is iterative variant of SNIP (de Jorge et al., 2021) with the same important score. But, iterative SNIP gradually prunes the remaining weights with lowest scores from sparsity - to sparsity sf iteratively T times for f = 1,2.....
Iterative SNIP.
SynFlow. SynFlow (Tanaka et al., 2020) is an iterative and data-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 as follows. One first replaces all weights in the network by their absolute values. Then, an input tensor passed through the network, and one computes the sum of the logits as R = 1 T (Tl= |wss))1. Finally, the score of weight w is computed as @ R.. SynFlow prunes the network iteratively T times.
PHEW. PHEW (Patil & Dovrolis 202I) 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 start from a unit that is selected through round robin procedure. This process continues until the subnetwork achieves the predefined sparsity.
3.2 METRIC DEFINITION
In sparse network, is intuitively clear that should arrange the connections into configuration neither too thin nor too spread-out to have good information propagation during training. For a better measurement, propose using two metrics to evaluate the quality of subnetworks. Please refer to Appendix
B for detailed discussions and Python code for calculating the metrics.
We define path to be effective if it connects an input node to an output node without interruption (see Figure 2). Metrics based on paths are mentioned in [anaka et al.) (2020); Gebhart et al. (2021) as l and l2 path norms, respectively. In this paper, we only take into account the number of paths.
Effective path.
Effective node/channel. An effective node/channel is one that at least one effective path goes through it (demonstrated as the right part in Figure 2 This concept is also considered in works of
Patil Dovrolis (2021); Frankle et al. 22221) }. For convolutional layers, we consider a kernel as
connection, and channel as a node, and then convert the convolutional layer into a fully connected
layer. An illustrative example can be found in Figure 2
In the following sections, we compute and visualize the ratio of these metrics. In particular, we take logarithm scale of the number of effective paths and calculate the ratio of the pruned network and the dense ones, since effective paths have very large values. With effective nodes, we simply compute the ratio of the number of effective nodes between after and before pruning.
3.3 LAYERWISE SHUFFLING PHENOMENON
In this section, we investigate the intriguing phenomenon that layer- reshuffling the subnetwork found by Pal methods still produces competitive accuracy (Frankle et al.) 2021] Su et al.) 2020). Based on metrics, we provide new way understand why reshufiling subnetworks work and when they fail. We first use three Pal methods, i.e., SNIP (Lee et al. 2019), SynFlow (Tanaka et al. 2020), and PHEW (Patil & Dovrolis 2021), to find the subnetworks. Then, randomly shuffle
4

---

Under review as a conference paper at ICLR 2023
08-20e 2413 mub
Accussor INC
SNNP
0.66
Staffidd
Stulked
Staffic Lop
66:38
00.10
16:01
60.03
00.11
09.03
09.32
16.90
92.0 96.0
90.00
99.44
04.22
00.50
08:38
66.30
16.11
50.00
00.11
09.08
06.02
$6.90
SyaFlow
64
Sarifed over
Surtee perr di Ure-STee
50:20 20.00 25.04
92.00
22.44
20.00
20.02
20.50
06.33
30.03 5604
50.01
50.41
20.50
20:02
$0.00
50:00
20.00 05.44
92.00
9264
20 10.00
20 50.50
PHEW
Stufied Laperwa Layanalss (erreffle)
Staffed Lagerdts Unmodlee
23-
-Suffed LayarAlt
10.35 20:21 1654
55.07
20:44
59.55
25.52
15.00
30.00
3584
55.0
93.44
53.6
25.82
50
16.35
30.30
3654
50.03
50.44 33.00 35.52 $550
Ours
1.5
SNP
SKP
SSERIN
2.0
22.00
Sporsity
Seanty 290
Figure 3: Layerwise shuffling results on various sparse subnetworks of ResNet20 produced by SNIP, SynFlow, and PHEW at initialization on CIFAR-10.
the pruning mask my All the subnetworks (both unmodified and shuffled) are trained in the same setting. Finally, we calculate metrics and visualize the average scores in Figure
In SNIP and SynFlow, the number of effective nodes drops significantly sparsity increases, pecially SynFlow by using iterative pruning procedure. After reshuffling, the connections are dis- tributed uniformly in each layer. As a result, the number of effective nodes increases leading to essentially 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, reshufiling hurts the concrete network configuration, then reduces both the number of effective nodes and effective paths as sparsity is higher.
In normal sparsity cases, layerwise shuffled subnetworks show competitive performance even bet- ter (with SynFlow and SNIP) compared with unmodified ones. In addition to the explanation based on the effective connection preservation from Frankle et al. (202T). we provide a more comprehen- sive heuristic reason to understand this phenomenon. 99%), shuffled subnetworks with SynFlow and SNIP still ensure the information flow from input to output through enough effective paths, meanwhile the representation capacity of subnetworks is increased due to the growth in the number of effective nodes. In more detail, Figure 3 shows that the number of effective nodes and effective paths of shuffled layerwise subnetworks produced by SynFlow and SNIP are similar to unmodified subnetworks of PHEW with corresponding sparsitics. It suggests that the effective network width is more vital in normal sparsity when the number of input-output paths is still enough to transfer information.
particular, at these sparsities (below ratio
However, in the extreme sparsity regime, random shuffling significantly reduces the performance of the subnetworks. Along with the reduction of the number of effective parameters (see Appendix (). the number of input-output paths decreases substantially when the network becomes more sparse. Even though layerwisely shuffled networks become wider, the limited number of effective paths hinders the information flows in the subnetworks. These explain why the accuracy of shuffled sub- networks is much lower than the unmodified ones in intensive sparsities.
These observations indicate that increasing the number of effective paths (SynFlow) or effective nodes (PHEW) alone is not sufficient in the design of Pal methods. We hypothesize that to have better subnetworks, the number of effective paths and effective nodes should be concurrently con-
5

---

Under review as a conference paper at ICLR 2023
sidered. If we balance these two metrics well, the performance after training of subnetworks will be enhanced, especially in extreme sparsity levels (see the last row Figure
NODE-PATH BALANCING PRINCIPLE
From observations in Section 3.3 and toy example in Appendix [ both effective paths and nodes have shown their critical roles in the performance of subnetworks. We now formally state the Node-Path Balancing Principle.
Node-Path Balancing Principle: The combination of both the numbers of effective nodes and effective paths is a proxy to potential performance of subnetworks under pruning. pruning at initialization method which produces pruned subnetworks with too many effective paths (resp. ef- fective nodes) will has less than necessary the number of effective nodes (resp. effective paths), and consequentially has suboptimal performance. It is necessary to balance the numbers of effective nodes and effective paths for better performance of pruned subnetworks.
Algorithm Iterative pruning algorithm to find a pruning mask
1: Inputs: Final sparsity s, number of pruning steps T', weights Winits De, mma
2: Obtain sparsity {st at each pruning iteration
3: Define intial mask mg =
4: Wo Winit mg
do 6: if t % A. and Tmax < t then
5: for t = 0, O,,..,,, ,'
7:
Find m, by Random pruning with sparsity st
8:
else
Find m by SynFlow pruning with sparsity st 10: end if
9:
11: W: = W @ m.
12: end for
Return: WT
Proposed Method. Here, we describe modification of the iterative pruming algorithm that better satisfies the Node-Path Balancing Principle. We choose SynFlow (Tanaka et al.) (020) the base method since solely focuses on optimizing effective paths, hence, the node-path balancing effect, resulted from our modifications, will be easy to observe. Leveraging the iterative pruning procedure of SynFlow, we introduce a new pruning scheduler balance effective nodes and paths by perform- ing random pruning at several pruning iterations. We arbitrarily replace the pruning criterion in some early iterations with random pruning. The justification for doing this is based the intuition that in iterative pruning methods like SynFlow if a node has some pruned connections (low-degree node) in the initial few iterations it has a higher likelihood of being detached in later iterations (Patil & Dovrolis 2021). Therefore, our method helps low-degree nodes avoid being removed at subsequent iterations since it randomly eliminates connections to high-degree units.
additional hyperparameters A, and Tiaz, which means in the first Tmaz pruning iteration, we use random pruning after each (A, 1) steps. The pseudo-code is in Algorithm[] [ Adjusting these two hyperparameters leads to different configurations of subnetworks. Intuitively. a large Tmaz casily drives subnetworks to layer-collapse since the pruner randomly re- moves important connections when the network is in intensive sparsity, which destroys a large num- ber of input-output paths. While randomly pruning the network when it is in normal sparsities may increase the subnetwork's 's width because it fortuitously prunes edges to high-degree nodes. More investigations on pruning scheduler are provided in Section 5.4 and Appendix
Specifically, we introduce
EXPERIMENT
5.1 EXPERIMENTAL SETTINGS
Architectures and Datasets. Our main experiments are conducted with CIFAR-10 and Tiny- Imagenet datasets. With CIFAR-10, we use ResNet-20 and VGG-19 from Tanaka et al. (2020). For ImageNet, utilize ResNet-18 18 with 18 layers adapted from Tanaka al. 2020) We

---

Under review as a conference paper at ICLR 2023
treat all of the weights from convolutional and linear layers of these networks are prunable parame- ters, but we do not prune the biases nor the weights in the batch normalization layers. run five seeds with CIFAR- 10 experiments and three seeds with experiments on Tiny-Imagened We take the average value of the results and plot them in visualizations. More details Appendix
5.2 EXPERIMENT ON REGULAR SPARSITIES
In Figure we show the results of different Pal methods with varied conventional sparsities on three settings: VGG-19 CIFAR-10, ResNet-20 CIFAR-10 and ResNet-18 Tiny-Imagenet. In all settings, we use A, and max = 15 for our method. Our main observations are below.
Effective node is more important in the normal sparsity regime. In normal sparsities (< 99%), PHEW, data-agnostic method, consistently performs better than other data-independent methods like SynFlow and Random, well as data- dependent methods like SNIP and Iter-SNIP. The second column in Figure shows that PHEW produces wider subnetworks associated with adequate num- ber of input-output paths (ratios > 40%) which attributes to its superior performance. Specifically, broader width enhances the representation potential of the subnetworks while having enough effec- tive paths preserves the information flow in the network Patil & Dovrolis (2021). These two factors together contribute to efficient training of pruned subnetworks leading to higher accuracy.
With the same number of effective nodes, the higher the number of effective paths, the better perfor- mance subnetworks will reach after training. In unn-Imagenet experiments, our methods, Random, and PHEW produce subnetworks with all nodes activated up to sparsity 99.00%. However, subnet- works generated by our method have slightly higher effective paths than PHEW and are significantly higher than that of Random, which results in improved performances. This behavior also happens in experiments with ResNet-20 where our method and SNIP have the same number activated units but Ours has more input-output paths.
VGG19 CIFAR-16
Effective node tablo
Top Ricurscyy (Ng)
0.8
0.4
0.2
1.0
ResNee200 CIFAR-10
0.8
Effective roce ratto
0.8
Top-1 Accuray/ 116
80
70
Effective
0.6
0.4
0.4
50
40
43.77
68.38
82.22
90.00
90.84
99.00
43.77
68.38
82.22
90.00
96.84
99.00
43.77
08.38
82.22
90.00
96.94
99.00
RosNed88 Taly Amngggnne
1.0
Effective path o8to
Effective naderatia
0.8
0.8
Accuracy
0.6
0.4
43.77
68.35
82.22
90.00
96.84
99.00
43.77
68:38
82.22
90.00
96.84
99.00
43.77
68.38
82.22 90.00 96.24
99.00
Randoom
SyrFlow
PHEW
Dense
Figure 4: The ratio of effective paths (after log scale), nodes after and before pruning, and the corresponding accuracy of different Pal methods on three datasets the regular sparsity regimes.
5.3 EXPERIMENT ON EXTREME SPARSITIES
In Figure 5 we show the results of different Pal methods with intensive sparsities. We summarize main observations below.
7

---

Under review as a conference paper at ICLR 2023
Extremely sparse subnetworks prefer effective paths effective nodes. In extreme sparsities (> 99%), with very limited parameters, despite the higher effective nodes, PHEW, SNIP, and Ran- dom prunings start performing poorly than iterative pruning methods like SynFlow and Iter-SNIP (see the first two rows Figure 5). We hypothesize that it is because both PHEW and Random pruning produce small numbers of input-ouiput paths (the effective path ratios are below 10%) which makes the pruned subnetworks contain great number of straight paths (lacks criss-cross nections). This hinders the optimization of subnetworks. However, if we better balance the trade-off between effective nodes and effective paths, the accuracy increases. For example, with experiments on CIFAR-10, our method increases subnetworks width compared with SynFlow and Iter-SNIP while the number of effective paths is much higher than PHEW. Therefore, the performance of pruned networks after training enhanced. Further discussions can be found Appendix [
With similar numbers of effective paths in extreme sparsities, subnetworks that have more effective nodes show better performance. We want highlight that is intractable force two methods to generate subnetworks with the same number of effective paths given a sparse ratio. Therefore, select some subnetworks having similar input-output paths in experiments. In experiments with ResNet-20 on CIFAR-I0 (the second row in Figure 5). our method and Iter-SNIP produce two subnetworks with similar numbers of effective paths in sparsities from 99.00% to 99.90%. However, our method produces broader subnetworks, which induces better performance.
1.0
VGG1I9 CIEAR-10
0.8
Offecivv node rabl
0.8
Top Accurasy 05)
0.4
0.6
0.4
0.2
0.0
0.0
99.00
89.44
99.68
99.82 99.90 99.94 99.99
99.00
99.44
99.68
99.82
99.90
99.94 99.99
99.00
99.44
99.68 99.82 99.90 99.94 99.99
0.6
RosNer20 CIFAR-H0
Effective node rabe
0.8
Top Accurscy (36)
80
0.4
60
Eflectvv
0.3
0.4
0.2
0.1
0.0
90.90 09
99.68
99.82 90:90 09.
ResNer18 Thy Amuggnet
1.0
Effedive path rato
0.6
0.8
Top Accuracy
0.4
0.6
Effective
0.4
20
0.2
0.2
0.0
Sparsity (%)
Sparsity (%)
Spansity (8)
Ra moloo
+ SNIP
Syniloo
-
Ite+-NIP
PHEW
Durs
Derse
Figure The ratio of effective paths (after log scale), nodes after and before pruning, and the corresponding accuracy of different Pal methods on three datasets in the extreme sparsity regimes.
The above experimental results bolster our Node-Path Balancing Principle. In particular, these find- ings indicate that pruning neural networks in the regular sparsity regime should give more consid- eration to the number of effective neurons since the information flow is conserved by the sufficient number of outut- paths. Meanwhile, when the sparsity level becomes balance between the number of paths and nodes leads to gains in performance of subnetworks.
extreme, a delicate
5.4 EXPERIMENTAL RESULTS WITH DIFFERENT PRUNING SCHEDULERS
In this part, we investigate how different choices of the scheduler in our method affect the perfor- mance of subnetworks through two hyperparameters: A and T Tmax- We first vary Tmaz {10, 15), A, {2,3) to add more random pruning in early iterations with the goal of avoiding layer-collapse in extremely sparse ratios. We also change the value of T Tmaz= (15, 20, 30, 40, 50, 60, 70, 80, 90)
8

---

Under review as a conference paper at ICLR 2023
with the fixed A, 5 to investigate how mao affects the subnetwork's structure. We visualized selected results in Figure more in Appendix G Our main observations are as follows.
Applying random priming during the pruning process creates large-width subnetworks in regular sparsity levels. In SynFlow, if neuron loses some connections in previous pruning iterations, has a high probability to be pruned in subsequent iterations as result of the decrease in the number of pathways that pass through that unit. Therefore, higher T max allows the pruner remove edges connecting to units that have more connections. This implicitly constructs wider subnetworks as shown in Figure and Appendix G
In extreme sparsity regimes, a large man significantly reduces the number of effective paths. When the subnetwork achieves specific high sparsity, randomly removing connections in the subnetwork more likely to destroy effective paths. This is presented in Figure 6 when Tmas 50 or even more severe with higher Tmax= 80.
Frequently using random pruming in the early stage of pruning generates subnenworks with better performance in extreme spursities. At the first few pruning iterations, subnetworks have high density, thus, randomly eliminating edges has less influence on preventing substantial drop of the number of effective paths. Moreover, it has effects on growing the chance of being kept for low-degree nodes. This is supported by the experimental results of red and blue lines in Figure
rabc
0.8
Utective mode mbo
80
0.6
0.6
60
0.4
20
68.38
96.84
99.04
99.02
99.90
68.38
96.84
99:44
99 82
99.94
68.38
96.84
99.44
99.9 82
99.94
Sparsity
1%)
Sparsity (56)
2-15
SyrFlow
Figure 6: Scheduler ablation with ResNet-20 on CIFAR-10. We vary the value of A, and T maaz and name schedulers as A,-Tmaze
CONCLUSION
In this work, we propose a new framework to study Pal methods via systematic uses of the config- uration of pruned subnetworks based two different metrics: the number of effective paths and the number of effective nodes of subnetworks. As proxies to performance Pal methods, we use these two metrics in combination. We discover new relation between these metrics, called Node-Path Balancing Principle. which guides the understanding and optimization of Pal methods. We then propose a simple method to demonstrate that nontrivial balancing of num- bers of effective paths and nodes can lead improved performance of Pal methods. Our framework provides unified explanations for the intriguing Layerwise Connection Reshuffling Phenomenon (Su al. 2020 Frankle et al.) 2021 of subnetworks produced by Pal methods in normal pruning spar- sity regime, as well as failure of this phenomenon in extreme sparsity levels. Our findings are supported by extensive experiments tive based on configuration of subnetworks, in terms of effective nodes and effective paths, provide new insights to the working mechanism of Pal methods, and opens new research directions on neural network pruning methods, well as designs of sparse neural network.
pruned networks of
different model architectures and datasets. Our new perspec-
In particular, our framework directly calls for attention to optimizing the number of effective nodes and effective paths. Guiding by the Node-Path Balancing Principle, our goal is to optimize the num- ber of activated nodes and paths at given sparsity levels without using data. A potential approach is to consider the pruning problem as multi-objective optimization problem. More precisely, our problem becomes given an architecture, find the optimal balance between effective paths and effec- live nodes with a given number of parameters. This is a non-trivial problem, but with the advances from multi-objective optimization literature, there many promising approaches.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohamed Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero- cost proxies for lightweight [nas). In International Conference Learning Representations, 2021. Utthttss:///o http::///pppeevveeeeeem net. for forum?i 500
Milad Alizadeh, Shyam A. Tailor, Luisa M Zintgraf. Joost van Amersfoort, Sebastian Farquhar, Nicholas Donald Lane, and Yarin Gal. Prospect pruning: Finding trainable weights at initializa- tion using meta-gradients. In International Conference Learning Representations, 2022. URL
htttp:://openrevil
net forum? i d= 9uwfcl1
Pal Bithika, Biswas Arindam, Kolay Sudeshna, Mitra Pabitra, and Basu Biswajit. A study on the ramanujan graph property of winning lottery tickets. In International Conference Machine Learning, volume 162, pp. 17186 7718-17701, 2022.
Tom Brown, Benjamin Mann, Nick Ryder. Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020..
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 35 (1):126-136, 2018.
Minsu Cho, Ameya Joshi, and Chinmay Hegde. Espn: Extremely sparse pruned networks. In 2021 IEEE Data Science and Learning Workshop (DSLW), pp. 1-8. IEEE, 2021.
Pau de Jorge, Amartya Sanyal, Harkirat Behl, Philip Torr, Grégory Rogez, and Puneet K. Dokania. Progressive skeletonization: Trimming more fat from a network at initialization. In International Conference Leurning Reprexentations, 2021. URthttps: woppneeveeii. net forum?
id= (d=$G=FFUUUUP1
Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(4): 485-532, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recogni- tion at scale. In International Conference on Learning Representations, 2021. URL https: 77 //openzeview.
VicbFaNNTT
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 1991):19772217,, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 10X3::88033036335 2018
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, pp- 3259-3269. PMLR, 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021. htRpstt:: ope.review. net/ forum? wewpuuun-------Vo---i..
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint urXiv:1902.09574 2019.
Thomas Gebhart, Udit Saxena, and Paul Schrater. A unified paths perspective for pruning at initial- ization. ArXiv, abs/2101.10552. 2021.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pp. 293-299. IEFF, 1993.
10

---

Under review as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.0255 2(7), 2015.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(1), jan 2021.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019. URL dd= Feeee/oouuttddBB1222
hittps://oee ptttp:://cpenreview. wttp:ewwwwwweeeeeee.eem.m Tatt/forungg Eorum?
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effeectiveness of random pruning: Return of the most naive baseline for sparse training. International Conference on Learning Representations, 2022. httptttts///pe::me
net wtw.rrommmnnn_oaaaa____
Seyed Majid Naji, Azra Abtahi, and Farokh Marvasti. Efficient sparse artificial neural networks. ArXiv, abs/2103.07674, 2021.
Shreyas Malakarjun Patil and Constantine Dovrolis. Phew: Constructing sparse networks that learn fast and generalize well without training data. In International Conference on Machine Learning, pp. 8432-8442. PMLR, 2021.
Ilan Price and Jared Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via subspace offset. In International Conference Machine Learning, pp- 8620-8629. PMLR, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748-8763. PMLR, 2021.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning. pp. 8821-8831 PMLR, 2021.
Kartik Sreenivasan, Jy yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Eric Xing, Kangwook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets ini- tialization. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances in Neural Information Processing Systems, 2022. Utthttps: /ttp:////peeeieeeeeeeeee /nt//iewweeee///eeeeo Forum?id Jpxd9 3u2vK-
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. Advances in Neural Information Processing Systems, 33:20390-20401, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 33:6377-633 2020.
Artem Vysogorets and Julia Kempe. Connectivity matters: Neural network pruning through the lens of effective sparsity. arXiv preprint 10Xiv:210..02.300 2021.
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. In International Conference on Learning Representations, 2020. URİ. https::/cpenrews net

---

Under review as a conference paper at ICLR 2023
Huan Wang, Can Qin, Yue Bai, Yulun Zhang, and Yun Fu. Recent advances neural network pruning at initialization. In Luc De Raedt (ed.), Proceedings of the Thirty-First International Joinl Conference Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pp- 5638 5645. ijcai.org. 2022. doi: 2244966/jcaii URL https: /tw.///ii.ooo orq//0. 24963/1jcame 2022/786
Geng Yuan, Xiaolong Ma, Wei Niu, Zhengang Li, Zhenglun Kong, Ning Liu, Yifan Gong, Zheng Zhan, Chaoyang He, Qing Jin, al. Mest: Accurate and fast memory-economic sparse training framework on the edge. Advances Neural Information Processing Systems, 34:20838-20888 2021.
Chiyuan Zhang, Samy Bengio, and Yoram Singer. Are all layers created equal? 2019.
Ritchie Zhao, Yuwei Hu, Jordan Dotzel, Chris De Sa, and Zhiru Zhang. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pp. 7543-7552. PMLR, 2019.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression, arXiv preprint arXiv: 17100077, 2017.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations, 2017. URU/atpps://ogeneeeiee..s net//orum??
id=r1Ue8Hcxq
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
12

---

Under review as a conference paper at ICLR 2023
A EXPERIMENT DETAILS
In this section, along with pruning at initialization (Pal) methods in the main text, we provide ex- perimental results with GraSP (Wang al. 2020). In particular, GraSP is another gradient-based pruning Pal that aims to preserve the gradient flow of sparse networks obtained by pruning. The score 2 of weight w in GraSP is computed as -w @ wH,, 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 conduct experiments on a single GTX 3090Ti and use Pytorch library. We adapt Tanaka et al. (2020) source code for SNIP, GraSP, SynFlow, and Random, and change the prume epochs to 100 for Iterative SNIP instead in SNIP. And we use the official code Patil & Dovrolis (021) for PHEW.
Datasets. Our main experiments are conducted with CIFAR- and Tiny-Imagenet datasets, where:
CIFAR-I0 is augmented by normalizing per-channel, randomly flipping horizontally.
Tiny-ImageNNet is augmented by normalizing per channel, cropping to 64x64, and randomly flipping horizontally.
Architectures. We use three different networks:
VGG-19 CIFAR-10 network used SynFlow (Tanaka et al. 2020). batch-normalizztioon version.
choose
ResNet-20 is a 20-layer CIFAR-10 10 version of ResNet created by He et al. (2016). This version has added batch normalization layers before each activation function.
ResNet-18 is a ImageNet version with 18 layers adapted from SynFlow Tanaka et al., 2020). 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 of these networks are prunable pa- rameters, but we do not prune the biases nor the weights the batch normalization layers. The weights in convolutional and linear layers are initialized with Kaiming normal, while biases are ini- tialized to zero. We run five seeds with CIFAR-10 experiments and three seeds with experiments on
Training details With Iterative pruning methods SNIP and SynFlow, we use 100 pruning epochs. With methods using training data like SNIP, GraSP, and Iterative-NNIP. we randomly select 10 samples for each class, particularly, 100 data points for CIFAR-10, 2000 data samples for Tiny- ImageNet. Other hyperparameters are chosen as follow:
Table 1: Summary of the architectures, datasets, and hyperparameters used in experiments.
Network
Dataset
Epochs
Batch
Optimizer
Momentum
LR
LR Drup. Epoch
Weight Decay
VGG-19
CIFAR-10
160
128
SGD
0.9
0.1
10x. [60,120]
0:0001
ResNet-20
CIFAR-10
160
128
0.9
0.1
10x. [60.120]
0.0001
ResNet-18
Tiny-ImageNet
100
128
SGD
0.9
0.01
10x. [30,60,80]
0.0001
"htts://gttub..oo//aggguuuu http://gghhbblbommmmnlilllla/aap http:://sssthil.ooosssssaaaaaaar
13

---

Under review as a conference paper at ICLR 2023
B EFFECTIVE METRICS CALCULATION
Effeetivv path. To exactly compute the number effective paths, we remove the batch nor- malization layers, we initialize all the remaining parameters to 1. Then, put the input vec- tor one to the network, and the number of effective paths is the sum of logits on the output layer = (T wel)1.
More precisely, we face problems with pooling layers in convolutional neural networks. With max pooling layer, we simply
not modify the output of this layer. that time, the result is the maximum number of paths in subnetworks. With average pooling layer, since all inputs of this layer contribute the oulput, we change the average operator the sum 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 Frankle et al. 2021 when identifying which effective param- eter. Similar to computing effective paths, make further steps. After having the sum of logits, compute the gradients this sum with respect to weights R. Then, an unpruned weight has non-zero gradient. it is effective and vice versa. Effective parameters dense edges that connect two effective nodes as visualized Figure
Effective node/channel. With fully connected layers, if all connections to one node or out of one node are pruned, this node pruned node. If there exist connections to a node but all of these con- nections are ineffective, then this node becomes ineffective In convolutional layers, instead of nodes, have channels. We consider kernel connection, channel node, and then convert the convolutional layer into a fully connected layer. The connection is pruned if and only if all param- eters in the corresponding kernel removed. Finally, identifying the effective nodes/channels is similar to the way in fully connected layers.
def metric calculatiin (model, mask):
model: network architecture
mask: mask for subnetwork
=**
n_eff_pathe
n_eff_nodes
n_eff_params
10
Initialize network with pruned weight = 0 and kept weight for name, param in model. named parameters
model..nmed.
param.copy_ (mask [name])
torch. c,h,w)
channel h: height w: width
15
y model (x)
16
sum_ Lim_logits y. s.sum ()
17
18
n_eff_paths- = sum_logits.item/
hun_logits.backwrrdy
with torch. ()
for name, param model. named _amee___aaammtterrssa ()
23
eit param torch. where (param.grad.data!-)) 1,
24
n_eff_params +- torch. (eff
25
26
eff eff_in_node = torch,
where torch.where (torch sum (efff__aaaa d=0) >0, 1, 0)
27
n_eff_nodes += torch. barch.sum(off_innnoo
with output layer eff eff_cut_node n Lodes nodes += torch.sum(efe out node)
30
wherh.whereeee (y>0,
31
32
33
return r_eff_paths n_eff_nodes, n_eff_paran
Listing 1: Metric calculation example in fully connected neural networks
14

---

Under review as a conference paper at ICLR 2023
C LAYERWISE SHUFFLING EXPERIMENTS
With each setting, at cach sparsity ratio, we seek subnetworks with different seeds, and with each seed, randomly shuffle the subnetwork two times. In addition 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 to Frankle al. (2021) 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 more intensive, the configu- ration of 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 in performance compared with unmodified ones.
0000
SNIP Meectee
34
StuPeet
Layeraa
Stuffed 330
64.10
$0.00
19.00
P2.44
19.00
64.10
20.00
29.44
20.00
09.10
$2.00
89.45
2.3
Syaat
SwuThe lavrr
Suffiee aurraiz
Ly
St Lover
02.5
60.00
60.00
19.08
10.00
14.44
10.00
10.0
64.35
10.00
19.40
69.1
10.00
PHEN
98
40
Started Lane
Stulhed Leterite
Shu Jaysatte
68.15
$02.00
$0.00
10.44
$0.00
10.44
$0.00
19.00
10000
$0.00
3944
Ours
HEW
PHiWi
Bumt
Dert
Durt
86.0
19.04
68-66
P9.0
66.
19.00
29.02
29.00
47:4
19:66
Figure 7: Layerwise shuffling results various sparse subnetworks of ResNet20 produced SNIP,
SynFlow, and PHEW at initialization on CIFAR-10.
SNNP
Uneosttee
10.00
20.00
19.0
Ionaeeen 1880
(00)
92
Accusss
1500
Unmouiiid
Unmaa oz
E80
10.00
44.44
6949
42.2
$0.00
Figure& 8: Layerwise shuffling results on various sparse subnetworks of VGG19 produced by SNIP
an SynFlow at initialization CIFAR-10.
15

---

Under review as a conference paper at ICLR 2023
D DIFFERENT SPARSITY REGIMES EXPERIMENTS INCLUDING GRASP
We report the min/averagc/max value of multiple runs and also the results of GraSP method in this Appendix to avoid ambiguity in the main text. Interestingly, GraSP tends to produce broader subnetworks compared with SNIP or SynFlow since GraSP's goal is preserving gradient flow after pruning (Wang et al. 2020). Iterative pruning methods like ours, SynFlow, and PHEW generate subnetworks with low variance in terms number of effective paths and nodes and accuracy after training as well. When sparsity becomes more extremely, effective parameters (Figure IT] and effec- tive paths (Figure TO) of one-shot pruning methods like SNIP, GraSP Random drop significantly, which drives to decrease in the performance.
With ResNet-18 on Tiny-lmagener experiments, PHEW and our method still preserve relatively large number of effective paths (> 30%) extremely sparse ratios (up to sparsity 99.82%). which ensures the information transfers well in the sparse networks. Therefore, both perform better than path preserving methods like SynFlow and Iter-SNIP.
92
0.9
VGG19 CHAR-10
Effective rede rebi
Top-1 Accurdr (h6
0.7
Effeche
86
0.5
0.4
0.5
0.4
0.2
43.77
82.22
90.00
43:77
68.38
82.22
58.04
90.00
48.77
68.36
82.22
98.00
98.84
96.8
99.00
0.9
RosNer30 M CIFAR-10
0.8
Effectvv rode ratl
Top-1 Accuriity (96)
0.7
0.7
Effectoe
0.5
0.5
50
0.4
0.3
20
63.77
82.22
98.00
96.84
88
43.77
68.38
82.22
90.00
96.3
99.00
68.36
82.22
90.00
96.84
99.00
1.0
0.9
55
RosNet18 Thay- Imagend
Effective path obto
50
0.7
45
Effective
0.6
0.6
0.4
0.3
30
25
23.77
60.38
82.22
80
90.00
43.77
68 3.38
36 M4
00
43:77
38
02.22
00
98.84
90.00
90.00
59
68
39
Sparsity
Spansity
Sparsity
Random
SNPP
Gra
SynFlow
SNIP
PHEW
Ours
Dense
Figure 9: The ratio of effective paths (after log scale), nodes after and before pruning, and the
corresponding accuracy of different Pal methods three datasets in the regular sparsity regime.
16

---

Under review as a conference paper at ICLR 2023
1.0
90
VGG19 CIFAR-10
Effectivendde raão
Tap-2 Accuracy (8)
80
0.6
25
0.4
0.2
0.0
50
99
00
44
90.666
90.62
$9.90
99 Sh
88 69
90.00
95.4
99 66
00.00
99.96
98.90
99.00
99
$9,666
99.82
30 90
98 04
99.99
0.8
RosNech RosNech CIARR-1
0.5
80
Effecaiv rabo
0.4
Tap-1 Accuracy
60
0.3
40
0.2
0.1
20
0.0
10
00
00.68
93.82
09.50
99.
89
93.00
88.44
99.6 65
99.94
93.59
99.00
99.44
99.00
09.82
89.90
0.7
60
50
ResNedl8 Thny -imagone
Effective 9 rato
40
0.6
0.4
30
Efeedive
0.4
20
10
0.2
93.00
68
82
80
36
90.99
00
44
68
34
59 99
44
88
62
99.94
90
999
99
38
99
99
99
99
59
99
99
99
:ity
Spansity
Sparsity
Random
SNP
Gra
SynFlow
-
Rar SNIP
PHEW
Ours
Dense
Figure 10: The ratio of effective paths (after log scale), nodes after and before pruning, and the
corresponding accuracy of different Pal methods three datasets in the extreme sparsity regime.
17

---

Under review as a conference paper at ICLR 2023
E
EFFECTIVE PARAMETER RATIOS
1.0
Elfective parameter retle
0.8
VGGI9 CIEAR-ID
0.6
0.4
0.2
0.0
43.77
68.38
82.22
90.00
96.84
99.00
99.44
99.68
99.82
99.90
99.94
99.99
Sparsity (96)
...- Random
SNIP
GraSP
SynFlow
- Itr-NNIP
PHEW
Ours
1.0
Elfective parameter rato
0.8
ResNeroo CIFAR-10
0.6
0.4
0.0
43.77
68.38
82.22
96.84
99.00
99.44
99.68
99.94
99.99
Sparsity (56)
...
Random
SNIP
GraSP
SynFlow
IterSNIP
PHEW
Our
1.0
RodNells Thy-- mny--Imggeet
Effective parameter ratio
0.8
0.4
0.0
43.77
68.38
82.22
96.84
99.44
99.68
99.82
99.99
Sparsity (%)
....
Random
SNIP
GraSP
SynFlow
-
Btr-SNIPP
PHEW
Durs
Figure 11: The ratio of effective parameters and unpruned parameters with different Pal methods on three datasets in varied sparsity regimes.
18

---

Under review as a conference paper at ICLR 2023
F EFFECTIVE NODES AT EACH LAYER
In Figure we visualize the number activated channels/nodes in each hidden layer networks in different sparsities and settings. As mentioned, PHEW gradually adds new imput-output paths such that nodes are activated as highly as possible. This is why PHEW consistently creates wider subnetworks. Except PHEW, iterative pruning methods (Iterative SNIP and SynFlow) tend to prune nodes more in later hidden layers compared with SNIP and GraSP because convolution layers the top usually learn highly sparse features and thus more weights can be pruned (Wang et al. 2020 Zhang 2019). We believe that further investigations into the configuration of hidden layers bring insightful knowledge to understand the success of Pal methods.
300
Spanits 68.38%
Spanitty 00.00%
Spanits 96.84%
Spaniity 90 00000
Spursit 000%
Randoo
Iben
PHEW
Dengc
Figure 12: The number of effective nodes in each hidden layer of three settings on different sparsi- ties.
19

---

Under review as a conference paper at ICLR 2023
G ADDITIONAL RESULTS ON SCHEDULER
We present ablations on the scheduler with different settings. The observations are consistent in the main text. Higher maa tends to produce wider subnetworks in normal sparsities, but it drives to layer-collapse in extensive sparsities. These experimental results one more time highlight our Node- Path Balancing Principle that regular sparse subnetworks prefer effective nodes to effective paths while subnetworks with extreme sparsity levels require good balance between nodes and paths.
VGG1V CHAR-
67.55
1944
R1/2
9114
1934
03.4
9.54
17.34
03.40
1822
9754
RoNNer00 CIFAR-10
Scndy
300
81400
RosNeTT Thoy Insggese
44.4
47.00
Janndyy
Figure 13: Scheduler ablation different settings.
20

---

Under review as a conference paper at ICLR 2023
H POTENTIAL FUTURE DIRECTIONS
Efficient Pruning Scheduler Based on the iterative pruning of SynFlow, we modify the pruning schedule with two additional hyperparameters, which balances better between effective paths and nodes. Adjusting these two drives to different architecture configurations as shown in Section [5.4 However, we believe that if we take into account a more sophisticated pruning scheduler, the pruned subnetwork will better satisfy the Node-Path Balancing Principle. From the view of the exploration and exploitation trade-off, it opens a new approach to pruning at initialization problems. To improve the effectiveness of the scheduler, could borrow ideas from Reinforcement learning.
Optimize the Node-Path Balancing From the Node-Path Balancing Principle, our goal is to op- timize the number of activated nodes and paths without using data given the sparsity. One possible way is that switch the pruning problem to multi-objective optimization problem. In particular, our problem becomes given architecture, maximizing both effective paths and effective nodes with the constraint of the number of parameters. This non-trivial problem, but with the long-standing development of optimization problems, there are many promising approaches.
Proxy for Evaluate Networks in Neuron Architecture Search Problem Neural Architecture Search (NAS) is known as the process of automating architecture engineering which is the next step in the automation of machine learning Elsken al. (2019). One main problem of NAS is computation overhead in estimating the performance of candidates Zoph & Le (2017); Zoph et al. (2018). Recently, AAbdelfattah al. (2021) leverage pruning methods perform zero-cost proxies. We believe our effective nodes and paths could be promising scores to evaluate the architecture candidates in NAS.
21

---

Under review as a conference paper at ICLR 2023
1
Toy EXPERIMENT
Sparsity 95%
Accuracy (%)
40000
86
The number of effective paths
87
39000
88
89
90
38000
91
37000
36000
35000
860
870
880
890
900
910
The number effective nodes
Sparsity 97%
Accuracy (%)
33500
48
The number of effective paths
54
60
33000
78
32500
32000
31500
805
810
815
820
825
830
835
840
The number of effective nodes
Figure 14: The toy experiments MLP network with three hidden layers and MNIST dataset. We sample 100 subnetworks with each two sparsity levels (95%, 97%)
In this experiment, we consider an MLP network with the numbers neurons in its layers are choosen as 784 128 64 10 with sparsity level of 95% and 97%, respectively. We keep all the nodes of input and output activated, other connections are randomly assigned into the network to create sparse subnetworks. Different subnetworks have different numbers of effective paths and nodes. We train all subnetworks with the same procedure to converge.
easy to see that subnetworks which have better balance between node and path tend to have better performance given the same sparsity. This proves that taking number of effective nodes and paths into account provides novel insight in understanding Pal methods and then open new research directions in designing network architectures.
22

---

Under review as a conference paper at ICLR 2023
J COMPARISON WITH RAREGEM AND LTH
Sparsity 90.00%
Number of effective paths (log scale)
39
Accuracy (%)
84.94
85.37
86.18
87.41
91.3
36
Method
PHEW
35
SynFlow
LTH
RareGem
Ours
6.1
6.2
6.3
6.4
6.5
Number of effective nodes (In scale)
Sparsity 99%
Number of effective paths (log scale)
Accuracy (%)
28
66.05
67.17
26
70.44
72.22
24
22
Method
PHEW
20
SynFlow
RareGem
18
Ours
5.00
5.25
5.50
5.75
6.00
6.25
6.50
Number of effective nodes (In scale)
Figure 15: Comparison with RareGem and LTH methods on three aspects the number of effective nodes, paths and accuracy after training subnetworks.
We reproduce the results of LTH (Frankle & Carbin 2018) and RareGem (Sreenivasan et al. 2022) on CIFAR-10 with Resnet20 figure out whether subnetworks produced by these methods support our proposed principle or not. We compute the number of effective nodes and paths of subnetworks generated by PHEW, SynFlow, LTH, RareGem, and Ours. We then visualize in the Figure [5] We consider LTH as a upper bound and optimal solution for balancing node-path. Through the additional experiments, we observe that subnetwork near optimal solution in terms of effective nodes and paths show better performance (accuracy after training). In extreme sparsity levels, RareGem produce better node-path balanced subnetworks compared to others, leading to higher performance of subnetworks. We strongly believe these results align with our principle and further support our principle as a necessary condition for good Pal. We want to highlight that RareGem and LTH both use dataset to produce subnetworks, and RareGem methods since requires a "gem mining" process.
costly compared with data-agnostic Pal
23


Reviews:
[{"review_id": "ojMFeuNKreS", "reviewer": "Reviewer_4Ufw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Motivated by a recent findings on the properties of prune at initialization (Su et al., 2020, Frankle et al., 2021), this paper proposes a new way of studying PaI methods. It suggests new metrics -- the number of effective paths\" and \"the number of effective nodes\" -- which are proxies to the performance of pruned network according to the authors' claim. The authors conjecture that a good balance between these two metrics are needed to let the pruned network have a good performance. Motivated by this so-called \"node-path balancing principle\", this paper suggests a simple method to improve SynFlow. ", "summary_of_the_review": "This paper is suggesting new direction of understanding PaI in terms of effective node/path in the network, but we cannot have much insight or logic from their discussion & results. ", "strength_and_weaknesses": "* Strength\n    * This paper focuses on an interesting problem of analyzing the intriguing property of PaI methods. \n\n* Weakness\n    * The conjecture made by the authors is not supported by theory. \n    * The empirical results are not supported by theory. For example, the empirical observation talks about two regimes (the normal sparsity and the extreme sparsity), but we do not know why 99% is a good threshold making different behaviors.\n    * Algorithm 1 is proposed based on the conjecture, but I would say it is a small variant of Synflow and not optimized for the purpose of balancing two metrics. Does the success of Algo 1 imply that we really need the balance of two metrics? I see only little connection btw Node-path balancing principle and the design of algorithm 1. \n\n\n* Question\n\n> Page 5, \"These observations indicate that increasing the number of effective paths (SynFlow) or effective nodes (PHEW) alone is not sufficient in the design of PaI methods.\"\n\nI didn't fully get why the observation in Fig.2 implies this. From the figure, we cannot say SynFlow and PHEW are not a good option, I guess?\n\n> Page 6, \"From observations in Section 3.3 where both effective paths and nodes play critical roles in performances of subnetworks.\"\n\nI guess this is not grammatically correct. Maybe the authors mean \"From observations in Section 3.3, both effective paths and nodes play critical roles in performances of subnetworks\"?\n\n> Algorithm 1 line 6\n\nIsn't it $t < T_{max}$, to be consistent with the description \"in the first Tmax pruning iteration, we use random pruning after each (∆t − 1) steps\"? \n\n> Is node-path balancing principle necessary for having a good performance?\n\nA recent PaI method [R1] passes the sanity check of layer wise shuffling and performs similar or better than IMP. I am curious whether this method has balanced node/path. If [R1] does not have balanced node/path, maybe the node-path balancing principle is not a necessary condition for good PaI?\n\n[R1] Rare Gems: Finding Lottery Tickets at Initialization", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OOiTEdcLVQs", "reviewer": "Reviewer_8VAP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates pruning at initialization through the lens of 'effective nodes' and 'effective paths'. Effective paths are defined as paths that exist from input node to output node and effective nodes as nodes that participate in at least one of these paths. The paper argues that these 2 objectives must be simultaneously met if one is to successfully prune at initialization. ", "summary_of_the_review": "The paper presents a novel idea for pruning at initialization in the form of the two objectives, however, lack of theoretical justification or strong empirical results makes the proposal unconvincing. Perhaps the authors could supplement the experiments with simpler toy experiments where they can explicitly optimize for the two objectives, this might help convince readers of the usefulness of the objectives. ", "strength_and_weaknesses": "Strengths:\n- The idea of dividing the pruning at initialization problem into these two objectives is novel\n- The paper is mostly easy to follow\n\nWeaknesses:\n- The new objectives are not supported by much more than heuristic arguments\n- The explanation in section 3.3 that attempts to explain the layerwise shuffling phenomenon through the lens of these two objectives is underdeveloped and should be expanded to allow readers to understand how the trade-off between the two objectives explains these results\n- The experimental results where the paper attempts a first pass at using these two objectives to prune at initialization are unconvincing (understandably the authors do clarify that this is not the goal of the paper, but considering lack of theoretical justification for the objectives, the experiments should instead instill faith in these two objectives)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AWaRhKmf4_c", "reviewer": "Reviewer_EqZe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a new pruning approach called, node-path balancing principle, based on the intuition that both effective nodes and effective paths need to be preserved high such that training sparse neural networks from scratch can be performed well.\nThe method is essentially done by tuning the schedule of (random) pruning for the obtained connectivity in the subnetwork.\nThis intuition is obtained based on recent works on pruning including the shuffling mask effect.\nThe authors summarize their findings in two different regimes, regular and extreme sparsity levels, that while effective nodes are more important than effective paths for regular sparsity, it may not be the case for extreme sparsity levels.\n", "summary_of_the_review": "I believe the paper investigates an important aspect based on good intuition. However, the methodology developed seems to be quite obvious, and the resulting algorithm is not backed up with strong empirical evidence.\n", "strength_and_weaknesses": "Strength\n- The writing is very clear, and the main idea and intuition behind are delivered well to readers.\n- The intuition behind the proposed method makes sense and based upon previous research findings in the literature.\n- The experiments are conducted systematically.\n\nWeaknesses\n\n- The proposed method introduces additional hyperparameters (\\Delta_t and T_\\text{max}) which can be suboptimally set in practice or expensive to perform. It is also hard to compare with others without solid fair hyperparameter searching. In terms of algorithmic or methodological advances it is simply considered as another schedule for iterative magnitude based pruning but with some resetting. When it comes to comparisons, it is hard to tell which one is better than which and things are not conclusive.\n- The proposed method being not better than PHEW in terms of the subnet accuracy (for regular sparsity levels) weakens the main argument on the importance of node-path balancing, which is somewhat critical.\n- Perhaps not the most critical issue, but it would have been better to add experiments on more diverse and larger data sets and network models since the paper relies on empirical evidence.\n- The results on effective paths and effective nodes divided by regular and extreme sparsity levels seem somewhat inconsistent and remain based on hypothetical intuition level without direct or provable evidence. The divider threshold between can be thought of as favoring the interpretation of the proposed method without a clear setup as to how the threshold has to be chosen.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "64iElTjt3WS", "reviewer": "Reviewer_uZiV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Neural network pruning (also referred as pruning at initialization(PaI)) task involves balancing the tradeoff between model complexity and accuracy. This makes it a challenging task. In this paper, authors have proposed a few guidelines to design PaI methods that involve leveraging configuration of subnetwork 1) number of effective paths 2) number of effective nodes. Authors provide new insights to the working mechanism of PaI methods, and open new research directions on neural network pruning methods. Authors find that width of subnetworks and node-path balancing plays an important role in designing PaI subnetworks. Experiments were conducted using PaI methods like SNIP, SynFlow, and PHEW on different architectures( ResNet, VGG) and datasets (CIFAR, Tiny-Imagenet).", "summary_of_the_review": "This paper provides helpful empirical insights for designing pruning at initialization(PaI) methods. Experiments show the impact of the topology of subnetworks - specifically subnetwork configurations like 1) number of effective paths 2) number of effective nodes in designing PaI methods, and how to balance these metrics in regular sparsity vs extremely sparse scenarios. Experiments were conducted using PaI methods like SNIP, SynFlow, and PHEW on different architectures( ResNet, VGG) and datasets (CIFAR, Tiny-Imagenet). Please refer to strengths/weaknesses section for more details. \n", "strength_and_weaknesses": "Authors have well drafted the related work/background section, clearly outlining past work in neural network pruning, importance of nodes and connection configurations, extreme sparse network design. Empirical evaluation in the paper is very detailed - for example, sections on layerwise shuffling, impact on regular/extreme sparsities are intriguing.  Iterative pruning algorithm/Node-Path balancing principle described in the paper found to be very effective in optimizing the number of activated nodes and paths.\n\nIterative pruning algorithm to find a pruning mask described in the paper sounds to be similar to existing work in this literature and paper doesn’t sound innovative from a theoretical point. Some subsections seek more details - for example, what is the motivation to introduce additional hyperparameters described in section 4, and statements like “findings indicate that pruning neural networks in the regular sparsity regime should give more consideration to the number of effective neurons since the information flow is conserved by the sufficient number of input-output paths.”. Providing qualitative analysis around scheduler ablation experiments can help understand the empirical numbers better. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject