Private testing of large graphs for key properties with few queries
Private Graph Property Testing
Data Structures and AlgorithmsCryptography and Security
Summary
Big graphs can have many connections, and checking if they have certain characteristics usually takes a lot of work. This paper studies how to check these properties by looking at only a small random part of the graph while protecting privacy. The authors created methods that keep the graph's details private but still test the properties efficiently. Their techniques work for common types of graphs and keep the number of checks needed similar to non-private methods.
What this means in practice
- •For data privacy engineers: Inspect large network data for structural properties without exposing sensitive connection details through sublinear queries with formal privacy guarantees.
- •For social network analysts: Efficiently test social network properties like bipartiteness or community structure while preserving user privacy by sampling small graph parts.
Authors
Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee, Sayantan Sen
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.