Trading off Accuracy for Speedup: Multiplier Bootstraps for Subgraph Counts
This work addresses computational bottlenecks in statistical inference for graph data, offering scalable methods for researchers analyzing large networks, though it is incremental as it builds on existing bootstrap techniques.
The authors tackled the problem of efficiently estimating subgraph counts in graphs by proposing multiplier bootstraps that trade off accuracy for computational speed, achieving √n-consistent inference in certain sparsity regimes and valid coverage with vanishing confidence intervals in more challenging ones, with simulations and real data showing state-of-the-art performance.
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 $\sqrt{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.