acceptodds
Under review as a conference paper at ICLR 2027

The Power of Input Perturbation: Differentially Private Learning from Pairwise Distances

Abstract

Differential privacy (DP) has been extensively studied for metric learning problems within specific geometric contexts, such as Euclidean space. However, in many applications, the input metric is available only as a matrix of pairwise distances. This paper systematically investigates the power of *input perturbation* for pairwise distances in general metric spaces under the -distance-based DP model. The approach is remarkably simple: we add independent Gaussian noise to the pairwise distance entries, optionally repair the matrix to the nearest metric, and release the matrix for downstream tasks. This mechanism offers significant practical utility, as a single privatized distance matrix can be reused across various downstream applications. Despite this simplicity, we prove that this method achieves a nearly tight additive error for -DP metric release. We further apply this approach to a host of metric learning tasks, including minimum spanning trees (MST), -clustering, hierarchical clustering (HC), and coresets, leading to bounds that are either tight or match the state-of-the-art. Experiments on 12 datasets demonstrate the advantages of this approach in terms of utility and time complexity compared to existing benchmarks. The experiments also reveal error-efficiency trade-offs via different metric repair strategies for practical private metric release.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Metric Release, k-clustering, Minimum Spanning Tree, Hierarchical Clustering, Coresets

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_yYAYOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the following problem: given a pair-wise distance matrix between the elements of a dataset, privately release all pairwise distances. Privacy follows the DP definition but introduces a ρ-neighrbor relation, such that the adjacent datasets have identical elements apart from one point that may change by at most ρ.

To do this, the paper proposes a simple approach: add Gaussian noise to each pair-wise distance, project the result into a pseudometric space (if necessary) and release the result. The paper shows that this achieves an optimal (up to logarithmic factors) error bound. Then it discusses applications in MSTs and clustering. Finally, it experimentally evaluates the additive error, the cost of projection and compares to Zou et al. for MSTs.

Critical strengths
  • Optimal Solution: The paper provides an optimal yet simple solution for the difficult problem of releasing the pair-wise distance metric. In other words, if one wishes to release all distances, the Gaussian mechanism is the natural and optimal approach. Moreover, the paper generalizes on any distance metric, instead of focusing on particular metrics as prior works.

  • Multiple instantiations: The paper discusses possible use cases (MSTs and clustering; with interesting lower/upper bound analysis) and provides different approaches with varying accuracy-privacy-running time trade-offs (Table 1).

  • Ablation on projection mechanisms: The paper evaluates with different projection mechanisms giving insights on which one is preferable.

Critical weaknesses
  • Limited Scalability: Modern ML applications require vast datasets. The proposed mechanism does not scale well as nn, the size of the dataset increases. For example: (a) the noise scales with (n)\sqrt(n), (b) Exponential complexity in some use cases, (c) faster (still polynomial) mechanisms degrade the acurarcy-privacy trade-off as nn increases (e.g. k-median recursive). I understand the difficulty of the problem but for an ML conference I find practically for ML tasks particularly important.

  • Limited novelty of the mechanism: The proposed mechanism is not novel: the paper combines the known Gaussian mechanism and largely known projections to pseudometric spaces. The main contribution lies on the theoretical side: the generalization of results to any metric space.

  • Insufficient evaluation: Evaluation focuses on small datasets and considers a single other work to compare against.

Questions for authors

Questions:

  • Does your mechanism scale well for modern ML tasks with increased nn? If not, how (e.g. heuristics, approximations) can it be applied to larger datasets and with what cost in accuracy/privacy? Show running time, accuracy and privacy with the full MNIST/CIFAR-10 datasets.

  • How does your mechanism compare to Zou et al. with varying nn (instead of dd)?

  • Evaluate on other metrics against related work. For example, you can instantiate on different metrics and compare against "Perturb-and-Project: Differentially Private Similarities and Marginals" of V. Cohen et al. or "Optimal bounds for private mini-mum spanning trees via input perturbation" of Pagh et al.

  • The number of noise seeds is small: increase the number of seeds and report +- std.

Suggestions for future work/improvements:

  • To gain space, I would keep lines 434-437 and refer to Table 3 (placed in the Appendix) as justification. Table 3 evaluates different (known) design choices for the proposed instantiation.

  • Line 410: You have already assumed in Prop 2.1. and Theorem 1 that ε≤1\varepsilon \leq 1. Thus experiments with larger ε\varepsilon offer limited value as they do not match the theory.

3 comments

We thank the reviewer for the careful review and helpful comments. We address the theoretical and presentation questions below and report the experiments in a separate response.

Limited scalability (weakness and Q1)

We agree that an O(n)O(\sqrt{n}) entrywise error becomes large for very large datasets. However, as the reviewer also notes, this rate is optimal if one wishes to release all pairwise distances by Theorem 2. The same is true for the downstream tasks, where our upper bounds are matched by lower bounds that also grow with nn (Table 1). In this sense, the dependence on nn comes from the privacy model, which cannot be treated as a weakness of our algorithms.

Regarding running time, we agree that the kk-clustering algorithms based on exhaustive search take exponential time. We include them to show that input perturbation can achieve the tight bounds. For practical use, we also provide polynomial-time algorithms based on recursive metric compression (Table 1). Their additive error carries an extra nηn^{\eta} factor for any fixed 0<η<1/20 < \eta < 1/2, at the cost of a larger constant approximation factor. We note that some growth in nn is unavoidable here as well, by our lower bound.

Limited novelty of the mechanism

We agree that the mechanism itself is not new, and we do not claim novelty for it. Our main contribution is the versatility: we show that one simple mechanism is already near-optimal for a range of problems on general metrics.

Establishing this requires a separate analysis for each problem. For the upper bounds, we need to control how the noise propagates through each post-processing step, e.g., through metric repair, or through the hierarchical clustering objective, where we use the fact that every tree has the same score on a unit-weight metric.

For the lower bounds, each problem requires its own hard instance, e.g., the two-star construction for MST and the planted structures for hierarchical clustering. These arguments build on standard tools, but we believe that adapting them to each problem is not trivial, and that the resulting near-tight picture is a useful contribution.

Suggestions

We thank the reviewer for the presentation suggestion and will consider moving Table 3 to the appendix while keeping the discussion in Lines 434–437.

For ε>1\varepsilon>1, our experiments use the analytic Gaussian calibration of Balle and Wang (ICML'18), which remains valid in this regime. We will clarify its distinction from the ε≤1\varepsilon\leq1 assumption in our stated bounds.

We report the additional experiments and address the evaluation questions below.

Experiments (Weakness and Q1)

The main computational cost in the image experiments is constructing the input distance matrix: each pair requires solving an optimal transport problem for the Wasserstein-1 distance. This cost also applies to non-private methods using the same input. To demonstrate this, we evaluated CIFAR-10 subsets with n=2,000,5,000,10,000n=2{,}000,5{,}000,10{,}000, with ε=1\varepsilon=1, δ=10−4\delta=10^{-4}, and three noise seeds.

All times below are in seconds. The noise column averages perturbation times across both methods and three seeds; MDS and Fréchet report mean repair times.

nnPairsW₁ constructionGaussian noiseMDSFréchet
2,0001,999,00057.4590.0341.1160.406
5,00012,497,500424.5700.19829.61319.528
10,00049,995,0001,613.1530.863243.513160.211

At n=10,000n=10{,}000, nearly 50 million optimal transport computations take 1,613 seconds, versus less than one second for Gaussian perturbation and 244/160 seconds for MDS/Fréchet repair. Distance construction accounts for 87%/91% of the respective totals.

These results show that, once the distance matrix is available, the privacy step adds little computational overhead and is scalable. In fact, to our best knowledge, input perturbation is the most efficient mechanism in DP (comparing to exponential mechanism, DP-SGC, private multiplicative weight, etc.)

Comparison with Zou et al. for varying nn and Pagh et al. (Q2, Q3)

We originally fixed n=500n=500 and varied dd because Zou et al.'s accuracy depends on dd through the JL projection, whereas ours does not. We have now added a comparison varying nn, using Zou et al.'s Euclidean generator with d=1,000d=1{,}000, ε=1\varepsilon=1, δ=10−4\delta=10^{-4}, and ρ=1\rho=1. We also compare with Pagh et al. as suggested. The table reports mean additive error over the exact original MST, with standard deviations across five repetitions.

nnOurs: No repairZou et al.Pagh et al.
100979.4 ± 35.62,302.1 ± 225.42,396.6 ± 286.1
3004,635.7 ± 152.46,454.6 ± 299.57,057.0 ± 381.5
5007,283.9 ± 204.612,447.6 ± 1,018.012,700.2 ± 339.9
70015,559.7 ± 617.319,952.7 ± 1,377.923,113.8 ± 516.9
1,00021,247.4 ± 526.426,734.2 ± 1,038.331,139.5 ± 1,798.9

Our "No repair" variant (Gaussian perturbation followed by Kruskal) achieves lower mean excess tree weight than both baselines at every tested size. At n=1,000n=1{,}000, the reductions are 20.5% relative to Zou et al. and 31.8% relative to Pagh et al. The mean running times at n=1,000n=1{,}000 were 0.064, 0.079, and 0.070 seconds, respectively for three methods.

Number of noise seeds

In the paper we already use three noise seeds and five repetitions, we will add the standard deviation. The above results are also obtained via the same setting.

Dear reviewer, As the author–reviewer discussion period ends today, we would appreciate hearing whether our response addresses your concerns. Thank you!

Reviewer_57X9OpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper studies a sequence of geometric problems (Minimum Spanning Tree (MST), hierarchical clustering, coresets, k-clustering etc) under the constraints of ρ\rho-distance differential privacy in a metric DP setting. Concretely, we are given as input a private metric space, i.e. some nn public labels and private pairwise distances, and under the constraint that any change of up to ρ\rho in the n−1n-1 pairwise distances of a single point should lead to ε\varepsilon-indistinguishable outcomes, the goal is to solve the problems mentioned.

This paper has two main theoretical contributions:

  1. A result showing that private preprocessing of the distance matrix via the Gaussian mechanism followed by application of non-private algorithms suffices to achieve provable error bounds.
  2. A lower bound demonstrating that in this setting, this approach achieves near-optimal additive error for releasing a pseudometric, and also for solving the geometric problems considered here.

They also show a lower bound specifically for private MST, which is also shown by Zou et al. Further, the authors conduct experiment to evaluate their results in practice on a number of datasets.

Critical strengths

I think the ρ\rho-dist DP model deserves more study, and this paper takes a step in that direction.

Critical weaknesses

I think this formulation of the problem is potentially not well-posed. Notice how the upper and lower bounds incur factors of n\sqrt{n} in the additive error. This is a very large amount of error to incur in the central model of DP. This seems to be happening because of the formulation itself - a single point may be changed in pairwise distance by a value of ρ\rho separately with respect to its n−1n-1 many pairwise distances. This would happen for instance if a point were allowed to move by ρ\rho units in ℓ∞\ell_\infty distance. It also seems very close to the local model of DP, if ρ\rho were a constant, and this also explains why the algorithm is so simple - it adds Gaussian noise separately to each of the pairwise distances, at a scale of n\sqrt{n}. It is not clear when one would work with such a model with this ℓ∞\ell_\infty geometry, and not just do local DP, given the magnitude of error incurred.

The experiments are also problematic. The first experiment compares the performance of different sorts of post-processing/repair on the privatized distance matrix to construct a pseudo-metric with a goal of testing which is best; this would be interesting. This is fine, but does not give us any way to evaluate the quality of this method compared to for instance a data-oblivious random pseudometric (for a baseline, at the very least). The second experiments compares the performance for private MST of their work with that of Zou et al. The problem here is that n=500n = 500 is kept fixed here, so we cannot really tell what the trends are, and whether this work dominates for other values of nn.

Finally, there doesn't seem to be much technical novelty here. The main algorithm is simply a direct application of the Gaussian mechanism. The lower bounds for this model are good to see, but the particular model itself needs more motivation I feel.

Questions for authors
  1. Can you explain why you picked this particular ℓinfty\ell_infty-metric formulation for these private geometric problems? Are there any practical settings where you would formulate them in this way?

  2. Are there any points of novelty or theoretical interest which you feel I have missed?

4 comments

We thank the reviewer for the careful review and the thoughtful questions. We believe that there might be some misunderstanding between the reviewer’s comments and our paper, and we would like to clarify them below. We will also improve the presentation of the model and its motivation in the final version.

Is the formulation well-posed? (Weakness and Q1)

Our privacy model is not new. It extends the distance-based privacy notion of Epasto, Mirrokni, Narayanan, and Zhong (NeurIPS'23), which protects movements of one point within radius ρ\rho, to settings where only pairwise distances are available. Their motivating applications include location data (where uncertainty of a few miles protects an individual) and smart-meter data. Zou, Epasto, Fan, and Das (AISTATS'26) later used the same notion for Euclidean MST. By the triangle inequality, moving one point by at most ρ\rho changes each of its n−1n-1 distances by at most ρ\rho. Conversely, any two ρ\rho-neighboring distance matrices can be realized by moving a single point by at most ρ\rho within a common pseudometric. So the fact that all distances of one point may change simultaneously is not an artifact of ℓ∞\ell_\infty geometry: it is exactly what moving a point does in any metric space.

Regarding the magnitude of the error, we note two points. First, it is measured in units of ρ\rho, intended to be small relative to the data scale. Under standard DP, where a point can be replaced arbitrarily, the additive error instead depends on the diameter of the data, which is precisely what distance-based privacy was introduced to avoid. Second, polynomial dependence on nn is unavoidable even in the central model. Theorem 2 gives an Ω(ρn/ε)\Omega(\rho\sqrt{n}/\varepsilon) maximum entrywise error lower bound for every (ε,δ)(\varepsilon,\delta)-DP algorithm on some input, and Table 1 gives matching downstream lower bounds. Zou et al. (AISTATS'26) also establish an Ω(n1.5)\Omega(n^{1.5}) MST lower bound for general graphs, contrasting with the Euclidean case. This dependence reflects the cost of having only distances rather than coordinates. We also note that additive errors polynomial in nn are common in well-studied problems in central DP, e.g., the Ω(n)\Omega(n) lower bound for private min ss-tt cut (Dalirrooyfard, Mitrović, and Nevmyvaka, NeurIPS'23), the O~(n/ε)\tilde{O}(n/\varepsilon) bound for private Gomory–Hu trees (Aamand et al., 2024), the Θ~(n1.5)\tilde{\Theta}(n^{1.5}) bounds for private MST (Pagh, Retschmeier, Wu, and Zhang, PODS'25), and O~(n)\tilde{O}(\sqrt{n}) additive error for outputting all-pairs min-cut values (Aamand, Chen, Dalirrooyfard, Mitrović, Silwal, and Xu, arxiv:2611.08650). We view a large worst-case error as a property of the problem that is worth understanding, and our near-tight bounds characterize it precisely.

Relation to local DP (Weakness)

We would like to clarify that all of our upper and lower bounds results are in the central model, where a trusted curator holds the full distance matrix. We agree with the reviewer's observation that our mechanism is very simple: it adds independent noise to each distance, and in that sense it resembles a local randomizer. However, our lower bounds show that this simplicity is not what causes the error. Even a central algorithm that sees the entire matrix cannot do asymptotically better (Theorem 2 and Table 1). Since local DP is a stronger requirement than central DP, any local algorithm would incur at least as much error. In other words, one of our main messages is that, for most of the problems we study, the central model offers no asymptotic advantage over simply adding noise to the input. We will make this point explicit in the revision.

Why this ℓ∞\ell_\infty formulation? (Q1)

The ℓ∞\ell_\infty notion appears in two places in our paper, and we will separate them more clearly in the revision. The first is the neighboring relation, which, as explained above, is the distance-matrix form of moving one point by at most ρ\rho. The second is the error measure, the maximum entrywise error of the released matrix. We use the entrywise guarantee because it is the strongest per-distance guarantee and it transfers directly to downstream tasks: an objective whose value changes by a bounded amount when each distance changes by at most η\eta inherits a correspondingly bounded error. This is how a single private release yields near-tight bounds for MST, single-linkage clustering, hierarchical clustering, kk-clustering, and coresets.

As for practical settings, the formulation is natural whenever the data are accessible only through a distance function and coordinates are unavailable or not meaningful. Examples include shortest-path distances in social networks, edit distances between protein sequences, and Wasserstein or Hausdorff distances between images and shapes. These are the settings of our experiments (Table 2).

Experiments (Weakness)

We would appreciate a clarification of the baseline the reviewer has in mind. If the reviewer means, e.g. always releasing a fixed pseudometric, it satisfies privacy trivially, but contains no information about the input geometry. Such a baseline may achieve small entrywise error when distances concentrate, without identifying which pairs are close.

Beyond the repair methods analyzed in our theory, we also evaluate three heuristics (SP-Closure, MDS, and Fréchet). To our knowledge, no prior method addresses private release of general non-Euclidean metrics under this privacy model.

Regarding the fixed n=500n=500 in the original MST experiment: Zou et al.’s accuracy depends on d through the JL projection, whereas ours does not. We therefore varied d to show this effect. We agree that varying n is also informative, and have added a comparison with Zou et al. and Pagh et al. using Zou et al.’s Euclidean generator with d=1000d=1000, ε=1\varepsilon=1, $\delta=10^{-4}$, and ρ=1\rho=1. The table reports mean excess tree weight over the exact original MST, with standard deviations across five repetitions; lower is better.

nOurs: Gaussian + Kruskal (No repair)Zou et al.Pagh et al.
100979.4 ± 35.62,302.1 ± 225.42,396.6 ± 286.1
3004,635.7 ± 152.46,454.6 ± 299.57,057.0 ± 381.5
5007,283.9 ± 204.612,447.6 ± 1,018.012,700.2 ± 339.9
70015,559.7 ± 617.319,952.7 ± 1,377.923,113.8 ± 516.9
1,00021,247.4 ± 526.426,734.2 ± 1,038.331,139.5 ± 1,798.9

Our “No repair” variant achieves lower mean excess tree weight than both baselines at every tested size. At n=1,000, the reductions are 20.5% relative to Zou et al. and 31.8% relative to Pagh et al.

Technical novelty (Weakness and Q2)

We agree that our algorithm is simple, and we see this as a strength rather than a weakness. We do not claim novelty for the mechanism itself. The main technical contributions lie in the analysis, which we summarize here in response to Q2. First, we give nearly tight bounds for private release of general metrics under this model, including a lower bound via a reduction from 1-way marginals. Second, we show that post-processing this single release gives near-tight bounds for MST, single-linkage merge heights, and the hierarchical clustering dissimilarity objective, and tight bounds for kk-clustering with constant kk. Each of these requires its own analysis of how the noise propagates through the post-processing step, and its own hard instance for the lower bound (e.g., the two-star construction for MST and planted structures for hierarchical clustering). Third, we give polynomial-time kk-clustering algorithms via recursive metric compression and a private coreset construction. These arguments build on standard tools, but adapting them to each problem is not automatic. Taken together, they show that in this model, simple input perturbation is essentially the best one can do for a wide range of problems, which we believe is a useful message for the community.

We thank the reviewer again, and we hope these clarifications help.

Reviewer_57X9OpenReview ↗

Response

Thank you very much for your detailed response!

Regarding the model setting, I should have clarified, I don't have an issue with metric DP, but rather this setting in which one only sees pair-wise distances, and yet one is operating in the central model. I understand better now that this problem is indeed well-posed and well-motivated - the use of ℓ∞\ell_\infty to measure neighborhood distance now makes sense to me as well. However, I think the lower bounds and the large amount of error incurred seems to imply that perhaps one cannot solve this problem well in this setting. I see that a sufficiently small value of ρ\rho would justify this, but then I think one needs to demonstrate that for some privacy attack of interest, there exist values of ρ\rho such that one achieves both good privacy and good accuracy. Otherwise, in some sense this line of investigation perhaps shows that it is not possible to achieve non-trivial accuracy-privacy trade-offs.

Thank you for conducting more experiments! Regarding the baseline, yes, that is the construction I had in mind. One could construct a random MST, or a random allocation of kk-centers, and measure the error - this would establish a default floor. I see that Pagh et al. work in a more restrictive privacy setting since they allow all matrix entries to vary in sup norm between neighboring matrices. However, I think it is clear that for the notion of neighborhood you consider, you get less error than prior work for MST. I think the random baseline is important though since it gives a more concrete measure of how much improvement these DP algorithms are getting. I would also suggest including the utility of a non-private method as a ceiling.

I am increasing my score to a 2 - I still think more work needs to be done, especially the question of whether solving this problem under metric DP gives useful solutions in practical settings that one cares about (by showing that good values of ρ\rho exist, like mentioned above). Another path might be to go beyond minimax optimality and get lower error for some reasonable notion of instance-optimality. Alternatively, there could be some other argument demonstrating why solving these problems in this model is interesting from a theoretical perspective. I would agree that the simplicity of the method is a strength, not a weakness, but I think one needs to establish more impact beyond meeting minimax lower bounds since the model is rather harsh.

We thank the reviewer for the feedback. We are glad that the motivation for the model and the neighboring relation are now clearer. We are also grateful that the reviewer points out the importance of showing that good values of ρ\rho exist. We add two experiments in response.

Can one choose ρ\rho to achieve both privacy against a concrete attack and useful accuracy?

We study MST on NYC taxi pickups. The attack is to identify one passenger's pickup location. The attacker knows the other 99 locations and two equally likely candidate locations for this passenger, at most 100 meters apart. After seeing the full noisy matrix, the attacker guesses which candidate was the actual pickup.

We choose ρ\rho from the privacy goal before measuring utility. At ε=1\varepsilon=1 and δ=10−4\delta=10^{-4}, our Gaussian calibration ensures that with ρ=125\rho=125 meters, even the optimal attacker succeeds with probability at most 55% for any such pair. Random guessing succeeds with probability 50%.

We tested five groups of 100 pickups from the 2015 NYC Yellow Taxi data, using the same 251 candidate pairs (50–100 meters apart) at each ρ\rho. We report the highest optimal attack success probability across these pairs and mean tree lengths in kilometers. Private tree lengths are averaged over five noise seeds, and the random baseline is the expected length of a uniformly random spanning tree.

ρ\rhoMax. attack successNon-private MST (km)Gaussian + Kruskal (km)Random tree (km)
100 m55.61%60.2185.9441.8
125 m54.49%60.2205.8441.8
150 m53.75%60.2224.7441.8
200 m52.81%60.2250.7441.8

We hope this illustrates how one can choose ρ\rho for a specific privacy goal and still retain useful information for MST.

Random baseline and non-private comparison

Following the reviewer's suggestion, we also added both comparisons on the six datasets used in our downstream evaluation. We score every tree on the original distances. Each edge belongs to a uniformly random spanning tree with probability 2/n2/n, so we can compute its expected weight exactly. The private column gives the mean over three noise seeds.

DatasetNon-private MSTGaussian + KruskalRandom tree (expected)
MNIST19.7649.6557.11
CIFAR-1062.00109.03123.80
ModelNet10136.71268.36299.74
Characters19.1882.53132.86
Mushroom1,444.009,983.3311,489.74
Email985.002,439.002,548.13

We hope these comparisons clarify how much the private tree improves on a random tree and how close it comes to the non-private optimum. We will include them in the revision.

Reviewer_3cfVOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies differentially private release of general metric spaces where data is represented solely as an n×nn \times n matrix of pairwise distances, instead of through geometric coordinates or ambient space embeddings. The authors adopt the distance-based differential privacy model (ρ\rho-distance DP) from Epasto et al., where two metric matrices are defined as ρ\rho-neighbors if they differ only in the entries associated with a single data point, with each of its pairwise distances changing by at most ρ\rho. Under this formulation, the paper explores the paradigm of input perturbation, specifically, adding independent Gaussian noise to the pairwise distance matrix and optionally projecting the result back onto the cone of valid pseudometrics, and evaluates whether applying standard, non-private optimization algorithms as post-processing can yield optimal or near-optimal privacy-utility trade-offs across several fundamental metric optimization tasks. The starting point of this paper is private metric release. The authors show that calibrating Gaussian noise to the matrix's ℓ2\ell_2-sensitivity of Δ2≤ρn−1\Delta_2 \le \rho \sqrt{n-1} provides (ϵ,δ)(\epsilon, \delta)-DP with a maximum entry-wise error of O~(ρnlog⁡(1/δ)ϵ)\tilde{O}(\frac{\rho \sqrt{n \log(1/\delta)}}{\epsilon}), and an ℓ∞\ell_\infty projection (metric repair) preserves this error guarantee due to contractive properties over the pseudometric cone. This upper bound is shown to be tight up to logarithmic terms via an Ω(ρnϵ)\Omega(\frac{\rho \sqrt{n}}{\epsilon}) lower bound reduced from answering 1-way marginals using fingerprinting codes.

The authors also study a lot of downstream tasks, running Kruskal's algorithm directly on the perturbed distances without metric repair achieves an additive error of O~(ρn3/2ϵ)\tilde{O}(\frac{\rho n^{3/2}}{\epsilon}) for the minimum spanning tree (MST) problem, matching a self-contained double-star lower bound. For metric kk-clustering, the paper addresses the challenge of distorted medoids on noisy distances by introducing an intra-cluster average distance surrogate QzQ_z, which approximates the true clustering objective within constant factors.

The authors further extend this framework to hierarchical clustering and coresets. Under single-linkage agglomerative clustering, the private merge height error is bounded by O~(ρnϵ)\tilde{O}(\frac{\rho \sqrt{n}}{\epsilon}), matching a corresponding lower bound. For the hierarchical clustering dissimilarity maximization objective, input perturbation attains an additive error of O~(ρn3ϵ)\tilde{O}(\frac{\rho n^3}{\epsilon}), which is shown to be nearly tight through an Ω(ρn3ϵ)\Omega(\frac{\rho n^3}{\epsilon}) lower bound that exploits Dasgupta’s combinatorial score invariance on complete graphs to cancel out internal tree topologies.

Critical strengths

I feel this paper is generally very well written and easy to follow, presenting its ideas clearly. I think it is particularly important given that AI is now producing slop everywhere. The paper studies private distance problems and establishes tight upper and lower bounds for private estimation of many important graph problems, including hierarchical clustering, coresets, and k-clustering.

Though the techniques are simple, it is good to learn that a simple mechanism like input perturbation is already asymptotically optimal for a wide range of graph tasks.

The authors also conduct an extensive set of experiments, validating the power of simple input perturbation mechanisms.

Critical weaknesses
  1. The upper bound construction might be a little bit straightforward, so the technical depth on the upper bound side is not particularly impressive, but I think it is fine: simple does not mean bad.
  2. I feel the upper bound for private MST might be somewhat incremental (see my questions for details).
Questions for authors

The minimum spanning tree result you claim in the paper is \rho n^{1.5}; I might be wrong, but I feel this result is somehow implied in Pagh et al. (2025). In particular, they also use input perturbation for minimum spanning tree, and give n^{1.5} purely additive error under ℓ∞\ell_{\infty} neighboring, i.e., all edges could change by at most one in the neighboring graph; while it seems that your Definition 1.1 is exactly the same notion if we define the distance as the weight of the direct edge between u and v.

In this sense, I am also wondering: is there a particular reason that you claim (Hladík & Tetek, 2025) uses "a different neighboring notion"? (on line 296-297) Because they also use the ℓ∞\ell_{\infty} notion, and again it seems the same as your Definition 1.1 in the graph setting.

Another question, just out of curiosity: do you ever consider pure-DP (e.g., adding symmetric Laplace noise to each entry) and see if there is any separation? I assume for general distance matrix release it has to be Θ(n) error, so not very interesting, but it would be very interesting to see if there is a separation between pure and approximate DP for many downstream graph tasks.

Pagh et al. (2025): Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation. Proceedings of the ACM on Management of Data

2 comments

We thank the reviewer for the careful review and the positive assessment. Our responses to the weaknesses and questions are below.

Technical depth (weakness)

We agree with the reviewer that most of the upper and lower bounds in the paper are obtained via variants of standard techniques. As the reviewer points out, however, simplicity does not imply weakness. Moreover, we believe the main strength of our paper lies in the versatility of the approach.

Novelty of the MST result (question)

We thank the reviewer for the catch. We agree that the ℓ∞\ell_\infty-neighboring privacy models of Pagh, Retschmeier, Wu, and Zhang (PODS'25) and Hladík & Tětek (FORC'25) are stronger than ours. As a result, any algorithm that is private in their model is also private in ours: we can simply construct a complete graph whose edge weights are the distances, any two ρ\rho-neighboring distance matrices yield graphs whose edge weights differ by at most ρ\rho on every edge, i.e., neighbors in their model.

We initially overlooked this because these papers use a graph formulation, while we work with metric spaces. As we already point out in the paper, a similar MST upper bound was presented by Zou, Epasto, Fan, and Das (AISTATS'26) for Euclidean space, and we do not claim the MST upper bound as novel. Instead, we use it as an example of the versatility of our approach.

On the other hand, since their privacy models are stronger, a lower bound in their setting does not imply a lower bound in ours. Nonetheless, the construction in Zou, Epasto, Fan, and Das (AISTATS'26) can be adapted to give the same lower bound in our setting, and our contribution here is a self-contained proof with a slightly different construction.

We will revise the discussion accordingly in the final version. We thank the reviewer again for the great catch.

Pure DP in our model (question)

The input perturbation framework also supports pure DP, but it is not clear to us whether pure DP can be achieved while keeping the error small. As the reviewer points out, adding Laplace noise to each entry leads to Θ~(n)\tilde{\Theta}(n) additive error if we want high-probability bounds. We can also establish a separation for MST itself. For 0<ε≤10<\varepsilon\le1 and sufficiently large nn, every pure ε\varepsilon-DP algorithm incurs expected additive error Ω(ρn2/ε)\Omega(\rho n^2/\varepsilon) on the same two-star metric construction in this paper. The punchline is packing argument based on group privacy. Together with our approximate-DP upper bound of O~(ρn3/2/ε)\widetilde{O}(\rho n^{3/2}/\varepsilon), this establishes a polynomial separation between pure and approximate DP. We will include the proof in the revision.

Other problems under pure DP can be an interesting direction for future work.

Thanks for your response, I will keep my positive score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.