{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-21","reactions":{}}