# Trading off Accuracy for Speedup: Multiplier Bootstraps for Subgraph Counts

arXiv: https://arxiv.org/abs/2009.06170 · HTML: https://mlsanity.com/paper/2009.06170/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2020.

## Built on by (most cited first, 1 of 1)

- [Rethinking Epistemic Uncertainty in Node Classification through Information Growth](https://mlsanity.com/paper/2610.03418/) (2026)

## Abstract (arXiv)

We propose a new class of multiplier bootstraps for count functionals, ranging from a fast, approximate linear bootstrap tailored to sparse, massive graphs to a quadratic bootstrap procedure that offers refined accuracy for smaller, denser graphs. For the fast, approximate linear bootstrap, we show that √n-consistent inference of the count functional is attainable in certain computational regimes that depend on the sparsity level of the graph. Furthermore, even in more challenging regimes, we prove that our bootstrap procedure offers valid coverage and vanishing confidence intervals. For the quadratic bootstrap, we establish an Edgeworth expansion and show that this procedure offers higher-order accuracy under appropriate sparsity conditions. We complement our theoretical results with a simulation study and real data analysis and verify that our procedure offers state-of-the-art performance for several functionals.