arXiv preprint ·
Private Graph Property Testing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Fast Stencil Computations on a Single Arbitrarily Moving Interval
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.