Link prediction

Link prediction estimates how likely it is that an edge, a connection, exists or will form between two nodes in a graph that are not currently linked. Typical uses include suggesting a new social connection, flagging a probable but undisclosed relationship between two accounts, or predicting which two products are likely to be purchased together.

Simple approaches score node pairs using graph analytics structural signals, such as the number of neighbors two nodes share or their similarity by centrality measures; more advanced approaches learn node embeddings, vector representations of each node's position in the graph, and predict a link from the similarity of those vectors. This differs from community detection, which groups existing structure into clusters; link prediction instead forecasts structure that is missing or yet to appear.

Link prediction matters for friend and product recommendation systems, for completing sparse knowledge graphs, and for investigative work such as surfacing likely but hidden relationships between entities. A common pitfall is evaluating a link prediction model on a random sample of non-edges, which is far easier than the real task, since most true missing links occur between nodes that are already structurally close; a fair evaluation should account for that base rate.