Path, Neighborhood, Reachability, Pattern Matching, and Variable-Length Traversal

Learning outcomes

Use neighborhoods, reachability, bounded paths, and shortest-path-like reasoning without turning variable-length traversal into an unbounded combinatorial search.

1. Different graph questions return different objects

A neighborhood asks which nodes/relationships are near an anchor within some hop limit. Reachability asks whether a target can be reached under permitted edge semantics. A path is a sequence of nodes and relationships connecting endpoints. Pattern matching constrains labels, relationship types/directions, properties, and sometimes path length. A shortest path minimizes an explicit cost such as hop count or weighted distance. These are not interchangeable. AtlasMart fraud screening may need “customers within four verified identity-sharing hops,” while dependency analysis may need “all services downstream of database X,” and recommendations may need scored candidate paths rather than every possible path.

2. Variable length must be bounded by semantics

Modern property-graph languages can express repeated path patterns. Neo4j's current Cypher documentation, for example, supports quantified path patterns such as a relationship repeated between lower and upper bounds and explicitly warns that broad variable-length patterns can match very large numbers of paths. The safe design question is not merely syntax. Choose a maximum depth justified by the domain, constrain edge types and tenant labels, prune on properties, and decide whether repeated nodes/edges are legal. A fraud rule that loses meaning beyond four hops should encode that business boundary instead of asking the database for arbitrary-length connectivity.

3. AtlasMart lab: make the mechanism observable

Save the following as lesson3_paths.py and run it with python lesson3_paths.py. The program has no dependencies and mutates no external state.

from collections import defaultdict, deque

adj = defaultdict(list)
edges = [
    ("cust:c1", "USES", "dev:d1"),
    ("dev:d1", "SEEN_WITH", "cust:c2"),
    ("cust:c2", "USES", "card:p9"),
    ("card:p9", "SEEN_WITH", "cust:c3"),
    ("cust:c3", "USES", "dev:d2"),
    ("dev:d2", "SEEN_WITH", "cust:c1"),  # cycle
    ("cust:c2", "USES", "dev:d3"),
    ("dev:d3", "SEEN_WITH", "cust:c4"),
]
for a,t,b in edges:
    adj[a].append((t,b))
    adj[b].append((t+"_REV",a))

def bounded_neighborhood(start, max_depth):
    q = deque([(start,0,[start])])
    best = {start:0}
    reached = []
    expansions = 0
    while q:
        node, depth, path = q.popleft()
        if depth == max_depth: continue
        expansions += 1
        for typ,nxt in adj[node]:
            nd = depth + 1
            if nd < best.get(nxt, 10**9):
                best[nxt] = nd
                q.append((nxt,nd,path+[nxt]))
                reached.append((nxt,nd,path+[nxt]))
    return reached, expansions

reached, expansions = bounded_neighborhood("cust:c1", 4)
print("bounded reached:", [(n,d) for n,d,p in reached])
print("expansions:", expansions)
path_to_c3 = next(p for n,d,p in reached if n == "cust:c3")
print("shortest discovered path to c3:", path_to_c3)

# Deliberately wrong: enumerate walks with no visited-state pruning.
def count_walks(start, depth):
    frontier = [start]
    total = 0
    for _ in range(depth):
        nxt = []
        for node in frontier:
            for _,neighbor in adj[node]:
                total += 1
                nxt.append(neighbor)
        frontier = nxt
    return total, len(frontier)

for depth in (2,4,6,8):
    examined, frontier = count_walks("cust:c1", depth)
    print(f"unpruned depth={depth}: edges_examined={examined}, frontier={frontier}")

4. Branching factor creates a multiplicative search space

If each expanded node has roughly b useful outgoing relationships, an unconstrained tree-like traversal can expose on the order of b^d candidate walks at depth d. Real graphs have cycles and shared nodes, so the exact number varies, but the operational lesson remains: broad predicates and high-degree nodes make variable paths expensive. “Graph query” is not synonymous with cheap query. Measure rows/paths produced per expansion, maximum frontier size, memory, network hops, and tail latency.

5. Cycles require an explicit path semantics

AtlasMart's identity graph naturally contains cycles: customer→device→customer→card→customer and perhaps back to an earlier device. A traversal engine must know whether a node or relationship may repeat within a path. A reachability search often uses a visited set because revisiting the same state adds no value. A path enumeration query may intentionally permit different routes to the same node. Those choices change both correctness and cost; hiding them behind an unlimited *-style pattern is an operational mistake.

6. Security and tenancy belong inside traversal rules

A path query can leak information even when individual anchor lookups are authorized. Suppose tenant t1 can see a shared IP node but must not learn that tenant t2 also touched it. If traversal privileges or application filters do not preserve the tenant boundary at every hop, the graph becomes a lateral information channel. Tests therefore need negative paths: start with a permitted tenant anchor, cross a shared infrastructure node, and verify that forbidden tenant nodes/edge properties remain invisible.

7. Production judgment

Bound variable-length queries, verify query plans, cap result cardinality, and distinguish “shortest one path” from “enumerate all paths.” Use precomputation when the same expensive reachability answer is requested repeatedly and its freshness contract is clear. In distributed graphs, each frontier expansion can multiply network fan-out; in dense graphs, memory and scheduler pressure may dominate. Benchmark with realistic degree distributions and cold/warm cache states rather than a toy chain. The next lesson focuses on the supernodes and edge cuts that make those costs extreme.

Wrong approach: ask for “all paths of any length” and hope the graph is small

Verification, cleanup, and production checklist

Verification is the program output plus the conceptual checks below. Cleanup is simply deleting the local lesson3_paths.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.

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 Cypher Manual — Variable-length paths — current syntax and warnings about broad variable-length path matches.
• Neo4j Cypher Manual — Shortest paths — current implementation semantics for shortest-path queries.
• ISO/IEC 39075:2024 — GQL — standard property-graph query-language foundation.
• Neo4j Operations Manual — Access-control limitations — current graph/subgraph traversal authorization considerations.