Source-linked AI summary
Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning
Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, Charalampos E. Tsourakakis
TL;DR
Triangle counting must remain accurate and efficient on very large graphs because triangles support network analysis and applications. The paper combines edge sampling with degree-based vertex partitioning, extends the approach to semistreaming, and reports strong practical performance while also analyzing random projections.
Problem
Triangle counting is computationally expensive on large graphs, motivating methods that are fast, space-efficient, accurate, and parallelizable.
Method
The method combines Tsourakakis et al.’s sampling with Alon, Yuster, and Zwick’s partitioning of low- and high-degree vertices.
Results
The algorithm achieves an ε approximation, adapts to semistreaming, and obtains excellent accuracy and running time on networks with several million edges.
Takeaways & Limitations
The approach is practically useful for large networks, with reported running times typically of a few seconds and satisfactory accuracy.
Takeaways & Limitations
The random-projection condition is sufficient rather than necessary, and it can fail for graphs with many 6-circuits and no triangles.
Abstract
from arXiv · showhide
The number of triangles is a computationally expensive graph statistic which is frequently used in complex network analysis (e.g., transitivity ratio), in various random graph models (e.g., exponential random graph model) and in important real world applications such as spam detection, uncovering of the hidden thematic structure of the Web and link recommendation. Counting triangles in graphs with millions and billions of edges requires algorithms which run fast, use small amount of space, provide accurate estimates of the number of triangles and preferably are parallelizable. In this paper we present an efficient triangle counting algorithm which can be adapted to the semistreaming model. The key idea of our algorithm is to combine the sampling algorithm of Tsourakakis et al. and the partitioning of the set of vertices into a high degree and a low degree subset respectively as in the Alon, Yuster and Zwick work treating each set appropriately. We obtain a running time $O \left(m + \frac{m^{3/2} Δ\log{n}}{t ε^2} \right)$ and an $ε$ approximation (multiplicative error), where $n$ is the number of vertices, $m$ the number of edges and $Δ$ the maximum number of triangles an edge is contained. Furthermore, we show how this algorithm can be adapted to the semistreaming model with space usage $O\left(m^{1/2}\log{n} + \frac{m^{3/2} Δ\log{n}}{t ε^2} \right)$ and a constant number of passes (three) over the graph stream. We apply our methods in various networks with several millions of edges and we obtain excellent results. Finally, we propose a random projection based method for triangle counting and provide a sufficient condition to obtain an estimate with low variance.
1 Introduction
Triangle counting supports network analysis and applications, but large graphs require fast, space-efficient, accurate, and parallelizable methods. The paper combines sampling and degree-based partitioning, extends the method to semistreaming, evaluates it on large networks, and proposes a random-projection approach.
- Triangles support transitivity and clustering analysis, web-structure discovery, web-activity classification, link recommendation, and exponential random graph models.
- The paper proposes an ε-approximate triangle-counting method with a stated running-time bound involving n, m, Δ, t, and ε.
- The method combines Tsourakakis et al.’s sampling scheme with Alon, Yuster, and Zwick’s vertex-partitioning idea.
- The algorithm adapts to semistreaming, and experiments on networks with several million edges report excellent accuracy and running time.
- The paper also optimizes cache behavior and proposes a random-projection method with a sufficient condition for low-variance estimates.
2 Preliminaries
The preliminaries motivate approximate counting for large graphs, review exact, approximate, streaming, sampling, and matrix-based approaches, and introduce the probabilistic and dimensionality-reduction tools used later.
- Existing work: Approximate triangle counts are preferred for the paper’s applications because exact counts are not crucial, while faster high-quality estimates are desirable.
- Existing work: Existing exact methods include listing and matrix-multiplication approaches, but matrix-based algorithms have high memory requirements and are often impractical for medium-sized networks.
- Existing work: Streaming algorithms represent graphs as edge or incidence streams and target relative ε-approximations with high probability.
- Existing work: Naive and moment-based sampling methods can require graphs to be sufficiently dense relative to their triangle counts for high-probability ε-approximation.
- Theoretical background: The analysis uses a Chernoff bound and the Johnson–Lindenstrauss lemma, whose version maps points with a Gaussian random matrix into a lower-dimensional space.
3 Proposed Method
The proposed method combines edge sparsification with degree-based triple sampling. It partitions low- and high-degree cases to reduce the sampling universe, while concentration bounds support approximation guarantees and practical efficiency.
- Overview: The algorithm first sparsifies edges randomly and then samples triples using vertex partitioning inspired by Alon, Yuster, and Zwick.
- Edge Sparsification: Keeping each edge with probability p retains each triangle with probability p^3 and can reduce the processed graph to O(mp) edges.
- Edge Sparsification: The sparsified triangle count concentrates under a condition on p^3 and Δ/t, yielding an ε-approximation with high probability.
- Edge Sparsification: Triangles can be partitioned into sets larger than Ω(t/Δ), with the number of sets bounded by O(Δ).
- Triple Sampling: The method samples triples from a universe U and uses Chernoff concentration to obtain an ε-approximation with probability at least 1−n^-d.
- Triple Sampling: Splitting vertices at degree m^1/2 gives |U| ≤ 3m^3/2, leading to a sampling-time bound with an m^3/2 log n term.
- Practical behavior: In practice, t is usually Ω(m), making the second term negligible in many datasets, while balancing sparsification terms can improve performance in some situations.
4 Experiments
The experiments evaluate several triangle-counting variants on real-world web graphs using different sampling, sparsification, and implementation choices. Results show that no variant consistently dominates, while the reported error rates and running times improve substantially over previous results.
- 4.1 Data: The experiments use real-world web graphs, with multiple edges and self-loops removed when present.Experiments ran on a single machine using a C++ implementation compiled with gcc and optimization enabled.
- 4.2 Implementation: Sorting edges into neighbor lists improves cache behavior and can significantly improve performance.The preprocessing time for converting the input into this format was not counted.
- 4.2 Implementation: Offline processing checks whether the third edge exists for sampled triples, allowing one graph pass after sorting query lists.The sampling rate can be varied so the number of queries is approximately the graph size.
- 4.3 Results: The six evaluated code variants combine optional edge sparsification at p = 0.1 with exact, simple triple-sampling, or hybrid-sampling algorithms.The simple and hybrid sampling methods differ in how they handle triples associated with low- and high-degree vertices.
- 4.4 Remarks: No variant clearly outperforms all others across the datasets, while the reported error rates and running times are significantly lower than previous results.On wiki graphs, the exact algorithms have roughly the same speed order as other approximate triangle-counting implementations.
5 Theoretical Ramifications
The paper examines random-projection and semistreaming approaches to triangle counting, including concentration conditions and a degree-aware sampling procedure. It also identifies limitations of projection-based preservation and gives a three-pass streaming adaptation with stated space usage.
- 5.1 Random Projections and Triangles: Random projections approximately preserve Euclidean distances but not all pairwise inner products, so triangle counting requires a more targeted approach.The triangle count depends on inner products of adjacency-matrix columns, but the paper notes that general inner-product preservation is unavailable.
- 5.1 Random Projections and Triangles: The direct cubic random-projection estimator has expectation zero because it is a linear combination of zero-mean triple products, so that projection cannot be used directly.The paper therefore considers a quadratic-form-based approach instead.
- 5.1 Random Projections and Triangles: A sufficient concentration condition requires the estimator’s variance to be small relative to the square of its mean, rather than requiring exponential tails.The estimated mean is tied to the triangle count, while the variance analysis involves circuits of length 6.
- 5.1 Random Projections and Triangles: The concentration condition is sufficient but not necessary and can fail for graphs with many 6-circuits and no triangles.Thus, the random-projection guarantee has a graph-structure-dependent limitation.
- 5.2 Sampling in the Semi-Streaming Model: The semistreaming procedure treats low- and high-degree vertices differently and stores sampled edge queries for final membership checks.Low-degree neighbors are read directly, while high-degree vertices use binomially sampled vertex selections; the sampled triples are checked with a hash table.
6 Conclusions & Future Work
The paper extends triangle-counting methods with degree-based partitioning, supports semi-streaming use, and reports strong practical performance. It also introduces a random-projection approach and identifies parallel implementation as future work.
- The proposed Monte Carlo algorithm combines prior sampling with Alon, Yuster and Zwick’s partitioning idea to approximate triangle counts within ε.
- The method extends to the semi-streaming model using three passes and bounded memory overhead.
- In practice, the methods achieve excellent running times, often taking only a few seconds on graphs with several million edges, while maintaining satisfactory accuracy.
- The paper proposes random-projection triangle counting with a sufficient condition for obtaining a low-variance estimate.
- Because the proposed methods are easily parallelizable, a MapReduce implementation is identified as a natural practical direction.