Knowledge Graphs and RAG: Combining Structure with Search

Vector search answers one kind of question very well: find the passages that mean something like this. Many real questions are a different kind. How many contracts expire this quarter? Which customers bought both products? What replaced this policy, and what replaced that? These need facts that are filtered, counted or followed from one thing to the next.

A knowledge graph stores exactly those facts: things as nodes, relationships as labelled edges. Combined with retrieval-augmented generation, it lets a system answer structured questions exactly and leave the open-ended ones to vector search.

Two kinds of question

Similarity search returns the top few passages. It cannot count everything, guarantee a complete list or follow a chain of links. The research on combining language models with knowledge graphs makes the general point: models are weak at reliably accessing specific facts, and graphs store those facts explicitly, at the cost of being hard to build and keep current (Pan et al.: LLMs and knowledge graphs).

A graph from metadata you already have

The cheapest knowledge graph is the one hiding in existing structured data. Every Python Enhancement Proposal begins with a header of metadata: authors, status, type, target Python version, and which proposals it requires, replaces or is superseded by (PEP 1). The script reads those headers from 744 PEPs into a graph, with people and proposals as nodes and relationships as labelled edges (NetworkX: MultiDiGraph). It then asks four structured questions and tries one of them with vector search.

import re
from collections import Counter
from pathlib import Path

import networkx as nx
from sentence_transformers import SentenceTransformer


def header(text):
    # a PEP starts with "Field: value" lines; continuation lines are indented
    fields, key = {}, None
    for line in text.split("\n"):
        if not line.strip():
            break
        m = re.match(r"([A-Za-z-]+):\s*(.*)", line)
        if m and not line[0].isspace():
            key = m.group(1)
            fields[key] = m.group(2).strip()
        elif key:
            fields[key] += " " + line.strip()
    return fields


def people(field):
    names = re.sub(r"\s*<[^>]*>", "", field)            # drop email addresses
    return [n.strip() for n in names.split(",") if n.strip()]


peps = {}
for path in sorted(Path("peps").glob("pep-*.rst")):
    h = header(path.read_text(encoding="utf-8"))
    if h.get("PEP", "").isdigit():
        peps[int(h["PEP"])] = h

# 1. Build the graph: PEPs and people as nodes, relationships as labelled edges
G = nx.MultiDiGraph()
for n, h in peps.items():
    G.add_node(f"PEP {n}", kind="pep", status=h.get("Status", "").strip(),
               version=h.get("Python-Version", "").strip(), title=h.get("Title", ""))
    for person in people(h.get("Author", "")):
        G.add_node(person, kind="person")
        G.add_edge(person, f"PEP {n}", rel="wrote")
    for other in re.findall(r"\d+", h.get("Superseded-By", "")):
        G.add_edge(f"PEP {n}", f"PEP {int(other)}", rel="superseded_by")
    for other in re.findall(r"\d+", h.get("Requires", "")):
        G.add_edge(f"PEP {n}", f"PEP {int(other)}", rel="requires")

kinds = Counter(d["kind"] for _, d in G.nodes(data=True) if "kind" in d)
rels = Counter(d["rel"] for _, _, d in G.edges(data=True))
print(f"graph: {kinds['pep']} PEPs, {kinds['person']} people, edges {dict(rels)}")

# 2. Questions the graph answers exactly
wrote = Counter(u for u, v, d in G.edges(data=True) if d["rel"] == "wrote")
print("\nmost PEPs written:", ", ".join(f"{p} {n}" for p, n in wrote.most_common(4)))

target = sorted(int(p[4:]) for p, d in G.nodes(data=True)
                if d.get("kind") == "pep" and d["version"] == "3.12" and d["status"] == "Final")
print(f"Final PEPs targeting Python 3.12: {len(target)} -> {target}")

guido = "Guido van Rossum"
partners = Counter(other for pep in G.successors(guido) for other in G.predecessors(pep)
                   if other != guido and G.nodes[other].get("kind") == "person")
print("most frequent co-authors of", guido + ":", ", ".join(f"{p} {n}" for p, n in partners.most_common(3)))

chains = []
for start in [p for p, d in G.nodes(data=True) if d.get("kind") == "pep"]:
    chain = [start]
    while True:
        nxt = [v for _, v, d in G.out_edges(chain[-1], data=True) if d["rel"] == "superseded_by"]
        if not nxt or nxt[0] in chain:
            break
        chain.append(nxt[0])
    chains.append(chain)
longest = max(chains, key=len)
print("longest supersession chain:", " -> ".join(longest))

# 3. The same structured question through vector search over one text card per PEP
cards = {n: f"PEP {n}: {h.get('Title', '')}. Status: {h.get('Status', '').strip()}. "
            f"Python version: {h.get('Python-Version', 'none').strip()}." for n, h in peps.items()}
model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2")
numbers = list(cards)
vectors = model.encode([cards[n] for n in numbers], normalize_embeddings=True)
query = model.encode(["Final PEPs for Python version 3.12"], normalize_embeddings=True)[0]
top = [numbers[i] for i in (vectors @ query).argsort()[::-1][:10]]
hits = [n for n in top if n in target]
print(f"\nvector search, top 10 for 'Final PEPs for Python version 3.12': {top}")
print(f"   correct: {len(hits)} of 10 returned, {len(hits)} of the {len(target)} that exist")

graph: 744 PEPs, 373 people, edges {'wrote': 1162, 'superseded_by': 32, 'requires': 39}

most PEPs written: Alyssa Coghlan 53, Guido van Rossum 50, Barry Warsaw 46, Brett Cannon 35
Final PEPs targeting Python 3.12: 15 -> [669, 683, 684, 687, 688, 689, 692, 695, 697, 698, 699, 701, 706, 709, 721]
most frequent co-authors of Guido van Rossum: Barry Warsaw 5, Moshe Zadka 3, Ivan Levkivskyi 3
longest supersession chain: PEP 241 -> PEP 314 -> PEP 345 -> PEP 566

vector search, top 10 for 'Final PEPs for Python version 3.12': [1, 749, 160, 361, 236, 3100, 3003, 3135, 221, 375]
   correct: 0 of 10 returned, 0 of the 15 that exist

What the output shows

• The graph answers structured questions exactly. Fifteen Final PEPs target Python 3.12, listed in full. Alyssa Coghlan has written the most PEPs. Guido van Rossum's most frequent co-author is Barry Warsaw. PEP 241 was superseded by PEP 314, which was superseded by PEP 345, and that by PEP 566.
• Vector search failed the filter completely. Asked for "Final PEPs for Python version 3.12", it returned ten PEPs, none of them correct. The cards contained the right facts, but embeddings capture overall meaning, not the exact value of a version field, so similar-sounding cards for other versions ranked higher.
• Some questions are impossible for retrieval. "Who wrote the most PEPs?" needs every authorship counted. No top-ten list of passages can answer it.
• Building this graph needed no language model. The facts were already structured. Extracting them from free text would have needed an LLM pass, with its own errors to check.

GraphRAG and its relatives

"GraphRAG" now names several approaches.

Graph-backed retrieval. A question is turned into a graph query, often by an LLM writing the query, and the exact results go into the prompt as context. This is the pattern above, with a model in front.

Graphs built from text. Microsoft's GraphRAG uses an LLM to extract entities and relationships from documents into a graph, groups closely related entities into communities and writes a summary of each. Its authors show that ordinary RAG fails on global questions such as the main themes of a corpus, and that combining the community summaries answers them (Edge et al.: GraphRAG). The price is many LLM calls at indexing time.

Hybrid retrieval. Vector search finds the relevant passages, and the graph adds connected facts: the author of a retrieved section, the policy that replaced it, the products in the same family.

Adding a graph to a RAG system

1. Collect the questions that fail with vector search. If they are about counts, filters, lists or connections, a graph may help.
2. Look for structure you already have: database tables, document metadata, tags, links. Start there.
3. Extract from text only where needed, and check a sample of what the LLM extracted.
4. Route each question. Send structured questions to the graph, open questions to vector search, and some to both.
5. Validate generated queries. A model writing graph queries can write wrong ones. Allow reads only, and check results that look implausible, such as an empty list.
6. Keep the graph current. A graph built once goes stale as the documents change.

For the vector side, see vector databases explained and semantic search vs keyword search. For the overall design, see RAG architecture explained.

Common mistakes

• Building a graph before finding the questions that need it.
• Extracting everything with an LLM when the facts already exist in structured form.
• Expecting embeddings to filter by exact values such as versions, dates or IDs.
• Trusting generated graph queries without validation.
• Letting the graph and the documents drift apart.

Retrieval-augmented generation, including document indexing and retrieval methods, is covered in the Generative AI course.

Sources

• From Local to Global: A Graph RAG Approach to Query-Focused Summarization (arXiv) — Edge et al.
• Unifying Large Language Models and Knowledge Graphs: A Roadmap (arXiv) — Pan et al.
• PEP 1: PEP Purpose and Guidelines (Python Enhancement Proposals) — Python Software Foundation
• MultiDiGraph (NetworkX documentation) — NetworkX