Link Prediction

These are non-learning, rule-based approaches that calculate a score for a potential edge based on local graph structure. They are computationally efficient and serve as strong baselines.

• Common Neighbors: Scores a link by the number of neighbors two nodes share.
• Jaccard Coefficient: Normalizes the common neighbors count by the total union of neighbors.
• Adamic-Adar: Weighs common neighbors by their inverse degree, giving less weight to high-degree hub nodes.
• Preferential Attachment: Assumes a node's probability of forming new links is proportional to its current degree.

These methods are fast and interpretable but are limited to capturing only immediate, local topology.

This approach embeds nodes into a low-dimensional latent space where link probability is a function of the distance between node vectors. It models the graph's adjacency matrix as being generated by latent node features.

• Factorization: Decomposes a node-node similarity matrix (e.g., Katz index, Laplacian) into low-rank matrices representing node embeddings.
• Assumption: Nodes that are 'close' in the latent space are likely to be connected.
• Example: The dot product of two node embedding vectors predicts the likelihood of an edge.

While powerful for static graphs, these methods typically lack the ability to incorporate node features or model complex, non-linear relationships directly.

The dominant deep learning approach, where a GNN (e.g., GCN, GAT, GraphSAGE) learns node embeddings by aggregating information from a node's local neighborhood. Link prediction is then performed on the learned embeddings.

• Encoder: A GNN transforms node features and graph structure into dense vector representations.
• Decoder: A simple function (e.g., dot product, MLP) takes the embeddings of two nodes and outputs a link score.
• Training: Models are trained on existing edges (positive examples) and randomly sampled non-edges (negative examples).

This approach excels at leveraging both node attributes and graph structure, leading to state-of-the-art performance on many benchmarks.

These are self-supervised models that learn to reconstruct the graph's adjacency matrix from a compressed latent representation. Link prediction is a direct output of the reconstruction.

• Encoder: Maps the graph to a latent node embedding matrix Z (often using a GNN).
• Decoder: Reconstructs the adjacency matrix from Z, e.g., via sigmoid(Z * Z^T).
• Training: The model is trained to minimize the difference between the original and reconstructed adjacency matrix.

Variants like the Graph Variational Autoencoder (Graph VAE) introduce a probabilistic latent space, enabling the generation of new graph structures and uncertainty estimation for predictions.

Instead of predicting links based on full-graph node embeddings, these methods extract and reason over local subgraphs surrounding the candidate node pair.

• Subgraph Extraction: For nodes u and v, a enclosing subgraph (e.g., k-hop neighbors) is extracted.
• Relational Reasoning: A neural network (often a GNN) processes this subgraph to predict the link, explicitly considering the local relational structure.
• Advantage: Highly inductive and can generalize to unseen graph structures, as predictions are based on local patterns rather than global node IDs.

This approach is particularly effective for inductive link prediction, where the model must make predictions for nodes not seen during training.

These methods specialize in predicting future links in evolving graphs, where the network structure changes over time. They incorporate temporal sequences of graph snapshots.

• Temporal Graph Neural Networks (TGNNs): Models like EvolveGCN or TGN use RNNs or attention mechanisms to update node embeddings over time as new interactions occur.
• Dynamic Representation: Node embeddings are functions of time, capturing how a node's role and connectivity evolve.
• Application: Essential for predicting next interactions in social networks, financial transaction networks, or recommendation systems.

These models move beyond static assumptions, capturing the continuous or discrete-time dynamics that drive link formation.

A Graph Neural Network (GNN) is a class of neural networks designed to operate directly on graph-structured data. It uses a message-passing mechanism where nodes iteratively aggregate feature information from their local neighborhoods to learn powerful node, edge, or graph-level representations. GNNs are the foundational architecture for most modern link prediction models.

• Core Mechanism: Neighbor feature aggregation and update functions.
• Primary Use: Learning embeddings that encode topological and feature information, which are then used for tasks like node classification and link prediction.

Graph embedding is the technique of mapping nodes, edges, or entire graphs to low-dimensional, continuous vector representations (embeddings). These embeddings aim to preserve the structural properties—like connectivity and community membership—of the original graph. For link prediction, node embeddings are often compared (e.g., via dot product) to score the likelihood of a missing edge.

• Key Methods: Include shallow models like Node2Vec and DeepWalk, as well as embeddings learned by GNNs.
• Link Scoring: The similarity (cosine, Euclidean) between two node embeddings is a direct heuristic for link existence.

A generative graph model is a probabilistic or deep learning model designed to learn the underlying distribution of a graph dataset (P(G)). It can then synthesize new, realistic graph instances. Link prediction can be framed as a generative task: predicting the probability of an edge (a micro-generation event) given the observed partial graph.

• Model Families: Include Stochastic Block Models (SBM), Graph Variational Autoencoders (Graph VAE), and Graph Generative Adversarial Networks (GraphGAN).
• Objective: Capture complex dependencies like transitivity (friends of friends are likely friends) and community structure.

Message passing is the fundamental, iterative computational mechanism at the heart of Graph Neural Networks. In each layer, nodes create "messages" (typically a function of their current state) and send them to neighboring nodes. Each node then aggregates incoming messages and updates its own representation. This process allows information to propagate across the graph.

• Role in Link Prediction: Enables nodes to build representations that are informed by multi-hop network context, which is critical for assessing the potential for a connection.
• Aggregation Functions: Common choices include sum, mean, max, or attention-weighted sum.

A Graph Convolutional Network (GCN) is a specific, widely-used type of GNN that performs a localized, spectral-based convolution. It updates a node's feature vector by taking a normalized weighted sum of its own features and the features of its immediate neighbors. The GCN layer provides an efficient and effective baseline for many graph tasks.

• Link Prediction Application: GCNs generate node embeddings that encode local graph structure. A downstream decoder (e.g., a bilinear layer) then operates on pairs of node embeddings to predict link scores.
• Characteristic: Uses a symmetric normalization of the adjacency matrix to stabilize learning.

The Stochastic Block Model (SBM) is a classical generative statistical model for random graphs. It defines a community structure where nodes are partitioned into blocks (communities). The probability of an edge existing between two nodes depends solely on their block memberships. It serves as a fundamental benchmark and theoretical model for link prediction.

• Mechanism: Defined by a block-assignment vector and a matrix of inter-block connection probabilities.
• Use Case: Modeling homophily (nodes in the same block connect more frequently) and providing a simple, interpretable baseline for link likelihood.