Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908496684908544 |
|---|---|
| author | Moroie, Gregory |
| author_facet | Moroie, Gregory |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14324 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs Moroie, Gregory Data Structures and Algorithms Computational Complexity 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$. |
| title | Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2508.14324 |