  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.
