The Power of Interaction in Locally Edge-Private Subgraph Counting

We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph H with k vertices, ≥1 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 ε-LEDP algorithm with additive error and root mean square error both O(nk-3/2/ε⁾ on every n-vertex graph. For fixed sufficiently small ε, this improves the optimal noninteractive additive error for triangles by a factor of √ 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 (+2)-round ε-LEDP algorithm with additive error O(nq-1/2dk-q-1log³⁻²n/ε⁾. For connected patterns, its polynomial factor is √ n\,dᵏ⁻², 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.