Convolutional Neural Network Pruning with Structural Redundancy Reduction

In plain words

A convolutional network can often be made smaller and cheaper to run by deleting whole filters, which are the units that detect patterns in an image. The usual approach ranks every filter in the network by how important it looks and deletes the weakest ones, wherever they sit.

This paper argues that the more useful question is where the network wastes capacity. If one layer holds many filters that do nearly the same job, removing some of them from that layer costs little, even if the individual filters look important on their own. The authors make this idea concrete. For each layer they compare the filters as points in a space, connect the ones that nearly coincide, and count how many separate clusters and how many representative filters are needed to cover the rest. Layers with many redundant filters get pruned first, and inside each chosen layer the usual smallest-weight rule decides which filters go.

The practical point is that the layer chosen for pruning is decided per network, not by a single global ranking. The method is also meant to be used on top of an existing pruning rule rather than replacing it.

TL;DR

Layer-adaptive channel pruning. Each conv layer gets a redundancy score from a graph over its filters, the most redundant layers lose filters first, and the filters within a layer are removed by smallest absolute weight, followed by fine-tuning. Author-reported ResNet results on CIFAR-10 and ImageNet beat the compared channel-pruning baselines at comparable FLOPs reduction. The paper's theory assumes many filters per layer, and the experiments use only ResNets in the main text.

Problem

Channel (filter) pruning removes whole filters so that the result runs on normal hardware, but the usual rule of dropping the least important filters across all layers assumes importance is comparable between layers §1. The authors argue that this belief does not hold: pruning in a layer with much structural redundancy can beat pruning the least important filters globally §1 §3. Methods that rank filters by a criterion (weight magnitude, activation, Taylor estimates, reconstruction error or similarity) are the baselines they compare against §2 §5.1.

Assumptions in the analysis: the layer must contain many filters (the argument is asymptotic in the number of filters) and filter contributions must satisfy the bounds listed in the Method's theory section §3. The paper states that the asymptotic condition can be relaxed in practice but gives no proof of that §3.

Method

Theory: why pruning the most redundant layer helps §3

The authors model each filter's contribution to performance as a positive random variable. Two layers are modelled, one with m filters and one with n \gg m filters. A layer "performs well" if the sum of its contributions exceeds a threshold (a for layer \xi, b for layer \eta). The system performance is the sum of the two probabilities of these events, with no division by m or n §3. Five cases are compared: no pruning; random pruning in the \eta layer; pruning the least important filter in the \eta layer; pruning the least important filter in the \xi layer; and pruning the globally least important filter §3.

p_o = P\Big(\sum_{i=1}^m \xi_i \ge a\Big) + P\Big(\sum_{i=1}^n \eta_i \ge b\Big) eq. 1

p_{\eta r} = P\Big(\sum_{i=1}^m \xi_i \ge a\Big) + P\Big(\sum_{i=1}^{n-1} \eta_i \ge b\Big) eq. 2

p_{\underline{\eta}} = P\Big(\sum_{i=1}^m \xi_i \ge a\Big) + P\Big(\sum_{i=1}^{n} \eta_i - \underline{\eta} \ge b\Big) eq. 3

p_{\underline{\xi}} = P\Big(\sum_{i=1}^m \xi_i - \underline{\xi} \ge a\Big) + P\Big(\sum_{i=1}^{n} \eta_i \ge b\Big) eq. 4

p_g = \frac{m}{m+n}\, p_{\underline{\xi}} + \frac{n}{m+n}\, p_{\underline{\eta}} eq. 5

Here \underline{\eta} = \min\{\eta_1, \dots, \eta_n\} and \underline{\xi} = \min\{\xi_1, \dots, \xi_m\}. The claim is that random pruning in the redundant layer, p_{\eta r}, is at least as good as pruning the least important filter in the other layer, under the assumptions below §3. The inequality chain stated is p_{\underline{\xi}} \le p_g \le p_{\eta r} \le p_{\underline{\eta}} \le p_o §3. The sandwich used to prove it is

P\Big(\sum_{i=1}^{n-1}\eta_i \ge b\Big) \le P\Big(\sum_{i=1}^{n}\eta_i - \underline{\eta} \ge b\Big) \le P\Big(\sum_{i=1}^{n}\eta_i \ge b\Big) eq. 6

which relies on 0 \le \eta_n - \underline{\eta} \le \eta_n §3.

Assumptions used by the proof §3:

• variances bounded: there is C_1 > 0 with \mathbb{D}\eta_i \le C_1 eq. 7;
• at most C_2 n correlated pairs, with 0 \le C_2 \le 1 §3;
• means bounded below: there is \epsilon_0 > 0 with \mathbb{E}\eta_i \ge \epsilon_0 eq. 9;
• Chebyshev's inequality gives P\big(\tfrac{1}{n}|\sum_i (\eta_i - \mathbb{E}\eta_i)| \ge \epsilon\big) \le \frac{\mathbb{D}(\sum_i \eta_i)}{\epsilon^2 n^2} eq. 8, which tends to zero as n \to \infty;
• n \to \infty is used for the limit step; the paper requires n > 2b/\epsilon_0 before taking the limit §3.

The authors state that they make no distributional assumption on the contributions, and that the conclusion is asymptotic in n §3. The inequality p_g versus p_{\underline{\eta}} is not settled by the limit, because m/n is not assumed to tend to zero §3. The paper says the assumption "can be relaxed" in practice, but this is supported by experiments only, not by a bound §3 §6.1.

Graph-based redundancy measure §4

Notation. The network has L layers. Layer i has N_i input and N_{i+1} output channels and filters of size h_i \times w_i §4.1. Channel pruning seeks weights with at most K non-zero filters §4.1.

Graph establishment §4.2. For a layer with N filters, flatten each filter and normalise it to unit length. The filters become points on the unit sphere in \mathbb{R}^n, where n = N_i \times h_i \times w_i §4.2. Join two filters x, y by an edge when

|x - y| / \sqrt{n} \le \gamma §4.2

with \gamma > 0 a fixed threshold. The paper uses \gamma = 0.034 §5.1. A vertex is a filter, and the graph metric d(x, y) is the minimum number of edges between two filters §4.1.

Quotient space size k §4.2. The connected components of the graph. Two filters are equivalent if a path joins them. k is the number of components §4.2.

1-covering number N_1^c §4.2. The minimum number of balls of radius 1 (sets of filters within graph distance 1) needed to cover all filters. The exact value is NP-hard to compute, so the authors estimate it §4.2 §6.1.

Estimate of N_1^c §4.2. Build two greedy sequences. For radius \ell = 1, repeatedly pick the unvisited filter with the largest degree in the graph, add its ball, and stop when the balls cover the layer; the number of picks is n_1. For radius \ell = 2 the same procedure gives n_2. The paper proves n_2 \le N_1^c \le n_1 §4.2. The estimate used is

\tilde{N}_1^c = \tfrac{1}{2}(n_1 + n_2) §4.2

The paper gives no bound on the error of this estimate §4.2. The implementation uses \ell = 1 for the covering-number definitions §4.2.

Redundancy score §4.2.

R(X) = \frac{N}{w_1 k + w_2 N_1^c} eq. 10

where N is the number of filters in the layer and w_1, w_2 are weights that trade off k against N_1^c. The paper uses w_1 = 0.35 and w_2 = 0.65 §5.1.

With \gamma \to 0, k = N_1^c = N and R = 1 for every layer, so pruning becomes uniform across layers. With \gamma \to \infty, k = N_1^c = 1 and R = N, so the layer with the most filters is pruned first §6.3.

Pruning procedure §4.2

1. Build the graph for every layer and compute R for each eq. 10.
2. Remove one filter at random from the layer with the highest R, which deletes its vertex and edges.
3. Recompute the redundancy after the graph is rebuilt, and repeat until the target is reached (for example a set number of filters removed) §4.2.
4. Within each layer, keep the filters ranked by smallest absolute weight (min-weight rule) and remove the rest §4.2.

Layers are ranked separately. The number of filters removed from each layer comes from step 3, so the result is layer-adaptive §4.2. The filter selection criterion in step 4 is one choice; the authors say any filter ranking can be used §4.2.

# Choose how many filters to remove from each layer  [§4.2]
# Input:  per-layer filter weights, gamma, w1, w2, number of removals
# Output: removal count per layer

def select_layer_budgets(layers, gamma, w1, w2, num_removals):
    # Start with each layer's current filter count  [§4.2]
    counts = {layer: layer.num_filters for layer in layers}
    # Repeat until the target number of removals is reached  [§4.2]
    for step in range(num_removals):
        # Score each layer by its redundancy  [§4.2] [eq. 10]
        scores = {
            layer: redundancy(layer.weights, gamma, w1, w2)
            for layer in layers
        }
        # Remove one filter from the most redundant layer  [§4.2]
        # (random vertex removal; see Pitfalls on how to recompute)
        chosen = max(scores, key=scores.get)
        counts[chosen] -= 1
    return counts

# Redundancy of one layer's filter graph  [§4.2] [eq. 10]
# Input:  weights (N, dim), filters flattened and unit-normalised
# Output: scalar redundancy

def redundancy(weights, gamma, w1, w2):
    # N is the number of filters in the layer  [§4.2]
    num_filters = weights.shape[0]
    # Connect filters closer than gamma * sqrt(dim)  [§4.2]
    edges = distance(weights) <= gamma * sqrt(dim)
    # k = number of connected components  [§4.2]
    k = count_components(edges)
    # Greedy covers with radius 1 and 2  [§4.2]
    n1 = greedy_cover(edges, radius=1)
    n2 = greedy_cover(edges, radius=2)
    # Average of the two covers estimates N1c  [§4.2]
    n1c = (n1 + n2) / 2
    # Redundancy  [§4.2] [eq. 10]
    return num_filters / (w1 * k + w2 * n1c)

Filter selection and fine-tuning §4.2 §5.1

Pruned networks can be trained from scratch or obtained by pruning a pre-trained model and fine-tuning. The experiments use the second option: prune the pre-trained model with the numbers of filters chosen above, then fine-tune the slimmed network §5.1. The paper picks the min-weight rule as a simple, common choice that needs no forward passes over training data to rank filters §4.2.

Hyperparameters

Results

Author-reported. Setup: ResNet20 and ResNet56 on CIFAR-10, with baseline accuracies from the authors' own training runs §5.1; ResNet50 on ImageNet ILSVRC-2012, starting from torchvision pre-trained weights and pruned in single-shot mode §5.1. Baselines are the methods named in §5.2 and the values below are as reported in each table. Table cells are quoted as printed.

CIFAR-10 tab. 1. Accuracy before and after pruning, drop (negative means a gain) and FLOPs reduction.

MW results on CIFAR-10 come from the authors' own implementation tab. 1 caption. The "before" baseline differs between rows, so the drop columns are not on one common baseline.

ImageNet ResNet50 tab. 2. Top-1 and top-5 accuracy before and after pruning, drops and FLOPs reduction.

MW, APoZ and Taylor are the authors' own implementations tab. 2 caption. GM and GAL appear twice at different FLOPs reductions.

Cost of the 1-covering number tab. 3. Seconds to compute the oracle value and the proposed estimate. Hardware not stated.

Filter selection criterion, AlexNet on CIFAR-10 tab. 4. 30% FLOPs pruned after redundancy-guided layer choice, accuracy after fine-tuning. MA is not defined in the compiled text.

Redundancy measure, ResNet50 ImageNet tab. 5. Same baselines as tab. 2.

Headline numbers (author-reported).

• ImageNet ResNet50: 44.1% FLOPs reduction with 0.37% top-1 and 0.19% top-5 drop; 55.1% FLOPs with 1.02% and 0.51% drop tab. 2 §5.2.
• CIFAR-10 ResNet56: 53.8% FLOPs reduction with a test accuracy 0.37 points above its baseline; ResNet20: 45.8% with a 0.21 point gain tab. 1 §5.2.
• Uniform (MW) pruning of ResNet50 at the same FLOPs drops top-1 by 4.89% tab. 2. The paper reports the redundancy step adds about 4 points over this baseline §5.2.
• Figure 2 (a-b) shows that n_1 and n_2 agree closely across \gamma values for AlexNet and VGG16 fig. 2 §6.1. The text says no large deviations were seen in any experiment, with no table of values §6.1.

Paper vs code

No official code.

The paper contains no code link, and the fetched LaTeX source has no URL for code [raw/src/2104.03438/cvpr.tex]. GitHub searches with the WebFetch tool found: erceguder/cnn-pruning, which describes itself as an unofficial implementation and is not used; lijiang99/redundancy-graph-decomposition, owned by an unrelated user; and nothing for "SRR pruning". I also checked the repositories of the first author's GitHub account and found no pruning project.

Pitfalls

• Asymptotic argument. The formal claim assumes n \to \infty filters in the redundant layer, plus variance, mean and correlation bounds §3. The paper expects the key inequality to hold on average in practice, but offers no bound. Do not rely on the theory for layers with a few dozen filters.
• Recomputing redundancy after removal is unclear. The text says a random vertex is removed and then the redundancy is recomputed after "graph reconstruction" §4.2. It does not say whether the remaining filters are rebuilt from their weights, or whether only the vertex is deleted and k and N_1^c updated. The pseudocode above follows the first reading.
• Choosing the target. The number of filters to remove is set by the FLOPs or filter budget the authors aimed for. The paper does not give a rule that maps a FLOPs target to a filter count. The count per layer comes from the removal loop §4.2.
• Random removal versus min-weight. Removal inside the graph loop is random §4.2, but the final per-layer filter selection is by smallest absolute weight. The norm used for "absolute weights" is not stated.
• \gamma is a per-setting hyperparameter. \gamma = 0.034 is given once §5.1, with no per-dataset or per-architecture values. The sensitivity study covers only AlexNet on CIFAR-10 §6.3. Expect to re-tune it.
• Covering-number estimate. The estimate averages a radius-1 greedy cover and a radius-2 greedy cover §4.2. The greedy choice uses "maximum degree", and the paper does not say whether degree counts edges to all filters or only to uncovered ones. Ties are broken arbitrarily §4.2.
• Estimate error is not quantified. The proof of n_2 \le N_1^c \le n_1 is given §4.2, but the error of the average is only shown empirically §6.1.
• Weights w_1, w_2 are given without justification. They are chosen as 0.35 and 0.65 "to emphasise" the covering number §5.1. No ablation on them is reported.
• Baselines are not on one footing. Each table row uses its own "before" accuracy, and MW, APoZ and Taylor were re-implemented by the authors tab. 1 tab. 2. The paper does not say where the numbers for the other methods come from.
• Duplicated methods in tab. 2. GM and GAL each appear at two FLOPs ratios with different baselines (for example GM at 42.2% and at 53.5%). Read each row against its own FLOPs column.
• Main text uses ResNets only for the headline numbers. AlexNet and VGG16 are used only in the analysis §6. The paper says the progressive-pruning results and the AlexNet examples are in an appendix. The LaTeX source fetched has no appendix, so those numbers could not be checked.
• Missing details. Hardware and GPU count are not stated. Random seeds are not stated. The CIFAR training schedule used for the base models is only referred to as "the setup in He et al. 2019" §5.1.
• Table 4 MA column. "MA" (mean activation) is not defined in the compiled text, so its exact criterion must be taken from the cited sources.
• Speed claim. Table 3 times only the covering-number computation, not the whole pruning run. The paper says the real running time is almost the same as existing methods with the same filter criterion §6.1, without a table.

Lineage

• Builds on: min-weight filter ranking (cited as Li et al. 2016 in the paper) for the per-layer selection §4.2; fine-tuning strategy from He et al. 2018 (SFP) §5.1; CIFAR training setup from He et al. 2019 (GM) §5.1.
• Compared against: MW, Taylor expansion, APoZ, SFP, DCP, NISP, SNN, AutoPruner, GAL, GM, TAS, CUP, ABC, TRP, SCP, HRank §5.1 §5.2. Numbers for the methods in tab. 1 and tab. 2 are copied as reported.
• Related analysis: mentions Liu et al. 2018 and Mittal et al. 2018 on whether pruned structure matters more than kept filters §2.