Organizations: School of ECE, National Technical University of Athens, Greece · Robotics Institute, Athena Research Center, Maroussi, Greece · HERON - Hellenic Robotics Center of Excellence, Athens, Greece · Department of Computer Science, ETH Zurich
We present TropNNC, a framework for compressing neural networks with linear and convolutional layers and ReLU-type activations using tropical geometry. By representing a network's output as a tropical rational function, TropNNC enables structured compression via reduction of the corresponding tropical polynomials. Our method identifies redundancy via similarity and improves upon the geometric approximation of previous work by adaptively selecting the weights of retained neurons. We relate it to SVD and spectral clustering, and provide insights into network compression beyond the specific setting considered. We provide the tightest known theoretical compression bound, and the first successful application of tropical geometry to convolutional layers. TropNNC requires access only to network weights - no training data - and achieves competitive performance on MNIST, CIFAR, and ImageNet, matching strong baselines such as ThiNet and CUP.
Figures & tables
Figure 1: Neural network with one hidden ReLU layer. The first linear layer has weights {aiT} with bias {bi} corresponding to node i∈[n] and the second has weights {cji} between nodes j∈[m],i∈[n]
{
∣ci∣(aiT,bi):ci>0},
{
∣ci∣(aiT,bi):ci<0}.
Algorithm 1 TropNNC, Single output
Figure 2: Example execution of TropNNC compared to the method of Misiakos et al. (2022) . The original zonotope in Figure 2(a) corresponds to a network with 3 neurons, each providing one of its generators. To compress the hidden layer to 2 neurons, we equivalently seek to approximate the original zonotope by zonotopes of order 2. We cluster the generators/neurons into 2 clusters based on similarity. Misiakos et al. (Fig. 2(b) ) replace the generators of a cluster by the cluster center. Instead, TropNNC (Fig. 2(c) ) replaces the cluster by the sum of the generators of the cluster, leading to a better zonotope approximation.
Figure 3: Example of simultaneous zonotope approximation for a network with 2 outputs and 2 hidden neurons. With multiple zonotopes, one is forced to choose a common direction between the ideal diagonals.
Percentage of Remaining Neurons
MNIST
Fashion-MNIST
Neural Path K-means
TropNNC
Neural Path K-means
TropNNC
100.0
98.54 ± 0.16
98.54 ± 0.16
89.16 ± 0.21
89.16 ± 0.21
50.0
97.85 ± 0.39
98.49 ± 0.14
88.17 ± 0.46
89.00 ± 0.25
25.0
96.69 ± 1.06
98.36 ± 0.14
86.33 ± 0.87
88.70 ± 0.22
10.0
96.25 ± 1.39
97.96 ± 0.35
84.91 ± 1.28
88.24 ± 0.40
5.0
95.17 ± 2.36
97.06 ± 0.73
81.48 ± 3.90
87.42 ± 0.46
Table 1: Comparison of Neural Path K-means and TropNNC on MNIST and Fashion-MNIST
Figure 4: Compression of linear and convolutional layers of ReLU neural networks on MNIST datasets.
Figure 5: Compression of linear layers of AlexNet and convolutional layers of VGG on CIFAR datasets.
Method
Threshold
#params ↓
FLOPS ↓
Acc. ↑
Original
-
14.7M
0.63G
93.64
CUP
0.15
6.24M
0.46G
92.41
TropNNC (3 iters)
0.014
5.22M
0.46G
93.58
CUP
0.20
4.62M
0.42G
67.91
TropNNC (3 iters)
0.017
3.61M
0.42G
93.02
CUP
0.25
3.61M
0.39G
16.02
Table 2: Comparison of CUP and TropNNC (variant 1) accuracy across different pruning thresholds on CIFAR10, VGG.
Method
Threshold
#params ↓
FLOPS ↓
Acc. ↑
Original
-
11.69M
3.64G
69.75
CUP
0.5
11.66M
3.58G
66.80
TropNNC (v2)
1.1
11.66M
3.48G
68.95
CUP
0.6
11.49M
3.38G
53.40
TropNNC (v2)
1.2
11.46M
3.25G
61.30
CUP
0.65
11.17M
3.15G
28.45
Table 3: Comparison of CUP and TropNNC accuracy across different pruning thresholds on ImageNet, ResNet18.
Method
Threshold
#params ↓
FLOPS ↓
Acc. ↑
Original
-
14.7M
0.63G
93.64
TropNNC
0.02
2.75M
0.39G
86.2
TropNNC (3 iters)
0.021
2.52M
0.38G
91.2
TropNNC
0.025
1.80M
0.33G
34.89
TropNNC (3 iters)
0.0255
1.76M
0.33G
69.95
Table 4: Comparison of non-uniform TropNNC and non-uniform iterative TropNNC (variant 1) accuracy on CIFAR10, VGG.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Example of reduction of tropical polynomial.
Figure 7: (a) depicts a single-variate tropical polynomial, (b) depicts a multi-variate tropical polynomial, (c) depicts a single-variate tropical rational function, (d) depicts a multi-variate tropical rational function
Figure 8: Operations on tropical polynomials. ENewt(f∨g) corresponds to the convex hull of the union of the vertices of the polytopes ENewt(f),ENewt(g) . ENewt(f+g) corresponds to the Minkowski sum of ENewt(f),ENewt(g) . For the polytope ENewt(f∨g) we illustrate with blue the upper envelope, which consists of a single face. The vertices of the upper envelope are the only non reduntant terms of the polynomial f∨g .
Figure 9: Empirical verification of assumptions on a feedforward deepNN (left) and on a convolutional VGG (right) network. For the weight-decay assumption, we plot the greatest value Ω(1) such that the bound ( 5 ) holds. For all pruning ratios, this constant exceeds 1 (red threshold), and the assumption holds (even in our favor). Note that for VGG, Ω(1) was not uniform among the different layers, with deeper layers giving better values than earlier ones. The plot presents Ω(1) for an earlier layer giving worse/smaller Ω(1) . Still, it holds Ω(1)>1 . For cluster compactness, we plot the average of the smallest ϵk satisfying the definition. It follows a reverse relation to the accuracy of the compressed model, indicating it is linked to the compressibility of the network. Note that the quantities follow a different scale (TropNNC → "Accuracy (%)" scale; Compactness → "Compactness Metric" scale; Weight-decay + red threshold → "Weight-decay Metric" scale.)
Department of Mathematics, Imperial College London, UK · London School of Geometry and Number Theory, UK · Department of Electrical and Computer Engineering, Rice University, USA +2