# Hashing-Accelerated Graph Neural Networks for Link Prediction

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 59 references that are in the map.
- First posted on arXiv 29 May 2021.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (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)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Dynamic Graph Message Passing Networks](https://mlsanity.com/paper/1908.06955/) (2019)
- [SceneGraphNet: Neural Message Passing for 3D Indoor Scene Augmentation](https://mlsanity.com/paper/1907.11308/) (2019)
- [Learning to Hash with Graph Neural Networks for Recommender Systems](https://mlsanity.com/paper/2003.01917/) (2020)
- [Deriving Neural Architectures from Sequence and Graph Kernels](https://mlsanity.com/paper/1705.09037/) (2017)
- [A Review for Weighted MinHash Algorithms](https://mlsanity.com/paper/1811.04633/) (2018)
- [Improved Consistent Weighted Sampling Revisited](https://mlsanity.com/paper/1706.01172/) (2017)
- [Flexible Attributed Network Embedding](https://mlsanity.com/paper/1811.10789/) (2018)

## Built on by (most cited first, 14 of 14)

- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Simplifying Subgraph Representation Learning for Scalable Link Prediction](https://mlsanity.com/paper/2301.12562/) (2023)
- [NeutronOrch: Rethinking Sample-based GNN Training under CPU-GPU Heterogeneous Environments](https://mlsanity.com/paper/2311.13225/) (2023)
- [A Lower Bound of Hash Codes' Performance](https://mlsanity.com/paper/2210.05899/) (2022)
- [RCoCo: Contrastive Collective Link Prediction across Multiplex Network in Riemannian Space](https://mlsanity.com/paper/2403.01864/) (2024)
- [Graph Representation Learning for Interactive Biomolecule Systems](https://mlsanity.com/paper/2304.02656/) (2023)
- [From random-walks to graph-sprints: a low-latency node embedding framework on continuous-time dynamic graphs](https://mlsanity.com/paper/2307.08433/) (2023)
- [PROXI: Challenging the GNNs for Link Prediction](https://mlsanity.com/paper/2410.01802/) (2024)
- [Accelerating Sparse Graph Neural Networks with Tensor Core Optimization](https://mlsanity.com/paper/2412.12218/) (2024)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [Learning Similarity Preserving Binary Codes for Recommender Systems](https://mlsanity.com/paper/2204.08569/) (2022)
- [Deep-Graph-Sprints: Accelerated Representation Learning in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2407.07712/) (2024)

## Abstract (arXiv)

Networks are ubiquitous in the real world. Link prediction, as one of the key problems for network-structured data, aims to predict whether there exists a link between two nodes. The traditional approaches are based on the explicit similarity computation between the compact node representation by embedding each node into a low-dimensional space. In order to efficiently handle the intensive similarity computation in link prediction, the hashing technique has been successfully used to produce the node representation in the Hamming space. However, the hashing-based link prediction algorithms face accuracy loss from the randomized hashing techniques or inefficiency from the learning to hash techniques in the embedding process. Currently, the Graph Neural Network (GNN) framework has been widely applied to the graph-related tasks in an end-to-end manner, but it commonly requires substantial computational resources and memory costs due to massive parameter learning, which makes the GNN-based algorithms impractical without the help of a powerful workhorse. In this paper, we propose a simple and effective model called #GNN, which balances the trade-off between accuracy and efficiency. #GNN is able to efficiently acquire node representation in the Hamming space for link prediction by exploiting the randomized hashing technique to implement message passing and capture high-order proximity in the GNN framework. Furthermore, we characterize the discriminative power of #GNN in probability. The extensive experimental results demonstrate that the proposed #GNN algorithm achieves accuracy comparable to the learning-based algorithms and outperforms the randomized algorithm, while running significantly faster than the learning-based algorithms. Also, the proposed algorithm shows excellent scalability on a large-scale network with the limited resources.