  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.
