node2binary: Compact Graph Node Embeddings Using Binary Vectors

Niloy Talukder, Croix Gyurek, Mohammad HasanWWW 2025 · OpenReview

TL;DR

Node2binary is a novel framework that compresses graph node embeddings into compact binary vectors, reducing memory usage by up to 64x compared to traditional floating-point methods. By treating embedding as a combinatorial optimization problem over a hierarchical community tree, it achieves state-of-the-art performance on classification and link prediction tasks while remaining lightweight enough for low-power edge devices.

What Problem Does This Paper Address?

Graph Representation Learning (GRL) has become essential for everything from social network analysis to protein interaction mapping. However, as graphs grow to millions or billions of nodes, the "memory tax" becomes a massive hurdle.

Standard embeddings represent each node as a vector of double-precision floating-point numbers. For a graph with 10 million nodes and 100-dimensional vectors, you’re looking at over 60 GB of storage just for the embeddings. This is a non-starter for edge devices like smartphones, IoT sensors, or battery-powered hardware where RAM is scarce and data transfer drains power. While some researchers have tried to "quantize" models after training, Node2binary asks: Can we learn high-quality embeddings directly in binary space?

Methods

The authors move away from traditional matrix factorization and neural networks, instead proposing a community-centric optimization approach.

  1. Constructing the Community Partition Tree ($T_G$): Using the Leiden algorithm, the graph is recursively partitioned into hierarchical communities. The root represents the entire graph, and the leaves are individual nodes.
  2. Logical Implication (Inheritance): The core mathematical "trick" is treating bit indices as indicators of behavior. If a parent community possesses a certain trait (a '1' bit), all its sub-communities and leaf nodes must inherit that '1' bit. This creates a logical constraint: $parent \implies child$.
  3. Sibling Similarity: To ensure the embeddings are meaningful, the model encourages "sibling" nodes (nodes in the same community) to have a low Hamming distance (i.e., they should share many of the same bits).
  4. Discrete Gradient Descent: Since binary space is discrete, you can't use standard backpropagation. The authors developed a Discrete Gradient Descent method using Boolean logic. They calculate a "Flip Probability" for each bit, allowing the model to navigate the NP-hard combinatorial space effectively without getting stuck in local maxima.

Datasets

The model was evaluated on four diverse real-world datasets:

  • PPI: A protein-protein interaction network (3,890 nodes).
  • DBLP: A co-authorship network (13,326 nodes).
  • BlogCatalog: A social network of bloggers (10,312 nodes).
  • YouTube: A massive social network. The authors used a subset for classification tasks and the full dataset (1.1 million nodes, 3 million edges) to test scalability.

Key Insights and Ideas

  • Hierarchy is Identity: The paper posits that a node's identity is defined by the communities it belongs to. By forcing nodes to inherit bits from their ancestors in the community tree, the embedding naturally captures the multi-scale structure of the graph.
  • Direct Binary Learning: Unlike methods that train in floating-point and then truncate (which often destroys accuracy), Node2binary optimizes for the binary constraints from day one.
  • The Power of 128 Bits: One of the most surprising findings is how much information can be packed into just 128 bits. In many cases, Node2binary at 128 bits outperformed competitors using thousands of bits.
  • Linear Scalability: The algorithm runs in linear time relative to the number of edges and nodes, making it viable for "web-scale" graphs.

Key Results

  • Efficiency: Node2binary embeddings are 32x to 64x more space-efficient than double-precision competitors at the same dimension.
  • Node Classification: On the YouTube dataset, Node2binary achieved a ~9.27% F1-score using only 256 bits. Most competitors required 8,192 bits to reach similar performance.
  • Link Prediction: The model consistently ranked as the best or second-best performer, particularly on the YouTube and BlogCatalog datasets, showing that binary vectors are excellent at capturing the likelihood of connections between nodes.
  • Convergence: Despite the discrete nature of the problem, the authors demonstrated that their loss functions (Hierarchy loss and Sibling loss) converge smoothly over time.

Limitations and Future Work

  • Transductive Nature: Currently, Node2binary is transductive, meaning it cannot generate embeddings for "unseen" nodes added to the graph after training. A full re-run is required if the graph changes significantly.
  • Implementation Language: The current implementation is in Python. The authors note that moving to C++ or MATLAB would likely yield significant speedups, as their main competitors are currently faster due to language-level optimizations.
  • Inductive Extension: The authors suggest that a future direction involves extending the logic to inductive learning, allowing the model to handle dynamic graphs where new nodes arrive constantly.

Summary updated

Abstract

With the adoption of deep learning models to low-power, small-memory edge devices, energy consumption and storage usage of such models has become a key concern. The problem acerbates even further with ever-growing data and equally-matched bulkier models. This concern is particularly pronounced for graph data due to its quadratic storage, irregular (non-grid) geometry, and very large size. Typical graph data, such as road networks, infrastructure networks, social networks easily exceeds millions of nodes, and several gigabytes of storage is needed just to store the node embedding vectors, let alone the model parameters. In recent years, the memory issue has been addressed by moving away from memory-intensive double precision floating-point arithmetic towards single-precision or even half-precision, often by trading-off marginally small performance. Along this effort, we propose Node2binary, which embeds graph nodes in as low as 128 binary bits, which drastically reduces the memory footprint of vertex embedding vectors by several order of magnitude. Node2binary leverages a fast community detection algorithm to covert the given graph into a hierarchical partition tree and then find embedding of graph vertices in binary space by solving a combinatorial optimization (CO) task over the tree edges. CO is NP-hard, but Node2binary uses an innovative combination of discrete gradient descent and randomization to solve this effectively and efficiently. Our extensive experiments over four real-world graphs show that Node2binary achieves competitive performances compared to the state-of-the art graph embedding methods in both node classification and link prediction tasks.
BibTeX
@inproceedings{talukder2025node,
  author = {Niloy Talukder and Croix Gyurek and Mohammad Hasan},
  title = {{node2binary: Compact Graph Node Embeddings Using Binary Vectors}},
  booktitle = {The Web Conference},
  year = {2025},
  url = {https://openreview.net/forum?id=s3KIzcRdll},
}
Figure