LEAN: graph-based pruning for convolutional neural networks by extracting longest chains
Authors: Richard Arnoud Schoonhoven
Allard Hendriksen
Daniel Pelt
Joost Batenburg
Venue: ICLR 2022 Submitted (2022)
Keywords: Pruning
Sparsity
Compression
Graph pruning

Abstract: Neural network pruning techniques can substantially reduce the computational cost of applying convolutional neural networks (CNNs). Common pruning methods determine which convolutional filters to remove by ranking the filters individually, i.e., without taking into account their interdependence. In this paper, we advocate the viewpoint that pruning should consider the interdependence between series of consecutive operators. We propose the LongEst-chAiN (LEAN) method that prunes CNNs by using graph-based algorithms to select relevant chains of convolutions. A CNN is interpreted as a graph, with the operator norm of each operator as distance metric for the edges. LEAN pruning iteratively extracts the highest value path from the graph to keep. In our experiments, we test LEAN pruning on several image-to-image tasks, including the well-known CamVid dataset, and a real-world X-ray CT dataset. Results indicate that LEAN pruning can result in networks with similar accuracy but 3--20x fewer convolutional filters than networks pruned with methods that rank filters individually.

Under review as a conference paper at ICLR 2022
LEAN: GRAPH-BASED PRUNING FOR CONVOLU-
TIONAL NEURAL NETWORKS BY EXTRACTING
LONGEST CHAINS
Anonymous authors Paper under double-bile blind review
ABSTRACT
Neural network pruning techniques can substantially reduce the computational cost of applying convolutional neural networks (CNNs). Common pruning meth- ods determine which convolutional filters to remove by ranking the filters indi- vidually, i.c., without taking into account their interdependence. In this paper, we advocate the viewpoint that pruning should consider the interdependence between series of consecutive operators. We propose the LongEst-chAiN (LEAN) method that prunes CNNs by using graph-based algorithms to select relevant chains convolutions. A CNN is interpreted erator as distance metric for the edges. LEAN pruning iteratively extracts the high- est value path from the graph keep. In our experiments, on several image-to ponee-to-ime to-image tasks, including the well-known Cam Vid dataset, and real-world X-ray CT dataset. Results indicate that LEAN pruming can result networks with similar accuracy, while using 1.7-12x fewer convolutional filters than existing approaches.
graph, with the operator norm of each op-
test LEAN pruning
INTRODUCTION
In recent years, convolutional neural networks (CNNs) have become ofate-of-the-art for many image- to-image translation tasks (LeCun al., 2015), including image segmentation (Ronneberger al., 2015), and denoising (Tian et al., 2020). They are increasingly used as subcomponent of a larger system, e-g., visual odometry (Yang al., 2020), as well as energy-limited and real-time appli- cations (Yang et al., 2017). In these situations, the applicability of high-accuracy CNNs may be limited by large computational resource requirements. Small networks may be more applicable in such settings, but may lack accuracy.
Neural network pruning (Mozer & Smolensky, 1989; Karnin, 1990) has recently gained popularity technique to reduce the size of neural networks (Blalock et al., 2020). Neural networks consist of learnable parameters, including the scalar components of the convolutional filters. When pruning, the neural network is reduced in size by removing such sealar parameters while trying to maintain high accuracy. We distinguish between individual parameter pruning (Han et al., 2016), where each parameter of an operation is ranked and pruned separately, and structured pruning (Li et al., 2017; Luo et al., 2017), where entire convolutional filters are ranked and pruned. As convolution operators can only be removed once all scalar parameters of the filter kernel have been pruned, structured pruning is favored over individual pruning when aiming to improve computational performance (Park al., 2017). In the remainder of this paper, we focus on structured pruning.
Although structured pruning methods take into account the division of neural network into opera- tions, they do not take into account the fact that the output of the network formed by a sequence of such operations. This has two drawbacks. First, since the relative scaling of individual convolutions may vary without changing the output of the whole chain, pruning methods that prune individual operators could potentially prune suboptimal set of operators from the chain. Second, to signif- icantly reduce evaluation time, a severe pruning regime must be considered, i.e., a pruning ratio (percentage of remaining parameters after pruning) of 1-10%. In this regime, pruning can result in network disjointness, i.., the network contains sections that are not part of some path from the input to the network output. Some existing pruning methods take into account network structure

---

Under review as a conference paper at ICLR 2022
limited degree (Salchinejad & Valace, 2021). In practice, however, these methods do not contain safeguards to avoid network disjointness.
In this paper, we present novel pruning method called LongEst-chAiN (LEAN) pruning, which as opposed to conventional pruning approaches uses graph-based algorithms to keep or prune chains of operations collectively. In LEAN, CNN is represented tors, with the operator norm of each operator as edge weights. We argue that strong subnetworks in a CNN can be discovered by extracting the longest (multiplicative) paths, using computationally effi- cient graph algorithms. The main focus of this work is to show how LEAN pruning can significantly improve the computation speed of CNNs for real-world maage-to-image applications, and obtain high accuracy in the severe pruning regime that is difficult to achieve with existing approaches.
graph that contains all the CNN opera-
This paper is structured follows. In Section 2, we explore existing pruning approaches. In Section 3, we outline the preliminaries on CNNs, pruning filters, and the operator norm. Next, in Section 4, we introduce LEAN pruning and describe how to calculate the operator norm of various convolu- tional operators. We discuss the setup of our experiments in Section 5. In Section 6, we demonstrate the results of the proposed pruning approach on a series of image segmentation problems and report practically realized wall time speedup. Our final conclusions are presented in Section 7.
2 RELATED WORK
Reducing the size of neural networks by removing parameters has been studied for decades (Mozer & Smolensky, 1989; Karnin, 1990; Hassibi et al., 1993). Several works take into account the struc- ture of the network to some degree. In Lin et al. (2017) filters are pruned at runtime based on the feature maps (Lin et al., 2017). Alternatively, one can prune entire channels (He et al., 2017), or decide which channels to keep so that the feature maps approximate the output of the unpruned network over several training examples (Luo et al., 2017). In recent work, a graph is built for each convolutional layer, and filters are pruned based on the properties of this graph (Wang et al., 2021). I). In Salehinejad & Valaee (2021) neural network is represented as graph and interdependencies are determined using the Ising model.
Many pruning approaches are aimed at reducing neural network size with little accuracy drop (Dong & Yang, 2019; He et al., 2019; Molchanov et al., 2019; Zhao et al., 2019), as opposed to sacrificing accuracy in favor of computation speed. These approaches rarely exceed pruning ratio of 12-50% (Blalock et al., 2020; Luo et al., 2017; Lin et al., 2019). When a high pruning ratio is used, e.g., a range of 5-10% (Lin et al., 2017; Liu et al., 2019), a significant drop in accuracy is observed. Pruning ratios of 2-10% can be achieved with an accuracy drop of 1-3% by learning-rai caaning-rattee rewinding (Renda et al. 2020). However, the reduction in FLOPs was less substantial (1.5-4.8 times). In Yeom et al. (2021) severe pruning ratios of up to 1% have been considered, but the approach achieved limited improvements in terms of FL.OPs reduction compared with existing pruning methods.
Criteria for deciding which elements of a neural network to prune have been extensively studied. A parameter's importance is commonly scored using its absolute value. Whether this is a reasonable metric has been questioned (LeCun et al., 1990). Singular values (which determine certain operator norms) have been used to compress network layers (Denton al., 2014) and prune feed-forward networks (Abid et al., 2002). Efficient methods for the computation of singular values have been developed for convolutional layers (Sedghi et al., 2019). Furthermore, defimition of ReLU singular values was proposed recently with an accompanying upper bound (Dittmer et al., 2019).
3 PRELIMINARIES
3.1 CNNS FOR SEGMENTATION
A common image to image translation task semantic image segmentation. The goal of semantic image segmentation is assign class label to each pixel in an image. A segmentation CNN computes a function f mm > [0, ]|xxmxx, which specifies the probability of each pixel being in one of the k classes for
x image.
CNNs are composed of layers of operations which pass images from one layer to the next. Every operation, e.g., convolution, has an input and output y. The input and output consist of one
2

---

Under review as a conference paper at ICLR 2022
more images, called channels. For clarity, we distinguish throughout this paper between an operation, which may have several input and output channels, and an operator, which computes the relation between single input channel and single output channel. For instance, in convolutional operation with input channels X1,-... XN, an output channel yj is computed by convolving input images with learned filters
y, has bj-
Here haj is the filter related to the convolution operator that acts between channel and Yj. and by is an additive bias parameter. similar way, every CNN operation produces an output which consists of a number of channels. The exact arrangement of operations, and connections between them, depends on the architecture.
A common operator to downsample images is the strided convolution. The stride defines the step size of the convolution kernel. A convolution with stride defines a map : R - R x Upsampling images can be done by transposed convolutions. Transposed convolutions intersperse the input image pixels with zeroes so that the output image has larger dimensions.
In addition convolution operators, other common operators such pooling and batch normaliza- tion are often used. A batch normalization operator (loffe Szegedy, 2015) normalizes the input images for convolutional layers. A batch normalization operator scales and shifts an image x; by
PB V
V: =
+ +
Here, 7 and B are scaling and bias parameters which are learned during training, and μa and o'g are the running mean and variance of the mini-batch, i.e., the set images used for the current training step. For an overview of CNN components we refer to Goodfellow et al. (2016).
3.2 PRUNING CONVOLUTION FILTERS
Pruning techniques aim to remove extraneous parameters from a neural network. Several schemes exist to prune parameters from network, but retraining the network after pruning is critical to avoid significantly impacting accuracy (Han et al., 2015). Pruning network once after training is called one-shot pruning. Alternatively, network can be fine-tuned, where the network is repeatedly pruned by certain percentage and is retrained for a few epochs after every pruning step. Fine-tuning typically gives better results than one-shot pruning (Renda al., 2020).
Generic pruning algorithm: All pruning methods used in this work make use of the fine-tuning pruning algorithm outlined in Algorithm 1. The selection criteria for determining which filters to keep for each step define the different pruning methods. The pruning ratio pRat. remaining convolutions we ultimately want keep, and stepRat i the fraction of convolutions that is pruned at each step.
t i o is the fraction of
Algorithm 1 Fine-tuning pruning algorithm
1: procedure PRUNE(MODEL, PRATIO, NSTEPS, EPOCHS)
2: stepRatio + /n(ppRattoo//SStppp
for step <- 0 ruSteps do
4: pruneParams <- seleciPuuneasssmmeelee stepRatio)
5: model x- removePars(model, pruneParams)
6: for k + 0 to epochs do
model trainOOneEpoch(mmddl, trainData)
return model
Here, we focus on structured pruning. structured pruning, a common approach to decide which filters to remove is structured magnitude pruning. When using structured magnitude pruning, convolution filter h E k is scored by its L1 vector norm ||h|| Filters with norms below threshold are pruned. The threshold is determined by sorting group of filters, and removing percentage based on the pruning ratio. Thresholds can be set per layer or globally. Setting thresholds globally can give higher accuracy than setting thresholds per layer (Blalock al., 2020).
3

---

Under review as a conference paper at ICLR 2022
(A) CNN
(B) Pruning Graph
Ihoo
Input
Output
IPL
Must
Shut
ReLli
Vul
Conv 3x3, ReLU
BatchNorm
RoLU
Relu
Avg
Upconv
Figure 1: (A) Example CNN architecture with the number of channels indicated above each layer. (B) Associated pruning graph. Every channel is a node, and every operator is an edge connecting input and output nodes. The edge weights are the corresponding operator norms.
3.3 OPERATOR NORM
As an alternative the Li-ormm one can interpret convolution h as a linear operator which acts on the input image, and score it according to an operator norm. The (induced) operator norm Il-1lp is defined as
1hlp == sup { [/ * x x R", 1x
(3)
common operator norm is the spectral norm, which is induced by the Euclidean norm (p = 2). The spectral norm can be obtained by calculating the largest singular value of the matrix H associated with h, ||Al|, = maa (H) (Meyer, 2000). A property that we will use is that the spectral norm submultiplicative, i.c., we have
|| $
||||| |[B], for all A, B B"x=
4 METHOD
The idea behind LEAN to construct a weighted graph structure formed by the operators of the CNN and having their respective norms as edge weights, such that the multiplicative longest paths in this graph are selected as important subnetworks. The remaining unselected operators will then be pruned. The motivation for LEAN two-fold. The first consideration is that since convolutions linear operators, the scaling of an individual convolution within a chain of convolutions is somewhat arbitrary. For a scalar X and chain of linear operators A₃ (A1 A1) o... (Am Am) is equivalent if X 1. Since |,A, = |>a] ||l]] this can lead to any arbitrary ranking operators. However, the chain as whole gives the same output for each input. We argue that this can lead to incorrect pruning when pruning individual operators based on norms, rather than entire chains. We hypothesize that these scaling properties still approximately hold in the presence of non-linear operators. Since LEAN ranks chains of operators, it is invariant under these scaling properties. Second, by extracting chains LEAN combats network disjointness.
Ams we have that any chain
4.1 LEAN: CREATING THE PRUNING GRAPH
Graph structure: In this section, we define the pruning graph that is the basis of the LEAN algo- rithm. As discussed in Section 3.1, we say that every CNN operation has an input x and an output y, consisting of channels x; and y;. For each channel, we add single node in the pruning graph. An edge connects two nodes corresponding to input channel x; and output channel y; if channel x; used in the computation of channel y:. In the terminology of Section 3.1, each edge corresponds to an operator. For instance, convolution operation is converted by adding an edge from each input channel x, to every output channel yj. each corresponding to exactly one filter haj- Certain CNN operations may be performed in-place in practice, but consider them separate nodes in the pruning graph. A combined convolution and ReLU operation, for instance, results a node for the output of the convolution and separate node for the output of the ReLU, as shown in Figure 1.
Edge weights:
To each edge, we assign as weight the operator norm of its corresponding operator. result of applying the
That is, calculate the maximal scaling that input could undergo operator. In this calculation, we ignore any additive bias terms. For instance, applying a batch nor- malization results in scaling of hrl/ V (see Equation (2)). The scaling of non-linear operators
4

---

Under review as a conference paper at ICLR 2022
in neural networks is sometimes bounded, as in the case of the ReLU for instance, to which we sign a weight of 1. We describe the calculation of operator norms for various convolution operators in Section 4.3.
Path lengths:
The length of a path in the graph is determined by multiplying the edge weights. LEAN aims to model the norm of the composition of the operators corresponding the edges. Equation (4) states that |||||-|| [| is an upper bound for ||AB|] For LEAN, we assume that || x |||||-||B|| is a reasonable approximation, although it may not hold generally. By defining the path length as the multiplication of the edge weights (operator norms), path lengths are invariant under scaling linear operators chain if the scalars multiply 1.
There are some edge cases to consider. First, some CNNs contain operations that are meant to dis- tribute features throughout the network, but are not implemented with learnable parameters, e.g., residual connections in ResNet (He et al., 2016). We include residual connections in the pruning graph with an edge weight of but label them as unprunable to prevent the residual connections from being removed from the network. Second, we do not consider CNNs with recurrent connec- tions. Therefore, the pruning graph a Directed Acyelic Graph (DAG). Large pruning graphs can be reduced in size, e.g., by merging nodes that are connected by single edge (see Appendix B).
4.2 LEAN: EXTRACTING CHAINS FROM THE GRAPH
The LEAN method prunes chains of convolutions based on paths in the graph; we keep the longest paths (with the highest multiplicative operator norm). We refer to this as LongEst-chAiN (LEAN) pruning. When perform LEAN pruning, we iteratively extract such paths from the graph until have reached the pruning ratio. This means that the edges that are not extracted are pruned. Finding paths is done by iteratively running an all- all-pairs longest path algorithm Cormen et al. (2009).
Algorithm 2 LLEAN
1:
procedure LEAN(MODEL, PRUNERATIO)
2: graph creadePPuninnngGrpploooeddd)
retainedConvs < [ 4: while fractionneeaiinnngCCnss < prune do
5:
bestChain + retainedConvs + retainedConvs + bestChhain graph < renooveFrrmmCrrppiggggh bestChain)
6:
7:
8: convsToPrune convsInModel retainedConvs
9:
return convsToPrune
LEAN pruning is incorporated in the fine-tuning procedure. For each pruning step in the fine-tuning procedure, Algorithm 2 is used to select the filters to prune (line 4 in Algorithm 1). For DAGs, the longest path in graph can be found in O(V + [E' time, where V is the of nodes, and E is the set of edges (Sedgewick & Wayne, 2011) 1). For a CNN with m channels (nodes), and i operators (edges), we can extract a longest path in O + k) time. As we extract least one operator with every execution of line 5 in Algorithm 2, the longest path algorithm is run at most k(1 -p) p) times. So the worst-case complexity of Algorithm is (() (m + k)) for a pruning ratio p. Unprunable edges can be part of longest path to extract operators, but do not count towards the pruning ratio.
After every LEAN pruning step is concluded, some pes-processsig is performed. In some cases there are channels which receive no input data at all, or which are equal to homogeneous constant image for all input data. We therefore remove nodes without incoming edges as well as nodes where the succeeding batch normalization has running variance below some threshold (10 (10-40 by default). A low running variance can occur when the output of a convolution is always zero after applying the ReLU activation function, for instance. Second, bias terms removed from the CNN when all associated convolution or batch normalization operations are pruned.
4.3 OPERATOR NORM CALCULATION
Operator norm of convolutions: For a convolution filter and an n x n image, h+ is the filter padded with zeros to size The singular values of h are the magnitudes of the complex entries
5

---

Under review as a conference paper at ICLR 2022
O
Figure 2: The output of s convolution can be obtained by adding the result of 4 convolutions. Split the image and filter into the coloured sections, with white entries representing zeroes, and sum the outputs pixel-wise. The dots in the image represent the positions of the center of the filter as it moves over the image.
of the 2D Fourier transform (2 (Section of Jain (1989))
men H)) max (|22
(S)
Downsampling: operator norm for strided convolutions: A strided convolution is equal to the sum of regular convolutions on smaller input images (see Figure 2). A single parameter of a stride-2 convolution filter is multiplied only with every other pixel (horizontally and vertically). Similarly, filter parameters which are 2 apart are multiplied with the same pixels. Here, we calculate the operator norm for a stride-2 convolution operator h. Let hb1 and X be the partitioned convolution kernels and input images, both vero-padded to the correct size. For stride-2 convolution we have
h X
Σ M X
We can apply Equation 5 to obtain the singular values of h[6] Equation is analogous to the equa- tion of convolutional layer with 4 input channels, and output channel. The operator norm of convolutional layer can be computed by means of a tensor E fgxx1xxX (Sedghi al., 2019)
PounsCouesh = F2D (2
According to Theorem of Sedghi al. (2019), the spectral norm of the convolutional layer equals the maximum of the singular values of the 4 x 1 matrices P...ig. Since the matrices are single- column, their singular value equals their L2- norm. Therefore, the spectral norm of h equals
||ll max 1.j
Σ p2 Cinsish
Upsampling: operator norm for transposed convolutions: The matrix of a stride-s transposed convolution is the transposed matrix stride-s convolution (Long et al., 2015). Since we have || | for transposed convolution h, the operator norm can be computed by Equation 7.
EXPERIMENTAL SETUP
In our experiments, we compare LEAN pruning to several structured pruning methods across three image segmentation datasets and three CNN architectures: MS-D, U-Net4, and ResNet50. We assess the performance of pruned neural networks across 5 independent runs of fine-tuning (Algorithm 1). For each dataset, we have trained single model as starting point for pruning. In every experimental run, the same trained model was pruned.
For all pruning methods, we measure the pruning ratio as the fraction of convolutions remaining: EnEn (M))/HH where H is the set of all convolutions in network, and (h) is O if convolution H is pruned and otherwise. This means that other parameters, such batch normalization and bias parameters, pruned when the associated convolutions are pruned, but do not count towards the pruning ratio.
The MS-D networks were pruned to a pruning ratio of 1% in 45 steps. The U-Net4, and ResNet50 networks were pruned to a ratio of 0.1% in 30 steps. All were retrained for 5 epochs after each step. interested in significant computational
We chose relatively severe pruming ratios because speedup. U-Net4 and ResNet50 are pruned lower ratio as they have orders of magnitude more convolutions than the MS-D network.

---

Under review as a conference paper at ICLR 2022
5.1 STRUCTURED PRUNING METHODS
We compare LEAN to two layer-wise pruning methods, and two global pruning methods. The layer- wise pruning methods are geometric median pruning (GM) (He al., 2019), and soft filter pruning (SFP) (He et al., 2018). The first global pruning method we compare to is structured magnitude pruning, i.e., pruning entire filters by their L1-morm (see Section 3.2), and the second global method compare to is operator norm pruning, i.c. pruning entire filters using the operator norm. Here, we choose to use the spectral norm. The difference between LEAN and structured magnitude prun- ing is 1) the operator norm; 2) the consideration of network structure. The comparison of LEAN to structured operator norm pruning measures the effect of incorporating the network structure.
We compare LEAN to structured magnitude pruning and operator norm pruning for all CNN archi- tectures. Both GM and SFP contain implementations to prune ResNet50 but not MS-D or U-Net4, and hence are used only in the ResNet50 experiments.
5.2 CNN ARCHITECTURES
In this section, we describe three fully-convolutional CNN architectures that are used in the ex- periments: the Mixed-Scale Dense convolutional neural network (MS-D) network (Pelt & Sethian, 2018), U-Net (Ronneberger et al., 2015), and ResNet (He et al., 2016). Table outlines which op- erators are present in the networks. The networks were trained using ADAM (Kingma & Ba, 2014) with Ir = 0.001, minimizing the negative log likelihood function.
Convolution Transposed
Batch
Edges in pruning graph
CNN
Strided
Dilated
Pooling
normalization
Parameters
MS-D
No
No
Yes
No
No
4.57 10
5.05 10
ResNet50
Yes
No
Yes
Yes
Yes
3.29 107
1.44 10²
U-Net4
No
Yes
No
Yes
Yes
1.48. 107
1.84 10
Table 1: Operators present in MS-D, ResNet50, U-Net4 architectures.
In our experiments we MS-D networks as described in Pelt & Sethian (2018) and implemented in Hendríksen (2020). Every layer has channel and all convolutions have a dilated 3 x 3 filter, except the final 1 1-layer. The dilations for layer were set to 1 + (i mod 10). The final layer is excluded from pruning as it contributes less than 0.5% of FLOPs.
As U-Net architecture we use a fully-convolutional (FCN) U-Net4 network, i.e., a U-Net with scaling operations. We used a U-Net4 architecture from the PyTorch-UNe. repository Milesi (2020). As ResNet architecture, we use an (CN-ResNet50 network (He et al., 2016). The ResNet50 model is adapted from PyTorch's 's model 700 code. We replace the max pooling layers of ResNet and U- Net with average pooling layers as average pooling is a linear operator which can be modeled as strided convolution for which we can compute the operator norm. In some cases U-Net with average pooling can perform better than with max pooling (Astono et al., 2020).
5.3 DATASETS
In our experiments, we consider three datasets: a high-noise, but relatively simple, segmentation dataset (Pelt & Sethian, 2018) (CS dataset); the well-known Cam Vid dataset (Brostow et al., 2008; 2009); and real-world X-ray CT dataset (Coban & Lucka, 2019; Coban et al., 2020) to test the methods in practice. The CS dataset a 5-class segmentation dataset of 1000 training, 250 valida- tion, and 100 test images. As starting point for pruning, we trained 100-layer MS-D network with an accuracy of 97.5%, ResNet50 with 95.8% accuracy, and U-Net4 with 97.6% accuracy.
The X-ray CT dataset consists of 9216 training, 2048 validation, and 1536 test images. As in Schoonhoven et al. (2020), we use the Fl-score to quantify results. As a starting point for pruning, we trained 100-layer MS-D network with 0.88 Fl-score, ResNet50 with a 0.85 Fl-score, and U- Net4 with a 0.88 Fl -corc. As in Paszke et al. (2017), experimental results on the Cam Vid dataset are quantified using mean Intersection-over- Uvir-nnon (mloU). As starting point for pruning, we trained a 150-layer MS-D with 0.52 mloU, ResNet50 with 0.71 mloU, and U-Net4 with 0.65 mloU, More details on the datasets can be found in Appendix A.
7

---

Under review as a conference paper at ICLR 2022
MS-D
U-Net4
ResNet50
10 parameters
1.5 10 parameters
3.3 x 11' parameters
CircleSquare (Simulated)
0.56
6.95
0.45
0.50
0.75
0.70
0.70
0.70
10
105
10
10
10
1.00
10
10
10
10"
Dynamic X-ray CT (Real-time appliccl icaton)
0.4
0.8
24
0.4
F
0.2
8.7
0.7
0.7
Kagatzale
0.6
0.6
LEAN
Opentie som
Ca (Challenging
GM
sTP
0.4
Unyeuved
0.3
0.3
0.3
0.2
0.2
02
9.0
Fraction of convolctionas remaining (no final Layes]
Fraction of conpolatioons
Fraction convodutionn remnsiing
retuoining
Figure 3: Comparison of structured pruning methods and LEAN pruning on three datasets (rows).
Pruning methods are applied to MS-D, U-Net4, ResNet50 network architectures. The base model is pruned to ratio of 1% (MS-D) or 0.1% (ResNet50, U-Net4) for all datasets. This is repeated five times (translucent lines) and the average is taken (solid lines).
RESULTS
6.1 EXPERIMENTAL RESULTS FOR SEVERE PRUNING
The results of the pruning experiments are displayed in Figure 3, showing that LEAN pruning at similar accuracy obtains networks with lower pruning ratio than the four compared methods. The pruning ratio that can be achieved without significant loss of accuracy depends on the network architecture and the complexity of the dataset.
In the CS dataset results, we notice a drop-off point where performance decreased significantly for all networks. On average over 5 runs of pruning, LEAN achieved 3.4%, 0.79%, and 0.79% pruning ratio for MS-D, U-Net4, and ResNet50, with an average accuracy reduction of 1.4%. 2.5%, and 2.1% respectively. On ResNet50, an accuracy reduction of 3% compared to the unpruned network, LEAN achieves 43% reduction in the number of convolutions compared to GM and SFP. Below 15% accuracy reduction SFP and GM perform better, but the network no longer reliably segments the data at these accuracies.
On the dynamic X-ray CT dataset, we notice large fluctuations in for MS-D and U-Net4. This may be due to the F1-score which is defined as a reciprocal. In addition, on U-Net4, LEAN performs better than the structured pruning methods right from the start. On average over 5 runs, LEAN achieved a 5. % and 6.3% pruning ratio for MS-D and U-Net4, with an average Fl drop of 5.7%, and 3.3% respectively. For ResNet50, a drop-off point is again observed, which occurs at a significantly lower pruning ratio for LEAN than for both global pruning methods. GM and SFP exhibit more gradual reduction F1-score.At an Fl-score reduction 3% compared to the unpruned network, LEAN achieves 92% reduction in the number of convolutions compared GM and SFP.
8

---

Under review as a conference paper at ICLR 2022
Practical speedup prumed vs. base MS-D
Evauxtton time (8) on tess datuses
Ungeazed MBD
LEAN
10.9
10
2
16
Batch size
Figure 4: Practically realized speedup of pruned MS-D networks evaluated on the test dataset.
On the Cam Vid dataset, we observe a declining mIoU for MS-D and U-Net4 as pruming progresses on this challenging dataset. On ResNet50 we notice an initial drop in mloU, but subsequent pruning steps increase the performance initially. These observations could indicate that epochs of retraining are not sufficient for the CamVic Vid dataset to recover performance. Interestingly for U-Net4, we notice that for two pruning ratios, structured magnitude pruning appears to perform slightly better than LEAN. Given the variance between different runs, possibly due to the limited number of retraining epochs, we suspect that this difference is not statistically significant. After the initial drop in mIoU, notice later drop-off pruning ratio on ResNet50. LEAN achieves 6.3% pruning ratio with an average mloU reduction of 14.3% on ResNet50, whereas the best performing other method dropped- off at 20.0% pruning ratio. Interestingly, both layer-wise pruning methods GM and SFP exhibit sustained reduction in test mloU rather than the drop-off we observe for the global pruning methods.
6.2 SPEEDUP REAL-WORLLD DYNAMIC X-RAY CT SEGMENTATION
In addition to measuring the achievable pruning ratios, we measure the practically realized wall- time speedup. We tested this on the dynamic X-ray CT dataset for which a speedup has immediate benefits in practice. Existing pruming support in PyTorch only masks pruned filters, thereby not creating a faster network. Therefore, we implemented a custom MS-D model which loads only the unpruned filters. During the experiments, reduction) with LEAN achieved an Fl-score of 0.83 (drop of 5.4%). This network was 10.9 times faster than the unpruned network in practice. The speed of evaluating the entire test set is impacted by the batch size, which we take into account as shown in Figure 4. For comparison, we included the best performing pruned MS-D network by an other pruning method (operator norm pruning) which achieved pruning ratio of 15.8% with an F1-score of 0.83. We show differences between MS-D networks pruned with different pruning methods in Appendix C.
MS-D network pruned to ratio of 2.5% (40-fold
7 CONCLUSION
In this paper, have introduced novel pruming method (LEAN) for CNN pruning by extracting the highest value paths of operators. We incorporate existing graph algorithms and computationally efficient methods for determining the operator norm. We show that LEAN pruning permits removing significantly more operators while retaining better network accuracy than several existing pruning methods. Our results show that LEAN pruning can increase the speed of the network, both in theo- retical speedup (FLOPs reduction) and in practice. In conclusion, LEAN enables severe pruning of CNNs while maintaining high accuracy, by effectively exploiting the interdependency of network operations.
Future work could be split along several lines. First, there are more CNN operators for which methods to compute their operator norms could be developed. Notably, we have mostly disregarded non-linear operators this work. Next, LEAN approximates the norm of a chain of operators using New methods for approximating the
the submultiplicative property upper bound || < norm of a chain of composed operators could strengthen LEAN as it more accurately extracts chains with strong operator norms. In addition, new graph theoretic approaches for extracting meaningful paths from the graph could be explored. Such algorithms are already abundant in the field of graph theory, and could quite readily be carried over to neural network pruning research. Lastly, LEAN currently works by greedily extracting high-value paths. Approaches such as Guo et al. (2016) could be considered to avoid greedy selection of operators.
||

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
In order to aid reproducibility the authors have published (Python) code for LEAN pruning. There installation instructions that aim help users install and run the code on their machines, as well as explanations and documentation for the code and scripts. The scripts are intended to be usable on relatively simple machines (with GPU and CUDA), and be limited to several minutes run time. First, the code contains script generate the CircleSquare (CS) dataset. Second, the code contains a script to train an MS-D network (a pre-trained network also supplied) on the CS dataset. The script uses the MS-D network as it is the least computationally expensive to run, but the U-Net4 and ResNet50 models and pruning methods are also supplied. Third, the code contains script to run LEAN pruning, and the two global pruning methods, the trained MS-D network for the CS dataset (example results are also supplied). This way, users can check the experimental results, and experiment themselves with the LEAN method. In addition, the code contains several testing procedures that aim to verify the correctness of the function in the code. For example, the Fourier-based method of computing the operator norm is tested against the power method for random convolutions and strides, and against explicitly computing the SVD of the matrix that is associated with a convolution. Another example is that these tests check whether the pruning methods actually prune the correct number of convolutions. The code is submitted as .zip file in the supplementary materials section, with README instructions.
REFERENCES
S. Abid, F. Fnaiech, and M. Najim. A new neural network pruning method based on the singular value decomposition and the weight initialisation. In 2002 11th European Signal Processing Conference, pp. 1-4, 2002.
Indriani P. Astono, James S. Welsh, Stephan Chalup, and Peter Greer. Optimisation of 2D U- Net Model Components for Automatic Prostate Segmentation on MRL. Applied Sciences, 10 (7), 2020, ISSN 2076-3417. doi: 10.3390/ap11007261. URL https: http:w.mppppp.p.po com/
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. SegNet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine intelligence, 29(12))2481-2495, 2017. 13
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of Machine Learning and Systems, 2020. 1, 2,
Gabriel Brostow, Jamie Shotton, Julien Fauqueur, and Roberto Cipolla. Segmentation and recog- nition using structure from motion point clouds. In European conference on computer vision (ECCV), pp. 44 57. Springer, 2008. 7, 13
Gabriel J Brostow, Julien Fauqueur, and Roberto Cipolla. Semantic object classes in video: A high-definition ground truth database. Pattern Recognition Letters, 30(2):88-97) 2009. 7, 13
Sophia Bethany Coban and Felix Lucka. Dynamic 3D X-ray micro- CT data of tablet dissolution in a bater- gel, 2019. URL https: http:://doo..rg////// 100. 528 /eoooo .tt.ea....666100 6110187. 7,
Sophia Bethany Coban, Felix Lucka, Willem Jan Palenstijn, Denis Van Loo, and Kees Joost Baten- burg. Explorative Imaging and Its Implementation at the FleX-ray Laboratory. Journal of Imag- ing, 684):18, 2020. URL "https: /ttp://dooiiooo org/ 100 3390/ 1mmag in 6040000001100 8.. 7, 13
Thomas H Cormen, Charles Leiserson, Ronald I. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. 5
Emily L Denton, Wojeiech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in neural informa- tion processing systems. pp. 1269-1277, 2014.
S. Dittmer, E. J., and Maass. Singular values for relu layers. JEEE Transactions on Neural Networks and Learning Systems, pp. 1-12, 2019. 2
10

---

Under review as a conference paper at ICLR 2022
Xuanyi Dong and Yi Yang. Network pruning via transformable architecture search. In Advances in Neural Information Processing Systems, pp. 760-771, 2019. 2
David Eigen and Rob Fergus. Predicting depth, surface normals and semantic labels with a common multi-scale convolutional architecture. In Proceedings of the IEEE international conference
computer vision, pp. 2650-2658, 2015. 13
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016. 3
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp- 1387-1395, 2016. 9
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances neural information processing systems, pp. 1135-1143, 2015. 3
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. International Conference on Learning Representations (ICLR), 2016.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In JEEE international conference on neural networks, pp. 293-299. IEEE, 1993. 2
K. He, X. Zhang, S. Ren, and Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016. 5,7
Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018.
Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019. 7
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE international conference on computer vision, pp. 1389-1397, 2017. 2
Allard A. Hendriksen. Mixed-scale dense networks for pytorch. https://githhit com/
ahendr wondrrisse/meee wesesksmmmddptorreeee 2020. 7
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Leurning (ICML), 2015.
Anil K. Jain. Fundamentals of Digital Image Processing. Prentice-Hall, Inc., USA, 1989. ISBN 0133361659,
E. D. Kamin. A simple procedure for pruning pack-propagation trained neural networks. IEEE Transactions on Neural Networks, 1(2):239-242, 1990. 1,2
Diederík Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014. 7
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):4664444 2015. 1
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient ConvNets. In 5th International Conference on Learning Representations, ICLR 2017, 2017. 1
11

---

Under review as a conference paper at ICLR 2022
Ji Lin, Yongming Rao, Jiwen Lu, and Jie Zhou. Runtime neural pruning. In Advances in neural information processing systems, pp. 2181-2191, 2017. 2
Shaohui Lin, Rongrong Ji, Chenqian Yan, Baochang Zhang, Liujuan Cao, Qixiang Ye, Feiyue Huang, and David Doermann. Towards optimal structured CNN pruning via generative adver- sarial learning. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern
Recognition (CVPR), 2019. 2
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. International Conference on Learning Representations (ICLR), 2019. 2
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-3440, 2015. 6
Jan Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE international conference on computer vision, pp. 5058-5066, 2017. 1.2
Carl D Meyer. Matrix analysis and applied linear algebra, volume 71. Siam, 2000. 4
Alexandre Milesi, Unet: semantic segmentation with pytorch. https: pttps://githule com/
milesiall/ytoon Ayllesial/Pytorrc--Ueettt 2020.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Michael C Mozer and Paul Smolensky. Skeletonization: technique for trimming the fat from network via relevance assessment. In D. S. Touretzky (ed.), Advances in Neural Information Processing Systems 1, pp. 107-115. Morgan-Kaufmann 1989. 1,2
Jongsoo Park, Sheng Li, Wei Wen, Ping Tak Peter Tang, Hai Li, Yiran Chen, and Pradeep Dubey. Faster CNNs with direct sparse convolutions and guided pruning. International Conference on Learning Representations (ICLR), 2017.
Adam Paszke, Abhishek Chaurasia, Sangpil Kim, and Eugenio Culurciello. ENet: A deep neural network architecture for real-time semantic segmentation. International Conference Learning
Representations (ICLR), 2017. 7, 13
Daniël M. Pelt and James A. Sethian. A mixed-scale dense convolutional neural network for image analysis. Proceedings of the National Academy of Sciences, (5(22)254-255, 2018. ISSN 0027- 8424. doi: 10. 254. 13
URL http: /wwwwwwww.o.m..oo//////w// pnas org/ wwwpr///ooeettttteee /115////
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. International Conference on Learning Representations (ICLR), 2020. 2,
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional networks for biomedi- cal image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234 244,244,222 2015. 1,7
Hojjat Salehinejad and Shahrokh Valace. Pruning of convolutional neural networks using ising energy model. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3935-3939, 2021. 2
R. Schoonhoven, J. W. Buurlage. M. Pelt, and K. Batenburg. Real-time segmentation for tomographic imaging. In 2020 IEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1 1-6, 2020. doi: 10.1090MLSP99002.00009221 642. 7, 13
Robert Sedgewick and Kevin Wayne, Algorithms. Addison- professional, edition, 2011. 5
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. Inter-
national Conference Learning Representations (ICLR), 2019. 2,
12

---

Under review as a conference paper at ICLR 2022
Chunwei Tian, Yong Xu, and Wangmeng Zuo. Image denoising using deep CNN with batch renor- malization. Neural Networks, 221:461-773, 2020.
Zi Wang, Chengcheng Li, and Xiangyang Wang. Convolutional neural network pruning with struc- tural redundancy reduction. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 14913-14922, 2021. 2
Nan Yang, Lukas von Stumberg, Rui Wang, and Daniel Cremers. D3vo:
Deep depth, deep pose and deep uncertainty for monocular visual odometry. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1281-1292, 2020.
T. Yang, Y. Chen, and V. Sze. Designing energy eefegy-efficient convolutional neural networks using energy-aware pruning. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6071 6071-6079, 2017.
Seul-Ki Yeom, Philipp Seegerer, Sebastian Lapuschkin, Alexander Binder, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Pruning by explaining: A novel criterion for deep neural network pruning. Pattern Recognition, 115:107899, 2021.
Chenglong Zhao, Bingbing Ni, Jian Zhang, Qiwei Zhao, Wenjun Zhang, and Qi Tian. Variational convolutional neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019. 2
A APPENDIX: DATASETS
In this appendix we discuss some more details on the datasets used for experimentation.
Figure 5: Example input and target images of the (Left) Circle-Square (CS), (middle) Cam Vid, (right) real-world dynamic CT datasets.
Simulated Circle-Square (CS) dataset: We used a simulated high-noise 5-class segmentation dataset containing 256 256 images of randomly placed squares and circles (CS dataset) (Pelt & Sethian, 2018) (see Figure 5). The objects were assigned a random grey value and Gaussian noise was added the images. In total, we generated 1000 training, 250 validation, and 100 test images. Experimental results on the CS dataset are quantified using global accuracy, i.e., the ratio of correctly classified pixels, regardless of class, the total number of pixels.
The Cambridge-driving Labeled Video Database (CamVid (Brostow et al., 2008; 2009) a collection videos with labels, captured from the perspective of driving automobile. In total, 700 labeled frames are split into 367 training, 100 validation, and 233 test images. As there are few training images, we combined the training and validation datasets and trained for fixed 500 epochs. Similar to other papers that apply CNNs to Cam (Badrinarayanan et al., 2017; Paszke et al., 2017), we use classes, and a single class representing unlabeled pixels (see Figure 5).
CamVid:
We used median frequency balancing (Bigen & Fergus, 2015) to balance classes for training, and set the unlabeled class weights to zero. During training, we used data augmentation by cropping and (horizontally) flipping input images.
Real-world dynamic CT dataset: The real-time dynamic X-ray CT dataset contains images of dissolving tablet suspended in gel (Coban & Lucka, 2019; Coban et al., 2020). The bubbles are to be segmented within glass container filled with gel (Schoonhoven et al., 2020) (see Figure 5). The dataset consists of 512 x 512 images, split into 9216 training images, 2048 validation images, and 1536 test images. As in Schoonhoven et al. (2020), we use the Fl-score because the large amount of background pixels make global accuracy unsuitable metric.
13

---

Under review as a conference paper at ICLR 2022
Unprumed
Random
Magnitude
Operator norm
LEAN
Figure 6: Adjacency matrices of active convolations lnn white) after pruning. All pruned network were pruned to ratio of 10%. From trained real dynamic CT randomly pruned
right, have unpruned convolutions, strictured magnituee pruning, strictured openato norm pruning, and LEAN..
layer
B APPENDIX: REDUCING THE SIZE OF THE PRUNING GRAPH
The procedure outlined in Section 4 can lead to large pruning graphs but the size of the graph can be reduced. First, according Equation 3, the operator norm of ReLU Therefore, the combination of convolution followed by ReLU can be combined into single edge whose weight equals the norm the convolution.
Batch normalization often succeeds a convolution. normaaizmmiiinioonn scaling is applied with dif- ferent learned parameters per input channel, and output a single channel. Therefore, the input con- volution edge and the following batch normalization edges can be combined. The edges can be combined into a single edge whose weight the product of the two edge weights, preserving path length.
C APPENDIX: STRUCTURE OF PRUNED MS-D NETWORKS
To investigate the structure of pruned networks plotted the adjacency matrices of pruned net- works where an entry is 0 it is pruned (black) and I is still active (white). Here, we show the adjacency matrices of MS-D networks pruned to ratio of 10% in Figure 6. After pruning, LEAN retains only connections linked to nearby layers in the densely connected MS-D network. Compared individual filter pruning, LEAN exposes a distinct structure which may suggest that LEAN could be used for architecture discovery.
14


Reviews:
[{"review_id": "eBKLG186D9x", "reviewer": "Reviewer_rCV2", "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": "Strengths:\n1. The idea of using a graph-based algorithm for structured pruning is novel and interesting. Since LEAN prunes the network by keeping the longest path in the graph, it can use the global pruning ratio without worrying about generating a disconnected network. Therefore, it may prune much more aggressively in some layers than the other two structured pruning methods.\n2. Experiment results show great potentials for LEAN pruning.\n\nWeaknesses:\n1. A primary concern is on the evaluation. (a) The paper only compares LEAN with two naive structured pruning strategies, but not other more advanced methods. (b) The datasets used are too small (e.g., 1000 training examples in the Simulated CS dataset). It is not clear whether applying ResNet50 or U-Net4 is reasonable. Why not use those commonly used datasets (e.g., Cifar10, ImageNet) and networks for evaluation? (c) The speedup results are only shown for an MS-D network on the dynamic X-ray CT dataset. And the paper mentioned that it uses a custom MS-D model which loads only the unpruned filters. Then I wonder what the speedups of networks pruned with other structured pruning methods or unstructured pruning methods are with such customized implementations.\n2. I would like to see some theoretical analysis on why LEAN outperforms the basic structured pruning methods such as structured magnitude pruning or operator norm pruning. It may help make the paper more rigorous.\n3. The authors may want to improve the presentation to better describe the definition of preliminaries and how to construct the pruning graph. Figure 1 (B) is confusing. \n\n\nMinor comments:\n1. The figures are not black/white printer friendly.\n2. Most of the related works discussed in section 2 are those before 2020. I would like to see more discussions on the most recent related pruning works.\n3. It might be better also to report the accuracy/F1-score/mIoU of the unpruned network in the paper.\n4. It would be good to see the structure of the pruned networks with LEAN in either the main paper or the appendix.\n5. In the last paragraph of section 6.1, the paper mentions structured magnitude pruning performs slightly better than LEAN for a few pruning ratios with U-Net4 and the CamVid dataset. But it doesn't give any explanation or discussion.", "summary_of_the_paper": "This paper proposes the LongEst-chAiN (LEAN) method to perform structured pruning of CNN networks. LEAN maps a CNN network to a pruning graph, where every channel of input/output is a node, and every operator is an edge connecting input and output nodes. It uses the operator norms as the weights of edges. Then it prunes the network by keeping the longest path in the graph iteratively until it reaches the target pruning ratio. This paper demonstrates the effectiveness of LEAN pruning by comparing it to two structured pruning methods (structured magnitude pruning, operator norm pruning) across three image segmentation datasets (Simulated Circle-Square dataset, CamVid, Real-world dynamic CT dataset) and three CNN architectures (MS-D, U-Net4, and ResNet50). Experiment results show that LEAN outperforms the other two structured pruning methods as it achieves similar model qualities with much smaller pruning ratios in most cases. Also, the paper shows that a MS-D model pruned with LEAN is 10.9X faster than the unpruned network in practice.", "summary_of_the_review": "Overall, the idea of the paper is novel and interesting, and the experiment results look promising. However, the paper fails to compare LEAN with the most advanced related works on structured pruning. The datasets used in the experiments are too small, and the experimented tasks are not commonly used in CNN pruning works. So it is hard to justify the advances of the proposed pruning method. Also, the presentation of the paper needs to be improved.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "RB8YtKrm1f1", "reviewer": "Reviewer_wyEq", "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": "Strengths:\nPropose the new concept of the longest chain path over DAG, which is used in model pruning. \n \nWeakness:\n1.  The algorithm is actually in a greedy manner to remove the path one by one. Actually, in previous existing work, there are some discussions about how to deal with the wrongly pruned channels at the early stages of pruning. Any discussion about this issue? \n2.  Any comparisons on classification benchmarks on imagenet? I think as a model pruning method, it is necessary to compare with other many SOTA pruning methods on classification benchmarks, to demonstrate its superiority. \n3. For image segmentation tasks mainly discussed in the paper, the comparing methods are the only magnitude and operator norm, which I think is also not enough. ", "summary_of_the_paper": "This paper abstracts the AI model as DAG and proposes to use the longest chain path with accumulated operator norm as criteria to perform a greedy pruning method. ", "summary_of_the_review": "Due to the aforementioned weakness, I temporarily think this paper is marginally below the acceptance threshold. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KkpBUaBmLU", "reviewer": "Reviewer_ami3", "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": "The idea is somewhat novel and sound. It is proved to be effective in the evaluation.", "summary_of_the_paper": "This paper proposes a pruning method for CNNs by using a graph-based algorithm. It was evaluated by using CS, CamVid, and dynamic CT dataset.", "summary_of_the_review": "The size of the databases used for the evaluation seems rather small. Hence, the improvement may be obtained from the adaptation of models to the target domain. It would be better to evaluate this method by using datasets with a larger size to clarify this point. Also the comparison with the existing pruning methods are not sufficient.", "strength_and_weaknesses": "", "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": "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": "Aid0tTVN0ah", "reviewer": "Reviewer_XPch", "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": "The method is simple in its approach, which allows the method to be easy to understand.  Suggestions for improvement are minor: Comparisons to additional methods presented in the related work and corresponding benchmarks would strengthen the results (e.g. ResNet per Dong & Yang 2019). Benchmarks for the full network could help better contextualize pruned results. Replicates are presented in a way that is difficult to distinguish methods from one another.  For example it's difficult to distinguish light blue vs gray lines in Figure 3.  Additionally, variability of speedup between training runs is not presented in figure 4. Moreover, the relative number of remaining convolutions metric is presented a bit vaguely.  It's not clear why some panels have these metrics missing.  Additionally, it's not clear how one would calculate what accuracy is used to calculate \"relative number of convolutions at equal accuracy\" for each graph.", "summary_of_the_paper": "The authors propose a structured pruning method which turns structure pruning into a graph pruning problem.  The authors represent each input, output pair as an operator node, with edges measured by operator norms between operators.  The authors then propose an iterative structured pruning algorithm which prunes layers based on the longest path in the graph.  They then evaluate their method on three image segmentation tasks.", "summary_of_the_review": "Overall, the method is easy to understand and the paper is clearly presented.  Some organizational and presentation changes could help make the results easier to interpret.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "95XZaFRYSj_", "reviewer": "Reviewer_xFHB", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n1. The proposed approach Use graph-based concepts for network pruning, which is a new approach that raises researchers' interest recently.\n2. The proposed approach can prune the network with large pruning ratios.\n3. The proposed approach works on segmentation tasks.\n\nCons:\n1. The introduction and related work sections are not described well.\n\n    The motivation of the proposed methods is not described well. Avoiding disconnectness seems to be a weak reason. The related work section lists a number of previous pruning works but it seems difficult to connect them with the proposed approach. On the other hand, related graph-based pruning approaches are missing. For example, [1] proposes to build a graph for each conv layer and prune filters based on the graph complexity. \n\n    [1] Convolutional neural network pruning with structural redundancy reduction. In CVPR 2021.\n\n\n2. The proposed approach lacks theoretical justification. It is not clear why extracting the longest chain in the graph is the optimal choice for filter pruning.\n\n\n3. The methodology is not presented well and is hard to follow. It is presented narratively, without formal definitions of the concepts used in the approach and equations, making it difficult to understand the implementation details. Specifically,\n\n    -In Fig. 1(B), what do the blue line, (i) and (ii) mean?\n\n    -It is hard to distinguish the concepts of operation and operator. According to Section 4.1, a node is a channel and an edge is an operator. However, in Fig. 1(B) it seems that a node represents the output of a filter rather than a channel?\n\n    -I think the calculation of operator norms is very important and should be moved from the Appendix to the main text. (On the other hand, the description of datasets in Section 5 is trivial.)\n\n    -It is unclear why $||AB||  \\approx ||A||\\cdot||B||$.\n\n    -It is unclear how to search for the longest path in the graph.\n\n\n4. The experiment settings and results are not satisfactory.\n\n    The proposed approach is not evaluated with benchmark classification tasks such as CIFAR and ImageNet. Besides, only structured magnitude and operator norm pruning are used for performance comparison. Both approaches are proposed many years ago. State-of-the-art methods should be added for comparison.", "summary_of_the_paper": "This paper proposes a structured pruning approach by building a graph according to the structure and weights of the CNN to be pruned. The operators with the longest chain in the graph as preserved while others are pruned. The proposed approach is evaluated with several network structures (MS-D, U-Net, ResNet) and datasets.", "summary_of_the_review": "Overall, I think there are several nontrivial weaknesses in the manuscript as listed above. I currently give a negative score but I will consider changing it if the authors' feedback resolves the concerns.", "strength_and_weaknesses": "", "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:

Meta-review: I do not recommend accepting this paper, although I make this decision with reservations. The review quality for this paper was not particularly strong, and I wish to emphasize to the authors that I read the paper myself in detail in the process of writing this metareview.

This paper proposes a new structured pruning technique called LEAN. It involves computing an operator norm of the convolutions in a convolutional neural network, multiplying these norms over paths through the network, and keeping the paths with the highest such values (and pruning everything else). This paper makes the argument that this metric is robust to scaling and prevents network discontinuities. (In this way, the technique is very reminiscent of SynFlow (Tanaka et al., Pruning Neural Networks without any data by iteratively conserving synaptic flow) in terms of motivation and resulting technique, although SynFlow is unstructured. I do not mean this as a criticism - just a suggestion for the authors of a connection they might be able to make in the future.)

One big concern I have about this paper based on the methodology alone is as follows: the paper states a number of hypotheses about why this is a sensible way to prune (e.g., in the beginning of Section 4). I see no reason why any of these hypotheses are wrong, but the paper never makes an effort to evaluate any of them. I don't mean a theoretical justification here - that's difficult and unlikely to yield useful information about what happens in practice. I mean experiments to ablate the salient properties of the heuristic mentioned in the paragraph at the beginning of Section 4 (Does scaling invariance actually matter in practice? Is network disconnectivity actually a risk in practice?).

My biggest concerns about the paper, however, are in the evaluation. I share two major reviewer concerns that were mentioned:
(1) The paper compares to a very limited set of baseline pruning methods, and relatively older ones at that (2019 is indeed old in the world of pruning).
(2) The paper does not look at standard, "large-scale" benchmarks for computer vision - namely, ResNet-50 on ImageNet.

Neither of these concerns is necessarily decisive in my view. For example, with respect to Concern 1, the reviewers unhelpfully do not suggest very many additional structured pruning benchmarks to consider, and I think the additional baselines added during the revision process have softened this concern. I would also recommend taking a look at "Growing Efficient Deep Networks by Structured Sparsification" (Yuan et al) for a useful method and a good set of baselines. There are an arbitrary number of baselines one could add and the structured pruning space is a confusing mess, but I think the claims in this paper merit more than are currently present.

With respect to Concern 2, I'm even more conflicted. On the one hand, I have rarely seen any pruning techniques proposed for or evaluated on vision tasks beyond image classification, despite the fact that - in the real world - segmentation is much more popular than it would seem by reading the ICLR proceedings. To that end, I applaud the authors for focusing on those settings and I see substantial value in a paper that does so. On the other hand, ResNet-50 on ImageNet (among other standard classification benchmarks) is the de facto measuring stick for evaluating pruning methods in computer vision, and the exclusive focus on segmentation here means it is very difficult to compare the proposed technique to other benchmarks. If the paper is to focus on segmentation alone, this places a higher burden on adding many additional comparisons to other methods (i.e., Concern 1). Finally, I don't see any reason why the paper *couldn't* also include ResNet-50 on ImageNet or the like in addition to segmentation; if it is a limitation on the compute available to the authors (something I empathize with), they did not say so in any of the author responses. Upon reading the author responses, I was left asking, "Why not both?"

For those reasons, I do not recommend accepting the paper, although I think there are some good reasons to value the paper's contributions. At the end of the day, there are some relatively simple things that could be changed to make the paper much easier to contextualize within the pruning literature. As of right now, it would be very difficult for me to say whether or in what contexts this method should actually be used in practice.

(P.S. I agree with the reviewers that Figure 3 is exceptionally hard to parse.)
Decision: Reject