{"id":"c828fc40-4a6c-4a44-bb12-02ccfae743ba","arxiv_id":"2506.05900","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DPClustX privately selects the most informative attributes for each cluster and releases noisy histograms only for those attributes, providing differentially private explanations of clustering results.","lead":"DPClustX is a system that explains what each cluster of a sensitive dataset represents while provably protecting the privacy of individuals in the data. It privately picks the most informative attributes per cluster and releases only the histograms for those attributes, making cluster interpretation possible under differential privacy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Experimental quality claims lack error bars; a 1-2% gap to TabEE may be within run-to-run noise.","rationale":"The central privacy claim is sound: Theorem 5.3 follows from sequential and parallel composition, and the sensitivity bounds in Section 4 are correct. I also verified that the one-shot Gumbel top-k mechanism is exactly equivalent to iteratively applying the exponential mechanism k times with budget ε/k (the Gumbel softmax yields the Plackett-Luce model, which is the sequential exponential mechanism), so Proposition 5.1's utility bound is valid despite the reader's concern about the cited reference. The cluster-size limitation is real and acknowledged: the theoretical utility bound in Proposition 5.1(2) becomes vacuous when the noise term 2|C|k/ε (ln|A|+t) exceeds the score range [0, |D_c|], and Figure 8b confirms degradation for small clusters. However, this is a scope limitation, not a correctness flaw. The most load-bearing unaddressed concern is statistical: all quality experiments average 10 runs with no error bars or significance tests. The headline claim of quality within 1-2% of TabEE at ε=0.1 could be within run-to-run noise, especially for the Diabetes gap of 0.66%. Without confidence intervals, the empirical conclusion that DPClustX provides explanations comparable to the non-private baseline is not established. My read reinforces the reader's CONDITIONAL verdict; the conditions should require statistical support for the experimental comparisons and an explicit statement of the minimum cluster size under which the utility guarantee is meaningful.","tokens_in":44333,"tokens_out":31122,"duration_ms":287867,"concrete_test":"Rerun the Figure 5 quality experiments for Diabetes, Census, and Stack Overflow with at least 100 independent runs per configuration, and compute 95% confidence intervals for the difference in Q between DPClustX and TabEE at ε=0.1 (and ε=0.2 for the full pipeline). If any interval contains 0 or the upper bound exceeds 5%, the claim of comparable quality is not statistically supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central empirical claim is that DPClustX selects attributes of quality within 1-2% of the non-private TabEE baseline at ε=0.1. However, all results are averaged over 10 runs with no standard deviations, confidence intervals, or significance tests. At ε=0.1, the reported gap for Diabetes is 0.66%; with 10 runs, the standard error could easily exceed this, making the gap statistically indistinguishable from zero. The same issue affects the comparison to DP-Naive (20% gap), where the gap is large, but the 'comparable to TabEE' claim specifically rests on small differences that may be noise. Furthermore, Figure 8b shows a 20% degradation at an average cluster size of 2035, but without error bars we cannot tell whether this degradation is significant or overlaps with the performance at larger clusters. If the 1-2% differences are not significant, the conclusion that DPClustX provides 'insightful and accurate explanations' under tight privacy is not supported by the experiments.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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%.","tokens_in":44483,"tokens_out":9219,"duration_ms":100088,"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":[{"comment":"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.","section":"§5.1, Proposition 5.1(2), and §A.5"},{"comment":"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.","section":"§6.2, Figures 5 and 8b"},{"comment":"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.","section":"§6.2, 'Selected attributes quality score' and 'Quality for different cluster sizes'"}],"minor_comments":[{"comment":"The Jensen–Shannon divergence formula writes H(q) twice; it should be 1/2 H(p) + 1/2 H(q).","section":"Appendix A.1, Definition A.4"},{"comment":"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.","section":"Appendix A.4, Proposition 4.14 proof"},{"comment":"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.","section":"§6.1, baseline description"},{"comment":"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.","section":"§6.2, MAE definition"},{"comment":"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.","section":"§6.1 and §6.2, budget terminology"}],"recommendation":"major_revision","confidential_remarks":"The paper is relevant and original for a data-management or privacy venue. The unresolved utility-proof mismatch and the missing statistical rigor in the experiments are the main barriers; both are fixable within the manuscript's scope, so I would not recommend rejection. I would also ask the editor to have the 'first framework for DP clustering explanations' claim checked carefully against recent literature on DP explanation mechanisms, since the related-work section focuses on ML explanations and may not cover all relevant systems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. This is the first framework I know of that gives differentially private histogram-based explanations for clustering results, and the privacy story is basically sound. The second thing is that the utility proof for the candidate-selection stage doesn't match the actual mechanism, and the experimental headline numbers come without error bars. Both are fixable, but they are real.\n\nWhat's actually new: they replace the sensitive interestingness/sufficiency/diversity scores from the non-private TabEE line of work with low-sensitivity variants (Int_p, Suf_p, Div_p) whose sensitivity is bounded by 1, and they design a two-stage private selection: one-shot Gumbel top-k per cluster, then an exponential mechanism over combinations, then private histograms only for selected attributes. The sensitivity proofs in the appendix check out, and the overall (eps_CandSet + eps_TopComb + eps_Hist)-DP composition is correct. Ranking equivalence with the original quality functions is proven, not assumed, which is a real asset.\n\nThe softer spots. Proposition 5.1(2) claims a per-rank utility bound for the one-shot top-k mechanism, but the proof in A.5 assumes the output distribution is identical to iteratively applying k exponential mechanisms. For one-shot Gumbel top-k that equivalence is not established in the cited Durfee-Rogers work; the distributions actually differ because the one-shot mechanism uses fixed Gumbel draws rather than re-sampling after each selection. The privacy claim still holds, but the stated utility bound is unsupported as written. They should either prove the per-rank bound directly for the Gumbel mechanism or state the standard joint bound with the larger log(|A| choose k) term.\n\nThe experiments: all numbers are averages over 10 runs with no error bars. At eps=0.1 the reported gap to the non-private baseline is often under 1%, and with 10 runs the standard error can easily exceed that. The overall trend across datasets and methods is consistent, so I don't doubt the qualitative conclusion, but the specific 'comparable to TabEE' claim needs standard deviations or confidence intervals before it carries the weight they put on it. The cluster-size limitation is honestly reflected in Figure 8b, though it could be stated as an explicit assumption.\n\nWho this is for: anyone building privacy-preserving data-exploration or explanation tools; it is a useful capability, not a reshaping. It deserves a serious referee. I'd send it out, but ask for the utility analysis to be corrected and the experimental claims to be backed by error bars. With those changes it would be a solid contribution.","headline":"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.","tokens_in":45020,"tokens_out":4591,"would_cite":true,"duration_ms":50471,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["differential privacy","clustering explanations","histogram-based explanations","low-sensitivity quality functions","exponential mechanism","one-shot top-k selection","black-box clustering","private attribute selection"],"falsifier":"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.","tokens_in":75,"feed_emoji":"🔒","tokens_out":10358,"duration_ms":162063,"temperature":0.7,"pith_summary":"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.","feed_headline":"Private cluster explanations stay within 2% of non-private quality","feed_subtitle":"Rescaled scores with sensitivity 1 let it match the non-private baseline's attributes at budget ε=1.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The non-private TabEE baseline whose quality functions the paper adapts, and the baseline the experiments compare DPClustX against.","marker":"[8]"},{"why":"The one-shot top-k mechanism that Stage-1 builds on; its privacy and utility properties anchor Proposition 5.1.","marker":"[15]"},{"why":"The exponential mechanism used in Stage-2 to select the private global attribute combination.","marker":"[47]"},{"why":"Supplies the composition theorems, the sensitivity definition, and the exponential-mechanism utility bound (Theorem 3.11) used throughout the proofs.","marker":"[19]"},{"why":"The faithfulness/sufficiency framework whose sufficiency notion the paper adapts into the low-sensitivity $\\mathrm{Suf}_p$ score.","marker":"[10]"},{"why":"The Geometric mechanism used as the DP histogram generator in the experiments.","marker":"[26]"},{"why":"The Diabetes dataset on which the main quality and identity-of-selection results are demonstrated.","marker":"[7]"},{"why":"The US Census dataset used to show the framework scales to roughly 2.5 million tuples.","marker":"[49]"}],"fun_headline_variants":["Private cluster explanations within 2% of non-private quality","Sensitivity-1 scores enable private cluster explanations","DP explanations match non-private ranking at ε=0.1","Histogram-based cluster explanations privatized, quality holds","Tight DP budget: cluster explanations stay accurate"],"cache_read_input_tokens":47232,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Private cluster explanations within 2% of non-private quality","Sensitivity-1 scores enable private cluster explanations","DP explanations match non-private ranking at ε=0.1","Histogram-based cluster explanations privatized, quality holds","Tight DP budget: cluster explanations stay accurate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000271,"raw_usage":{"total_tokens":1696,"prompt_tokens":1080,"completion_tokens":616,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":539}},"tokens_in":696,"tokens_out":616,"duration_ms":6785,"temperature":1.0,"reasoning_tokens":539,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:13:40.421900+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The non-private TabEE baseline whose quality functions the paper adapts, and the baseline the experiments compare DPClustX against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The one-shot top-k mechanism that Stage-1 builds on; its privacy and utility properties anchor Proposition 5.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The exponential mechanism used in Stage-2 to select the private global attribute combination."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The faithfulness/sufficiency framework whose sufficiency notion the paper adapts into the low-sensitivity $\\mathrm{Suf}_p$ score."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Geometric mechanism used as the DP histogram generator in the experiments."}],"review_version":1}