Link Prediction

Classical approaches compute a similarity score between node pairs based on graph topology. These methods serve as strong baselines and are computationally efficient.

• Common Neighbors: Counts shared neighbors; more shared connections imply a higher likelihood of a link.
• Jaccard Coefficient: Normalizes common neighbors by the total number of unique neighbors, reducing bias toward high-degree nodes.
• Adamic-Adar Index: Weighs common neighbors inversely by their degree, giving more importance to rare shared connections.
• Preferential Attachment: Predicts links based on the product of node degrees, capturing the 'rich-get-richer' phenomenon in network growth.

Nodes are mapped to a low-dimensional vector space where geometric proximity encodes structural similarity. A link is predicted if the combined embeddings of two nodes score above a threshold.

• Node2vec: Uses biased random walks to generate embeddings that balance homophily and structural equivalence.
• Matrix Factorization: Factorizes the adjacency matrix directly to learn latent features for each node.
• Scoring Functions: A binary operator (e.g., dot product, cosine similarity, or a learned neural network layer) is applied to the node pair's embeddings to produce a link probability.

GNNs generate node representations by aggregating features from local neighborhoods, capturing complex, non-linear dependencies that heuristic methods miss.

• Graph Convolutional Network (GCN): Aggregates neighbor features using a normalized mean, producing smooth representations suitable for homophilous graphs.
• Graph Attention Network (GAT): Uses self-attention to learn dynamic importance weights for different neighbors, allowing the model to focus on the most relevant connections.
• GraphSAGE: An inductive framework that samples and aggregates features from a fixed-size neighborhood, enabling generalization to entirely new nodes not seen during training.

Instead of learning isolated node embeddings, these methods extract the local subgraph surrounding a target node pair and classify the subgraph directly.

• SEAL Framework: Extracts an enclosing subgraph around the two nodes, labels nodes by their distance to the target pair, and feeds the subgraph into a GNN for binary classification.
• Labeling Trick: The distance-based node labeling (Double Radius Node Labeling) is critical; it injects structural information that allows the GNN to distinguish the target nodes from the rest of the subgraph.
• Advantage: Captures the rich relational patterns of the local topology, often outperforming node-embedding methods on complex relational data.

Link prediction is framed as a binary classification task, requiring both positive (existing) and negative (non-existing) edges for training. The strategy for selecting negative samples critically impacts model performance.

• Uniform Random Sampling: Randomly selects non-existent edges, but often creates easy negatives that don't challenge the model.
• Hard Negative Mining: Selects non-edges that are difficult to distinguish from true edges (e.g., nodes sharing many neighbors but no direct link), forcing the model to learn finer-grained distinctions.
• Adversarial Sampling: Dynamically generates negatives that the current model is most likely to misclassify, improving robustness.

Model performance is measured by its ability to rank true missing links above false ones on a held-out test set of edges.

• Area Under the ROC Curve (AUC-ROC): Measures the probability that a randomly chosen positive edge is ranked higher than a randomly chosen negative edge.
• Mean Reciprocal Rank (MRR): Computes the average of the reciprocal ranks of the first correct prediction across all queries, emphasizing top-ranked results.
• Hits@K: The fraction of test edges that appear in the top K positions of the ranked prediction list (e.g., Hits@10, Hits@100).

Predicts potential new supplier relationships by scoring the likelihood of a connection forming between a buyer and an unknown manufacturer. Graph Neural Networks analyze structural similarity—if Company A and Company B share the same tier-2 suppliers, materials, and logistics nodes, a missing edge between them is flagged. This enables procurement teams to identify alternative sources for critical components without relying solely on manual market research. The model ingests heterogeneous graphs containing financial health, geographic location, and material specialization to rank candidates by compatibility score.

Reveals n-tier concentration risk by inferring undisclosed connections deep in the supply network. A manufacturer may report a diversified supplier base, but link prediction on a Bill of Materials (BOM) Graph can expose that multiple tier-1 suppliers all source a specific semiconductor from the same tier-3 foundry. This single point of failure remains invisible to traditional risk audits. The technique applies Relational Graph Convolutional Networks (R-GCNs) across heterogeneous nodes—parts, facilities, and sub-assemblies—to predict missing 'supplies' edges that represent latent dependencies.

Anticipates how a localized failure propagates by predicting new edges that will form under stress. When a port closes, link prediction models forecast which alternative logistics nodes will connect to affected distribution centers based on dynamic graph snapshots. The system learns from historical disruption patterns—hurricanes, labor strikes, sanctions—to score the probability of temporary edges forming between shippers and emergency warehouses. This moves the control tower from reactive monitoring to prescriptive re-routing before bottlenecks materialize.

Identifies shell companies and collusive networks by predicting edges that should not exist but do. A legitimate supply chain exhibits predictable graph homophily—suppliers connect to buyers with matching scale, geography, and compliance profiles. When a small, newly registered entity forms a high-value edge with a major buyer, the model flags the anomaly. Link prediction scores the edge probability; a low predicted probability coupled with a high transaction volume triggers an investigation into procurement fraud or sanction evasion.

Predicts future mergers, acquisitions, or joint ventures by analyzing the evolving topology of the supply network. When two organizations begin sharing the same niche logistics providers, patent classifications, or rare material suppliers, a Graph Attention Network (GAT) assigns increasing weight to these overlapping neighbors. The model predicts a high probability of a future 'partnership' or 'merger' edge, providing competitive intelligence. This application uses inductive learning to generalize to companies not seen during training.

Validates the completeness of temperature-controlled logistics networks by predicting missing monitoring handoff points. A pharmaceutical shipment must pass through certified cold chain nodes with unbroken IoT telemetry. Link prediction models trained on compliant shipment graphs identify gaps where a predicted 'monitored-by' edge is absent, indicating a segment where temperature logging failed or was tampered with. This automates quality assurance by flagging graph structural anomalies that correlate with spoilage risk.

The core mechanism enabling link prediction in Graph Neural Networks. Nodes iteratively aggregate feature information from their local neighbors to update their own hidden state.

• Aggregation: Collects vector representations from adjacent nodes
• Update: Combines aggregated neighbor data with the node's own features
• Readout: After k iterations, a node's embedding captures structural information from its k-hop neighborhood

This process allows the model to learn rich node representations that encode both local topology and feature similarity, which are essential for scoring potential links.

A low-dimensional, dense vector representation of a node that encodes its structural position and feature information in a continuous latent space.

• Proximity Preservation: Nodes that are close in the graph should have similar embeddings
• Structural Equivalence: Nodes with similar local roles (e.g., hubs) should map to similar regions
• Downstream Utility: Embeddings serve as input to a link prediction classifier, where the similarity between two node vectors (e.g., via dot product or cosine similarity) directly scores the likelihood of a connection

Techniques like Node2Vec and GraphSAGE are foundational for generating these representations.

An unsupervised learning framework specifically designed for link prediction. The model consists of two components:

• Encoder: A Graph Convolutional Network (GCN) that generates latent node embeddings Z from the input graph's features and structure
• Decoder: A pairwise scoring function, typically the inner product σ(z_i^T z_j), that reconstructs the adjacency matrix, predicting the probability of a link between nodes i and j

GAEs are trained to minimize the reconstruction error on known edges, making them highly effective for tasks where the goal is to recover missing connections.

A paradigm that jointly learns an optimal graph topology and node representations when the underlying graph is noisy, incomplete, or entirely absent.

• Latent Graph Inference: The model learns a probabilistic adjacency matrix simultaneously with node embeddings
• Denoising: Filters out spurious or irrelevant edges that degrade link prediction accuracy
• Iterative Refinement: The learned structure improves embeddings, which in turn refine the structure

This is critical in supply chains where the documented Bill of Materials (BOM) Graph may be outdated or missing critical dependencies.

A GNN variant that employs self-attention mechanisms to assign different importance weights to neighboring nodes during feature aggregation.

• Implicit Weighting: Instead of treating all neighbors equally, GAT learns to focus on the most relevant connections
• Multi-Head Attention: Stabilizes learning by running multiple attention mechanisms in parallel
• Link Prediction Benefit: Produces more nuanced node embeddings where the influence of strong, predictive neighbors is amplified, leading to higher accuracy when scoring candidate edges in heterogeneous supply chain networks

A self-supervised learning paradigm that learns node representations by maximizing agreement between differently augmented views of the same graph.

• Augmentation: Generates new views via edge dropping, node feature masking, or subgraph sampling
• Contrastive Objective: Pulls embeddings of the same node in different views together while pushing apart embeddings of different nodes
• Label-Free Pretraining: Learns robust structural representations without requiring labeled links, enabling strong link prediction performance even when ground-truth edges are scarce