Graph Data Modeling

Designing temporal graphs for audit-trail compliance

You need to prove, on demand, exactly what an entity looked like at any past instant — the state of a customer record on the day a transaction cleared, the terms of a contract before an amendment, the permission set a user held when an action was taken. Regulatory frameworks (SOC 2, HIPAA, GDPR, FINRA) all require this kind of immutable historical reconstruction, and a mutable property graph cannot supply it: once you overwrite a value, the prior state is gone. This page shows how to model audit history in Neo4j 5.x as an append-only temporal graph — each change materialized as a discrete, immutable snapshot node linked by a unidirectional SUPERSEDED_ON chain — and how to write, index, and query it so point-in-time reconstruction stays deterministic and fast as the history grows into the millions of nodes.

Prerequisites

Why append-only, not mutable properties

The most common compliance failure is embedding history into an array or JSON string on a single node. That forces the storage engine to deserialize a growing payload on every traversal, destroys index selectivity, inflates heap pressure, and makes point-in-time reconstruction impossible to express in Cypher. The disciplined alternative is to treat temporal state as a first-class graph construct: never mutate the old value in place, materialize each state transition as its own immutable node, and keep the live node lightweight and query-optimized. Audit trails then become explicit graph paths you can traverse, verify, and even hash-chain — not hidden strings.

The diagram below shows the unidirectional SUPERSEDED_ON chain linking the current node to immutable historical snapshots.

The unidirectional SUPERSEDED_ON chain Four circles in a row. On the left, a blue :Customer node marked "current" is the live head. A single SUPERSEDED_ON edge dated 2026-05-14 points right to an amber :HistoricalState node "Snapshot v3". From there a 2026-03-02 edge points to "Snapshot v2", and a 2026-01-08 edge points to "Snapshot v1", the oldest. All arrows point the same way, so an active node has at most one outgoing edge and the history reads newest to oldest. SUPERSEDED_ON2026-05-14 SUPERSEDED_ON2026-03-02 SUPERSEDED_ON2026-01-08 :Customer current · live :HistoricalState Snapshot v3 :HistoricalState Snapshot v2 :HistoricalState Snapshot v1 newest state oldest snapshot One outgoing edge per active node — the chain never forks or reverses.

Two rules make this topology deterministic. First, label separation: keep :Customer / :Transaction / :Contract for live state and reserve :HistoricalState / :AuditSnapshot for archived versions, so routine CRUD never accidentally traverses history. Second, a strict relationship cardinality and directionality policy: model progression as a single-direction chain where every active node has exactly zero or one outgoing :SUPERSEDED_ON edge. Avoid bidirectional :HISTORY or :PREVIOUS edges — they create cycle ambiguity and force the planner to evaluate redundant traversal directions.

Step 1 — Constraints and the temporal index

Anchor the entity key with a uniqueness constraint, then index the relationship timestamp so reconstruction resolves through a range scan rather than walking the whole chain. Neo4j 5.x supports indexes on relationship properties.

cypher
// Anchor the live entity so every MATCH seeks a unique index.
CREATE CONSTRAINT customer_id IF NOT EXISTS
FOR (c:Customer) REQUIRE c.id IS UNIQUE;

// Range index on the temporal edge property drives point-in-time filters.
CREATE INDEX idx_superseded_timestamp IF NOT EXISTS
FOR ()-[r:SUPERSEDED_ON]-() ON (r.timestamp);

Step 2 — The transactional snapshot write

Transactional integrity is non-negotiable: a snapshot that is created without its chain edge, or a live node updated without a snapshot, corrupts the audit trail permanently. Wrap the whole transition in one managed transaction so it commits atomically or not at all. The write clones the node’s prior state into an immutable :HistoricalState node, links it with a single SUPERSEDED_ON edge carrying changed_by provenance, and only then updates the live node.

The snapshot write: prior state materialized as a new immutable link Two panels. Left, labelled BEFORE write: a blue live :Customer node with state free links downward through a SUPERSEDED_ON edge to an amber :HistoricalState snapshot with state basic. Right, labelled AFTER write: the same live :Customer node now shows state enterprise; directly below it a teal-highlighted new :HistoricalState snapshot holding the prior state free is spliced in, its incoming SUPERSEDED_ON edge stamped with timestamp and changed_by; below that the older basic snapshot remains untouched. The live node keeps exactly one outgoing edge and no historical node is ever mutated. BEFORE write AFTER write SUPERSEDED_ON { timestamp, changed_by } :Customer · live state: free :HistoricalState state: basic SUPERSEDED_ON { timestamp, changed_by } SUPERSEDED_ON :Customer · live state: enterprise :HistoricalState state: free :HistoricalState state: basic NEW
python
from neo4j import GraphDatabase

def append_audit_snapshot(tx, entity_id: str, new_state: dict, user_id: str):
    # Read the current node inside the same transaction so the snapshot
    # reflects exactly the state we are about to supersede (no read/write race).
    record = tx.run(
        "MATCH (c:Customer {id: $id}) RETURN c AS current",
        id=entity_id,
    ).single()
    if record is None:
        raise ValueError(f"Entity not found: {entity_id}")
    current = record["current"]

    # Snapshot the OLD state, chain it, then move the live node forward.
    # The WHERE guard asserts the node is the chain head (0 outgoing edges),
    # so a concurrent write cannot fork the history.
    tx.run(
        """
        MATCH (c:Customer {id: $id})
        WHERE NOT (c)-[:SUPERSEDED_ON]->()
        CREATE (snap:Customer:HistoricalState {
            id:          $id,
            state:       $old_state,
            captured_at: datetime(),          // timezone-aware, always
            version:     $version
        })
        CREATE (c)-[:SUPERSEDED_ON {
            timestamp:  datetime(),
            changed_by: $user_id
        }]->(snap)
        SET c.state = $new_state, c.updated_at = datetime()
        """,
        id=entity_id,
        old_state=dict(current),
        version=current.get("version", 0) + 1,
        new_state=new_state,
        user_id=user_id,
    )

uri = "neo4j+s://your-cluster.databases.neo4j.io"
with GraphDatabase.driver(uri, auth=("neo4j", "password")) as driver:
    with driver.session(database="compliance_db") as session:
        # execute_write retries the whole unit on transient/deadlock errors.
        session.execute_write(
            append_audit_snapshot,
            "CUST-9921",
            {"tier": "enterprise"},
            "admin@corp.com",
        )

Always use datetime() (timezone-aware) rather than localdatetime() for every audit timestamp. Compliance audits routinely span jurisdictions, and a normalization failure invalidates the legal timeline. The choice of native temporal types over string timestamps is covered in graph data type selection; for audit trails it is mandatory, not stylistic.

Step 3 — Reconstruct state as of a datetime

The reconstruction query is where naive designs collapse: an unbounded expansion like MATCH (n)-[:SUPERSEDED_ON*]->(h) triggers a full traversal and can exhaust memory. The correct form bounds the depth, filters every edge on the requested instant, and returns the single closest snapshot.

cypher
MATCH (current:Customer {id: $customer_id})
OPTIONAL MATCH path = (current)-[r:SUPERSEDED_ON*0..100]->(historical:Customer)
WHERE ALL(rel IN relationships(path) WHERE rel.timestamp <= $as_of_datetime)
RETURN
  historical,
  reduce(m = null, rel IN relationships(path) |
    CASE WHEN m IS NULL OR rel.timestamp < m THEN rel.timestamp ELSE m END
  ) AS snapshot_timestamp
ORDER BY snapshot_timestamp DESC
LIMIT 1;

The *0..100 bound lets the query return the live node itself when $as_of_datetime is “now”, and caps traversal cost otherwise. Tighten 100 to whatever your retention policy allows.

Validation & verification

Confirm two invariants before trusting the trail. First, no active node may have more than one outgoing chain edge — a forked history means a concurrent write slipped past the guard:

cypher
// Expect zero rows. Any result is a corrupted (forked) chain head.
MATCH (c:Customer)-[:SUPERSEDED_ON]->()
WITH c, count(*) AS out_edges
WHERE out_edges > 1
RETURN c.id AS forked_entity, out_edges;

Second, verify the reconstruction query seeks the index instead of scanning. Run it under PROFILE: the plan should open with a NodeUniqueIndexSeek on :Customer(id) and use the relationship index for the timestamp filter. If PROFILE shows an Expand(Into) with no index or a large db hits count, confirm idx_superseded_timestamp is ONLINE — after creating indexes, block on CALL db.awaitIndexes(300) before running production reads so the planner has a live index to bind to.

Scaling and governance

Audit graphs only grow, so plan for volume and access control from the start.

  • Partition by time or tenant. Once chains exceed millions of nodes, apply graph partitioning strategies: archive snapshots older than your retention window to a cold instance, route per-tenant history to separate databases via multi-database, and tag archival nodes with a :Partition {year, quarter} label for fast pruning.

  • Separate read roles with RBAC. Give compliance auditors read-only reach into history without exposing live-node mutation. Run against the system database:

    cypher
    CREATE ROLE compliance_ro IF NOT EXISTS;
GRANT READ {*} ON GRAPH compliance_db NODES HistoricalState TO compliance_ro;
DENY WRITE ON GRAPH compliance_db TO compliance_ro;

  • Hash-chain for tamper evidence. For high-assurance environments, compute a SHA-256 over each snapshot’s property map at creation and store it as payload_hash; verification becomes a traversal comparing each node’s stored hash against a recomputed one.

Edge cases & gotchas

localdatetime() on the timestamp. A single non-timezone-aware timestamp anywhere in the chain makes cross-jurisdiction ordering ambiguous and can fail an audit. Fix: enforce datetime() everywhere; add a constraint or ingestion check that rejects LocalDateTime values on SUPERSEDED_ON.timestamp.

Concurrent writers forking the chain. Two transactions that both read the same chain head and both create a snapshot produce two outgoing edges. The WHERE NOT (c)-[:SUPERSEDED_ON]->() guard plus execute_write retry closes most of this, but under heavy contention take a write lock on the entity first (MATCH (c) SET c._lock = c._lock in the same transaction) so the second writer serializes behind the first. The forked-entity validation query above is your safety net.

Unbounded reconstruction expansion. Dropping the depth bound (* instead of *0..100) turns a targeted lookup into a whole-graph walk under memory pressure. Fix: always bound the expansion and cap it at your retention depth; never ship a SUPERSEDED_ON* query without an upper limit.

Parent context

This page is the immutable-history deep dive within Schema Evolution & Versioning — the temporal chain here is what lets a live schema change without ever destroying the state it replaced.