Differentially Private Gomory-Hu Trees

You introduced edge weight differential privacy in Appendix A.5, but in Appendix G you tried to draw an analogy between min s-t cuts and all pairs shortest path distances without mentioning that many existing works considered different privacy notions for these two problems. How are these two problems comparable?

These two problems are not directly related (i.e. as far as we are aware, results for one don't imply results for the other). Our goal was to contrast the progress on the private shortest path problem to the APMC problem (please see the next answer). Regarding privacy models, most works on the two problems use the same model of edge privacy, where two graphs are defined to be neighboring if they differ in one edge weight by at most one. Works on DP shortest paths also assume the graph topology is public (but the edge weights are private). In our setting, we do not need such assumptions.

Also, in line 1349-1350, you appear to be describing an obstacle in min s-t cuts. Why exactly is this an obstacle? In particular, for all pairs shortest path distances, even under edge weight differential privacy, the value set of the shortest path distances can also change in at least Omega(n) entries right? If these problems are somewhat comparable, then this shouldn't really be an obstacle?

The discussion on lines 1344-1350 is attempting to motivate a different version of our problem where we only ask to release the pairwise min s-t cut values, rather than the cuts themselves. In the DP shortest paths problem, there is a separation between these two versions, as sublinear error is possible for the value problem, but linear error is necessary to release an approximate shortest path. Thus, we are motivated to ask if such a separation also exists for min $st$ cuts. The lines starting from “One might wonder…” argue that the simple, but natural, algorithm of just computing pairwise min $st$ values and releasing a noisy version can have large errors since changing even one edge can impact $\Omega(n)$ min cut values. Please see lines 178-181 for further discussion. We are not arguing that achieving sublinear error for this values problem is impossible, rather we are hopeful that future work could make progress on this interesting open question.

Weaknesses: The algorithm is largely built on two previous works: the non-private Gomory-Hu tree algorithm by Li and the private s-t-min-cut query by Dalirrooyfard et al., with modifications to control the quality of some intermediate objects.

These two works are important to our paper, but we would point out that many DP papers follow the general strategy of carefully privatizing a known non-DP algorithm. In our case, beyond finding the right non-DP algorithm as a starting point and identifying the steps needed to make it private, we had to tackle several technical challenges, which we have highlighted in Section 2 and again below.

Two important examples are (1) ensuring the private min isolating cuts found are close to their non-private counterparts in terms of their weighted edge values and are simultaneously not 'too small' in cardinality and (2) ensuring that a single edge does not appear in many recursive calls of our private GH tree subroutine, even if the recursive depth is bounded.

These challenges are not relevant in the non-private setting, but require novel analysis for a DP algorithm. Furthermore, the Bounded-Overlap Branching Composition technique which we develop along the way may be of independent interest. We refer to Section 2.3-2.6 for further discussion.

Some technical details, especially for the privacy analysis, are not clear (will question later)

See the discussion below.

Algorithm 1 invokes the contraction sub-rountine multiple times. By its definition A1, the subroutine uses edges and edges' weights information. The privacy analysis of Algorithm 1, line 801-804, claims that only the min-cut uses the sensitive information, which is straightforward for the input graph G, but not directly for the last call. Can the author comments on the correctness of the privacy analysis, especially analyzing the sensitivity of H?

First, the sets $W_r$ are private since they are obtained from postprocessing the $\lg|R|$ privately computed min cuts $C_i$. Furthermore, the sets $W_r$ importantly form a partition of $V$. This implies that an edge in the initial graph contributes its weight to at most two edges in $\mathcal{H}$. Namely, an edge internal to some $W_r$ appears only in $H_r$ and an edge between some $W_r$ and $W_{r’}$ is only contracted into an edge in $H_r$ and an edge in $H_{r’}$. Thus, the sensitivity of $\mathcal{H}$ is 2, and running an $\epsilon$-DP algorithm on $\mathcal{H}$ is thus $2\epsilon$-DP with respect to the initial graph. It appears we have forgotten to incorporate this factor of 2 in our privacy analysis. Fortunately, it only affects our bounds by a constant factor, but we apologize for the confusion and will update the manuscript to address this. Thanks for pointing this out!

Similarly to Algorithm 4 and its privacy analyses on graph Gv and $G_{large}$.

The privacy analysis of Algorithm 4 is more complicated and requires our Bounded-Overlap Branching Composition Theorem D.2 to analyze the privacy loss through all recursive steps of the algorithm. We note (similar to the previous comment) that since the sets $\hat S_v$ are disjoint, any edge of the initial graph can contribute its weight to at most three of the sub-instances $G_v, v\in R$ and $G_{large}$. Moreover, in the language of Theorem D.2, it appears unsanitized in at most one of these subinstances, which turns out to be crucial to bound the privacy loss over all recursive steps of the algorithm. Bounding the number of times (sanitized and sensitive) edges appear in recursive sub-instances makes it possible to apply Theorem D.2 to our problem.

In Algorithm 2, what does "satisfying the conditions on Algorithm 2" mean?

We apologize for the typo. It should say “satisfying the conditions on Line 7 of Algorithm 2”, which is the following condition (stated in the description of Algorithm 2): $\hat{w}(\hat{S}{\_v}^i) \le \hat{\lambda}(s,v)+ (2 \lfloor \log_2 |U| \rfloor - i) + 1) \Gamma_{\text{iso}} + \Gamma_{\text{values}}$. We will update the manuscript to include algorithm lines and fix this typo.

In the composition theorem, can the authors specify the privacy model (wrt to the sensitive dataset and sanitized data),i.e., the neighborhood definition wrt the two types of data.

The theorem works generally for any replacement definition of neighboring datasets where the indices of the dataset (e.g., the $\binom{n}{2}$ edge weights) are public, but any given datapoint may be replaced with a different value. The key properties we require are that (a) the index set is public and (b) any neighboring datasets $X, X’$ differ at a single index. We will update the manuscript to clarify this.

Pure theory paper, may not be interesting to a large body of the NeurIPS community. Maybe it is helpful to use one or two sentences to discuss the applications of GH tree in machine learning.

Thank you for the feedback. Indeed, the main focus of our work is theoretical and gives nearly optimal private algorithms for releasing all pairs min $st$ cuts (with error comparable to the lower bound even for releasing a single cut). That said, there are applied works that use the computation of many min $st$ cuts, and thus their private version might benefit from our work (see, e.g., [1] and [2]). To give a specific example that is relevant to privacy, consider a social network, where each node represents a person and a weighted edge represents the strength of the relationship between two people. Edge-neighboring privacy corresponds to the case where the set of people are known, but we do not want to leak information about any specific friendship relation. Running multiple min $st$ cuts can help in community detection by detecting tightly-knit communities within a network by identifying weak links that separate different groups (see [2] for a non-private version of this example).

[1] Gary William Flake, Robert Endre Tarjan, and Kostas Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Math., 1(4):385–408, 2003.

[2] Hyungsik Shin, Jeryang Park, and Dongwoo Kang. A graph-cut-based approach to community detection in networks. Applied Sciences, 12(12), 2022.

In Line 47, neighbouring weighted graphs are defined as those that have total weights that differ by at most one and in a single edge. I am curious about the number one here. Why can't we scale the weight to make the difference arbitrarily large? Are there other reasonable neighbouring models for weighted graphs?

Thank you for the feedback. We discuss the choice of neighboring graphs in section A.5.

This is a great point to scale the weight and one can indeed define neighboring graphs to have total weight difference of say $\Delta$, which would result in the additive error also being scaled by $\Delta$. Thus, the “one” is a natural choice to use. This notion of DP is a standard generalization of unweighted edge-DP and has been widely used to study cut problems in graphs (see [1-5] for a small selection of such works).
Other reasonable DP models include changing an edge (of unbounded weight) or changing the entire neighborhood of a node. But these notions of privacy are too stringent and result in trivial solutions for cut problems. If the edge weights are arbitrary, as in our setting, removing a node or an edge can cause a cut value to go from any positive value to 0. This is a main reason why the literature on preserving cuts uses the edge weight definition, but it is an interesting future direction to explore other natural neighboring notions for weighted graphs.

[1] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, 2010.

[2] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauss transform itself preserves differential privacy. In FOCS, pages 410–419, 2012.

[3] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In SODA, pages 560–578, 2020.

[4] Mina Dalirrooyfard, Slobodan Mitrović, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. In NeurIPS, 2023.

[5] Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In SODA, pages 1019–1049, 2024.