# MST-compression: Compressing and Accelerating Binary Neural Networks with Minimum Spanning Tree

arXiv: https://arxiv.org/abs/2308.13735 · HTML: https://mlsanity.com/paper/2308.13735/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 26 Aug 2023.

## Builds on (most cited first, 23 of 23)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Differentiable Soft Quantization: Bridging Full-Precision and Low-Bit Neural Networks](https://mlsanity.com/paper/1908.05033/) (2019)
- [Bi-Real Net: Enhancing the Performance of 1-bit CNNs With Improved Representational Capability and Advanced Training Algorithm](https://mlsanity.com/paper/1808.00278/) (2018)
- [ReActNet: Towards Precise Binary Neural Network with Generalized Activation Functions](https://mlsanity.com/paper/2003.03488/) (2020)
- [Forward and Backward Information Retention for Accurate Binary Neural Networks](https://mlsanity.com/paper/1909.10788/) (2019)
- [FINN: A Framework for Fast, Scalable Binarized Neural Network Inference](https://mlsanity.com/paper/1612.07119/) (2016)
- [Towards Accurate Binary Convolutional Neural Network](https://mlsanity.com/paper/1711.11294/) (2017)
- [Deep Learning with Low Precision by Half-wave Gaussian Quantization](https://mlsanity.com/paper/1702.00953/) (2017)
- [XNOR-Net++: Improved Binary Neural Networks](https://mlsanity.com/paper/1909.13863/) (2019)
- [Rotated Binary Neural Network](https://mlsanity.com/paper/2009.13055/) (2020)
- [Regularizing Activation Distribution for Training Binarized Deep Networks](https://mlsanity.com/paper/1904.02823/) (2019)
- [FINN-R: An End-to-End Deep-Learning Framework for Fast Exploration of Quantized Neural Networks](https://mlsanity.com/paper/1809.04570/) (2018)
- [ReCU: Reviving the Dead Weights in Binary Neural Networks](https://mlsanity.com/paper/2103.12369/) (2021)
- [AdaBin: Improving Binary Neural Networks with Adaptive Binary Sets](https://mlsanity.com/paper/2208.08084/) (2022)
- [FleXOR: Trainable Fractional Quantization](https://mlsanity.com/paper/2009.04126/) (2020)
- [Sub-bit Neural Networks: Learning to Compress and Accelerate Binary Neural Networks](https://mlsanity.com/paper/2110.09195/) (2021)
- [Towards Fast and Energy-Efficient Binarized Neural Network Inference on FPGA](https://mlsanity.com/paper/1810.02068/) (2018)

## Abstract (arXiv)

Binary neural networks (BNNs) have been widely adopted to reduce the computational cost and memory storage on edge-computing devices by using one-bit representation for activations and weights. However, as neural networks become wider/deeper to improve accuracy and meet practical requirements, the computational burden remains a significant challenge even on the binary version. To address these issues, this paper proposes a novel method called Minimum Spanning Tree (MST) compression that learns to compress and accelerate BNNs. The proposed architecture leverages an observation from previous works that an output channel in a binary convolution can be computed using another output channel and XNOR operations with weights that differ from the weights of the reused channel. We first construct a fully connected graph with vertices corresponding to output channels, where the distance between two vertices is the number of different values between the weight sets used for these outputs. Then, the MST of the graph with the minimum depth is proposed to reorder output calculations, aiming to reduce computational cost and latency. Moreover, we propose a new learning algorithm to reduce the total MST distance during training. Experimental results on benchmark models demonstrate that our method achieves significant compression ratios with negligible accuracy drops, making it a promising approach for resource-constrained edge-computing devices.