An Optimal Algorithm for Triangle Counting in the Stream

Rajesh Jayaram, John KallaugherAPPROX-RANDOM 2021 · OpenReview

TL;DR

This paper presents a new, optimal algorithm for counting triangles in massive graphs that arrive as a stream of edges. It achieves this by cleverly combining edge and vertex sampling, achieving a space complexity that depends on graph properties like the maximum number of triangles sharing an edge or vertex, thus resolving a long-standing problem in graph streaming.

What Problem Does This Paper Address?

Imagine a massive social network or a web graph. We're interested in understanding its structure, and a fundamental way to do this is by counting "triangles" – sets of three nodes where each node is connected to the other two. This is crucial for applications like community detection and identifying influential groups. However, processing these massive graphs is challenging, especially when the data arrives as a "stream" – a sequence of edges arriving one by one, without knowing the total size or structure beforehand. Traditional algorithms require too much memory to store the entire graph.

The challenge is to count these triangles using very little memory (sublinear space) while the edges stream in. Previous work established lower bounds on the space required, showing that simply knowing the total number of edges ($m$) and triangles ($T$) isn't enough for truly efficient streaming algorithms. Researchers introduced new graph parameters: $\Delta_E$ (the maximum number of triangles sharing a single edge) and $\Delta_V$ (the maximum number of triangles sharing a single vertex). The problem then became finding an algorithm whose space complexity was optimal with respect to $m$, $T$, $\Delta_E$, and $\Delta_V$.

Methods

The core of the paper's contribution is a novel streaming algorithm that achieves optimal space complexity. It builds upon existing ideas but introduces a key innovation: a hybrid sampling strategy.

Here's a breakdown:

  • Edge Sampling (inspired by prior work): The algorithm samples edges with a certain probability. For a triangle to be counted, all three of its edges must be sampled. This approach's effectiveness is limited by the density of triangles around edges (captured by $\Delta_E$).
  • Vertex Sampling (also inspired by prior work): Alternatively, one could sample vertices. If a triangle has at least one sampled vertex, it might be counted. This is limited by the density of triangles around vertices (captured by $\Delta_V$).
  • Hybrid Approach (the paper's novelty): The paper's algorithm cleverly merges these two strategies. It samples vertices with probability $p$ and edges with probability $q$. An edge is stored if it's sampled and at least one of its endpoints was a sampled vertex. Triangles are then counted when an edge completes a "wedge" (two edges incident to a common vertex) where the common vertex was sampled.
  • Parameterization: The crucial insight is how to set $p$ and $q$ optimally. By choosing $p$ and $q$ based on the graph parameters $\Delta_E$ and $\Delta_V$ (specifically, $p \approx \Delta_V/T$ and $q \approx \max(\Delta_E/\Delta_V, 1/\sqrt{\Delta_V})$), the algorithm balances the trade-offs between missing triangles due to edge sampling and missing triangles due to vertex sampling.
  • Unbiased Estimator: The algorithm outputs an unbiased estimator for the number of triangles. To achieve a high probability of accuracy, this estimation process is repeated multiple times, and the results are averaged (or a median is taken).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of Hybrid Sampling: The most significant insight is that combining edge and vertex sampling, with carefully chosen probabilities, can overcome the limitations of using either method alone. This hybrid approach allows for a more robust and efficient estimation of triangles.
  • Parameterizing for Optimality: The paper demonstrates that optimal space complexity in graph streaming often requires considering parameters beyond just the total number of edges and triangles. $\Delta_E$ and $\Delta_V$ are critical for achieving theoretical optimality in triangle counting.
  • Resolving a Classic Problem: By achieving a space complexity that matches known lower bounds up to logarithmic factors, this work definitively settles the complexity of triangle counting in the insertion-only graph streaming model.

Key Results

The paper presents an algorithm for insertion-only graph streams that approximates the number of triangles ($T$) with an error of $\epsilon T$ and probability $1-\delta$, using space:

$$ O\left(\frac{m}{\epsilon^2 T} \left(\Delta_E + \sqrt{\Delta_V}\right) \log^2 n \log \frac{1}{\delta}\right) $$

This space complexity is optimal up to logarithmic factors, matching the best known lower bounds for this problem. The algorithm is also shown to be optimal for linear sketching algorithms and potentially for turnstile streaming algorithms under certain conditions.

Limitations and Future Work

  • Insertion-Only Model: The presented algorithm is for the "insertion-only" model, meaning edges only arrive and are not deleted. While related to turnstile streaming (which allows deletions), the paper doesn't directly provide an optimal algorithm for the turnstile model. The relationship between these models for triangle counting remains an open question.
  • Parameter Knowledge: Like most streaming algorithms, this one requires knowledge of graph parameters ($\Delta_E$, $\Delta_V$, and a lower bound on $T$) that are not known beforehand. The paper notes that upper bounds on $\Delta_E$ and $\Delta_V$, and a lower bound on $T$, are sufficient, and their exact values aren't needed.
  • Dense Graphs: The paper mentions that for very dense graphs (where $m$ is close to $n^2$), the algorithm is already trivially optimal as it uses polylogarithmic space. However, the complexity landscape for more general dense graphs remains an area for further exploration.
  • Turnstile Streaming Equivalence: The paper discusses the equivalence between turnstile streaming and linear sketching, but notes that this equivalence has stringent conditions. It remains an open question whether the presented algorithm can be converted into a turnstile algorithm under less restrictive conditions, or if the complexity for turnstile streams lies somewhere between insertion-only and linear sketching.

Summary updated

Abstract

We present a new algorithm for approximating the number of triangles in a graph G whose edges arrive as an arbitrary order stream. If m is the number of edges in G, T the number of triangles, Δ_E the maximum number of triangles which share a single edge, and Δ_V the maximum number of triangles which share a single vertex, then our algorithm requires space: Õ(m/T⋅(Δ_E + √{Δ_V})) Taken with the Ω((m Δ_E)/T) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Ω((m √{Δ_V})/T) lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming.
BibTeX
@inproceedings{jayaram2021optimal,
  author = {Rajesh Jayaram and John Kallaugher},
  title = {{An Optimal Algorithm for Triangle Counting in the Stream}},
  booktitle = {APPROX-RANDOM},
  year = {2021},
  url = {https://openreview.net/forum?id=iQujywqpNu},
}
Figure