kgdiff architecture
git diff for knowledge graphs. kgdiff tells you, at a glance, what changed between two versions of a graph — and lets you review it like a pull request.
This document is the source of truth for how the project is put together. Algorithms are specified in algorithms.md, the visual language in visual-language.md, the viewer's behaviour in interaction.md and the patch format in delta-format.md.
Positioning
AI systems now write and rewrite knowledge graphs: GraphRAG pipelines, agent memories, ontology assistants, semantic layers. Humans have to review those changes the way they review AI-written code. Existing tools show ontology changes as tables or trees, or recolor nodes on a re-run force layout so everything jumps. kgdiff is built around four ideas:
- Semantic, not syntactic. A merge is a merge, a rename is a rename, a moved class is a move — not "one node deleted, one node added".
- One mental map. Both versions share one stable layout. Nothing moves unless it changed.
- Color is meaning. Five meaning families (added, removed, content, structure, identity) and gray for context. Nothing else gets a color.
- Review is a workflow. Changes are grouped into hunks you can step through, replay, mark as reviewed and export as an invertible delta.
Design principles
- Deterministic. Same input + same options → byte-identical output (diff JSON, layout, hunk order). Seeded PRNGs only; no
Math.random, noDate.now()in results. - Pure core, thin shells. Algorithms are pure functions over immutable data. I/O, DOM and timers live only in
rendererandviewer(and in the nativekgdiffcommand line). - Contracts first. Each package exposes a small typed API (
src/index.ts). Internals are free to change; contracts change only with this document. - Zero-config, fully configurable. Good defaults for every option, every default documented.
- Accessible by construction. Contrast is tested, color is never the only cue, motion respects
prefers-reduced-motion, everything is keyboard-operable. - Small and fast. Budgets below are enforced by benchmarks and size checks, or measured and recorded (the engine's, since 0.11).
- Isomorphic.
core,layoutandscenerun unchanged in browsers, Node, Deno, Bun and workers.
Packages
@kgdiff/core model and read path: normalize, JSON transports, delta, hunk titles; diff (compute)
@kgdiff/layout layout document, radii, label widths; stable union layout (compute)
@kgdiff/compute kgdiff's Rust engine in WebAssembly: diff, parsers, layout
@kgdiff/scene diff semantics → visual primitives: tokens, encodings, replay, focus
@kgdiff/renderer Canvas 2D engine: camera, LOD, labels, picking, swipe, minimap (DOM)
@kgdiff/viewer <kgdiff-viewer> web component and its elements: modes, change list, details, review (DOM)
@kgdiff/g6 AntV G6 v5 adapter: render a kgdiff scene inside a G6 graph (peer: @antv/g6)
kgdiff CLI: terminal diff, JSON / delta / Markdown, single-file HTML report
(`@kgdiff/cli`: an npm launcher of the native Rust binary, no TypeScript compute)
crates/ Rust: kgdiff-core, -formats, -layout, -report, the `kgdiff` binary, kgdiff-wasm
(built into `@kgdiff/compute`)
apps/site landing page + playground (drag two files in, get a diff)Dependency graph (arrows point at dependencies; each package also depends on core directly, and viewer on layout and scene as well):
core ◀── layout ◀── scene ◀── renderer ◀── viewer
scene ◀── g6@kgdiff/compute is not in the graph, although core, layout and viewer list it in their dependencies: installing any of them installs it, and compute and the two model packages depend on each other in package.json. No module imports the other back when it loads: compute imports core and layout (their types and read path), while core and layout load compute only with a dynamic import() when a function that computes is first called, and declare the few functions they call instead of importing its types (compute's tests check them). The viewer loads it on demand too (layouts, diffs, and the parsers for text sources), so a bundle that only reads reports contains no WebAssembly. The parsers' types (ParseOptions, ParseResult, FormatId, …) and FORMAT_EXTENSIONS are defined by @kgdiff/core and re-exported by @kgdiff/compute. Since 0.11 TypeScript keeps only what reads a computed diff synchronously (tests/read-path.ts); the engine itself is the Rust one. @kgdiff/cli is not in the graph: it holds no TypeScript compute, only a launcher of the Rust kgdiff binary. The Rust crates (kgdiff-core, kgdiff-formats, kgdiff-layout, kgdiff-report) implement the same contracts as core and layout; the conformance corpus keeps both byte-identical (RFC 0002, docs/rfcs/0002-rust-compute-core.md).
Data flow
text ──compute.parseGraph─▶ GraphInput ×2
──core.diff──────────▶ DiffResult (union graph + facets + hunks + delta + stats)
──layout.layoutDiff──▶ LayoutResult (one position per union node)
──scene.buildScene───▶ Scene (indices, roles, families, titles, timeline)
──resolver.resolve(view)──▶ FrameVisuals (per frame: what to draw)
──renderer.setFrame──▶ pixelsThe CLI (the Rust kgdiff-report) runs everything up to layoutDiff natively and embeds packDiffJSON(diffToJSON(…)) + layoutToJSON in the HTML report (ReportPayload), so the browser only builds the scene and renders. Reports are reproducible and open instantly. A payload may also leave the layout out (an application that computed the diff itself): the viewer then runs layoutDiff with its default options when it reads the payload, with the compute module, and still never the diff engine. The packed diff stores the unchanged elements (most of a large diff) as tables of indices into one string table: for 100k nodes / 300k edges, 28% of the bytes and 46% once gzipped (edges with a label or attributes of their own are not packed, so diffs of such graphs shrink less). The viewer unpacks it and reads it with diffFromJSON, which checks that the document is consistent before anything is drawn. Rebuilding the two graphs is most of that read: the snapshots are already canonical, so they are read straight into graphs (each checked to be what normalize would keep as it is), and only a document that is not, such as one with parallel edges, is normalized again. Either way their text (labels, aliases, types) is taken as written, never composed to NFC again with the browser's Unicode tables: the content hashes in the delta check it, so a report opens the same way in every browser.
Package contracts (summary)
| Package | Main API |
|---|---|
| core | normalize, diff, matchNodes, applyDelta, invertDelta, hashGraph, diffToJSON/diffFromJSON, packDiffJSON/unpackDiffJSON, formatHunk, facetLabel, textSimilarity, predicateLabel |
| layout | layoutDiff, extendLayout, nodeRadius, estimateLabelWidth, layoutToJSON/layoutFromJSON |
| scene | getTheme, buildScene, createVisualResolver, createViewState, computeFocus, frameBounds, contrastRatio, hunkFamily; experimental shapes option and outline functions |
| renderer | createRenderer (setFrame, camera, pick, toDataURL; experimental addLayer: the host draws under and over the graph), createMinimap, labelFootprint |
| viewer | <kgdiff-viewer> (load, payload, panels, selectHunk, next, prev, play, …), defineViewer; composable elements (<kgdiff-root>, <kgdiff-stage>, …) |
| g6 | toG6Data, createDiffGraph |
| cli | kgdiff <before> <after> [options], kgdiff apply <graph> <delta> |
The full, documented signatures live in each package's src/index.ts (and src/types.ts).
The JSON documents kgdiff writes are contracts too: graphs (kgdiff.graph), diffs (kgdiff.diff), packed diffs (kgdiff.diff.packed, in reports), deltas (kgdiff.delta), layouts (kgdiff.layout) and report payloads (kgdiff.report) each carry their format and version, and each has a JSON Schema in packages/core/schema/ (graph.v1.json, diff.v1.json, diff-packed.v1.json, delta.v1.json, layout.v2.json, report.v1.json, published with @kgdiff/core). Tests validate everything kgdiff writes against them, so a change to these formats changes its schema in the same commit; an incompatible change bumps the version. Layouts have two versions. kgdiff's Rust layout engine (crate kgdiff-layout) writes version 2, which layout.v2.json describes: version 1's members plus generator, a non-empty string such as "kgdiff-layout/1" that names the engine generation that computed the positions. layoutToJSON of @kgdiff/layout writes version 2 for a layout with a generator (every layout computed since 0.11) and version 1 for one without (as 0.x wrote them), and layoutFromJSON reads both. Positions from either version are valid pins. A report payload holds a diff (packed or not), its layout of either version or none, meta and view (report.v1.json). The crate kgdiff-report writes it, with the layout of the default options (report_payload) or the one the application gives it (report_payload_with, RFC 0003), and <kgdiff-viewer> reads it. Later minor versions add optional members to view, which older viewers ignore, so the schema allows members of view it does not name.
Formats: mapping conventions
All parsers produce the same GraphInput shape:
| Concept | RDF (Turtle, N-Triples, N-Quads, TriG, RDF/XML, JSON-LD) | OBO | JSON |
|---|---|---|---|
| node id | IRI; OBO PURLs → CURIE (GO:0008150); blank nodes ([], rdf:nodeID, JSON-LD _: or no @id) → hashed _:b… (see below) | id: | id / key / data.id |
| label | rdfs:label, skos:prefLabel, schema:name, … (language preference over @en, xml:lang, @language) | name: | label / name / title |
| types | rdf:type, typed node elements, @type (not edges by default) | stanza type (Term, Instance) | type / types / category / … |
| aliases | skos:altLabel, oboInOwl synonyms | synonym: | aliases / synonyms |
| attrs | other literal-valued properties (compact predicate → value; repeated → sorted array) | def, namespace, xref, comment, … | remaining fields |
| edges | IRI-valued properties (rdf:resource, JSON-LD @id values and @reverse); OWL existential restrictions → C –R→ D | is_a, relationship: | edges / links / elements.edges |
| deprecated | owl:deprecated true | is_obsolete: true | deprecated |
| replacedBy | IAO:0100001 (term replaced by) | replaced_by: | replacedBy |
Every RDF syntax is first read into RDF quads — Turtle, N-Triples, N-Quads and TriG by n3, RDF/XML and JSON-LD by kgdiff's own synchronous readers (rdfxml.ts on a small XML parser, jsonld.ts) — and one mapper (rdf.ts) turns quads into GraphInput, treating the graph as a set (repeated triples count once). The same graph in any RDF syntax therefore gives the same GraphInput, hashGraph and diff.
- RDF/XML follows the whole RDF 1.1 XML Syntax:
rdf:about/rdf:ID/rdf:nodeID, typed node elements, property attributes,rdf:li,xml:baseandxml:langscoping,rdf:parseTypeResource,CollectionandLiteral(an exclusive-canonical XML literal), and reification byrdf:ID. Entities declared in the DTD (as older Protégé versions write them) are expanded; external entities and DTDs are never loaded, and expansion is capped. An OWL/XML document read as RDF/XML fails with a conversion hint, and a GraphML or GEXF one with the format to read it with. - JSON-LD 1.1 is expanded and converted to RDF per the W3C algorithms. Contexts are inline or come from the caller's synchronous
jsonld.documentLoader; nothing is fetched, so a remote@contextwithout a loader is an error. Without a base IRI, relative IRIs stay relative (as in Turtle) instead of being dropped. Keys that expand to no IRI are dropped with ajsonld-unmapped-termswarning,@directionis not represented, named graphs are merged (named-graphs), and documents nested deeper than 200 levels are rejected.
Predicates and types are compacted only with well-known prefixes (plus prefixes the caller passes in rdf.prefixes), so their identity never depends on the @prefix declarations of a particular file: the same graph serialized as Turtle or as N-Triples diffs as identical. Prefixes declared in a file (@prefix, xmlns:, JSON-LD prefix terms) are returned in ParseResult.prefixes for display only.
Edge labels derive from the predicate alone (rdfs:subClassOf → subClassOf, part_of → part of; opaque ids such as BFO:0000050 stay whole), so a property declaration appearing or disappearing never relabels edges. Names a file gives its relations (an RDF property's own rdfs:label, OBO [Typedef] names) are returned as ParseResult.predicateLabels and graph.meta.predicateLabels for display.
Blank nodes used by exactly one subject / predicate and not on a cycle are skolemized by context: _:b + hash(parent id, predicate, content), so alice :knows [] and bob :knows [] stay two nodes. Shared, unreferenced and cyclic blank nodes are identified by content alone (cycles by colour refinement); structurally identical ones share an id.
Statement annotations (owl:Axiom, rdf:Statement, RDF 1.2 {| |}) are folded into the attrs of the annotated edge (or node, for literal statements) instead of becoming nodes (rdf.foldAnnotations, default true). OBO alt_id also populates replaces, so merged terms are recognised from their alternative ids.
kgdiff JSON reads core's graphToJSON output losslessly (types, implicit; a label is never taken for the predicate). Its optional marker (format: "kgdiff.graph", version: 1) skips shape detection; another kgdiff.* format (a diff, a delta) or graph version is rejected with unsupported-version, while a format field outside the kgdiff. namespace is ignored. Fields a JSON dialect does not map (rendering state, G6 shape types, …) are dropped with a json-ignored-fields warning. Values nested deeper than 1000 levels are rejected with invalid-input. A number beyond the range of a double (1e400, which JSON.parse reads as Infinity) is kept as the string "Infinity" or "-Infinity", as normalize keeps non-finite numbers, with a json-non-finite warning; a lone surrogate escape ("\ud800", half of a UTF-16 pair), which JSON.parse accepts, is rejected with invalid-input, in JSON-LD and deltas too, so that kgdiff's text is well-formed Unicode in every implementation (RFC 0002, D-2 and D-11).
Budgets
| What | Budget |
|---|---|
diff, exact ids, 10k nodes / 30k edges | < 150 ms (WebAssembly in Node, including the transport to DiffResult; M-class laptop) |
diff, exact ids, 100k nodes / 300k edges | < 2 s (same) |
normalize memory, 100k nodes / 300k edges | < 80 MB of WebAssembly linear memory; < 50 MB resident growth natively |
| similarity matching, 5k unmatched on each side | < 800 ms (WebAssembly) |
layoutDiff, 2k nodes | < 450 ms (WebAssembly) |
buildScene, 10k nodes | < 50 ms |
resolve per frame, 5k nodes / 10k edges | < 4 ms, zero steady-state allocations |
| pan / zoom, 5k nodes / 10k edges | 60 fps |
| viewer standalone bundle (min + gzip, without parsers and compute add-on) | < 130 kB (target 90 kB) |
| HTML report overhead (without data or compute add-on) | < 135 kB gzip |
compute.wasm (core and layout, no parsers), gzip | < 400 kB |
The compute rows are the targets of RFC 0002 and, since 0.11, they are measured and recorded, not enforced by a test: the engine is Rust, its native timings are cargo bench (divan) and the sizes are CI's limits on the modules. The rows from buildScene to the viewer bundle are still enforced by Vitest benchmarks and size tests. What 0.11 measured, and which targets it did not reach, is in the RFC's Phase 5 results.
Engineering conventions
- TypeScript 7, strict,
noUncheckedIndexedAccess, ESM only, Node ≥ 22, evergreen browsers. - Rust (
crates/, one Cargo workspace):cargo test --workspace,cargo clippy,cargo fmt; the crates and the TypeScript packages share one version number and are checked against the same conformance corpus, which the Rust crates generate (cargo xtask conformance;pnpm conformance:replayreplays its CLI runs). - Relative imports use
.jsextensions (NodeNext). Cross-package imports use the package name; in development@kgdiff/*resolves topackages/*/src/index.ts(seetsconfig.base.json,vitest.shared.ts), so no package needs building before tests; only the WebAssembly modules of@kgdiff/computedo, once (CONTRIBUTING.md). - Tests: Vitest, colocated in
packages/*/test. Core uses property-based tests (fast-check). Unit tests assert no wall-clock times; the budgets above are checked by Vitest benchmarks (test/*.bench.ts,pnpm bench), which run the TypeScript source through Vite's module runner and so measure upper bounds. - Lint / format: Biome (
pnpm lint,pnpm format). - No new runtime dependency without a written justification in the PR / review.
- Errors: throw
KgdiffErrorwith a stablecode; never throw strings. - Public functions have TSDoc that states defaults, complexity when non-obvious, and edge cases.
- Commands:
pnpm test,pnpm typecheck,pnpm lint,pnpm build,pnpm check(all three),pnpm bench,pnpm check:packages(the packed tarballs, afterpnpm build).