ABSet: Harnessing Blowfish Privacy for Private Friend Recommendations

In this talk, we describe ABSet-DP (aka ABSet), a novel Blowfish-based framework that is currently being used in the Snapchat production friend recommendation system.

ABSet helps protect the privacy of the underlying social graph (e.g., the social connection between Alice and Bob should only be known to them). While traditional techniques like edge-DP are applicable, they can be infeasible for large graphs (e.g., O(10^8) nodes), or non-trivial to correctly implement.

ABSet has low computation cost and a high provable privacy bar. For each Snapchat user, friend suggestions come from multiple sources; for example, it considers users that are 2-hops and 3-hops away from the searcher in the friend graph. ABSet assumes a partition of sources into two sets: set A and set B, and applies a randomized swapping mechanism to the list of friend recommendations. It provides indistinguishability as to which source a recommendation is coming from, and thus limiting the friend graph leakage.

In general, ABSet considers two datasets as neighboring by differing one set label, and it allows flexible rules for the set assignment, therefore the mechanism design on top of ABSet is orthogonal to the semantic meaning of the set assignment. Following the Blowfish framework, ABSet's policy offers privacy semantics that are equivalent to edge-DP under certain practical assumptions.

Authors: Yuchao Tao and Ios Kotsogiannis