Link Prediction

Classic methods score node pairs based on structural proximity without requiring training. These include:

• Common Neighbors: Counts shared adjacent nodes; more intersections suggest a higher link probability.
• Jaccard Coefficient: Normalizes common neighbors by total unique neighbors, penalizing high-degree hubs.
• Adamic-Adar Index: Weighs common neighbors inversely by their degree, prioritizing rare shared connections.
• Preferential Attachment: Scores pairs by the product of their degrees, capturing the 'rich-get-richer' phenomenon in scale-free networks. These heuristics provide a fast, interpretable baseline but fail to capture complex, non-linear relational patterns.

These techniques learn a low-dimensional vector representation for each node, where geometric proximity encodes structural similarity. Key approaches include:

• Matrix Factorization: Decomposes the adjacency matrix (e.g., using SVD) to generate embeddings that reconstruct the original graph structure.
• Random Walk Models (e.g., Node2Vec): Generate node sequences via biased random walks and apply a skip-gram model to map nodes that share similar contexts to nearby vectors.
• Translational Distance Models (e.g., TransE): Model relationships as translations in the embedding space; for a triple (h, r, t), the model learns h + r ≈ t. The score for a candidate link is the distance between the translated head and the tail.

GNNs represent the state-of-the-art by learning node embeddings through iterative neighborhood aggregation. A typical architecture uses:

• Message Passing: Each node receives feature information from its neighbors, transforms it, and aggregates it to update its own state.
• Graph Convolutional Networks (GCNs): Apply a first-order approximation of spectral convolutions, effectively averaging neighbor features.
• Graph Attention Networks (GATs): Introduce a self-attention mechanism to weigh the importance of different neighbors during aggregation.
• Decoder Function: After encoding, a decoder (e.g., a dot product or a DistMult bilinear model) computes a probability score for the candidate link between the final node embeddings.

A powerful technique for link prediction involves extracting the local subgraph surrounding the target node pair. The subgraph, typically containing nodes within a k-hop radius of both endpoints, is fed into a GNN for binary classification. This approach, known as SEAL (Subgraphs, Embeddings, and Attributes for Link prediction), explicitly learns structural heuristics like common neighbors as a function of the subgraph pattern. The enclosing subgraph captures the 'gamma' shape of the local topology, allowing the model to generalize across different graph regions and learn complex, non-linear heuristics that outperform predefined topological scores.

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 node pairs without an edge. Simple but often generates easy negatives that don't challenge the model.
• Corrupted Tail Sampling: Replaces the tail entity of a true triple with a random entity, common in knowledge graph embedding training.
• Hard Negative Mining: Actively selects negative edges that are difficult to distinguish from positives (e.g., nodes sharing many neighbors but lacking a direct link), forcing the model to learn finer-grained decision boundaries.

In dynamic graphs where edges are timestamped, the task extends to predicting future interactions. This requires modeling the temporal evolution of the graph structure:

• Snapshot-Based Methods: Train on a sequence of static graph snapshots to predict edges in the next time step.
• Continuous-Time Dynamic Graphs (CTDGs): Represent the graph as a stream of timestamped events. Models like TGN (Temporal Graph Networks) maintain a compressed memory state for each node that is updated upon each interaction, enabling predictions at any point in continuous time.
• Hawkes Processes: Model the intensity of future events as a function of past events, capturing self-exciting and mutual-exciting dynamics between node pairs.

The pipeline process of ingesting raw structured or unstructured data, transforming it into a graph-compatible format, and loading it into a graph database. The quality of link prediction models depends directly on the completeness and accuracy of the underlying graph constructed during ETL.

• Entity resolution deduplicates and links co-referring entities across documents
• Relation extraction identifies typed connections between entities from natural language text
• Incremental loading updates the graph with new documents without full reconstruction

A robust legal graph ETL pipeline ensures that link prediction models have access to a comprehensive, clean graph with accurate node attributes and verified edge types before training begins.