Scalable Triangle Counting: The Threshold Algorithm

We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm—read edges from the stream until $Q$ triangles are observed in the prefix, then output $Q(m\mathrm{/}S{)}^3$ where $S$ is the stopping length—and prove that, when the maximum number of triangles incident to any edge satisfies $\eta \le T^{2\mathrm{/}3}$, this is a $(1\pm \epsilon )$-approximation of $T$ with probability $1-\delta$ using $O({\epsilon }^{-2}\log (1\mathrm{/}\delta )m\mathrm{/}{T}^{1\mathrm{/}3})$ memory. Crucially, the algorithm does not need any a priori estimate of $T$, in sharp contrast with state-of-the-art sampling-rate based algorithms (McGregor and Vorotnikova, PODS 2020; Tsourakakis et al., KDD 2009). It also does not need a prescribed memory budget: the stopping rule self-selects the prefix length and can return an estimate before reading the entire stream. The proof rests on a Schudy–Sviridenko concentration argument for an independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. On six real temporal streams, the algorithm’s stopping prefix follows the predicted cube-root scaling and achieves at most $6\mathrm{\%}$ error at a $10\mathrm{\%}$ prefix, without using $T$. At a fixed stored-edge budget, variance-reduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, $1.8\times {10}^9$-edge graph, the threshold algorithm reads $0.46\mathrm{\%}$ of the stream and returns $3.8\mathrm{\%}$ error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap.