SQUASH: Distributed Square Estimation with Provable Error Bounds for Dynamic Graphs

Abstract

Counting subgraph motifs is a fundamental kernel in large-scale graph analytics, yet square (4-cycle) estimation in dynamic graphs remains challenging due to combinatorial explosion and distributed state maintenance costs. We introduce SQUASH (SQUare Approximation via Sampling and High-performance communication), a distributed framework for streaming square estimation, and demonstrate both theoretically and empirically that the average error in square counting decreases inversely with the number of workers. The results indicate that utilizing approximately 1.5% of memory compared to the exact counterpart yields a relative error of about 1%. Additionally, it provides unbiased estimates with (ϵ, δ)-approximation guarantees. By leveraging Bernstein-type concentration, we prove that \(O(\frac{1}{p\epsilon ^2} \log \frac{1}{\delta })\) samples are sufficient for accurate estimation, where p is the closure probability of centered 3-path. For large-scale graphs in static settings, centered 3-path sampling reduces computation time by approximately three orders of magnitude relative to exact counting method having relative error of approximately 1%. Furthermore, we provide a rigorous communication analysis showing that volume is governed by the interplay between wedge generation rate and pair-space size, achieving sublinear growth with provable phase transitions. This exposes a principled three-way trade-off between estimation accuracy, memory, and communication cost. Experiments on graphs with up to 117M edges demonstrate that SQUASH maintains high accuracy while establishing a mathematically grounded solution for higher-order motif estimation at scale.