论文标题
以速度交易准确性：子图计数的乘数引导程序
Trading off Accuracy for Speedup: Multiplier Bootstraps for Subgraph Counts
论文作者
论文摘要
我们为计数功能提出了一类新的乘数引导程序，范围从量身定制的快速，近似线性引导程序到稀疏，大型图形的二次引导程序，该过程为较小，较密集的图提供了精确的精度。对于快速，近似线性的引导程序，我们表明$ \ sqrt {n} $ - 计数功能的一致推断在某些取决于图形的稀疏度级别的计算方案中可以实现。此外，即使在更具挑战性的制度中，我们也证明了Bootstrap程序提供有效的覆盖范围和消失的置信区间。对于二次引导程序，我们建立了一个Edgeworth的扩展，并表明该过程在适当的稀疏条件下提供了更高级的精度。我们通过模拟研究和实际数据分析来补充理论结果，并验证我们的程序是否为多种功能提供了最先进的性能。
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.
