# QUINT: Node embedding using network hashing

arXiv: https://arxiv.org/abs/2109.04206 · HTML: https://mlsanity.com/paper/2109.04206/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 9 Sep 2021.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Attributed Social Network Embedding](https://mlsanity.com/paper/1705.04969/) (2017)
- [Fast and Accurate Network Embeddings via Very Sparse Random Projection](https://mlsanity.com/paper/1908.11512/) (2019)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [Hashing-Accelerated Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2105.14280/) (2021)
- [FREDE: Anytime Graph Embeddings](https://mlsanity.com/paper/2006.04746/) (2020)
- [InstantEmbedding: Efficient Local Node Representations](https://mlsanity.com/paper/2010.06992/) (2020)
- [Efficient Sketching Algorithm for Sparse Binary Data](https://mlsanity.com/paper/1910.04658/) (2019)
- [A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent](https://mlsanity.com/paper/2005.13789/) (2020)
- [SSNE: Effective Node Representation for Link Prediction in Sparse Networks](https://mlsanity.com/paper/2011.07788/) (2020)

## Abstract (arXiv)

Representation learning using network embedding has received tremendous attention due to its efficacy to solve downstream tasks. Popular embedding methods (such as deepwalk, node2vec, LINE) are based on a neural architecture, thus unable to scale on large networks both in terms of time and space usage. Recently, we proposed BinSketch, a sketching technique for compressing binary vectors to binary vectors. In this paper, we show how to extend BinSketch and use it for network hashing. Our proposal named QUINT is built upon BinSketch, and it embeds nodes of a sparse network onto a low-dimensional space using simple bi-wise operations. QUINT is the first of its kind that provides tremendous gain in terms of speed and space usage without compromising much on the accuracy of the downstream tasks. Extensive experiments are conducted to compare QUINT with seven state-of-the-art network embedding methods for two end tasks - link prediction and node classification. We observe huge performance gain for QUINT in terms of speedup (up to 7000x) and space saving (up to 80x) due to its bit-wise nature to obtain node embedding. Moreover, QUINT is a consistent top-performer for both the tasks among the baselines across all the datasets. Our empirical observations are backed by rigorous theoretical analysis to justify the effectiveness of QUINT. In particular, we prove that QUINT retains enough structural information which can be used further to approximate many topological properties of networks with high confidence.