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.

本文提出了一种名为最小生成树（MST）压缩的新方法，用于学习压缩和加速二值神经网络（BNNs），旨在降低计算成本和延迟，实验结果表明这种方法在资源受限的边缘计算设备上能够显著提高压缩比率并实现可忽略的准确度下降。