BARC Talk by Jacob Imola
Counting Triangles in a Graph under Local Differential Privacy
Abstract:
Graph algorithms, such as computing how many friends of a user are also friends, are an important part of data mining that is of much practical and theoretical interest. There is by now a large literature on private graph algorithms, but most apply to central differential privacy, a model where a user trusts a central data aggregator with their data.
In this talk, we design private graph algorithms in the local model of differential privacy, where users simply apply private algorithms to their data without needing to trust a central aggregator. We outline three private algorithms for computing the number of triangles in a graph which trade between error, required communication, and rounds of interaction. We will then briefly address follow-up questions such as lower bounds, robustness to data poisoning, and more complex graph statistics.
