Id: arxiv/2606.22629 Url: https://arxiv.org/abs/2606.22629 Tags: math.NA Score: 0 Title: Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products Domain: math.NA Source: arxiv Authors: Soumyadip Ghosh, Lior Horesh, Vasileios Kalantzis, Yingdong Lu, Tomasz Nowicki, Shashanka Ubaru Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-21 Page: https://delphi.science/r/arxiv/2606.22629 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 $\mathbf{A}^3$ is infeasible for large graphs. Hutchinson randomized trace estimator offers an efficient alternative by approximating the trace through stochastic averaging of quadratic forms, requiring only matrix vector products with $\mathbf{A}$. However, in distributed and…