  The current success of Graph Neural Networks (GNNs) usually relies on loading
the entire attributed graph for processing, which may not be satisfied with
limited memory resources, especially when the attributed graph is large. This
paper pioneers to propose a Binary Graph Convolutional Network (Bi-GCN), which
binarizes both the network parameters and input node attributes and exploits
binary operations instead of floating-point matrix multiplications for network
compression and acceleration. Meanwhile, we also propose a new gradient
approximation based back-propagation method to properly train our Bi-GCN.
According to the theoretical analysis, our Bi-GCN can reduce the memory
consumption by an average of ~31x for both the network parameters and input
data, and accelerate the inference speed by an average of ~51x, on three
citation networks, i.e., Cora, PubMed, and CiteSeer. Besides, we introduce a
general approach to generalize our binarization method to other variants of
GNNs, and achieve similar efficiencies. Although the proposed Bi-GCN and
Bi-GNNs are simple yet efficient, these compressed networks may also possess a
potential capacity problem, i.e., they may not have enough storage capacity to
learn adequate representations for specific tasks. To tackle this capacity
problem, an Entropy Cover Hypothesis is proposed to predict the lower bound of
the width of Bi-GNN hidden layers. Extensive experiments have demonstrated that
our Bi-GCN and Bi-GNNs can give comparable performances to the corresponding
full-precision baselines on seven node classification datasets and verified the
effectiveness of our Entropy Cover Hypothesis for solving the capacity problem.
