Definition
A knowledge graph is a store of facts written as typed links between named things — IL7R participates in IL-7 Signaling Pathway, Amlexanox binds PDE4B — held in a form where a query can follow several links in a row. That chaining is the entire point, and it is the one thing a document index cannot do: a search engine returns text that resembles your question, and a knowledge graph returns the result of a join across facts that were never written down together.
The structure is trivial — three columns and an index will do it. What costs is everything that makes the structure worth querying: deciding that "IL7R", "CD127" and "interleukin 7 receptor" are one entity, that a relationship extracted from a 2019 paper is still true, and that a source deserves to be believed. Almost all of a knowledge graph's value comes from the curation, and the curation is the part nobody sells you. Watch what happened when curation was offered free. When Google shut Freebase down it held, in the migration team's words, "more than 3 billion facts about almost 50 million entities", and handed the lot to Wikidata under CC0. By January 2016, just over a hundred Wikidata editors had performed about 90,000 approve-or-reject actions against the 14 million statements the import tool had queued up.
What breaks if you ignore this: you build the graph, demo it, and then it rots. Nothing in a graph tells you a fact expired. The failure is silent — a query still returns rows, they are just wrong — and it is worse than a stale document index, because a graph answer arrives with the authority of a database and no passage of text for a reader to sanity-check against.
How It Works
A fact is a triple, and a query is a join
Every knowledge graph reduces to the same three-part statement: a subject, a predicate, an object. Disease::DOID:2377 associates Gene::3575. Store enough of these and you have a graph, because the object of one triple is the subject of the next. Querying is then a join: start at a node, follow one edge type, follow another from wherever you land.
A relational database can do this too, and for two joins it will do it faster. The graph earns its keep when the number of hops is not known in advance, when the join is over edge types rather than tables, and when the schema is sparse — most entities have most properties missing, which is a disaster in a wide table and costs nothing in an edge list.
The multi-hop question, worked on a real graph
Take Hetionet v1.0, the biomedical graph behind the drug-repurposing study Project Rephetio: 47,031 nodes of 11 types and 2,250,197 relationships of 24 types, assembled from 29 public sources by Himmelstein and colleagues and published in eLife in September 2017. Among them are 20,945 genes, 1,822 pathways, 1,552 compounds and 137 diseases.
Now ask the question a vector index cannot answer: which drugs bind a protein sitting in the same pathway as IL7R — a gene associated with multiple sclerosis? Run it as a traversal and the shape is:
IL7R → 7 pathways → 1,180 other genes in those pathways → 159 of those genes have a known binding compound → 132 distinct compounds.
Three hops, three index lookups, one answer. Now try it with documents. No paper links Amlexanox to IL7R, because the connection is two facts long and lives in two literatures: one about a drug and a phosphodiesterase, one about a receptor and a signalling cascade. To reconstruct the chain by reading, you need the pathway membership of IL7R (1 record), then the membership list of each of its 7 pathways (7 records), then a binding check on each of the 1,180 genes those lists contain: 1,188 lookups, in three dependent rounds. Retrieve ten documents a round and that is 119 rounds of retrieval, each one of which has to know what the previous round found. An embedding of the original question is close to none of those 1,188 documents, because none of them mentions IL7R and a compound in the same breath. This is not a ranking problem that a better embedding fixes. The information the question needs exists only as a join.
The corollary matters as much: run the same traversal from a disease rather than a gene and multiple sclerosis's 150 associated genes reach 664 pathways, 8,309 genes and 1,385 of Hetionet's 1,552 compounds. Three hops from a well-connected start node returns most of the graph. Multi-hop traversal is powerful and it over-generates; Rephetio's actual method scores degree-weighted paths rather than counting reachable nodes, precisely because reachability alone says almost nothing.
Building one from text costs more tokens than reading the text
The modern promise is that an LLM reads your documents and produces the graph, so the curation problem goes away. It does not; it becomes a token bill, and the arithmetic is worth doing before committing.
Microsoft's GraphRAG paper (Edge et al., April 2024) indexed a podcast-transcript corpus of about 1 million tokens — 1,669 chunks of 600 tokens with 100-token overlaps — into a graph of 8,564 nodes and 20,691 edges. The pipeline does not stop at extraction: it clusters the graph into communities and writes a summary of every community at every level of the hierarchy. Those summaries, as reported in the paper's Table 2, come to 26,657 tokens at the root level, 225,756, 565,720 and 746,100 at the three levels below — 1,564,233 tokens of generated text from a 1,000,000-token corpus. The news corpus behaves the same way: about 1.7 million tokens in, 2,513,575 tokens of summaries out. Indexing the podcast set took 281 minutes on their configuration.
That output is the part you can count, and it is only the output. Every chunk is also read by the model at least once during extraction, usually more than once, and every entity and relationship description is read again to be summarised. So the durable statement is this: graph construction is an output-heavy job whose total token traffic is several times the corpus, paid up front, before a single question is asked. Vector indexing is an input-only job — one embedding pass over the corpus, at per-token prices roughly two orders of magnitude below generation. Microsoft's own follow-up put a figure on the gap when it announced LazyGraphRAG in November 2024: deferring the summarisation to query time made "data indexing costs identical to vector RAG and 0.1% of the costs of full GraphRAG".
Types
The consequential split is not by domain but by data model, and it decides what you can do later.
RDF triple stores give every entity and every predicate a global URI, and query with SPARQL. The identifier is the feature: because wd:Q42 means the same thing in your database and in someone else's, two graphs can be merged by anyone, which is what makes Wikidata and DBpedia usable as public infrastructure rather than as somebody's private table. The cost is that a triple has exactly three slots, so saying something about a fact — who asserted it, when it was true, how confident you are — requires reification, named graphs or RDF-star, all of which make the query longer and the data larger. The schema is written as an ontology in RDFS or OWL; that machinery has its own page, and a knowledge graph's schema is an ontology whether or not anyone wrote it down.
Property graphs — Neo4j, Memgraph, TigerGraph, queried in Cypher or Gremlin — let nodes and edges carry key-value properties directly, so binds can have an affinity and a source without ceremony, and adjacency is stored as pointers, which makes local traversal fast. The cost is identity: a node id means nothing outside the database that issued it, so merging two property graphs is a data-integration project rather than a set union.
Hetionet is distributed in both, which is the honest summary of the trade-off: publish in RDF or JSON so others can combine it, load into Neo4j when you actually want to traverse it.
Real-World Applications
Google Knowledge Graph. The system that put the term into general use, launched 16 May 2012 with "more than 500 million objects, as well as more than 3.5 billion facts about and relationships between these different objects". By Google's own reintroduction on 20 May 2020 it had "amassed over 500 billion facts about five billion entities" — tenfold the entities and roughly 143 times the facts in eight years, which is a useful reminder that the curated core of these systems is fed by extraction at a scale no editorial team could match. It is what fills the knowledge panel beside a search result and what lets semantic search resolve "his wife" into a person.
Wikidata. The largest openly editable knowledge graph: about 122.5 million items and 2.52 billion edits since its 2012 launch, maintained by 41,233 active editors as of July 2026. Divide those and the curation problem is quantified — roughly 2,970 items per active editor, against about 21 edits for every item that exists. It is the structured backbone behind Wikipedia infoboxes and a common grounding source for assistants that need entity identifiers rather than prose.
Hetionet and Project Rephetio. The 2,250,197-edge biomedical graph above was built to rank drug-repurposing hypotheses, integrating gene expression, protein interaction, pathway membership, side effects and 755 known compound-treats-disease pairs into one queryable structure. The point is not that the graph knew anything new — every edge came from an existing database — but that no existing database supported the join.
Microsoft's GraphRAG. Released as an open-source library in July 2024, it is the reason most people meet the term today: build a graph over internal documents so an assistant can answer questions that span them. Its published evidence needs reading carefully, and the next section does that.
Key Concepts
Radical incompleteness is the normal state. The single most useful number about knowledge graphs comes from Google's Knowledge Vault paper (Dong et al., KDD 2014), which measured Freebase — then the largest open knowledge base — and found that 71% of people in it had no known place of birth and 75% no known nationality. The accompanying KDD talk extended the table: 68% missing a profession, 91% an education, 94% a parent. These were not obscure entities; they were the people someone had already bothered to create a record for.
A missing edge is not a false fact, and treating it as one is a bug. Query a graph for "people born in Honolulu" and you get the 29% who have the property. Under the closed-world assumption the rest are not born there; under the open-world assumption they are unknown. Databases default to closed, graphs of the real world are open, and code written by someone who has not noticed the difference will quietly report absence as negation. This is also why link prediction exists as a research field, and why graph neural networks are trained on knowledge graphs at all: the interesting problem is not querying the edges you have but scoring the ones you do not. The Knowledge Vault itself was that project — 1.6 billion candidate triples fused from web extraction, of which 324 million scored above 0.7 confidence and 271 million above 0.9.
Entity resolution is the whole game. Two records that should be one node cost you a join; one node that should be two poisons every query that touches it. The Freebase-to-Wikidata migration measured this directly: of Freebase's roughly 48 million topics, the team could map only 4.56 million — 9.5% — to Wikidata items, and those mapped topics were the subject of just 64 million of the 3 billion facts. Nine-tenths of a mature, well-funded knowledge graph could not be automatically matched to another mature knowledge graph about the same world.
Challenges
The curation does not amortise. A vector index over a document set is rebuilt by re-running an embedding pass; correctness is inherited from the documents. A knowledge graph asserts facts in its own voice, so every assertion is a standing claim someone has to be willing to defend. That is why the Freebase donation stalled: the data was free, the review was not, and 90,000 human decisions in a year against 14 million queued statements is the rate at which volunteer curation actually happens. Budget for the reviewers or accept an unreviewed graph — there is no third option, and an LLM-built graph is an unreviewed graph with better formatting.
GraphRAG's published gains are real but smaller than the headline. The 2024 paper reports Graph RAG beating conventional vector RAG on comprehensiveness with win rates of 72-83% on the podcast corpus and 72-80% on the news corpus, judged by an LLM. Read the same figure one column across, though, and the control condition tells a different story: summarising every source chunk with no graph at all beat vector RAG 83-17 on the podcast corpus, where the best graph condition managed 79-21. Against that no-graph control, the graph's own head-to-head margin was 57% on podcasts and 62% on news. Nearly all of the improvement over vector RAG came from reading the whole corpus, not from the structure imposed on it. Note also what was measured — comprehensiveness and diversity, not correctness; the paper's own directness check found vector RAG produced the most direct answers of any condition.
Where the graph genuinely wins on those numbers is cost. Answering from root-level community summaries needed 26,657 context tokens against 1,014,611 for map-reduce over source texts — 38× fewer tokens per query, for a few points of quality. That is a real and defensible reason to build one: not that the graph knows more, but that a hierarchy of summaries is a compression of the corpus you can afford to query repeatedly.
Independent evaluation says the win is task-shaped. The systematic comparison by Han et al. (RAG vs. GraphRAG, arXiv:2502.11371, February 2025) found graph methods ahead on multi-hop questions — 69.87% against 65.77% for standard RAG on MultiHop-RAG with Llama 3.1-70B — and behind on single-hop ones, where plain RAG scored 68.18 F1 on Natural Questions against 64.03. Roughly four points each way, in opposite directions, depending entirely on whether the question needs a join. The construction cost was not symmetric: 135 seconds to index the corpus for RAG against 7,702 seconds for the graph, a 57× difference, with retrieval latency also higher for the triple-based variant. If your questions are mostly single-hop lookups, you are paying 57× to lose four points.
Temporal validity has no natural home. "CEO of" is true for an interval, and the triple has no slot for one. Every graph that has run for a few years has accreted a convention for this — qualifiers, named graphs, edge properties, a valid_from column — and none of them is portable, which is a large part of why merging two real graphs is harder than the shared vocabulary suggests.
Future Trends
Deferring construction rather than scaling it. The LazyGraphRAG result — index like a vector store, do the graph work at query time, report comparable global-question quality at a fraction of the cost — points at the honest reading of the last two years: the expensive precomputation was buying less than assumed. Expect more architectures that extract structure per query instead of maintaining it globally.
The graph as a view, not an asset. Most organisations already hold their entity relationships in relational tables and event logs. Building a second, divergent copy in a graph database creates a synchronisation problem on top of the curation problem, and the more interesting direction is exposing a graph query interface over the existing stores rather than exporting into a new one.
Provenance as a first-class edge property. Once graphs are populated by extraction, the question "which document, which model, which run produced this edge, and when" stops being metadata hygiene and becomes the mechanism by which the graph can be audited and rolled back. A graph whose edges cannot be traced to a source is one bad extraction run away from being unusable, and unlike a document store it has no original text to fall back on.
Verification, not extraction, as the research frontier. Extraction quality is adequate and improving; nothing has moved the cost of checking an extracted fact. The Knowledge Vault's confidence scores were an early attempt, and the gap between its 1.6 billion candidate triples and the 271 million it scored above 0.9 confidence is a fair estimate of how much of automated web extraction a system is willing to stand behind — about 17%.
Code Example
The multi-hop join, first as a query against Hetionet's actual Neo4j schema, where relationship types carry the metaedge abbreviation (GpPW = Gene-participates-Pathway, CbG = Compound-binds-Gene):
MATCH (g:Gene {name: 'IL7R'})
-[:PARTICIPATES_GpPW]-(pw:Pathway)
-[:PARTICIPATES_GpPW]-(other:Gene)
-[:BINDS_CbG]-(c:Compound)
WHERE other <> g
RETURN c.name AS compound, count(DISTINCT pw) AS shared_pathways
ORDER BY shared_pathways DESC, compound
Three edge patterns in a row, and the reason this is not a search: nothing in the query mentions a word that would appear in a document about the answer. The same traversal without a database, over the published edge list:
import collections, gzip, io, urllib.request
BASE = "https://media.githubusercontent.com/media/hetio/hetionet/master/hetnet/tsv/"
raw = urllib.request.urlopen(BASE + "hetionet-v1.0-edges.sif.gz").read()
pathways_of = collections.defaultdict(set) # gene -> pathways it participates in
genes_of = collections.defaultdict(set) # pathway -> genes in it
binders_of = collections.defaultdict(set) # gene -> compounds that bind it
with gzip.open(io.BytesIO(raw), "rt") as fh:
next(fh)
for line in fh:
source, metaedge, target = line.rstrip("\n").split("\t")
if metaedge == "GpPW":
pathways_of[source].add(target)
genes_of[target].add(source)
elif metaedge == "CbG":
binders_of[target].add(source)
start = "Gene::3575" # IL7R
pathways = pathways_of[start]
neighbours = set().union(*(genes_of[p] for p in pathways)) - {start}
compounds = set().union(*(binders_of[g] for g in neighbours))
print("pathways containing IL7R :", len(pathways))
print("other genes in those pathways :", len(neighbours))
print(" with a binding compound :", sum(1 for g in neighbours if binders_of[g]))
print("distinct compounds reached :", len(compounds))
print("lookups to rebuild by reading :", 1 + len(pathways) + len(neighbours))
Output:
pathways containing IL7R : 7
other genes in those pathways : 1180
with a binding compound : 159
distinct compounds reached : 132
lookups to rebuild by reading : 1188
Two dictionaries and a set union — thirty lines, no graph database, and the answer in under a second once the file is loaded. That is the honest scale of the structure. The 2,250,197 edges those thirty lines traverse took a research team and 29 curated source databases to assemble, and that ratio is the whole subject.