# The Power of Interaction in Locally Edge-Private Subgraph Counting

DevFeed: [The Power of Interaction in Locally Edge-Private Subgraph Counting](<https://devfeed.tech/articles/the-power-of-interaction-in-locally-edge-private-subgraph-counting-116162.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.05038>)

Author: Xian Chen, Pan Peng

Published: 2026-11-04T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [error](<https://devfeed.tech/tags/error.md>), [graph](<https://devfeed.tech/tags/graph.md>), [interaction](<https://devfeed.tech/tags/interaction.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [privacy](<https://devfeed.tech/tags/privacy.md>)

## AI overview

The paper studies counting copies of a fixed, non-induced pattern graph under local edge differential privacy. Its Linear Noise Cancellation (LNC) algorithm uses two rounds and achieves additive and root mean square error O(n^{k−3/2}/ε^ℓ) on arbitrary n-vertex graphs. At fixed sufficiently small privacy parameter, this improves the optimal noninteractive triangle additive error by √n and gives the same worst-case root mean square improvement for cliques with at least three vertices. For graphs with public maximum degree bound d, Predict and Correct (PC) uses ℓ+2 rounds and achieves additive error O(n^{q−1/2}d^{k−q−1} log^{3ℓ−2} n/ε^ℓ). For connected patterns, the polynomial factor is √n d^{k−2}, yielding sublinear error on constant-degree graphs at fixed privacy. The authors give matching lower bounds in n and d up to logarithmic factors at fixed privacy, including under arbitrary interaction and approximate privacy with sufficiently small δ; at d=Θ(n), the lower bound establishes LNC's optimal n-dependence.

## Source excerpt

arXiv:2611.05038v1 Announce Type: cross 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 $\delta$. At $d=\Theta(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.