Fichtenberger team makes graph property testing private
TL;DR
- The paper bridges two long-separated fields: sublinear-query graph property testing and differential privacy by subsampling.
- New privacy amplification theorems cover induced subgraph sampling, random walks, and k-disc sampling.
- The authors prove every property of hyperfinite graphs is privately testable, with query costs comparable to non-private testers.
Four researchers (Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee, and Sayantan Sen) have posted a 46-page paper on arXiv showing that differentially private algorithms can test properties of massive graphs with query budgets comparable to their non-private counterparts.
The authors' framing: "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." Because testers only look at tiny random slices of the input, the authors argue the fit with differential privacy should be obvious: "they appear naturally compatible with differential privacy and privacy amplification by subsampling. Despite this, few results link these two fields."
The paper proves privacy amplification theorems for three sampling procedures (induced subgraph sampling, random walks, and k-disc sampling) and uses them to build a private canonical tester in the dense graph model, plus private bipartiteness and subgraph-freeness testers in both the dense and bounded-degree models. Using the new k-disc amplification, the authors prove that "every property of hyperfinite graphs is privately testable."
The abstract publishes no concrete query-complexity bounds and no experiments; the claim is only that the resulting complexities are "comparable to those of their non-private counterparts."
Shared on Bluesky by 2 AI experts
-
Congratulations to Abigail Gentle and her co-authors, Hendrik Fichtenberger, Tamalika Mukherjee and Sayantan Sen, on having their paper on Private Graph Property Testing accepted to #ITCS2027! arxiv.org/abs/2609.14394 A…
View on Bluesky →
Originally reported by arxiv.org
Read the original article →Original headline: Private Graph Property Testing