Counting triangles in repeated edge graph streams with low space
Counting Triangles in Graph Streams with Repeatable and Forgettable Edges
Data Structures and Algorithms
Summary
Graphs often stream data where edges can appear multiple times, like repeated phone calls or transactions. Most methods for counting triangles assume edges only show up once, which doesn’t work well for these cases. The authors design new algorithms that can accurately count triangles even when edges repeat, using minimal memory. They also introduce a way to 'forget' old edges and still keep accurate counts. These methods work efficiently in a single pass or a few passes over the data.
What this means in practice
- •For network analysts: Analyze communication networks with multiple repeated connections efficiently using low-memory algorithms that accurately count interaction triangles.
- •For financial fraud detection teams: Detect suspicious transaction patterns involving repeated interactions by accurately counting triangles in financial transaction streams despite edge repetitions.
Authors
Sourav Chakraborty, Debarshi Chanda, Arijit Ghosh, A. Pavan, Chhaya Trehan, N. V. Vinodchandran
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.