Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs

In this work, we address the problem of approximating the $k$-disc distribution (“frequency vector”) of a bounded-degree graph in sublinear-time under the assumption of hyperfiniteness. We revisit the partition-oracle framework of Hassidim, Kelner, Nguyen, and Onak [HKNO09], and provide a concise, self-contained analysis that explicitly separates the two sources of error: (i) the cut error, controlled by hyperfiniteness parameter $\phi$, which incurs at most $\epsilon \mathrm{/}2$ in ${\mathrm{\ell }}_1$-distance by removing at most $\phi \mathrm{\mid }V\mathrm{\mid }$ edges; and (ii) the sampling error, controlled by the accuracy parameter $\epsilon$, bounded by $\epsilon \mathrm{/}2$ via $N=\mathrm{\Theta }({\epsilon }^{-2})$ random vertex queries and a Chernoff and union bound argument. Combining these yields an overall ${\mathrm{\ell }}_1$-error of $\epsilon$ with high probability. Algorithmically, we show that by sampling $N=\lceil C{\epsilon }^{-2}\rceil$ vertices and querying the local partition oracle, one can in time $poly(d,k,{\epsilon }^{-1})$ construct a summary graph $H$ of size $\mathrm{\mid }H\mathrm{\mid }=poly(d^k,1\mathrm{/}\epsilon )$ whose $k$-disc frequency vector approximates that of the original graph within $\epsilon$ in ${\mathrm{\ell }}_1$-distance. Our approach clarifies the dependence of both runtime and summary-size on the parameter $d$,$k$, and $\epsilon$.