acceptodds
Under review as a conference paper at ICLR 2027

Are you dense? Incorporating Density-based Structures in Explainable Clustering

Abstract

Explainable clustering methods have focused almost entirely on centroid-based reference clusterings with mostly convex cluster shapes. However, many real-world datasets contain clusters of non-convex, arbitrary shapes that are typically found with density-based clustering methods. We address this gap with our novel explainability framework **LUCID** (exp**L**aining cl**U**ster stru**C**tures v**I**a **D**ensity-aware trees). LUCID explains a given density-based clustering by fitting an interpretable tree over its density-connectivity structure, combining sparse feature rules with a case-based explanation for structure no such simple rule can separate. We demonstrate LUCID's applicability in extensive experiments, highlighting its necessity for density-based reference clusterings and datasets containing density-connected structures.

Primary area:
interpretability and explainable AI
Keywords:
explainable clustering, unsupervised learning, density-connectivity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_xYKEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces LUCID, a framework that constructs a global explanation tree for a given reference clustering by leveraging density-based connectivity distances, the Minimum Spanning Tree (MST) of a mutual reachability graph, and single-linkage hierarchical clustering. For each node, the method first identifies a density-respecting binary partition; it then selects an explanatory rule—drawn from a set of linear, symbolic, or connectivity-based rules—by balancing error against model complexity, with a fallback option to partition the data into its constituent maximal clusters when necessary. As the first framework designed for the global explanation of density-based clustering, LUCID reportedly outperforms methods such as SpEx, IMM, CART, and TAO across 67 datasets and five different reference clustering configurations. Evaluation is primarily conducted using metrics including AMI, ARI, DISCO, and DBCV, supplemented by ablation studies, statistical significance testing, and an analysis of node types.

Critical strengths
  1. The problem is clearly defined; while global interpretability for density-based clustering has lacked systematic research, LUCID integrates density-connected hierarchies, interpretation trees, and a set of rules for three types of nodes into a comprehensive framework.

  2. The experimental evaluation is extensive, encompassing 67 datasets, 5 reference clustering methods, and multi-metric assessment. Furthermore, the inclusion of significance testing and parameter ablation studies effectively demonstrates the method's capabilities within the context of density-based clustering.

  3. The paper provides conditions for "exact recovery" and discloses implementation details, ensuring strong reproducibility and serving as a valuable reference for future comparative studies.

Critical weaknesses
  1. The novelty of the proposed method is limited, as it primarily consists of a combination of existing components, dc-dist, MST, single-linkage hierarchical clustering, and interpretable trees are not new concepts. The theoretical analysis is restricted to "exact recovery," lacking both approximation guarantees and an assessment of the "price of explainability." Furthermore, the absence of guarantees for "fallback" nodes weakens the methodological contribution.

  2. The experimental advantages may stem from an inherent bias toward density-based structures; LUCID shares either the dc-dist metric or density priors with DBSCAN, HDBSCAN, and SHADE. Its performance is merely comparable to Spectral clustering and shows only marginal improvements over the ground truth. Moreover, the method performs poorly on real-world high-dimensional datasets such as CIFAR and MNIST, making it difficult to claim general effectiveness.

  3. The work suffers from issues regarding interpretability and the fairness of comparisons. The connection rules rely directly on actual data samples and dc-distance thresholds, yet no user studies or readability assessments were conducted. The rule-selection process, which prioritizes minimizing error, may result in the selection of non-intuitive rules. The set of baselines lacks rule-based, prototype-based, or polyhedral methods, and the reference clustering approaches rely on fixed heuristics without hyperparameter tuning. Additionally, the O(n2)O(n^2) memory and quadratic time complexity limit the method's scalability.

Questions for authors
  1. For reference clusterings that do not utilize dc-dist, how can it be demonstrated that the advantages of LUCID do not stem from a shared density prior? Could the evaluation be expanded to include reference methods that are independent of density, as well as baselines based on more robust rule sets?

  2. Beyond the guarantee of "exact recovery," is it possible to provide an upper bound on the approximation error, or at least characterize the worst-case scenario for "fallback" nodes?

  3. How is the human readability of the connection rule, defined as "the dc-dist to an instance zz is less than ϵ\epsilon", evaluated? Are there any user studies or metrics for measuring the complexity of the explanations?

  4. Are the runtime and memory usage reported as functions of nn, dd, and kk? Does the method remain feasible when n>104n > 10^4?

  5. Could the heuristic used to fix the parameters for reference clusterings introduce a bias in favor of LUCID? Would it be possible to ensure a fairer comparison by selecting these parameters through independent tuning or cross-validation?

  6. Given that the "price of explainability" is a key metric for assessing the interpretability of clusterings, why was this not analyzed?

5 comments

Dear Reviewer,

Thank you very much for your helpful feedback.

W1 (novelty): dc-dist, MST, single linkage, and decision trees are existing, and we do not claim them. Our contributions are the problem setting (global explanation of density-based clusterings), density-aware trees that split at a cut in the density hierarchy and explain it with a rule, connectivity rules with their ultrametric-ball property (Lemma 1, Prop. 1), and the empirical study.

W2+Q1 (bias): LUCID performs best on density-based references because it is designed for them, not because the evaluation is biased. Density-based clusterings (DBSCAN, HDBSCAN, SHADE) are defined by density-connectivity rather than by an objective function, and existing explainable-clustering methods were not designed for this setting. IMM and its follow-ups explain centroid-based objectives (k-means/k-median), relying on convex cells around centers. TAO needs a cost function to optimize, and SpEx uses a graph-conductance criterion with axis-aligned cuts. All can run on arbitrary labels, but none is designed for density-connected, non-convex clusters, so they fall behind here.

On a k-means reference (App. G), LUCID is not significantly better than any competitor (AMI 0.820 vs. CART 0.805, IMM 0.811, SpEx 0.814, TAO 0.931), so we restrict the claims in the abstract and conclusion to density-based references.

On real high-dimensional data, LUCID’s lead shrinks with d, which we attribute to degrading reference quality. On new DENSIRED data (d up to 500, App. I), the pooled lead is positive at every d ≥ 20, so dimension alone does not cause the shrinkage seen on real data. Much of the growth at d ≥ 100 comes from the spectral reference. Without it the lead is about +0.02 at d = 100–500, still not a negative trend.

W3 (interpretability): Rule selection is lexicographic by (error, size), so a less direct rule is chosen only if it fits the target strictly better, favoring fidelity. Connectivity rules are harder to read but more expressive. Users can control the trade-off with the feature cap j_max and an added cap on connectivity nodes (one per tree gives AMI 0.916 vs. 0.933 full). An error tolerance δ\delta (take the simplest rule whose error is within δ\delta of the best) lowers the connectivity share from 17.2% to 5.2% (δ\delta = 0.05), while the mean AMI drops from 0.933 to 0.886, so the default (δ\delta = 0) is the best-aligned setting.

Rule-, prototype-, and polyhedral-based methods return per-cluster descriptions rather than a global tree, so we compare within the tree family.

Q2 + Q6 (bound, price of explainability): We have no bound beyond exact recovery and state this as an open problem. The price of explainability is the worst-case ratio between the cost of the best explanation tree and the cost of the reference clustering under a clustering objective such as k-means. Density-based clusterings optimize no such objective, and under our misclassification cost (Definition 1) the reference itself has cost zero, so the ratio is undefined. We thus report differences in DISCO/DBCV as measures for the change in quality.

At fallback nodes (30.75% of splits), where no density-respecting bipartition exists, there is no guarantee, so we characterize behavior empirically (App. I): 44% (729 of 1,655) are reproduced exactly (nodes: 61% linear, 17% signomial, 0% connectivity).

Q3 (readability): A connectivity rule “dc(x, z) < ε\varepsilon” reads: x is connected to the real example z through objects whose mutual-reachability distance stays below ε\varepsilon, i.e., x lies in the dense region around z. App. E prints examples with the feature values of z. We have not run a user study and list this as a limitation. We added the following complexity measures (LUCID/CART/IMM/SpEx/TAO): depth 3.21/2.74/3.24/2.93/1.98; conditions per path 2.35/2.17/2.36/2.24/1.80; distinct features per tree 2.81/2.48/2.35/2.39/45.8.

Q4 (runtime): App. H adds runtime experiments (DENSIRED, 5% noise, HDBSCAN reference). The original implementation spent 76 of 84 s (n = 20k, d = 10) on the n×n dc-distance matrix. An improved implementation computes one exact mutual-reachability MST and derives each node’s dendrogram from its sorted edges, returning identical labels (60/60 runs). At d = 10, n = 5k drops from 3.3 s to 0.45 s, n = 20k from 83.8 s (14.2 GB) to 3.3 s (0.24 GB), and n = 100k takes 46 s (0.54 GB). On real data, Pendigits takes 4.8 s and Beans 2.2 s. CART, IMM, and SpEx are faster than LUCID, and TAO is slower at d = 10 (n = 20k) but faster at d = 50 (2.1 vs. 11.7 s).

Q5 (parameters): We did not tune the references per dataset, so none is tuned toward LUCID. We varied µ_ref (App. G). LUCID’s lead over the best competitor for µ_ref = 2/5/10: DBSCAN +0.055/+0.115/+0.101; HDBSCAN −0.034/+0.071/+0.071; SHADE +0.146/+0.151/+0.150. Only HDBSCAN at µ_ref = 2 shows no advantage.

We did not use cross-validation since the target is a fixed clustering.

Reviewer_xYKEOpenReview ↗

review

Thank you for your reply.

Could you clarify the relationship between your work and interpretable clustering, as well as its connection to the price of explainability? Since the "price" in interpretable clustering is important, and recent work focuse on how to reduce this price.

Thank you for the question and for giving us a chance to clarify this.

LUCID belongs to the family of tree-based interpretable clustering methods (IMM and its follow-ups), but our setting differs slightly. We focus on density-based clustering, which, in contrast to centroid-based clustering, does not assign points to clusters by solving an optimization problem.

In most k-means/k-median interpretable clustering, the goal is a threshold tree whose clustering has low cost under the same objective. The price of explainability is the worst-case ratio between the tree's cost and the optimal clustering's cost. This requires a clustering objective that is not present in the clustering methods we focus on. LUCID thus explains a given clustering post hoc, and we measure how faithfully the tree reproduces it (AMI/ARI, misclassification cost in Definition 1). Under that cost, the reference itself has cost zero, so a cost ratio is undefined. A bound in the price-of-explainability sense would first require a density-based clustering objective, which we consider an open problem and say so in the paper. What we report instead is the difference in clustering quality (DISCO/DBCV) with respect to the density structure, together with how well the tree aligns with the reference clustering (AMI/ARI). DISCO/DBCV can be used in a way similar to a cost or an objective, however, the difference is that both DISCO and DBCV are measures of clustering quality rather than objective functions that the algorithms optimize for.

In the rebuttal, we present two settings to control the resulting interpretability-fidelity tradeoff, i.e., the harder-to-read connectivity rules (lower interpretability) that allow us to capture more of the actual structure (alignment with structure and reference/fidelity): the feature cap and an error tolerance δ in rule selection.

We will add a paragraph to the related work and the limitations explaining this distinction. We hope that our answer could clarify your question, and we are happy to answer any further questions you may have!

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

The paper introduces LUCID, an explainable clustering algorithm for density-based clustering. The authors, motivated by prior work on explainable clustering, define their explanation tree to be a decision tree that aims to approximate a reference clustering, such that each internal node uses a "simple" rule to split the data to its left and right child.

LUCID is a top-down algorithm that starts with the root of the tree containing all non-noise points and while there are "splittable" nodes, i.e. nodes that contain at least 2 labels, it splits them using a cut, until there are k leaves. To split a node, the algorithm sets a target split and then fits a "simple" rule to approximate this split. To select the target split, a "density-respecting" split is used, if such exists, otherwise the largest cluster in the node is separated from the rest. Then, the authors consider 3 types of rules: linear, signomial and connectivity rules. The linear and signomial rules are forced to use a small number of features to ensure explainability. To select which rule to use, the candidate rules are prioritized according to error first and then according to the number of features used by the rule. Moreover, in case of ties, simpler rules are used (e.g. linear instead of signomial).

The paper offers limited theoretical guarantees and extensive experiments on synthetic and real datasets. The experiments show that LUCID usually uses linear rules and it outperforms other explainable clustering algorithms on density-based reference clusterings.

Critical strengths
  • The paper introduces a global explanation method for density-based clustering, which is an original and interesting question.
  • The paper includes extensive experiments for both synthetic and real datasets, showing that LUCID outperforms other methods for density-based reference clusterings in terms of AMI and ARI.
  • Most internal nodes created in the experiments use simple axis-aligned splits and sparse linear hyperplanes.
Critical weaknesses
  • It is not clear why the LUCID clustering is explainable. For example, the axis-aligned splits performed by the IMM algorithm induce simple explanations that are the paths from the root to the leaf of the tree. Here, it is not immediately clear why signomial splits and especially connectivity splits are explainable. In the experiments, it is reported that only connectivity rules account for about 17% of the internal nodes, which is not negligible (about 1 out of 6 nodes). It would be, perhaps, more interesting if connectivity nodes were about 1-5%.
  • The theoretical results are limited. The exact recovery corollary seems trivial, when allowing connectivity nodes and assuming that the reference clustering has this exact form.
  • Clarity issue: In the definition of density-respecting bi-partitions, it reads that each node in T separates the reference clusters it contains in 2 groups such that one is the complement of the other. This is confusing, because even the LUCID tree sometimes separates data points from other points in their cluster, meaning that the labels of the left and right child would not be disjoint. (There are other minor issues like incomplete sentences and typos).
Questions for authors
  • Can the authors describe how the LUCID explanations would look like and why they think they would be understandable by humans?
  • Do the authors know of any non-trivial trade-off between the number of connectivity nodes allowed and the alignment of the LUCID clustering with the reference clustering? For instance, can you lower the number of connectivity nodes while still outperforming the other explainable clustering algorithms?
  • Is it possible that the improved performance of LUCID compared to the other algorithms for density-based reference clusterings is explained by allowing it to use very expressive yet complicated partitions?
2 comments

Dear Reviewer,

Thank you very much for your constructive feedback.

W1 (explainability): We agree that signomial and especially connectivity rules are less direct than threshold nodes. A signomial rule is a power law (a product or ratio of a few features); a connectivity rule explains by example: x lies in the dense region around a real object z, up to level ε\varepsilon. We use them only where no feature rule with at most three features is as accurate, so connectivity nodes mark exactly the splits no sparse feature rule reproduces. Examples are in the revised appendix.

We agree that the 17% of connectivity splits is not negligible. However, 65.4% of the 1,424 trees contain none, and one connectivity node per tree already gives AMI 0.916 (0.933 unlimited). We also added new experiments where we tested two ways to lower the percentage:

  • More features per rule helps little for d≤64d\leq 64 (18.4% with three features, 16.7% with twelve) but a lot for d>64d>64 (26.6% with one feature, 2.7% with twelve, at 91% exact splits).
  • An error tolerance δ\delta (choose the simplest rule within δ\delta of the best error) lets users trade interpretability for fidelity: δ\delta= 0.01/0.02/0.05 lowers the share from 17.2% to 10.2%/7.9%/5.2%, while pooled AMI falls from 0.933 to 0.913/0.900/0.886 and the lead over the best competitor from +0.063 to +0.044/+0.031/+0.016. A 1–5% share is thus possible, at a clear cost in alignment.

W2 (theory): Corollary 1 is a consistency result: if every reference cluster is a node of the density-connectivity hierarchy (e.g., DBSCAN* without noise), the construction recovers it exactly. Its substance lies in Proposition 1 and the ball lemma, which show that a connectivity rule can realize any density-respecting target. We reworded it and removed any suggestion of a stronger guarantee. The price of explainability is undefined here: density-based clusterings optimize no classic objective, and the reference has cost zero under our misclassification cost.

W3 (clarity): Thank you for pointing this out. The bipartition (SvS_v, complement) in Sec. 3.2 partitions the cluster labels at node vv, so it is disjoint by definition and defines the target yvy_v. The rule then routes objects and may misroute some, measured by errverr_v. We rewrote the paragraph, state that at fallback nodes the target splits off the plurality cluster, and minor issues.

Q1 (explanations): We add printed trees to App. E. Iris (ground truth, AMI 0.948) needs one threshold, petal_length < 2.45, and one three-feature linear rule. Pendigits with a DBSCAN reference (AMI 1.000; best baseline ≤\leq 0.576) needs three connectivity rules and one linear rule. A connectivity rule reads: “x belongs to the dense region around example z (feature values listed), i.e., its dc-distance to z is below ε\varepsilon.” For each connectivity node, we also add (1) the features in which the cut-out region B differs most from the node’s other points and (2) the best sparse feature rule and its error (e.g., Pendigits node 0: 48 of 10,950 points, best three-feature rule misclassifies 14). Readers thus get the exact rule plus a feature description and an approximate rule to read alongside it.

Q2/Q3 (trade-off): Most of the gain comes from connectivity rules: they depend on all d features, thus capturing density structure that sparse feature rules miss, but are harder to read. LUCID selects it only when no short feature rule reproduces the split as well, which happens at 17.2% of splits. They trade interpretability for fidelity (AMI/ARI). To make the trade-off explicit, we add a cap: each connectivity split allowed costs interpretability and buys fidelity. With a cap mm on connectivity splits per tree (1,424 trees in total), the pooled mean AMI and the mean AMI difference to the per-run best competitor are:

Cap mm012unlimited
Pooled mean AMI (CART 0.849, IMM 0.832, SpEx 0.837)0.8140.9160.9250.933
Pooled, difference to best competitor-0.056+0.047+0.056+0.063
HDBSCAN-0.044+0.056+0.064+0.071
DBSCAN+0.001+0.104+0.110+0.115
DPC-0.019+0.021+0.027+0.027
SHADE+0.002+0.144+0.149+0.151
Ground truth-0.062+0.008+0.017+0.032
Spectral-0.163-0.042-0.026−0.009

With $m= $, only 493 instead of 927 connectivity splits are used (0.35 vs 0.65 per tree on average, median 0 throughout), and 85% of the gain over m=0m=0 is retained. So yes: the number of connectivity nodes can be lowered while still outperforming the baselines on density-based references (p<1e−4p<1e-4 pooled for m≥1m ≥ 1). This does not hold everywhere: on ground truth the difference is not significant for m ≤ 2, and on spectral references, LUCID stays below the best competitor for m ≤ 2.

We will add this discussion, with δ\delta and mm.

I thank the authors for their detailed answer and effort to address my concerns. In my view, the paper does not offer a convincing notion of explainability for density-based clusterings. Instead, the authors discover a (non-trivial) tradeoff between explainability and accuracy: LUCID trees can explain large parts of density-based clusterings with simple or almost simple rules, while allowing almost unintelligible nodes when using any simple rule would increase the cost significantly. I think the paper would benefit from a reframing of the purpose of LUCID to highlight this tradeoff. Moreover, I agree with reviewer xYKE, that a well-defined price of explainability would make the paper more interesting and I believe that a more convincing definition of density-based explainability would improve the paper. I would also view the results as stronger, if a stronger theoretical result was also proved. For these reasons, I will retain my score.

Reviewer_ojBXOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This study proposes LUCID as a post-hoc approach for explaining a density-based cluster assignment by an “interpretable tree” over its density-connectivity structure. Given a pre-computed cluster assignment, it separates clusters by cutting a dc-dist dendrogram built on a mutual-reachability MST. It then explains each split with a rule that is “linear” (hyperplanes), “signomial” (hyperplanes in log space), or “connectivity-based” otherwise (dc-dist below some threshold, for arbitrary split geometries). The resulting nodes are assembled into a binary tree that can be seen as an “explanation” of the global spatial structure between clusters. The approach is tested on 67 datasets and six reference clusterings (ground truth, DBSCAN, HDBSCAN, DPC, SHADE, and spectral), and compared against CART, IMM, TAO, and SpEx (axis-aligned and oblique baselines). Results suggest that LUCID matches the reference clustering more closely than the competing methods, with significant gains for density-based references, while being the only method that preserves the density structure of the reference.

Critical strengths

A global density-based clustering explanation method built for a setting that existing tree-based methods do not cover. On non-convex structures, it shows clear gains over the competitors (e.g., cb_spiral, cb_chainlink, two_moons and coil20 in Table 11).

Critical weaknesses

Motivation and usefulness. The paper does not fully answer why global explanations of density-based clusterings are needed, what the problem is of not having them, and what LUCID brings in practice. More concretely, it does not describe how a practitioner should use a LUCID tree and offers no concrete real-world example. Specifically, no printed tree with rules in the original features of any real dataset, no description of how a connectivity rule is read by a user or how it classifies a new point, and no evaluation of interpretability beyond rule-type counts. It is therefore unclear to what extent LUCID provides a labeling together with the “reasoning behind it”, and how a signomial rule (for example) might be useful in practice.

Questions for authors
  1. Based on Table 11, AMI performance drops on higher-dimensional datasets, or at least offers no gain over the other methods (e.g., digits, wine, beans, olivetti, cifar10). Could the authors include a short analysis of the effect of dimensionality on alignment, while controlling for reference DISCO? Also, when high-dimensional data are reduced by PCA, is there any way to interpret the resulting split rules given the feature-space transformation? In other words, what is a user is meant to read from, e.g. a three-feature linear rule on principal components?

  2. Could the authors provide an interpretation of the dc-dist when it is first introduced, and briefly state which ultrametric properties the method relies on? Since it is central to the method, this would help readers who are not already familiar with it.

  3. The abstract is excessively condensed and does not say what LUCID explains or how. Vague terms such as "interpretable tree", "sparse feature rules", "case based explanation" do not help understand the contribution on a first read. “Extensive experiments” should be specified together with the main quantitative result. The closing claim that the experiments highlight LUCID’s “necessity” is not supported by anything stated in the abstract. Could the authors revise it to improve undertstanding?

  4. HDBSCAN’s condensed cluster tree and the OPTICS reachability plot already describe the hierarchical relationship between density-based clusters, but neither is discussed as an explanation. Could the authors explain what LUCID provides beyond these structures (presumably the description of each separation in terms of features), and state this in the introduction?

  5. LUCID’s splits come from the same mutual-reachability hierarchy from which HDBSCAN extracts its clusters and of which DBSCAN* clusters are nodes (Lemma 2), so the AMI of 1.00 on these references (Figure 3) appears to be largely guaranteed by construction. Could the authors confirm whether HDBSCAN uses the same µ as LUCID (Appendix B), discuss this overlap in Section 4.2, and report alignment with connectivity rules disabled to show how much of the advantage comes from the feature rules?

2 comments

Dear Reviewer,

Thank you very much for your suggestions to help us improve our paper.

W1 (motivation): We will revise the introduction accordingly. Density-based clusters are defined by reachability through dense regions. Because LUCID explains a given clustering rather than predicting one, it needs no assignment function. Its explanations describe how the given clusters differ, for example, by identifying a single feature that yields a linear cut between them. We add printed-tree examples to Appendix E.

Connectivity rules act as example-based explanations: they identify a specific data point that is density-connected to the original point, so the explanation accounts for the data’s density. We agree that connectivity rules are harder to interpret than, e.g., linear rules, and we thus use them only when no feature rule is expressive enough to capture the information. This is a trade-off between interpretability and fidelity (measured with AMI/ARI): connectivity rules are more difficult to read but more expressive.

Q1 (dimensionality):
LUCID’s AMI gap to the best competitor shrinks with growing dimensionality in the initially included high-dimensional datasets. We attribute this to the degrading quality of the reference clustering rather than to a property of LUCID. To check that dimension alone is not the cause, we generated new DENSIRED data with d∈{20,50,100,200,500}d \in \{20, 50, 100, 200, 500\} (App. I). The clusters stay density-connected (ground-truth DISCO rises from 0.72 at d=2d = 2 to 0.97 at d=500d = 500), and LUCID's AMI is 0.97 to 1.00 at every d. Its lead over the best competitor, pooled over all six references, does not shrink: +0.005 (d=20d = 20), +0.016 (50), +0.073 (100), +0.079 (200), +0.077 (500). We will add these results to the revision.

We agree that the PCA components limit the interpretability of the clustering. We will remove them in the revision, as they add little to the analysis.

Q2 (dc-dist): We revised the introduction of the dc-distance accordingly. Intuitively, it is the smallest density level ε at which x and y are connected by a chain of core points, i.e., the smallest ε\varepsilon at which they would be assigned to the same DBSCAN cluster.

In Section 3.2, we will add the ultrametric properties our method relies on: (i) the ball property: every ball {x : dc(x, z) < ε\varepsilon} is a dendrogram node (Lemma 1), so connectivity rules do not depend on which member z is reported and correspond to exact dendrogram nodes (Proposition 1); (ii) closure under restriction: the dc-distance on any subset is again an ultrametric, so nodes can reuse the distances without recomputation.

Q3 (abstract): Thank you for pointing this out. We rewrote the abstract to state that LUCID explains a given clustering with a binary tree whose splits are derived from the density-connectivity hierarchy and added clarification about how the nodes work.

Q4 (HDBSCAN and Optics): The condensed tree and the reachability plot show the hierarchy of density levels over the data objects. However, they do not indicate which features separate two branches, and their branches are not tied to a given reference clustering (e.g., DPC, SHADE, or ground truth). LUCID builds on the same hierarchy but, at each node, selects the split that separates the reference clusters and explains it with a rule. We will add this discussion to the revision.

Q5 (parameters): HDBSCAN and LUCID do not use the same μ\mu, hdbscan with min_samples=5 uses the 5th nearest neighbor excluding the point, which is μ=6\mu=6 in LUCID's convention (μ=5\mu=5 is the 4th neighbor). With the matching convention (min_samples=4) LUCID's AMI is 0.996 and its lead over the best baseline +0.077. We varied the reference's parameter (App. G): for μref=5\mu_{ref}=5 and 10 the lead is +0.071 and significant against all four baselines; for μref=2\mu_{ref}=2 it is -0.034, i.e., the advantage vanishes when the reference is less smoothed than LUCID's dc-distance.

Corollary 1 guarantees exact recovery for DBSCAN* clusterings without noise, but it does not cover our DBSCAN and HDBSCAN references. DBSCAN has border points, and noise is removed before the dc-distance is computed; HDBSCAN extracts clusters by stability rather than from a single cut. Near-perfect alignment on these references is nonetheless expected and is a design choice.

Pooled over 1,424 runs:

LUCIDLUCID without connectivityCARTIMMSpExTAO
AMI0.9330.8140.8490.8320.8370.764

Without connectivity rules, LUCID no longer beats CART, IMM, or SpEx on the pooled results and is worse on spectral and ground-truth references. It still beats TAO and remains on par or slightly above on DBSCAN and SHADE. The advantage over axis-aligned baselines therefore comes from the connectivity rules. This is the interpretability tradeoff, which users could adjust when allowing for some error during the fitting process.

Reviewer_ojBXOpenReview ↗

Review

I sincerely thank the authors for their response and the efforts to address my concerns. Despite this, I think the paper remains below the acceptance bar for ICLR. In particular, I think the proposed method has limited applicability and usefulness as an interpretability tool. For this reason, I will maintain my original rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.