Link prediction
Link prediction is the inference of unobserved or future relationships in a network from information available about its observed structure, its entities, or its temporal development. A network is represented as a graph (G=(V,E)), where (V) contains the vertices and (E) contains the observed edges. The task assigns a score or probability to a pair of vertices that is not connected in the observed graph.
The interpretation of a predicted link depends on the system being modeled. In a social network, it can represent a future association between people. In a citation network, it can represent a citation that has not yet been observed. In a biological network, it can represent an interaction omitted by incomplete measurement. Link prediction also applies to transportation, communication, commercial, and knowledge networks, provided that the meaning and temporal status of an edge are defined consistently.
Formalization
For a simple undirected graph, the candidate set is usually drawn from
[ U={{u,v}:u,v\in V,\ u\neq v,\ {u,v}\notin E}. ]
A link predictor is a function
[ s:U\rightarrow\mathbb{R}, ]
where a larger value of (s(u,v)) indicates a stronger expectation that the edge ({u,v}) is missing or will appear during a specified observation interval. Probabilistic models instead estimate
[ P\bigl((u,v)\in E_{t+\Delta}\mid G_{\leq t},X_{\leq t}\bigr), ]
where (G_{\leq t}) is the network history available at time (t), and (X_{\leq t}) contains admissible attributes or external observations.
This formulation separates link prediction from graph completion, although the two tasks overlap. Graph completion generally concerns edges that already exist in the underlying system but are absent from the recorded graph. Temporal link prediction concerns edges that form after the prediction time. A dataset can contain both conditions, making the distinction dependent on the observation process rather than on topology alone.
The task can also be defined for directed graphs, weighted networks, signed networks, and multigraphs. In these settings, the ordered endpoints, edge magnitude, edge polarity, or relation type become part of the prediction target. Prediction over a knowledge graph commonly estimates a missing triple ((h,r,t)), in which the relation (r) cannot be reduced to an unlabeled edge without losing semantic information.
Structural foundations
Many link-prediction methods follow the principle of triadic closure, under which two vertices become more likely to connect when they share neighbors. For vertices (u) and (v), let (\Gamma(u)) denote the neighborhood of (u). The common-neighbors score is
[ s_{\mathrm{CN}}(u,v)=|\Gamma(u)\cap\Gamma(v)|. ]
This score treats every shared neighbor as an equal contribution. The Jaccard index normalizes the overlap by the combined neighborhood:
[ s_{\mathrm{J}}(u,v)= \frac{|\Gamma(u)\cap\Gamma(v)|} {|\Gamma(u)\cup\Gamma(v)|}. ]
The normalization reduces the tendency of high-degree vertices to receive large scores solely because they have many neighbors. It also makes the score undefined when both neighborhoods are empty, a case ordinarily assigned a conventional value within an implementation.
Lada Adamic and Eytan Adar introduced a degree-weighted measure in their study of similarity among personal web pages. The resulting Adamic–Adar index is
[ s_{\mathrm{AA}}(u,v)= \sum_{z\in\Gamma(u)\cap\Gamma(v)} \frac{1}{\log |\Gamma(z)|}. ]
A shared neighbor contributes less when it is connected to many other vertices. The related resource-allocation index replaces the logarithmic denominator with the degree itself, corresponding to the fraction of a unit resource that a common neighbor distributes uniformly across its adjacent edges.
Preferential-attachment scoring uses the product of endpoint degrees:
[ s_{\mathrm{PA}}(u,v)=|\Gamma(u)|,|\Gamma(v)|. ]
Its interpretation follows the degree-dependent attachment mechanism studied in evolving networks. Unlike neighborhood-overlap measures, it can assign a substantial score to vertices with no shared neighbors. It therefore reflects network growth driven by endpoint prominence rather than local closure.
Paths and global structure
Local scores examine a restricted neighborhood and consequently ignore much of the graph. Path-based methods incorporate longer routes between candidate endpoints. The Katz score, derived from the Katz centrality construction, sums over paths of all lengths while geometrically reducing the contribution of longer paths:
[ s_{\mathrm{Katz}}(u,v)= \sum_{\ell=1}^{\infty}\beta^\ell \left(A^\ell\right)_{uv}, ]
where (A) is the adjacency matrix and (\beta) is smaller than the reciprocal of the spectral radius of (A). The matrix entry ((A^\ell)_{uv}) counts walks of length (\ell) between the vertices.
Other global approaches derive scores from random walks, matrix factorization, or latent geometric representations. A random-walk score measures how probability mass moves through existing edges, while a latent-space model assigns each vertex a position whose distance influences edge probability. Matrix-factorization methods approximate the adjacency matrix by a lower-rank product,
[ A\approx ZZ^{\mathsf T}, ]
so that the inner product of two rows of (Z) serves as a link score. For directed or typed networks, separate source and target representations replace the symmetric factorization.
Global structure can improve discrimination between candidate pairs that have identical local neighborhoods. It also couples the prediction for one pair to distant portions of the graph, which increases computational requirements and makes the result more sensitive to broad structural changes.
Statistical models
A statistical link model specifies how observed variables determine the distribution of edges. In a dyadic logistic regression, the probability of an edge may be written as
[ P(A_{uv}=1\mid x_{uv})
\frac{1} {1+\exp[-(\alpha+\theta^{\mathsf T}x_{uv})]}, ]
where (x_{uv}) contains measurements associated with the vertex pair. Structural scores can appear as components of (x_{uv}), although dependence among dyads means that ordinary independent-observation interpretations do not generally hold.
Stochastic block models represent each vertex through a latent or observed group assignment. Edge probability then depends on the groups of the two endpoints. Mixed-membership variants allow a vertex to participate in several structural roles, producing different interaction probabilities across contexts.
Exponential random graph models assign probabilities to complete graphs using sufficient statistics such as edge counts and configurations associated with closure. These models represent dependence among edges directly, but their normalization and estimation can be computationally demanding. Temporal variants replace a distribution over static graphs with a transition model over graph states.
Representation learning
Modern link-prediction systems frequently construct numerical representations through graph embedding. Early embedding methods used truncated random walks to generate vertex sequences and then applied distributional learning objectives. Vertices with comparable structural contexts acquired nearby representations even when they were not adjacent.
Graph neural networks generalize this approach by repeatedly aggregating information from neighboring vertices. After several message-passing layers, a decoder converts two vertex representations into a link score. A dot-product decoder uses
[ s(u,v)=z_u^{\mathsf T}z_v, ]
while a learned decoder applies a parameterized function to (z_u), (z_v), and any available edge attributes.
Standard message-passing models can produce similar representations for vertices whose local structures are indistinguishable under the model’s aggregation rule. Positional encodings, subgraph extraction, and pair-specific features address parts of this limitation by preserving information about the relationship between the candidate endpoints.
Knowledge-graph models extend representation learning to labeled relations. Translational models represent a relation as a displacement between entity vectors, whereas bilinear models use a relation-specific transformation. Their objective is not merely to determine whether two entities are connected, but to identify which relation completes a candidate triple.
Temporal development
The modern empirical formulation of link prediction emerged from work on time-stamped social networks. David Liben-Nowell and Jon Kleinberg established an influential evaluation framework in which an earlier network snapshot was used to rank pairs whose interactions could appear during a later interval. This separation between observation and outcome periods made link prediction a forecasting problem rather than a reconstruction of randomly hidden edges.
Temporal models account for the order and recurrence of interactions. A recent common neighbor can carry different information from a common neighbor observed far in the past. Event-based models represent links as occurrences in continuous time and assign each candidate dyad an intensity,
[ \lambda_{uv}(t\mid\mathcal H_t), ]
conditioned on the event history (\mathcal H_t). Repeated interactions, delayed responses, and network-wide activity changes can then alter the estimated probability of an event during a future interval.
In 2016, You Watanabe and Kenta Akiyama analyzed link prediction in a time-stamped coastal mobility network whose edges represented recorded direct journeys between landing points. Their study separated recurring seasonal routes from newly formed connections and showed that evaluations based on random edge removal overstated performance when future journeys were allowed to influence training features. The work formed part of the broader transition from static edge reconstruction to chronologically constrained evaluation in transportation networks.
Temporal ordering is essential because an undated graph can contain information created after the event being predicted. When such information enters training data, the predictor becomes a classifier of already completed history. This condition is known as data leakage and can affect structural features, vertex attributes, negative examples, and preprocessing operations.
Evaluation
Evaluation begins with a division between information available to the model and links treated as outcomes. In a temporal design, all training information precedes the test interval. In a missing-edge design, observed edges are withheld according to a sampling mechanism intended to represent measurement loss. These designs answer different questions and do not produce interchangeable performance estimates.
Most real networks contain far more nonedges than edges. Class imbalance therefore has a substantial effect on evaluation. The area under the receiver operating characteristic curve measures the probability that a randomly selected positive edge receives a higher score than a randomly selected negative pair. Because this statistic averages over the large negative class, it can remain high even when the highest-ranked candidates contain few true links.
Precision and recall focus more directly on predicted positives. Precision at (k) measures the proportion of true links among the (k) highest-ranked candidates, while recall measures the fraction of test links recovered within a selected set. Average precision and the area under a precision–recall curve summarize behavior across ranking thresholds.
Probabilistic predictions require evaluation beyond ranking. The Brier score measures squared error between predicted probabilities and observed outcomes, while calibration compares predicted probability levels with empirical event frequencies. A ranking can be accurate without being calibrated because any strictly increasing transformation preserves the ordering but changes the numerical probabilities.
Negative examples require a defined interpretation. A vertex pair without an observed edge can represent a genuine nonrelationship, an unrecorded relationship, or a relationship that has not yet formed. Sampling these cases as equivalent negatives changes the target distribution and can make performance dependent on the sampling rule rather than solely on the predictor.
Sampling and observation
The recorded graph is usually a partial representation of an underlying system. Missing vertices can remove all incident edges, while missing interactions alter degrees and neighborhood overlap. Boundary rules can also create apparent nonedges when one endpoint lies outside the observation domain.
Network construction therefore affects the meaning of prediction. Aggregating repeated events into a single edge discards frequency and order. Combining several relation types can turn semantically distinct interactions into equivalent links. Dividing continuous activity into discrete snapshots can cause events near a boundary to appear farther apart than events separated by the same duration within one interval.
The observation mechanism may itself depend on network structure. Interactions involving prominent vertices are often more likely to be recorded, and some measurement systems detect recurring edges more reliably than isolated ones. Under these conditions, a model can learn the probability of observation rather than the probability of the underlying relationship.
Limits of interpretation
Link prediction estimates relationships under a specified representation and data-generating process. A high score does not establish a causal mechanism for edge formation. Structural proximity can arise from shared circumstances, measurement practices, or earlier interactions that are not represented in the graph.
Performance also varies across regions of the same network. Vertices with extensive histories provide more structural evidence than newly observed vertices, producing a cold-start problem. Dense communities offer many short paths, whereas sparse regions can contain few signals for neighborhood-based methods. Aggregate metrics can conceal these differences by averaging over candidate pairs with dissimilar informational conditions.
A predicted link can influence the network when predictions determine recommendations or visibility. In that setting, the model is part of the mechanism that creates later edges. The resulting feedback changes both the network and the distribution of future training data, so subsequent observations no longer represent development independent of earlier predictions.