CS Paper Radar

Counting Triangles in Graph Streams with Repeatable and Forgettable Edges

Sourav Chakraborty, Debarshi Chanda, Arijit Ghosh, A. Pavan, Chhaya Trehan, N. V. Vinodchandran

cs.DS ·submitted 2026-09-17 09:17 UTC · v1
hot direction

Abstract

Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often contain many repeated occurrences of the same edge. In general, the algorithms developed for the single-edge arrival case can fail when edges can arrive multiple times. Motivated by this, we study the {\em repeated-edge arrival graph streaming model} where an edge is allowed to arrive multiple times. In this work, we study the triangle counting problem in the repeated-edge arrival model: approximate the number of triangles in the underlying {\em simple graph} despite arbitrary edge repetitions. We design the first algorithms for triangle counting with optimal space complexity. In particular, we present a single-pass algorithm that computes an $(\varepsilon,δ)$-approximation of the number of triangles with optimal space complexity. We introduce {\em right-to-be-forgotten graph streaming} (RFGS) model, where a forget operation can cause all previous occurrences of an edge to disappear. We show that our single-pass algorithm can be extended to the RFGS model with optimal space complexity. Finally, we present optimal constant-pass algorithms that compute an $(\varepsilon,δ)$-approximation of the number of triangles and cliques for the repeated-edge arrival graph streams.

Closest papers

Nearest neighbours by meaning across the whole index.

Parameter-Free Triangle Counting

cs.DS ·2026-09-21 ·Asaf Etgar, Anna Gilbert, Quanquan Liu, Andrew McGregor
theory similarity 0.73
Abstract

Given an undirected, unweighted graph $G = (V,E)$ with $n$ vertices and $m$ edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph counting are classical problems in graph algorithms, central to applications such as community detection, computing the clustering coefficient, motif discovery in protein networks, and social network analysis. In many of these applications, the graph datasets are so voluminous that we model them as streams of updates to an underlying graph. There are a number of foundational results for streaming triangle counting, both theoretical and practical. There is, however, one major drawback to all previous sublinear-space algorithms: to achieve both a constant factor approximation and the sublinear space guarantees, one needs to know a priori a constant factor approximation of the triangle count $T$, an inherently circular requirement. We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream. We describe a family of $O(p)$ pass parameter-free triangle counting algorithms that guarantee a mixed multiplicative and additive approximation of $T$ and use $\widetilde{O}(\frac{m+T}{\sqrt{T}})$ expected space. Moreover, this family leads to an $O(\log\log(n))$ pass algorithm that gives a $(1+\eps)$ multiplicative approximation of $T$ with the same space complexity. These algorithms rely on the notion of a \emph{verified} parametrized algorithm: an algorithm parametrized by $τ$ that either provides an approximation of $T$ when $τ\le T$, or declares that $T < τ$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $Θ(m)$ space, even on streams where the triangle count is moderately large.

0.18

Scalable Triangle Counting: The Threshold Algorithm

cs.DS cs.DB ·2026-09-14 ·Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor
hot direction similarity 0.71
Abstract

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/S)^3$ where $S$ is the stopping length---and prove that, when the maximum number of triangles incident to any edge satisfies $η\le T^{2/3}$, this is a $(1\pm\varepsilon)$-approximation of $T$ with probability $1-δ$ using $O(\varepsilon^{-2}\log(1/δ)\, m/T^{1/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\%$ error at a $10\%$ 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\times10^9$-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.

0.34

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

cs.DS ·2026-09-20 ·Cristian Boldrin, C. Seshadhri
published similarity 0.66
Abstract · VLDB 2027

Triangle counting is one of the most fundamental problems in network analysis. Given the massive sizes of real-world graphs, there is a long history of small-space streaming algorithms providing accurate estimates for this problem. However, most of the results focus on estimating the total triangle count or the number of triangles incident to individual nodes. In practice, one often wants fine-grained information to understand how triangles are distributed, as captured by clustering coefficients. In particular, a standard network analysis task requires computing the binned degree-wise clustering coefficient distribution, which provides a rich and informative summary of the structure of the graph. In this work we present BOLIDE, the first efficient and practical algorithm for estimating binned degree-wise clustering coefficients in streaming. Our algorithm makes a single pass over the edge stream, and is allowed to store only a small fraction of the total number of edges. BOLIDE carefully combines different sampling strategies to efficiently gather degree and triangle information across sets of nodes. As a result, our algorithm provably approximates the binned degree-wise clustering coefficients, and provides guarantees on the amount of memory used. Our experimental evaluation shows that BOLIDE accurately estimates clustering coefficient distributions while efficiently processing large datasets with billions of edges and triangles.

0.31

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

cs.DS ·2026-10-25 ·Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
similarity 0.65
Abstract

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.

0.45

Enumeration-based Triangle Counting on GPUs

cs.DC ·2026-10-21 ·Sayan Ghosh
similarity 0.65
Abstract · 11 pages

Subgraph enumeration in partitioned graphs across distributed-memory systems is beset with challenges in balancing data movement with the local computation. Especially, counting the number of triangles induced by the closed wedges (i.e., length-3 cycles) is a measure of connectedness in a graph, but often limited by the significant search space caused by open wedges or length-2 paths (usually greater than the number of edges in a graph), which must be inspected to assess whether a particular wedge is closed. To mitigate triangle counting on massive graphs, distributed-memory partitioned-graph approaches are viable (i.e., assessing closed wedges independently within a partition), but load imbalance due to arbitrary communication can overshadow any gains from enhanced concurrency, owing to the inherent lack of structure in regular graphs. In this paper, we discuss a distributed-memory exact graph triangle counting implementation, and assess its performance over billion-edge real-world graphs on contemporary scale-out and scale-up based NVIDIA GPU platforms (considering NVIDIA ``Ampere'' and ``Hopper'' architectures), depicting a scalability spectrum of multiple orders of magnitude. Comparisons with existing state-of-the-art approaches demonstrates up to 10$\times$ improvements relative to distributed-memory CPU baseline, 2-100$\times$ over single-GPU vendor-optimized NVIDIA RAPIDS cuGraph and 10-60\% over multi-GPU $G^2$Miner, in terms of end-to-end execution times.

0.31

Sparsification Framework for Directed Densest Subgraph

cs.DS ·2026-10-01 ·Slobodan Mitrović, Theodore Pan
similarity 0.63
Abstract

We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrović and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).

0.08

Optimal Passes and Perfect Sampling for Similarity Graph Statistics

cs.DS ·2026-09-17 ·Qin Zhang
hot direction similarity 0.62
Abstract · 32 pages

We study statistical estimation on implicit weighted similarity graphs presented as node-arrival streams. Previous work~\cite{LZ26b} obtained constant-pass, sublinear-space algorithms for several basic statistics of such graphs, including the diversity index $\mathsf{DI}=\sum_i d_i^{-1}$ and the degree moments $M_p=\sum_i d_i^p$ for $p>0$, together with their associated sampling problems $L_{\mathsf{DI}}$ and $L_{M_p}$. We settle three questions left unresolved by the previous work. First, we show that any two-pass streaming algorithm that $1.1$-approximates $\mathsf{DI}$ requires $Ω(n)$ bits of space; combined with the three-pass $\tilde{O}(\sqrt n)$-space algorithm of~\cite{LZ26b}, this establishes a sharp transition between two and three passes for $\mathsf{DI}$. Second and third, for every fixed $c>0$ we give a three-pass $n^{-c}$-perfect $L_{\mathsf{DI}}$-sampler using $O_c(\sqrt n\log n)$ words and a two-pass $n^{-c}$-perfect $L_{M_p}$-sampler using $O_{p,c}(n^{1-1/(p+1)}\log n)$ words. Matching lower bounds up to polylogarithmic factors show that both the number of passes and the polynomial dependence on $n$ are optimal.

0.43

Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes

cs.DS ·2026-11-03 ·Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
theory similarity 0.60
Abstract

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $Ω(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).

0.20