This paper introduces a triangle counting estimator for massive graphs that achieves (1±·) approximation using only O(log n)-wise independence, significantly reducing variance and matching the accuracy of fully independent approaches.
Key findings
A novel triangle counting estimator based on k-wise independent edge sketches achieves (1±·) approximation with O(log n)-wise independence.
An adaptive refinement mechanism reduces variance by increasing sampling density in high local triangle density regions.
The algorithm matches the accuracy of fully independent approaches with O(m/·^2) space complexity.
Experiments on diverse graph types demonstrate 2--3× variance reduction from adaptive refinement and validate theoretical space bounds.
Limitations & open questions
The paper does not discuss the potential impact of graph sparsity on the performance of the estimator.
The scalability of the algorithm for graphs with extremely large numbers of vertices and edges is not fully explored.