CS Paper Radar

The Power of Interaction in Locally Edge-Private Subgraph Counting

Xian Chen, Pan Peng

cs.DS cs.CR ·submitted 2026-11-03 15:10 UTC · v1
theory

Abstract

We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.

Comment
64 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Subgraph Counting with Local Node Differential Privacy

cs.DS cs.CR ·2026-10-15 ·Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov
top venuetheory similarity 0.82
Abstract · To appear at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2027

We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\varepsilon)$ factors or only applied to promise problems.

0.32

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

cs.DS cs.CR ·2026-09-09 ·Jacob Imola, Rasmus Pagh, Lukas Retschmeier
top venuetheory similarity 0.70
Abstract · 32 pages, 3 figures. To appear at PODS 2027

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

0.60

Tight Bounds for Differentially Private Cut Release

cs.DS ·2026-11-14 ·Chenghua Liu, Boning Meng
theory similarity 0.69
Abstract · 24 pages

We give a polynomial-time algorithm for releasing a nonnegative weighted synthetic graph under $(\varepsilon,δ)$-edge differential privacy. Given an $n$-vertex nonnegative weighted graph $G=(V,w_G)$, the output $H=(V,w_H)$ satisfies, with probability at least $1-β$, simultaneously for every $S\subseteq V$, $|w_G(S,V\setminus S)-w_H(S,V\setminus S)| \leγw_G(S,V\setminus S)+O\bigl((n\log n)/(\varepsilonγ)\bigr)$, provided that $γ,\varepsilon,δ,β$ are at least inverse polynomial in $n$. For constant $γ,\varepsilon$ and $δ=β=n^{-10}$, this improves the recently obtained additive error bound of $O(n\log^7 n)$ to $O(n\log n)$. We also prove a matching $Ω(n\log n)$ lower bound. Our algorithm combines degree decomposition with private multiplicative weights, using a degree-sensitive semidefinite oracle to generate update proposals from single Gaussian samples. Each proposal is validated by a noisy check of its exact entropy decrease, and a joint Rényi analysis of sampling and validation avoids additional logarithmic losses.

0.06

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.68
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10

Private Graph Property Testing

cs.DS cs.CR ·2026-09-13 ·Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee, Sayantan Sen
theoryhot direction similarity 0.66
Abstract · 46 pages

Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property testers typically inspect only a small, randomly sampled portion of the input, they appear naturally compatible with differential privacy and privacy amplification by subsampling. Despite this, few results link these two fields. We initiate a systematic study of differentially private graph property testing with the goal of designing efficient testers with formal privacy guarantees in the dense and bounded-degree graph models. We develop new privacy amplification theorems for several widely used graph-sampling procedures such as induced subgraph sampling, random walks and k-disc sampling. We then leverage these privacy amplification techniques to design a private canonical tester in the dense graph model, as well as private bipartiteness testers and subgraph freeness testers in the dense and bounded-degree graph models. Finally, using the new privacy amplification theorem for k-disc sampling, we prove that every property of hyperfinite graphs is privately testable. The resulting query complexities of our private testers are comparable to those of their non-private counterparts.

0.30

Improved polynomial-time algorithms for detecting and recovering planted $Θ(\sqrt{n})$-cliques

cs.DS math.ST ·2026-09-21 ·Dmitriy Kunisky, Songtao Mao
similarity 0.65
Abstract · 77 pages

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected graphs of treewidth at most $t$, cliques of size $k = λ\sqrt{n}$ planted in a random location with $λ> 1 / \sqrt{c(t)}$ can be detected and recovered in time $n^{t + 1 + o(1)}$. For instance, since $c(1) = e$, this recovers by counting signed trees the performance of the $\widetilde{O}(n^2)$-time message-passing algorithm of Deshpande--Montanari (2015) that succeeds when $λ> 1 / \sqrt{e} \approx 0.6066$. For $t \geq 3$, the exact value of $c(t)$ is not known, but lower bounds on it give a hierarchy of slower polynomial-time algorithms that succeed for smaller $λ$. We further show that the above algorithm for $t = 2$ can be implemented in time $n^{ω+ o(1)}$ for $ω$ the constant of square matrix multiplication and succeeds when $λ> 0.3320$; under the folklore conjecture that $ω= 2$, this runs in the nearly-linear time of the algorithm of Deshpande--Montanari while finding smaller cliques. Second, we show that the above algorithm for $t = 1$ can be combined with the boosting scheme of Alon--Krivelevich--Sudakov (1998) using rectangular matrix multiplication, giving improved runtimes for smaller $λ$. Taken together, our results achieve the best known tradeoff between runtime and signal strength $λ$.

0.27

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.65
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

Introvert Clustering for Distributed Graph Algorithms

cs.DC cs.DS ·2026-09-09 ·Yi-Jun Chang, Nima Dolatabadi
similarity 0.64
Abstract

We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at least a $\left(\frac12-\varepsilon\right)$-fraction of its relevant neighbors in its own cluster. Repeatedly applying this primitive yields a layered introvert network decomposition with $O(\log n)$ layers and weak diameter $O(\log n)$. We give two applications in the $\mathsf{LOCAL}$ model. For every constant $\varepsilon>0$, we obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for list $\left(\frac32+\varepsilon\right)Δ$-edge coloring on graphs of maximum degree $Δ\geqΔ_0(\varepsilon)$; for bipartite graphs, the result holds for all $Δ$. For every constant $0<\varepsilon<1/4$, we also obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for a $\left(\frac14-\varepsilon\right)$-locally balanced cut, where every vertex has at least a $\left(\frac14-\varepsilon\right)$-fraction of its neighbors on the opposite side. The resulting algorithms are remarkably simple: edge coloring processes the layers in reverse order and colors each cluster, while locally balanced cut processes them forward and computes a locally maximum cut within each cluster. The introvert guarantee enables these procedures beyond the usual greedy regime of network decomposition. We construct the decomposition in $O(\log^2 n)$ randomized rounds using Miller--Peng--Xu low-diameter clustering and a simple trimming procedure, and deterministically in $\widetilde O(\log^2 n)$ rounds via a white-box adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [FOCS 2024].

0.26