Parameter free algorithms count triangles in large graph streams efficiently
Parameter-Free Triangle Counting
Data Structures and Algorithms
Summary
Counting triangles in large networks, like social or protein networks, is important but challenging when data is massive and arrives over time. Previous methods needed a guess of how many triangles exist beforehand, which is tricky. The authors propose algorithms that do not require any prior guess and still count triangles approximately using limited memory and multiple reads over the data. They also show a limit: any method providing precise approximation without parameters must use a lot of memory. This work helps analyze huge dynamic graphs more practically.
What this means in practice
- •For network data engineers: Implement efficient triangle counting over streaming graph data without prior knowledge of triangle counts, saving memory and passes.
- •For social media platform operators: Analyze evolving user interaction graphs for community detection and clustering metrics without manual parameter tuning.
Authors
Asaf Etgar, Anna Gilbert, Quanquan Liu, Andrew McGregor
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.