# Flashlight: Scalable Link Prediction with Effective Decoders

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 69 references that are in the map.
- First posted on arXiv 17 Sep 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [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)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Neural Collaborative Filtering vs. Matrix Factorization Revisited](https://mlsanity.com/paper/2005.09683/) (2020)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Pairwise Learning for Neural Link Prediction](https://mlsanity.com/paper/2112.02936/) (2021)
- [Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation](https://mlsanity.com/paper/2202.10226/) (2022)
- [A Greedy Approach for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1610.03317/) (2016)
- [Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search](https://mlsanity.com/paper/1911.04654/) (2019)
- [HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces](https://mlsanity.com/paper/1804.06829/) (2018)
- [Norm-Ranging LSH for Maximum Inner Product Search](https://mlsanity.com/paper/1809.08782/) (2018)
- [A Bandit Approach to Maximum Inner Product Search](https://mlsanity.com/paper/1812.06360/) (2018)
- [Understanding and Improving Proximity Graph based Maximum Inner Product Search](https://mlsanity.com/paper/1909.13459/) (2019)

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

- [Link Prediction with Non-Contrastive Learning](https://mlsanity.com/paper/2211.14394/) (2022)
- [On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks](https://mlsanity.com/paper/2409.17475/) (2024)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [Retrieval with Learned Similarities](https://mlsanity.com/paper/2407.15462/) (2024)
- [DURENDAL: Graph deep learning framework for temporal heterogeneous networks](https://mlsanity.com/paper/2310.00336/) (2023)
- [PROXI: Challenging the GNNs for Link Prediction](https://mlsanity.com/paper/2410.01802/) (2024)
- [Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors](https://mlsanity.com/paper/2402.00053/) (2024)

## Abstract (arXiv)

Link prediction (LP) has been recognized as an important task in graph learning with its broad practical applications. A typical application of LP is to retrieve the top scoring neighbors for a given source node, such as the friend recommendation. These services desire the high inference scalability to find the top scoring neighbors from many candidate nodes at low latencies. There are two popular decoders that the recent LP models mainly use to compute the edge scores from node embeddings: the HadamardMLP and Dot Product decoders. After theoretical and empirical analysis, we find that the HadamardMLP decoders are generally more effective for LP. However, HadamardMLP lacks the scalability for retrieving top scoring neighbors on large graphs, since to the best of our knowledge, there does not exist an algorithm to retrieve the top scoring neighbors for HadamardMLP decoders in sublinear complexity. To make HadamardMLP scalable, we propose the Flashlight algorithm to accelerate the top scoring neighbor retrievals for HadamardMLP: a sublinear algorithm that progressively applies approximate maximum inner product search (MIPS) techniques with adaptively adjusted query embeddings. Empirical results show that Flashlight improves the inference speed of LP by more than 100 times on the large OGBL-CITATION2 dataset without sacrificing effectiveness. Our work paves the way for large-scale LP applications with the effective HadamardMLP decoders by greatly accelerating their inference.