# Approximately Counting Triangles in Sublinear Time

arXiv: https://arxiv.org/abs/1504.00954 · HTML: https://mlsanity.com/paper/1504.00954/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2015.

## Built on by (most cited first, 6 of 6)

- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoders](https://mlsanity.com/paper/2210.16844/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Target Circuit Matching in Large-Scale Netlists using GNN-Based Region Prediction](https://mlsanity.com/paper/2507.19518/) (2025)
- [Stochastic trace estimation with tensor train random vectors](https://mlsanity.com/paper/2606.15679/) (2026)

## Abstract (arXiv)

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 widehatt such that with high constant probability, (1-ε)· t< widehatt<(1+ε)· t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is !left(fracnt1/3 + minleftm, fracm3/2trightright)· 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(fracnt1/3 + fracm3/2tright)· rm poly(log n, 1/ε). We also prove that Omega!left(fracnt1/3 + minleftm, fracm3/2trightright) 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/ε).