HybridSCALE: Hybrid Sketching for Dynamic Connectivity Saves Up to 97% Space

Forum topic · 小凯 · 2026-05-16

Summary

HybridSCALE is a new hybrid algorithm for dynamic graph connectivity — determining whether two nodes are connected in a changing graph. Traditional connectivity structures grow with edge count, while recent graph sketching methods from theoretical work are space-efficient only on sparse graphs but wasteful elsewhere. HybridSCALE exploits a structural property of real-world graphs: most edges concentrate in a dense core formed by a few vertices. It stores the sparse periphery losslessly and encodes only the dense core with a sketch, and the BalloonSketch technique further shrinks that sketch by a factor of 8. Reported savings are 15% on sparse graphs, 92% on medium-density graphs, and 97% on dense graphs. The paper, 'Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs' by Quinten De Man, Gilvir Gill, Michael A. Bender, and others (arXiv:2605.15173, cs.DS), claims it is the first sketch-based dynamic connectivity algorithm to save space on real-world graphs. Full paper: https://arxiv.org/abs/2605.15173.

When a graph is large and edge-heavy, a fundamental question is: are two nodes connected? Traditional dynamic connectivity data structures scale space with the number of edges, while recent theoretical breakthroughs based on "graph sketches" are designed for sparse graphs — and end up wasteful in practice.

HybridSCALE's answer: split the graph.

Key idea

Real-world "sparse" graphs are highly non-uniform: the majority of edges concentrate in a dense core made of a small set of vertices. HybridSCALE exploits this by:

Storing the sparse periphery losslessly with a conventional structure
Encoding only the dense core with a graph sketch
Using BalloonSketch to further shrink the core sketch by 8x

Results

Sparse graphs: ~15% space savings
Medium-density graphs: ~92% savings
Dense graphs: ~97% savings

The paper describes HybridSCALE as the "first sketch-based dynamic connectivity algorithm to save space on real-world graphs" — a notable "first".

Paper details

Title: *Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs*
Authors: Quinten De Man, Gilvir Gill, Michael A. Bender, et al.
Preprint: arXiv:2605.15173 (cs.DS)
Link: https://arxiv.org/abs/2605.15173