Binary graph codes speed up node classification with little memory
Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching
Machine Learning
Summary
Graph neural networks usually use complex numbers to represent nodes, which can be slow and take up a lot of memory. The authors describe a new way to create simple binary codes (strings of 0s and 1s) for nodes that capture important graph structure without using node features or slow training processes. Their method uses random sampling techniques to quickly generate these codes. Tests on several datasets show it works faster and better than similar binary methods, and it fits well with certain types of brain-inspired computing.
What this means in practice
- •For machine learning engineers: Generate compact and fast binary node codes for large graph classification tasks without using node features or training.
- •For neuromorphic hardware developers: Implement node representations compatible with event-driven spiking neural networks and gradient-free learning.
Authors
Srajan Agarwal, Megha P, Bikas C Das, Zakaria Laskar, Saptarshi Bej
Abstract
Graph neural networks typically rely on dense, floating-point node representations, which can impose substantial memory and computational costs. Binary graph hashing offers an alternative by encoding node information as compact bit strings. However, existing approaches either sacrifice global topological information for computational efficiency or incur substantial generation costs. We introduce an ultra-fast, entirely algebraic hashing method that constructs binary node representations directly from graph structure, without requiring node features or gradient-based training. Our method approximates a high-order structural transition matrix using randomized column sampling inspired by the Nyström method and combines it with an efficient label-safe semantic propagation mechanism. The resulting continuous representations are discretized through column-wise thresholding to obtain compact binary codes. Experiments on ten node classification datasets show that the proposed method consistently improves classification accuracy over existing feature-free binary baselines while requiring sub-second code generation on many datasets. The resulting binary representations are also naturally suited to event-driven computation, making them compatible with neuromorphic spiking neural networks and gradient-free learning rules. These results demonstrate that simple algebraic approximations can provide an efficient alternative to learned pipelines for discrete graph representation learning.