PaperlayerView exact revision on arXiv

Source-linked AI summary

Binary Graph Neural Networks

Mehdi Bahri, Gaétan Bahl, Stefanos Zafeiriou

arXiv:2012.15823v2cs.LGcs.AIcs.CV

TL;DR

Graph neural networks face growing needs for smaller, faster models, while binarization has been little explored in geometric deep learning. This paper develops binarization strategies with cascaded distillation, including dynamic graph search in Hamming space. The authors report close or equal performance to floating-point models on difficult benchmarks and savings on embedded devices, while noting that their embedded speed estimate uses an unoptimized implementation.

  • Problem

    Graph neural networks need smaller, faster models, but model binarization has seen little application in geometric deep learning.

    Source: §1 · pp. 1–2

  • Method

    The paper studies GNN binarization using cascaded knowledge distillation and dynamic graph construction in Hamming space.

    Source: §1 · p. 2, §3 · p. 3, §4.2 · p. 5

  • Results

    The authors report that binary GNNs can closely match or equal floating-point models on difficult benchmarks, with significant reductions in memory consumption and inference time.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    Binary node features support high-accuracy dynamic graph models and fast inference-time graph construction using Hamming-based algorithms.

    Source: §1 · p. 2, §6 · p. 8

    The embedded speed result is estimated from profiling an unoptimized Hamming-distance implementation rather than an optimized implementation.

    Source: §5.1 · p. 8

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data. As they generalize the operations of classical CNNs on grids to arbitrary topologies, GNNs also bring much of the implementation challenges of their Euclidean counterparts. Model size, memory footprint, and energy consumption are common concerns for many real-world applications. Network binarization allocates a single bit to parameters and activations, thus dramatically reducing the memory requirements (up to 32x compared to single-precision floating-point numbers) and maximizing the benefits of fast SIMD instructions on modern hardware for measurable speedups. However, in spite of the large body of work on binarization for classical CNNs, this area remains largely unexplored in geometric deep learning. In this paper, we present and evaluate different strategies for the binarization of graph neural networks. We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks. In particular, we present the first dynamic graph neural network in Hamming space, able to leverage efficient k-NN search on binary vectors to speed-up the construction of the dynamic graph. We further verify that the binary models offer significant savings on embedded devices. Our code is publicly available on Github.

1. Introduction

Graph neural networks extend CNN-style learning to irregular data, but growing model and dataset demands make smaller, faster graph models desirable. This paper studies GNN binarization as a compression approach, including dynamic graph construction in Hamming space and acceleration on a budget ARM device.

1. Introduction

  • Growing computational complexity and graph-dataset scale increase the need for faster, smaller models, particularly where energy, storage, or inference costs matter.The passage identifies embedded devices, IoT graph learning, and CPU-based inference as relevant settings.Source: §1 · pp. 1–2
  • Binarization compresses existing GNN architectures while aiming to preserve performance, complementing rather than replacing graph-scaling methods such as sampling and architectural changes.The paper studies several binarization strategies and includes an ablation study of their techniques and hyperparameters.Source: §1 · p. 2
  • The paper introduces a binarization strategy combining techniques for binary neural networks with knowledge distillation for graph networks.It also develops dynamic graph construction in Hamming space, with the stated aim of enabling faster inference-time construction and negligible accuracy loss with real-valued weights.Source: §1 · p. 2

2. Related Work

Prior work establishes GNNs as message-passing models for graph data and develops binary networks to reduce model precision and inference costs. Existing GNN binarization studies are described as limited in scale, motivating this paper's broader focus on binarization strategies.

2. Related Work

  • Knowledge distillation transfers information from a pretrained teacher to a smaller student through logit matching or matching internal activations and relational knowledge.LSP defines local-structure vectors for graph nodes and a loss comparing student and teacher local structures.Source: §2 · pp. 2–3
  • Quantization lowers model numerical precision to reduce size and speed inference, with binary networks representing its single-bit extreme.Graph neural networks extend message-passing approaches beyond earlier spectral and attention-based formulations.Source: §2 · p. 2
  • Binary neural networks use one bit for weights and activations; XNOR-Net++ learns shared rescaling factors, while Real-to-Binary networks combine binary-model techniques with knowledge distillation.XNOR-Net introduced floating-point rescaling to reduce quantization error.Source: §2 · p. 2
  • Message passing formulates GNNs through permutation-invariant aggregation of neighbor messages and vertex updates, while EdgeConv uses max aggregation of edge messages based on feature differences.DGCNN repeatedly finds point-cloud neighbors by k-nearest-neighbor search in feature space.Source: §2 · pp. 2–3
  • Earlier GNN binarization work covered GAT and GCN on small-scale datasets, while PointNet binarization used tailored aggregation and scaling functions.The passage identifies LSP as the only GNN-specific knowledge-distillation method at the time of writing.Source: §2 · p. 3

3. Method

The method adapts binary-network techniques to graph convolutions and trains increasingly quantized students through cascaded distillation. It also investigates design choices for binarization, learnable rescaling, activations, and graph-neighbor search.

3. Method

  • Binarizing graph message passing requires choosing whether and how to quantize node features, edge messages, aggregation, and update functions.The graph operator is more general than a Euclidean convolution, which reduces to a single matrix product to quantize.Source: §3 · p. 3
  • The method uses sign binarization with a straight-through estimator for gradients and mean-centers and clips latent weights after backpropagation updates.The sign function is applied to both weights and activations.Source: §3 · p. 3
  • XNOR-Net++-style blocks use learned rescaling tensors for approximated dot products, with channel-wise and rank-1 constructions considered.Fully connected layers following graph feature extraction use these binarized blocks.Source: §3 · pp. 3–4
  • The method investigates nonlinear activations such as PReLU and applies logit matching and LSP as distillation methods for graph-network binarization.PReLU is identified as bringing the most improvement among the cited nonlinear activations in XNOR-Net-type blocks.Source: §3 · p. 3
  • Cascaded distillation trains three increasingly quantized students: first real-valued, then binary activations with real weights, and finally binary weights and activations.Logit matching and LSP are used at each stage; weight decay is omitted in stage three, whose learning rate and schedule strongly affect final performance.Source: §3 · p. 3, Figure 2 · p. 4

4. Models

The models study binarized DGCNN operators, including a direct approach with real-valued outputs and a dynamic-graph approach that searches in Hamming space. DGCNN is the main case study because its feature-space k-NN search is a potential target for binary-vector search.

4. Models

  • DGCNN is the main case study because EdgeConv uses both node features and edge messages, and feature-space k-NN search strongly affects its time complexity; the paper also derives a binary SAGE operator.Binary graph features make efficient Hamming-space k-NN search a potential route to faster dynamic-graph construction at inference.Source: §4 · p. 4

4.1. Direct binarization

  • The direct approach binarizes weights and input graph features while retaining real-valued outputs, replacing EdgeConv with BinEdgeConv and applying the same structure to the MLP classifier.BinEdgeConv uses learnable rescaling and batch normalization before quantization.Source: §4.1 · p. 4, Figure 3 · p. 4

4.2. Dynamic Graph in Hamming Space

  • Binary node features enable fast inference-time k-nearest-neighbor graph computation by replacing the ℓ2 norm with Hamming distance, motivating quantization-aware training with k-NN search on binary vectors.Because Hamming distance has an ill-defined gradient, the authors investigate two continuous relaxations, including using the standard ℓ2 norm for training.Source: §4.2 · pp. 4–5
  • For binary node features, XorEdgeConv adapts EdgeConv’s edge operation using Boolean algebra: addition becomes XOR, and a binary vector is its own additive inverse.For the paper’s {-1, 1}^n quantization, the passage relates XOR to the elementwise product.Source: §4.2 · p. 5

5. Experimental Evaluation

On ModelNet40, binary-node-feature DGCNNs with real weights and Hamming-space k-NN matched the floating-point model, while full-binary variants lost accuracy; several training and activation choices affected performance. The evaluation also reports GraphSAGE results on OGB benchmarks, embedded-device speed and memory savings, and implementation settings.

5. Experimental Evaluation

  • Balance functions lowered performance in every tested case; the authors suggest batch normalization before quantization is sufficient for aggregation and graph embeddings.Source: §5 · p. 5
  • Real-weight DGCNN with binary node features and Hamming-space k-NN matched the floating-point model, while full-binary models lost accuracy.Real-valued node features with ℓ2 k-NN performed comparably to the floating-point model as well.Source: Table 1 · p. 6, §5 · p. 6
  • Progressive three-stage distillation consistently outperformed direct distillation and training from scratch.The comparison is on ModelNet40 DGCNN variants.Source: Table 1 · p. 6, §5 · p. 7
  • PReLU significantly improved binary-node-feature models over ReLU or no added activation, at the cost of one fp32 parameter.The largest improvements occurred with median-centering or batch normalization before quantization.Source: §5 · p. 6
  • LSP with Gaussian RBF similarity had inconsistent effects, while Hamming-based Eq. 22 did not match Gaussian ℓ2 counterparts, possibly because of poor gradients.Source: §5 · p. 7, Table 2 · p. 7
  • On OGB-Products, full-binary GraphSAGE was within 5–6% of full precision; on OGB-Proteins, it was within 3% and outperformed full-precision GCN.Products used logit matching without PReLU; Proteins used PReLU without distillation because LSP was impractical at that edge scale.Source: Table 3 · p. 7, §5 · p. 7

5.1. Speed on embedded hardware

  • The optimized binary DGCNN halved runtime on Raspberry Pi 4B, while peak memory fell from 575MB to 346MB.The runtime comparison used the LCE benchmark tool over 50 runs; some costly operations were not accelerated by binarization.Source: §5.1 · pp. 7–8, Figure 4 · p. 8

5.2. Implementation details

  • DGCNN kept its final classifier layer real-weighted, while GraphSAGE used binary weights in all three layers; training schedules and regularization differed by model.Source: §5.2 · p. 8

6. Conclusion

The paper introduces a GNN binarization scheme combining XNOR-Net++ methodology with knowledge distillation, and reports competitive benchmark performance with reduced memory and inference time. It also applies binary features to dynamic graph construction in Hamming space.

6. Conclusion

  • Binary GNNs closely match or equal floating-point model performance on difficult benchmarks while reducing memory consumption and inference time.The DGCNN in Hamming space nearly equals the full floating-point model with floating-point weights and remains competitive with binary weights.Source: §6 · p. 8
  • The proposed scheme combines XNOR-Net++ methodology with knowledge distillation and evaluates design choices for binarized GNNs.Source: §6 · p. 8
  • Binary node features enable high-accuracy dynamic graph models and fast graph construction using Hamming-based algorithms.The conclusion relates these models to metric learning and compact hashing.Source: §6 · p. 8
  • The authors identify final-stage learning-rate scheduling as a possible route to higher performance and list accuracy, theory, and fast Hamming-space k-NN search as future work.Source: §6 · p. 8

A. DGCNN and ModelNet40

The appendix supplies omitted details about the DGCNN model and ModelNet40 classification setup. The experiment uses 3D point-cloud coordinates and an EdgeConv-based architecture.

A. DGCNN and ModelNet40

  • The appendix provides the DGCNN and ModelNet40 details omitted from the main text for brevity.Source: A. DGCNN and ModelNet40 · p. 9
  • ModelNet40 contains 12,311 shapes across 40 categories; the setup uses 9,843 for training and 2,468 for testing.It samples 1,024 points per shape from mesh faces and normalizes the point clouds to the unit sphere, discarding the original meshes.Source: A. DGCNN and ModelNet40 · p. 9
  • The classifier receives only the 3D coordinates of the sampled points, and overall accuracy is the reported model score.The setup uses random scaling and perturbations for augmentation.Source: A. DGCNN and ModelNet40 · p. 9
  • DGCNN variants use four graph-convolution layers with 64, 64, 128, and 256 channels, followed by 1,024-dimensional node embeddings and pooled graph features.The concatenated average- and max-pooled features feed a three-layer MLP with dimensions 512, 256, and 40; dropout is 0.5.Source: A. DGCNN and ModelNet40 · p. 9

B. Low-level implementation

The appendix section covers low-level implementation details and model memory cost.

B. Low-level implementation

B.1. Parameter counts

The parameter-count analysis reports that the binary models add a few parameters while making more than 99% of their parameters binary.

B.1. Parameter counts

  • Table 5 reports binary and floating-point parameter counts for the baseline DGCNN and the binary models at stage 3.Source: §B.1 · p. 9, Table 5 · p. 9
  • 99.39% of parameters are binary for BF1 and BF2, and 99.16% are binary for RF.Table 5 separates parameter counts into floating-point and binary operations.Source: Table 5 · p. 9
  • The binarization procedure introduces a few extra parameters, while over 99% of network parameters are binary.Source: §B.1 · p. 9

B.2. Profiling and optimization of DGCNN

Profiling DGCNN identifies Hamming-distance computation as a substantial runtime target, while TopK and other operations constrain attainable speedups. The merged sections also document why LSP results were omitted and how additional balance-function operations affected performance.

B.2. Profiling and optimization of DGCNN

  • The profiler tables cover DGCNN node types and a single Hamming-distance calculation, although the models perform three such calculations.Models were converted with LARQ and benchmarked using LCE; pairwise Hamming distance was naively implemented as matrix multiplication.Source: §B.2 · p. 9, Table 6 · p. 9, Table 7 · p. 10
  • 24% of network runtime comes from the profiled operations; a 32× speed-up would reduce their share to around 1%.The estimate is conservative because it does not account for LCE’s bit-packed conversion.Source: §B.2 · pp. 9, 11
  • Hamming distance can be implemented with ARM NEON popcount operations, but TopK accounts for 22% of runtime and is treated as incompressible in the simulation.The authors note that TopK might also use NEON, but that optimization is less straightforward; remaining operations such as concatenation cannot be optimized further.Source: §B.2 · pp. 9, 11

C. Details regarding GraphSAGE

  • LSP results are omitted because its gradient with respect to node features has size |E| × |V| × D, and available sparse-tensor gradient support was insufficient.The experiments otherwise follow the OGB architecture, procedure, evaluators, and dataset splits, and compare binary GraphSAGE with GraphSAGE and GCN floating-point baselines.Source: C. Details regarding GraphSAGE · p. 11

D. Balance functions

  • Additional balance-function operations degraded performance for both stage-3 full-binary models and stage-2 models with binary inputs but real weights.The paper reports these stage-2 results for completeness in Table 8.Source: D. Balance functions · p. 11

Related papers

Loading 2012.15823v2…