Flashlight: Scalable Link Prediction with Effective Decoders
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph LearningLink PredictionPredictionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
DNCASR: End-to-End Training for Speaker-Attributed ASR
This paper introduces DNCASR, a novel end-to-end trainable system designed for joint neural speaker clustering and automatic speech recognition (ASR), enabling speaker-attributed transcription of long multi-party meeting…
Automatic Speech RecognitionAutomatic Speech Recognition (ASR)speech-recognitionSpeech RecognitionVR-SFT: Reproducing Swinging Flashlight Test in Virtual Reality to Detect Relative Afferent Pupillary Defect
The relative afferent asymmetry between two eyes can be diagnosed using swinging flashlight test, also known as the alternating light test. This remains one of the most used clinical tests to this day. Despite the swingi…
Flashlight: Enabling Innovation in Tools for Machine Learning
As the computational requirements for machine learning systems and the size and complexity of machine learning frameworks increases, essential framework innovation has become challenging. While computational needs have d…
BIG-bench Machine LearningFlashlight CNN Image Denoising
This paper proposes a learning-based denoising method called FlashLight CNN (FLCNN) that implements a deep neural network for image denoising. The proposed approach is based on deep residual networks and inception networ…
DenoisingImage DenoisingOn the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks
Heterophily, or the tendency of connected nodes in networks to have different class labels or dissimilar features, has been identified as challenging for many Graph Neural Network (GNN) models. While the challenges of ap…
Graph LearningGraph Neural NetworkLink PredictionNode Classification+1