M01 · Knowledge Graph Fundamentals

Learning objectives

Nodes, edges, and why the types matter

{
  "nodes": [
    { "id": "function:shared.auth.decode_jwt",
      "kind": "function",
      "name": "decode_jwt",
      "file": "shared/auth.py", "line": 16 }
  ],
  "edges": [
    { "source": "function:shared.auth.verify_token",
      "target": "function:shared.auth.decode_jwt",
      "type": "calls",
      "provenance": "EXTRACTED" }
  ]
}

Read that edge aloud and you get a sentence: "verify_token calls decode_jwt — and we extracted that fact directly from the source." A graph is a database of such sentences. Everything else in this course is machinery for producing, storing, serving, and trusting them.

Traversal vs search — the determinism dividend

A map is only useful if following it is cheaper than wandering. Here's the precise sense in which it is.

To answer "who calls decode_jwt?" without a graph, an agent searches: grep for the name (getting every mention — imports, comments, strings), open each candidate file, and read enough surrounding code to judge which hits are real call sites. The cost is proportional to the number and size of files touched, and the result is a judgment call. Run it twice, phrase the question differently, and you may get different answers.

With a graph, the agent traverses: look up the node, follow its incoming calls edges, done. The cost is proportional to the number of edges followed — usually a handful — and the answer is a fact retrieved, not a text interpreted. Same question, every time, same answer. That repeatability is what the course means by deterministic: no similarity thresholds, no ranking, no luck.

This is also the moment to name the complexity honestly. Search costs O(files × file size) in tokens per query, paid every query. Traversal costs O(edges followed) — after a one-time extraction cost paid when the graph is built. Extraction moved the expensive work out of the query path. You'll hear this called "compile once, query forever," and it's the same economic trick a database index plays.

Multi-hop reasoning — where flat retrieval structurally fails

Some questions cannot be answered from any single file, no matter how cleverly you retrieve it. Consider: "What breaks in the API layer if I alter the schema in db/migrations/04_users.sql?" The answer requires chaining facts: the migration alters a table → a model class maps that table → a repository uses the model → three route handlers call the repository. Four files. The connecting facts never co-occur in one place; each hop lives in a different file, and some hops (the model↔table mapping) are implicit.

A graph answers this by construction: it's a path. Start at the table node, walk maps_to → used_by → called_by edges, and the four-file chain falls out as a sequence of lookups. In orderflow miniature: change decode_jwt's claims format, and the graph walks decode_jwt ← verify_token ← post_invoice — two hops from an auth helper to a billing route that never mentions JWTs at all.

Hold this example: in M02 you'll see exactly why chunk-based retrieval cannot make this chain (the hops are never co-located in a chunk), and in M10 "multi-hop reasoning failure" becomes the first of two formal triggers that justify adding a structural graph to a production stack.

Communities — subsystems the graph discovers by itself

God nodes and the price of centrality

Watch the animation's final frames: DatabasePool is reached by billing and orders, while publish is the one that actually touches all three communities. Which of them is "the god node" depends entirely on which measure you ask, and orderflow is small enough that you can check every answer by hand.

Graph tools call the winners god nodes: the main characters of your codebase, identified by centralityA family of graph measures scoring how "important" a node is — by how many edges it has (degree), or how many shortest paths run through it (betweenness). measures. The corpus definition is memorable and accurate: "the classes everything else depends on — we call these God Nodes because if they die, the universe ends."

Why you care, concretely: a god node is where refactoring risk, review scrutiny, and onboarding attention should concentrate. On orderflow that is shared/db.py — not because it is the most connected (it is not) but because it has the largest blast radius: change it and seven functions across billing and orders can change behaviour. A new engineer (or agent) reading the graph learns in seconds what might take weeks of tribal exposure: this is the file you don't touch casually.

Now the honest cost accounting. The strictest centrality measure — betweenness centrality, which counts how many shortest paths pass through each node — costs O(V×E): nodes times edges. On orderflow (36 nodes, 22 edges) that's nothing. On a real monorepo it's a wall: one documented case in the corpus involved a 450,000-node, 690,000-edge graph — roughly 310 billion operations, single-threaded, because the algorithm doesn't parallelize cleanly. A full rebuild on a 96-core Xeon was killed after 114 minutes without completing, while a different (smaller) repo finished in ~10 minutes on a laptop. Remember this number in M11: it's why "just rebuild the graph on every commit" stops being a plan at scale, and why cheap proxies like plain degree count (which our lab uses) are often the right engineering choice.

Blast radius — impact analysis as a graph walk

The single most valuable query a code graph answers is the one that prevents outages: "if I change this, what could break?" The graph formulation is clean: the blast radius of a node is everything reachable by walking incoming call edges transitively — callers, callers-of-callers, and so on. It's a breadth-first searchBFS: explore a graph level by level from a starting node, using a queue and a visited-set so nothing is processed twice. over the reversed graph, about ten lines of code, and you write it below.

Mature tools score the result rather than just listing it. okf-rs's impact command, for instance, ranks every changed concept between two git refs by three factors: transitive-caller count (the raw radius), public-API membership (external consumers can't be refactored alongside you), and cycle participation (changes inside dependency cycles propagate unpredictably). Its review subcommand turns that into a PR comment with a --fail-on-risk CI gate — impact analysis promoted from a query to a policy.

The corpus example that sells the feature: a developer asks, "if I delete this 'deprecated' method, will the payment gateway explode?" — and the graph shows the 14 hidden dependencies that say Yes. Fourteen facts no one person remembered, retrieved in milliseconds.

Provenance — the honesty layer

One primitive remains, and it's the one that separates trustworthy graphs from confident guessers.

Not every edge is equally certain. When a parser sees decode_jwt(token) inside verify_token's body in the same module, the call edge is a fact. But when code calls execute(...) and three different classes define an execute method, the extractor must guess — or admit it can't. Serious tools label every edge:

One reviewer in the corpus called this labeling "the whole argument" for graph tools: it is the only approach in the codebase-context landscape that tells you which of its answers are facts and which are guesses. Grep doesn't. Vector search certainly doesn't — every RAG result arrives with the same confident tone regardless of quality (M02 makes this failure visceral). A machine-readable confidence label is what lets an agent act boldly on EXTRACTED edges and double-check INFERRED ones — exactly the policy you'll implement in the lab's final step.

Where do dynamic languages fit? Python and JavaScript — where, as the corpus jokes, types are merely suggestions — force more INFERRED edges because names can't be resolved statically. M03 shows the resolution ladder (heuristics → language servers → honest AMBIGUOUS labels). The discipline stays the same: never emit a guess dressed as a fact.

Walk it, step by step

Build the graph by hand now — nodes, then edges, then the provenance that decides whether an edge can be trusted. Watch how few edges a parser can prove outright.

Code walkthrough — the whole toolkit in 40 lines

Let's build every primitive from this module over orderflow's real graph. The extractor (labs/shared_tools/kg_extract.py) has already produced graph.json — 36 nodes, 22 edges, each edge provenance-tagged. We'll write three functions: a reverse index, a direct-callers query, and a provenance-aware blast radius.

Chunk 1 — the reverse index. Edges are stored source→target ("who do I call?"), but impact questions run the other way ("who calls me?"). Rather than scanning all edges per query, we index them once by target. This tiny dict IS the difference between search and traversal: after this line, "who calls X" is a hash lookup. Gotcha: filter to calls edges — in richer graphs, walking imports edges into a blast radius wildly overstates impact.

Chunk 2 — direct callers. Resolve a human-friendly short name ("decode_jwt") to node ids, then read the reverse index. Note the deliberate handling of misses: an empty list, not an exception — in M09 the same behavior becomes the graceful "not in graph, try grep" MCP response that lets agents fall back safely.

Chunk 3 — blast radius with a confidence gate. A textbook BFS with a queue and a visited-set (the visited-set matters: real graphs have cycles, and without it you loop forever). The one addition worth staring at: when min_confidence="EXTRACTED", the walk skips unverified edges — computing the radius you can prove versus the radius you suspect. Two numbers, and the gap between them is your uncertainty, made visible.

import json
from collections import defaultdict, deque

graph = json.load(open("graph.json", encoding="utf-8"))
short = lambda node_id: node_id.rsplit(".", 1)[-1]

# ---- Chunk 1: index edges by TARGET, once ----
reverse = defaultdict(list)
for edge in graph["edges"]:
    if edge["type"] == "calls":
        reverse[edge["target"]].append(edge)

# ---- Chunk 2: direct callers, with graceful misses ----
def callers(name):
    targets = [n["id"] for n in graph["nodes"] if short(n["id"]) == name]
    found = {short(e["source"]) for t in targets for e in reverse.get(t, [])}
    return sorted(found)          # unknown name -> [] (never a crash)

# ---- Chunk 3: BFS blast radius with a confidence gate ----
def blast_radius(name, min_confidence=None):
    seeds = [n["id"] for n in graph["nodes"] if short(n["id"]) == name]
    queue, visited, impacted = deque(seeds), set(seeds), set()
    while queue:
        for edge in reverse.get(queue.popleft(), []):
            if min_confidence == "EXTRACTED" and edge["provenance"] != "EXTRACTED":
                continue          # skip guesses when proof is demanded
            if edge["source"] not in visited:
                visited.add(edge["source"])
                impacted.add(short(edge["source"]))
                queue.append(edge["source"])
    return sorted(impacted)

print(callers("decode_jwt"))                     # ['verify_token']
print(blast_radius("decode_jwt"))                # [... 'post_invoice', 'verify_token']
print(blast_radius("execute"))                   # everything touching the DB pool
print(blast_radius("execute", "EXTRACTED"))      # ...the provable subset

import { readFileSync } from "node:fs";

const graph = JSON.parse(readFileSync("graph.json", "utf-8"));
const short = (id) => id.split(".").at(-1);

// ---- Chunk 1: index edges by TARGET, once ----
const reverse = new Map();
for (const edge of graph.edges) {
  if (edge.type !== "calls") continue;
  if (!reverse.has(edge.target)) reverse.set(edge.target, []);
  reverse.get(edge.target).push(edge);
}

// ---- Chunk 2: direct callers, with graceful misses ----
function callers(name) {
  const targets = graph.nodes.filter((n) => short(n.id) === name).map((n) => n.id);
  const found = new Set();
  for (const t of targets) for (const e of reverse.get(t) ?? []) found.add(short(e.source));
  return [...found].sort();            // unknown name -> [] (never a crash)
}

// ---- Chunk 3: BFS blast radius with a confidence gate ----
function blastRadius(name, minConfidence = null) {
  const seeds = graph.nodes.filter((n) => short(n.id) === name).map((n) => n.id);
  const queue = [...seeds], visited = new Set(seeds), impacted = new Set();
  while (queue.length) {
    for (const edge of reverse.get(queue.shift()) ?? []) {
      if (minConfidence === "EXTRACTED" && edge.provenance !== "EXTRACTED") continue;
      if (!visited.has(edge.source)) {
        visited.add(edge.source);
        impacted.add(short(edge.source));
        queue.push(edge.source);
      }
    }
  }
  return [...impacted].sort();
}

console.log(callers("decode_jwt"));                  // ['verify_token']
console.log(blastRadius("decode_jwt"));              // [..., 'post_invoice', 'verify_token']
console.log(blastRadius("execute", "EXTRACTED"));    // the provable subset

Hands-on lab — labs/M01-graph-fundamentals

📂 Get the files: labs/M01-graph-fundamentals on GitHub — or clone the whole course once: git clone https://github.com/varasrinivas/knowledge-graph-course.git

What you'll build: the file above, from a TODO skeleton, verified by automated checks. Time: 30–45 min. Files: starter/graph_basics.py (yours), solution/ (if stuck), expected_output/sample_output.txt.

1. Step 1 — Load the graph. cd labs/M01-graph-fundamentals/starter && python graph_basics.py. The loader runs the extractor for you. Expected: 36 nodes, 22 edges loaded. ✅ If you see an import error, run from inside starter/.
2. Step 2 — TODO 1: the reverse index. Loop over graph["edges"], append each calls edge under its target.
3. Step 3 — TODO 2: BFS blast radius. Seed a deque with matching node ids; walk the reverse index with a visited-set. blast_radius("decode_jwt") must include post_invoice — two hops away.
4. Step 4 — TODO 3: the confidence gate. Skip non-EXTRACTED edges when demanded; compare both radii for execute.
5. Verify. python graph_basics.py --check → ALL CHECKS PASSED. 🎉

Troubleshooting: empty blast radius almost always means you walked edges forward (caller→callee) instead of backward. KeyError: 'edges' means the loader was edited — diff against the solution.

Stretch goal: compute each node's in-degree from the reverse index and print the top 3. The winner should be orderflow's god node. You've just implemented (degree) centrality — the cheap cousin of the O(V×E) betweenness measure from this module.

Knowledge check

Module summary

What we built on orderflow: a 36-node, 22-edge graph plus reverse index, callers query, and provenance-gated blast radius — the exact primitives every later module refines.

Next — M02: The RAG Baseline and Where It Breaks. Before adopting graphs everywhere, you need the disease in your hands: you'll build a retrieval pipeline over orderflow's docs and watch it confidently return a stale metric definition — nothing crashing, everything wrong.

References

• Course extractor: labs/shared_tools/kg_extract.py · ground-truth edges: labs/sample-project/README.md
• Leiden algorithm (Traag, Waltman & van Eck) — used by Graphify for community detection
• Clauset–Newman–Moore modularity clustering — used by okf-rs graph communities
• okf-rs impact analysis (impact, review --fail-on-risk) — github.com/jyjeanne/okf-rs
• Graphify god-node and community reporting — graphify.net · GRAPH_REPORT.md format (M04)