Imagine you're running a census of a city, but you can't actually visit anyone's house. Instead, each household independently garbles their own data before mailing it in — adding noise calibrated so no individual household's details leak. Your job is to reconstruct citywide statistics (how many three-person households share a car?) from these garbled reports. The harder question: can you prove nobody else could do it better? That's the structural problem this paper solves, except the "city" is a social network, the "households" are nodes, and the "statistics" are subgraph counts — triangles, 4-cliques, stars, cycles, any fixed pattern. The committed claim: for any constant-size template graph H on k nodes, the authors give a noninteractive (ε,0)-LNDP algorithm that counts copies of H in an n-node graph with additive error O(n^{k-1/2} / ε^{k-1}), and they prove a matching Ω(n^{k-1/2}) lower bound for any noninteractive algorithm when H has maximum degree > 1. This is a genuine first — the tight error characterization for general subgraph counting under local node privacy was open. Prior LNDP work (Imola, Kasiviswanathan, Murakami, and others) only handled functions of the degree distribution. Counting triangles or 4-cycles was out of reach. The ladder position matters. Under central node DP — where a trusted curator sees the full graph — subgraph counting is easier; the error can be polynomial factors smaller. This paper's lower bound yields the first known poly(n) gap between central and local node DP that holds for all input graphs, not just promise problems. Previous central-vs-local separations either involved only poly(1/ε) factors or required restricted input classes. That gap is a structural insight about the cost of distributing trust, not just an artifact of a particular algorithm. Architecturally, the algorithm lives in the randomized response / local randomizer family: each node independently perturbs its adjacency list, and a central aggregator computes an unbiased estimator of the subgraph count from these noisy reports. The key technical innovation is a careful combinatorial decomposition of the subgraph count into terms whose variance can be controlled after local perturbation. The lower bound uses information-theoretic arguments — fingerprinting-style reductions adapted to the node-private setting. No heavy computational machinery; this is combinatorics and probability, not optimization or learning. Integrity is strong for a theory paper. The results are mathematical proofs, not simulations. The upper bound is constructive (you can implement the algorithm), and the lower bound is unconditional — it applies to all noninteractive LNDP algorithms regardless of computational complexity. There's no cherry-picking of benchmarks because the results are worst-case over all n-node graphs. The only caveat: the poly(1/ε) gap between upper and lower bounds is acknowledged but left open. The practical milestone is closing that poly(1/ε) factor. Right now, the upper bound has ε^{-(k-1)} dependence while the lower bound is ε-independent. For triangles (k=3), that's a gap of 1/ε² — manageable for moderate ε but potentially painful at small ε. The next concrete target: either prove that the ε-dependence is necessary or shave it down. Beyond that, extending to interactive (multi-round) LNDP protocols could yield tighter bounds, since interaction sometimes helps in local models. The experiment not run: empirical evaluation on real social networks. This is pure theory — no implementation results, no runtime benchmarks, no comparison of practical noise levels on, say, a Facebook or Twitter subgraph. The honest read: this isn't compute-limited or hidden-negative-result territory. It's a theory paper accepted at SODA; empirical work is a different paper for a different venue. The open theoretical question — whether interaction helps — is the real successor, and it's likely being saved or is genuinely hard.
