mlsanityData to 7 Oct 2026

Flashlight: Scalable Link Prediction with Effective Decoders

arXiv 2209.10100 ↗First posted 17 Sep 2022cs.SI cs.AI cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

29 of 69 references.

References · 29

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  5. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  6. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  7. 2016Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translationcited by 1,471
  8. 2016Variational Graph Auto-Encoderscited by 1,373
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  10. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  11. 2018Link Prediction Based on Graph Neural Networkscited by 829
  12. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
17 more
  1. 2015LINE: Large-scale Information Network Embeddingcited by 582
  2. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  3. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  4. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  5. 2020Neural Collaborative Filtering vs. Matrix Factorization Revisitedcited by 123
  6. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  7. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
  8. 2022Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learningcited by 28
  9. 2014On Symmetric and Asymmetric LSHs for Inner Product Searchcited by 23
  10. 2021Pairwise Learning for Neural Link Predictioncited by 23
  11. 2022Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendationcited by 14
  12. 2016A Greedy Approach for Budgeted Maximum Inner Product Searchcited by 11
  13. 2019Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Searchcited by 10
  14. 2018HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spacescited by 8
  15. 2018Norm-Ranging LSH for Maximum Inner Product Searchcited by 8
  16. 2018A Bandit Approach to Maximum Inner Product Searchcited by 5
  17. 2019Understanding and Improving Proximity Graph based Maximum Inner Product Searchcited by 5

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 4.

7 papers.

  1. 2022Link Prediction with Non-Contrastive Learningcited by 11
  2. 2024On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networkscited by 10
  3. 2023Efficient Link Prediction via GNN Layers Induced by Negative Samplingcited by 6
  4. 2024Retrieval with Learned Similaritiescited by 3
  5. 2023DURENDAL: Graph deep learning framework for temporal heterogeneous networkscited by 1
  6. 2024PROXI: Challenging the GNNs for Link Predictioncited by 1
  7. 2024Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictorscited by 0