Counting triangles of graphs via randomized trace estimation with incomplete matrix-vector products

Abstract Counting triangles in graphs is a fundamental operation in network analysis, underpinning metrics such as clustering coefficients and serving as a signal for community detection, link prediction, and anomaly detection. The standard approach computes the trace of the cube of the adjacency matrix, but explicitly forming <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mi>𝐀</m:mi> <m:mn>3</m:mn> </m:msup> </m:math> {\mathbf{A}^{3}} is infeasible for large graphs. Hutchinson’s randomized trace estimator offers an efficient alternative by approximating <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>Tr</m:mi> <m:mo>⁡</m:mo> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:msup> <m:mi>𝐀</m:mi> <m:mn>3</m:mn> </m:msup> <m:mo stretchy="false">)</m:mo> </m:mrow> </m:mrow> </m:math> {\operatorname{Tr}(\mathbf{A}^{3})} through stochastic averaging of quadratic forms, requiring only matrix-vector products with <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>𝐀</m:mi> </m:math> {\mathbf{A}} . However, in distributed and heterogeneous computing environments, observing all entries of these products can be costly due to communication overhead and straggler effects. To address this, we propose a new variant of Hutchinson’s estimator that operates under partial observation constraints, where both the number and identities of observed entries are random. We provide theoretical guarantees on unbiasedness, variance bounds, and sample complexity, and demonstrate through experiments on synthetic and real-world graphs that our method achieves accurate triangle count estimates while reducing synchronization costs. This work highlights the adaptability of randomized algorithms to modern computational architectures and opens avenues for efficient motif counting in large-scale network analytics.