Source-linked AI summary
TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal
TL;DR
Estimating triangle counts in massive, fully dynamic graph streams is difficult under one-pass and fixed-memory constraints. TRIÈST uses reservoir-based sampling to maintain global and local estimates, outperforming state-of-the-art approaches while achieving high accuracy and update times of hundreds of microseconds on billion-edge datasets.
Problem
Web-scale, fully dynamic graph streams require high-quality one-pass approximations of global and local triangle counts under fixed memory.
Method
TRIÈST uses reservoir sampling and random pairing to maintain unbiased triangle-count estimates continuously in adversarial fully dynamic streams.
Results
TRIÈST outperforms state-of-the-art approaches, achieves high accuracy on datasets with more than one billion edges, and has update times of hundreds of microseconds.
Takeaways & Limitations
TRIÈST provides a fixed-space approach for continuously estimating local and global triangle counts in large fully dynamic graph streams.
Takeaways & Limitations
For algorithms beyond trièst-base, the paper provides variance upper bounds that are not currently tight.
Abstract
from arXiv · showhide
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully-dynamic graph represented as an adversarial stream of edge insertions and deletions. Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches which use hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they will use. We show a full analysis of the variance of the estimations and novel concentration bounds for these quantities. Our experimental results on very large graphs show that TRIÈST outperforms state-of-the-art approaches in accuracy and exhibits a small update time.
1. INTRODUCTION
The paper addresses triangle estimation in huge, fully dynamic, adversarial graph streams, where exact computation is impractical and quantities are volatile. TRIÈST uses fixed-memory, one-pass sampling algorithms to estimate global and local triangle counts with theoretical guarantees and strong empirical accuracy.
- Motivation: Fixed-probability edge sampling can require prior stream knowledge and produce sample sizes that grow with the stream.These drawbacks motivate TRIÈST’s departure from independent fixed-probability sampling.
- Contributions: TRIÈST estimates global and per-vertex triangle counts at every time instant in fully dynamic streams using a fixed amount of memory.The user specifies available memory rather than a fixed sampling probability.
- Contributions: TRIÈST combines reservoir sampling and random pairing to use available memory, with analyses of estimator unbiasedness, variance, and concentration.The paper presents these techniques for subgraph counting in fully dynamic, arbitrarily long, adversarially ordered streams.
- Contributions: On very large graphs, TRIÈST reduces average estimation error by up to 90% versus state-of-the-art methods for both global and local estimation using the same memory.The evaluation compares against existing methods on graphs including datasets with billions of edges.
- Contributions: The journal version strengthens variance analysis, extends TRIÈST to multigraph triangle counting, and expands theoretical and experimental details.It includes proofs and additional experiments and comparisons with existing state-of-the-art methods.
2. PRELIMINARIES
The paper defines global and local triangle counting in fully dynamic undirected graphs whose edges undergo arbitrary adversarial insertions and deletions, and notes an extension to multigraph streams.
- Stream model: The stream evolves by effective edge insertions or deletions, adding previously unseen endpoints and removing vertices when their degree reaches zero.The adversary cannot access the algorithm’s random bits.
- Triangle-counting problems: Global and local triangle counting estimate the total number of triangles and, respectively, the number of triangles incident to each vertex at every time.A triangle consists of three edges joining three distinct vertices.
- Multigraphs: The same global and local counting problems extend to multigraph edge streams, where edges are represented as a bag and local triangles remain defined by their incident corners.The multigraph formalization is analogous to the graph-stream model.
3. RELATED WORK
Related work spans exact and approximate triangle counting, but prior approaches often target more restricted settings or impose looser computational constraints. TRIÈST combines single-pass processing, fully dynamic streams, fixed memory, one interpretable parameter, and estimates at every time instant, outperforming cited insertion-only methods experimentally.
- Prior triangle-counting research includes exact algorithms, graph sparsifiers, complex-valued sketches, and MapReduce methods.
- Several approaches handle restricted settings, including static graphs with multiple passes and algorithms operating under less stringent computational constraints.
- TRIÈST uniquely combines one-pass processing, fully dynamic streams, fixed memory, one interpretable parameter, and estimates at every time instant among the discussed works.
- TRIÈST experimentally outperforms the algorithms of Jha et al. [2015] and Pavan et al. [2013] on insertion-only streams.
- Lim and Kang’s fixed-probability independent edge sampling underuses memory for most of the stream, increasing estimate variance, whereas TRIÈST handles fully dynamic streams.
- Reservoir-sampling foundations include Vitter’s analysis and Random Pairing’s extension to fully dynamic insertion-deletion streams, later generalized to key-value pairs with potentially negative values.
4. ALGORITHMS
TRIÈST is a suite of reservoir-sampling algorithms for approximate global and local triangle counting under insertion-only and fully dynamic edge streams. Its variants provide exactness or unbiasedness guarantees, variance and concentration analyses, and fixed-memory operation, with accuracy balanced against computational simplicity.
- Algorithm suite: TRIÈST provides three algorithms for approximate global and local triangle counting: two for insertion-only streams and trièst-fd for fully dynamic streams with deletions.The algorithms maintain an edge sample containing up to M edges.
- Insertion-only algorithms: trièst-base and trièst-impr are exact when t ≤ M and unbiased afterward, while their analyses establish variance and concentration guarantees for global and local counts.trièst-impr is designed to produce lower-variance estimates than trièst-base.
- Variance analysis: Reservoir sampling creates dependencies among sampled edges, so TRIÈST’s variance analysis accounts for triangle pairs sharing sampled edges rather than assuming independent edge sampling.For α = 0.99, M ≥ 400, and mascot-c using p = M/T, trièst-base has strictly smaller variance for 99% of the stream.
- Fully dynamic algorithm: trièst-fd adapts reservoir sampling to insertions and deletions by removing deleted sampled edges, tracking deletion and insertion counts, and preserving the stated unbiasedness guarantee before t∗.The fully dynamic update procedure changes the sample as edges are deleted or inserted.
- Limitations and trade-offs: The paper gives exact variance analysis only for trièst-base; the other algorithms receive upper bounds that are not tight, while more accurate alternatives would require greater computational complexity.The discussion frames this as a speed–accuracy trade-off for analyzing very large graphs.
5. EXPERIMENTAL EVALUATION
TRIÈST achieves accurate triangle-count estimates with low variance while using bounded memory, outperforming competing methods in error and update efficiency. Its fully dynamic variant remains accurate and scalable under deletions and sliding-window streams, including graphs with billions of edges.
- Estimation of the global number of triangles: On smaller graphs, TRIÈST-impr estimates are practically indistinguishable from exact triangle counts and exhibit very small variance on very large graphs.Exact global and local triangle counts were computed for smaller graphs, while experiments covered real-world graphs with up to a billion edges.
- Comparison with the state of the art: Competing methods are up to ≈3 orders of magnitude slower per update than mascot variants and TRIÈST, while TRIÈST handles updates in a few hundred microseconds.Larger samples generally increase update time, but long streams and reservoir sampling enable low average times on large Yahoo! and Twitter graphs.
- Fully-dynamic and sliding-window evaluation: TRIÈST-fd maintains good accuracy and scalability in sliding-window streams and under massive deletions, with LastFm Avg. MAPE of 0.04 at M = 200000 and 0.006 at M = 1,000,000.Precision improves with memory, and relatively small samples provide low global MAPE, high local Pearson correlation, and low ε error.
6. CONCLUSIONS
TRIÈST provides fixed-space, reservoir-based streaming algorithms for unbiased, low-variance estimation of local and global triangle counts in fully dynamic graphs, and outperforms state-of-the-art methods on billion-edge real-world datasets.
- 6. CONCLUSIONS: TRIÈST continuously estimates local and global triangle counts in fully dynamic streams with arbitrary edge and vertex insertions and deletions.The estimates are unbiased and low-variance.
- 6. CONCLUSIONS: TRIÈST uses reservoir sampling and its variants while maintaining a fixed, user-specified amount of space.This design supports continuous processing under a predetermined memory budget.
- 6. CONCLUSIONS: Experiments show that TRIÈST outperforms state-of-the-art approaches and achieves high accuracy on real-world datasets containing more than one billion edges.The evaluation covers large-scale real-world graphs.
APPENDIX · A. ADDITIONAL THEORETICAL RESULTS
This appendix presents theoretical results, including statements and proofs, that were not included in the paper’s main body.
- A. ADDITIONAL THEORETICAL RESULTS: The appendix collects theoretical statements and proofs omitted from the main body.
A.1. Theoretical results for trièst-base
The theoretical analysis establishes that reservoir sampling maintains a uniformly random fixed-size subset of the stream’s edges, providing the sampling property used in subsequent proofs.
- Theoretical results for trièst-base: For t > M, the sample S contains M edges chosen uniformly at random from all M-edge subsets of E(t).This is the stated reservoir-sampling property.
- Theoretical results for trièst-base: For k > min{M, t}, containing B in S is impossible, giving probability 0.The proof handles this boundary case before assuming k ≤ min{M, t}.
- Theoretical results for trièst-base: When t ≤ M, every edge seen so far is included in S, so the relevant containment probability equals 1.The proof explicitly uses E(t) ⊆ S in this case.
A.1.1. Expectation
The expectation analysis proves that TRIÈST-BASE’s global and local triangle estimators are unbiased, and exactly correct while the stream time t does not exceed the memory size M. The proof establishes this through an induction invariant for sampled-subgraph triangle counts and a separate argument for t > M.
- Expectation: An induction invariant shows that the counter τ equals the number of triangles in the sampled graph, |∆S|, after each UpdateCounters call.The base case has one sampled edge and τ = 0; the inductive step handles an inserted edge by decomposing sampled triangles into prior and newly formed triangles, with removals treated analogously.
- Expectation: TRIÈST-BASE’s global and local triangle estimators are unbiased, with exactness guaranteed for t ≤ M.The theorem proof states the result for global counts and notes that local counts follow the same steps; for t ≤ M, the sampled graph equals the full graph.
- Expectation: For t > M, the proof analyzes each full-graph triangle using a random variable that equals its sampling weight ξ(t) when all three edges are in S and 0 otherwise.If the current graph contains no triangles, the estimator is deterministically correct; otherwise, linearity of expectation and the sampling lemma complete the unbiasedness argument.
A.1.2. Concentration
The concentration analysis uses conditional sampling arguments to compare edge subsets and establish probability bounds. It also develops technical inequalities for variance analysis, including a comparison showing TRIÈST-BASE has lower variance than MASCOT-C for most of the stream.
- Concentration: Conditioning on the sampled-set size shows that the included edges are uniformly random subsets, enabling the probability comparison in Lemma 4.7.The argument applies the law of total probability and Lemma A.1 to relate Sin conditioned on size M to Smix.
- Concentration: The analysis uses Stirling approximation and auxiliary inequalities to complete concentration proofs and bound ratios involving t(t−1)(t−2) and M(M−1)(M−2).Fact A.2 provides an inequality for x > 2 that is used in the ratio analysis of Lemma 4.10.
- Concentration: The section proves that TRIÈST-BASE’s estimation variance is lower than MASCOT-C’s for most of the stream.This comparison is introduced as the subject of Lemma 4.11.
A.1.3. Variance comparison.
The variance comparison proves that, for sufficiently large memory M relative to the stream ratio α, the functions f(M,t) and g(M,t) are bounded by their corresponding normalized expressions.
- Variance comparison: For t > M > 42 and t ≤ αT, the proof establishes f(M,t) < ¯f(M/T) and g(M,t) < ¯g(M/T).The inequalities follow from the stated conditions and bounds on M relative to α.
- Variance comparison: The bound for f holds when M ≥ 4α^3/(1−α^3) + 2, which is guaranteed by M ≥ 42 for α < 0.6 and by M > 8α/(1−α) for α ≥ 0.6.These conditions make the right-hand side of the comparison non-positive.
- Variance comparison: The bound for g follows because the right-hand side of its comparison is non-positive under the assumption M > 8α/(1−α).This yields g(M,t) < ¯g(M/T) in the stated regime.
A.2. Theoretical results for trièst-impr · A.2.1. Expectation
The expectation proof for trièst-impr reduces to trièst-base when t ≤ M and otherwise analyzes triangle contributions through stream-order-dependent random variables and counter updates. Linearity of expectation then yields the stated result.
- A.2.1. Expectation: For t ≤ M, trièst-impr behaves exactly like trièst-base, so the expectation statement follows from Lemma 4.2.
- A.2.1. Expectation: For t > M, the proof assumes |∆(t)| > 0; otherwise, the algorithm deterministically returns 0 as its estimation.
- A.2.1. Expectation: For each triangle λ, the proof orders its edges a, b, and c by their stream appearance and defines tλ as the arrival time of c.
- A.2.1. Expectation: The random variable δλ equals ξ2,tλ−1 when a and b are in S at time tλ −1, and equals 0 otherwise.
- A.2.1. Expectation: When c = (u, v) arrives, trièst-impr calls UpdateCounters and increments τ by |N S u,v|, counting triangles with (u, v) in ∆S∪{c}.
- A.2.1. Expectation: These triangles share the same random-variable value ξ2,tλ−1, allowing τ(t) to be expressed accordingly and the result to follow by linearity of expectation and (20).
A.2.2. Variance … A.3.3. Concentration.
The appendix establishes the sampling properties underlying TRIÈST-FD’s expectation and variance analyses, then derives concentration guarantees under conditions on memory, stream size, and deletions. It also shows that before the sample first exceeds memory, the estimator exactly matches the current triangle count.
- A.2.2. Variance: The variance analysis derives joint-inclusion bounds by conditioning on sampled edges and exploiting independence from earlier sampling events.The proof uses events A_i, B_i, and C, together with conditional relationships involving D_λ and D_γ.
- A.3. Theoretical results for trièst-fd: The appendix’s TRIÈST-FD theory is organized around expectation, variance, and concentration results derived from reservoir-sampling properties and deletion-aware sample-size analysis.The preliminary results include exact behavior before t∗, uniform conditional sampling, variance lemmas, and concentration conditions.
- A.3.1. Expectation.: Conditioned on its size, the maintained sample is uniformly distributed over subsets of the current edge set of that size.This uniformity supports the expectation and variance arguments for TRIÈST-FD.
- A.3.1. Expectation.: Before the first time the edge set exceeds memory, TRIÈST-FD stores the entire stream graph and returns the exact triangle count.For t < t∗, S = E(t), κ(t) = 1, and ρ(t) = |∆(t)|; the zero-triangle case is handled deterministically.
- A.3.2. Variance.: For t ≥ t∗, Lemmas A.9–A.11 characterize global and local variance terms and the hypergeometric distribution of the sample size.The analogous variance results apply to each vertex’s local quantities, while M(t) follows a hypergeometric distribution when s(t) ≥ M.
- A.3.2. Variance.: If unpaired deletions satisfy d(t) ≤ αs(t) and memory is sufficiently large, Corollary A.12 supplies concentration control for the estimator.The stated condition requires 0 ≤ α < 1, s(t) ≥ M, and a logarithmic lower bound on M involving α, α′, c′, and s(t).
- A.3.2. Variance.: Theorem 4.17 combines total-variance decomposition with the preceding bounds to obtain an overall variance guarantee for TRIÈST-FD.Its proof separately bounds the main components and composes the bounds under the memory and deletion assumptions.
- A.3.3. Concentration.: The concentration proof applies Chebyshev’s inequality and reduces the result to two sufficient conditions involving M′ = (1 − α′)M.The proof then verifies these conditions using the variance theorem and assumptions on |∆(t)|, memory, and stream size.