Paper 2026/2759

Differentially Oblivious Graph Ball Queries

Abstract

A graph ball query returns all vertices within distance $r$ of a source vertex. On $N$-vertex graphs with maximum degree at most $\Delta$, ordinary breadth-first search answers such queries with $O_{\Delta,r}(1)$ record accesses. These accesses depend on private edges and can reveal graph structure. Full obliviousness hides this dependence, but incurs substantial overhead. Differential obliviousness (DO) [Chan et al., SODA'2019] trades off between privacy and efficiency by relaxing full obliviousness to $(\varepsilon, \delta)$-differential privacy on the access traces of neighboring graphs. We study DO graph ball queries under three widely-adopted edge-level neighboring relations: add/delete, replacement, and $2$-switch. Starting from padded adjacency records, we charge all observable accesses, including preprocessing. For fixed $\Delta,r\ge2$, error probability $0<\beta<1/2$, and $0\le\delta\le(1-2\beta)/2$, we prove an $\Omega_{\Delta,r,\beta}(1+Ne^{-\varepsilon})$ expected lower bound at every sufficiently large connected graph and every public source. For every fixed $r\ge2$, we give $(\varepsilon,0)$-DO sampling algorithms with expected cost $O_{\Delta,r,\beta}(1+Ne^{-\varepsilon/C})$ using constant size of hidden workspace, where $C$ depends only on $\Delta,r$ and the neighboring relation. Especially, for $r=2$, we have $C=1$, which indicates that the algorithm achieves the tight bound under all three relations. Finally, we consider repeated queries on the same graph, where the cost of protected preprocessing can be amortized across queries. For fixed $\Delta,r,\beta$, we construct a linear-size reusable index with $(\varepsilon,0)$-DO preprocessing and constant query cost. The expected preprocessing cost is linear in $N$ when $\varepsilon$ exceeds a sufficiently large constant multiple of $\log N$.