Source-linked AI summary
Colorful Triangle Counting and a MapReduce Implementation
Rasmus Pagh, Charalampos E. Tsourakakis
TL;DR
The paper addresses efficient approximate triangle counting when exact counting is unnecessary. It introduces colorful vertex-based sampling, analyzes concentration using graph coloring and Chernoff-style tools, and presents a parallel implementation. The authors report improved sampling behavior and an easily implemented MapReduce realization, while noting open extensions and assumptions in the concentration analysis.
Problem
Triangle counting is a fundamental problem, and applications such as large social networks may require fast, high-quality estimates rather than exact counts.
Method
The algorithm randomly colors vertices, retains monochromatic edges, counts triangles in the sampled graph, and multiplies the count by p^-2.
Results
The authors report that correlated sampling reduces the polynomial degree by one relative to previous work and supports concentration analysis and parallel implementation.
Takeaways & Limitations
The method yields a randomized approximate triangle-counting approach with a MapReduce implementation and can extend to subsets of triangles satisfying predicates.
Takeaways & Limitations
The stated concentration condition is sufficient rather than necessarily optimal, and the authors identify improving the dependence on Δ as an open possibility.
Abstract
from arXiv · showhide
In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles. Specifically, if $p \geq \max{(\frac{Δ\log{n}}{t}, \frac{\log{n}}{\sqrt{t}})}$, where $n$, $t$, $Δ$ denote the number of vertices in $G$, the number of triangles in $G$, the maximum number of triangles an edge of $G$ is contained, then for any constant $ε>0$ our unbiased estimate $T$ is concentrated around its expectation, i.e., $ \Prob{|T - \Mean{T}| \geq ε\Mean{T}} = o(1)$. Finally, we present a \textsc{MapReduce} implementation of our algorithm.
1. Introduction
The note presents a randomized colorful sampling method for approximating triangle counts, designed to improve sampling efficiency and support parallel implementation. Its central design correlates edge sampling so sampled triangles are preserved more effectively.
- Motivation: Triangle counting is fundamental, and fast high-quality estimates can be preferable to exact counts in large social networks.Prior approximate methods have largely focused on sampling in streaming settings.
- Sampling design: Correlated edge sampling ensures that if two edges of a triangle are sampled, the third is also sampled.This reduces the degree of the multivariate polynomial representing sampled triangles.
- Contribution: The approach is presented as an improvement over existing sampling methods and is intended to be easily implemented in parallel.The note also discusses a MapReduce implementation.
- Algorithm: The algorithm uses random vertex colors and samples exactly the monochromatic edges, then estimates the triangle count by multiplying the sampled count by p^-2.It sets N = 1/p and counts triangles in the sampled edge set.
- Comparison: Earlier independent edge sampling can leave no sampled triangles in graphs containing many edge-disjoint triangles when p^3t = o(1).The colorful sampling approach is contrasted with this failure regime.
2. Theoretical Preliminaries
The theoretical preliminaries introduce concentration tools used later in the analysis. They include a Chernoff inequality for independent indicators and the Hajnal-Szemerédi coloring theorem.
- Chernoff inequality: The analysis uses a Chernoff inequality for independently distributed {0, 1} variables with expectation p.The bound applies for any ϵ > 0.
- Hajnal-Szemerédi theorem: The Hajnal-Szemerédi theorem states that every graph with maximum vertex degree at most k is k + 1 colorable with large color classes.Each color class has size at least n/k according to the supplied statement.
3. Analysis
The analysis establishes concentration guarantees for colorful triangle sampling, explains the partition-based proof, and derives implementation and empirical consequences. It also identifies dependence constraints and presents a MapReduce realization.
- Second Moment Method: The second-moment analysis seeks p small enough to retain strong concentration of the triangle estimate.It targets Var[T] = o(E[T]^2) as a sufficient condition.
- Second Moment Method: Each triangle is monochromatic with probability p^2, so the expected sampled triangle count is p^2t.Dependencies occur only between triangles sharing an edge, with covariance below p^3.
- Concentration via the Hajnal-Szemerédi Theorem: Partitioning triangles into vertex-disjoint classes makes their indicator variables independent, enabling Chernoff bounds and a union bound.The auxiliary graph has one vertex per triangle, and the resulting classes have size Ω(t/tmax).
- Concentration via the Hajnal-Szemerédi Theorem: Theorem 3 guarantees Pr[|T − E[T]| > ϵE[T]] ≤ 1/n^d when p^2 ≥ 4(d+3)tmax log n/(ϵ^2t).Here tmax is the maximum number of triangles containing a vertex.
- Complexity: The sampled graph can be counted in expected time O(n + m + p^2 Σ_i deg(i)), implying a 1/p^2 speedup for the counting task.The runtime depends on the triangle-counting subroutine applied to monochromatic edges.
- Implementation and Discussion: The MapReduce implementation colors vertices, emits monochromatic edges by color, counts triangles within each color class, and scales each triangle by 1/p^2.The method’s polynomial degree is two rather than three because correlated edge sampling reduces dependencies.
4. A MapReduce Implementation
The method is designed for MapReduce processing of large-scale networks: mappers retain monochromatic edges, and reducers process the resulting color-keyed groups with bounded expected resource use.
- MapReduce is presented as a standard framework for analyzing large-scale networks, with prior triangle-counting implementations based on node iteration or overlapping graph subsets.
- Mappers emit each monochromatic edge using its color as the key, allowing reducers to process sampled edge groups.
- O(p^2m) expected size per reduce instance and O(pm) expected total map-phase space characterize the implementation’s resource use.
5. Conclusions
The paper concludes that colorful sampling yields a parallel randomized triangle-counting method with improved polynomial degree and concentration guarantees, while identifying extensions and implementation details for future work.
- The algorithm is easily implemented in parallel, including within the MapReduce framework.
- Colorful sampling decreases the degree of the triangle-counting multivariate polynomial by one compared with previous sampling approaches.
- The concentration proof uses the Hajnal-Szemerédi theorem, although the authors state that the resulting concentration bound is unlikely to be best possible.
- The same result extends to any subset of triangles satisfying a predicate, such as triangles containing a specified vertex.
- Future work includes sampling methods for weighted graphs, other subgraphs, and systems-oriented aspects of the approach.