Source-linked AI summary
Approximately Counting Triangles in Sublinear Time
Talya Eden, Amit Levi, Dana Ron, C. Seshadhri
TL;DR
Triangle counting lacks sublinear algorithms when only degree and neighbor queries are available. This paper adds vertex-pair queries and designs an estimator with high-probability multiplicative accuracy. Its query complexity matches the lower bound up to polylogarithmic factors and dependence on 1/ε.
Problem
Existing triangle-counting algorithms read the entire graph, while degree and neighbor queries alone do not permit sublinear approximation.
Method
The paper designs a sublinear triangle-counting algorithm using degree, neighbor, and vertex-pair queries.
Results
The estimator achieves a (1−ε)-to-(1+ε) approximation with high constant probability, with query complexity nearly matching the lower bound.
Takeaways & Limitations
Adding vertex-pair queries makes sublinear triangle-count approximation possible with nearly optimal query complexity.
Takeaways & Limitations
The lower-bound argument uses random new-neighbor queries and separately derives implications for standard neighbor queries.
Abstract
from arXiv · showhide
We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter $0<ε<1$, the algorithm provides an estimate $\widehat{t}$ such that with high constant probability, $(1-ε)\cdot t< \widehat{t}<(1+ε)\cdot t$, where $t$ is the number of triangles in the graph $G$. The expected query complexity of the algorithm is $\!\left(\frac{n}{t^{1/3}} + \min\left\{m, \frac{m^{3/2}}{t}\right\}\right)\cdot {\rm poly}(\log n, 1/ε)$, where $n$ is the number of vertices in the graph and $m$ is the number of edges, and the expected running time is $\!\left(\frac{n}{t^{1/3}} + \frac{m^{3/2}}{t}\right)\cdot {\rm poly}(\log n, 1/ε)$. We also prove that $Ω\!\left(\frac{n}{t^{1/3}} + \min\left\{m, \frac{m^{3/2}}{t}\right\}\right)$ queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in $n$ (and the dependence on $1/ε$).
1 Introduction
Triangle counting is a fundamental graph problem with applications across network analysis, but existing algorithms read the entire graph. This work asks whether vertex-pair queries can enable sublinear-time approximation.
- Existing triangle-counting algorithms read the entire graph, motivating sublinear algorithms for massive graphs.
- The algorithm accesses graphs through degree, neighbor, and vertex-pair queries.
- Earlier work ruled out sublinear approximation with degree and neighbor queries alone.
- The paper shows that sublinear approximation is possible when vertex-pair queries are added.
1.1 Results
The paper gives a sublinear estimator with explicit accuracy and complexity guarantees, then proves a matching lower bound up to polylogarithmic and approximation-parameter factors.
- With high constant probability, the estimator returns a (1−ε)-to-(1+ε) approximation of the triangle count.
- The lower bound establishes that the query complexity is almost optimal.
- Earlier lower-bound work required Ω(n) degree and neighbor queries in a setting without pair queries.
1.2 Overview of the algorithm
The algorithm reduces estimator variance by separating heavy and light vertices, weighting triangles by light endpoints, and sampling edges and neighbors efficiently. These procedures yield the stated running-time and query bounds.
- 1.2.1 A simple oracle-based procedure for a 1/3-estimate: The oracle-based procedure uses uniform vertex sampling and truncation to obtain a controlled 1/3-estimate.
- 1.2.1 A simple oracle-based procedure for a 1/3-estimate: Heavy vertices are thresholded to control variance, while triangles whose endpoints are all heavy contribute only O(εt).
- 1.2.2 Assigning weights to triangles so as to improve the estimate: The estimator assigns inverse weights based on each triangle’s number of light endpoints, achieving expected value within (1±O(ε))t.
- 1.2.3 Deciding whether a vertex is heavy: Heavy-versus-light decisions estimate incident triangle counts by sampling random incident edges and neighbors.
- 1.2.4 Estimating P: The final estimator samples directed edges incident to sampled vertices and estimates their assigned triangle weights using smaller-degree endpoints.
- 1.2.4 Estimating P: When t < m^(1/2), the query bound can replace m^(3/2)/t with m by storing queried edges.
1.3 A high level discussion of the lower bound
The lower-bound construction compares triangle-free graphs with graphs containing Θ(t) triangles while preserving n and m. Distinguishing these cases requires the same asymptotic query scale as the upper bound.
- The construction uses graphs with n vertices and m edges, including a triangle-free graph and graphs with Θ(t) triangles.
- For t ≥ √m, distinguishing the graph families requires the corresponding lower-bound query scale.
- For t < √m, at least Ω(m) queries are required.
- Three constructions handle different ranges of t as a function of m.
1.4 Related Work
Prior triangle-counting algorithms span theoretical, practical, streaming, distributed, and other models, but typically inspect the whole graph. This work follows sampling-based estimation while addressing the challenge of constructing a suitable random experiment with sublinear query access.
- Sublinear graph-parameter algorithms previously estimated average degree and stars using degree and neighbor queries.
- Triangle counting is harder than star counting because triangles are induced subgraphs, whereas stars are non-induced.
- Existing triangle-counting algorithms use matrix multiplication, enumeration, eigenvalues, sparsification, path sampling, and specialized computation models.
- Sampling methods estimate triangle counts from random vertices or edges whose induced triples are tested for triangles.
2 Preliminaries
The paper studies simple graphs through uniform vertex sampling and degree, neighbor, and pair queries. It fixes notation, a degree-based vertex order, and probabilistic tools used in the algorithm’s analysis.
- The graph has n vertices and m edges; degrees, neighborhoods, incident edges, incident triangles, and the total triangle count receive dedicated notation.
- The query model permits uniform vertex sampling, degree queries, neighbor queries, and pair queries testing whether two vertices share an edge.
- The analysis uses a multiplicative Chernoff bound for bounded independent variables and Chebyshev’s inequality.
- Vertices are ordered by increasing degree, breaking ties by vertex identifier, and two degree queries determine the order of a pair.
- A claim bounds the number of neighbors ordered after a fixed vertex by using degree comparisons.
3 The Algorithm
The algorithm partitions vertices into heavy and light classes, assigns triangle weights to support unbiased sampling, estimates heavy status, and combines these components into a final estimator. Its analysis establishes approximation, success probability, and sublinear complexity without prior knowledge of graph parameters.
- 3.1 Heavy and light vertices: Triangles are assigned to directed incident edges according to the vertex order, and triangle weights depend on how many endpoints lie in the light set.
- 3.3 Estimating the number of triangles: With an appropriate partition, zero-weight triangles contribute at most c_H · εt, while the weighted estimator has expectation between t(1 − c_H · ε) and t.
- 3.2 Classifying vertices: Heavy(v) classifies every genuinely heavy or light vertex correctly with probability at least 1 − 1/n^2, yielding an appropriate partition with probability at least 1 − 1/n.
- 3.3 Estimating the number of triangles: The estimator uses three nested randomness levels—vertex samples, selected incident edges, and neighborhood samples—to control its expectation and deviation.
- 3.4 The final algorithm: It removes the initial requirement for prior estimates of the edge and triangle counts through geometric search and average-degree approximation.
- 3.4 The final algorithm: The final algorithm returns a (1 ± ε)-approximation with probability at least 5/6, using O*(n/t^1/3 + min{m, m^3/2/t}) expected queries and O*(n/t^1/3 + m^3/2/t) expected time.
4 A Lower Bound
The lower-bound section proves that triangle-counting approximation requires many queries under degree, pair, and random new-neighbor access. Its constructions match the algorithm’s dependence on n, m, and t up to polylogarithmic and 1/ε factors.
- The lower bound matches the upper bound’s dependence on n, m, and t(G) up to polylogarithmic factors and dependence on 1/ε.
- Ω(n/t^(1/3)) queries are necessary to distinguish an empty graph from graphs containing Θ(t) triangles hidden in a clique.
- For larger triangle counts, Ω(m^(3/2)/t) queries are required to distinguish a triangle-free bipartite graph from a family containing Θ(t) triangles.
- The lower-bound constructions preserve vertex degrees, so degree queries reveal no useful distinguishing information.
- Pair and neighbor algorithms must find rare witness pairs, requiring Ω(m^(3/2)/t) queries in the relevant construction.
- The formal lower-bound analysis compares query-answer processes for a fixed graph and a uniformly selected graph family using knowledge graphs and query histories.
4.1 A lower bound for t = m
For t = m, the hard family modifies a complete bipartite graph with matchings that create Θ(m) triangles while preserving degrees, making the two cases difficult to distinguish.
- 4.1.1 The lower-bound construction: The construction creates Θ(m) triangles by adding blue matchings within the two sides and removing a red matching across the bipartition.
- 4.1.2 Definition of the processes P1 and P2: The process P2 answers queries while constructing a uniformly selected graph from the hard family, and its final distribution is uniform over that family.
- 4.1.2 Definition of the processes P1 and P2: The analysis bounds distinguishability by tracking query-answer histories and the probability of detecting witness pairs.
- 4.1.2 Definition of the processes P1 and P2: A witness pair is a positive within-side pair, a negative crossing pair, or a random neighbor query returning a within-side vertex.
- 4.1.3 The auxiliary graph for t = m: The auxiliary graph connects witness and non-witness graph instances through matching switches that preserve matching size.
4.2 A lower bound for m < t < m3/2
For m < t < m^3/2, the lower-bound construction repeats the t = m construction through r matchings, yielding graphs with Θ(r·m) triangles while preserving degrees. An auxiliary-graph argument shows that algorithms using at most Q queries cannot reliably distinguish the zero-triangle graph from the Θ(t)-triangle family.
- Lower-bound construction: The construction repeats the t = m family r times, using r edge-disjoint red matchings and r edge-disjoint blue matchings on each bipartite side.Each graph is defined by 3r matchings, with red matchings crossing between the two sides and blue matchings within each side.
- Lower-bound construction: Every graph in the constructed family contains Θ(r·m)=Θ(t) triangles.The construction distinguishes blue and mixed triangles; each blue edge participates in many mixed triangles, while the number of blue triangles is bounded.
- Auxiliary graph: A witness graph is obtained by making a queried pair part of one of the red or blue matchings, while switches preserve the matching structure and connect witness to non-witness graphs.The auxiliary graph links graphs differing by a switch involving the queried pair and one additional pair.
- Statistical distance: Consequently, after fewer than Q queries, the transcript distributions for the zero-triangle and Θ(t)-triangle cases have small statistical distance.The stated lemmas establish this indistinguishability for Q in the relevant range, completing the lower-bound argument for this regime.
- Auxiliary graph: For every relevant pair, witness graphs have degree at least 1/√m and non-witness graphs have degree at most r in the auxiliary graph.The proof accounts for the r red matchings when bounding candidate switches and non-witness neighbors.
4.3 A lower bound for √
For the √m-scale regime, the construction uses partial crossing matchings and matched squares to create graphs with many triangles while retaining the degree pattern of a triangle-free graph. Modified query-answering processes and switching arguments establish indistinguishability even when all-neighbors queries are allowed.
- The lower-bound construction: The family uses a crossing matching of size k and paired blue matchings, forming matched squares while preserving every vertex degree at √m.Each matched square contains two red pairs and two blue pairs; unmatched four-tuples form the alternative switching locations.
- The lower-bound construction: Every blue edge participates in √m−2 triangles, and every triangle contains exactly one blue edge.Thus the triangle count is determined by the number k of matched structures.
- The auxiliary graph: The switching analysis bounds the number of compatible witness alternatives while limiting how many witness graphs each non-witness graph can reach.The proof counts potential squares and accounts for queried induced pairs when maintaining consistency with the transcript.
- The auxiliary graph: A switch removes the red and blue edges of one matched square and inserts the corresponding edges of an unmatched square.This operation changes which square is matched while preserving the matching-based construction.
- Statistical distance: The lower-bound processes treat unusually informative neighbor responses as witness answers and condition the comparison on histories without such answers.All-neighbors queries can reveal a deviation from the complete bipartite neighborhood, so they receive a separate analysis.
4.4 Lower Bound for t < 1
For smaller triangle counts, the lower-bound construction uses two bipartite components with carefully removed and added edges, producing a triangle-free family and a family with exactly 4t triangles. Green and purple special edges support a switching argument that remains indistinguishable under limited queries.
- The construction: The base graph consists of two complete bipartite components whose degrees are preserved by removing red edges and adding blue cross-component edges.The construction partitions each side into subsets and replaces selected within-component complete bipartite subgraphs with cross-component ones.
- The construction: The modified graph family adds green special edges and removes purple special edges, changing one incident edge at each special vertex.The special pairs are (a*, c*) and (b*, d*) for green edges, and (a*, b*) and (c*, d*) for purple edges.
- Triangle counts: The base graph has no triangles, whereas every graph in the modified family has exactly 4t triangles.Each green edge participates in 2t triangles, and the two green edges account for the total.
- The auxiliary graph: A switch replaces a green special pair with an eligible unmatched pair by restoring the associated purple edges and removing the corresponding alternative edges.The operation is defined so that the special-edge structure moves without changing the broader construction.
- The auxiliary graph: For limited-query algorithms, the auxiliary graph has many compatible witness switches but at most one way to turn a non-witness graph into a witness graph.This imbalance supports the subsequent statistical-distance lower bound.
4.5 Wrapping things up
The final reduction converts ordinary neighbor queries into random new-neighbor queries with at most a constant-factor query increase. This transfers the lower bounds to algorithms using degree, pair, and neighbor queries.
- Wrapping things up: Any algorithm using degree, pair, and neighbor queries can be simulated with random new-neighbor queries using at most three times as many graph queries.The simulation preserves degree and pair queries directly and randomizes unused neighbor labels for neighbor queries.
- Wrapping things up: The simulation stores previously used neighbor labels so that its answers match those of the original neighbor-query algorithm.The resulting algorithm has the same approximation success probability as the original one.