Link Prediction

Link prediction algorithms output a probability score between 0 and 1 for each candidate node pair, quantifying the confidence that a relationship should exist. These scores are derived from node embeddings that capture structural proximity and attribute similarity. In fraud graphs, a high-probability link between a synthetic identity and a known fraudulent account serves as a strong signal for investigation. Common scoring functions include dot product, cosine similarity, and neural tensor networks that learn complex interaction patterns between node representations.

Traditional link prediction relies on local neighborhood heuristics that measure node proximity without training:

• Common Neighbors: Counts shared connections between two nodes; a high count suggests a likely link
• Jaccard Coefficient: Normalizes common neighbors by total unique neighbors, penalizing high-degree nodes
• Adamic-Adar Index: Weighs common neighbors inversely by their degree, giving more weight to rare shared connections
• Preferential Attachment: Multiplies node degrees, predicting links to high-degree hubs These heuristics serve as baselines and feature inputs for learned models.

Modern link prediction uses node embedding techniques that map graph nodes into dense, low-dimensional vector spaces where geometric proximity encodes topological similarity. Node2Vec generates embeddings through biased random walks that balance breadth-first and depth-first exploration. GraphSAGE learns inductive embeddings by sampling and aggregating features from local neighborhoods, enabling predictions on unseen nodes. Graph Convolutional Networks (GCNs) propagate information across edges, learning representations that capture multi-hop dependencies critical for detecting synthetic identity rings.

Training link prediction models requires both positive edges (observed connections) and negative edges (absent connections). Negative sampling strategies directly impact model quality:

• Uniform Random Sampling: Selects random non-edges, but may produce easy negatives that don't improve discrimination
• Hard Negative Mining: Selects non-edges between nodes that share many common neighbors, forcing the model to learn subtle distinctions
• Adversarial Sampling: Dynamically generates negatives that the current model misclassifies, improving robustness In fraud graphs, careful negative sampling prevents the model from learning trivial separations.

In dynamic financial graphs, temporal link prediction forecasts future connections based on historical snapshots. This is critical for anticipating synthetic identity expansion before fraudulent transactions occur. Techniques include:

• Temporal Graph Networks (TGNs): Maintain memory states for nodes that update as new interactions occur
• EvolveGCN: Uses a recurrent neural network to evolve GCN parameters over time, adapting to changing graph dynamics
• Hawkes Processes: Model the self-exciting nature of fraudulent activity where one synthetic identity creation increases the probability of subsequent creations

Link prediction in fraud graphs faces extreme class imbalance where true connections among millions of possible edges are rare. Standard accuracy is misleading. Key metrics include:

• Mean Reciprocal Rank (MRR): Measures how highly the correct edge ranks among candidates
• Hits@K: The fraction of true edges appearing in the top-K predictions; Hits@10 and Hits@100 are common thresholds
• Area Under the Precision-Recall Curve (AUPRC): More informative than ROC-AUC for highly imbalanced edge prediction tasks
• Precision@K: The proportion of top-K predicted edges that are actual fraud connections