GraphRAG and Knowledge Graphs

Vector search finds passages that look like the question. Some questions are not like any single passage: "Which of our suppliers are owned by companies that a sanctioned person controls?" or "What are the main themes across these 2,000 interview transcripts?" The first needs facts chained across documents; the second needs a view of the whole corpus. Knowledge graphs and GraphRAG target exactly these gaps. They are used in finance (ownership and risk networks), life sciences (drug, gene and disease relations), enterprise search, fraud investigation and intelligence analysis.

The picture: a detective's corkboard

A vector index is like a filing cabinet with a brilliant clerk who can find the folder most similar to your request. A knowledge graph is the detective's corkboard: photos of people, companies and places pinned up, with red string between them labelled "CEO of", "acquired", "lives in". You can follow the string from one pin to the next, which is how you answer chains of questions. GraphRAG adds a further step: step back from the board, notice the clusters of tightly connected pins, and write a summary card for each cluster, so you can answer "what is going on overall?" without reading every folder.

Knowledge graphs: the formal model

A knowledge graph (KG) represents knowledge as entities (nodes: people, organizations, products, concepts) and relations (typed, directed edges between them). The atomic unit is the triple (subject, predicate, object), for example (Nimbus Labs, ACQUIRED, Kestrel AI). A set of triples defines a directed, labelled multigraph $G = (V, E)$ with $E \subseteq V \times \mathcal{R} \times V$, where $\mathcal{R}$ is the set of relation types.

Two data models dominate:

• RDF (Resource Description Framework), a W3C standard. Every subject and predicate is an IRI (a global identifier), and objects are IRIs or literals (strings, numbers, dates). Schemas and ontologies are expressed in RDFS and OWL, enabling formal reasoning (for example inferring that a subsidiary of a subsidiary is also owned). Queried with SPARQL. Strong for data integration and published vocabularies; Wikidata, a large public knowledge base, is published as RDF and queried with SPARQL.
• Labelled property graphs (LPG), used by graph databases such as Neo4j and others. Nodes have labels and key-value properties; edges have a type and their own properties (for example ACQUIRED {year: 2023, price_usd: 1.2e8}). Queried with Cypher, or with GQL (ISO/IEC 39075:2024), the ISO-standard property-graph query language published in 2024, which draws heavily on Cypher. Strong for application development and graph algorithms.

An ontology or schema defines allowed entity types and relation types, for example "a Person can be CEO_OF an Organization". Without one, extracted graphs drift into thousands of near-synonymous relation names.

Building a KG with LLM extraction

Classic KG construction used named-entity recognition, relation classifiers and hand-written rules. LLMs make extraction far more flexible:

1. Chunk documents (smaller chunks yield more extracted facts per token, at higher cost).
2. Extract: prompt an LLM to return entities (name, type, description) and relations (source, target, type, description, optional strength) as structured JSON, ideally constrained to your schema. A second "did you miss anything?" pass (sometimes called gleaning) increases recall at extra cost.
3. Resolve entities: merge "Nimbus Labs", "Nimbus Labs Inc." and "Nimbus" into one node, using normalization, string similarity, embeddings of descriptions and, for hard cases, an LLM judge. Entity resolution errors are the most damaging failure in KG construction: missed merges fragment the graph, wrong merges invent connections.
4. Attach provenance: every node and edge stores the chunk IDs it came from, so answers can cite sources and you can audit or delete.
5. Validate: check types against the schema, flag low-confidence facts, and sample for human review.

Extracted facts are LLM outputs and can be hallucinated; provenance and validation are what make the graph trustworthy.

GraphRAG: Microsoft's approach

"GraphRAG" is used loosely for any retrieval that uses a graph. The best-known specific method is from Microsoft Research: Edge et al., "From Local to Global: A Graph RAG Approach to Query-Focused Summarization" (arXiv, April 2024), released as the open-source graphrag library. Its indexing pipeline:

1. Split the corpus into text units (chunks).
2. Use an LLM to extract entities, relationships and claims from each chunk, and summarize the descriptions of each entity and relationship across all mentions.
3. Build the entity graph and run hierarchical community detection with the Leiden algorithm, which partitions the graph into communities of densely connected nodes, then recursively partitions those communities, giving levels from a few broad communities to many fine-grained ones.
4. Use an LLM to write a community report (summary) for every community at every level, bottom-up, describing its key entities, relations and claims.

It then offers two main query modes:

• Global search answers corpus-wide "sensemaking" questions ("What are the main themes in this dataset?"). It works map-reduce style: each community report at a chosen level is given to the LLM with the question to produce a partial answer with a helpfulness score (map); the most helpful partial answers are combined into a final answer (reduce). Ordinary top-$k$ vector RAG struggles here because no single chunk contains "the main themes".
• Local search answers questions about specific entities. It finds the entities relevant to the question (via embeddings of entity descriptions), then gathers their neighbours, relationships, claims, related community reports and source text units into the context window.

The paper evaluated global search on query-focused summarization over corpora of roughly a million tokens (podcast transcripts and news articles), using an LLM judge to compare answers, and reported that GraphRAG answers were more comprehensive and diverse than those from a conventional vector RAG baseline. Note what this does and does not show: it is evidence for global sensemaking questions, judged by an LLM, not a claim that graphs beat vectors on ordinary fact lookup. The project has continued to add query modes and cheaper indexing variants since; check its documentation for the current set.

When graphs beat vectors

Worked example of multi-hop. Suppose these facts sit in four different documents: Ada Chen is CEO of Nimbus Labs; Nimbus Labs acquired Kestrel AI; Kestrel AI develops Falcon OCR; Falcon OCR is used by Harbor Bank. Question: "Which banks use products built by companies Ada Chen runs?" The question's embedding resembles the first document (it mentions Ada Chen) and maybe the last (it mentions banks), but the two middle documents mention neither, so top-$k$ retrieval likely misses at least one link and the LLM cannot complete the chain. In the graph, the answer is a four-hop traversal: Ada Chen to Nimbus Labs to Kestrel AI to Falcon OCR to Harbor Bank.

import networkx as nx

triples = [  # (subject, relation, object) as an LLM extractor might emit them
    ("Ada Chen", "CEO_OF", "Nimbus Labs"),
    ("Nimbus Labs", "ACQUIRED", "Kestrel AI"),
    ("Kestrel AI", "DEVELOPS", "Falcon OCR"),
    ("Falcon OCR", "USED_BY", "Harbor Bank"),
    ("Harbor Bank", "HEADQUARTERED_IN", "Rotterdam"),
    ("Ben Ortiz", "CTO_OF", "Kestrel AI"),
    ("Nimbus Labs", "PARTNER_OF", "Orchid Cloud"),
    ("Orchid Cloud", "HOSTS", "Harbor Bank"),
]
G = nx.MultiDiGraph()
for s, r, o in triples:
    G.add_edge(s, o, relation=r)

def follow(node, relation):
    return [o for _, o, r in G.out_edges(node, data="relation") if r == relation]

for company in follow("Ada Chen", "CEO_OF"):
    for sub in follow(company, "ACQUIRED"):
        for prod in follow(sub, "DEVELOPS"):
            print(company, "->", sub, "->", prod, "->", follow(prod, "USED_BY"))
# Nimbus Labs -> Kestrel AI -> Falcon OCR -> ['Harbor Bank']

# Communities on the undirected graph (GraphRAG uses Leiden; networkx
# provides Louvain, an older relative that optimizes the same objective)
U = nx.Graph(G.to_undirected())
for i, c in enumerate(nx.community.louvain_communities(U, seed=42)):
    print(i, sorted(c))

On this toy graph Louvain finds three communities: {Ada Chen, Nimbus Labs, Orchid Cloud}, {Ben Ortiz, Kestrel AI, Falcon OCR} and {Harbor Bank, Rotterdam}. In GraphRAG, an LLM would write a report for each, such as "Kestrel AI and its OCR product line", which global search would then map-reduce over. (Exact community assignments can vary with the seed and library version.) Both Louvain and Leiden maximize modularity, which compares the density of edges inside communities with what a random graph of the same degrees would have; Leiden adds a refinement step that guarantees communities are internally connected, a known weakness of Louvain.

Query languages: Cypher and SPARQL basics

The same four-hop question in Cypher, which uses ASCII-art patterns, (node)-[:RELATION]->(node):

MATCH (p:Person {name: "Ada Chen"})-[:CEO_OF]->(c:Organization)
      -[:ACQUIRED]->(s:Organization)-[:DEVELOPS]->(prod:Product)
      -[:USED_BY]->(b:Organization)
RETURN c.name, s.name, prod.name, b.name

An aggregation that vector search cannot do, counting customers per product:

MATCH (prod:Product)-[:USED_BY]->(customer)
RETURN prod.name, count(customer) AS customers
ORDER BY customers DESC LIMIT 10

In SPARQL, patterns are triples with ?variables, and prefixes abbreviate IRIs (ex: here is a made-up example namespace):

PREFIX ex: <http://example.org/>
SELECT ?company ?product ?bank WHERE {
  ex:AdaChen  ex:ceoOf    ?company .
  ?company    ex:acquired ?sub .
  ?sub        ex:develops ?product .
  ?product    ex:usedBy   ?bank .
}

An LLM can translate natural-language questions into Cypher or SPARQL (text-to-query), given the schema in its prompt. Treat generated queries like generated SQL: validate them, run them read-only with timeouts and row limits, and enforce access control in the database, not in the prompt.

Costs

GraphRAG-style indexing is expensive because it calls an LLM on every chunk and again for every community. An illustrative estimate (the assumptions are ours, not the library's defaults): a 1-million-token corpus split into 600-token chunks gives about $1{,}000{,}000 / 600 \approx 1{,}667$ chunks. If each extraction call sends the chunk plus a 1,500-token instruction prompt, input is about $1{,}667 \times 2{,}100 \approx 3.5$ million tokens, plus perhaps 400 output tokens per chunk ($\approx 0.67$ million). One gleaning pass roughly doubles that. Then entity and relationship description summaries and community reports add further calls; with, say, 500 communities across all levels at 3,000 input and 800 output tokens each, that is another 1.5 million input and 0.4 million output tokens. The total is on the order of 10 million tokens processed, versus embedding 1 million tokens for vector RAG, which is one to two orders of magnitude cheaper. Multiply by your model's per-token price, and remember re-indexing when documents change: inserting new documents can alter communities and require regenerating their reports.

Other costs: graph database operations, entity resolution engineering, schema design, and query latency for global search (one LLM call per community report in the map step).

Ways to reduce cost: use a small, cheap model for extraction and a strong one for answering; restrict extraction to a schema; build the graph only over the subset of documents where relationships matter; and use structured sources (databases, CRMs, existing ontologies) directly instead of extracting facts that already exist in structured form.

Combining graph and vector retrieval

The strongest systems use both:

• Vector entry, graph expansion: embed the question, find the most similar entities or chunks, then expand along graph edges ($1$ to $2$ hops) to collect connected facts and their source chunks. This is essentially GraphRAG's local search.
• Graph-filtered vector search: use the graph to compute a candidate set (for example all documents about subsidiaries of a company) and run vector search inside it.
• Router: classify the question; send fact lookups to vector RAG, aggregations and multi-hop questions to text-to-Cypher or text-to-SPARQL, and corpus-wide questions to community summaries.
• Vectors inside the graph: many graph databases store embeddings on nodes and offer vector indexes, so one query can combine pattern matching and similarity.

Common pitfalls

• Building a graph because it is fashionable. If your questions are single-fact lookups, a graph adds cost and failure modes without benefit. Classify a sample of real questions first.
• No schema: thousands of relation types like ACQUIRED, BOUGHT, TOOK_OVER, ACQUISITION_OF that queries cannot rely on.
• Weak entity resolution: duplicate nodes break multi-hop paths; over-merging (two different "John Smith"s) invents false connections.
• Dropping provenance, making answers uncitable and errors untraceable.
• Treating extracted triples as ground truth: they inherit LLM extraction errors.
• Ignoring update cost: a corpus that changes daily may not afford full community re-summarization.
• Unvalidated text-to-query, leading to wrong answers that look authoritative or to expensive runaway queries.

In practice

• Start with strong hybrid vector retrieval and an evaluation set. Add a graph when the evaluation shows failures on multi-hop, aggregation or global questions, and measure the improvement.
• When your organization already has structured data (ownership tables, product catalogues, org charts), load it as a graph directly; use LLM extraction for what exists only in text.
• Define a small schema, enforce it in extraction prompts with structured outputs, and invest in entity resolution.
• For corpus-wide sensemaking over a fixed corpus (research archives, investigations, survey responses), GraphRAG-style community summaries are worth evaluating despite the indexing cost.
• Keep provenance end to end so every answer can cite the chunks behind each fact.