Achieving Sub-second Pairwise Query over Evolving Graphs

Asking for the shortest path between two specific people in a graph that is changing millions of times a second should be fast, because you only need one answer rather than all of them — but every system prunes the search using upper bounds, which by a simple counting argument can never eliminate more than about half the work; SGraph (Tsinghua, Sydney and Purdue) notices that the inequality everyone was using has a second half nobody had exploited, giving lower bounds from exactly the same precomputed data, and that takes the fraction of the graph touched from half to under one percent.

Why this problem is worth solving

Changing the question changes what is achievable.

The pruning rests on a property that is more general than it looks.

What people did before, and where it broke

• Run the exhaustive single-source algorithm and read off one entry. Correct and simple. Where it broke. It does all the work for every vertex to answer a question about one, which is precisely the exhaustive nature that rules out interactive latency.
• Prune using the current best answer. Track the best route found to the destination so far, and discard any update that is already worse. Where it broke. It only rules out vertices whose value already exceeds the answer. About half the graph is genuinely closer to the source than the destination is, so those vertices survive every such test and must be activated.
• Precompute distances to a few hub vertices and start from a tighter upper bound. Pick some high-degree vertices, compute distances to and from every vertex, and use them to initialise the search near the answer rather than at infinity. Where it broke. It makes the upper bound tighter but leaves it an upper bound, so the same counting argument applies. Measured, this still activates around half the vertices.
• Maintain the whole single-source result incrementally as the graph changes. Track which values a deleted edge invalidated, repair them, and reuse the rest. Where it broke. It is solving the exhaustive problem faster rather than avoiding it, so the state maintained grows with the graph and the per-query work is still proportional to it.
• Use an industrial graph database. The obvious production answer, with real engineering behind it. Where it broke. Measured here, hundreds of times slower than what this pruning achieves on the same queries.
• The gap. The pruning test everyone uses has a third term in it — how much further the path must still go from the current vertex to the destination — and because that concerns a part of the graph nobody has explored yet, every existing system quietly substitutes zero. Upper-bound-only pruning is not a different technique; it is the general rule with its most conservative possible value plugged in.

How a lower bound changes the search

The idea

Upper-bound pruning is not one technique among several; it is the general rule with a zero substituted in. Write down when a vertex is genuinely not worth exploring and three quantities appear: how good the route to it is, how much the remaining journey to the destination must still cost, and how good the current best answer is. Two of those are known from what the search has already done. The third is about a region nobody has visited, so every prior system assumes it could be zero — perfectly safe, and the reason those systems waste work. The counting argument that follows is the sharpest thing in the paper: if the two endpoints are chosen at random, about half the vertices are genuinely closer to the source than the destination is, so their values are legitimate, no upper bound can exclude them, and they must be activated. That is a ceiling on what upper-bound pruning can ever achieve, not an implementation shortcoming. Recognising that an accepted formulation is the degenerate case of a more general one, and that filling in the missing term changes the cost class of the problem, is the same kind of reframing the evolving-graph work covered elsewhere on this site performs when it converts expensive deletions into cheap additions over a shared subgraph.

The missing bound turns out to be free, which is why nobody noticed it was missing. The second clause of the triangle inequality had been dismissed as an algebraic rearrangement of the first, and in a sense it is — but rearranged into a form that bounds a leg of the journey that has not been walked yet. Given hub distances already stored for the upper bounds, two lower bounds on the remaining distance follow immediately, and the tighter of them can be used. No new precomputation, no new index, no extra space beyond what was already there. The effect is dramatic: activations fall from about half the graph to under one percent, and for several query types the bounds meet, so the answer is known without touching the graph at all. What is interesting is what this does to the rest of the system, because a query that touches one percent of the graph has completely different bottlenecks from one that touches all of it — a storage design that buffers recent edges in a log, entirely reasonable when every iteration scans the graph anyway, becomes the dominant cost when each iteration scans almost nothing. Solving the main problem well enough that the bottleneck relocates to something previously invisible is the same dynamic the multi-device transform work covered elsewhere on this site runs into when fast arithmetic pushes the constraint onto the interconnect.

The developer states a property; the system derives the machinery. There are many pairwise queries and each application bends them — an edge filter here, a label restriction there — and any of those changes can invalidate a hand-built bound. Requiring developers to design bound maintenance and pruning logic per query would make the technique unusable. So the interface asks for something much smaller: an ordinary vertex program, plus five functions defining a zero, an infinity, a combining operator, a subtracting operator and a comparison, each typically one or two lines. From those the system generates the index construction, the incremental repair when edges are deleted, and both directions of the pruning test. Seven query types are demonstrated this way, differing only in those five definitions. Moving the difficult, error-prone part of a technique out of every tool and into the framework, so users declare what their problem is rather than implementing how to exploit it, is exactly the shift the value-profiling framework covered elsewhere on this site makes for binary instrumentation.

Following one query through the system

Sometimes the upper and lower bound for the pair are equal, in which case the answer is already known and no vertex is ever activated. This happens often for reachability and connectivity queries.

Why it works

• Half the graph is unprunable by upper bounds as a matter of arithmetic. With randomly chosen endpoints, roughly half the vertices are genuinely nearer the source than the destination is → their computed values are correct and not worse than any known bound, so no upper-bound test can discard them → which puts a ceiling of about half on what that entire family of techniques can achieve, independent of how cleverly the bound is estimated.
• A bound on the unexplored remainder is exactly the missing term. The honest pruning condition needs to know how much further the journey must go from here → that concerns territory the search has not entered, so it was always replaced by zero → supplying any positive value tightens the test, and supplying a good one lets vertices be discarded for pointing the wrong way rather than for being far away.
• The second clause of the inequality supplies it at no cost. Lower bounds on the unexplored leg follow from the hub distances already stored for the upper bounds → so the extra pruning power requires no new index, no new precomputation and no extra space → which is why the technique can be added to systems that were already paying for hub indexes.
• Forming bounds lazily is essential once pruning is this good. Computing bounds for every vertex costs time proportional to graph size times hub count → but the whole point is that under one percent of vertices get visited → so precomputing would make the setup dominate the query, and storing hub distances beside each vertex lets bounds be built only where they are needed.
• The three techniques multiply rather than add. Upper bounds alone give between 1.43 and 2.04 times; adding bidirectional search or lower bounds separately gives single digits → but the lower bounds apply in both search directions, so each constrains the other → and all three together give between 20.7 and 35.7 times, several times more than any pair.

What it costs (trade-offs and scope)

• Freshness is traded for latency, explicitly. Queries run against the last snapshot whose indexes are ready, so answers are seconds stale. The comparison system computes on the freshest data because it precomputes nothing. The paper states the trade plainly and argues seconds-level staleness is acceptable for its target applications, which is a judgement about the applications rather than a technical result.
• On breadth-first search the advantage largely disappears. Against the fastest prior system it is between 1.16 and 1.63 times, essentially comparable. The paper explains why: the comparison system can skip an entire phase for this query, and the web graph used has a small diameter, so the bounds contribute little and most of the gain comes from bidirectional search instead.
• Both baselines are re-implementations. Neither prior system is open source, so both were rebuilt on the same execution engine. That is the right way to isolate the algorithm, and it also means these are not measurements of the original systems.
• One of the baselines is a construction of the authors. The upper-bound-only comparison combines one system’s index-based bounds with another’s pruning, an extension the authors made to have a fair opponent. It is a reasonable strawman to build and it is still a strawman they built.
• Applicability is limited to queries satisfying the inequality. A developer must be able to define the three operators. Seven query types are shown, and the paper claims the class is broad, but a query outside it gets nothing.
• Hub selection is a heuristic with a cliff. Sixteen highest-degree vertices, justified by the observation that one connected component usually covers most of a real graph. A vertex not connected to a given hub gets an infinite upper bound and a zero lower bound from it, which is to say no pruning at all from that hub.
• Index repair is the expensive half and deletions are the expensive case. Maintaining indexes takes from about a sixth of a second to four seconds per batch depending on query and batch size. The paper describes freshness as sub-second for simple queries and within several seconds for complicated ones.
• The storage design is admittedly special-purpose. The authors say directly that their format is not a better general-purpose dynamic graph store; it works because only two rolling snapshots are ever needed and ingestion is bounded by index repair anyway.
• Scaling is sub-linear. Eight nodes give four to six times a single machine.
• Everything is averaged over a thousand queries with endpoints chosen at random, which is also the assumption the central counting argument depends on. Workloads with correlated or local endpoints would behave differently in ways not explored.

The evaluation

Check yourself

Sources

The paper is “Achieving Sub-second Pairwise Query over Evolving Graphs” by Hongtao Chen, Mingxing Zhang, Ke Yang, Kang Chen, Albert Zomaya, Yongwei Wu and Xuehai Qian, published at ASPLOS 2023, pages 1-15, DOI 10.1145/3575693.3576173. The first three authors contributed equally. It is open access under a Creative Commons licence.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the motivation contrasting real-time relational analytics with the exhaustive nature of graph algorithms, and the pairwise reformulation with its navigation, recommendation and risk-detection examples; the analysis of why upper-bound-only pruning cannot exceed roughly half, with both the counting argument and the worked example graph showing which activations each scheme prunes; the case study on point-to-point shortest path, covering the baseline vertex program, the two clauses of the generalised triangle inequality with their abstract operators, how existing systems use the first clause with hub indexes to tighten upper bounds, the derivation of two lower bounds from the second clause, and the resulting pruning condition; the micro-benchmark of active vertices per iteration; the programming model requiring a vertex program plus five operator definitions, and the automatic generation of index construction, incremental maintenance and pruning logic from them; the decoupled architecture with its three concurrent activities, the two-bit-per-edge snapshot scheme with its worked epoch-by-epoch example, and the implementation details covering hub selection, ad-hoc bound calculation and bidirectional search; and the evaluation covering the cluster and datasets, per-application query latency against two re-implemented prior systems and two industrial databases, the larger graph study, vertex activation ratios, index maintenance times across batch sizes, the comparison against an alternative storage format, the three-way breakdown of pruning techniques, and inter-node scalability.