Differentially Private Gomory-Hu Trees

Given an undirected, weighted n-vertex graph G = (V,E,w), a Gomory-Hu tree T is a weighted tree on V that preserves the Min-s-t-Cut between any pair of vertices s,t V. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is ε-DP, runs in polynomial time, and can be used to compute s-tcuts that are O(n/ε)-additive approximations of the Min-s-t-Cuts in Gfor all distinct s,t V with high probability. Our error bound is essentially optimal, since [29] showed that privately outputting a single Min-s-t-Cut requires Ω(n) additive error even with (ε,δ)-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-s-t-Cuts were O(n3/2/ε)for ε-DP [47] and O( mn/ε)for (ε,δ)-DP [66], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an ε-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle'bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.