Link Prediction

Classic approaches compute a similarity score between node pairs based on graph topology without learning. These methods serve as strong baselines.

• Common Neighbors: Counts shared neighbors between two nodes. A higher count suggests a higher probability of connection.
• Jaccard Coefficient: Normalizes common neighbors by the total number of unique neighbors, penalizing nodes with high degrees.
• Adamic-Adar Index: Weighs common neighbors inversely by their degree, giving more importance to rare shared connections.
• Preferential Attachment: Multiplies the degrees of the two nodes, based on the principle that popular nodes tend to connect to other popular nodes.

These models learn low-dimensional vector representations for entities and relations to score triples. They frame link prediction as a translation or tensor factorization problem.

• TransE: Models a relationship as a translation vector h + r ≈ t in the embedding space. It is highly efficient but struggles with complex relation patterns like symmetry.
• DistMult: Uses a bilinear diagonal tensor product. It captures symmetric relations well but cannot model asymmetric or inverse relations.
• ComplEx: Extends DistMult into the complex space, allowing it to model both symmetric and asymmetric relations by using the Hermitian dot product.
• RotatE: Defines each relation as a rotation in complex vector space, effectively modeling inversion and composition patterns.

Instead of learning shallow embeddings, Graph Neural Networks (GNNs) generate node representations by aggregating information from a node's local neighborhood. This captures structural features that shallow methods miss.

• Graph Convolutional Networks (GCNs) apply a first-order approximation of spectral convolutions to aggregate neighbor features.
• GraphSAGE learns a function to sample and aggregate features from a node's local neighborhood, enabling inductive learning on unseen nodes.
• Graph Attention Networks (GATs) use a self-attention mechanism to assign different weights to different neighbors during aggregation, focusing on the most relevant connections.
• A standard GNN encoder for link prediction often uses a Siamese architecture to encode the head and tail nodes separately before scoring the pair.

Link prediction is often framed as a binary classification task. Since real graphs are sparse, generating high-quality negative samples (non-existent edges) is critical for training.

• Uniform Random Sampling: Randomly corrupts the head or tail entity of a true triple. This is fast but often generates easy negatives that don't help the model learn.
• Bernoulli Sampling: Replaces the head or tail entity with a probability based on the relation's mapping property (one-to-many, many-to-one) to reduce false negatives.
• Adversarial Sampling: Dynamically selects negative samples that the current model scores highly, forcing the model to learn from its hardest mistakes.
• Self-Adversarial Sampling: Weighs negative samples by their current model score during the loss calculation, avoiding the computational cost of full adversarial generation.

After encoding the source and target nodes, a decoder function computes the final likelihood score for the potential edge.

• Dot Product: Computes the inner product of the two node embeddings. Simple but effective for undirected graphs.
• DistMult Decoder: A bilinear diagonal product <h, r, t>, where r is a relation-specific diagonal matrix.
• ConvE: Uses a 2D convolutional layer over reshaped and concatenated embeddings, capturing rich feature interactions.
• InteractE: Improves upon ConvE by increasing the number of feature permutations and reshapes, capturing more heterogeneous interactions.

The performance of link prediction models is evaluated by ranking a true target entity against all other possible entities in the graph.

• Mean Reciprocal Rank (MRR): The average of the inverse of the rank assigned to the correct entity. It heavily penalizes low ranks.
• Hits@K (e.g., Hits@10): The fraction of test triples where the correct entity appears in the top K positions of the ranked list. This is the most common metric for knowledge base completion.
• Mean Rank (MR): The average rank of the correct entity. A lower value is better, but it is highly sensitive to outliers from a few very bad predictions.
• Evaluation is performed under a filtered setting, where all other known true triples are removed from the ranking list before calculating the rank to avoid penalizing the model for predicting other valid facts.

The overarching task of inferring missing facts in a knowledge graph, often formulated as a link prediction problem. KBC systems predict whether a missing edge should exist between two existing nodes.

• Goal: Transform an incomplete graph into a denser, more useful one
• Common approach: Score all possible missing triples and select the highest-ranked ones
• Example: Predicting a person's nationality when the graph already contains their birthplace and employer

A foundational knowledge graph embedding model that represents relationships as translation vectors in a low-dimensional space. For a true triple (h, r, t), the embedding of the head entity plus the relation should approximately equal the embedding of the tail entity: h + r ≈ t.

• Scoring function: Negative L1 or L2 distance between h + r and t
• Strength: Simple, computationally efficient, and highly interpretable
• Limitation: Struggles with complex relation patterns like 1-to-N, N-to-1, and symmetric relations

The application of graph neural networks to relation extraction, modeling entities and their surrounding context as a graph structure. GNNs capture inter-entity dependencies that sequential models miss.

• Architecture: Entities become nodes; syntactic dependencies become edges
• Key advantage: Message passing allows information to flow between related entity pairs
• Common variants: GCN, GAT, and R-GCN for multi-relational graphs
• Use case: Document-level RE where entities span multiple sentences

A low-dimensional vector representation of a semantic relationship, learned to capture its properties for downstream tasks like link prediction. Relation embeddings encode the latent semantics of how two entities connect.

• Properties captured: Transitivity, symmetry, compositionality
• Training: Often learned jointly with entity embeddings via contrastive objectives
• Example: The embedding for 'employed_by' should be close to the composition of 'works_at' and 'owned_by'
• Output: Used directly in scoring functions for triple plausibility

A binary classification task that determines whether a given subject-predicate-object triple represents a true fact. Unlike ranking-based link prediction, triple classification provides a definitive yes/no decision.

• Input: A complete (head, relation, tail) triple
• Output: A confidence score thresholded to produce a binary label
• Evaluation metric: Accuracy, precision, recall, and F1 score
• Challenge: Requires both positive and high-quality negative examples for training

A modeling paradigm that simultaneously identifies entities and their relationships in a single step rather than as a pipeline. This approach prevents error propagation where entity recognition mistakes cascade into relation extraction failures.

• Pipeline problem: If an entity is missed, its relationships are automatically lost
• Joint approach: Shared representations allow entity and relation signals to reinforce each other
• Architecture: Often uses span-based models or table-filling methods
• Benefit: Stronger performance on overlapping and nested entity-relation structures