Trace AtlasMart fraud navigation from an indexed anchor into local adjacency and compare it with repeated global edge scans.
Adjacency, Index-Free Traversal Concepts, and When Relationships Are First-Class Data
Understand what adjacency buys after an entity is located, why “index-free adjacency” is implementation-dependent, and when relationship properties justify graph-native modeling.
Learning outcomes
Understand what adjacency buys after an entity is located, why “index-free adjacency” is implementation-dependent, and when relationship properties justify graph-native modeling.
Define adjacency and distinguish anchor lookup from subsequent traversal.
Explain the idea—and limitation—of index-free adjacency terminology.
Compare adjacency traversal with relational joins and precomputed lookup tables without slogans.
Recognize when relationship identity/properties make an edge first-class domain data.
Mandatory work uses Python 3.13+ standard library only on a single local process. No graph database, Docker image, cloud account, paid feature, network manipulation, or destructive failure injection is required. Neo4j 2026.07.1 is an optional current implementation reference; Community Edition is GPLv3. Product-specific clustering, sharding, security, and enterprise features are not assumed by the lab.
1. Find an anchor, then navigate topology
A graph query usually has two different jobs. First it
identifies an anchor—for example customer
c1, card fingerprint p9, or a known
fraudulent device. That step may use an index or another lookup
structure. Second it expands relationships from nodes already
found. Adjacency means the graph representation
can discover a node's incident/outgoing relationships from that
node's graph state rather than starting every hop with an
application-level scan of every possible relationship.
2. “Index-free adjacency” is a concept, not a universal contract
The phrase index-free adjacency is often used for graph engines that store direct or near-direct references between connected records, so traversing from an already located node does not require a global secondary-index lookup for each hop. The exact storage mechanism is product/version dependent. Some engines may use IDs, pointer-like references, compressed adjacency, partitions, caches, or remote lookups. Therefore the safe statement is workload-oriented: a graph system can make repeated neighborhood navigation a primary access path. Do not infer constant-time hops, no indexes anywhere, or no network cost in a distributed graph.
3. AtlasMart lab: make the mechanism observable
Save the following as lesson2_adjacency.py and run
it with python lesson2_adjacency.py. The program
has no dependencies and mutates no external state.
from collections import defaultdict, deque
edges = [
("cust:c1", "USES_DEVICE", "dev:d1", {"first_seen": 1}),
("cust:c2", "USES_DEVICE", "dev:d1", {"first_seen": 2}),
("cust:c2", "USES_CARD", "card:p9", {"first_seen": 3}),
("cust:c3", "USES_CARD", "card:p9", {"first_seen": 4}),
("cust:c3", "PLACED", "order:o7", {"amount": 220}),
("cust:c4", "USES_DEVICE", "dev:d8", {"first_seen": 5}),
]
adj = defaultdict(list)
for src, typ, dst, props in edges:
adj[src].append((typ, dst, props))
adj[dst].append((typ + "_REV", src, props))
# Locate the anchor once (conceptually via an index), then follow adjacency.
frontier = ["cust:c1"]
visited = {"cust:c1"}
adjacency_reads = 0
for depth in range(2):
next_frontier = []
for node in frontier:
adjacency_reads += 1
for typ, dst, props in adj[node]:
if dst not in visited:
visited.add(dst)
next_frontier.append(dst)
frontier = next_frontier
print("two-hop neighborhood:", sorted(visited))
print("adjacency lists read:", adjacency_reads)
# Deliberately wrong baseline: rescan every edge list for every expanded node.
frontier = ["cust:c1"]
visited2 = {"cust:c1"}
edge_rows_examined = 0
for depth in range(2):
next_frontier = []
for node in frontier:
for src, typ, dst, props in edges:
edge_rows_examined += 1
for a, b in ((src, dst), (dst, src)):
if a == node and b not in visited2:
visited2.add(b); next_frontier.append(b)
frontier = next_frontier
print("global edge rows examined:", edge_rows_examined)
# Relationship properties remain attached to the connection.
for typ, dst, props in adj["cust:c2"]:
if typ == "USES_CARD":
print("c2 card edge metadata:", props)
Expected evidence: the two-hop neighborhood from customer c1 reaches the shared device and customer c2, adjacency expansion reads only the lists for nodes actually expanded, while the deliberately naïve baseline repeatedly examines the whole edge collection. The relationship metadata stays attached to the c2→card association rather than being copied into both endpoint records.
4. Relational joins and denormalized maps are legitimate alternatives
A relational database can represent the same topology with
entity tables plus relationship tables and indexes on foreign
keys. For bounded, selective traversals, that may be excellent.
A key-value system can also precompute
customer→devices and
device→customers maps. The tradeoff is maintenance:
each new relationship may require multiple derived entries, and
relationship properties must remain consistent across copies.
Graph-native modeling is compelling when the topology changes
frequently and applications need many combinations of
relationship types and directions rather than a small fixed set
of lookup maps.
5. Relationship properties prevent semantic flattening
AtlasMart's USES_CARD relationship can carry
first_seen, last_seen, source,
confidence, or verification state. Those values describe the
connection, not the customer or card independently. Making the
association first-class avoids awkward arrays of nested records
or duplicated lookup tables. But edges still need authorization
and lifecycle rules: deleting a customer may require edge
cleanup or retention for audit; a cross-tenant edge may be a
severe privacy breach; and a relationship created from weak
evidence should not be treated like a verified identity link.
6. Read the evidence as work performed, not as a benchmark
The lab compares counts of adjacency-list reads with a deliberately inefficient full edge scan. Those counts demonstrate an algorithmic access-path difference in this tiny deterministic model. They are not latency numbers and do not prove any graph product outperforms a relational engine. Production evidence should include execution plans, relationship-degree distributions, cache state, page/cache misses, remote shard hops, tail latency, and the selectivity of the anchor lookup.
7. Production judgment
Use adjacency-centric storage when the dominant question begins with known entities and repeatedly follows changing relationships. Bound the traversal, index common anchors, inspect high-degree nodes, and establish tenant-aware traversal permissions. If all queries are one fixed join or one precomputed reverse lookup, the operational simplicity of relational or key-value storage may win. In distributed graphs, an “adjacent” node may live on another shard, so topology placement and edge cuts can dominate the cost; Lesson 4 makes that explicit.
Wrong approach: rescan the world on every hop
The application stores an unsorted global edge list and, for every node in the frontier, scans every edge to discover neighbors. The query is logically correct on small data but its work multiplies with both graph size and frontier size. The repair is not “graphs are always faster”; it is to create an access structure that maps an anchor to its incident relationships, then measure the resulting degree, cache behavior, and remote-hop cost.
Verification, cleanup, and production checklist
Verification is the program output plus the conceptual checks
below. Cleanup is simply deleting the local
lesson2_adjacency.py file; the simulation creates
no sockets, services, databases, containers, credentials, or
persistent data. In production, additionally verify tenant
authorization on traversals, identity/constraint health, degree
and path-cardinality distributions, p95/p99 latency, cache and
remote-hop behavior where applicable, backup/restore or
projection rebuild, software/security advisories, and
edition/license constraints before adopting product-specific
features.
Check your understanding
- What is adjacency?
- Does index-free adjacency mean a graph database never uses indexes?
- Why might an association deserve its own relationship record?
- What does the lab’s edge-row count prove?
- What new cost appears when a graph is sharded?
Review the answers
1. The ability to obtain a node’s incident/outgoing relationships from graph-local state associated with that node.
2. No. Indexes are commonly used to locate anchors; the term concerns navigation after an anchor is found and remains implementation-dependent.
3. Because the connection can have properties, lifecycle, multiplicity, provenance, and traversal significance of its own.
4. Only the work difference between two deterministic in-memory algorithms, not real database latency.
5. An adjacent node/edge may require a remote shard/network hop, so logical adjacency is not necessarily physical locality.
References
Foundational statements use the published property-graph standard where appropriate; implementation-sensitive examples use current official documentation and are labeled as examples rather than universal graph guarantees.
- Neo4j — What is a graph database — current node/relationship/property graph overview.
- Neo4j — Relational to graph modeling — current implementation guidance comparing relational entities and graph relationships.
- Neo4j Operations Manual — Index configuration — evidence that graph systems still use indexes for property and token lookup.
- ISO/IEC 39075:2024 — GQL — standardized property-graph structures and operations.