Link Prediction

These are simple, computationally efficient metrics that predict a link based on the immediate local structure around two nodes. They operate under the principle that nodes with many common neighbors are more likely to connect.

• Common Neighbors: Counts the number of nodes adjacent to both target nodes.
• Jaccard Coefficient: Normalizes the common neighbor count by the total union of neighbors.
• Adamic-Adar: Weighs common neighbors inversely by their degree, giving more importance to connections through rare neighbors.
• Preferential Attachment: Assumes the probability of a new link is proportional to the product of the degrees of the two nodes, modeling 'rich-get-richer' dynamics.

These methods are foundational but limited to capturing only first or second-order proximity.

These algorithms consider the entire graph topology, using paths of all lengths between nodes to infer connection likelihood. They capture higher-order structural dependencies.

• Katz Index: Sums over all paths between two nodes, damping longer paths exponentially. It's calculated via a power series of the adjacency matrix.
• Rooted PageRank: Simulates a random walk starting from one node and measures the steady-state probability of landing on the other, indicating structural proximity.
• SimRank: A recursive measure based on the principle that two nodes are similar if they are connected to similar neighbors.

While more expressive, these methods can be computationally intensive for large graphs due to matrix operations or iterative computations.

This approach learns low-dimensional latent representations (embeddings) for nodes such that the dot product of two node vectors predicts the likelihood of a link. It decomposes a matrix derived from the graph (e.g., adjacency matrix, Katz index).

• Singular Value Decomposition (SVD): Directly factorizes a graph matrix.
• Non-negative Matrix Factorization (NMF): Constrains factors to be non-negative, often leading to more interpretable embeddings.
• The core idea is to project nodes into a continuous vector space where geometric proximity (e.g., cosine similarity) indicates link probability. This technique directly enables downstream machine learning but requires retraining for graph updates.

GNNs are deep learning models that learn node representations by recursively aggregating and transforming feature information from a node's local graph neighborhood. These learned embeddings are then used for link prediction via a decoder (e.g., a dot product or MLP).

• Graph Convolutional Networks (GCNs): Perform a localized spectral convolution to aggregate neighbor features.
• GraphSAGE: Learns an aggregator function (mean, LSTM, pool) to generate embeddings inductively, generalizing to unseen nodes.
• Graph Attention Networks (GATs): Use attention mechanisms to weigh the importance of neighboring nodes during aggregation.

GNNs excel at leveraging both node attributes and graph structure, achieving state-of-the-art performance on many benchmarks.

This classic approach formulates link prediction as a binary classification task. A model is trained on pairs of nodes, using features engineered from the graph.

Feature Categories:

• Topological Features: Local heuristics (Common Neighbors), node degrees, clustering coefficients.
• Embedding-Based Features: Node vectors from DeepWalk, node2vec, or other shallow embedding techniques.
• Node Attribute Features: Intrinsic properties of the nodes themselves.

Algorithms like Random Forests, Gradient Boosting (XGBoost), or Logistic Regression are then trained on these feature vectors for node pairs. This method offers high interpretability and can combine diverse feature sources.

These algorithms specialize in predicting future links in evolving networks by explicitly modeling the temporal dynamics of graph changes.

• CTDNE (Continuous-Time Dynamic Network Embeddings): Learns time-respecting embeddings by sampling temporal random walks.
• JODIE: A recurrent deep model that projects user and item trajectories into a latent space that evolves over time.
• DyRep: A framework that models network evolution as two interrelated processes: communication (frequent) and association (infrequent).

These models are essential for real-world applications like social network growth, recommendation systems, and fraud detection, where the timing and sequence of interactions are critical signals.

A Graph Neural Network (GNN) is a class of deep learning models designed to perform inference on graph-structured data. They are the primary architecture for modern link prediction. GNNs operate by iteratively aggregating and transforming feature information from a node's local neighborhood, learning powerful node embeddings that encode both attributes and graph structure. These embeddings can then be used to score potential edges.

• Key Mechanism: Message passing between connected nodes.
• For Link Prediction: A decoder function (e.g., a dot product) computes a likelihood score for an edge between two nodes based on their GNN-generated embeddings.

Graph embedding is a technique that maps nodes, edges, or entire subgraphs to low-dimensional vector representations. The goal is to preserve the graph's structural properties (like connectivity and neighborhood) in a continuous vector space. These embeddings serve as compact, numerical features for downstream machine learning tasks.

• Link Prediction Use Case: Methods like Node2Vec or TransE learn embeddings such that nodes likely to be connected have similar or predictably related vectors. The probability of a link is often calculated as a function of the distance between two node embeddings.

A heterogeneous graph contains multiple types of nodes (entities) and/or multiple types of edges (relationships). This structure is common in enterprise knowledge graphs (e.g., Customer-PURCHASED->Product-SUPPLIED_BY->Vendor). Link prediction in such graphs is more complex and informative.

• Challenge: Must account for different semantic meanings of connections.
• Solution: Models like Heterogeneous Graph Neural Networks (HetGNN) or Meta-path based approaches are used to predict specific types of missing links (e.g., will this Researcher co-author a paper with that Researcher?).

Knowledge Graph Completion (KGC) is a specific application of link prediction focused on inferring missing facts in a knowledge graph. The graph is typically represented as a set of triples (head, relation, tail), and the task is to predict missing heads or tails for a given relation.

• Core Methods: Use latent factor models like RESCAL, ComplEx, or RotatE. These models learn embeddings for entities and relations that satisfy logical patterns (symmetry, inversion, composition).
• Business Impact: Directly increases the completeness and utility of an enterprise knowledge graph by suggesting new worksFor or manufactures relationships.

Graph-based feature engineering is the process of creating predictive features for machine learning models by extracting structural information from a graph. For traditional ML approaches to link prediction, these hand-crafted features are crucial.

• Common Features for Link Prediction:
  • Node-level: Degree centrality, clustering coefficient.
  • Pair-wise: Shortest path length, common neighbors (Jaccard index), Adamic-Adar index, preferential attachment score.
• Application: These calculated metrics can be used as input features to a classifier (e.g., Logistic Regression, XGBoost) to predict the existence of a link.

An adjacency matrix is a fundamental square matrix representation of a graph. For a graph with n nodes, it is an n x n matrix where the element A[i][j] indicates the presence (or weight) of an edge from node i to node j.

• Role in Link Prediction: It is the primary mathematical object that many algorithms operate on. Matrix factorization techniques for link prediction, such as Singular Value Decomposition (SVD), decompose the adjacency matrix (or a derived matrix) to learn low-rank node embeddings. A predicted adjacency matrix A' contains the likelihood scores for all possible node pairs.