← Back
Home › Systems › AI applications

knowledge-graph

Stores facts as entities joined by typed relations so that questions about how things relate can be answered by following edges.

Wikidata, Google Knowledge Graph

Open the knowledge-graph pageknowledge-graph Dictionary encodingcompression: Map values to small integer codes via a dictionary for compact, comparable columnsBFS and DFSgraphs: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Pagerankgraphs: Power-iteration PageRank on a sparse graph with damping and dangling nodesEntity linkingmachine-learning: Map each mention to a knowledge-base id, or to NIL, by generating candidates from an alias table, scoring them on prior and context, and thresholding.›Knowledge graph embeddingsmachine-learning: Embedding entities and relations (TransE, RotatE, ComplEx) for link predictionNamed entity recognitionmachine-learning: Find the character spans of entities in text and give each a type, by labelling every token and decoding a valid label sequence.›Relation extractionmachine-learning: Extracting (subject, relation, object) triples from text with classifiers or LLMsEdit distancesearch-sort: Levenshtein/Damerau distance by DP, bit-parallel Myers variantB+ treestorage: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›Entity resolutionstorage: Decide which records describe the same real-world thing: block to cut the pair space, score pairs with a probabilistic model, cluster the matches transitively.›Hash joinstorage: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.›Inverted indexstorage: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›LSM-treestorage: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›MVCCstorage: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.›Triple store indexingstorage: Storing RDF/property triples with SPO/POS/OSP permutation indexes and dictionary-encoded idsWorst case optimal joinstorage: Leapfrog triejoin/generic join for cyclic graph patternsSparse matrices (CSR)numerics: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›Reproducible reductionnumerics: Order-independent floating-point sums (fixed order, Kahan, binned) for bit-for-bit reproducibilityCross-encoder rerankingsearch-sort: Re-score the top-k candidates of a cheap first stage with a model that reads query and candidate together; more accurate than separate embeddings, but one model call per pair.›Loss functionsmachine-learning: The scalar a model minimizes: cross-entropy for classes and tokens, MSE or Huber for values, each with a stable form and simple gradient.›Negative samplingmachine-learning: Train by contrasting each observed positive with a few sampled negatives instead of normalising over every candidate; the choice of sampler decides bias and quality.›Byte-pair encoding (BPE)tokenizationmachine-learning: Learn a subword vocabulary by repeatedly merging the most frequent adjacent pair; byte-level BPE encodes any input losslessly with 32k-200k tokens.›Convolutional codes and theViterbi decodersignal-processing: Streaming error-correcting code: each output bit is a parity of the last K input bits; the Viterbi decoder finds the most likely path through a 2^(K-1)-state trellis.›Embeddingsmachine-learning: A learned table mapping discrete ids to dense vectors: gather forward, sparse scatter-add backward, row-wise optimizers to keep huge tables cheap.›Transformer blockml-training: The decoder-only pre-norm block (attention plus MLP on a residual stream) behind every modern LLM, with exact shapes, parameter, FLOP and KV-cache counts.›Text classificationmachine-learning: Assign one or more labels to a text; climb a ladder from regexes to linear models on n-grams, embeddings, fine-tuned encoders and LLM prompts, only as far as the data and budget demand.›Union-findgraphs: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Record linkagesearch-sort: Probabilistic record matching (Fellegi-Sunter) with blocking for patient or entity indexes+ 7 moreTop-k selectionsearch-sort: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›Text normalizationmachine-learning: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.›AdamWml-training: Adam's per-parameter adaptive steps with weight decay applied directly to the weights; the default optimizer for transformers and LLM pretraining.›Reverse-mode automaticdifferentiationml-training: Record the forward computation on a tape, then sweep it backwards once to get the gradient of a scalar loss for all inputs.›Calibrationmachine-learning: Make predicted probabilities match observed frequencies: measure with ECE, fix post hoc with temperature, Platt or isotonic scaling on held-out data.›Linear and logistic regressionmachine-learning: Fit a weighted sum of features to a number (least squares) or a probability (logistic); the baseline every model must beat.›Near-duplicate detection withMinHash LSHmachine-learning: Estimate set Jaccard similarity from k min-hashes and find similar pairs with banded LSH buckets; the standard dedup for web crawls, training corpora and sequence collections.›Fuzzy string matchingsearch-sort: Edit distance, Jaro-Winkler and trigram indexes for approximate name and address matching+ 2 mored-ary heapdata-structures: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›L-BFGSnumerics: Quasi-Newton minimizer that approximates the inverse Hessian from the last m gradient differences via the two-loop recursion; O(m·n) memory and work per step.›LU and Cholesky factorizationnumerics: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Fast hash functionsdata-structures: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Rolling hashdata-structures: Rabin-Karp polynomial rolling hashes and winnowing for substring fingerprints and document matchingSwiss tabledata-structures: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.›

How it is built

Architecture overview

A knowledge graph stores facts as entities (a person, a company, a molecule, a product) joined by typed relations, so that questions about how things relate can be answered by following edges instead of reading documents. Each fact is a statement of the form subject, predicate, object, plus where it came from and when it held. The system has two halves that meet in a store. A construction pipeline turns raw sources (text, tables, other databases) into statements: find mentions, link them to known entities, extract relations, merge duplicates, check against a schema. A serving side indexes the statements so that a graph pattern (find all pairs of people who share a university and an employer) runs as joins over sorted indexes, and so that a free-text name resolves to an entity in milliseconds. The idea that makes it work is a stable identifier per entity: every source is mapped to it, every index is keyed by it, and the quality of the graph is the quality of that mapping. Hogan et al. survey the data models, schema languages, construction and quality work behind this (Hogan et al. 2021); Wikidata is the open collaborative example (Vrandečić and Krötzsch 2014), and Google introduced the term to a wide audience for search in 2012 ("things, not strings").

Parts:

 sources: web pages, PDFs, tables, partner DBs, human edits
      │
      ▼
 NER ──► entity linking ──► relation extraction ──► entity resolution ──► validation (schema, constraints)
 (mentions)  (ids, NIL)       (candidate triples)    (merge, canonical id)       │ accept / queue for review
      ▲            ▲                                                             ▼
      │       alias index + vectors                      ┌──────────── statement store ───────────────┐
      │       (inverted index, ANN)                      │ dictionary: term ⇄ integer id              │
      │                                                  │ SPO / POS / OSP sorted indexes (LSM or B+) │
      │                                                  │ provenance, validity time, version (MVCC)  │
      │                                                  └───────────────┬────────────────────────────┘
 text query ─► link query ─► graph pattern (SPARQL-like) ─► join plan ─► results       │
                                                                   ▲   analytics: PageRank, embeddings
                                                                   └────────── scores written back as features

How the parts fit together

Statement store

The data model is the one in RDF 1.1: a statement is a triple of subject, predicate and object, with entities named by IRIs (W3C RDF 1.1 Concepts). A "property graph" model with attributes on edges is the common alternative; the storage ideas below apply to both. Real graphs use long strings for terms, so the store first maps every term to a small integer through dictionary-encoding (no page yet) and holds triples as three integers. triple-store-indexing (no page yet) keeps the triples in several sort orders (subject-predicate-object, predicate-object-subject, object-subject-predicate), so any pattern with one or two bound positions is a range scan on some index; the indexes compress well because neighbouring keys share prefixes (Delta encoding on the integer ids, radix-trie for the dictionary side). The index structure is a choice with a known trade-off: a B+ tree reads fast and updates in place, an LSM-tree absorbs a stream of small writes as sequential I/O and merges in the background, which is what a graph that gets continuous edits wants. Readers must see a consistent graph while writers edit, so MVCC keeps timestamped versions and gives every query a snapshot. In memory, the dictionary and the caches use an open-addressing table (Swiss table) with a fast hash. The contract with the rest: every statement has a stable id, a source, a time and a confidence; nothing is deleted, only superseded, so history and "who said so" remain answerable.

Query engine

A graph query is a pattern: several triple patterns that share variables. Evaluating it is a join of the matching ranges. For acyclic patterns the classic plan joins pairs of triple patterns one at a time with a Sort-merge join over two sorted indexes (the sort orders above make the inputs already sorted) or a Hash join on the smaller side. For cyclic patterns (a triangle of friends, a motif in a molecule), pairwise joins can produce intermediate results far larger than the final answer. worst-case-optimal-join (no page yet; the leapfrog triejoin of Veldhuizen) instead binds one variable at a time and intersects the sorted lists of candidates, so its running time is bounded by the size of the largest possible answer. The graph's indexes in several sort orders are what make that intersection cheap. Path questions ("how is A connected to B in at most four hops") are traversals (BFS and DFS), which a query language exposes as property paths. The contract: the engine takes a pattern and a snapshot id and streams solutions, with cost estimates coming from statistics kept per predicate. The W3C standard language for RDF graphs is SPARQL 1.1.

Text to mention

Most knowledge enters as text. Named entity recognition finds the character spans of mentions and labels their type (person, organisation, place, gene), by tagging each token of a BPE tokenisation with a Transformer and decoding the tags into spans; older systems use a Viterbi decode over tag sequences (Convolutional codes and the Viterbi decoder shows the algorithm). Before and after, Text normalization and Unicode tokenization make "Müller", "Mueller" and "MÜLLER" meet. The contract: spans with offsets into the original text, a type, and a score; offsets matter later, for provenance.

Linking

Entity linking maps each mention to an entity id, or to NIL when the entity is not in the graph yet. It is a retrieval problem followed by a reranking problem. Candidates come from an alias table, an Inverted index over names and descriptions scored with BM25, and from a vector index of entity Embeddings (a vector database, see the vector-db system page). The posting lists are compressed (Delta encoding, Bit packing, Varint) and intersected by merging and galloping; the best few are kept with Top-k selection on a d-ary heap. A Cross-encoder then reads the mention in its context and each candidate description together and picks one; BLINK (Wu et al. 2019) is the well-known recipe: a bi-encoder for dense retrieval, a cross-encoder to rerank. The NIL decision matters: forcing a link for an unknown entity pollutes the graph with confident mistakes. Contract: a linked mention carries the entity id, a score and the alternatives considered.

Relation extraction

Given two linked mentions in a sentence, relation-extraction (no page yet) decides which predicate, if any, holds, as a Text classification problem over the sentence with marked entities, or by letting a language model generate triples directly (REBEL, Huguet Cabot and Navigli 2021, is an example of the generative route). The output is a candidate, not a fact: its probability must be calibrated so thresholds mean the same thing across relations, and a logistic combination of the extractor's score, the number of independent sources and the source's reliability gives the confidence stored with the statement. Extraction errors are the main source of wrong facts, so candidates go through validation before they join the graph.

Entity resolution

Two sources describe "the same" company with different names, and a text extractor invents a new id for an entity that exists. Entity resolution fixes it: blocking cuts the n² pairs to plausible ones (by name keys, MinHash buckets, or shared neighbours), pair scoring compares attributes (record-linkage in the Fellegi-Sunter sense, fuzzy-string-matching with edit-distance for names, no pages yet, and rolling-hash fingerprints for long strings), and clustering merges the matches transitively with Union-find. Merging is the risky step: a wrong merge fuses two people into one and poisons everything downstream. The conservative rule is to keep both ids, record a same-as link with a confidence, and merge only above a high threshold; a human queue handles the band between. The graph's own structure helps: two companies with the same CEO, address and founding year are more likely the same than their names alone suggest.

Graph analytics and embeddings

Two derived products come from the whole graph. pagerank (no page yet) computes an importance score for every entity by power iteration on the link graph stored as a Sparse matrix in CSR form; it feeds ranking in search and the choice of which entities to verify first, and reproducible-reduction (no page yet) makes the floating-point sums order-independent so a rerun gives the same scores. knowledge-graph-embeddings (no page yet; TransE, RotatE and relatives) learn a vector per entity and relation so that true triples score higher than corrupted ones, trained with negative sampling, a margin or log loss and AdamW over autodiff. Their use is link prediction: suggest missing facts (for review, not for automatic insertion) and score extracted candidates against what the graph already implies. RotatE (Sun et al. 2019) models each relation as a rotation in complex space, which captures symmetric, inverse and compositional patterns. Smaller solvers such as L-BFGS and LU/Cholesky handle the convex parts (fitting calibration and linear models), and SIMD accelerates the dot products in scoring.

Data and control flow

Ingesting one document (seconds to minutes, order of):

  1. Fetch and normalise the text; keep the source id and timestamp.
  2. NER marks mention spans and types.
  3. Linking retrieves candidates from the alias index and vector index, reranks with the cross-encoder, and returns an id or NIL for each mention.
  4. Relation extraction proposes triples between linked mentions; each has a calibrated probability and the sentence offsets as evidence.
  5. NIL mentions with enough context become new provisional entities; resolution checks whether they match existing ones.
  6. Validation applies schema constraints (types of subject and object per predicate, cardinality, value formats; W3C SHACL is the standard language for such shapes). Rejected or low-confidence triples go to a review queue.
  7. Accepted statements are written with provenance to the store under a new version; the indexes (and the alias and vector indexes) are updated.

Answering one graph query (milliseconds to seconds, order of):

  1. Free-text names in the question are linked to ids with the same linker (fast path: alias table).
  2. The question becomes a pattern; the planner picks index orders and a join strategy from per-predicate statistics.
  3. The engine opens a snapshot, runs range scans and joins (worst-case-optimal for cyclic parts), and streams solutions.
  4. Results are ranked (importance score, confidence, recency) and returned with the provenance of each statement.

Scaling

In the order they bite:

  1. Join blow-up: cyclic and highly connected patterns create huge intermediates. Levers: worst-case-optimal joins, good statistics, early filtering by type, limiting path depth.
  2. Store size and write rate: billions of triples, continuous edits. Levers: dictionary encoding, compressed sorted indexes, LSM-style ingestion, partitioning by predicate or by subject hash, read replicas for queries.
  3. Hub entities: a few nodes (a country, "human") have millions of edges and dominate cost. Levers: statistics-aware plans, special indexes for type edges, caching, per-predicate limits.
  4. Extraction throughput: models are the slow part of construction. Levers: batch GPU inference, cheaper models for triage, extract only from sources whose facts are missing.
  5. Resolution cost: pairs grow quadratically. Levers: blocking, MinHash buckets, incremental resolution of new records only.
  6. Quality: error rate, not speed, limits trust. Levers: constraints, multiple independent sources, sampling-based audits of each source and relation, a review queue ranked by importance score.

Failure modes

FailureSymptomCauseFix
Wrong mergeone entity with two people's factsresolution threshold too low, name collisionconservative merging, same-as with confidence, unmerge by provenance
Missed mergeduplicate entities, split factsblocking too strict, spelling variantsmultiple blocking keys, fuzzy and phonetic keys, periodic global re-resolution
Forced linkingunknown entity linked to a famous namesakeno NIL option, over-confident rerankercalibrate scores, NIL threshold, require context agreement
Hallucinated relationplausible but false triplesgenerative extractor with no evidence checkrequire an evidence span, confidence threshold, schema validation
Join explosionquery times out on a cyclic patternpairwise join planworst-case-optimal join, pattern rewrite, result limits
Hub skewone entity makes queries slowmillions of edges on one nodestatistics-aware planner, caching, partial indexes
Stale facts"current CEO" is last year'sno validity time, no re-checkvalid-from/valid-to on statements, refresh jobs for volatile predicates
Schema driftconstraints reject good data or admit junkschema not updated as the domain changesversioned schema, constraint reports as a quality dashboard
Embedding over-trust"predicted" facts treated as truelink prediction used as ground truthmark as inferred, review before insert, keep out of the base graph
Lost provenancecannot explain or retract a factstatements stored without source and timeprovenance required on write; retraction by source

Real implementations

namewhat it isrepolicencenotes
Apache JenaRDF framework with a triple store (TDB) and a SPARQL serverapache/jenaApache-2.0Java; reference for RDF and SPARQL behaviour
Oxigraphgraph database implementing SPARQL, in Rustoxigraph/oxigraphApache-2.0small, embeddable
QLeverSPARQL engine for very large graphs with text searchad-freiburg/qleverApache-2.0built for query speed on big RDF
Wikibasethe software behind Wikidatawikimedia/Wikibase—statements with references and qualifiers
BlazegraphRDF and SPARQL store, graph databaseblazegraph/databaseGPL-2.0archived on GitHub
BLINKbi-encoder plus cross-encoder entity linkingfacebookresearch/BLINKMITarchived on GitHub
REBELgenerative relation extractionBabelscape/rebel—triples generated end to end
KnowledgeGraphEmbeddingreference code for RotatE and related modelsDeepGraphLearning/KnowledgeGraphEmbeddingMITlink prediction training

The Wikidata Query Service exposes Wikibase data through a SPARQL API (MediaWiki documentation). Google's Knowledge Graph and enterprise graphs are closed; only descriptions exist.

Sources

  • A. Hogan et al., Knowledge Graphs, ACM Computing Surveys, 2021. paper
  • D. Vrandečić, M. Krötzsch, Wikidata: A Free Collaborative Knowledgebase, Communications of the ACM, 2014 paper.
  • W3C, RDF 1.1 Concepts and Abstract Syntax. spec; SPARQL 1.1 Query Language. spec; Shapes Constraint Language (SHACL). spec
  • T. L. Veldhuizen, Leapfrog Triejoin: a worst-case optimal join algorithm, 2012. paper
  • L. Wu et al., Scalable Zero-shot Entity Linking with Dense Entity Retrieval, 2019 (BLINK). paper
  • P.-L. Huguet Cabot, R. Navigli, REBEL: Relation Extraction By End-to-end Language generation, Findings of EMNLP 2021. paper
  • Z. Sun et al., RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space, ICLR 2019. paper
  • Google, Introducing the Knowledge Graph: things, not strings, 2012. blog
  • MediaWiki, Wikidata Query Service. docs

Similar systems

Share the most building blocks with this one.

graph-db 24 %sanctions-screening 19 %threat-intel-platform 18 %