Pith. sign in

REVIEW 3 minor 43 references

A Hutchinson estimator variant using randomly incomplete matrix-vector products counts triangles accurately with lower communication costs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 09:43 UTC pith:R3UFCKXU

load-bearing objection The paper gives a Hutchinson trace estimator variant that stays unbiased under random partial observations of each matrix-vector product, with variance bounds that carry over from the standard case.

arxiv 2606.22629 v1 pith:R3UFCKXU submitted 2026-06-21 math.NA cs.NA

Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products

Soumyadip Ghosh , Lior Horesh , Vasileios Kalantzis , Yingdong Lu , Tomasz Nowicki , Shashanka Ubaru This is my paper
classification math.NA cs.NA
keywords triangle countingHutchinson estimatorrandomized trace estimationincomplete matrix-vector productsgraph motif countingdistributed algorithmsadjacency matrix trace
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a modified Hutchinson randomized trace estimator that uses only a random subset of entries from each matrix-vector product with the graph's adjacency matrix. This addresses the high cost of full observations in distributed computing due to communication and stragglers. Theoretical results establish that the estimator stays unbiased and has bounded variance, allowing control over the number of samples required. Numerical tests on synthetic and real graphs show it delivers precise triangle counts while cutting synchronization overhead.

Core claim

By treating both the count and positions of observed entries in each matrix-vector product as random variables, the trace of A cubed can be estimated without bias using the Hutchinson method, providing an efficient way to count triangles as one-sixth of that trace for large graphs where forming A^3 explicitly is impossible.

What carries the argument

The incomplete randomized trace estimator operating on partial matrix-vector products with random observation patterns.

Load-bearing premise

The random model for the number and identities of observed entries in each matrix-vector product is such that the standard unbiasedness and variance properties of the Hutchinson estimator extend directly to the incomplete case.

What would settle it

A direct comparison on a small graph with known exact triangle count, where the incomplete estimator is applied with the specified random observation model; if the estimates are biased beyond the variance bound, the claim fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The estimator is unbiased for the trace of the adjacency matrix cubed.
  • Bounds on variance yield explicit sample complexity requirements.
  • Triangle count estimates remain accurate on both synthetic and real-world graphs.
  • Communication and synchronization costs are reduced in distributed settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This could enable efficient counting of larger motifs by estimating traces of higher matrix powers under similar partial observations.
  • The approach may inspire variants for other linear algebra tasks in heterogeneous computing environments.
  • Extensions to non-uniform random observation models could further optimize for specific network structures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper proposes a variant of the Hutchinson randomized trace estimator for approximating tr(A^3) to count triangles in large graphs. The variant operates on matrix-vector products observed only partially, with both the count and identities of observed entries chosen randomly. It claims to establish unbiasedness of the estimator, variance bounds, and sample complexity guarantees under this observation model, and reports experiments on synthetic and real-world graphs showing accurate estimates with reduced synchronization costs in distributed settings.

Significance. If the unbiasedness and variance results hold under the stated random partial-observation model, the work would extend randomized linear algebra techniques to communication-constrained environments, offering a practical route to motif counting on heterogeneous or distributed architectures. The combination of theoretical guarantees with empirical validation on both synthetic and real graphs is a positive feature.

minor comments (3)
  1. The abstract and introduction should explicitly state the precise probability model (e.g., independent Bernoulli observations per entry, or a fixed random subset size) used for the incomplete matrix-vector products, as this is central to the claimed extension of the standard Hutchinson properties.
  2. In the experimental section, error bars or variance estimates across the random trials should be reported for the triangle-count estimates; the current description mentions accuracy but does not detail how many independent runs or how variance is quantified.
  3. Notation for the incomplete observation operator (e.g., the random mask matrix) should be introduced once and used consistently; occasional shifts between verbal description and symbols reduce readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of its potential significance in extending randomized linear algebra to communication-constrained settings, and the recommendation for minor revision. The report does not enumerate any specific major comments.

Circularity Check

0 steps flagged

No significant circularity; guarantees derived from stated random model

full rationale

The paper extends the Hutchinson estimator to incomplete matrix-vector products under a random observation model for both count and identities of entries. Theoretical claims on unbiasedness, variance, and sample complexity are presented as following directly from this model rather than from fitted parameters, self-citations, or definitional reductions. No load-bearing step reduces to its own inputs by construction; the derivation remains self-contained against the external random model. This matches the normal non-circular case for papers whose central result rests on an explicit probabilistic assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on extending the Hutchinson estimator to a new random partial-observation model; the main unstated cost is the assumption that this model preserves unbiasedness and admits clean variance bounds.

axioms (1)
  • domain assumption Random partial observation model for the number and identities of observed entries in matrix-vector products
    Invoked in the abstract as the operating constraint under which the new estimator is defined and analyzed.

pith-pipeline@v0.9.1-grok · 5743 in / 1287 out tokens · 27566 ms · 2026-06-26T09:43:42.328349+00:00 · methodology

0 comments
read the original 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 $\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 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 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.

Figures

Figures reproduced from arXiv: 2606.22629 by Lior Horesh, Shashanka Ubaru, Soumyadip Ghosh, Tomasz Nowicki, Vasileios Kalantzis, Yingdong Lu.

Figure 1
Figure 1. Figure 1: Cumulative relative error (top row) and 95% CI (bottom row) for the graph Er￾dos971. Figures 1-3 plot the cumulative relative error of the triangle counting estima￾tors as n = 1, 2, . . . , 1000, increases and f varies, as well as the 95% CI. As n, increases, the asymptotic behavior of each estimator improves to a more accurate approximation, although it is likely that better statistical approximations mig… view at source ↗
Figure 2
Figure 2. Figure 2: Cumulative relative error (top row) and 95% CI (bottom row) for the random graph. 0 500 1000 Iteration index 10−6 10−4 10−2 100 Relative error (log scale) Running relative error (f = 0.2) 0 500 1000 Iteration index 10−6 10−4 10−2 100 Relative error (log scale) Running relative error (f = 0.6) 0 500 1000 Iteration index 10−6 10−4 10−2 100 Relative error (log scale) Running relative error (f = 1.0) Iteration… view at source ↗
Figure 3
Figure 3. Figure 3: Cumulative relative error (top row) and 95% CI (bottom row) for the graph Har￾vard500 [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Top row: relative error as E[T]/N varies. Bottom row: 95% CI half-width. From left to right: Erdos971, random graph with N = 5000 nodes, and Hardvard500. 5 Conclusion In this paper, we considered the problem of estimating the number of triangles in large-scale graphs under constraints that limit full observation of matrix–vector products with the adjacency matrix. By extending Hutchinson’s randomized trace… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 2 canonical work pages

  1. [1]

    More asymmetry yields faster matrix mul tiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yi nzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix mul tiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discre te Algo- rithms (SODA) , pages 2005–2039

    2025

  2. [2]

    Finding and cou nting given length cycles

    Noga Alon, Raphael Yuster, and Uri Zwick. Finding and cou nting given length cycles. Algorithmica, 17(3):209–223, 1997

    1997

  3. [3]

    Counting triangles in large graphs using ran domized matrix trace estimation

    Haim A vron. Counting triangles in large graphs using ran domized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Ap- plications (KDD’10 Workshop) , Washington, DC, USA, 2010. A vailable as technical report from Tel A viv University

    2010

  4. [4]

    Randomized algorithms for e stimating the trace of an implicit symmetric positive semi-definite matri x

    Haim A vron and Sivan Toledo. Randomized algorithms for e stimating the trace of an implicit symmetric positive semi-definite matri x. Journal of the ACM (JACM), 58(2):1–34, 2011

    2011

  5. [5]

    Parallel tri angle counting and enumeration using matrix algebra

    Ariful Azad, Aydin Buluç, and John Gilbert. Parallel tri angle counting and enumeration using matrix algebra. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop , pages 804–811, 2015

    2015

  6. [6]

    An estimator for the diagonal of a matrix

    Costas Bekas, Effrosyni Kokiopoulou, and Yousef Saad. An estimator for the diagonal of a matrix. Applied Numerical Mathematics , 57(11–12):1214–1229, 2007. REFERENCES 21

    2007

  7. [7]

    Parallel and distributed computation: numerical methods

    Dimitri Bertsekas and John Tsitsiklis. Parallel and distributed computation: numerical methods. Athena Scientific, 2015

    2015

  8. [8]

    Fine-grained parallel incom plete lu factoriza- tion

    Edmond Chow and Anil Patel. Fine-grained parallel incom plete lu factoriza- tion. SIAM Journal on Scientific Computing , 37(2):C169–C193, 2015

    2015

  9. [9]

    Matrix multiplica tion via arith- metic progressions

    Don Coppersmith and Shmuel Winograd. Matrix multiplica tion via arith- metic progressions. Journal of symbolic computation , 9(3):251–280, 1990

    1990

  10. [10]

    The University of Florida s parse matrix collection

    Timothy A Davis and Yifan Hu. The University of Florida s parse matrix collection. ACM Transactions on Mathematical Software (TOMS) , 38(1):1– 25, 2011

    2011

  11. [11]

    Power iterati on with prob- abilistic updates for systems with heterogeneous performa nce

    Soumyadip Ghosh, Lior Horesh, Vassilis Kalantzis, Geo rgios Kollias, Ying- dong Lu, Tomasz Nowicki, and Shashanka Ubaru. Power iterati on with prob- abilistic updates for systems with heterogeneous performa nce. In 2025 IEEE High Performance Extreme Computing Conference (HPEC) , pages 1–7. IEEE, 2025

    2025

  12. [12]

    Michael B. Giles. Multilevel monte carlo methods. Acta Numerica, 24:259– 328, 2015

    2015

  13. [13]

    Co mpact estimator for streaming triangle counting

    Jiqing Gu, Chao Song, Haipeng Dai, Li Lu, and Ming Liu. Co mpact estimator for streaming triangle counting. IEEE Transactions on Knowledge and Data Engineering, 2024

    2024

  14. [14]

    On the variance of schatten p-norm estimation with gaussian sk etching matrices

    Lior Horesh, Vasileios Kalantzis, Yingdong Lu, and Tom asz Nowicki. On the variance of schatten p-norm estimation with gaussian sk etching matrices. Monte Carlo Methods and Applications , 31(2):119–130, 2025

    2025

  15. [15]

    Hutchinson

    Michael F. Hutchinson. A stochastic estimator of the tr ace of the influence matrix for Laplacian smoothing splines. Communications in Statistics – Sim- ulation and Computation , 19(2):433–450, 1990

    1990

  16. [16]

    Acce lerating data un- certainty quantification by solving linear systems with mul tiple right-hand sides

    V Kalantzis, C Bekas, A Curioni, and E Gallopoulos. Acce lerating data un- certainty quantification by solving linear systems with mul tiple right-hand sides. Numerical Algorithms, 4(62):637–653, 2013

    2013

  17. [17]

    Asynchronous randomized trace estimation

    Vasileios Kalantzis, Shashanka Ubaru, Chai Wah Wu, Geo rgios Kollias, and Lior Horesh. Asynchronous randomized trace estimation. In Sanjoy Das- gupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and St atistics, volume 238 of Proceedings of Machine Learning Research, pages 4294–4302. ...

    2024

  18. [18]

    Asynchronous randomized trace estimation

    Vasileios Kalantzis, Shashanka Ubaru, Chai Wah Wu, Geo rgios Kollias, and Lior Horesh. Asynchronous randomized trace estimation. In International Conference on Artificial Intelligence and Statistics , pages 4294–4302. PMLR, 2024

    2024

  19. [19]

    Straggler- 22 REFERENCES tolerant stationary methods for linear systems

    Vassilis Kalantzis, Yuanzhe Xi, Lior Horesh, and Youse f Saad. Straggler- 22 REFERENCES tolerant stationary methods for linear systems. SIAM Journal on Scientific Computing, (0):S1–S22, 2025

    2025

  20. [20]

    Counting triangles in massive graphs with mapreduce

    Tamara G Kolda, Ali Pinar, Todd Plantenga, C Seshadhri, and Christine Task. Counting triangles in massive graphs with mapreduce. SIAM J. Sci. Comp., 36(5):S48–S77, 2014

    2014

  21. [21]

    Counting triangles of graphs vi a matrix partitioning

    Georgios Kollias et al. Counting triangles of graphs vi a matrix partitioning. In Proceedings of the 34th IEEE International Workshop on Mach ine Learn- ing for Signal Processing (MLSP 2024) , 2024. Preprint available via NSF https://par.nsf.gov/biblio/10593378

    work page arXiv 2024

  22. [22]

    Kolountzakis et al

    Mihail N. Kolountzakis et al. Efficient triangle countin g in large graphs via degree-based vertex partitioning. In Algorithms and Models for the Web- Graph, pages 15–24. Springer Berlin Heidelberg, 2010

    2010

  23. [23]

    Meyer, Cameron Musco, Christopher Musco, an d David P

    Raphael A. Meyer, Cameron Musco, Christopher Musco, an d David P. Woodruff. Hutch++: Optimal stochastic trace estimation. arXiv preprint arXiv:2010.09649, 2020. Preprint available online

    work page arXiv 2010

  24. [24]

    Shen-Orr, Shalev Itzkovitz, Nadav Kas htan, Dmitri Chklovskii, and Uri Alon

    Ron Milo, Shai S. Shen-Orr, Shalev Itzkovitz, Nadav Kas htan, Dmitri Chklovskii, and Uri Alon. Network motifs: Simple building b locks of com- plex networks. Science, 298(5594):824–827, 2002

    2002

  25. [25]

    Numerical computing with MATLAB

    Cleve B Moler. Numerical computing with MATLAB . SIAM, 2004

    2004

  26. [26]

    The structure and function of complex ne tworks

    Mark EJ Newman. The structure and function of complex ne tworks. SIAM review, 45(2):167–256, 2003

    2003

  27. [27]

    Triangle counting for scale-free graphs at scale in distributed memory

    Roger Pearce. Triangle counting for scale-free graphs at scale in distributed memory. In 2017 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–4, 2017

    2017

  28. [28]

    Improved variants of the hutch++ algorithm for trace estimation

    David Persson, Alice Cortinovis, and Daniel Kressner. Improved variants of the hutch++ algorithm for trace estimation. SIAM Journal on Matrix Analysis and Applications , 43(3):1162–1185, 2022

    2022

  29. [29]

    Robert and George Casella

    Christian P. Robert and George Casella. Monte Carlo Statistical Methods . Springer, New York, 2nd edition, 2004

    2004

  30. [30]

    DNA microarray d ata and contex- tual analysis of correlation graphs

    Jacques Rougemont and Pascal Hingamp. DNA microarray d ata and contex- tual analysis of correlation graphs. BMC bioinformatics , 4(1):15, 2003

    2003

  31. [31]

    A new randomized vector algorithm for i terative solution of large linear systems

    Karl Sabelfeld. A new randomized vector algorithm for i terative solution of large linear systems. Applied Mathematics Letters , 126:107830, 2022

    2022

  32. [32]

    A 2d parallel triangl e counting algo- rithm for distributed-memory architectures

    Ancy Sarah Tom and George Karypis. A 2d parallel triangl e counting algo- rithm for distributed-memory architectures. In Proceedings of the 48th In- ternational Conference on Parallel Processing , ICPP 2019, pages 45:1–45:10, New York, NY, USA, 2019. ACM

    2019

  33. [33]

    Tsitsiklis, Dimitri P

    John N. Tsitsiklis, Dimitri P. Bertsekas, and Michael A thans. Distributed asynchronous deterministic and stochastic gradient optim ization algorithms. IEEE Transactions on Automatic Control , 31(9):803–812, 1986. REFERENCES 23

    1986

  34. [34]

    C. E. Tsourakakis. Fast counting of triangles in large r eal networks without counting: Algorithms and laws. In 2008 Eighth IEEE International Confer- ence on Data Mining , pages 608–617, Dec 2008

    2008

  35. [35]

    Counting triangles in real -world networks using projections

    Charalampos E Tsourakakis. Counting triangles in real -world networks using projections. Knowledge and Information Systems , 26(3):501–520, 2011

    2011

  36. [36]

    Tsourakakis, U

    Charalampos E. Tsourakakis, U. Kang, Gary L. Miller, an d Christos Faloutsos. Doulion: Counting triangles in massive graphs with a coin. I n Proceedings of the 15th ACM SIGKDD International Conference on Knowledge D iscovery and Data Mining (KDD ’09) , pages 837–846. ACM, 2009

    2009

  37. [37]

    Spectral counting of tr iangles in power-law networks via element-wise sparsification

    Charalampos Tsourakakis et al. Spectral counting of tr iangles in power-law networks via element-wise sparsification. In 2009 International Conference on Advances in Social Network Analysis and Mining , pages 66–71. IEEE, 2009

    2009

  38. [38]

    Visualizing the signatures of social roles in online discussion groups

    Howard T Welser, Eric Gleave, Danyel Fisher, and Marc Sm ith. Visualizing the signatures of social roles in online discussion groups. Journal of social structure, 8(2):1–32, 2007

    2007

  39. [39]

    Fast linear algebra-based triangl e counting with kokkoskernels

    Michael M Wolf et al. Fast linear algebra-based triangl e counting with kokkoskernels. In 2017 IEEE High Performance Extreme Computing Con- ference (HPEC), pages 1–7. IEEE, 2017

    2017

  40. [40]

    Estimating the trace of the matrix inverse by interpo- lating from the diagonal of an approximate inverse

    Lingfei Wu, Jesse Laeuchli, Vassilis Kalantzis, Andre as Stathopoulos, and Efstratios Gallopoulos. Estimating the trace of the matrix inverse by interpo- lating from the diagonal of an approximate inverse. Journal of Computational Physics, 326:828–844, 2016

    2016

  41. [41]

    Functional and topological characterization of protein interaction n etworks

    Soon-Hyung Yook, Zoltán N Oltvai, and Albert-László Ba rabási. Functional and topological characterization of protein interaction n etworks. Proteomics, 4(4):928–942, 2004

    2004

  42. [42]

    LiteTE: Lightweight, communication-efficient distr ibuted-memory triangle enumerating

    Yongxuan Zhang, Hong Jiang, Fang Wang, Yu Hua, Dan Feng, and Xiang- hao Xu. LiteTE: Lightweight, communication-efficient distr ibuted-memory triangle enumerating. IEEE Access, 7:26294–26306, 2019

    2019

  43. [43]

    Sparse hanson–wright inequalities for s ubgaussian quadratic forms

    Shuheng Zhou. Sparse hanson–wright inequalities for s ubgaussian quadratic forms. Bernoulli, 25(3):1603–1639, 2019

    2019