Knowledge graphs

An RDF triple consists of Subject, Predicate, and Object. The Subject may be an IRI or blank node; the Predicate must be an IRI; the Object may be an IRI, blank node, or literal. Together, a triple encodes a directed, labeled edge in a knowledge graph — the fundamental unit of fact representation in the Semantic Web.

SPARQL uses triple patterns with '?' prefixed variables. The keyword 'a' is shorthand for rdf:type, and a semicolon chains multiple predicates on the same subject. The result is a table of ?person (IRI) and ?name (literal) pairs. Prefixes must be declared or the full IRI used inline.

PREFIX schema: <https://schema.org/>
SELECT ?person ?name
WHERE {
  ?person a schema:Person ;
          schema:name ?name .
}

TransE models a relation r as a translation in embedding space: for a valid triple (h, r, t), it optimizes h + r ≈ t using margin-based loss. Its primary limitation is handling 1-to-N, N-to-1, and N-to-N relations — a single embedding for the tail entity t cannot simultaneously satisfy all head entities mapped to the same tail, causing those embeddings to collapse together.

DistMult uses real-valued bilinear scoring h⊤ diag(r) t, which is symmetric by construction (score(h,r,t) == score(t,r,h)) and therefore cannot distinguish asymmetric or anti-symmetric relations such as 'parentOf'. ComplEx lifts all embeddings to complex-valued vectors and scores triples as Re(h⊤ diag(r) t̄), where the conjugate breaks symmetry while keeping the model bilinear and efficient — enabling accurate modeling of asymmetric and anti-symmetric relations on benchmarks like FB15k-237.

MRR = (1/|Q|) Σ 1/rank_i, where rank_i is the position of the correct answer among all candidate entities for query i; Hits@K is the fraction of queries where the correct answer appears in the top K positions. Both are computed under the 'filtered' setting: before ranking, all other known correct completions (from train/validation/test sets) are removed from the candidate list to avoid artificially penalizing correct answers that happen to rank above the test triple.

Under CWA (used in relational databases), any fact not explicitly asserted is assumed false. Under OWA, absence of a fact means it is simply unknown — the knowledge base may be incomplete. OWL and most KG systems (Wikidata, DBpedia) adopt OWA, meaning a missing triple is not treated as evidence of falsity, which directly impacts how negation and missing data are handled during reasoning.

In a Labeled Property Graph (e.g., Neo4j), both nodes and relationships carry arbitrary key-value properties directly as first-class citizens, making operational queries natural. In RDF, every piece of information must be encoded as a triple; attaching metadata to an edge (e.g., a confidence score on a relation) requires reification — creating an additional node to represent the edge and adding extra triples — which significantly increases triple count and query complexity.

R-GCN assigns a separate weight matrix W_r per relation type r so aggregation for node v is h_v^(l+1) = σ(Σ_r Σ_{u∈N_r(v)} (1/c_{r,v}) W_r^(l) h_u^(l) + W_0^(l) h_v^(l)). With many relations (e.g., 237 in FB15k-237), the number of parameters grows prohibitively. R-GCN addresses this with basis decomposition — expressing each W_r as a linear combination of B shared basis matrices — reducing parameters from O(|R|·d²) to O(B·d²).

from torch_geometric.nn import RGCNConv
# num_relations=237 for FB15k-237; basis decomposition via num_bases
conv = RGCNConv(in_channels=64, out_channels=64,
                num_relations=237, num_bases=30)
# edge_type: int tensor assigning a relation id to each edge
out = conv(x, edge_index, edge_type)

RotatE embeds entities in complex vector space and models each relation as element-wise rotation: t = h ∘ r where |r_i| = 1. The rotation formulation provably captures: (1) symmetry (r² = identity ↔ r_i = ±1), (2) anti-symmetry (r ≠ r⁻¹), (3) inversion (r₁ = r₂⁻¹), and (4) composition (r₃ = r₁ ∘ r₂). RotatE outperforms TransE and DistMult on FB15k-237 and WN18RR without requiring multiple relation-specific weight matrices.

Equivalent classes share exactly the same extension, so the reasoner infers every individual of class A is also an individual of class B (and vice versa) through ABox completion. If additional cardinality or uniqueness constraints (owl:hasValue, owl:maxCardinality 1) further identify individuals, the reasoner may additionally infer owl:sameAs between distinct-named individuals that must occupy the same role — a phenomenon called individual merging under the Unique Name Assumption's absence.

The Fellegi-Sunter model classifies record pairs as match/non-match using likelihood ratios over field-level agreement patterns. It estimates m-probabilities (probability of agreement given a true match) and u-probabilities (agreement by chance) for each attribute, then computes a composite log-odds score. In KG entity resolution, attribute similarity (name, birthdate) and structural similarity (shared relation neighbors) form agreement vectors; modern implementations replace manual probability calibration with supervised classifiers (XGBoost, BERT-based) trained on labeled entity pairs.

SHACL (Shapes Constraint Language, W3C 2017) defines structural constraints over RDF graphs and validates that instance data conforms to them — for example, 'every Person must have exactly one birthDate typed as xsd:date'. OWL operates under the Open World Assumption and infers new facts but never raises errors for missing or ill-typed data. SHACL provides closed-world data quality enforcement for specific node shapes, acting as the 'schema enforcement' layer of the Semantic Web stack.

Temporal KGs annotate triples with validity timestamps or intervals — e.g., (Obama, presidentOf, USA, [2009, 2017]) — making facts time-dependent. Embedding models must learn time-conditioned representations: TNTComplEx tensorizes time as an additional mode of a Tucker decomposition; DE-SimplE injects a time-dependent perturbation into entity embeddings; ATISE represents time points as Gaussians. Evaluation also changes: link prediction is performed conditioned on a specific timestamp, requiring temporal filtering of candidates.

Neural LP (Yang et al., 2017) learns differentiable weights for Horn rules (e.g., uncle(X,Z) ← brother(X,Y) ∧ parent(Y,Z)) by operating on relation adjacency matrices and differentiating through chain-of-matrix-products. DRUM (Shi & Weninger, 2019) extends this with bidirectional RNNs to jointly predict rule body relations and confidences without explicitly enumerating all path lengths. Unlike embedding models (TransE, DistMult) that score individual (h,r,t) triples, these rule-learning methods produce interpretable reasoning chains and generalize inductively to unseen entities because rules reference relation types, not entity embeddings.

Pure dense RAG retrieves text chunks by semantic similarity but misses precise multi-hop relational facts (e.g., 'Who owns the company that acquired X?') because vector similarity cannot traverse relation chains. KG-augmented RAG traverses entity-relation paths to gather structured, citable facts with explicit intermediate steps. Microsoft GraphRAG additionally builds a community hierarchy over the extracted KG, enabling both local entity-focused queries and global summarization queries over entire communities — substantially improving recall for questions spanning the full document collection.

In the transductive setting, all entities are present during training and each has a dedicated learned embedding (TransE, DistMult, RotatE); these models cannot score new entities at test time. In the inductive setting, entities unseen during training must be handled. GraIL encodes entities via local subgraph structure; NodePiece tokenizes entities as sets of anchor-node distances plus relation types; ULTRA learns a universal graph model using relation-relative representations, achieving zero-shot transfer across entirely different KGs.

Semantic Parsing (SP) translates the question into a formal query (SPARQL, λ-DCS, S-expression) executed against the KG — high precision and interpretability, but brittle to paraphrase variation and complex compositional structures. Embedding-based QA (EmbQA) encodes questions and entities/relations into a shared space and ranks candidates by similarity — flexible and robust to surface variation, but less interpretable and prone to errors on multi-hop constraints. Modern LLM-based systems generate SPARQL via chain-of-thought prompting or iteratively call KG APIs, combining strengths of both paradigms.

KGAT computes relation-aware attention for each neighbor (h, r, t): α(h,r,t) = softmax over a learned scoring function — typically tanh applied to a linear combination of the concatenated head, relation, and tail embeddings — so the model assigns higher weight to semantically relevant relational contexts. It is primarily evaluated on collaborative filtering for recommendation: the user-item interaction graph is enriched with a product KG (item-brand, item-category relations), and KGAT propagates multi-hop entity information to improve top-N recommendation over baselines like BPR-MF.

The SERVICE keyword delegates a graph pattern sub-query to a remote SPARQL endpoint, enabling a single query to join data from multiple distributed triple stores. Performance challenges include: (1) poor cardinality estimation leading to suboptimal join ordering, (2) network round-trip latency per remote call, (3) large intermediate result transfer between endpoints, and (4) remote endpoint timeout and availability. Mitigation strategies include bind-join (sending bound variable values to restrict remote result sets) and adaptive query planning that re-orders joins at runtime based on observed cardinalities.

Wikidata stores each claim as a Statement rather than a bare triple; each Statement can carry (a) Qualifiers — key-value pairs adding context (startTime, endTime, appliesTo, determination method) and (b) References — provenance triples (statedIn, retrievedFrom). Multiple Statements for the same property-value pair are stored simultaneously with a Rank (preferred, normal, deprecated) to indicate which value to surface by default. This lets Wikidata represent evolving facts, multiple simultaneously valid values, and full source attribution without overwriting historical records.

SPARQL Basic Graph Pattern (BGP) matching is formally equivalent to subgraph homomorphism — finding all mappings from query graph nodes to data graph nodes that preserve edge labels (unlike strict isomorphism, multiple query nodes may map to the same data node). General subgraph isomorphism is NP-complete, but homomorphism is tractable for acyclic queries using Yannakakis' algorithm; cyclic BGPs and full OWL entailment raise complexity to PSPACE and EXPTIME respectively. Practical SPARQL engines use worst-case optimal join algorithms such as Leapfrog Triejoin to handle complex patterns efficiently.

Ontology alignment finds correspondences between concepts, properties, and instances across two or more ontologies — for example, mapping foaf:Person ↔ schema:Person or SNOMED CT concept 44054006 ↔ ICD-10 E11. Challenges include lexical heterogeneity (different names for the same concept), structural heterogeneity (different modeling choices for the same domain), and sheer scale (SNOMED CT has >350K concepts). State-of-the-art matchers (BERTMap, LogMap, OWL2Vec*) combine embedding-based string/semantic similarity with logical consistency checking to propagate and filter matches.

(1) Completeness: fraction of expected attribute slots that are populated, e.g., % of Person entities with a birthDate. (2) Accuracy: fraction of triples verified correct against gold standard or human annotation. (3) Consistency: number of SHACL/OWL constraint violations per 1,000 entities. (4) Timeliness: fraction of time-sensitive facts (e.g., CEO, population) still valid relative to today's date. These dimensions are formalized in W3C Data on the Web Best Practices and DQ4KG benchmark frameworks.

In the raw (unfiltered) setting, when ranking the correct tail t* for query (h, r, ?), other entities t' that also form valid triples (h, r, t') appear in the candidate list and may rank above t*, artificially inflating the rank of t*. The filtered protocol removes all known correct completions (from train, validation, and test sets) from the candidate list before ranking the test triple, so rank reflects only how well the model distinguishes the target answer from genuine negatives. Implementation: build a set of known tails per (h, r) pair, mask those indices from the score vector, then compute the rank of t*.

# Pseudocode for filtered MRR
for h, r, t_target in test_set:
    scores = model.score_tails(h, r)          # shape [num_entities]
    known = known_tails[(h, r)] - {t_target}   # other valid tails
    scores[list(known)] = -float('inf')         # mask them out
    rank = (scores > scores[t_target]).sum() + 1
    mrr += 1.0 / rank

KG construction (information extraction) builds a KG from raw external sources: NLP pipelines apply Named Entity Recognition (NER), relation extraction (RE), and coreference resolution to text corpora to identify and populate entities and relations. KG completion assumes a partial KG already exists and predicts missing triples using its internal structure: embedding models (RotatE) or symbolic rule miners (AnyBURL) infer plausible absent facts. Construction focuses on external-to-graph recall; completion focuses on internal graph-structural reasoning.

Distant supervision (Mintz et al., 2009) automatically generates training labels by aligning an existing KG with a text corpus: if (e1, r, e2) is a KG triple, every sentence co-mentioning e1 and e2 is labeled as expressing relation r. This avoids expensive manual annotation at scale. The core noise problem is wrong labeling: a co-mentioning sentence may not express r (e.g., 'Apple, founded by Jobs, sued Samsung' does not express foundedBy(Apple, Jobs)). Multi-instance learning with sentence-level attention (PCNN+ATT, BERT-based models) filters noise by attending over bag-of-sentences evidence.

Schema.org is a shared structured-data vocabulary co-developed by Google, Microsoft, Yahoo, and Yandex, allowing webmasters to annotate HTML pages using JSON-LD, Microdata, or RDFa with types like schema:Product, schema:Event, and schema:Person and their properties. Search engines consume these markup signals at massive scale to extract machine-readable facts from web pages. Google's Knowledge Graph is partly populated by this signal — linking markup entities to canonical Knowledge Graph entries — enabling rich search features (knowledge panels, event carousels) and powering voice assistant responses.

Independent entity linking disambiguates each mention in isolation using only local textual context and prior KG popularity. Collective entity linking resolves all mentions in a document jointly by enforcing global coherence: co-occurring entities should be semantically related in the KG. For example, if 'Jordan' is linked to the basketball player, 'Chicago Bulls' in the same document should resolve to the NBA team rather than a cattle ranch. Graph-based approaches formulate this as a maximum-coherence optimization — using ILP, loopy belief propagation, or deep neural coherence models — yielding globally consistent entity assignments.

Biomedical KGs such as Hetionet and DRKG (Drug Repurposing Knowledge Graph) integrate heterogeneous entity types — drugs, genes, diseases, pathways, side effects — connected by typed relations (treats, binds, upregulates, associates). Drug repurposing is framed as link prediction: embedding models (RotatE, BioKGE) score the plausibility of (drug, treats, disease) triples for drug-disease combinations not in the training set; high-scoring novel pairs are prioritized for wet-lab validation. DRKG + RotatE was applied to prioritize existing drugs as COVID-19 treatment candidates in 2020.

LLMs parametrically encode world knowledge but exhibit three systematic failure modes as KG replacements: (1) hallucination — generating plausible but factually incorrect statements without citation; (2) epistemic opacity — no mechanism to report whether a specific fact lies within the model's reliable knowledge boundary; (3) no updatability — correcting or adding a fact requires expensive retraining or fine-tuning. Empirical probes (LAMA, PopQA) confirm LLMs recall high-frequency facts but are unreliable for tail entities with low training-data presence. The emerging consensus is KG + LLM hybrid architectures (e.g., GraphRAG, KG-augmented RAG) outperform either in isolation.

WebQuestionsSP (WebQSP) requires up to 2-hop SPARQL queries over Freebase, testing entity linking, relation disambiguation, and date/type constraint handling. ComplexWebQuestions (CWQ) extends WebQSP to 4-hop compositional questions requiring conjunction, count, and superlative operations ('What is the largest country whose capital was founded before 1500?'), stressing compositional decomposition and multi-constraint reasoning. Both evaluate end-to-end systems from natural language question to final KG answer with no intermediate annotation.

In large KGs (millions to billions of entities), learning one embedding vector per entity is memory-prohibitive and impossible for unseen entities. NodePiece tokenizes each entity as a fixed-size set of anchor node IDs (selected by graph distance) plus the surrounding relation-type vocabulary — similar to BPE tokenization in NLP but over the graph structure. A small MLP (the 'tokenizer') maps this token set to a node embedding, so total parameters scale with the number of anchors (k ≪ |V|) rather than all entities. Unseen entities can be encoded at inference time using their anchor distances, achieving inductive generalization.

ULTRA (Galkin et al., 2023) is a foundation model for KG reasoning that represents relations relatively — each relation is treated as a node in a 'relational graph' connected to its inverse and to composed relations — rather than learning absolute entity/relation embedding vectors. A conditional message-passing network over this relational graph produces graph-invariant relation representations. At inference on a completely new KG, new relations are encoded through the same relational graph construction without any fine-tuning, enabling zero-shot link prediction. ULTRA achieves competitive performance across 57 diverse KGs with a single pre-trained checkpoint.

Cypher uses ASCII-art path syntax: parentheses for nodes and square brackets for relationship types. The pattern traverses from the director node to the movie node via [:DIRECTED], then from the movie to actors via [:ACTED_IN] in reverse. Variables bind to matched nodes, and RETURN projects selected properties. Ordering by movie title makes results readable.

MATCH (d:Person {name: 'Christopher Nolan'})-[:DIRECTED]->(m:Movie)<-[:ACTED_IN]-(a:Person)
RETURN a.name AS actor, m.title AS movie
ORDER BY m.title