arXiv:2609.15848v1 [cs.DS] 14 Sep 2026
Scalable Triangle Counting: The Threshold Algorithm Asaf Etgar
Anna Gilbert
Yale University New Haven, USA [email protected]
Yale University New Haven, USA [email protected]
Quanquan C. Liu
Andrew McGregor
Yale University New Haven, USA [email protected]
University of Massachusetts Amherst, USA [email protected]
ABSTRACT We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm—read edges from the stream until 𝑄 triangles are observed in the prefix, then output 𝑄 (𝑚/𝑆) 3 where 𝑆 is the stopping length—and prove that, when the maximum number of triangles incident to any edge satisfies 𝜂 ≤ 𝑇 2/3 , this is a (1 ± 𝜀)-approximation of 𝑇 with probability 1 − 𝛿 using 𝑂 (𝜀 −2 log(1/𝛿) 𝑚/𝑇 1/3 ) memory. Crucially, the algorithm does not need any a priori estimate of 𝑇 , in sharp contrast with state-of-the-art sampling-rate based algorithms [19, 30]. 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% error at a 10% prefix, without using 𝑇 . At a fixed stored-edge budget, variancereduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, 1.8 × 109 edge graph, the threshold algorithm reads 0.46% of the stream and returns 3.8% error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap. PVLDB Reference Format: Asaf Etgar, Anna Gilbert, Quanquan C. Liu, and Andrew McGregor. Scalable Triangle Counting: The Threshold Algorithm. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/WildAlg/threshold-algorithm.
1
INTRODUCTION
Counting the number of triangles 𝑇 in a massive graph 𝐺 = (𝑉 , 𝐸) is one of the most-studied primitives in scalable graph data science [2, This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX
6–9, 12, 13, 20, 22]. In the single-pass streaming model, an algorithm sees the edges of 𝐺 one at a time and must output an estimate of 𝑇 using memory much smaller than |𝐸| = 𝑚. Sampling primitives are the standard design paradigm in this setting. There is also a long line of work on counting triangles via sublinear time algorithms that, potentially in addition to sampling, may make various queries to the graph [1, 3, 4, 11, 29]. Worst-case lower bounds make this problem challenging: even on random-order streams, any (1 + 𝜀)-approximation requires √ √ Ω(𝜀 −2𝑚/ 𝑇 ) memory when 𝑇 ≤ 𝑚 [19]. State-of-the-art randomorder algorithms [19, 30, 31] attain this bound up to log factors, and all utilize a sample-based approach: They set a sampling rate 𝑝 (or multiple rates) and sample edges as they arrive. Crucially, they are all 𝑇 -aware and require an a priori constant-factor estimate of 𝑇 to set their sampling rate. This requirement is prohibitive on real-world streams: even two snapshots of the same network can differ in 𝑇 by an order of magnitude. Another family of triangle counting algorithms are 𝑇 -free and do not require an estimate on 𝑇 [9, 14, 17, 21, 26, 27, 32]. These algorithms are provided with a specified memory budget 𝑀, and utilize reservoir or budget sampling to keep a variance-reducing set, typically alongside a running unbiased triangle count. While these families of algorithms do not assume a priori knowledge of 𝑇 , both families suffer from scalability and adaptability issues. First, they require a full pass over the entire stream of edges. When graphs grow in orders of magnitude, even a single pass could be the runtime bottleneck for an algorithm, even if all other parameters are set optimally. Secondly, they rely on input parameters to guarantee accuracy; e.g., a sufficiently large memory budget. This paper studies a remarkably simple alternative: An algorithm that returns a global estimate of 𝑇 while only looking at a small prefix of the stream and without an initial estimate of 𝑇 or a memory budget. In a random order stream, any prefix consists of a uniform sample of edges drawn without replacement. Consequently, rather than forcing a full pass over the stream, our algorithm halts when a prefix is large enough to serve as a signal for the entire graph. A major benefit of the algorithm is that said prefix is self-selected by the algorithm and does not need to be prescribed, while still guaranteeing a tight approximation of 𝑇 . The algorithm is surprisingly simple to implement, and different implementations allow the user to adjust the space-time-accuracy tradeoff according to use case constraints.
Algorithm 1 Threshold algorithm for random-order triangle counting.
More formally, let 𝐺 = (𝑉 , 𝐸) be a simple graph with 𝑚 = |𝐸| edges and 𝑇 triangles. For each edge 𝑒, let 𝜏 (𝑒) denote the number of triangles containing 𝑒, and let
Require: Stream length 𝑚; triangle threshold 𝑄; random-order stream of edges of 𝐺. 1: S ← ∅; adjacency list 𝐴 ← ∅; b 𝑡 ← 0. 2: for each arriving edge 𝑒 = (𝑢, 𝑣) do b 3: 𝑡 ←b 𝑡 + |𝑁𝐴 (𝑢) ∩ 𝑁𝐴 (𝑣)| ⊲ triangles closed by inserting 𝑒 4: S ← S ∪ {𝑒}; update 𝐴 to include 𝑒. 5: if b 𝑡 ≥ 𝑄 then break 6: 𝑆 ← |S|. 3 b=𝑄 · 𝑚 . 7: return 𝑇 𝑆
𝜂 := max 𝜏 (𝑒). 𝑒 ∈𝐸
Throughout, we assume 0 < 𝜀 ≤ 1/2 and 0 < 𝛿 < 1/10. We consider the stochastic process of drawing random edges from 𝐺 without replacement until some prescribed number 𝑄 of triangles is observed (assuming 𝑄 ≤ 𝑇 ). Let 𝑆 be the random variable corresponding to the number of edges sampled by this process. Theorem 1.1. Assume 𝜂 ≤ 𝑇 2/3 and set 𝑄 = 𝑐 0𝜀 −6 log3 (4/𝛿) for a sufficiently large constant 𝑐 0 > 0. Then 𝑚 3 𝑇b := 𝑄 𝑆 is a (1 ± 𝜀) approximation of 𝑇 with probability at least 1 −𝛿. Furthermore, 𝑆 = 𝑂 (𝜀 −2 log(1/𝛿) 𝑚/𝑇 1/3 ) with probability at least 1 − 𝛿.
with error ≈ 1 and need 97–98% of the stream to reach 5–10% error, while Threshold returns after reading a very small prefix, reading up to 215× fewer edges on com-friendster, and its GBBS [10] implementation scales to a 25× speedup on 64 cores.
The argument extends to arbitrary 𝜂, but then the choice of 𝑄 depends1 on the unknown ratio 𝜂/𝑇 . e(𝑚/𝑇 1/3 ) space. This is a factor ≈ 𝑇 1/6 more Our algorithm uses 𝑂 than the space used by McGregor and √ Vorotnikova [19] (henceforth MV20) near both the optimal 𝑚/ 𝑇 and the lower bound √ √ Ω(𝜀 −2𝑚/ 𝑇 ) of [19] (for 𝑇 ≤ 𝑚). The experiments show that this premium buys a different operating point: the algorithm self-selects 1–6.6% prefixes with single-digit error on real temporal streams, reads only 0.46% of the 1.8 × 109 -edge com-friendster stream with 3.8% error, and converts the main work into parallel static triangle counting on the stored prefix. Thus the tradeoff is qualitative rather than only asymptotic: instead of spending a full pass and a stale estimate of 𝑇 , the threshold rule allocates space from the observed stream and returns before the input is exhausted.
2
THE THRESHOLD ALGORITHM
We now describe the algorithm that realizes the stochastic process analyzed in Theorem 1.1. The algorithm receives a random-order stream of 𝑚 edges from a graph 𝐺 and is given a single integer parameter 𝑄, the triangle threshold. It keeps every arriving edge in memory and incrementally counts triangles closed by each new edge; once 𝑄 triangles have been observed it stops storing edges and returns its estimate. The implementation maintains S as a hash set and 𝐴 as hash- based adjacency lists; each edge insertion costs 𝑂 deg𝐴 (𝑢)+deg𝐴 (𝑣) time, so the total running time is dominated by the cost of the triangle enumeration inside the prefix of length 𝑆. Memory usage is 𝑂 (𝑆) machine words for the stored edges plus 𝑂 (𝑆) for the adjacency structure.
Contributions. • Section 2 presents the streaming algorithm that realizes Theorem 1.1 (Algorithm 1). The algorithm has only a single tunable parameter, 𝑄, and does not require any a priori estimate of 𝑇 or space budget. • Section 3–Section 4 prove Theorem 1.1 via Schudy–Sviridenko concentration on the independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. As a byproduct of our analysis, we improve the bound on the sampling probability 𝑝 by polylogarithmic factors, thereby improving the analysis for DOULION [30] and the subsequent work on triangle sparsifiers [31]. • Section 5 evaluates the algorithm on six real temporal streams and two large-scale graphs (by order of magnitude). The threshold 𝑄 acts as a smooth self-adapting knob: accuracy increases with 𝑄 and our Threshold algorithm reads only 0.46%–6.6% of the stream, with single-digit error. Against MV20 [19] and a broad set of 𝑇 -free baselines, Threshold is within 0.08 absolute error of the best equal-space method. The main advantage of our algorithm is the early-stop feature: forced to stop at the Threshold prefix, native reservoir samplers undershoot the triangle count
2.1
Theoretical guarantees
Algorithm 1 is the algorithm to which Theorem 1.1 directly refers. We restate the guarantee in terms of the algorithm’s parameters. Theorem 2.1 (Restatement of Theorem 1.1). Assume 𝜂 ≤ 𝑇 2/3 and set 𝑄 = 𝑐 0 𝜀 −6 log3 (4/𝛿) for a sufficiently large constant 𝑐 0 > 0. Let 𝑆 be the stopping time of Algorithm 1. Then 𝑇b = 𝑄 (𝑚/𝑆) 3 satisfies Pr (1 − 𝜀) 𝑇 ≤ 𝑇b ≤ (1 + 𝜀) 𝑇 ≥ 1 − 𝛿, and 𝑆 = 𝑂 𝜀 −2 log(1/𝛿) · 𝑚/𝑇 1/3 with probability at least 1 − 𝛿. Section 3 and Section 4 give the proof. In Section 3, we analyze sufficient conditions for tight concentration of the sampled number of triangles in the independent-edge sampling setup via the Schudy–Sviridenko inequality [24]. In Section 4, we analyze the algorithm’s stopping time 𝑆. Because the prefix of a random order stream behaves like a uniform sample without replacement of the edges, bounding 𝑆 directly is challenging. To overcome this, we couple the prefix with two binomial random variables 𝑋 1 and 𝑋 2 which represent prefix lengths drawn at an over-sampling rate 𝑟 1 and an under sampling rate 𝑟 2 . Crucially, a random-length prefix behaves identically to analyzing independent edge sampling allowing us to utilize results from Section 3. By carefully selecting the
1 One can resolve this limitation by using a learning-augmented predictor to estimate
this ratio from initial stream data. This method is studied in the companion paper [18], which uses prefix bucket profiles and deep neural networks to estimate triangle and 4-cycle counts on graph families in both random and arbitrary orders. 2
rates and the threshold 𝑄, we are able to couple 𝑆 with 𝑋 1, 𝑋 2 , and consequently guarantee both tight concentration of 𝑆 and of the estimator 𝑇b. Finally, we prove Theorem 2.1 in the parameter-free form under the promise 𝜂 ≤ 𝑇 2/3 .
P [ |𝑓 (𝑌 ) − E𝑓 (𝑌 )| ≥ 𝜆 ] ≤ ( 1/𝑟 )! 𝜆2 𝜆 𝑒 2 · max max exp − , max exp − . 1≤𝑟 ≤𝑞 1≤𝑟 ≤𝑞 𝜇 0 𝜇𝑟 𝐿 𝑟 Γ 𝑟 𝑅 𝑞 𝜇𝑟 𝐿 𝑟 Γ 𝑟 𝑅 𝑞
Practical setting of 𝑄. The constant 𝑐 0 in Theorem 2.1 is nonexplicit, so rather than fixing 𝑄 as a number we fix the space budget directly and let it induce 𝑄. Given a target memory fraction 𝑓 , we run the loop of Algorithm 1 until exactly 𝑆 = ⌈𝑓 𝑚⌉ edges have 𝑡 (𝑚/𝑆) 3 , where b been stored, then report 𝑇b = b 𝑡 is the number of triangles closed within the stored prefix. This is exactly Algorithm 1 run with the implicit threshold 𝑄 = b 𝑡 : because a uniform random prefix of fraction 𝑓 contains ≈ 𝑓 3𝑇 triangles, the realized threshold concentrates at 𝑄 ≈ 𝑓 3𝑇 . Sweeping the memory budget 𝑓 is therefore equivalent to sweeping 𝑄, and—crucially—requires no knowledge of 𝑇 , since 𝑓 is a quantity the operator already controls. (Deployed the other way around, with a fixed 𝑄 and no budget, the stopping time 𝑆 instead self-adjusts to the data and attains the 𝑂 (𝜀 −2 log(1/𝛿) 𝑚/𝑇 1/3 ) bound of Theorem 2.1 automatically.) In the implementation the target 𝑆 = ⌈𝑓 𝑚⌉ is reached by a geometric doubling schedule; on the dense real streams the process halts essentially at ⌈𝑓 𝑚⌉, while on sparse streams the realized 𝑆 can exceed the target before 𝑄 triangles accumulate, so we always report the realized 𝑆/𝑚.
3.2
We wish to bound the parameters 𝜇𝑟 of Theorem 3.1 for the triangle counting polynomial 𝑌 . Since no edge can appear twice in a single triangle and each triangle is comprised of 3 edges, 𝑌 is multilinear of degree 3. That is, Γ = 1 and 𝑞 = 3. The random variables 𝑋𝑒 are Bernoulli, |𝑋𝑒 | ≤ 1 and therefore a uniform moment bound is 𝐿 = 1. For 1 ≤ 𝑟 ≤ 𝑞 = 3 we compute a bound on 𝜇𝑟 . Lemma 3.2. For the triangle-counting polynomial ∑︁ Ö 𝑌 = 𝑋𝑒 , Δ 𝑒 ∈Δ
the Schudy–Sviridenko parameters satisfy 𝜇 0 = 𝑝 3𝑇 , 𝜇1 = 𝑝 2𝜂, 𝜇 2 ≤ 𝑝, and 𝜇 3 ≤ 1. Proof. First, " 𝜇 0 = E[𝑌 ] =
E
# Ö
𝑋𝑒 = 𝑝 3𝑇 .
𝑒 ∈Δ
For 𝑟 = 1, differentiating with respect to an edge-variable 𝑋𝑒 gives ∑︁ Ö 𝜕𝑌 = 𝑋𝑓 . 𝜕𝑋𝑒 Δ∋𝑒 𝑓 ∈Δ\{𝑒 }
Here, the notation Δ ∋ 𝑒 means counting over all triangles containing the edge 𝑒. Taking expectations, ∑︁ 𝜕𝑌 E = 𝑝 2 = 𝑝 2𝜏 (𝑒). 𝜕𝑋𝑒 Δ∋𝑒
CONCENTRATION OF TRIANGLES VIA INDEPENDENT EDGE SAMPLING
Therefore 𝜇 1 = max𝑒 𝑝 2𝜏 (𝑒) = 𝑝 2𝜂. 2𝑌 For 𝑟 = 2, fix distinct edges 𝑒, ℎ. Then 𝜕𝑋𝜕𝑒 𝜕𝑋 is nonzero if and ℎ only if 𝑒 and ℎ share a common triangle. Since the graph is simple, two edges share at most one triangle. Hence 𝜕 2𝑌 E ≤ 𝑝, 𝜕𝑋𝑒 𝜕𝑋ℎ
Fix a sampling rate 𝑝 ∈ (0, 1], and sample each edge independently with probability 𝑝. For each edge 𝑒 ∈ 𝐸, let 𝑋𝑒 ∈ {0, 1} be the indicator that 𝑒 is sampled. Define the triangle counting polynomial ∑︁ Ö 𝑌 = 𝑋𝑒 , Δ 𝑒 ∈Δ
where the sum is over all triangles Δ in 𝐺. Then 𝑌 is the number of sampled triangles, and 𝑌 𝑇ˆ := 3 𝑝 is the natural unbiased estimator for 𝑇 . The goal of this section is to derive a sufficient condition on 𝑝 ensuring P |𝑇ˆ − 𝑇 | ≥ 𝜀𝑇 ≤ 𝛿.
3.1
∑︁ Δ
Heavy-edge regime. When 𝜂 > 𝑇 2/3 , Theorem 1.1 no longer applies in the parameter-free form, but the analysis of Section 3– Section 4 still gives a (1 ± 𝜀)-approximation provided 𝑄 is set to absorb the factor 𝜂/𝑇 . The ratio 𝜂/𝑇 can be estimated from a small prefix using learned features of the stream; we focus the experiments below on the parameter-free regime and leave a full learningaugmented evaluation to companion work.
3
Applying the concentration result to triangle counting
for all pairs of edges 𝑒, ℎ, and thus 𝜇 2 ≤ 𝑝. For 𝑟 = 3, recall that 𝑌 is multilinear of degree 3 with coefficient 1 for all summands. Therefore the third mixed derivative is 1 if and only if the three differentiated edges form a triangle and 0 otherwise. Hence 𝜇3 ≤ 1. □ We proceed to apply Theorem 3.1 according to the bounds computed. Set 𝜆 := 𝜀𝜇 0 = 𝜀𝑝 3𝑇 and then P |𝑇ˆ − 𝑇 | ≥ 𝜀𝑇 = P [ |𝑌 − E𝑌 | ≥ 𝜀E𝑌 ] = P [ |𝑌 − 𝜇 0 | ≥ 𝜆 ] .
The Schudy–Sviridenko inequality
We use the following result by Schudy and Sviridenko [24, Theorem 1.4].
We set
Theorem 3.1 (Schudy–Sviridenko). Let 𝑓 (𝑌1, . . . , 𝑌𝑛 ) be a polynomial of degree 𝑞 and maximal variable power Γ in independent moment-bounded random variables 𝑌1, . . . , 𝑌𝑛 , all with the same moment-boundedness parameter 𝐿. Let 𝜇𝑟 denote the maximum expected partial derivative of order 𝑟 and 𝜇 0 = E[𝑓 (𝑌 )]. Then there is an absolute constant 𝑅 ≥ 1 such that, for every 𝜆 > 0,
1/𝑟 𝜆2 𝜆 , 𝐵 := 𝑟 𝜇 0 𝜇𝑟 𝑅 3 𝜇𝑟 𝑅 3 where 𝑅 is the constant from Theorem 3.1. In this notation, Theorem 3.1 states 𝐴𝑟 :=
P [ |𝑌 − 𝜇 0 | ≥ 𝜆 ] ≤ 𝑒 2 exp (− min{𝐴1, 𝐴2, 𝐴3, 𝐵 1, 𝐵 2, 𝐵 3 }) , 3
(2) The threshold 𝑄 is a reliable indicator that we have processed an 𝑟 -fraction of the stream, and not much more.
Using the upper bounds on 𝜇𝑟 , we obtain the following lower bounds on 𝐴𝑟 , 𝐵𝑟 : 𝐴1 ≥
𝜀 2 𝑝𝑇 , 𝜂𝑅 3
𝐵1 ≥
𝜀𝑝𝑇 , 𝜂𝑅 3
𝜀 2 𝑝 2𝑇 , 𝑅3 2 1/2 𝜀𝑝 𝑇 𝐵2 ≥ , 𝑅3
𝐴2 ≥
𝜀 2 𝑝 3𝑇 , 𝑅3 3 1/3 𝜀𝑝 𝑇 𝐵3 ≥ . 𝑅3
Then, instead of directly analyzing 𝑆, we couple 𝑆 with two random variables 𝑋 1, 𝑋 2 with two distinct sampling rates 𝑟 1, 𝑟 2 . We think of 𝑟 1 as an over sampling rate, and 𝑟 2 as an under sampling rate. Crucially, taking a prefix of a random length 𝑋𝑖 behaves like independent edge sampling from 𝐸, allowing us to utilize Theorem 3.3. Our choice of a threshold 𝑄 will separate these two sampling rates, and imply strong concentration of 𝑆. We proceed to formalize this approach.
𝐴3 ≥
Since 𝜀 ≤ 1, 𝐵 1 ≥ 𝐴1 . Since 𝑝 ≤ 1 we have 𝐴2 ≥ 𝐴3 . Moreover, 1/2 1/2 1/3 𝜀𝑝 2𝑇 /𝑅 3 ≥ 𝜀𝑝 3𝑇 /𝑅 3 ≥ 𝜀𝑝 3𝑇 /𝑅 3 and therefore 𝐵 2 ≥ 𝐵 3 . Thus the inequality simplifies to P |𝑇ˆ − 𝑇 | ≥ 𝜀𝑇 ≤ =
𝑒 2 exp (− min {𝐴1, 𝐴3, 𝐵 3 }) ( 1/3 )! 𝜀 2 𝑝𝑇 𝜀 2 𝑝 3𝑇 𝜀𝑝 3𝑇 2 , , . 𝑒 exp − min 𝜂𝑅 3 𝑅3 𝑅3
4.1
Coupling the Stopping Time
Let 𝑝 ★ denote the critical value of 𝑝 from Theorem 3.3. Let 𝑟 ≥ (1 − 𝜀) −1 · max(𝑝 ★, 3𝜀 −2 log(1/𝛿)/𝑚) . (1) Define two sampling rates 𝑟 1 := (1 + 𝜀) 𝑟
We arrive at the following sufficient condition for concentration of 𝑇ˆ around 𝑇 .
and
𝑟 2 := (1 − 𝜀) 𝑟 .
Consider two random variables 𝑋 1 ∼ Bin(𝑚, 𝑟 1 ) and 𝑋 2 ∼ Bin(𝑚, 𝑟 2 ). Theorem 3.3. Let 𝐺 be a simple graph with 𝑇 triangles and
Lemma 4.1. For each 𝑖 ∈ {1, 2}, the random set 𝐸 (𝑋𝑖 ) has the same distribution as an independent 𝑟𝑖 -sample of the edge set 𝐸.
𝜂 = max 𝜏 (𝑒). 𝑒 ∈𝐸
Sample each edge independently with probability 𝑝, let 𝑌 be the number of sampled triangles, and define 𝑇ˆ = 𝑌 /𝑝 3 . There is an absolute constant 𝐶 > 0 such that if 𝑝 ≥ 𝑝 ★ where ! 𝐶 𝜂 𝐿 𝐶 𝐿 1/3 𝐶 𝐿 3 1/3 𝛿 𝛿 𝛿 ★ 𝑝 (𝜀, 𝛿) = max , , (2) 2 2 𝜀𝑇 𝜀𝑇 𝜀𝑇 where 𝐿𝛿 = 2 + log(1/𝛿). Then P |𝑇ˆ − 𝑇 | ≥ 𝜀𝑇 ≤ 𝛿.
Proof. Fix 𝑖 ∈ {1, 2} and a subset 𝐹 ⊆ 𝐸 of size 𝑘. Then P[𝐸 (𝑋𝑖 ) = 𝐹 ]
P[𝑋𝑖 = 𝑘] ·
=
𝑚 𝑘 1 𝑟 (1 − 𝑟𝑖 )𝑚−𝑘 · 𝑚 𝑘 𝑖 𝑘
=
𝑟𝑖𝑘 (1 − 𝑟𝑖 )𝑚−𝑘 ,
𝑚 𝑘
which is exactly the probability that 𝐹 is obtained by keeping each edge independently with probability 𝑟𝑖 . □
Proof. A sufficient condition for Eq. (1) to be bounded above by 𝛿 is: 1/3 ! 𝜀 2 𝑝𝑇 𝜀 2 𝑝 3𝑇 𝜀𝑝 3𝑇 ≥ 𝐿𝛿 . (3) min , , 𝜂𝑅 3 𝑅3 𝑅3
Consequently, the number of triangles in 𝐸 (𝑋𝑖 ) has the same distribution as the random variable 𝑌 from Section 3 with sampling rate 𝑟𝑖 . Set 𝑄 = 𝑟 3𝑇 . We show that the choice of 𝑄 separates the two sampling rates with probability at least 1 − 𝛿. Denote by P𝑝=𝑟𝑖 the probability space where each edge in 𝐸 is sampled independently with probability 𝑟𝑖 .
Take 𝐶 = 𝑅 3 where 𝑅 is the constant from Theorem 3.1. Rearranging the three lower bounds on 𝑝 ★ in (2) gives exactly the displayed minimum condition in (3). □
4
1
=
STOPPING TIMES FOR EDGE SAMPLING WITHOUT REPLACEMENT
Lemma 4.2. P𝑝=𝑟 1 [𝑌 > 𝑄] ≥ 1 − 𝛿 and P𝑝=𝑟 2 [𝑌 < 𝑄] ≥ 1 − 𝛿. Proof. Recall that Theorem 3.3 applies at any sample rate that is at least 𝑝 ★, and that 𝑟 1, 𝑟 2 ≥ (1 − 𝜀)𝑟 ≥ 𝑝 ★. Then for 𝑟 1 by Theorem 3.3 with probability at least 1 − 𝛿,
The goal of this section is to apply the independent sampling result from Section 3 to a sampling without replacement setting. Fix a uniformly random ordering of the 𝑚 edges of 𝐺. For 𝑡 ∈ {0, 1, . . . , 𝑚}, let 𝐸 (𝑡) denote the set of the first 𝑡 edges in this ordering, and let 𝑁 (𝑡) denote the number of triangles contained in 𝐸 (𝑡). We wish to analyze the concentration of the stopping time
𝑌 ≥ (1 − 𝜀)𝑟 13𝑇 = (1 − 𝜀)(1 + 𝜀) 3𝑄 > 𝑄, which proves the first inequality. Similarly, for 𝑟 2 with probability at least 1 − 𝛿,
𝑆 := min{ 𝑡 : 𝑁 (𝑡) ≥ 𝑄 }.
𝑌 ≤ (1 + 𝜀)𝑟 23𝑇 = (1 + 𝜀)(1 − 𝜀) 3𝑄 < 𝑄 .
for an appropriate choice of a threshold 𝑄. Bounding 𝑆 directly is difficult as edges in 𝐸 (𝑡) are not drawn independently. In order to utilize Theorem 3.3, we look for a sampling rate 𝑟 with the following properties: (1) The rate 𝑟 is large enough to guarantee tight concentration around 𝑇 as in Theorem 3.3.
proving the second inequality.
□
Combined with Lemma 4.1, Lemma 4.2 transfers immediately to random prefixes. Lemma 4.3. P 𝑁 (𝑋 1 ) > 𝑄 ≥ 1 − 𝛿 and P 𝑁 (𝑋 2 ) < 𝑄 ≥ 1 − 𝛿. 4
4.3
Proof. By Lemma 4.1, P 𝑁 (𝑋 1 ) > 𝑄 = P𝑝=𝑟 1 𝑌 > 𝑄 ≥ 1 − 𝛿, and a similar argument holds for 𝑁 (𝑋 2 ).
Proof of Main Theorem
Proof of Theorem 1.1. Recall that 𝐶 𝜂 𝐿𝛿 𝐶 𝐿𝛿 1/3 ★ 𝑝 (𝜀, 𝛿) = max , , 2 𝜀 2𝑇 𝜀𝑇
□
We can now bound the stopping time 𝑆.
! 1/3 𝜀𝑇
𝐶 𝐿𝛿3
If 𝜂 ≤ 𝑇 2/3 , all three terms are 𝑂 (𝜀 −2 log(1/𝛿)/𝑇 1/3 ) and so Corollary 4.4 (Concentration of 𝑆).
𝑝 ★ = 𝑂 (𝜀 −2 log(1/𝛿)/𝑇 1/3 ) .
Pr[𝑚𝑟 (1 − 𝜀) 2 < 𝑆 < 𝑚𝑟 (1 + 𝜀) 2 ] ≥ 1 − 4𝛿 .
Hence, we set 𝑟 = 𝑐 01/3𝜀 −2 log(1/𝛿)/𝑇 1/3 for sufficiently large 𝑐 0 . Since 𝑇 1/3 ≤ 𝑚,
Proof. Recall that 𝑆 = min{𝑡 : 𝑁 (𝑡) ≥ 𝑄 }. By Lemma 4.3, 𝑁 (𝑋 1 ) > 𝑄 with probability at least 1 − 𝛿, and therefore 𝑋 1 ≥ 𝑆. Similarly, 𝑋 2 ≤ 𝑆. with probability at least 1 − 𝛿 By the union bound
𝑐 01/3𝜀 −2 log(1/𝛿) 𝑇 1/3
P [𝑋 2 < 𝑆 < 𝑋 1 ] ≥ 1 − 2𝛿 .
𝑟 ≥ (1 − 𝜀) −1 max(𝑝 ★, 3𝜀 −2 log(1/𝛿)/𝑚) . Consequently
P [𝑋 1 < (1 + 𝜀)𝑟 1𝑚] ≥ 1 − 𝛿 𝑟 3𝑇 = and similarly P [𝑋 2 > (1 − 𝜀)𝑟 2𝑚] ≥ 1 − 𝛿.
𝑐 01/3𝜀 −2 log(1/𝛿) 𝑇 1/3
!3 𝑇 = 𝑐 0𝜀 −6 log3 (1/𝛿).
3 Setting 𝑄 = 𝑟 3𝑇 = 𝑐 0𝜀 −6 log3 (1/𝛿) and 𝑇b = 𝑚 𝑄, by Corollary 𝑆 4.5 𝑇 𝑇 Pr ≤ 𝑇b ≤ ≥ 1 − 4𝛿 . (1 + 𝜀) 6 (1 − 𝜀) 6 Reparameterizing by 𝜀 ← 𝜀/10 and 𝛿 ← 𝛿/4 gives the result. □
Taking the union bound over both gives P [ (1 − 𝜀)𝑟 2𝑚 ≤ 𝑋 2 and 𝑋 1 ≤ (1 + 𝜀)𝑟 1𝑚] ≥ 1 − 2𝛿. Plugging in the definition of 𝑟 1, 𝑟 2 gives P (1 − 𝜀) 2𝑟𝑚 ≤ 𝑋 2 and 𝑋 1 ≤ (1 + 𝜀) 2𝑟𝑚 ≥ 1 − 2𝛿.
5
Alongside P [𝑋 2 < 𝑆 < 𝑋 1 ] ≥ 1 − 2𝛿, the union bound implies the corollary. □
EXPERIMENTAL EVALUATION
The experiments test the main promise of the paper: the threshold algorithm chooses a short prefix on its own and estimates 𝑇 accurately by only looking at the prefix of the stream. With a fixed stored-edge budget, the best reservoir samplers are often more accurate because they produce an estimate after reading the entire stream; the threshold algorithm is the first early-stopping algorithm that achieves comparable approximations looking at only a subset of the stream. Our advantage is that the algorithm stops early, needs no estimate of 𝑇 , and still returns a whole-graph estimate.
Designing a Triangle Estimator
By Corollary 4.4, the number of edges one must process before seeing 𝑄 triangles is tightly concentrated around 𝑚𝑟 . We wish to use 𝑆 as an estimator for the underlying sampling rate 𝑟 . Since 𝑇 = 𝑄/𝑟 3 and 𝑆 ≈ 𝑚𝑟 , this motivates the following estimate of the number of triangles in 𝐺:
Experimental Setup. We use six temporal streams from SNAP [16], the Network Repository [23], and KONECT [15] (copresence-InVS15, reddit, sx-superuser, wiki-talk-temporal, ca-cit-HepPh (the KONECT co-citation network; 𝑚 = 3,148,447), and sx-stackoverflow), plus com-orkut and com-friendster for large-scale analysis. We remove self-loops and duplicate edges. All accuracy experiments use uniformly random edge orders, matching Theorem 2.1; the true triangle count is used only for scoring. Algorithm 1 is implemented in GBBS [10] with ParlayLib [5]; ground-truth counts use Shun– Tangwongsan [28]. We re-implemented the remaining baselines: TRIÈST [9], ThinkD [27], WRS [26], GREAT [32], and MASCOT [17]; DOULION [30], MV20 [19], and triangle sparsification [31]; wedge and colorful samplers [21, 25]; and related estimators [7, 13, 14, 22]. All use the same C++/GBBS setup so every method sees identical input, representation, timing, and error accounting. Unless stated otherwise, accuracy entries report E𝜋 [|𝑇b𝜋 − 𝑇 |/𝑇 ], where 𝜋 ranges over independent random stream orders (every trial draws a fresh seeded permutation; no permutation is reused across operating
𝑚 3 𝑇b := 𝑄 . 𝑆 Corollary 4.5 (Triangle Estimation). 𝑇 𝑇 b ≤ ≤ 𝑇 ≥ 1 − 4𝛿 . Pr (1 + 𝜀) 6 (1 − 𝜀) 6 Proof. Since 𝑚 3 𝑚 3 𝑚𝑟 3 𝑇b = 𝑄 = 𝑟 3𝑇 = 𝑇, 𝑆 𝑆 𝑆 By Corollary 4.4, with probability at least 1 − 4𝛿 𝑚𝑟 (1 − 𝜀) 2 < 𝑆 ≤ 𝑚𝑟 (1 + 𝜀) 2 . So with probability at least 1 − 4𝛿 𝑚𝑟 3 𝑇 𝑇 ≤ 𝑇 ≤ . 6 (1 + 𝜀) 𝑆 (1 − 𝜀) 6
𝑐 01/3𝜀 −2 log(1/𝛿) 𝑚
and therefore
Applying the standard multiplicative Chernoff bound to 𝑋 1 ∼ Bin(𝑚, 𝑟 1 ) gives
4.2
≥
□ 5
Graph
vertices
edges
triangles
copresence-InVS15 reddit sx-superuser wiki-talk-temporal ca-cit-HepPh sx-stackoverflow
219 35,776 192,409 1,094,018 28,093 2,584,164
16,725 124,330 714,570 2,787,967 3,148,447 28,183,518
713,002 406,391 1,543,161 8,113,676 195,758,685 114,206,974
com-orkut com-friendster
3,072,441 65,608,366
117,185,083 1,806,067,135
627,584,181 4,173,724,142
mean relative error (%)
Table 1: Graphs used in the evaluation. The first six are real temporal streams; the last two are static graphs streamed in uniformly random order for scalability.
Threshold
mean rel. error (%)
copresence
5.2
7.8 4.7 3.8 4.8 5.5 7.2
101
102
mean rel. error (%)
sx-superuser 101 100
100
10 1
10 1
10 1
10 2
101
101
wiki-talk
101
ca-cit-HepPh
sx-stackoverflow 101
101
101 100
100
100
10 1
10 1
10 1
10 2
10 2 101
2.6 6.1 3.2 1.5 0.3 0.7
MV20 (given T) reddit
101
100
10 2
𝑄 pred. 𝑆/𝑚 err. err.@10% 6.2 6.6 9.2 3.3 1.0 0.9
101
realized prefix S/m (%)
MV20 uses nearly the optimal amount of space; empirically, however, its realized footprint is governed by a 𝑇 -dependent floor that is independent of the accuracy parameter 𝜀: across our streams the (corrected) implementation stores 49–77% of all edges regardless of the requested budget (65% on com-orkut, 77% on sx-stackoverflow). Given that space, MV20 with the true 𝑇 is accurate–often more accurate than the threshold algorithm at a matched nominal 𝜀. However, it stores roughly an order of magnitude more edges than our self-selected prefix at comparable error. Moreover, a single MV20 run on the 1.8-billion-edge com-friendster did not complete within 10 hours at 16 cores, whereas the threshold algorithm finishes every operating point in seconds (Section 5.4). The threshold algorithm reaches the single-digit accuracy regime without a triangle-count estimate while reading and storing only a small prefix.
Table 2: Self-sizing on real streams. 𝑄 is the target number of prefix triangles; all other entries are percentages. The final column is a separate fixed-10%-prefix check.
4.1 5.0 6.9 2.3 0.6 0.8
wiki-talk ca-cit-HepPh sx-stackoverflow
Figure 1: Sweep of 𝑄 values. Error decreases while the fraction of space usage increases as 𝑄 grows. The algorithm is given 𝑄 only, never 𝑇 or a memory budget.
Self-Sizing and Accuracy
copresence 50 reddit 50 sx-superuser 500 wiki-talk 100 ca-cit-HepPh 50 sx-stackoverflow 50
copresence reddit sx-superuser
100
Table 2 gives selected operating points while Fig. 1 shows the full sweep. The result is that 𝑄 behaves as a smooth accuracy knob: increasing 𝑄 lowers error while increasing the self-selected prefix, and 𝑆/𝑚 matches predicted space usage (labeled “pred.”). The algorithm takes only the triangle threshold 𝑄: it reads until the prefix contains 𝑄 triangles, stops at 𝑆 edges, and returns 𝑄 (𝑚/𝑆) 3 . Since a random 𝑓 -prefix contains about 𝑓 3𝑇 triangles, we expect 𝑆/𝑚 ≈ (𝑄/𝑇 ) 1/3 . We choose the smallest swept 𝑄 with single-digit mean error, reading only 0.9–9.2% of each stream. The last column is a separate 10%-prefix run (30 random orders); for ca-cit-HepPh and sx-stackoverflow, this is much larger than the threshold 1.0% and 0.9% prefixes that were used by our algorithm.
Stream
100
10 1
points or across algorithms). We use: 30 random orders for fixedprefix accuracy rows (including the err.@10% column); 10 per 𝑄 for self-sizing; 10 per operating point for MV20; 20 orders for matchedspace and iso-accuracy rows; and 5 for stream-read. Experiments run on shared-cluster nodes with two 32-core Intel Xeon Gold 8562Y+ CPUs, one thread per core, and 1–4 TB of DDR5. The real streams and com-orkut use a 1 TB node; com-friendster uses 4 TB. We compile the GBBS/ParlayLib code with g++.
5.1
101
realized stored edges / m (%)
10 2 100
101
101
Figure 2: Accuracy vs. space usage for the threshold algorithm (red, swept over 𝑄) and MV20 (blue, swept over 𝜀 and given 𝑇 ). Table 3 merges the two fixed-space views. In each cell, the left value is the mean relative error when the baseline receives exactly the threshold-selected budget 𝑀 = 𝑆 and no 𝑇 ; the right value is the smallest budget fraction that matches the best Threshold accuracy target. Thus the matched-space comparison is exact (1.0× the same stored-edge budget), and Threshold is within 0.08 absolute
Comparison with State-of-the-Art
Fig. 2 compares against MV20 [19], the state-of-the-art randomorder streaming algorithm with the best asymptotic bounds. MV20 is given the true value of 𝑇 ; our algorithm is not. Asymptotically 6
error of the best entry in every column. The same-accuracy side shows the complementary tradeoff: the variance-reduced reservoir samplers can match the target with less space on several streams, and Threshold uses at most 12× the smallest matching space, but those methods still spend that memory after reading all 𝑚 edges. Threshold spends more variance, and sometimes more prefix space, to avoid the whole-stream pass.
copresence reddit sx-superuser wiki-talk cit-HepPh stackoverflow com-orkut com-friendster
Books stress test. We also keep the controlled heavy-edge experiment under the neutral name books: each book has one spine edge shared by many triangular pages, and disjoint books are mixed with isolated triangles to sweep 𝜌 = 𝜂 3 /𝑇 2 from 10−7 to 10. At a 5% stored-edge budget, the experiment cleanly explains the theorem’s heavy-edge condition. When 𝜌 ≪ 1, triangles are spread out and wedge sampling is best (0.007 error versus Threshold’s 0.031 at 𝜌 = 10−5 ). Near the boundary the picture reverses: Threshold beats the best space-only baseline at 𝜌 = 0.1 (0.131 versus 0.245) and at 𝜌 = 1 (0.238 versus 0.366). Past the boundary all methods degrade. The point is not that the condition is cosmetic; it is that the transition is visible, and the threshold rule is competitive precisely at that transition.
5.3
0.03
Threshold
0.1
1.0
mean relative error (log)
Figure 3: Early stopping at the threshold prefix 𝑆. Reservoir samplers report the prefix graph and undershoot to error ≈ 1; cubic extrapolation makes them comparable to the threshold algorithm, although the extrapolation still underperforms much of the time. The threshold algorithm is the method that provides this whole-graph estimate natively, with no 𝑇 and no prescribed budget.
ingestion plus all checkpoint counts, excluding input parse and shuffle) takes 0.16 seconds on sx-stackoverflow, 0.53 seconds on com-orkut, and 10.8 seconds on the 1.8-billion-edge com-friendster — an effective rate of 1.7 × 108 stream edges per second on the largest graph. The (corrected) MV20 implementation, which must read the whole stream and build its sketch, takes 200 seconds per trial on com-orkut at the same thread count. Early stopping helps twice: the algorithm skips the remaining 𝑚 − 𝑆 edges, and after materializing the prefix it no longer has to maintain an online triangle estimator through sequential edge updates. The expensive work is instead triangle enumeration on a static prefix, so GBBS [10] parallelizes the edge-local neighbor-intersection counts and reduces the partial counts. The stream-order scan and the search over prefix lengths remain sequential across each graph; the dominant pergraph triangle count is what scales. Fig. 4 shows this parallel side: with the stream order fixed (so the work is identical at every thread count), the GBBS implementation reaches an 18.9× speedup at 32 threads on com-orkut and 23.1× at 32 threads on com-friendster (72% parallel efficiency); the larger graph scales better because its prefix exposes more parallel triangle-enumeration work per sequential byte.
Early Stopping: The Previously Missing Domain
We now investigate the effect of our key novelty on accuracy and space usage. Table 4 shows that the threshold algorithm returns an estimate after seeing only 0.46%–6.6% of the stream. Reservoir samplers, budget samplers, and related streaming estimators [7, 9, 13, 14, 17, 20–22, 25–27, 30–32] are also single-pass algorithms, but they must see all 𝑚 edges before returning the estimate. This is the resource that matters when the input itself is the bottleneck: on com-friendster, the threshold algorithm reads 215× fewer edges before returning an estimate. We next deny the reservoir samplers their whole-stream pass. In Table 5, every method is forced to stop at the same 𝑆-edge prefix selected by the threshold rule and is given no 𝑇 . The off-the-shelf estimators report only the graph they have seen, so their wholegraph estimate undershoots to error ≈ 1. The + (𝑚/𝑆) 3 column is deliberately oracle-aided: a random 𝑓 = 𝑆/𝑚 prefix has about 𝑓 3𝑇 triangles, so it scales the prefix count by (𝑚/𝑆) 3 . Knowing that the selected prefix is meaningful would require the triangle-count scale, essentially the precise value of 𝑇 , so this gives the reservoir samplers far more power than their native interface. Useful early stopping is not just storing a prefix; it is knowing how to extrapolate it without a triangle-count estimate. Finally, Table 6 removes memory as the bottleneck and asks how much of the stream must be read before a whole-graph estimate is within 10% or 5% error. A native reservoir sampler, even with unlimited memory, must read 97–98% of the stream because a random 𝑓 -prefix contains only about 𝑓 3𝑇 triangles. The threshold algorithm reaches comparable accuracy after a 1–7% prefix because it stops when it finds enough triangles and consequently extrapolates that number in its prefix to the entire graph.
5.4
+(m/S)3
native
speedup (streaming phase)
32 16 8 4 2 1
Runtime Scalability
com-orkut (18.9x @ 32t) com-friendster (23.1x @ 32t) ideal
1
2
4
threads
8
16
32
Figure 4: Strong scaling (streaming phase, fixed stream order): 18.9× on com-orkut and 23.1× on the 1.8-billion-edge comfriendster at 32 threads.
The measured streaming phase is consistent with the prefix cost. With 8 threads at a 5% prefix, the median streaming phase (prefix 7
Table 3: Matched-space and same-accuracy comparison. Each cell reports error at the threshold-selected budget 𝑀 = 𝑆 / minimum space needed to match the Threshold target accuracy. The Threshold row gives its matched-space error and the target error@space used for the second quantity. The columns are the streams common to both sweeps. Reservoir methods may win either half, but only after reading the whole stream; Threshold returns from the prefix. Bold marks the best value within each half of a column. Algorithm stored edges 𝑆 / target
sx-superuser
wiki-talk
cit-HepPh
copresence
32,781 / 0.017@18%
131,087 / 0.018@9%
32,781 / 0.010@4%
8,203 / 0.048@13%
1,032 / 0.024@12%
Threshold (ours)
0.065 / 18%
0.039 / 9%
0.056 / 4%
0.094 / 13%
0.095 / 12%
BuriolPODS [7] ColorfulTC [21] Doulion [30] FURL [14] GreatI [32] GreatII [32] GreatPlus [32] MV20 [19] Martingale [9] MascotC [17] MascotI [17] NaiveScale (control) ThinkDAcc [27] ThinkDFast [27] TriangleSparsifier [31] TriestBase [9] TriestImpr [9] WRS [26] WedgeSampling [25]
2.261 / >20% 0.051 / 20% 0.073 / >20% 0.087 / 20% 0.030 / 20% 0.024 / 10% 0.025 / 15% 0.073 / >20% 0.028 / 15% 0.073 / >20% 0.038 / >20% 0.108 / >20% 0.028 / 15% 0.028 / 15% 0.073 / >20% 0.091 / >20% 0.028 / 15% 0.030 / 15% 0.053 / 15%
2.824 / >20% 0.023 / 10% 0.028 / 15% 0.035 / 10% 0.010 / 5% 0.011 / 5% 0.010 / 5% 0.028 / 15% 0.017 / 5% 0.028 / 15% 0.023 / 10% 0.032 / 10% 0.017 / 5% 0.017 / 5% 0.028 / 15% 0.052 / 15% 0.017 / 5% 0.018 / 10% 0.066 / >20%
0.079 / >20% 0.018 / 5% 0.074 / 5% 0.048 / 10% 0.011 / 2% 0.010 / 1% 0.011 / 2% 0.074 / 5% 0.006 / 1% 0.074 / 5% 0.016 / 5% 0.062 / 5% 0.006 / 1% 0.005 / 1% 0.074 / 5% 0.068 / 5% 0.006 / 1% 0.009 / 1% 0.007 / 1%
0.868 / >20% 0.046 / 15% 0.074 / 20% 0.071 / 15% 0.040 / 10% 0.024 / 10% 0.043 / 10% 0.074 / 20% 0.044 / 10% 0.074 / 20% 0.048 / 10% 0.113 / 15% 0.044 / 10% 0.044 / 10% 0.074 / 20% 0.083 / 20% 0.044 / 10% 0.045 / 5% 0.031 / 5%
0.051 / >20% 0.058 / >20% 0.059 / >20% 0.107 / >20% 0.033 / 20% 0.036 / 10% 0.056 / 20% 0.059 / >20% 0.015 / 5% 0.059 / >20% 0.033 / 15% 0.072 / 15% 0.015 / 5% 0.015 / 5% 0.059 / >20% 0.051 / 15% 0.015 / 5% 0.015 / 5% 0.015 / 1%
Table 4: Early stopping. The threshold algorithm halts after 𝑆 edges; any reservoir/sampling baseline must see all 𝑚 edges. On com-friendster this is a 215× stream-read reduction. Stream copresence reddit-hyperlink sx-superuser wiki-talk cit-HepPh sx-stackoverflow com-orkut com-friendster any reservoir/sampling method
6
𝑚
reads 𝑆 𝑆/𝑚 𝑚/𝑆
16,725 1,032 124,330 8,203 714,570 32,781 2,787,967 131,087 3,148,447 32,781 28,183,518 367,018 117,185,083 1,048,594 1,806,067,135 8,388,629 𝑚
Table 5: Forced early stop at our self-selected prefix 𝑆, with budget 𝑀 = 𝑆 and no 𝑇 . Native samplers report the prefix graph and undershoot to error ≈ 1; adding our cubic extrapolation (which requires precise knowledge of 𝑇 ) makes them comparable. The threshold algorithm provides the wholegraph estimate. Best of extrapolated sampler and Threshold is bold.
6.2% 16× 6.6% 15× 4.6% 22× 4.7% 21× 1.0% 96× 1.3% 77× 0.9% 112× 0.5% 215×
𝑚 100%
Stream
𝑆/𝑚 samplers @ 𝑆 + (𝑚/𝑆 ) 3 Threshold (ours)
copresence 6.2% reddit 6.6% sx-superuser 4.6% wiki-talk 4.7% cit-HepPh 1.0% stackoverflow 1.3% com-orkut 0.9% com-friendster 0.46%
1×
CONCLUSION
The threshold algorithm reframes streaming triangle counting as a stopping problem rather than a budgeting problem: read until 𝑄 triangles appear in the prefix, then return 𝑇b = 𝑄 (𝑚/𝑆) 3 . Under e(𝑚/𝑇 1/3 ) space, 𝜂 ≤ 𝑇 2/3 , this gives a (1 ± 𝜀) approximation using 𝑂 without knowing 𝑇 or a memory budget in advance. Stopping is an algorithmic resource. While reservoir samplers remain strong when accuracy is measured after a full pass, they are inefficient when stream access is a scarce resource. The threshold algorithm self-selects the prefix, returns a whole-graph estimate after seeing only 0.46%–6.6% of the stream, and on a 1.8 × 109 -edge graph reads 0.46% of the edges with 3.8% error. A small random prefix can be enough, especially when you know when to stop.
1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
0.083 0.087 0.075 0.040 0.068 0.037 0.055 0.043
0.095 0.094 0.065 0.039 0.056 0.075 0.024 0.038
Table 6: Stream read before a whole-graph estimate is within 𝜀, with unlimited memory. Native reservoir samplers must read almost all edges because an 𝑓 -prefix contains about 𝑓 3𝑇 triangles; cubic extrapolation helps only after being handed the stopping fraction.
Stream
Threshold Reservoir (native) Reservoir +(𝑚/𝑆 ) 3 reads (err) ≤ 10% ≤ 5% ≤ 10% ≤ 5%
sx-superuser 5% (0.065) wiki-talk 5% (0.039) cit-HepPh 1% (0.056) reddit 7% (0.094) copresence 6% (0.095) 8
97% 97% 97% 97% 97%
98% 98% 98% 98% 98%
4% 2% 1% 5% 2%
6% 4% 1% 11% 7%
REFERENCES
1343–1350. https://doi.org/10.1145/2487788.2488173 [16] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (2014). [17] Yongsub Lim and U Kang. 2015. MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 685–694. [18] Quanquan C. Liu, Aruzhan Amanbayeva, and Julian Shun. 2025. Scalable Streaming Subgraph Counting via Learned Prefix Bucket Profiles. In Proceedings of the VLDB Endowment (companion paper). [19] Andrew McGregor and Sofya Vorotnikova. 2020. Triangle and four cycle counting in the data stream model. In ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 445–456. [20] Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. 2016. Better Algorithms for Counting Triangles in Data Streams. In Proceedings of the 35th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 401–411. https://doi.org/10.1145/2902251.2902283 [21] Rasmus Pagh and Charalampos E. Tsourakakis. 2012. Colorful Triangle Counting and a MapReduce Implementation. Inform. Process. Lett. 112, 7 (2012), 277–281. [22] Aduri Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. 2013. Counting and Sampling Triangles from a Graph Stream. Proceedings of the VLDB Endowment (PVLDB) 6, 14 (2013), 1870–1881. https://www.vldb.org/pvldb/vol6/ p1870-aduri.pdf [23] Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https: //networkrepository.com [24] Warren Schudy and Maxim Sviridenko. 2012. Concentration and Moment Inequalities for Polynomials of Independent Random Variables. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 437–446. https://doi.org/10.1137/1.9781611973099.37 [25] C. Seshadhri, Ali Pinar, and Tamara G. Kolda. 2013. Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs. arXiv preprint (2013). https://arxiv.org/pdf/1309.3321 [26] Kijung Shin. 2017. WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. In Proceedings of the IEEE International Conference on Data Mining (ICDM). 1087–1092. https://arxiv.org/abs/1709.03147 [27] Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos. 2018. Think Before You Discard: Accurate Triangle Counting in Graph Streams with Deletions. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD). 141–157. Extended version in ACM TKDD 14(2), 2020. [28] Julian Shun and Kanat Tangwongsan. 2015. Multicore Triangle Computations Without Tuning. In Proceedings of the 31st IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society, Seoul, South Korea, 149–160. https://doi.org/10.1109/ICDE.2015.7113280 [29] Jakub Tětek. 2022. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In International Colloquium on Automata, Languages, and Programming (ICALP). https://d-nb.info/1366700031/34 Open-access PDF hosted by DNB. [30] Charalampos E. Tsourakakis, U Kang, Gary L. Miller, and Christos Faloutsos. 2009. DOULION: Counting Triangles in Massive Graphs with a Coin. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 837–846. https://doi.org/10.1145/1557019.1557111 [31] Charalampos E. Tsourakakis, Mihail N. Kolountzakis, and Gary L. Miller. 2011. Triangle Sparsifiers. Journal of Graph Algorithms and Applications 15, 6 (2011), 703–726. [32] Siyue Wu, Dingming Wu, Sinhong Cheuk, Tsz Nam Chan, and Kezhong Lu. 2025. GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs. Proceedings of the VLDB Endowment (PVLDB) 18, 7 (2025), 2031–2043.
[1] Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. 2019. A Simple SublinearTime Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Innovations in Theoretical Computer Science (ITCS). https://theory.epfl.ch/kapralov/ papers/subgraphCountingITCS.pdf [2] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 623–632. https://twiki.di.uniroma1.it/pub/Ing_algo/WebHome/triangles.pdf Preprint PDF (SODA’02). [3] Suman K. Bera and C. Seshadhri. 2020. How to Count Triangles, without Seeing the Whole Graph. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). https: //doi.org/10.1145/3394486.3403073 [4] Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra. 2025. Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries. arXiv preprint (2025). https://arxiv.org/pdf/2502.15379 [5] Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib: A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, Virtual Event, USA, 507–509. https://doi.org/10.1145/ 3350755.3400254 [6] Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. 2013. How Hard is Counting Triangles in the Streaming Model. In International Colloquium on Automata, Languages, and Programming (ICALP). https://web.cs.ucla.edu/~rafail/ PUBLIC/148.pdf arXiv preprint (ICALP’13 version). [7] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto MarchettiSpaccamela, and Christian Sohler. 2006. Counting Triangles in Data Streams. In Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 253–262. https://www.cs.umd.edu/ ~samir/498/triang.pdf PDF (conference version). [8] Graham Cormode and Hossein Jowhari. 2014. A Second Look at Counting Triangles in Graph Streams. Theoretical Computer Science 552 (2014), 44–51. https://dimacs.rutgers.edu/~graham/pubs/papers/trianglestcs.pdf Preprint PDF (TCS 2014). [9] Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. 2016. TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). https://arxiv.org/pdf/ 1602.07424 [10] Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In SPAA. [11] Talya Eden, Amit Levi, and Dana Ron. 2015. Approximately Counting Triangles in Sublinear Time (Full Version). Technical Report 046. Electronic Colloquium on Computational Complexity (ECCC). https://eccc.weizmann.ac.il/report/2015/ 046/download/ [12] Rajesh Jayaram and John Kallaugher. 2021. An Optimal Algorithm for Triangle Counting in the Stream. In APPROX/RANDOM (LIPIcs), Vol. 207. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 11:1–11:11. [13] Madhav Jha, C. Seshadhri, and Ali Pinar. 2013. A Space Efficient Streaming Algorithm for Triangle Counting using the Birthday Paradox. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 589–597. https://chbrown.github.io/kdd-2013-usb/kdd/p589.pdf Extended abstract PDF. [14] Minsoo Jung, Sunmin Lee, Yongsub Lim, and U Kang. 2016. FURL: Fixed-memory and Uncertainty Reducing Local Triangle Counting for Graph Streams. arXiv preprint arXiv:1611.06615 (2016). https://arxiv.org/abs/1611.06615 [15] Jérôme Kunegis. 2013. KONECT: the Koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web (WWW Companion).
9