Traversal and degree skew

Why does traversal cost explode with depth, and why is degree skew the central mechanism?

Traversal as a query primitive

A traversal is a sequence of frontier expansions. The frontier is a set of vertices. Expansion replaces it with the union of their neighbours, minus what you have already seen. That "minus what you have seen" is not a detail. It is a stateful deduplication against the visited set, and it is why traversal cannot be written as a fixed pipeline: you do not know in advance how many iterations you need.

SQL has a feature for this, the recursive query (WITH RECURSIVE): a query that feeds its own output back in as input until no new rows appear. Graph traversal is fixpoint iteration (repeat a step until the result stops changing), and recursive SQL is the same mechanism behind a different interface. They are not two features.

-- Everyone reachable from user 7 within 3 hops (UNION removes already-seen pairs).
WITH RECURSIVE reach(user_id, depth) AS (
    SELECT 7, 0
  UNION
    SELECT f.followee_id, r.depth + 1
    FROM reach r JOIN follows f ON f.follower_id = r.user_id
    WHERE r.depth < 3
)
SELECT DISTINCT user_id FROM reach;

Frontier size is the cost, and it is governed by the branching factor. With average degree d (the number of edges at a vertex), hop k touches on the order of d^k vertices before deduplication.

This has a clean architectural consequence. Shallow traversal from few starting points is an OLTP workload (many small, fast, interactive operations). Anything else is an OLAP workload (few large scans over all the data). They want opposite systems: pointer-chasing over mutable adjacency, versus scan-shaped iteration over immutable CSR. Treating "graph" as one workload is the source of most disappointment in this family.

Pattern matching (finding a small shape, such as a triangle of three mutually-following users, inside a big graph) is a third cost regime, different from traversal. It is where worst-case-optimal join algorithms live: multiway join methods whose running time is bounded by the largest possible output size. They matter because ordinary pairwise joins can build huge intermediate results on triangle-like patterns.

BFS and DFS differ in memory shape, not in edges touched

Parallelism costs memory here. This is the general trade between ordering and parallelism, appearing in its memory-shaped form.

Bidirectional search deserves one line, because it is the only real asymptotic win available. Search k/2 hops from both ends and meet in the middle: the cost is 2·d^(k/2) instead of d^k. With d = 100 and k = 4: 2 × 100² = 20,000 instead of 100,000,000. It needs both endpoints, so it serves shortest-path queries and nothing else.

One line: traversal is fixpoint iteration whose cost is exponential in depth until it saturates the component. Shallow-from-few is OLTP; everything else is a disguised full scan.

Degree skew: the real central mechanism

Real graphs are power-law (also called heavy-tailed): a handful of vertices have degrees in the millions, while the median vertex has a handful. (This is the Zipf shape: a few items take most of the weight.) This is not a data-quality problem to be cleaned. It is the empirical shape of essentially every graph anyone cares about, including Haatly's follower graph.

It breaks partitioning, and the common explanation is wrong. The problem is not that balanced graph partitioning is NP-hard (computationally intractable in the worst case). Approximation algorithms exist and would be fine. The problem is that in a power-law graph there is no good balanced cut to find. The graph has no sparse separators, so every balanced partition cuts an enormous fraction of edges. Better partitioners cannot help, because they are searching for something that does not exist.

That forces a real change of representation:

Vertex-cut balances load on edges, which is what the work is actually proportional to.

Notice the shape of that resolution: when one entity is too large to place, split it and reconcile. It is the same move as salting a skewed join key (appending a random suffix so one hot key becomes several smaller keys, then merging the partial results), as sharding a hot partition, and as splitting a hot key in a stream. The constant cost is the same every time: an extra reconciliation step that the unskewed case does not need.

Skew also makes the average degree nearly useless for cost estimation. A traversal's cost is dominated by whether it hit a hub, which depends on the data and not on the query. This is variance costing more than volume, in its strongest form here: the variance of degree, not the mean, determines both latency and the failure mode, and a query planner with only average statistics will be wrong in the direction that matters.

One line: power-law graphs have no sparse balanced cuts to find, so you replicate hubs and reconcile. Degree variance, not the mean, sets every cost.