Hubbry Logo
Link predictionLink predictionMain
Open search
Link prediction
Community hub
Link prediction
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Link prediction
Link prediction
Link prediction
View on Wikipedia
from Wikipedia

In network theory, link prediction is the problem of predicting the existence of a link between two entities in a network. Examples of link prediction include predicting friendship links among users in a social network, predicting co-authorship links in a citation network, and predicting interactions between genes and proteins in a biological network. Link prediction can also have a temporal aspect, where, given a snapshot of the set of links at time , the goal is to predict the links at time . Link prediction is widely applicable. In e-commerce, link prediction is often a subtask for recommending items to users. In the curation of citation databases, it can be used for record deduplication. In bioinformatics, it has been used to predict protein-protein interactions (PPI). It is also used to identify hidden groups of terrorists and criminals in security related applications.[1]

Problem definition

[edit]

Consider a network , where represents the entity nodes in the network and x represents the set of "true" links across entities in the network. We are given the set of entities and a subset of true links which are referred to as observed links. The goal of link prediction is to identify the unobserved true links. In the temporal formulation of link prediction the observed links correspond to true links at a time , and the goal is to infer the set of true links at time Usually, we are also given a subset of unobserved links called potential links , and we need to identify true links among these potential links.

In the binary classification formulation of the link prediction task the potential links are classified as either true links or false links. Link prediction approaches for this setting learn a classifier that maps links in to positive and negative labels i.e. . In the probability estimation formulation, potential links are associated with existence probabilities. Link prediction approaches for this setting learn a model that maps links in to a probability i.e. .

Single link approaches learn a model that classifies each link independently. Structured prediction approaches capture the correlation between potential links by formulating the task as a collective link prediction task. Collective link prediction approaches learn a model that jointly identify all the true links among the set of potential links.

Link prediction task can also be formulated as an instance of missing value estimation task. Here, the graph is represented as an adjacency matrix with missing values. The task is to complete the matrix by identifying the missing values. Matrix factorization based methods commonly use this formulation.

History

[edit]

The task of link prediction has attracted attention from several research communities ranging from statistics and network science to machine learning and data mining. In statistics, generative random graph models such as stochastic block models propose an approach to generate links between nodes in a random graph. For social networks, Liben-Nowell and Kleinberg proposed a link prediction models based on different graph proximity measures.[2] Several statistical models have been proposed for link prediction by the machine learning and data mining community. For example, Popescul et al. proposed a structured logistic regression model that can make use of relational features.[3] Local conditional probability models based on attribute and structural features were proposed by O’Madadhain et al.[4] Several models based on directed graphical models for collective link prediction have been proposed by Getoor.[5] Other approached based on random walks.[6] and matrix factorization have also been proposed [7] With the advent of deep learning, several graph embedding based approaches for link prediction have also been proposed.[8] For more information on link prediction refer to the survey by Getoor et al.[9] and Yu et al.[10]

Approaches and methods

[edit]

Several link predication approaches have been proposed including unsupervised approaches such as similarity measures computed on the entity attributes, random walk and matrix factorization based approaches, and supervised approaches based on graphical models and deep learning. Link prediction approaches can be divided into two broad categories based on the type of the underlying network: (1) link prediction approaches for homogeneous networks (2) link prediction approaches for heterogeneous networks. Based on the type of information used to predict links, approaches can be categorized as topology-based approaches, content-based approaches, and mixed methods.[11]

Topology-based methods

[edit]

Topology-based methods broadly make the assumption that nodes with similar network structure are more likely to form a link.

Common neighbors

[edit]

This is a common approach to link prediction that computes the number of common neighbors. Entities with more neighbors in common are more likely to have a link. It is computed as follows:

A weakness of this approach is that it does not take into account the relative number of common neighbors.

Jaccard measure

[edit]

The Jaccard Measure addresses the problem of Common Neighbors by computing the relative number of neighbors in common:

Adamic–Adar measure

[edit]

The Adamic–Adar measure[12] is the sum of the log of the intersection of the neighbors of two nodes. This captures a two-hop similarity, which can yield better results than simple one-hop methods. It is computed as follows:

where is the set of nodes adjacent to .

Katz measure

[edit]

Neighbor based methods can be effective when the number of neighbors is large, but this is not the case in sparse graphs. In these situations it is appropriate to use methods that account for longer walks. The Katz Measure[13] is one metric that captures this. It is computed by searching the graph for paths of length in the graph and adding the counts of each path length weighted by user specified weights.

Let A be the adjacency matrix of a network under consideration. Elements of A are variables that take a value 1 if a node i is connected to node j and 0 otherwise. The powers of A indicate the presence (or absence) of links between two nodes through intermediaries. For instance, in matrix , if element , it indicates that node 2 and node 12 are connected through some walk of length 3. If denotes Katz centrality of a node i, then mathematically:

Note that the above definition uses the fact that the element at location of reflects the total number of degree connections between nodes and .

Node attribute-based methods

[edit]

Node-similarity methods predict the existence of a link based on the similarity of the node attributes.

Euclidean distance

[edit]

The attribute values are represented as normalized vector and the distance between the vectors used to measure similarity. Small distances indicate higher similarity.

Cosine similarity

[edit]

After normalizing the attribute values, computing the cosine between the two vectors is a good measure of similarity, with higher values indicating higher similarity.

Mixed methods

[edit]

Mixed methods combine attribute and topology based methods.

Graph embeddings

[edit]

Graph embeddings also offer a convenient way to predict links.[8] Graph embedding algorithms, such as Node2vec, learn an embedding space in which neighboring nodes are represented by vectors so that vector similarity measures, such as dot product similarity, or euclidean distance, hold in the embedding space. These similarities are functions of both topological features and attribute-based similarity. One can then use other machine learning techniques to predict edges on the basis of vector similarity.

Probabilistic relationship models

[edit]

A probabilistic relational model (PRM) specifies a template for a probability distribution over databases. The template describes the relational schema for the domain, and the probabilistic dependencies between attributes in the domain. A PRM, together with a particular database of entities and unobserved links, defines a probability distribution over the unobserved links.[5]

Probabilistic soft logic (PSL)

[edit]

Probabilistic soft logic (PSL) is a probabilistic graphical model over hinge-loss Markov random field (HL-MRF). HL-MRFs are created by a set of templated first-order logic-like rules, which are then grounded over the data. PSL can combine attribute, or local, information with topological, or relational, information. While PSL can incorporate local predictors, such as cosine similarity, it also supports relational rules, such as triangle completion in a network.[14]

Markov logic networks (MLNs)

[edit]

Markov logic networks (MLNs) is a probabilistic graphical model defined over Markov networks. These networks are defined by templated first-order logic-like rules, which is then grounded over the training data. MLNs are able to incorporate both local and relational rules for the purpose of link prediction.[15]

R-Model (RMLs)

[edit]

R-Models (RMLs) is a neural network model created to provide a deep learning approach to the link weight prediction problem. This model uses a node embedding technique that extracts node embeddings (knowledge of nodes) from the known links’ weights (relations between nodes) and uses this knowledge to predict the unknown links’ weights.[16]

Applications

[edit]

Link prediction has found varied uses, but any domain in which entities interact in a structures way can benefit from link prediction.[17] A common applications of link prediction is improving similarity measures for collaborative filtering approaches to recommendation. Link prediction is also frequently used in social networks to suggest friends to users. It has also been used to predict criminal associations.

In biology, link prediction has been used to predict interactions between proteins in protein-protein interaction networks.[18] Link prediction has also been used to infer interactions between drugs and targets using link prediction [19] Another application is found in collaboration prediction in scientific co-authorship networks.

Entity resolution, also known as deduplication, commonly uses link prediction to predict whether two entities in a network are references to the same physical entity. Some authors have used context information in network structured domains to improve entity resolution.[20]

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Link prediction

View on Grokipedia
from Grokipedia
Link prediction is a core task in and network analysis that aims to infer the likelihood of missing or future edges between nodes in a network, given a partial snapshot of its structure. This problem models real-world systems as graphs where vertices represent entities and edges denote relationships, enabling predictions based on observed topology, node attributes, and relational patterns. Originating from and studies in the early 2000s, link prediction gained prominence through foundational work examining collaboration networks and web structures. Early methods focused on similarity-based heuristics, such as the common neighbors index, which scores potential links by the number of shared connections, or global measures like the Katz index that propagate influence across paths of varying lengths. These approaches leverage topological features to estimate proximity, with local methods prioritizing efficiency and global ones capturing long-range dependencies. Subsequent developments introduced probabilistic and maximum likelihood models, including stochastic block models that assume community structures and hierarchical models accounting for network organization. In the deep learning era, graph neural networks (GNNs) have revolutionized the field by learning low-dimensional embeddings of nodes and edges, enabling scalable predictions through message-passing mechanisms in frameworks like GraphSAGE and SEAL. These GNN-based techniques excel in handling heterogeneous and dynamic graphs, outperforming traditional methods on benchmarks like citation and protein interaction networks. Link prediction finds diverse applications across domains, including recommender systems where it suggests user-item connections, biological network reconstruction to uncover protein interactions (e.g., estimating 80% missing links in yeast PPI networks), and knowledge graph completion for semantic web tasks. In social networks, it is prominently used in friend recommendation systems to anticipate potential friendships or collaborations, leveraging small-world properties (such as high clustering and short average path lengths) and hybrid techniques that combine link prediction with collaborative filtering and other methods, while in cybersecurity, it detects anomalous links. Evaluation typically uses metrics like area under the ROC curve (AUC) and precision at top-k, with datasets from sources like SNAP and KONECT serving as standards. Ongoing challenges include scalability for massive graphs, handling temporal dynamics, and addressing biases in imbalanced link distributions.

Problem Definition

Mathematical Formulation

Link prediction is the task of inferring the existence of potential missing or future edges in an undirected graph G=(V,E)G = (V, E), where VV is the set of nodes representing entities and EE is the set of observed edges representing interactions between them. This formulation assumes simple graphs without self-loops or multiple edges between the same pair of nodes. Formally, given a snapshot of the graph, the goal is to predict edges in the unobserved portion U∖EU \setminus E, where UU is the universal set of all possible edges, with ∣U∣=∣V∣⋅(∣V∣−1)/2|U| = |V| \cdot (|V| - 1)/2. In temporal settings, this involves dividing the edges into a training set ETE_T from an earlier time interval and a probe set EPE_P from a later interval, such that E=ET∪EPE = E_T \cup E_P and ET∩EP=∅E_T \cap E_P = \emptyset, then predicting links in EPE_P based on ETE_T. The problem is commonly framed as a task over pairs of nodes, treating observed edges as positive samples and unobserved pairs as negative samples, with the objective of estimating the probability p(u,v)p(u, v) that an edge exists between nodes uu and vv. The graph structure is often represented using the A∈{0,1}∣V∣×∣V∣A \in \{0, 1\}^{|V| \times |V|}, where Auv=1A_{uv} = 1 if (u,v)∈E(u, v) \in E and Auv=0A_{uv} = 0 otherwise (with AA symmetric for undirected graphs); link prediction then seeks to estimate values of AuvA_{uv} for unobserved entries. For large graphs, the computational challenge arises from the quadratic number of possible edges, O(∣V∣2)O(|V|^2), which makes exhaustive evaluation prohibitive without efficient approximations; static formulations (random edge splits) contrast with snapshot-based approaches (temporal divisions), where the latter better capture evolving dynamics but require handling time-stamped .

Problem Variants

Link prediction problems extend beyond the standard static, undirected, binary-edge setting to accommodate real-world complexities in graph structures. One key variant distinguishes between static and dynamic scenarios. In static link prediction, the graph is treated as fixed, focusing on inferring missing or potential links based on the current snapshot. In contrast, dynamic link prediction addresses evolving graphs where edges appear, disappear, or change over time, often using temporal snapshots to forecast future connections. This variant is crucial for applications like evolution, where historical interaction patterns inform predictions of emerging ties. Surveys highlight that dynamic approaches must capture temporal dependencies, such as using time-decay functions or sequential models to weigh recent interactions more heavily than older ones. Recent surveys as of 2025 emphasize ongoing advancements in temporal link prediction. Another important distinction involves directed versus undirected graphs. Undirected link prediction assumes symmetric relationships, where a link between nodes u and v implies mutual connectivity, common in friendship networks. Directed variants, however, model relations, such as citations or web hyperlinks, where an edge from u to v does not imply the reverse. In directed graphs, prediction requires distinguishing incoming and outgoing links, often using asymmetric similarity measures like directed common neighbors or variants to account for directionality. For instance, in citation networks, predicting a directed link from paper A to B involves analyzing A's references to B's topics without assuming reciprocity. Research emphasizes that naive adaptation of undirected methods to directed graphs can lead to suboptimal performance due to ignored . Heterogeneous graphs introduce further complexity by featuring multiple node and edge types, as seen in knowledge graphs with entities like persons, organizations, and relations such as "employs" or "located_in." Unlike homogeneous graphs, link prediction here must respect type constraints, predicting only plausible connections (e.g., links between persons and organizations). Methods often leverage meta-paths—sequences of typed edges—to capture semantic paths, enabling type-aware embeddings that enhance prediction accuracy in benchmarks like academic collaboration networks. This variant is prevalent in recommendation systems, where diverse data types (users, items, reviews) require tailored proximity measures. Seminal work on relational graph convolutional networks has established foundations for handling such multiplicity. N-ary link prediction generalizes beyond binary edges to multi-relational facts in knowledge graphs, such as (head , relation, tail , attributes), capturing complex interactions like "Einstein (discovered, , in 1915, with )." Traditional binary methods falter here, as they cannot model roles or additional qualifiers; n-ary approaches instead decompose facts into structured representations, like hyper-relations or box embeddings, to predict missing components. Surveys note that this variant addresses limitations in binary knowledge graphs, achieving improved Hits@1 scores on datasets like WikiPeople by incorporating role-specific embeddings. It is essential for domains like , where facts involve multiple interacting elements. Recent 2025 surveys review progress in n-ary methods. Signed and weighted link prediction incorporate edge attributes for richer semantics. Signed variants predict positive (e.g., trust) or negative (e.g., ) links in networks, using structural balance principles where cycles of even length with mixed signs indicate instability. Weighted prediction extends this by forecasting edge strengths, such as interaction frequencies, often via probabilistic models that normalize similarities by edge magnitudes. In signed networks, methods exploiting longer cycles have demonstrated superior AUC scores compared to local heuristics. For weights, reliable route-based approaches predict both existence and intensity, vital for or networks. These variants enhance standard by quantifying relation . Finally, hyperlink prediction in s targets higher-order connections where edges (hyperlinks) link multiple nodes, as in co-authorship groups or protein complexes. Unlike pairwise links, this predicts entire hyperedges, using incidence matrices or embeddings to infer group formations. Approaches like neural models have demonstrated improved F1 scores on datasets like DBLP, by modeling node subsets' joint affinities. This variant is key for capturing collective interactions absent in simple graphs.

Historical Development

Early Foundations

The origins of link prediction can be traced to foundational concepts in and during the 1970s, emphasizing graph distance, connectivity, and node similarity to model relational structures. A key contribution came from Lorrain and White, who in 1971 defined structural equivalence in social networks as occurring when two individuals (nodes) share identical connections to others, using measures like on adjacency vectors to quantify similarity and infer potential relational patterns. This approach highlighted how topological proximity could reveal underlying social structures, providing an early theoretical basis for predicting absent links based on existing connectivity. In the 1990s, these ideas extended to bibliographic and social networks, where similarity measures were applied to analyze co-authorship patterns and anticipate collaborations. Researchers drew on metrics such as common neighbors and co-citation—building on earlier work like Kessler's 1963 bibliographic coupling, which linked papers sharing common references as similar—to explore network evolution in scientific communities. Wasserman and Faust's 1994 comprehensive treatment formalized such measures for social network analysis, including structural equivalence variants like Hamming distance, enabling the identification of potential ties in co-authorship graphs through observed relational overlaps. These efforts underscored early predictive intuitions, such as forecasting researcher collaborations based on shared connections. Parallel influences emerged from database management and in the 1980s and 1990s, where and entity resolution techniques addressed the challenge of merging disparate sources by estimating the likelihood of matches via similarity scores. The probabilistic framework established by Fellegi and Sunter in 1969, which compared record pairs using weighted agreement patterns, became a cornerstone, with practical implementations proliferating in statistical agencies during this era to resolve entity identities across datasets. This work prefigured link prediction by treating potential matches as inferred connections in an implicit graph of records. The formalization of link prediction as a distinct problem occurred in the early 2000s, with Liben-Nowell and Kleinberg's 2003 paper articulating it as the task of inferring likely future edges from a network snapshot using proximity metrics derived from graph topology. Initial motivations focused on practical applications, such as predicting hyperlinks in web graphs and new collaborations in co-authorship networks, where simple node similarity measures demonstrated predictive power without requiring external features.

Key Advancements

In the , link prediction research gained prominence in , with similarity-based methods emerging as foundational approaches by leveraging topological features to infer potential connections. These methods, such as common neighbors and , were extended through integrations with global centrality measures like and , which adapted principles to score node pairs based on their authority and hub scores within the network. This period marked a shift toward empirical applications in large-scale social graphs, where such techniques demonstrated improved predictive accuracy over purely local heuristics by incorporating network-wide propagation effects. The 2010s saw the rise of and embedding techniques, enabling scalable representations for link prediction in sparse, high-dimensional networks. Early models treated link prediction as a supervised task, learning latent factors from observed edges to reconstruct missing ones, which proved effective on recommendation-like graphs. A pivotal advancement was the LINE model, which introduced efficient first- and second-order proximity objectives to embed nodes in low-dimensional spaces while preserving local and global structures, achieving up to 5x speedup over methods like DeepWalk on networks with millions of nodes. From 2015 to 2020, the advent of graph neural networks (GNNs) revolutionized link prediction by enabling end-to-end learning of node representations through . GraphSAGE (2017) advanced inductive learning by sampling and aggregating neighborhood features, allowing generalization to unseen nodes and demonstrating superior performance on inductive node classification tasks using dynamic citation networks. Similarly, the Graph Attention Network (GAT, 2018) incorporated attention mechanisms to weigh neighbor contributions dynamically, outperforming prior GNNs on node classification benchmarks. Between 2020 and 2025, developments addressed dynamic and heterogeneous settings, with temporal GNNs like TGAT (2020) introducing time-aware attention to model evolving interactions, capturing temporal dependencies in event streams for improved future link forecasting in social and biological networks. In knowledge graphs, N-ary models extended prediction to multi-entity facts, with surveys highlighting tensor-based and embeddings that enhanced completeness in complex domains like . The impact of big data drove scalability enhancements through sampling and approximation, such as neighborhood subsampling in GraphSAGE to handle billion-edge graphs and randomized low-rank approximations in matrix methods, reducing computational complexity from O(n^2) to near-linear while maintaining predictive quality. A key milestone was the 2024 survey on feature learning techniques, which underscored the transition to deep embedding methods, reporting significant improvements, such as GCN achieving higher AUC scores than traditional metrics like common neighbors on benchmarks. In late 2025, studies such as those reconsidering Graph Autoencoder (GAE) performance in link prediction highlighted the impact of advanced training techniques on GNN efficacy.

Background Concepts

Graphs and Networks

A graph GG is formally defined as an G=(V,E)G = (V, E), where VV is a of vertices (also called nodes) and EE is a set of edges, with each edge being an of distinct vertices from VV in the case of simple undirected graphs. Simple undirected graphs prohibit self-loops (edges connecting a vertex to itself) and multiple edges between the same pair of vertices, making them suitable for modeling symmetric relationships without redundancy. The AA of such a graph is a square matrix where the entry Aij=1A_{ij} = 1 if there is an edge between vertices ii and jj, and 00 otherwise; since the graph is undirected, AA is symmetric. Networks, often used interchangeably with graphs in this context, can vary in structure. Unweighted networks assign no numerical values to edges, focusing solely on their presence or absence, whereas weighted networks include edge weights to represent strengths, capacities, or similarities. Simple graphs contrast with multigraphs, which allow multiple edges between the same pair of vertices and may include self-loops, enabling the modeling of parallel connections or reflexive relations. Real-world , such as social or biological systems, frequently exhibit distinctive properties: scale-free degree distributions, where the probability P(k)P(k) of a node having degree kk follows a P(k)∼k−γP(k) \sim k^{-\gamma} with 2<γ<32 < \gamma < 3, as modeled by the preferential attachment mechanism in the Barabási–Albert model; the small-world phenomenon, characterized by short average path lengths despite high local clustering; and non-zero clustering coefficients, quantifying the tendency for neighbors of a node to be interconnected. The local clustering coefficient for a node uu with degree kuk_u is Cu=2×number of edges between neighbors of uku(ku−1)C_u = \frac{2 \times \text{number of edges between neighbors of } u}{k_u (k_u - 1)}, while the global coefficient averages this over all nodes. For efficient storage and traversal, especially in large-scale applications, graph representations differ based on density. Adjacency matrices require O(∣V∣2)O(|V|^2) space, which is inefficient for sparse graphs where ∣E∣≪∣V∣2|E| \ll |V|^2, but adjacency lists—arrays of lists where each index corresponds to a vertex and lists its adjacent vertices—use O(∣V∣+∣E∣)O(|V| + |E|) space, making them preferable for sparse structures common in complex networks. Basic operations include computing the degree d(u)=∣{v∈V:{u,v}∈E}∣d(u) = |\{ v \in V : \{u, v\} \in E \}|, identifying the open neighborhood N(u)={v∈V:{u,v}∈E}N(u) = \{ v \in V : \{u, v\} \in E \}, and measuring path lengths as the number of edges in the shortest sequence of adjacent vertices between two nodes. In the context of link prediction, these graph structures are crucial because the observed edge set EE typically represents an incomplete view of the underlying network.

Similarity and Proximity Measures

Similarity and proximity measures quantify the likelihood of a potential link between nodes in a graph by assessing how closely connected or structurally alike the nodes are, serving as foundational components in link prediction tasks across various network types. These measures operate on the principle that nodes exhibiting higher similarity or proximity are more prone to forming edges, drawing from topological properties of the graph. In link prediction, such measures help rank non-existent edges by assigning scores that reflect relational closeness, often derived from neighborhood overlaps or path structures without relying on node attributes. Local similarity measures focus on the immediate neighborhoods of nodes, capturing direct connections and common neighbors within short distances, which makes them computationally efficient for large graphs but limited in scope. In contrast, global similarity measures incorporate information from the entire network structure, such as paths spanning multiple hops, to provide a more comprehensive view of node relationships, though they are often more resource-intensive to compute. This distinction allows local measures to excel in dense, localized clusters while global ones better handle broader connectivity patterns in complex networks. Path-based proximity emphasizes the role of connecting paths between nodes, where shorter paths or weighted ensembles of all paths indicate stronger potential links; for instance, weights can decay exponentially with path length to prioritize nearby connections. These approaches model proximity as the aggregation of paths, reflecting how information or influence might propagate through the graph, and have been shown to improve prediction accuracy in networks with hierarchical structures. By considering multiple path lengths, path-based methods bridge local and global perspectives, enhancing robustness in diverse graph topologies. Structural equivalence assesses similarity based on nodes having comparable connection patterns to other nodes in the graph, regardless of direct proximity, identifying nodes that occupy similar roles or positions within the network. Nodes deemed structurally equivalent are expected to link to similar sets of other nodes, making this measure useful for predicting links in role-based systems like organizational or biological networks. This concept extends beyond mere neighbor overlap to capture isomorphic substructures, providing insights into functional similarities. The role of randomness in similarity measures is exemplified by stochastic block models (SBMs), which incorporate probabilistic community structures to define node similarity based on latent group memberships, where nodes within the same block have higher link probabilities. SBMs introduce randomness to account for unobserved community effects, enabling similarity scores that reflect block-wise affinities rather than deterministic patterns, and have been adapted for link prediction in evolving networks. This probabilistic framework helps model assortative mixing in communities, improving predictions in modular graphs. Despite their utility, similarity and proximity measures exhibit limitations, particularly sensitivity to network density and sparsity, where sparse graphs lead to unreliable scores due to insufficient paths or neighbors, resulting in poor generalization. In low-density settings, local measures may underperform due to noise from isolated nodes, while global measures suffer from computational overhead without proportional gains in accuracy. These challenges highlight the need for hybrid or adaptive approaches to mitigate biases in underrepresented regions. These measures fundamentally inform scoring functions in link prediction by transforming structural insights into probabilistic edge likelihoods, guiding algorithms toward pairs with high predicted connectivity and paving the way for more advanced topological methods.

Approaches

Topology-Based Methods

Topology-based methods for link prediction rely exclusively on the structural properties of the graph, such as connectivity patterns and path counts between nodes, to estimate the likelihood of a potential edge forming between two non-adjacent nodes uu and vv. These approaches assume that the topology encodes latent relational tendencies, where nodes with similar neighborhood structures or short paths between them are more prone to connect. Seminal work formalized many of these heuristics in the context of social networks, evaluating their predictive power across diverse datasets. One of the simplest topology-based measures is the common neighbors index, which scores a pair (u,v)(u, v) as the size of the intersection of their neighbor sets: s(u,v)=∣Γ(u)∩Γ(v)∣s(u,v) = |\Gamma(u) \cap \Gamma(v)|, where Γ(x)\Gamma(x) denotes the neighbors of node xx. This metric posits that shared connections indicate a higher probability of future linkage, as common neighbors may facilitate introductions or influence. It performs well in dense, clustered networks like collaboration graphs but can favor high-degree nodes without normalization. To address degree biases in common neighbors, the Jaccard coefficient normalizes the overlap by the union of neighborhoods: s(u,v)=∣Γ(u)∩Γ(v)∣∣Γ(u)∪Γ(v)∣s(u,v) = \frac{|\Gamma(u) \cap \Gamma(v)|}{|\Gamma(u) \cup \Gamma(v)|}. Originally a set similarity measure, it was adapted for link prediction to penalize pairs where one or both nodes have many connections, emphasizing relative overlap over absolute count. This makes it particularly effective in heterogeneous networks with varying node degrees. The Adamic-Adar index refines common neighbors by weighting shared intermediaries inversely by their degree: s(u,v)=∑w∈Γ(u)∩Γ(v)1log⁡∣Γ(w)∣s(u,v) = \sum_{w \in \Gamma(u) \cap \Gamma(v)} \frac{1}{\log |\Gamma(w)|}. Introduced to capture the intuition that connections through low-degree (rarer) nodes are more predictive than those through hubs, it boosts the signal from distinctive common neighbors. Empirical studies on web and citation networks showed it outperforming unweighted counts in precision. The Katz index extends beyond immediate neighbors by aggregating all walks of varying lengths between uu and vv, with exponential decay for longer paths: s(u,v)=∑ℓ=1∞βℓ⋅#(walks of length ℓ from u to v),s(u,v) = \sum_{\ell=1}^{\infty} \beta^\ell \cdot \#(\text{walks of length } \ell \text{ from } u \text{ to } v), where 0<β<10 < \beta < 1 controls the attenuation. This can be computed in closed form as the (u,v)(u,v)-entry of the matrix (I−βA)−1−I(I - \beta A)^{-1} - I, with AA the adjacency matrix, capturing global topological proximity akin to a decaying random walk. Derived from sociometric status measures, it excels in capturing transitive closures but requires tuning β\beta for sparsity. Preferential attachment draws from scale-free network growth models, scoring pairs as the product of their degrees: s(u,v)=∣Γ(u)∣⋅∣Γ(v)∣s(u,v) = |\Gamma(u)| \cdot |\Gamma(v)|. It embodies the "rich-get-richer" principle, where high-degree nodes are more likely to attract new links due to visibility or resources. Rooted in empirical observations of power-law distributions, this heuristic predicts well in growing networks like the World Wide Web but underperforms in static or assortative structures. For large-scale graphs, computing these scores naively is prohibitive due to O(n2)O(n^2) pairs and high-degree intersections. Efficient approximations leverage sparse matrix multiplications: for instance, common neighbors can be estimated via A2A^2's diagonal-off entries, Katz via Neumann series truncation or low-rank inversions, and preferential attachment directly from degree sequences. These techniques scale to millions of nodes on standard hardware, with preprocessing like indexing accelerating neighbor intersections.

Node and Edge Feature-Based Methods

Node and edge feature-based methods for link prediction rely on explicit attributes associated with nodes or potential edges, rather than solely on graph topology, to infer the likelihood of connections between pairs of nodes. These attributes can include vector representations xu\mathbf{x}_u for each node uu, such as user profiles in social networks (e.g., age, interests, or location) or protein properties in biological graphs. By computing similarity scores directly from these features, methods estimate link probabilities; for instance, nodes with highly similar attributes are more likely to form edges in domains like collaboration networks. A common approach uses distance-based similarity measures on node attribute vectors. The Euclidean distance between two nodes uu and vv is calculated as s(u,v)=∥xu−xv∥2s(u,v) = \|\mathbf{x}_u - \mathbf{x}_v\|_2, where lower distances indicate higher link probability, making it suitable for numerical attributes like coordinates or quantitative profiles. For directional or high-dimensional data, cosine similarity is preferred: s(u,v)=xu⋅xv∥xu∥∥xv∥s(u,v) = \frac{\mathbf{x}_u \cdot \mathbf{x}_v}{\|\mathbf{x}_u\| \|\mathbf{x}_v\|}, which captures angular alignment and is robust to vector magnitudes, as seen in text-based attributes like document embeddings or keyword vectors in academic coauthorship prediction. These measures provide interpretable scores that can be thresholded or ranked to predict links. Edge features extend this paradigm by incorporating attributes on potential connections, such as spatial distances in geographic networks where proximity (e.g., Euclidean distance between locations) serves as a direct predictor of link formation. In supervised settings, these node and edge features are concatenated into input vectors for classification models to predict edge existence. Logistic regression models the probability of a link as P(u,v)=σ(wTfuv+b)P(u,v) = \sigma(\mathbf{w}^T \mathbf{f}_{uv} + b), where fuv\mathbf{f}_{uv} combines node similarities and edge attributes, while support vector machines (SVMs) with RBF kernels have demonstrated superior performance, achieving up to 90% accuracy on coauthorship datasets by classifying feature vectors from historical links. Handling mixed attribute types is essential for real-world graphs. Categorical features, such as user categories or research topics, are often encoded via match counts (e.g., overlapping keywords) or one-hot encoding to enable similarity computation, while numerical features undergo normalization (e.g., min-max scaling to [0,1]) to prevent scale dominance in distance metrics. This preprocessing ensures robust feature integration, as validated in supervised frameworks where encoded attributes improve prediction precision and recall over unprocessed inputs.

Embedding and Representation Learning Methods

Embedding and representation learning methods for link prediction focus on deriving low-dimensional vector representations (embeddings) of nodes from graph structure, node attributes, or both, which are then used to compute similarity scores for potential edges. These approaches enable scalable predictions by capturing latent patterns in the data, often outperforming heuristic measures on large, sparse networks. Early techniques drew from and , while modern variants leverage to handle complex dependencies. Matrix factorization represents a foundational embedding method, decomposing the adjacency matrix AA of the graph into two low-rank matrices UU and VV such that A≈UVTA \approx U V^T, where rows of UU and VV serve as embeddings for source and target nodes, respectively. The likelihood of a link between nodes ii and jj is scored via the dot product ui⋅vju_i \cdot v_j, which approximates the entry AijA_{ij}. This approach, inspired by recommender systems, effectively learns latent factors from observed links while regularizing for sparsity, achieving strong performance on bipartite graphs like user-item networks. Random walk-based methods generate embeddings by simulating walks on the graph and applying word embedding techniques like Skip-Gram to predict context nodes. Node2Vec, introduced in 2016, extends this paradigm with biased random walks that balance breadth-first (homophily-focused) and depth-first (structural equivalence-focused) sampling via parameters pp and qq, producing embeddings where similar nodes co-occur in walk contexts. Link scores are computed as the dot product of node embeddings, enabling effective prediction in diverse networks such as social and citation graphs, with demonstrated improvements over prior walk-based models like DeepWalk. Graph neural networks (GNNs) advance embedding learning through iterative message passing, where node representations are updated by aggregating features from neighbors. GraphSAGE, proposed in 2017, introduces an inductive framework that samples and aggregates neighbor features using mean, LSTM, or pooling operations, generating embeddings scalable to unseen nodes without full graph retraining. For link prediction, embeddings of candidate nodes are concatenated and passed through a multilayer perceptron (MLP) to output edge probabilities, excelling in inductive settings like large-scale web graphs with textual node features. Extensions to heterogeneous and dynamic graphs address multi-relational and temporal aspects. Relational Graph Convolutional Networks (R-GCNs), from 2018, handle knowledge graphs with multiple edge types by applying relation-specific transformations during message passing, learning type-aware embeddings while sharing parameters for efficiency; link scores follow standard GNN decoding, improving prediction on benchmarks like Freebase. For temporal graphs, Temporal Graph Attention Networks (TGAT), introduced in 2020, incorporate time encoding via learnable embeddings and attention mechanisms to weigh historical interactions, producing time-aware node representations for dynamic link prediction in evolving networks like social interactions. Recent advances integrate transformer architectures into GNNs for enhanced scalability and expressiveness in heterogeneous link prediction. Transformer-based GNNs, such as those leveraging multi-head attention over graph paths or subgraphs from 2023 onward, capture long-range dependencies in knowledge graphs, outperforming convolutional variants on large-scale datasets by fusing local structure with global context; for instance, models like enhanced graph transformers achieve state-of-the-art results on tasks involving multimodal features. Training these embedding models often employs negative sampling to approximate the full objective efficiently, generating non-existent edges as negatives to contrast against observed positives, as in Node2Vec's Skip-Gram optimization. Contrastive losses further enhance representations by maximizing similarity for positive (linked) pairs while minimizing it for negatives, promoting discriminative embeddings; this is particularly vital for scalability in GNNs, reducing computational overhead from dense pairwise computations.

Probabilistic and Logical Methods

Probabilistic and logical methods in link prediction model the uncertainty inherent in graph edges by leveraging probabilistic frameworks and logical rules to infer potential links, emphasizing interpretability and the incorporation of prior knowledge over purely data-driven approaches. These methods treat link existence as a probabilistic event, often estimating the probability P(edge∣u,v)P(\text{edge} \mid u, v) based on relational structures and domain-specific rules, which allows for handling incomplete or noisy data in networks. By combining statistical inference with logical reasoning, they provide not only predictions but also explanations grounded in human-readable rules, distinguishing them from embedding-based techniques that prioritize latent representations. Bayesian approaches formulate link prediction as a probabilistic inference problem, where priors are placed on graph paths or relational patterns to estimate the likelihood of an edge between nodes uu and vv. For instance, Bayesian personalized ranking adapts matrix factorization with Bayesian priors to rank potential links in recommendation graphs, achieving superior performance on sparse datasets by incorporating user-item interactions as probabilistic evidence. More advanced variants, such as deep graph convolutional Gaussian processes, integrate Bayesian nonparametrics with graph convolutions to model edge probabilities while quantifying epistemic uncertainty through variational inference, demonstrating improved accuracy on citation networks like Cora compared to deterministic baselines. These methods excel in scenarios with limited labeled data, as the priors regularize predictions against overfitting. Markov logic networks (MLNs) extend first-order logic with probabilistic weights attached to rules, enabling the modeling of relational dependencies for link prediction. Each logical formula, such as "friends of friends are likely to be friends" (e.g., ∀x,y,z Friends(x,y)∧Friends(y,z)⇒Friends(x,z)\forall x, y, z \, \text{Friends}(x,y) \land \text{Friends}(y,z) \Rightarrow \text{Friends}(x,z)), is assigned a weight that reflects its confidence, and the network's probability distribution over possible worlds is defined via a Markov random field. Inference in MLNs for link prediction typically employs Markov chain Monte Carlo (MCMC) sampling to compute marginal probabilities of missing edges, as demonstrated in applications to social networks where relational rules capture transitivity and homophily. This framework has been shown to outperform independent link predictors by collectively reasoning over the entire graph structure. Probabilistic soft logic (PSL) relaxes the binary truths of classical logic using Łukasiewicz semantics, where truth values range continuously from 0 to 1, allowing for soft constraints in relational domains. In link prediction, PSL defines an objective function that maximizes the posterior probability over these soft truth values by minimizing hinge-loss violations of weighted rules, such as those encoding path-based similarities. The optimization is solved via convex programming, making it scalable for large graphs, and has been applied effectively to tasks like entity resolution and knowledge base completion, where it integrates noisy evidence from multiple relations. PSL's relaxation enables handling of conflicting rules, yielding more robust predictions than crisp logical systems. Relational models like R-Models (RMLs) use node embedding techniques in neural network architectures to predict link weights by extracting relational information from known connections. These models facilitate scalable inference over relational data in weighted graphs, balancing predictive power with the ability to handle multi-relational structures. Handling noise in these methods involves uncertainty quantification, such as computing confidence intervals or posterior distributions over predicted edges to account for observational errors or incomplete information. Bayesian frameworks naturally provide this through posterior sampling, offering epistemic uncertainty estimates that highlight low-confidence predictions in noisy environments like biological networks. Similarly, MLNs and PSL incorporate noise via weighted rules and soft truths, enabling robust inference that propagates uncertainty across relations. Recent neurosymbolic integrations, particularly from 2024-2025, hybridize graph neural networks (GNNs) with logical and probabilistic components for explainable link prediction. These approaches use GNNs to learn embeddings that are then constrained by symbolic rules, improving interpretability in complex domains; for example, neural-symbolic reasoning frameworks infer missing links via rule-grounded attention mechanisms, outperforming pure GNNs on knowledge graphs by providing traceable explanations as of 2025. Such hybrids have shown promise in applications requiring accountability, like supply chain networks, where they quantify prediction uncertainty while adhering to domain logic.

Evaluation

Performance Metrics

Link prediction performance is typically evaluated using metrics that assess the ability of models to rank potential edges correctly, given the inherent sparsity and class imbalance in graphs where non-edges vastly outnumber observed edges. These metrics emphasize ranking quality over absolute classification accuracy, as the task often involves prioritizing likely links from a large pool of candidates. The area under the receiver operating characteristic curve (AUC-ROC) measures the model's capacity to distinguish observed edges from non-edges by ranking non-observed pairs below observed ones, computed as the probability that a randomly chosen observed edge scores higher than a randomly chosen non-edge. Formally, for a scoring function s(u,v)s(u,v) assigning scores to node pairs (u,v)(u,v), AUC=1∣E+∣∣E−∣∑(u,v)∈E+∑(x,y)∈E−I[s(u,v)>s(x,y)],\text{AUC} = \frac{1}{|\mathcal{E}^+||\mathcal{E}^-|} \sum_{(u,v) \in \mathcal{E}^+} \sum_{(x,y) \in \mathcal{E}^-} \mathbb{I}[s(u,v) > s(x,y)], where E+\mathcal{E}^+ and E−\mathcal{E}^- are sets of observed and non-observed edges, respectively, and I[⋅]\mathbb{I}[\cdot] is the . AUC is widely adopted due to its threshold-independent and interpretability as performance, though it can be less sensitive in highly sparse networks. Precision at kk (P@k) evaluates the fraction of true edges among the top-kk highest-scored candidate pairs, focusing on the quality of the most promising predictions. It is defined as P@k=∣{(u,v)∈top-k:(u,v)∈E+}∣k,\text{P@k} = \frac{|\{ (u,v) \in \text{top-}k : (u,v) \in \mathcal{E}^+ \}|}{k}, prioritizing practical utility in applications like recommendation systems where only a small number of top predictions are acted upon. Mean average precision (MAP) extends precision by averaging precision values at each rank where a true edge appears, providing a robust measure for imbalanced settings through its emphasis on ranking order. For a set of queries (e.g., per-node predictions), MAP is the mean of average precisions across all queries, where average precision for a query is AP=1m∑r=1nP@r⋅I[r∈relevant ranks],\text{AP} = \frac{1}{m} \sum_{r=1}^{n} \text{P@r} \cdot \mathbb{I}[r \in \text{relevant ranks}], with mm as the number of true edges for the query and nn as the total ranked list length; this metric is particularly effective for capturing cumulative ranking quality in sparse graphs. Hit ratio at kk (HR@k), also known as recall at kk, assesses whether at least one true edge appears in the top-kk predictions, offering a binary indicator of basic retrieval success. Computed as HR@k=∣{q:top-kq∩Eq+≠∅}∣∣Q∣,\text{HR@k} = \frac{|\{ q : \text{top-}k_q \cap \mathcal{E}^+_q \neq \emptyset \}|}{|\mathcal{Q}|}, where Q\mathcal{Q} is the set of queries and top-kqk_q is the top-kk for query qq, it is useful for evaluating whether models recover any relevant links but overlooks ranking depth. Beyond accuracy-focused metrics, novelty and diversity evaluate the non-triviality and variety of predictions to avoid recommending obvious or redundant links. Novelty metrics, such as long-tail novelty, quantify how unexpected predictions are by measuring deviation from users' existing connections, often using formulas like the average complement of indegrees for predicted contacts. Diversity metrics, like intra-list dissimilarity, compute average pairwise distances between recommended nodes to ensure varied suggestions, promoting broader exploration in networks. These are adapted from recommender systems to penalize predictions of highly connected or similar nodes, enhancing practical value. Due to class imbalance in link prediction, where non-edges dominate, standard AUC can overestimate performance; alternatives like the F1-score, the harmonic mean of precision and recall, or the area under the precision-recall curve (AUPR) are preferred for balanced assessment. The F1-score is F1=2⋅precision⋅recallprecision+recall,\text{F1} = 2 \cdot \frac{\text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}}, applied after thresholding scores, while AUPR integrates precision across recall levels, better reflecting minority class (edge) performance in sparse graphs.

Datasets and Benchmarks

Link prediction research relies on a variety of benchmark datasets that capture different graph structures, domains, and dynamics to evaluate model performance across static, temporal, heterogeneous, and domain-specific scenarios. These datasets provide standardized resources for comparing algorithms, with static benchmarks often serving as foundational tests for - and embedding-based methods, while dynamic and heterogeneous ones address real-world complexities like evolving networks and multi-type relations. Static benchmarks include the Cora citation network, which consists of 2,708 nodes representing papers and 5,429 edges denoting citations between them, commonly used to assess link prediction in academic graphs. Another prominent example is the Protein-Protein Interaction (PPI) dataset, featuring 3,890 proteins as nodes and 76,584 interactions as edges in a network subgraph, enabling evaluation of biological link formation. For dynamic link prediction, datasets like the edit networks model temporal user interactions through edit histories, with snapshots capturing evolving collaborations over time. The -Eu-core dataset, derived from anonymized communications at a European research institution, includes 1,005 nodes and 25,571 edges, supporting predictions of interactions in communication networks. Heterogeneous datasets extend evaluation to multi-relational graphs; subsets of Freebase, such as FB15k with 14,951 entities and 134,500 triples across 1,345 relation types, test prediction of diverse links. The OGB-Arxiv dataset from the Open Graph Benchmark comprises 169,343 arXiv papers as nodes, 1,166,243 citation edges, and category labels as node features, facilitating link prediction in heterogeneous citation networks with metadata. In biomedical contexts, the BioSNAP collection provides datasets like those from the database, which includes over 2,000 proteins and 100,000+ interactions in human networks, for predicting protein associations. specifically offers high-confidence physical and functional links; the human network in version 11 contains over 19,000 proteins and millions of interactions, used to benchmark domain-specific predictors. Standard evaluation protocols involve time-splitting for dynamic datasets, typically allocating 80% of edges to training and 20% to testing based on timestamps to simulate future predictions. Negative sampling is employed to generate non-edges for training and ranking, with ratios ranging from 1:1 for balanced sets to 1:50 for challenging imbalanced scenarios, ensuring robust assessment of model discrimination. Recent benchmarks from 2023-2025 emphasize N-ary facts in knowledge graphs, extending beyond binary links; for instance, WikiKG90Mv2 from the Open Graph Benchmark contains 91 million entities and 601 million triples extracted from , supporting large-scale N-ary link imputation. These additions address complex, multi-entity relations in evolving KGs, as surveyed in works on N-ary prediction frameworks.

Applications

Social and Information Networks

Link prediction plays a central role in friend recommendation systems on social platforms like , , and , where a combination of techniques is used to suggest potential new connections. These include user-based collaborative filtering, which identifies users with similar connection patterns or common interactions and recommends friends of those similar users, and graph-based link prediction that treats the social network as a graph to predict missing edges representing potential friendships. Friend recommendation systems exploit the small-world properties of social networks, characterized by high clustering coefficients and short average path lengths (commonly referred to as the "six degrees of separation" phenomenon), by prioritizing suggestions within 2–3 degrees of separation, as most real-world friendships form through short network paths. Modern systems often employ hybrid recommender systems that combine graph-based link prediction, collaborative filtering, content-based filtering using user profiles and interests, and deep learning or graph neural network approaches to improve accuracy, handle cold-start problems, and provide diverse recommendations. Topological measures such as the Adamic-Adar index are employed to identify potential new connections based on common neighbors and their degrees. Introduced in 2003, the Adamic-Adar measure weights common friends by the inverse of their degree, giving higher importance to less-connected intermediaries, and has been implemented in production systems during the 2010s to suggest friends by predicting edges in user friendship graphs. For instance, on , supervised random walks incorporating temporal dynamics have enhanced prediction accuracy for future friendships, achieving significant improvements over baseline topological methods in large-scale evaluations. Similarly, on , link prediction using retweet histories has proven more effective than traditional friendship-based approaches for inferring user relationships, leveraging patterns to recommend follows. In web-based networks, link prediction aids in inferring missing hyperlinks within evolving sites, which supports efficient web crawling by anticipating new pages and connections. prediction extends traditional graph link prediction to directed web graphs, using node features like content similarity and topological scores to forecast outlinks, as surveyed in comprehensive studies of web structure dynamics. A practical application involves focused crawling, where models predict new outlinks from existing pages to prioritize discovery of relevant content, reducing crawl overhead in resource-constrained environments; for example, classifiers trained on historical link formations have demonstrated up to 20% improvement in discovering unindexed pages. Information diffusion in social and news networks often relies on link prediction to forecast sharing behaviors, such as retweets, by modeling the propagation of content as evolving edges in interaction graphs. Learning-based models that integrate user features, content semantics, and network structure have been developed to predict diffusion cascades on , capturing how initial shares lead to broader retweet links with accuracies exceeding 80% in benchmark tests. These approaches highlight the role of temporal and probabilistic factors in anticipating information spread, aiding platforms in moderating viral content. Ethical considerations in link prediction for social recommendations include privacy risks from inferring sensitive relationships and the potential to reinforce by prioritizing homophilous connections. Algorithms that suggest friends based on inferred links can inadvertently expose private associations through , raising concerns under regulations like GDPR. Moreover, link recommendation systems have been shown to amplify polarization by creating denser intra-group ties, as simulations on opinion dynamics reveal increased formation when recommendations favor similar users. To mitigate this, ethical frameworks advocate for diversity-aware predictions that balance accuracy with exposure to diverse viewpoints, preventing societal fragmentation. A notable case study is the competition of 2009, which influenced as a form of link prediction in bipartite user-item networks. The challenge framed movie recommendations as predicting missing ratings (edges) using matrix factorization and neighborhood methods, with winning ensembles achieving a 10% RMSE improvement over baselines, establishing as a cornerstone for social recommendation systems. This work demonstrated how link prediction principles scale to implicit feedback graphs, inspiring applications in friend and content suggestions on platforms like .

Biological and Biomedical Networks

Link prediction in biological and biomedical networks plays a crucial role in uncovering hidden relationships within complex systems, such as protein interactions, drug mechanisms, and disease associations, thereby accelerating scientific discovery in areas like and . These networks often model entities like proteins, genes, , and as nodes, with edges representing interactions derived from experimental data or databases. By applying link prediction techniques, researchers can infer potential connections that inform hypotheses for and . In protein-protein interaction (PPI) networks, link prediction helps identify novel interactions that elucidate cellular processes and disease pathways. The database, a comprehensive resource for PPI data, has been widely used in recent studies employing graph neural networks (GNNs) to predict edges in these networks. For instance, multiscale GNN models like MGPPI integrate hierarchical structural information to enhance prediction accuracy on STRING-derived datasets, achieving improvements over traditional methods by capturing both local and global network patterns. Similarly, hierarchical graph learning approaches have demonstrated superior performance in PPI prediction by leveraging multi-level representations, outperforming baseline topology-based methods on benchmark PPI datasets from . These 2024 advancements highlight the efficacy of GNNs in handling the scale and heterogeneity of PPI networks for tasks like functional annotation. Drug-target prediction utilizes link prediction to infer binding affinities in pharmacology graphs, where nodes represent drugs and proteins, and edges denote potential interactions. Graph-based models, such as GraphDTA, represent drugs as molecular graphs and employ GNNs to predict affinities, providing a foundational approach that has influenced subsequent work. More recent heterogeneous GNN frameworks, like GHCDTI, address limitations in homogeneous representations by modeling multi-type relations in networks, leading to enhanced prediction of drug-target interactions for repurposing applications. These methods prioritize structural and semantic features to forecast novel bindings, aiding in the identification of therapeutic candidates. For disease association, link prediction in gene-disease networks facilitates comorbidity forecasting by revealing shared genetic or pathway links between conditions. Approaches using variational graph auto-encoders on disease-disease interaction networks have shown promise in predicting comorbidities, with embeddings capturing latent associations to prioritize high-risk pairs. Genetically enriched homogeneous networks further improve accuracy by integrating semantic and genomic features, enabling the scoring of comorbid disease pairs based on learned node representations. Such predictions support epidemiological modeling and early intervention strategies in multifactorial diseases. Biomedical link prediction faces significant challenges, including noisy data from high-throughput experiments like , which introduce false positives and affect model robustness. Interpretability remains a key hurdle, as complex GNNs often act as black boxes, complicating validation in clinical contexts where causal insights are essential. Recent reviews emphasize addressing these through techniques like attention mechanisms and rule-based explanations to balance with transparency in biological networks. In 2025, heterogeneous graph neural networks (HGNNs) have advanced biomedical link prediction for by modeling diverse node types and relations in multi-omics networks. Frameworks like those applied to and datasets demonstrate HGNNs' ability to predict interactions for lead optimization, outperforming homogeneous GNNs in heterogeneous biomedical settings. These applications underscore HGNNs' role in integrating multi-modal data for efficient candidate identification.

Recommendation and Knowledge Graphs

Link prediction plays a pivotal in recommendation systems, particularly through on user-item bipartite graphs. In these graphs, nodes represent users and items (such as movies or books), with edges indicating interactions like ratings or purchases. Matrix factorization techniques decompose the into low-dimensional latent factor matrices for users and items, enabling the prediction of missing links by reconstructing potential interactions. For instance, this approach has been shown to outperform topology-based metrics like Adamic-Adar in tasks, achieving higher AUC scores on datasets with millions of edges. In completion, link prediction focuses on inferring missing triples (head, relation, tail) in structured RDF graphs, such as DBpedia, to enhance applications. The TransE model embeds entities and relations into a continuous , where a relation is modeled as a vector such that the head entity vector plus the relation vector approximates the tail entity vector, formalized as h+r≈t\mathbf{h} + \mathbf{r} \approx \mathbf{t}. This energy-based scoring function allows efficient prediction of plausible links, demonstrating strong performance on benchmarks like WN18 and FB15k, which include DBpedia subsets. In , link prediction on product co-purchase networks, exemplified by Amazon's dataset of over 500,000 products, identifies complementary items for recommendations. These networks treat products as nodes and co-purchases as edges, using graph neural networks like GraphSAGE to embed node features (e.g., titles and categories) and predict new edges for newly listed items. A modified GraphSAGE variant with one-hop sampling has achieved improvements in top-5 accuracy over baselines, enabling scalable suggestions in dynamic catalogs. For , neurosymbolic methods integrate neural networks with symbolic reasoning to predict supplier links in knowledge graphs, addressing opacity in traditional models. The Neural Bellman-Ford Network (NBFNet), introduced in 2024, combines graph neural propagation with logical rules for explainable predictions on heterogeneous graphs from sources like Marklines and Achilles, matching black-box GNN performance while providing transparency on datasets with tens of thousands of companies. This approach enhances digital surveillance by uncovering hidden dependencies across global networks. Recent advancements in n-ary extensions model multi-attribute relations beyond binary triples, crucial for handling complex facts like contracts with multiple roles and qualifiers. Models surveyed in 2025, such as those using convolutions and mechanisms, represent n-ary facts as star or box structures to capture qualifiers (e.g., time, ), improving completion accuracy on datasets like WikiPeople by 10-20% over binary baselines in applications. These methods facilitate richer representations in industrial settings, such as ontologies. Scalability remains essential for billion-scale graphs in recommendation and knowledge graphs, where full-graph processing is infeasible. Sampling techniques, such as two-stage degree-based and methods, extract representative subgraphs to approximate link predictions, reducing computational load while preserving performance. For example, on graphs with over 2 billion edges like OAG, these approaches with LLMs achieve 30% gains in hit rates over GNNs. These enable deployment on industrial platforms.

References

  1. https://www.cs.cornell.edu/home/kleinber/link-pred.pdf
  2. https://piccardi.faculty.polimi.it/VarieCsr/Papers/Lu2011.pdf
  3. http://papers.neurips.cc/paper/7763-link-prediction-based-on-graph-neural-networks.pdf
  4. https://openreview.net/pdf?id=YdjWXrdOTh
  5. https://www.nature.com/articles/30918
  6. https://link.springer.com/article/10.1023/A:1021240730564
  7. https://arxiv.org/pdf/2502.21185
  8. https://arxiv.org/abs/1010.0725
  9. https://jmlr.csail.mit.edu/papers/volume21/19-447/19-447.pdf
  10. https://arxiv.org/abs/2502.05724
  11. https://link.springer.com/chapter/10.1007/978-3-319-22735-1_2
  12. https://www.sciencedirect.com/science/article/abs/pii/S0167923620302037
  13. https://arxiv.org/abs/2302.10432
  14. https://arxiv.org/abs/2506.08970
  15. https://dl.acm.org/doi/10.1145/3308558.3313414
  16. https://www.ambujtewari.com/research/chiang11exploiting.pdf
  17. https://www.nature.com/articles/srep12261
  18. https://arxiv.org/abs/2207.02911
  19. https://malllabiisc.github.io/publications/papers/nhp_cikm20.pdf
  20. https://www.tandfonline.com/doi/abs/10.1080/0022250X.1971.9989788
  21. https://onlinelibrary.wiley.com/doi/10.1002/asi.5090140103
  22. https://www.tandfonline.com/doi/abs/10.1080/01621459.1969.10501049
  23. https://dl.acm.org/doi/10.1145/956863.956972
  24. https://cseweb.ucsd.edu/~elkan/ECML2011LinkPrediction.pdf
  25. https://arxiv.org/abs/1503.03578
  26. https://arxiv.org/abs/1706.02216
  27. https://arxiv.org/abs/1710.10903
  28. https://arxiv.org/abs/2002.07962
  29. https://link.springer.com/article/10.1007/s10462-024-10998-7
  30. https://arxiv.org/abs/2411.03845
  31. https://diestel-graph-theory.com/
  32. https://www.science.org/doi/10.1126/science.286.5439.509
  33. https://www.semanticscholar.org/paper/Friends-and-neighbors-on-the-Web-Adamic-Adar/8dc9d11e3fc229a1b70bb00de72dc15d55848174
  34. https://pdodds.w3.uvm.edu/files/papers/others/1999/barabasi1999a.pdf
  35. https://www.cs.rpi.edu/~zaki/PaperDir/LINK06.pdf
  36. https://arxiv.org/pdf/1502.04380
  37. https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p1817.pdf
  38. https://arxiv.org/abs/1607.00653
  39. https://www.nature.com/articles/s41598-025-08688-7
  40. https://keg.cs.tsinghua.edu.cn/jietang/publications/KDD20-Yang-et-al-Understanding_Negative_Sampling_in_GNN.pdf
  41. https://proceedings.mlr.press/v151/opolka22b/opolka22b.pdf
  42. https://homes.cs.washington.edu/~pedrod/papers/cikm02.pdf
  43. https://www.psl.law.stanford.edu/
  44. https://www.researchgate.net/publication/360516392_Predicting_future_link_in_social_network_A_review
  45. https://openreview.net/forum?id=hCyqbFapJi
  46. https://arxiv.org/abs/2401.03673
  47. https://www.sciencedirect.com/science/article/abs/pii/S0378437123000845
  48. https://academic.oup.com/pnasnexus/article/3/11/pgae498/7877235
  49. https://www.nature.com/articles/s41598-023-34055-5
  50. https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2163-9
  51. https://pmc.ncbi.nlm.nih.gov/articles/PMC9211798/
  52. https://dl.acm.org/doi/10.1145/3184558.3191576
  53. https://www.sciencedirect.com/science/article/pii/S221509862400168X
  54. https://arxiv.org/pdf/2005.00687
  55. https://arxiv.org/pdf/2310.00793
  56. http://snap.stanford.edu/deepnetbio-ismb/ipynb/Graph%2BConvolutional%2BPrediction%2Bof%2BProtein%2BInteractions%2Bin%2BYeast.html
  57. https://snap.stanford.edu/data/email-Eu-core.html
  58. https://snap.stanford.edu/biodata/
  59. https://proceedings.neurips.cc/paper_files/paper/2022/file/d49042a5d49818711c401d34172f9900-Paper-Datasets_and_Benchmarks.pdf
  60. https://www.mdpi.com/2076-3417/14/8/3516
  61. https://snap-stanford.github.io/ogb-web/docs/lsc/wikikg90mv2/
  62. https://cs.stanford.edu/people/jure/pubs/linkpred-wsdm11.pdf
  63. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0170279
  64. https://www.researchgate.net/publication/356083926_Prediction_of_new_outlinks_for_focused_crawling
  65. https://ieeexplore.ieee.org/document/7593657
  66. https://plato.stanford.edu/entries/ethics-social-networking/
  67. https://www.pnas.org/doi/10.1073/pnas.2102141118
  68. https://ojs.aaai.org/index.php/ICWSM/article/view/19275
  69. https://www.cs.uic.edu/~liub/KDD-cup-2007/proceedings/The-Netflix-Prize-Bennett.pdf
  70. https://shura.shu.ac.uk/33296/1/LPbasedRS_AAD.pdf
  71. https://arxiv.org/html/2404.10450v1
  72. https://pmc.ncbi.nlm.nih.gov/articles/PMC11284081/
  73. https://www.nature.com/articles/s41467-023-36736-1
  74. https://bmcbiol.biomedcentral.com/articles/10.1186/s12915-025-02359-9
  75. https://www.biorxiv.org/content/10.1101/684662v6.full-text
  76. https://www.nature.com/articles/s41598-025-16098-y
  77. https://dl.acm.org/doi/10.1007/978-3-032-02489-3_8
  78. https://www.sciencedirect.com/science/article/abs/pii/S0010482524013374
  79. https://pmc.ncbi.nlm.nih.gov/articles/PMC11187424/
  80. https://ieeexplore.ieee.org/iel8/6287639/10820123/10937165.pdf
  81. https://www.benevolent.com/about-us/publications/interpretable-graph-convolutional-neural-networks-inference-noisy-knowledge-graphs/
  82. https://academic.oup.com/bioinformaticsadvances/advance-article/doi/10.1093/bioadv/vbaf187/8222717?searchresult=1
  83. https://www.sciencedirect.com/science/article/pii/S2211383525006884
  84. https://proceedings.neurips.cc/paper_files/paper/2013/file/1ece0a27c5b3c970d5b8aa4e94b5d072-Paper.pdf
  85. https://arxiv.org/abs/2506.02482
  86. https://www.tandfonline.com/doi/full/10.1080/00207543.2024.2399713
  87. https://aclanthology.org/2025.emnlp-main.1451.pdf
  88. https://arxiv.org/abs/2401.13227
Add your contribution
Related Hubs
User Avatar
No comments yet.