Link Prediction

Link prediction asks: given a graph with some edges observed, which additional edges are likely to exist? This covers a wide range of practical problems: recommending new friends in a social network (which users are likely to become connected?), completing a knowledge graph (which entity pairs are likely to have an unstated relationship?), predicting protein interactions (which proteins are likely to bind?), and identifying potential drug-disease associations (which compounds might treat which conditions?).

Heuristic methods for link prediction operate on graph topology without learning. Common Neighbours (two nodes that share many mutual connections are likely to connect), Jaccard Coefficient (normalises common neighbours by total neighbours), Adamic-Adar index (weights common neighbours by the inverse log of their degree), and Preferential Attachment (nodes with many connections are more likely to gain new ones) are all simple structural predictors that perform surprisingly well on social networks.

Embedding-based methods learn vector representations for nodes and score candidate links by the geometric relationship between node pairs in embedding space. The simplest scoring function: dot product between node embeddings - nodes with similar embeddings are predicted to connect. More sophisticated scoring functions (Hadamard product, concatenation + MLP, learned bilinear forms) capture asymmetric or typed relationships better.

For knowledge graph link prediction (knowledge graph completion), relation-specific scoring functions encode different relation types differently. TransE scores (head + relation, tail) similarity by L2 distance. RotatE represents each relation as a rotation in complex space. ComplEx operates in the complex number domain to handle asymmetric relations ("A employs B" does not imply "B employs A"). These methods train on observed triples and score unobserved triples at inference time.

GNN-based link prediction runs message passing on the observed graph to produce node embeddings, then scores candidate edges by their node embedding pairs. Subgraph-based methods (SEAL) extract a local subgraph around each candidate edge and use GNNs or heuristics on this subgraph for prediction - capturing richer local structural patterns than node embeddings alone.

Evaluation of link prediction methods uses a held-out set of observed edges (treated as positive examples) paired with randomly sampled non-edges (negative examples). Metrics include AUC, average precision, and the Hits@K (what fraction of true edges rank in the top K among all candidates).

Link prediction is not merely a benchmarking task - it has direct industrial value. LinkedIn's "People You May Know", Facebook's friend suggestions, and Netflix's content-to-user recommendations are all forms of link prediction at massive scale.