{"ID":2880043,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14324","arxiv_id":"2508.14324","title":"Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs","abstract":"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 $φ$, which incurs at most $\\varepsilon/2$ in $\\ell_1$-distance by removing at most $φ|V|$ edges; and (ii) the sampling error, controlled by the accuracy parameter $\\varepsilon$, bounded by $\\varepsilon/2$ via $N=Θ(\\varepsilon^{-2})$ random vertex queries and a Chernoff and union bound argument. Combining these yields an overall $\\ell_1$-error of $\\varepsilon$ with high probability. Algorithmically, we show that by sampling $N=\\lceil C\\varepsilon^{-2} \\rceil$ vertices and querying the local partition oracle, one can in time $poly(d,k,\\varepsilon^{-1})$ construct a summary graph $H$ of size $|H|=poly(d^k,1/\\varepsilon)$ whose $k$-disc frequency vector approximates that of the original graph within $\\varepsilon$ in $\\ell_1$-distance. Our approach clarifies the dependence of both runtime and summary-size on the parameter $d$,$k$, and $\\varepsilon$.","short_abstract":"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 analys...","url_abs":"https://arxiv.org/abs/2508.14324","url_pdf":"https://arxiv.org/pdf/2508.14324v2","authors":"[\"Gregory Moroie\"]","published":"2025-08-20T00:40:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}