Link Prediction

Uses graph structure to score potential links based on node neighborhoods. Common Neighbors counts shared connections, while Jaccard Coefficient normalizes this by total unique neighbors. Adamic-Adar gives more weight to rare shared neighbors, and Preferential Attachment predicts links based on node degree product. These methods are computationally efficient baselines that capture structural proximity without requiring training data.

Transforms graph topology into dense vector representations where proximity correlates with link likelihood. Node2Vec uses biased random walks to capture homophily and structural equivalence. TransE models relationships as translations in vector space, where head + relation ≈ tail. RotatE extends this to complex space to model symmetric relations. These embeddings enable efficient nearest-neighbor search for candidate link generation.

Deep learning models that learn node representations by aggregating features from multi-hop neighborhoods. Graph Convolutional Networks (GCNs) apply spectral convolutions to capture local structure. Graph Attention Networks (GATs) learn to weight neighbor importance dynamically. GraphSAGE enables inductive learning on unseen nodes. These models achieve state-of-the-art performance by combining structural patterns with node attributes for end-to-end link prediction.

Extends static prediction to graphs evolving over time. Discrete-time methods treat the graph as a sequence of snapshots, applying recurrent architectures like LSTMs to capture temporal dependencies. Continuous-time methods model events as point processes, using temporal point processes or time-aware embeddings. This is critical for recommendation systems, financial transaction analysis, and social network evolution modeling.

Critical for training discriminative link prediction models. Uniform random sampling selects non-existent edges randomly but may produce easy negatives. Corrupting positive edges replaces head or tail entities while preserving relation type. Adversarial sampling generates hard negatives that the current model struggles to distinguish. The choice of negative sampling significantly impacts model calibration and ranking metrics like Mean Reciprocal Rank.

Assesses prediction quality using ranking-based metrics. Mean Reciprocal Rank (MRR) averages the reciprocal of the first correct entity's rank. Hits@K measures the fraction of correct predictions appearing in the top-K ranked results. Area Under the ROC Curve (AUC-ROC) evaluates binary classification performance. For knowledge graph completion, filtered settings remove known true triples from ranking to avoid penalizing valid but unobserved facts.

A class of deep learning models designed to perform inference on data described by graph structures. GNNs capture dependencies via message passing between nodes, making them the primary architectural backbone for modern link prediction. Common variants include Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs).

• Encoder-decoder framework: GNNs learn low-dimensional node embeddings that preserve topological proximity.
• Scoring function: A decoder (e.g., DistMult, TransE) computes the likelihood score for a candidate triple (subject, predicate, object).
• Inductive capability: Unlike transductive methods, GNNs can predict links for nodes unseen during training.

The task of automatically adding new facts to a knowledge graph by predicting missing links or attributes based on existing patterns. Link prediction is the primary mechanism for achieving this.

• Closed-world vs. open-world assumption: Under the closed-world assumption, missing facts are considered false; link prediction relaxes this by inferring probable true facts.
• Benchmark datasets: Commonly evaluated on FB15k-237, WN18RR, and YAGO3-10.
• Temporal scoping: Advanced completion tasks predict not just the existence of a link but its validity interval over time.

A dimensionality reduction technique that maps nodes, edges, or entire subgraphs into a low-dimensional vector space while preserving the graph's topological structure. These embeddings serve as the feature input for link prediction classifiers.

• Random walk methods: Algorithms like Node2Vec and DeepWalk generate sequences to capture local neighborhood structure.
• Translational distance models: TransE models relationships as translations in the embedding space (h + r ≈ t).
• Semantic matching models: RESCAL and ComplEx use tensor factorization to capture complex interaction patterns between entities.

The computational process of identifying and merging disparate records that refer to the same real-world entity across different data sources. Link prediction and entity resolution are complementary: resolution cleans the graph, while prediction enriches it.

• Blocking: Efficiently groups candidate record pairs using techniques like Locality-Sensitive Hashing (LSH) to avoid O(n²) comparisons.
• Fuzzy matching: String similarity metrics (Levenshtein, Jaro-Winkler) combined with contextual embeddings resolve lexical variations.
• Canonicalization: Assigns a unique, persistent identifier to each resolved entity, creating the golden record.

A software component that derives new logical facts from an existing knowledge base by applying a set of predefined ontological rules. Unlike statistical link prediction, inference engines use deductive reasoning.

• Forward chaining: Starts from known facts and applies rules to derive new conclusions iteratively.
• Backward chaining: Starts from a goal or query and works backward to determine if existing facts support it.
• Materialization: The process of pre-computing and storing all inferred triples to accelerate query-time performance. Often used alongside learned link predictors for hybrid symbolic-neural systems.

A W3C standard language for validating RDF graphs against a set of conditions. SHACL ensures that predicted links conform to the structural and semantic rules of the domain before they are committed to the knowledge graph.

• Shape definitions: Specify constraints on node types, property cardinalities, and value ranges.
• Closed shape validation: Rejects predicted links that violate domain integrity, acting as a post-prediction safety filter.
• SHACL-AF (Advanced Features): Supports SPARQL-based constraint components for complex validation logic beyond simple shapes.