Tracking a graph property across 50 snapshots of an evolving graph means either re-running the query 50 times or streaming changes snapshot-to-snapshot — and streaming hits a wall because edge deletions cost about 3× as much as additions for monotonic algorithms (a deletion invalidates every result that depended on the edge, forcing dependency-traced recomputation) — so CommonGraph computes the query once on the intersection of all snapshots, from which every snapshot is reachable by ADDITIONS ONLY (a deleted edge, viewed from the intersection, is just an edge to add back), turning the snapshot sequence into independent, parallel, mutation-free hops, and organizing shared additions into a Triangular Grid where the optimal evaluation schedule is a Steiner tree — 1.38–8.17× over KickStarter sequentially, with two-orders-of-magnitude headroom when hops run in parallel.
The argument in one glance
-
Problem
One query, fifty graphs
Real graphs change: social networks gain and lose edges, road networks congest and clear. Evolving-graph analytics asks how a property — shortest paths, reachability, widest paths — develops across MANY snapshots of the graph over a time window. With 50 snapshots of a billion-edge graph, running the iterative query independently on each snapshot repeats enormous shared work; the snapshots are, after all, mostly the same graph.
-
What people did
Stream the changes, update the answers
Streaming frameworks like KickStarter offer the obvious refinement: compute the query on the first snapshot, then apply each batch of edge additions and deletions in sequence, incrementally repairing the query results after each batch rather than recomputing. For monotonic algorithms (BFS, shortest/widest/narrowest paths, Viterbi), incremental repair is well-understood and usually cheap.
-
Why it fell short
Deletions are poison, mutation is a tax, and the chain forbids parallelism
Measured in KickStarter: incrementally processing a batch of deletions costs about 3× as much as an equal batch of additions. The asymmetry is fundamental to monotonic algorithms — an added edge can only IMPROVE values, so its effect propagates forward cheaply; a deleted edge may have SUPPORTED existing values, so the system must trace dependencies to find every result resting on it, reset them all, and recompute. In-place graph mutation (rewriting the adjacency structure per batch) adds its own cost, again worse for deletions. And streaming is inherently sequential — snapshot i+1's evaluation starts from snapshot i's results — so fifty snapshots form a fifty-link chain with no parallelism and no way to share the additions common to several snapshots.
-
This paper's idea
Start from the intersection, and every change is an addition
CommonGraph (UC Riverside) computes the query once on the COMMON GRAPH — the edges present in ALL snapshots — from which every snapshot is reachable by adding its missing edges: an edge that was "deleted" between snapshots i and i+1, viewed from the intersection, is simply an edge to add when hopping to snapshot i. Deletions vanish by change of reference point. The DIRECT-HOP schedule then reaches all snapshots independently (embarrassingly parallel, no chain); the TRIANGULAR GRID adds intermediate common graphs for snapshot subsequences, exposing shared additions — and picking the schedule that maximizes sharing is exactly a Steiner tree problem. A mutation-free representation (one CSR for the common graph plus one small CSR per addition batch, each edge stored once) eliminates the mutation tax outright. Results: 1.38–8.17× over KickStarter run sequentially, and 51–395× when the independent hops run in parallel.
Why this problem is worth solving
The gap between streaming and evolving analytics is easy to
miss and expensive to ignore.
a STREAMING system
maintains one current graph and keeps a query’s answer fresh
as updates arrive — one graph, one answer, always now. An
EVOLVING-graph query instead spans history: compute the
property on each of many stored snapshots across a time
window, e.g., how did shortest paths shift over a month of
road traffic? Same algorithms, but the many-snapshot
structure changes what is worth optimizing
the class KickStarter supports
— algorithms whose vertex values only tighten in one
direction as edges arrive, via compare-and-swap min/max edge
functions: BFS levels, shortest/widest/narrowest paths,
Viterbi. Monotonicity makes ADDITIONS cheap (a new edge can
only improve values; propagate the improvement and stop) but
makes DELETIONS structurally hard: a removed edge may have
been the support for downstream values, which must be found —
KickStarter tracks dependency trees for this — invalidated,
and recomputed
What makes the problem lovely is that the expensive half is an artifact of direction. Between two snapshots, an edge disappearing is a deletion — but between the snapshots’ intersection and the earlier snapshot, the same edge is an addition. The evolving setting, unlike true streaming, already holds all the snapshots; nothing forces processing them in chronological order from each other. CommonGraph is what happens when someone takes that freedom seriously: pick the reference point that makes every move an addition, and the deletion problem — algorithmic cost, mutation cost, and the sequential chain along with it — is not solved but dissolved.
What people did before, and where it broke
- Independent per-snapshot evaluation. Correct and parallel, but recomputes the shared bulk of the graph’s structure once per snapshot — for 50 snapshots differing by 0.01% of edges, almost all work is repeated 50 times.
- Sequential streaming (KickStarter and kin). Incremental algorithms avoid recomputation, but every hop pays the deletion premium (~3× additions) and the mutation tax (worse for deletions), and the chain — snapshot i+1 needs snapshot i’s results — serializes everything and prevents sharing additions common to multiple snapshots.
- Multi-version graph stores (Aspen). Solve snapshot STORAGE elegantly, but impose up to 2× query-time overhead versus flat representations — the paper’s CSR-plus-deltas layout reaches any snapshot with each edge stored exactly once and no mutation at all.
- The buried assumption. All of these treat the snapshot sequence as the processing order. Only the evolving setting makes that optional — and dropping it is where all the gains hide.
How CommonGraph works
Reverse the direction, then share the additions
-
The CommonGraph (intersection) new
G_c contains exactly the edges present in EVERY snapshot of the window. The iterative query runs once, from scratch, on G_c — work shared by all snapshots. Since G_c is a subgraph of every snapshot, each snapshot is reachable from it by ADDITIONS ONLY: its own additions batch is whatever it has beyond the intersection — including every edge that some later or earlier snapshot "deleted."
-
Direct-hop evaluation new
From G_c's converged results, hop to each snapshot independently: stream in its addition batch, run the cheap additions-only incremental algorithm (monotone tightening — propagate improvements, done). No deletions anywhere; no snapshot depends on another; all hops can run in parallel. The total addition count EXCEEDS streaming's adds+dels (22 vs 8+10 in the paper's worked example) — and still wins, because additions are ~3× cheaper, batched, and mutation-free.
-
Triangular Grid (TG) new
For n snapshots, build a grid: leaves are the original snapshots, the root is G_c, and between them sit Intermediate Common Graphs (ICGs) — intersections of consecutive subsequences (n−2 levels; every consecutive subsequence has its ICG). ALL grid edges are labeled with addition batches, computable by set algebra over the original add/delete batches. Additions shared by a subset of snapshots can be applied ONCE, at their common ICG, instead of once per snapshot.
-
Scheduling = Steiner tree new
Any tree rooted at G_c that reaches all leaves is a valid evaluation schedule; its cost is the total additions along its edges. Minimizing that cost over the grid is precisely the Steiner tree problem (choose which ICGs to route through). In the worked example: direct-hop costs 22 additions, the best tree 19. ICGs are never stored — they materialize on demand by streaming their shared additions when a schedule routes through them.
-
Mutation-free representation new
One CSR (compressed sparse row) structure holds G_c, immutable; each TG addition batch is its own small CSR. A snapshot IS the common graph plus a subset of delta CSRs — the incremental engine simply iterates over "common edges + batch edges." No in-place mutation ever happens; each edge in the system is stored exactly once (space-optimal); reaching a snapshot means loading, not rebuilding. Version-control primitives (get_version, diff, new_version) maintain G_c and the grid as new snapshots arrive.
-
Engine and scheduler
Implemented by extending KickStarter (Ligra-based storage, same vertex-centric push operators — CASMIN/CASMAX edge functions). The scheduler activates vertices touched by batch edges and propagates monotone updates over common+delta edges until quiescence.
The idea
The expensive operation is expensive only relative to a reference point — so move the reference point. A deletion is not intrinsically costly; it is costly from the snapshot that still has the edge. From the intersection, which never had it, the same difference is an addition. This is the paper’s entire first insight, and it is purely a change of coordinates — no new incremental algorithm, no approximation, just the observation that the evolving setting (all snapshots known) permits choosing where journeys start. Everything downstream compounds from it: the 3× algorithmic premium vanishes, the mutation machinery for deletions vanishes, and — because every hop starts from the same precomputed G_c results — the sequential chain shatters into independent hops whose parallel makespan is the longest single hop: 51–395× faster than the chain, given cores.
More work, cheaper work, sharable work. Direct-hop honestly processes more total edge updates than streaming (every snapshot re-adds what the intersection lacks). The bet is that each unit is cheaper — additions-only, batched, mutation-free — and the evaluation confirms it even sequentially (1.02–7.91×). The Triangular Grid then attacks the “more” directly: additions shared by consecutive snapshots apply once at their intermediate common graph, and choosing which ICGs to route through becomes a textbook Steiner tree instance over the grid. The site has seen this shape before — a design space reified into a classic combinatorial structure (a poset there, a Steiner instance here) so that optimization becomes principled rather than heuristic. The crossover is honest too: below ~23–35 snapshots, stabilizing at ICGs costs more than it shares, and plain direct-hop wins.
Never mutate what you can compose. The representation insight rounds out the trio: since schedules only ever ADD batches to the immutable G_c, a snapshot need not be constructed at all — it is the union of the common CSR and a few delta CSRs, iterated together. The mutation tax (prominent in the KickStarter breakdown, entirely absent from CommonGraph’s) is not reduced but deleted, each edge is stored once across the whole system, and the same immutable deltas are what make sharing across snapshots free. Readers of this site’s storage pages will recognize the instinct: append and compose rather than update in place, and coherence and sharing problems evaporate together.
Three snapshots, twenty-two additions, one Steiner tree
The paper's worked example, end to end
G_i..G_i+2 = consecutive snapshots. Δ+/Δ− = addition/deletion batches between them. G_c = intersection of all three. ICG = intermediate common graph of a consecutive pair. Costs count edge updates processed.
Step 1 of 6
The streaming bill
KickStarter computes on G_i from scratch, then streams to G_i+1 (3 additions, 5 deletions), then to G_i+2 (5 additions, 5 deletions): 8 additions plus 10 deletions, sequentially, with two rounds of in-place mutation. The deletions dominate — each may topple values across the graph that the dependency trees must find and rebuild.
deletions ≈ 3× additions per edge (KickStarter measurement) mutation cost is likewise deletion-heavy
Why it works
- Monotone algorithms make additions local (improvements propagate and stop) and deletions global (supports must be traced and rebuilt) → any schedule that avoids deletions saves ~3× per affected edge → starting at the intersection makes deletion-avoidance total, not partial.
- All snapshots are known in advance in the evolving setting → processing order need not follow time → the reference point can be CHOSEN, and the intersection is the unique point from which every snapshot is additions-only.
- Every hop starts from the same G_c results → hops share nothing and can run concurrently → the makespan collapses from the chain’s sum to the longest hop (51–395× measured headroom), a structural gain no faster incremental algorithm could match.
- Consecutive snapshots share additions beyond G_c → ICGs let shared batches apply once, and schedule cost is a sum over tree edges → minimal-work scheduling reduces to Steiner tree on the grid, a solved problem.
- Schedules only add batches to an immutable base → snapshots can be COMPOSED (common CSR + delta CSRs) instead of constructed → mutation cost is eliminated, each edge stored once, and the same immutable deltas are what sharing reuses.
What it costs
- Monotonic algorithms only. The additions-are-cheap asymmetry is a property of CASMIN/CASMAX-style monotone queries (the KickStarter class). Non-monotonic analytics — PageRank-style value iteration — get no free conversion, and the paper does not claim them.
- More raw edge work. Direct-hop re-processes each snapshot’s full difference from the intersection; with few snapshots, tiny deltas, or addition-heavy change mixes, the streaming chain’s smaller update count narrows the gap (LiveJournal Viterbi: 1.02× for direct-hop alone).
- A window must be chosen. G_c is the intersection over the query window; a longer window with heavy churn shrinks the common graph, raising every hop’s batch size. The grid’s incremental maintenance helps, but the window is a real knob.
- Steiner scheduling and grid bookkeeping. Work-sharing needs the TG built, batch set-algebra computed, and a Steiner instance solved; below the ~23–35-snapshot crossover, stabilizing intermediate results at ICGs costs more than it shares.
- Storage for deltas. Space-optimal per edge, but the grid’s batches must persist alongside G_c; and the evaluation is single-machine, shared-memory — distributed settings are untested here.
The evaluation
Four real graphs up to 1.5B edges, five monotonic queries, 50 snapshots with controlled batch sizes, three-way comparison (KickStarter streaming, direct-hop, work-sharing) plus sensitivity to snapshot count, batch size, add/delete ratio, and a parallel-potential study.
Three ways to answer one query on fifty snapshots
| Property | Independent per-snapshot evaluation | Sequential streaming (KickStarter) | CommonGraph (direct-hop + work sharing) |
|---|---|---|---|
| Work on the shared graph structure | Repeated once per snapshot — 50× redundancy at 0.01% churn | Computed once (first snapshot), then incrementally carried forward | |
| Deletions processed | None (each snapshot evaluated whole) | ||
| Parallelism across snapshots | Full (but each unit is expensive) | ||
| Graph representation | One structure per snapshot | One structure, mutated in place per batch — a measured, deletion-heavy cost | |
| Bottom line (50 snapshots, 5 queries, 4 graphs) | Dominated | 1.0× reference |
Check yourself
Check your understanding
1. For monotonic algorithms, why does incrementally processing an edge DELETION cost about 3× as much as an addition — the asymmetry the whole paper is built on?
2. CommonGraph "converts deletions to additions" without changing the incremental algorithm at all. What is the actual mechanism, and why does it win despite processing MORE total edge updates (22 vs 18 in the worked example)?
3. Direct-hop already shares the common graph's computation. What additional sharing does the Triangular Grid capture, and why is finding the best schedule a Steiner tree problem?
4. KickStarter's execution breakdown shows significant "mutation" time that is entirely absent from CommonGraph's. What replaced it, and what else does that replacement buy?
Sources
- ACM DL: CommonGraph: Graph Analytics on Evolving Data — ASPLOS 2023 (open access)