Pith. sign in

REVIEW 3 major objections 5 minor 81 references

Differentially Private Explanations for Clusters

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read By rewriting clustering-explanation quality scores so each has sensitivity bounded by 1, DPClustX produces histogram explanations whose selected attributes match non-private quality within 1–2 percent at a privacy budget of ε = 0.1.

desk verdict A credible first framework for differentially private histogram-based cluster explanations, with a sound privacy story but a utility proof that doesn't match the implemented mechanism and experimental headline numbers without error bars. read the letter →

arxiv 2506.05900 v1 pith:BBZXWLTI submitted 2025-06-06 cs.CR cs.DB

Amir Gilad , Tova Milo , Kathy Razmadze , Ron Zadicario This is my paper
classification cs.CRcs.DB
keywords differentialprivacyclusteringexplanationshistogram-basedlow-sensitivityqualityfunctionsexponentialmechanismone-shottop-kselectionblack-boxprivateattribute
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to show that explaining clustering results with per-cluster histograms can be done under differential privacy without giving up explanation quality. The standard histogram quality scores — interestingness, sufficiency, and diversity — turn out to have high sensitivity, so the noise needed to privatize them would overwhelm the signal. The paper rewrites each score so its sensitivity is bounded by 1 at the price of scaling by cluster size, then selects explanation attributes in two private stages and generates noisy histograms only for the attributes that survive. On three real datasets and five clustering methods, the selected attributes stay within roughly 1 to 2 percent of the non-private baseline in quality at a total privacy budget of $\varepsilon = 0.1$, where direct DP adaptations lose 10 to 20 percent, and at $\varepsilon = 1$ the chosen attributes coincide with the non-private baseline on the Diabetes dataset. If the claim holds, analysts can attach short private histogram explanations to black-box clusterings, including privately computed ones, without a manual and privacy-exhausting exploration session.

What carries the argument

The load-bearing object is a family of low-sensitivity quality functions, each with sensitivity bounded by 1: $\mathrm{Int}_p$ (interestingness, the $\ell^1$ deviation of the cluster histogram from the cluster's proportional share of the full-data histogram), $\mathrm{Suf}_p$ (sufficiency, the within-cluster concentration of each attribute value), and $\mathrm{Div}_p$ (pairwise diversity across clusters), combined into a single-cluster score $\mathrm{Score}_\gamma$ and a global score $\mathrm{GlScore}_\lambda$. The key trick is multiplying each distributional distance by the cluster size it describes — for instance $\mathrm{Int}_p = |D_c| \cdot \mathrm{TVD}$ — which leaves the attribute ranking unchanged on a fixed dataset but widens the score range from $[0,1]$ to $[0, |D_c|]$, giving the added noise room to breathe when clusters are large. Selection then proceeds in two private stages: Stage-1 draws $k$ candidate attributes per cluster using a one-shot top-$k$ mechanism with Gumbel noise of scale $2k|C|/\varepsilon_{\mathrm{CandSet}}$, and Stage-2 runs the exponential mechanism over the $k^{|C|}$ candidate combinations using the sensitivity-1 global score; noisy histograms are computed only for the chosen attributes, with out-of-cluster histograms obtained by subtraction as post-processing.

What would settle it

Run DPClustX with total budget $\varepsilon = 0.1$ on a dataset whose clusters average only a few hundred rows and compare the quality of the selected attributes against the non-private TabEE baseline; the central utility claim predicts a gap near 1 to 2 percent, so a double-digit gap at that cluster scale would falsify it. A second check is to simulate Algorithm 1's one-shot Gumbel selection alongside the iterated exponential mechanism it is asserted to equal: if the two output distributions differ measurably, the foundation of Proposition 5.1's utility bound would need to be re-examined.

Watch

Extended reading notes

Core claim

The central discovery is that a histogram-based cluster explanation can be privatized without first privatizing all candidate histograms, provided the quality scores are redesigned so that adding or removing a single tuple changes any score by at most 1. The paper proves that the original interestingness (total variation distance), sufficiency, and diversity scores have sensitivity at least $1/2$ over a range of $[0,1]$, which makes their direct DP use impractical; its replacements $\mathrm{Int}_p$, $\mathrm{Suf}_p$, $\mathrm{Div}_p$, and the weighted combinations $\mathrm{Score}_\gamma$ and $\mathrm{GlScore}_\lambda$ all have sensitivity bounded by 1, while inducing the same attribute ranking as the original scores on any fixed dataset. The pipeline selects per cluster a private candidate set of top-$k$ attributes with a one-shot Gumbel top-$k$ mechanism, applies the exponential mechanism over the restricted set of attribute combinations using the global score, and finally releases a differentially private histogram only for the selected attributes, deriving out-of-cluster histograms by subtraction. Theorem 5.3 states that the whole procedure is $(\varepsilon_{\mathrm{CandSet}} + \varepsilon_{\mathrm{TopComb}} + \varepsilon_{\mathrm{Hist}})$-DP, and the experiments report that at total budget $\varepsilon = 0.1$ the quality of the selected attributes is within 1 to 2 percent of the non-private TabEE baseline, while the DP baselines lose 10 to 20 percent.

Load-bearing premise

The framework's utility rests on clusters being large enough that the signal in the rescaled scores and the noisy histograms survives the added differential-privacy noise, and the utility bounds do not guarantee this independently of cluster size — the experiments show quality dropping by 12 to 20 percent once the average cluster size falls below a few thousand rows; the analysis also leans on the asserted equivalence between the one-shot Gumbel top-$k$ mechanism and iterated exponential mechanisms, which the paper does not prove.

Editorial extensions

If this is right

  • Black-box clusterings, including privately computed ones such as DP $k$-means output, can be accompanied by short histogram explanations whose privacy cost is explicit and composes additively with the clustering's own budget.
  • At $\varepsilon = 1$ the framework selects exactly the same attributes as the non-private baseline across all five clustering methods on the Diabetes dataset, so for moderately large datasets the explanation step can be effectively free in quality.
  • Because noisy histograms are generated only for the selected attributes, the framework's privacy analysis is independent of the specific histogram mechanism, so it inherits future improvements in DP histogram publishing automatically.
  • The low-sensitivity scores can serve as drop-in quality measures outside privacy, since on any fixed dataset they rank attributes identically to the sensitive measures they replace.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The rescaling trick that carries the paper — multiplying a distributional distance by the size of the subpopulation it describes — is portable to other settings that rank explanations by distribution shift, such as private visualization recommendations or differentially private query-result explanations.
  • A natural extension the paper leaves implicit is an adaptive budget split that spends more of the privacy budget on candidate selection when clusters are small, or that warns when the average cluster size falls below the regime where the experiments show degradation.
  • If the asserted equivalence between the one-shot Gumbel top-$k$ mechanism and iterated exponential mechanisms were ever shown to fail, the privacy bound of Algorithm 1 would survive via the composition argument, but the utility bound of Proposition 5.1(2) would need re-derivation with a different noise scale.
  • Swapping the Geometric histogram mechanism used in the experiments for other DP histogram generators and measuring end-to-end attribute quality would localize how much of the remaining error comes from histogram noise versus attribute-selection noise.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces DPClustX, a framework for releasing histogram-based explanations of black-box clustering results under differential privacy. The framework defines low-sensitivity variants of the interestingness, sufficiency, and diversity quality functions (Int_p, Suf_p, Div_p), combines them into per-cluster and global score functions with sensitivity bounded by 1, and then uses a two-stage private selection procedure: per-cluster top-k candidate attributes are chosen by a one-shot Gumbel top-k mechanism, a global attribute combination is selected by the exponential mechanism, and DP histograms are generated only for the selected attributes. Theorem 5.3 states the overall (ε_CandSet + ε_TopComb + ε_Hist)-DP guarantee. Experiments on Census, Diabetes, and Stack Overflow data with several clustering methods claim that, at ε = 0.1, the quality of attributes selected by DPClustX is within roughly 1–2% of the non-private TabEE baseline, while DP baselines lose 10–20%.

Significance. If the technical and empirical claims hold, DPClustX is a useful and original contribution: it is, to my knowledge, the first framework for DP histogram-based explanations of clustering results, and it addresses a real gap between non-private cluster-explanation systems and the DP setting. The sensitivity analyses in Section 4 and Appendix A are detailed and largely self-contained, and the ranking equivalence between the new low-sensitivity interestingness and sufficiency functions and the prior sensitive functions is proven rather than assumed. The paper also ships a public code repository and evaluates across three datasets and five clustering methods, which is a strength. However, two load-bearing points currently prevent full confidence: the utility proof for the implemented candidate-selection mechanism does not match the mechanism actually run, and the experimental section reports no error bars or significance tests for the small quality gaps that support the central empirical claim. Both issues are addressable in revision.

major comments (3)
  1. [§5.1, Proposition 5.1(2), and §A.5] The proof of Proposition 5.1(2) argues that the output of Algorithm 1 has the same distribution as iteratively applying k exponential mechanisms and then invokes the exponential-mechanism utility bound. Algorithm 1, however, sorts scores with independent Gumbel noise in a one-shot top-k mechanism. The asserted equivalence to iterated exponential mechanisms is not established in the paper and is not a direct consequence of the cited reference [15], which analyzes a joint mechanism. As written, the utility guarantee in Proposition 5.1(2) is therefore unsupported for the implemented algorithm. Please either provide a proof of the Gumbel top-k equivalence, or prove a utility bound directly for the one-shot mechanism, or restate the proposition using the joint utility theorem from the Durfee-Rogers analysis. This is load-bearing because the Stage-1 filtering guarantee is what justifies restricting the global search to the candidate sets.
  2. [§6.2, Figures 5 and 8b] All experimental results are stated as averages over 10 runs, but no standard deviations, confidence intervals, or significance tests are reported. The paper's central quantitative claim is that DPClustX is within 0.66%–1.6% of the non-private TabEE quality at ε = 0.1; with only 10 runs, such small gaps can easily be within run-to-run noise, and the same issue affects the interpretation of the 20% degradation at average cluster size 2035 in Figure 8b. Please report per-run variances or confidence intervals, and, for the main comparisons, provide a paired significance test (e.g., a Wilcoxon signed-rank test or a bootstrap interval) so that the reader can judge whether the 1–2% differences are statistically distinguishable from zero.
  3. [§6.2, 'Selected attributes quality score' and 'Quality for different cluster sizes'] The evaluation measures only the quality of the selected attribute combination, computed with the original sensitive score on the true data; it does not evaluate the accuracy of the released histograms, even though those histograms are the actual explanation output delivered to the user. The summary claim that DPClustX provides 'accurate explanations' under a tight privacy budget is therefore not directly supported: the histograms are generated with an additional privacy budget and could be substantially noisy even when the attribute selection is good. Please add a histogram-accuracy evaluation (for example, L1 error of the released counts or a utility measure evaluated on the noisy histograms) and clarify whether the reported 'total privacy budget' in the attribute-selection experiments includes the histogram budget, since Section 6.1 uses ε_CandSet + ε_TopComb + ε_Hist = 0.3 as the full default while Section 6.2 reports ε_CandSet = ε_TopComb = ε/2 with no histogram component.
minor comments (5)
  1. [Appendix A.1, Definition A.4] The Jensen–Shannon divergence formula writes H(q) twice; it should be 1/2 H(p) + 1/2 H(q).
  2. [Appendix A.4, Proposition 4.14 proof] In the range-bound part of the proof, the phrase '1/|C| Σ Suf_p' is repeated for both interestingness and sufficiency; the first occurrence should refer to Int_p.
  3. [§6.1, baseline description] The DP-TabEE baseline description mentions only Propositions 4.1 and 4.5 for the sensitivity of the original quality functions, but the original diversity measure also has a sensitivity lower bound (Proposition A.8); including it would make the baseline's noise calibration complete.
  4. [§6.2, MAE definition] The quantity called MAE is 1/|C| Σ 1{AC(c) ≠ AC*(c)}, which is an attribute-mismatch rate rather than a mean absolute error in the usual continuous sense; consider renaming it to avoid confusion.
  5. [§6.1 and §6.2, budget terminology] The phrase 'total privacy budget' is used inconsistently: in Section 6.1 it is the sum of all three components, while in Section 6.2 Figure 5 it is only the attribute-selection budget. Please make the terminology consistent so that readers can compare the reported ε = 0.1 results with the full framework's privacy guarantee.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the low-sensitivity scores are proven rescalings of prior-work measures and the DP argument rests on external mechanisms, not on the paper's own conclusions.

full rationale

The paper's derivation chain is self-contained. The low-sensitivity interestingness Int_p is explicitly defined as |D_c| times the total-variation distance, and the text proves the ranking identity rather than assuming it (Definition 4.3 and the paragraph following it). The sufficiency measure Suf_p is shown in Appendix A.2, Proposition 4.7(1), to satisfy |D|·Suf(D,f,AC) = sum_c Suf_p(D,f,c,AC(c)), a proved equality that justifies the ranking-consistency claim. The diversity measure Div_p is a convex combination of pairwise min·TVD terms whose sensitivity bound is proved via Lemma A.3 and Proposition A.10. The privacy argument in Theorem 5.3 is a standard sequential/parallel composition of Algorithm 1's one-shot top-k mechanism, the exponential mechanism, and DP histogram releases; the top-k mechanism and its utility bound are attributed to the external works Durfee and Rogers [14,15] and Dwork et al. [19], not to the present authors. The empirical evaluation compares against the non-private TabEE baseline [8] using the original sensitive quality functions; this is an external benchmark, and the 1-2% quality gap is not forced by construction because the global GlScore optimized by DPClustX is not identical to the evaluation score Q (global Int_p averages |D_c|·TVD while Q averages TVD, and global Div_p is pairwise min·TVD while Q uses the permutation-based diversity of [8]). The self-citations to [8] and [11] are for baselines, inspiration, and default weight parameters, but the paper re-derives the sensitivity and ranking properties it needs; the default weights are also shown to be non-critical through weight-robustness experiments. The only notable weakness, the heavy reliance on the cited Gumbel/EM equivalence for the utility bound, is a correctness or verification concern about an external theorem, not a circularity: the paper's conclusions do not reduce to its own unverified assertions. Overall, no prediction or claimed first-principles result is equivalent to its inputs by definition.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim relies on standard DP theorems plus the domain assumption that the clustering function is fixed. The one-shot top-k equivalence is the least standard item: the mechanism as implemented (add Gumbel noise, take top-k) is the joint mechanism, whose utility analysis is different from the iterative-EM analysis in the proof. No new entities (particles, forces, dimensions) are introduced. Free parameters are user-chosen weights and candidate sizes, not fitted to the target result.

free parameters (3)
  • lambda_Int, lambda_Suf, lambda_Div = 1/3 each
    Weights for the global score, adopted from the non-private TabEE work [8] based on prior user studies. They affect the relative importance of interestingness, sufficiency, and diversity but are not fitted to the target results.
  • k (candidate set size per cluster) = 3
    Chosen via ablation (Figure 7); the paper finds that increasing k beyond 3 does not improve quality but increases runtime. This is a hand-chosen hyperparameter, not a fitted constant.
  • privacy budget split = epsilon_CandSet = epsilon_TopComb = epsilon_Hist = 0.1 (defaults)
    The total privacy budget is split across the two selection stages and the histogram stage. The split choices are practical defaults, and the paper evaluates variation of the total budget.
assumptions (5)
  • standard math Sequential, parallel, and post-processing composition theorems for differential privacy (Dwork et al. 2006, 2014).
    Used in the proof of Theorem 5.3 to compose the clustering, candidate selection, global selection, and histogram stages.
  • standard math Exponential mechanism utility theorem (McSherry and Talwar 2007).
    Used to prove the utility bound in Proposition 5.1(2) and to analyze the global selection stage.
  • domain assumption The one-shot Top-k mechanism with Gumbel noise scale 2*k*Delta/epsilon is equivalent to k iterations of the exponential mechanism, each with privacy budget epsilon/k.
    This equivalence is asserted in Section 2.1 and used in the proof of Proposition 5.1(2). It is not the standard joint-mechanism analysis of the Gumbel top-k, and the cited reference does not state this equivalence in this form.
  • domain assumption The clustering function f: dom(R) -> C is fixed and public during the explanation step; neighboring datasets are considered with respect to the same f.
    Assumed in Definition 3.1 and used to argue sequential composition of DP clustering and DP explanation. The paper motivates this with a comparison to DP classifier explanations, but the assumption limits the scope to f that are data-independent or whose output is fixed before the explanation step.
  • domain assumption The DP histogram mechanism M_hist has utility guarantees that can be translated into accuracy requirements.
    The paper states that M_hist can be instantiated with any DP histogram mechanism and is accompanied by utility bounds; the actual accuracy of the final explanation depends on this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Differentially Private Explanations for Clusters." pith.science (2026). https://pith.science/paper/BBZXWLTI

@misc{pith2026250605900,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Explanations for Clusters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BBZXWLTI}},
  note         = {Machine review of arXiv:2506.05900}
}
read the original abstract

The dire need to protect sensitive data has led to various flavors of privacy definitions. Among these, Differential privacy (DP) is considered one of the most rigorous and secure notions of privacy, enabling data analysis while preserving the privacy of data contributors. One of the fundamental tasks of data analysis is clustering , which is meant to unravel hidden patterns within complex datasets. However, interpreting clustering results poses significant challenges, and often necessitates an extensive analytical process. Interpreting clustering results under DP is even more challenging, as analysts are provided with noisy responses to queries, and longer, manual exploration sessions require additional noise to meet privacy constraints. While increasing attention has been given to clustering explanation frameworks that aim at assisting analysts by automatically uncovering the characteristics of each cluster, such frameworks may also disclose sensitive information within the dataset, leading to a breach in privacy. To address these challenges, we present DPClustX, a framework that provides explanations for black-box clustering results while satisfying DP. DPClustX takes as input the sensitive dataset alongside privately computed clustering labels, and outputs a global explanation, emphasizing prominent characteristics of each cluster while guaranteeing DP. We perform an extensive experimental analysis of DPClustX on real data, showing that it provides insightful and accurate explanations even under tight privacy constraints.

Figures

Figures reproduced from arXiv: 2506.05900 by the authors.

Figure 1
Figure 1. Example of the Diabetes dataset. for the best clustering explanation, which encompasses all possible assignments, is considerably large. Hence, (3) we adapt techniques from prior work [8] and develop a DP mechanism that constructs a smaller candidate set for each cluster, from which the clustering explanation is privately derived. To this end, we adapt the idea of a single-cluster score function which is used to ran… view at source ↗
Figure 2
Figure 2. Cluster explanation with its textual description. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. System architecture of DPClustX. Algorithm 1 se￾lects candidate attributes for each cluster (1) using the single￾cluster score function (2). Algorithm 2 selects a high-quality attribute combination from these candidates (3) using the global score function (4), and generates noisy histograms only for the selected attributes (5). • We develop DPClustX, the first framework designed to generate histogram-based explanati… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Ranked explanation candidates for Cluster 1 of the [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: 𝑄𝑢𝑎𝑙𝑖𝑡𝑦 values of the selected attribute combination as the total privacy budget 𝜀 varies. Note that the range of the 𝑄𝑢𝑎𝑙𝑖𝑡𝑦 axis differs across methods, reflecting the substantial variation in explanation quality between clustering approaches. DP-k-means k-means k-mo…
Figure 6
Figure 6. Figure 6: Mean Absolute Error (MAE) values of the selected [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 9
Figure 9. Figure 9: DPClustX’s execution time trends for the Census (C), Diabetes (D), and Stack Overflow (SO) datasets by different parameters. Civ Emp, At Work N/A < 16 Not in Labor Unemployed 'iRlabor' 0 25 50 75 frequency (%) Cluster 1 Rest N/A < 16 No Yes 'iWork89' 0 25 50 75 100 fre…
Figure 10
Figure 10. Figure 10: Explanations for the US Census dataset case study. [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]
Figure 11
Figure 11. Figure 11: 𝑄𝑢𝑎𝑙𝑖𝑡𝑦 values of the selected attribute combination for the Diabetes dataset, as the total privacy budget 𝜀 varies. 10 2 10 1 10 0 Privacy Budget 0.0 0.2 0.4 0.6 0.8 1.0 MAE k-means 3 Clusters 10 2 10 1 10 0 Privacy Budget 0.0 0.2 0.4 0.6 0.8 1.0 DP-k-means 3 Cluster…
Figure 12
Figure 12. Figure 12: MAE values of the selected attribute combination for the Diabetes dataset, as the total privacy budget 𝜀 varies. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

81 extracted references · 63 canonical work pages

  1. [15]

    David Durfee and Ryan M Rogers. 2019. Practical differentially private top-k selection with pay-what-you-get composition.Advances in Neural Information Processing Systems32 (2019)

    work page 2019

  2. [1]

    DPClustX Git Repository

    2024. DPClustX Git Repository. https://github.com/ronzadi/DPClustX

    2024

  3. [2]

    Karim Abouelmehdi, Abderrahim Beni Hssane, and Hayat Khaloufi. 2018. Big healthcare data: preserving security and privacy.J. Big Data5 (2018), 1. https: //doi.org/10.1186/S40537-017-0110-7

    work page doi:10.1186/s40537-017-0110-7 2018

  4. [3]

    John M. Abowd. 2018. The U.S. Census Bureau Adopts Differential Privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, Yike Guo and Faisal Farooq (Eds.). ACM, 2867. https://doi.org/10.1145/3219819.3226070

    arXiv 2018

  5. [4]

    Gergely Acs, Claude Castelluccia, and Rui Chen. 2012. Differentially private histogram publishing through lossy compression. In2012 IEEE 12th International Conference on Data Mining. IEEE, 1–10

    work page 2012

  6. [5]

    Sihem Amer-Yahia, Tova Milo, and Brit Youngmann. 2021. Exploring ratings in subjective databases. InProceedings of the 2021 International Conference on Management of Data. 62–75

    work page 2021

  7. [6]

    Allan Borodin, Aadhar Jain, Hyun Chul Lee, and Yuli Ye. 2017. Max-sum di- versification, monotone submodular functions, and dynamic updates.ACM Transactions on Algorithms (TALG)13, 3 (2017), 1–25

    work page 2017

  8. [7]

    John Clore, Krzysztof Cios, Jon DeShazo, and Beata Strack. 2014. Diabetes 130- US Hospitals for Years 1999–2008. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5230J

    doi:10.24432/c5230j 2014

Show all 81 references
  1. [8]

    Roni Copul, Nave Frost, Tova Milo, and Kathy Razmadze. 2024. TabEE: Tabular Embeddings Explanations.Proceedings of the ACM on Management of Data2, 1 (2024), 1–26

    2024

  2. [9]

    1999.Mathematical methods of statistics

    Harald Cramér. 1999.Mathematical methods of statistics. Vol. 43. Princeton university press

    1999

  3. [10]

    Sanjoy Dasgupta, Nave Frost, and Michal Moshkovitz. 2022. Framework for eval- uating faithfulness of local explanations. InInternational Conference on Machine Learning. PMLR, 4794–4815

    2022

  4. [11]

    Daniel Deutch, Amir Gilad, Tova Milo, Amit Mualem, and Amit Somech. 2022. FEDEX: An Explainability Framework for Data Exploration Steps.Proceedings of the VLDB Endowment15, 13 (2022), 3854–3868

    2022

  5. [12]

    Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. InProceedings of the 31st International Conference on Neural Information Processing Systems(Long Beach, California, USA)(NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 3574–3583

    2017

  6. [13]

    Jinshuo Dong, David Durfee, and Ryan Rogers. 2020. Optimal differential privacy composition for exponential mechanisms. InInternational Conference on Machine Learning. PMLR, 2597–2606

    2020

  7. [14]

    Durfee and R

    D. Durfee and R. Rogers. 2021. One-shot DP top-k mechanisms. DifferentialPri- vacy.org. https://differentialprivacy.org/one-shot-top-k/

    2021

  8. [16]

    Cynthia Dwork. 2006. Differential privacy. InInternational colloquium on au- tomata, languages, and programming. Springer, 1–12

    2006

  9. [17]

    Cynthia Dwork. 2019. Differential Privacy and the US Census. InProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems(Amsterdam, Netherlands)(PODS ’19). Association for Computing Ma- chinery, New York, NY, USA, 1. https://doi.org/10.1145/32...

    2019

  10. [18]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Cali- brating noise to sensitivity in private data analysis. InTheory of Cryptography Conference. Springer, 265–284

    2006

  11. [19]

    Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differ- ential privacy.Foundations and Trends®in Theoretical Computer Science9, 3–4 (2014), 211–407

    2014

  12. [20]

    Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Ran- domized Aggregatable Privacy-Preserving Ordinal Response. InProceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (Scottsdale, Arizona, USA)(CCS ’14). Association for Com...

    2014

  13. [21]

    Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. 2022. Almost tight approximation algorithms for explainable clustering. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2641–2663

    2022

  14. [22]

    Sandra Gabriele and Sonia Chiasson. 2020. Understanding Fitness Tracker Users’ Security and Privacy Knowledge, Attitudes and Behaviours. InCHI ’20: CHI Conference on Human Factors in Computing Systems, Honolulu, HI, USA, April 25- 30, 2020, Regina Bernhaupt, Florian ’Floyd’ Mu...

    2020

  15. [23]

    Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson. 2021. Nearly- tight and oblivious algorithms for explainable clustering.Advances in Neural Information Processing Systems34 (2021), 28929–28939

    2021

  16. [24]

    Chang Ge, Xi He, Ihab F Ilyas, and Ashwin Machanavajjhala. 2019. Apex: Accuracy-aware differentially private data exploration. InProceedings of the 2019 International Conference on Management of Data. 177–194

    2019

  17. [25]

    Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2020. Differentially private clustering: Tight approximation ratios.Advances in Neural Information Processing Systems33 (2020), 4040–4054

    2020

  18. [26]

    Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2009. Universally utility-maximizing privacy mechanisms. InProceedings of the forty-first annual ACM symposium on Theory of computing. 351–360

    2009

  19. [27]

    Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar

  20. [28]

    Frederik Harder, Matthias Bauer, and Mijung Park. 2020. Interpretable and dif- ferentially private predictions. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 4083–4090

    2020

  21. [29]

    Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. 2010. Boosting the Accuracy of Differentially Private Histograms Through Consistency.Proceedings of the VLDB Endowment3, 1 (2010)

    2010

  22. [30]

    2013.Knowledge Discovery and Measures of Interest

    Robert J Hilderman and Howard J Hamilton. 2013.Knowledge Discovery and Measures of Interest. Vol. 638. Springer Science & Business Media

    2013

  23. [31]

    Naoise Holohan, Stefano Braghin, Pól Mac Aonghusa, and Killian Levacher. 2019. Diffprivlib: the IBM differential privacy library.arXiv preprint arXiv:1907.02444 (2019)

    2019 arXiv

  24. [32]

    Lianyu Hu, Mudi Jiang, Junjie Dong, Xinying Liu, and Zengyou He. 2024. Inter- pretable Clustering: A Survey.arXiv preprint arXiv:2409.00743(2024)

    2024 arXiv

  25. [33]

    Noah Johnson, Joseph P Near, Joseph M Hellerstein, and Dawn Song. 2020. Chorus: a programming framework for building scalable differential privacy mechanisms. In2020 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 535–551

    2020

  26. [34]

    Noah Johnson, Joseph P Near, and Dawn Song. 2018. Towards practical differen- tial privacy for SQL queries.Proceedings of the VLDB Endowment11, 5 (2018), 526–539

    2018

  27. [35]

    James Jordon, Jinsung Yoon, and Mihaela van der Schaar. 2019. Differentially private model personalization. InProceedings of the 36th International Conference on Machine Learning. PMLR

    2019

  28. [36]

    Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanava- jjhala, Michael Hay, and Gerome Miklau. 2019. Privatesql: a differentially private sql query engine.Proceedings of the VLDB Endowment12, 11 (2019), 1371–1384

    2019

  29. [37]

    Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec. 2016. Interpretable decision sets: A joint framework for description and prediction. InProceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1675–1684

    2016

  30. [38]

    Doris Jung-Lin Lee, Dixin Tang, Kunal Agarwal, Thyne Boonmark, Caitlyn Chen, Jake Kang, Ujjaini Mukhopadhyay, Jerry Song, Micah Yong, Marti A Hearst, et al

  31. [39]

    2017.Markov chains and mixing times

    David A Levin and Yuval Peres. 2017.Markov chains and mixing times. Vol. 107. American Mathematical Soc

    2017

  32. [40]

    Bing-Rong Lin and Daniel Kifer. 2013. Information preservation in statistical privacy and bayesian estimation of unattributed histograms. InProceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 677–688

    2013

  33. [41]

    Jianhua Lin. 1991. Divergence measures based on the Shannon entropy.IEEE Transactions on Information theory37, 1 (1991), 145–151

    1991

  34. [42]

    Yuyu Luo, Xuedi Qin, Nan Tang, and Guoliang Li. 2018. DeepEye: Towards Automatic Data Visualization. ICDE

    2018

  35. [43]

    Ge Lv and Lei Chen. 2023. On data-aware global explainability of graph neural networks.Proceedings of the VLDB Endowment16, 11 (2023), 3447–3460

    2023

  36. [44]

    Konstantin Makarychev and Liren Shan. 2021. Near-optimal algorithms for explainable k-medians and k-means. InInternational Conference on Machine Learning. PMLR, 7358–7367

    2021

  37. [45]

    Konstantin Makarychev and Liren Shan. 2022. Explainable k-means: don’t be greedy, plant bigger trees!. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 1629–1642

    2022

  38. [46]

    Ryan McKenna, Gerome Miklau, and Daniel Sheldon. 2021. Winning the NIST Contest: A scalable and general approach to differentially private synthetic data. arXiv preprint arXiv:2108.04978(2021)

    2021 arXiv

  39. [47]

    Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE, 94–103

    2007

  40. [48]

    Frank D McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. InProceedings of the 2009 ACM SIGMOD International Conference on Management of data. 19–30

    2009

  41. [49]

    Chris Meek, Bo Thiesson, and David Heckerman. 2001. US Census Data (1990). UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5VP42

    1990 doi

  42. [50]

    Rami Mochaourab, Sugandh Sinha, Stanley Greenstein, and Panagiotis Papa- petrou. 2021. Robust counterfactual explanations for privacy-preserving SVM. In International Conference on Machine Learning (ICML 2021), Workshop on Socially 14 Differentially Private Explanations for Cl...

    2021

  43. [51]

    Michal Moshkovitz, Sanjoy Dasgupta, Cyrus Rashtchian, and Nave Frost. 2020. Explainable k-means and k-medians clustering. InInternational conference on machine learning. PMLR, 7055–7065

    2020

  44. [52]

    Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. 2020. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency. 607–617

    2020

  45. [53]

    Huu Hiep Nguyen. 2018. Privacy-preserving mechanisms for k-modes clustering. Computers & Security78 (2018), 60–75

    2018

  46. [54]

    Huy L Nguyen, Anamay Chaturvedi, and Eric Z Xu. 2021. Differentially private k-means via exponential mechanism and max cover. InProceedings of the AAAI conference on artificial intelligence, Vol. 35. 9101–9108

    2021

  47. [55]

    Thanh Tam Nguyen, Thanh Trung Huynh, Zhao Ren, Thanh Toan Nguyen, Phi Le Nguyen, Hongzhi Yin, and Quoc Viet Hung Nguyen. 2024. A survey of privacy- preserving model explanations: Privacy risks, attacks, and countermeasures. arXiv preprint arXiv:2404.00673(2024)

    2024 arXiv

  48. [56]

    Stack Overflow. 2018. Stack Overflow Annual Developer Survey. https://survey. stackoverflow.co

    2018

  49. [57]

    Adedoyin Tolulope Oyewole, Bisola Beatrice Oguejiofor, Nkechi Emmanuella Eneh, Chidiogo Uzoamaka Akpuokwe, and Seun Solomon Bakare. 2024. Data privacy laws and their impact on financial technology companies: a review. Computer Science & IT Research Journal5, 3 (2024), 628–650

    2024

  50. [58]

    Neel Patel, Reza Shokri, and Yair Zick. 2022. Model explanations with differential privacy. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 1895–1904

    2022

  51. [59]

    Wahbeh Qardaji, Weining Yang, and Ninghui Li. 2013. Understanding hierarchical methods for differentially private histograms.Proceedings of the VLDB Endowment 6, 14 (2013), 1954–1965

    2013

  52. [60]

    Kaivalya Rawal and Himabindu Lakkaraju. 2020. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses.Advances in Neural Information Processing Systems33 (2020), 12187–12198

    2020

  53. [61]

    Sunita Sarawagi, Rakesh Agrawal, and Nimrod Megiddo. 1998. Discovery-driven exploration of OLAP data cubes. InEDBT

    1998

  54. [62]

    Uri Stemmer and Haim Kaplan. 2018. Differentially private k-means with con- stant multiplicative error.Advances in Neural Information Processing Systems31 (2018)

    2018

  55. [63]

    Beata Strack, Jonathan P DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof J Cios, and John N Clore. 2014. Impact of HbA1c measurement on hospital readmission rates: analysis of 70,000 clinical database patient records. BioMed research international2014, 1 (20...

    2014

  56. [64]

    Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. 2016. Differ- entially private k-means clustering. InProceedings of the sixth ACM conference on data and application security and privacy. 26–37

    2016

  57. [65]

    Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, Min Lyu, and Hongxia Jin

  58. [66]

    Bo Tang, Shi Han, Man Lung Yiu, Rui Ding, and Dongmei Zhang. 2017. Extracting top-k insights from multi-dimensional data. InProceedings of the 2017 ACM International Conference on Management of Data. 1509–1524

    2017

  59. [67]

    Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and XiaoFeng Wang. 2017. Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12.CoRRabs/1709.02753 (2017). arXiv:1709.02753 http://arxiv.org/ abs/1709.02753

    2017 arXiv

  60. [68]

    Yuchao Tao, Amir Gilad, Ashwin Machanavajjhala, and Sudeepa Roy. 2022. DPXPlain: privately explaining aggregate query answers.Proceedings of the VLDB Endowment16, 1 (2022), 113–126

    2022

  61. [69]

    Sariel Tutay and Amit Somech. 2023. Cluster-Explorer: An interactive Frame- work for Explaining Black-Box Clustering Results. InProceedings of the 32nd ACM International Conference on Information and Knowledge Management(Birm- ingham, United Kingdom)(CIKM ’23). Association for...

    2023

  62. [70]

    Marcos R Vieira, Humberto L Razente, Maria CN Barioni, Marios Hadjieleftheriou, Divesh Srivastava, Caetano Traina, and Vassilis J Tsotras. 2011. On query result diversification. In2011 IEEE 27th International Conference on Data Engineering. IEEE, 1163–1174

    2011

  63. [71]

    Cort J Willmott and Kenji Matsuura. 2005. Advantages of the mean absolute error (MAE) over the root mean square error (RMSE) in assessing average model performance.Climate research30, 1 (2005), 79–82

    2005

  64. [72]

    Kanit Wongsuphasawat, Dominik Moritz, Anushka Anand, Jock Mackinlay, Bill Howe, and Jeffrey Heer. 2016. Voyager: Exploratory analysis via faceted browsing of visualization recommendations.TVCG(2016)

    2016

  65. [73]

    Yonghui Xiao, Li Xiong, Liyue Fan, and Slawomir Goryczka. 2012. DPCube: Differentially private histogram release through multidimensional partitioning. arXiv preprint arXiv:1202.5358(2012)

    2012 arXiv

  66. [74]

    Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Ge Yu, and Marianne Winslett

  67. [75]

    Brit Youngmann, Sihem Amer-Yahia, and Aurelien Personnaz. 2022. Guided exploration of data summaries.Proceedings of the VLDB Endowment (PVLDB)15, 9 (2022), 1798–1807

    2022

  68. [76]

    Jun Zhang, Graham Cormode, Cecilia M Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2017. Privbayes: Private data release via bayesian networks.ACM Transactions on Database Systems (TODS)42, 4 (2017), 1–41. 15 Amir Gilad, Tova Milo, Kathy Razmadze, and Ron Zadicario A Theorem...

    2017

  69. [81]

    General Practice

    We consider two cases according to whether or not𝑡 is added to 𝐷𝑐. First assume that𝐷′ 𝑐 =𝐷𝑐. We have Suf𝑝(𝐷,𝑓,𝑐,𝐴)−Suf 𝑝(𝐷′,𝑓,𝑐,𝐴) = cnt𝐴=𝑡[𝐴](𝐷𝑐)2 cnt𝐴=𝑡[𝐴](𝐷) − cnt𝐴=𝑡[𝐴](𝐷𝑐)2 cnt𝐴=𝑡[𝐴](𝐷)+1 ≤1 where in the equality we have used that cnt𝐴=𝑎(𝐷𝑐)=cnt 𝐴=𝑎(𝐷′ 𝑐) for all𝑎 since𝐷...

  70. [2010]

    InProceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms

    Differentially private combinatorial optimization. InProceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1106– 1125

  71. [2013]

    Differentially private histogram publication.The VLDB journal22 (2013), 797–822

    2013

  72. [2017]

    Differentially private k-means clustering and a hybrid approach to private optimization.ACM Transactions on Privacy and Security (TOPS)20, 4 (2017), 1–33

    2017

  73. [2021]

    Lux: always-on visualization recommendations for exploratory dataframe workflows.PVLDB15, 3 (2021), 727–738

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.