Hierarchical and Density-based Causal Clustering
Authors: Kwangho Kim
Jisu Kim
Larry Wasserman
Edward Kennedy
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal inference
Heterogeneous treatment effect
Personalization
Subgroup analysis
Observational studies
Primary area: causal_inference

Abstract: Understanding treatment effect heterogeneity is vital for scientific and policy research. However, identifying and evaluating heterogeneous treatment effects pose significant challenges due to the typically unknown subgroup structure. Recently, a novel approach, causal k-means clustering, has emerged to assess heterogeneity of treatment effect by applying the k-means algorithm to unknown counterfactual regression functions. In this paper, we expand upon this framework by integrating hierarchical and density-based clustering algorithms. We propose plug-in estimators which are simple and readily implementable using off-the-shelf algorithms. Unlike k-means clustering, which requires the margin condition, our proposed estimators do not rely on strong structural assumptions on the outcome process. We go on to study their rate of convergence, and show that under the minimal regularity conditions, the additional cost of causal clustering is essentially the estimation error of the outcome regression functions. Our findings significantly extend the capabilities of the causal clustering framework, thereby contributing to the progression of methodologies for identifying homogeneous subgroups in treatment response, consequently facilitating more nuanced and targeted interventions. The proposed methods also open up new avenues for clustering with generic pseudo-outcomes. We explore finite sample properties via simulation, and illustrate the proposed methods in voting and employment projection datasets.

Hierarchical and Density-based Causal Clustering
Kwangho Kim Korea University kwanghi@korea.acco
Jisu Kim
Seoul National University 5kim82133@snu. ac.kr
Larry A. Wasserman Carnegie Mellon University larryestat. cmu, edu
Edward H. Kennedy Camegiee Mellon University edward cmu. edu
Abstract
Understanding treatment effect heterogeneity is vital for scientific and policy re- search. However, identifying and evaluating heterogeneous treatment effects pose significant challenges due to the typically unknown subgroup structure. Recently, a novel approach, causal k- k-means clustering, has emerged to assess heterogeneity treatment effect by applying the k-means algorithm to unknown counterfactual regression functions. In this paper, we expand upon this framework by integrating hierarchical and density-based clustering algorithms. We propose plug-in estima- tors which simple and readily implementable using off-the-shelf algorithms. Unlike k-means clustering, which requires the margin condition, our proposed estimators do rely strong structural assumptions on the outcome process. We go on to study their rate of convergence, and show that under the minimal regularity conditions, the additional cost of causal clustering essentially the estimation emror of the outcome regression functions. Our findings significantly extend the capabil- ities of the causal clustering framework. thereby contributing the progression of methodologies for identifying homogeneous subgroups in treatment response, consequently facilitating more nuanced and targeted interventions. The proposed methods also open up new avenues for clustering with generic pseudo-outcomer We explore finite sample properties via simulation, and illustrate the proposed methods in voting and employment projection datasets.
Introduction
1.1 Heterogeneity of Treatment Effects
Causal effects are typically summarized using population-level measures, such as the average treat- ment effect (ATE). However, these summaries may be insufficient when treatment effects vary subgroups. For example, finding the subgroups that experience the least or greatest benefit from a specific treatment of partieular importance in personalized medicine policy evaluation, where the subgroup effects of interest may diverge significantly from the population effect. Even while experiencing the same treatment effects, some people may have been exposed to significantly higher baseline risk. In the presence of effect heterogeneity, the typically unknown subgroup structure poses significant challenges in accurately identifying and evaluating subgroup effects compared to population- effects.
To delve deeper than the information provided by the population summaries and better understand treatment effect heterogeneity, investigators often estimate the conditional average treatment effect (CATE) defined by
E y | X),
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

where Y is the potential outcome that would have been observed, possibly contrary to fact, under treatment A a, and X X' is a vector of observed covariates. The estimation of the CATE has the potential to facilitate the personalization of treatment assignments, taking into account the characteristics of each individual. Admittedly, the CATE the most commonly-used estimand to study treatment effect heterogeneity. Various methods have been proposed to obtain accurate estimates of and valid inferences for the CATE, with a special emphasis in recent years on leveraging
the rapid development of machine learning methods [e.g.. 3 20 21 27
35
42
46
52
53 58 62).
Subgroup analysis has been the most common analytic approach for examining heterogeneity of treatment effect. Selection of subgroups reflecting one's 's scientific interest plays central role in the subgroup analysis. Statistical methods aimed at finding such subgroups from observed data have been termed sub subgroup discovery [4]. The selection of such subgroups may be informed by mechanisms and plausibility (e.g., clinical judgment), taking into account prior knowledge of treatment effect modifiers. They could be chosen by directly subsetting the covariate space, often in one- -er-variable-at- a-time fashion le.g.. 49. Most existing studies on data-driven subgroup discovery identify subgroups where the CATE exceeds prespecified threshold of clinical relevance, allowing researchers to prioritize subgroups with enhanced efficacy or favorable safety profiles [e.g.. [
44
47 51 63).
Some recent advances proposed heuristics for discovering rules based specific CATE estimator subject to a certain optimality criterion, yet without any theoretical exploration [e.g.. 8. 15 23 48)
Wang and Rudin [59] proposed an algorithm to automatically find subgroup based on the causal rule: (CATE >> ATE). Kallus [1I] proposed a subgroup partition algorithm for determining a subgroup structure that minimizes the personalization risk.
1.2 Causal Clustering
In contrast to earlier work predominantly focused on supervised learning approaches, there is a grow- ing interest in analyzing heterogeneity in causal effects from an unsupervised learning perspective, particularly within the causal discovery literature. Based on the causal graph structural causal model framework, there has been a series of recent attempts to learn structural heterogeneity through clustering analysis [c.g.. 25..g..5_000 26 45). Conversely, the exploration of treatment effect heterogeneity in the potential outuomm//cummeerfcctuull framework using unsupervised learning methods has received significantly less attention. To our knowledge, only one paper has developed such methods; Kim et al. (39 have proposed Causal k-Means Clustering, a new framework for exploring heterogeneous treatment effects leveraging tools from cluster analysis, specifically k-means clustering. It allows one to understand the structure of effect heterogeneity by identifying underlying subgroups as clusters without imposing a priori assumptions about the subgroup structure.
To illustrate, we consider binary treatments and project sample onto the two-dimensional Euclidean space Y | x]. EE X]). It is immediate to see that closer units are more homogeneous in terms of the CATE, which provides vital motivation for uncovering subgroup structure via cluster analysis on this particular counterfactual space. (See (a) & (e) in Figure []. This approach has the capability to uncover complex subgroup structures beyond those identified by CATE summary statisties or histograms. Moreover, it holds particular promise in outcome- wide studies featuring multiple treatment levels [56] 57]. because instead of probing a high digeesinnnsional CATE surface to assess the subgroup structure, one may attempt to uncover dimensionli clusters with similar responses to a given treatment set.
However, the method proposed by Kim et al. 39 only applies to k-means clustering. Despite is popularity, k-means has some drawbacks. It works best when clusters are at least roughly spherical. also has trouble clustering data when the clusters are of varying sizes and density, or based on non-Euclidean distance. Furthermore, the cluster centers (centroids) might be dragged by outliers, or outliers might even get their own cluster. Other commonly-employee clustering algorithms, particularly hierarchical and density-based -baee approaches, could mitigate some of these limitations [ 1 [2 29 40]. Density-basee -bsee clustering is applicable for identifying clusters of arbitrary sizes and shapes, while concurrently exhibiting robustness to noise and outlier data points. Hierarchical clustering proves beneficial in scenarios where the data exhibit a nested structure or inherent hierarchy, irrespective of their shape, and can accommodate various distance metrics. It enables for the creation of a dendrogram, which provides insights into the interrelations among clusters across multiple levels of granularity. Figure I illustattees the three methods in the causal clustering framework with

---

00000
te
e01
(a) Sample
(b) k-Means
(c) Hierarchical
(d) Density
(c) Sample 2
(f) k-Means
(g) Hierarchical
(h) Density
Figure I: Two instances which the three clustering techniques result distinct subgroups for the projected sample. The grey dotted diagonal line indicates treatment effects.
binary treatments, where hierarchical and density-based clustering methods produce more reasonable subgroup patterns.
In this work, we extend the work Kim et al. [39 by integrating hierarchical and density- based clustering algorithms into the causal clustering framework. We present plug-in estimators which are simple and readily implementable using off-the-shelf algorithms. Unlike k k-means clustering, which requires the margin condition [39], proposed estimators do not rely such strong structural assumptions on the outcome process. We study their rate of convergence, and show that under the minimal regularity conditions, the additional cost of causal clustering essentially the estimation етrоr of the outcome regression functions. Our findings significantly extend the capabilities of the causal clustering framework, thereby contributing the progression of methodologies for identifying homogeneous subgroups in treatment response, consequently facilitating more nuanced and targeted interventions. In a broader sense, causal clustering may be construed as nonparametric approach to clustering involving unknown functions, a domain that has received far less attention than conventional clustering techniques applied fully observed data, notwithstanding its substantive importance. Therefore, the proposed methods also open up new avenues for clustering with generic pseudo-outcomes that have never been observed, or have been observed only partially.
Framework
Following Kim et al. 139 we consider random sample (Z1,.., Zn) of n tuples Z = (Y, AX where Y E IR represents the outcome, A A = {1,..., 4 denotes an intervention with finite support, and E X C Rd comprises observed covariates. For simplicity, we focus on univariate outcomes, although our methodology can be easily extended to multivariate outcomes. Throughout, we rely on the following widely-used identification assumptions:
Assumption C1 (consistency). Y Y if A
Assumption C2 (no unmeasured confounding). A I L
Assumption C3 (positivity). P(A = X) is bounded away from 0 a.s. [P]
For A, let the outcome regression function be denoted by
(X) = E(Y X) E(Y
= a).
Then, the pairwise CATE can be consequently defined as Tao (X) = pa (X) pa (X) for any pair
a' E A. The conditional counterfactual mean vector μ X' + 129 projects unit characteristic onto q-dimensional Euclidean space spanned by the outcome regression functions {
x(X)= = [14 (X), [
(1)
3

---

Adjacent units in the above counterfactual mean vector space would have similar responses to a given set of treatments by construction. If all coordinates of a point p(X) are identical for given X, indicates the absence of treatment effects on the conditional mean scale. Hence, conducting cluster analysis on the transformed space by 14 allows for the discovery of subgroups characterized by a high level of within-cluster homogeneity in terms of treatment effects. Crucially, standard clustering theory is not immediately applicable here since the variable to be clustered is μa, a set of the unknown regression functions that must be estimated. We let {Ta} be some estimators of {ua). In Sections 3 and we analyze the nonparametric plug-in estimators for hierarchical and density-based causal clustering, respectively, where we estimate each pea with flexible nonparametrie methods and perform clustering based on p = (f......Pg))
It is worth noting that can be easily customized for specific need through reparametrization, without affecting our subsequent results. For example, it is possible that the difference in regression functions may be more structured and simple than the individual components [e.g., [3] 35 In this case, a parametrization such as μ = (f2 - 111 -1,...) could render our clustering task easier by allowing us to harness this nontrivial structure (e.g., smoothness or sparsity) [see] 39 Section 2].
Notation. We use the shorthand ((0) = (x())) and (0 m(x.) = [ (X,), (x))...,7,(((,))) (X.)) We let | denote Lp norm for any fixed vector x. For a given function f and r E N. we use the notation II. = [P(())) =
as the I., (To) of f. We use the shorthand an S 6n to denote an S cbn for some universal constant c >> 0. Further, for
ES and any real number r > O, we let B(x,, r) denote an open ball centered at x with radius r with respect to L2 norm, i.e. r(x,r) = (y E IR9 || vlla < <) and use the notation B(x,, r) for the closed ball. Lastly, we use the symbol = to denote equivalence relation between two notationally distinct quantities, especially when introducing simplified notation.
3 Hierarchical Causal Clustering
Hierarchical clustering methods build a set of nested clusters at different resolutions, typically represented by a binary tree or dendrogram. Consequently, they do not necessitate a predetermined number of clusters and allow for the simultaneous exploration of data across multiple granularity levels based on the user's preferred similarity measure. Moreover, hierarchical clustering can be performed even when the data is only accessible via pairwise similarity function. There are two types of hierarchical clustering: agglomerative and divisive. The agglomerative approach forms a dendrogram from the bottom up. finding similarities between data points and iteratively merging clusters until the entire dataset unified into single cluster. The divisive approach employs a top-down strategy, whereby clusters are recursively partitioned until individual data points are reached. Here we only consider the agglomerative approach which is more common in practice [6]]. We remark that the similar argument in this section may be applicable to the divisive approach as well.
Consider distance or dissimilarity between points, i.e., d R9 x R + 10, 1]. As in previous studies le.g.. 14 16 30, we extend d so that we can compute the distance, or linkage, between sets of points (p) = S and S2(H) = S2 in the conditional counterfactual mean vector space as D(S,, S2). There are three common distances between sets of points used in hierarchical clustering: letting Ni be the number of points in Sj and similarly for N2. we define the single, average, and complete linkages by min,, ES ES.. S. d(s), 82), N,No Σx, ES d(s). and max,, ES1.52E8, d(s), 82). respectively. Single linkage often produces thin clusters while complete linkage is better at spherical clusters. Average linkage in between. Causal clustering entails estimating the nuisance regression functions {pa F. which necessitates the following assumption.
Assumption A1. Assume that either (i) }na} and {Ta} are contained in a Donsker class, or (ii) { is constructed from a separate independent sample of same size.
Assumption A1 is required essentially because in our estimation procedure, we use the sample twice, once for estimating the nuisance functions {Pa} and again for determining the clusters. One may use the full sample if we restrict the flexibility and complexity of each P. through the empirical process conditions, as in (i), which may not be satisfied by many modern machine learning tools. In order to accommodate this added complexity from employing flexible machine learning, we can instead use sample splitting [e.g.. 12 as in (ii). We refer the readers Kennedy 32 for more details.

---

In the following proposition. we give an enror bound of computing the set distance with the conditional counterfactual mean vector estimates.
Proposition 3.1. Let D denote the single, average, or complete linkage between sets of points, induced by the distance function such that d(r, S || - vll.. Then under Assumption A7 for any Joy two sets $1, S2 in {ug)) and their estimates Sr, S2 with (P())).
(2) D(S,, S2) x Σ
l Malloo
aEAA
proof of the above proposition and all subsequent proof's can be found in Appendix. Proposition 3.1 suggests that in the agglomerative clustering we shall obtain identical cluster sets beyond a certain level of the dendrogram, where the distance between the closest pair of branches exceeds the outcome regression eπrоr The result applies to a wide range of distance functions in Euclidean space.
In some problems it might be expensive to compute similarities between all items to be clustered (i.e., O(n²) complexity). Eriksson et al. [16] proposed the hierarchical clustering of n items only based adaptively selected small subset of pairwise similarities the order of O log n). By virtue of Proposition 3.1 their their algorithm is also applicable to our framework as long as Tha is consistent estimator for pa [see 16 Theorem 4.1].
In contrast to k-means clustering, it is not straightforward to analyze the performance of hicrarchical clustering with respect to the true target clustering, because build a set of nested clusters across various resolutions (a hierarchy) such that the target clustering close to some pruning of that hierarchy. Moreover, conventional linkage-
algorithms may have difficulties in the presence of noise. Balcan et al. [5] proposed a novel robust hierarchical clustering algorithm capable of managing these issues. Their algorithm produces set of clusters that closely approximates the target clustering with a specified error rate even in the presence noise, and it is adaptable to an inductive setting, where only small subset of the entire sample is utilized. We shall adapt their algorithm for causal clustering, and analyze the performance of our proposed algorithm.
We consider inductive setting where only have access to small subset of points from much larger data set. This can be particularly important when running an algorithm over the entire dataset is computationally infeasible. Suppose that {CI,..., C& is the target clustering, and that there exist N samples in total. Assuming we are given a random subset U" of size n., n < N, consider a clustering problem (U", Z) in the conditional counterfactual mean vector space where each point μ U" has a true cluster label 1(μ) E [Ci...., } Further we let (²u) denote a cluster corresponding to the label U(,), and (C(())) denote the size of the cluster C(u). To proceed, goodd-neighborhood property to quantify the level of noisiness in our population distribution.
define the following
Definition 3.1 ((a, vooo Neighborhood Property for Distribution). For a fixed μt E R', ler C(r)) = {u- C(u)) C(n')), iee,, set whose label is equal C(p'), and Ty- inl(r Plu B(r'rr) +P(CC('))) The distribution P satisfies (ax, v--good neighborhood property if Pa,e = (1 P. + uPnniss where IP, is probability distribution that satisfies
Patu E (B(l,rw) (Cp')) S.a
and Pnoize is valid probability distribution.
The nogd-neighborhood property in Definition 3.1 is a distributional generalization both the v-strict separation and the a-good neighborhood property from Balcan et al. 54. a, be viewed as noise parameters indicating the proportion of data susceptible to erroneous behavior. Next, we assume the following mild boundedness conditions on the population distribution and outcome regression function.
Assumption A2. || 1| 2 S B for some finite constant B a.s. [PP.
Assumption A3. Po., in Definition 3.7 has bounded Lebesgue density.
In the next theorem, we analyze the inductive version of the robust hierarchical clustering [5] Algorithm 2] in the causal clustering framework. We prove that when the data satisfies the good neighborhood properties, the algorithm achieves small error on the entire data set, requiring only a small random sample whose size is independent of that of the entire data set.
5

---

Theorem 3.2. Suppose that UN consists of N i..dd samples from Fa., that satisfies the (a.v)- v)- good neighborhood property Definition 3.1 For n < N. consider random subset U ((()))..,,((()))) C U and its estimates U [1)).... ( in which clustering to be performed. y = = 1 - -nalloo and for any 8N E (0, 1), define
(v
1
(V)
a' = a
log N
v' ='=
log N
dn
Y N
1
== 0
7 log
+
log
Then under Assumptions A7 and A3 long the smallest target cluster has size greater than 12(v' + a + E)N. the inductive robust hierarehical clustering [S] on Ün with min(a'+e.p") log minla'+e.ry produces a hierarchy with pruning that has error most v/ + 8 with respect to the true target clustering with probability least 1 - 8 28N.
The main implication of Theorem 3.2 that, in essence, the natural misclassification error a from the a-good neighborhood property has increased by Op Op(EasA Hh Hall due to the costs associated with causal clustering.
4 Density-based Causal Clustering
The idea of density-based clustering was initially proposed as an effective algorithm for clustering large-scald noisy datasets 17 24] The density-based methods work by identifying areas of high point concentration as well as regions of relative sparsity or emptiness. It offers distinct advantages over other clustering techniques due to their adeptness in handling noise and capability to find clusters of arbitrary sizes and shapes. Further, it does not require a-priori specification of number of clusters. Here, we focus the level-set approach [see 50 and the references therein].
With a slight abuse of notation, we let P be the probability distribution of μ to distinguish it from the observational distribution IP, and be the corresponding Lebesgue density. We also let K denote valid kernel, i.e., a nonnegative function satisfying f K (u)du = We construct the oracle kernel density estimator P% with the bandwidth h > 0 as
(M')
K
11(1)
1 h
119
for Kyl E Rt. Then we define an average oracle kernel density estimator by (ph) = Ph. and the corresponding upper level set by La.t {u (4) t}. Suppose that for each t, Li.e can be decomposed into finitely many disjoint sets: In,t = C U...UC. Then C2 = [11,-.. Ct,} } is the
level set clusters of our interest level f.
With regard to the analysis of topological properties of the distribution P, the upper level set of ph. plays role akin to that of the upper level set of the true density p. yet it presents various advantages, as indicated in previous studies [e.g.. 19 37 50 60]; Pa is well-defined even when p is not, ph provides simplified topological information, and the convergence rate of the kernel density estimator with respect to Pı is faster than with p. For such reasons, we typically target the level set La,e induced from Ph in lieu of that from [see, e.g., 38 Section 2].
When each (() known (or has been observed), the level sets could be estimated by computing Σn,, {μ= Ph (M) t}. Specifically, for each we let W. {μ (14 > t). and construct graph G, where each (aa)) E WW a vertex and there is an edge between ((()) and ((j) if and only
[|(()) - Lا,ll2 < h. Then the clusters at level L are estimated by taking the connected components of
the graph G., which is referred to as a Rips graph. Persistent homology measures how the topology
of RG varies by the value of l. See, for example, Bobrowski al. (7), Fasy al. [19), Kent et [36 more information the algorithm and its theoretical features.

---

However, in our causal clustering framework, the oracle kernel density estimator Ph. is not computable since do not observe each (())- Thus we construct a plug-in version of the kernel density estimator:
1 K
Pio H
(a
419
/
with estimates (P())). Then we target the corresponding level set Ln.t = {u= ph) > t}. To account
for the added complications in estimating Li,t, we introduce the following regularity conditions on the kernel K, along with the bounded-densee condition from Assumption A3 on the distribution P.
Assumption A3' p is bounded a.s. [P].
Assumption A4. The fernetifucctin has a support on B(O, 1). Moreover, it is Lipschitz continuous with constant MR, i.e., for all x, y E R2, (xx) K(y) Mx x vll2-
The Hausdorff distance is a common way of measuring difference between two sets that are embedded the same space. what follows, we define the Hausdorff distance for any two subsets in Euclidean space.
Definition 4.1 (Hausdorff Distance). Consider sets S1, S2 C IR9. We define the Hausdorff distance (S1, S2) as
((,, = max sup inf (#ES) yES2
|| - vlla, sup inf ||< 81l2 yE sES;
Note that the Hausdorff distance can be equivalently defined
H(S1; S2) inf 2 0: S1 S2, and S2 C S1,c).
where for i 1,2, St, {y R there exists x S, with || u|1 S e].
To estimate the target level set Lr, (pr. > t} using the estimator L., (ph t), we normally assume that the function difference [pA pall bo is small. To apply this condition to the set difference (Ir,,, Tr,,), we have to ensure that the target level set Le, does not change drastically when the level & perturbs. We formalize this notion as follows.
Definition 4.2 (Level Set Stability). We say that the level set Lt,h {w IR9 (w) > f is stable if there exists and C such that, for all 5 <, a.
H(I2-5,1: T.+5,t) S C5.
The next theorem shows provided that the target level set Lh,t is stable the sense of Definition 4.2
our level set estimator Lm.t is close to the target level set LA,e in the Hausdorff' distance.
Theorem 4.1. Suppose that La, is stable and let H(:,)) be the Hausdorff distance between two sets. Let the bandwidth vary with n such that (hn]nEN
ho) and
lim sup (log( (lgg(1hh)) s/+)))+ < 00.
nh?
Then, under Assumptions A7
A2
A3
and A4
we have that with probability at least 8,
(log(1/hm)) h,,) + l2g(2/6)
Σ |ia - Halli + log (2/5) hn
([nne, $
min
nhg
Ag+I
The above theorem ensures that the estimated level sets in the causal clustering framework do not significantly deviate from Ln.t. provided that the error of P. remains small. As consequence, we show that causal clustering may also be accomplished via level-set density-based clustering, albeit at
the expense of estimating the nuisance regression functions for the outcome process. The bandwidth may be selected either by minimizing the error bounds derived from Theorem 4.1 or by employing data-driven methodologies [c.g.. 38 Remark 5.
7

---

Develly
Con Me
Salald beard
(a) 0.01
(b) 0.05
(c) 0.05
(d) 0.1
Figure 2: (a), (b): The y-axis represents classification error from hierarchical (causal) clustering, where we fix 0.01, 0.1 and vary (c), (d): The y-axis represents the average of H (Tn,es In,t) from density-hased (causal) clustering, where we fix = 0.05, 0.1 and vary n.
281
A
04
Tha CATE
(a)
(b)
(c)
Figure (a) Histogram of the true CATE in the test set. the original study 46 individuals
with zero treatment effects are assigned to the label L = O. (b) The result of density- based causal clustering. Units Cluster Cl appear to have higher baseline risk (μ1)). (c) observe that points in
Clusters C1 and C2 are more concentrated around the right upper area (larger No, ji) and the lower left area (smaller Po: (1), respectively.
Empirical Analyses
5.1
Simulation Study
Here, explore finite-sample properties of proposed plug-in procedures via simulation. In particular, we investigate the effect of nuisance estimation on the performance of causal clustering to empirically validate our theoretical findings in Sections and
For hierarchical causal clustering, we use the simulation setup akin to that Kim et al. (39 Letting 2500, randomly pick 10 points in a bounded hypercube [0, 1]3; {ct, Cio) and assign roughly n1/10 points following truncated normal distribution to each Voronoi cell associated with c; these are our {. Next, we let P.o Ma + & with
NN n #). which ensures that -| (p( Following Balcan et al. (5). by repeating simulations 100 times, we compute classification error as a proxy of the clustering performance using different values of parameter fixing the value of v and B. The results are presented in Figure (a) & (b) with standard deviation error bars The simulation result supports our finding in Theorem 3.2, indicating that the price we pay for the proposed hierarchical causal clustering is inflated due to the nuisance estimation error.
For density- based causal clustering, utilize the toy example from Fasy al. [18), originally used to illustrate the cluster tree. We consider a mixture of three Gaussians R.2. Then, roughly n/3 points for each of the three clusters generated, which our {Pg)) Similarly as before, let Pa = Ne + & with & NO,, P). Next, letting 0.01, we compute Pr. and Ph. and the corresponding level sets Ln,e and Ln, for different values For each n, we calculate the mean Hausdorff distance between Ln,t and Ln, through 100 repeated simulations, and present the results

---

PCI PC
PCS
Figure 4: The estimated causal clusters principal- comppneett hyperplanes with axes repre- senting the first and second, second and third principal components in the conditional counterfactual mean vector space, respectively.
1.
Figure 5: The density plots of the pariwise CATE of six other education levels relative to the doctoral degree across clusters. We observe substantial degree of effect heterogeneity. The red dashed vertical lines denote the zero CATE
in Figure (c) & (d) with error bars. Again, the results corroborate the conclusion from Theorem 4.J that the cost of causal clustering is associated with the nuisance estimation error.
5.2
Case Study
In this section, we illustrate method through two case studies. We use semi-synthetic data on the voting study and real-world data on employment projections.
Voting study. Nie and Wager [46] considered a dataset on the voting study originally used by Arceneaux et al. [2]. They generated synthetic treatment effects to render discovery of heterogeneous treatment effects more challenging. We use the same setup Nie and Wager [46] Chapter 2), where we have binary treatments, binary outcomes, and 11 pretreatment covariates. While Nie and Wager 466 specifically focused on accurate estimation of the CATE, here we aim to illustrate how the proposed method can be used to uncover an intriguing subgroup structure. We randomly chose a training set of size 13000 and test set of size 10000 from the entire sample. Then estimate ( using the gross-validation-bee bassdd Super Learner ensemble [54] to combine regression splines, support vector machine regression, and random forests the training sample, and perform the density-based causal clustering on the test sample using DeBaCl function TDA package [8].
In Figure (b). we see two clusters in our conditional counterfactual mean vector space that are clearly separable from each other, one with nearly zero subgroup effect (Cluster C2) and the other with negative effect (Cluster CI). They correspond to the two largest branches at the bottom of the tree (Figure (c). Roughly 4% the points are classified as noise. Interestingly, units in Cluster Cl appear have higher baseline risk μo than Cluster C2. This is indeed more clearly noticeable in

---

Figure (c); Clusters C1 and C2 have a higher concentration of units in the right upper area (larger No: M1) and the lower left area (smaller Po: H1)
Employment projection data.
The dataset, obtained from the US Bureau of Labor Statistics (BLS), provides projected employment by occupation. Specifically, the dataset consists of projected 10-year employment changes (2018 8-- 2028) computed from the BLS macroeconomic model across various occupations. We have eight education levels (No formal education, High school, Bachelor's is degree, etc.). Here, we aim to uncover subgroup structure in the effects of entry-level education on projected employment. Our data also include four covariates: baseline employment in 2018, median annual wage in 2019, work experience, and on-the-job training.
Again we randomly split the data into two independent sets and use the super learner ensemble to estimate the nuisance regression functions. We then find clusters using robust hierarchical causal clustering described in Section 3 Since we have multi-level treatments this time (g 8), for ease of visualization, in Figure 4 we present the resulting clusters in two-dimensional hyperplanes with axes representing the first and second, second and third principal components, respectively. We also present the density plots for some of the pairwise CATES across clusters in Figure 5
In Figure 4 we observe four distinct clusters which are quite clearly separable from each other on the principal component hyperplanes. It appears that some clusters show considerably different effects from the others (e-g.. Cluster 3), as shown in Figure 5 Our findings indicate a substantial heterogeneity in the effects of entry-level education on projected employment.
6 Discussion
Causal clustering is a new approach for studying treatment effect heterogeneity that draws on cluster analysis tools. In this work, expanded upon this framework by integrating widely-used hierarchical and density-based clustering algorithms, where we presented and analyzed the simple and readily implementable plug-in estimators. Importantly, we do not impose any restrictions the outcome process, the proposed methods offer novel opportunities for clustering with generic unknown pseudo outcomes.
There are some caveats and limitations which should be addressed. First, causal clustering plays a more descriptive and discovery-based than prescriptive role compared to other approaches. It enables efficient discovery of subgroup structures and intriguing subgroup features as illustrated in our case studies, yet will likely be less useful for informing specific treatment decisions. Understanding this trade-off is thus important, and we recommend using our methods in conjunction with other approaches. Nonetheless, the clustering outputs could be potentially utilized as an useful input for subsequent learning tasks, such as precision medicine or optimal policy, Next, our theoretical findings show that when the nuisance regression functions { are modeled nonparametrically, the clustering performance essentially inherits from that of (P.). The convergence rate of P., can be arbitrarily slow as the dimension of the covariate space increases. Kim et al. [39] addressed this issue by developing an efficient semiparametric estimator that achieves the second-order bias, and so attain fast rates even in high-dimensional covariate settings (34). In future work, aim to develop more efficient semiparametric estimators for hierarchical and density-based causal clustering. Extension to other robust clustering methods, such hierarchical density-based clustering [IO]. would be promising direction for future research as well. Lastly, our proposed methods are currently limited to the standard identification strategy under the mo-unmeasured-confone confoundinn assumption, which is typically vulnerable to criticism [e.g..28] Chapter 12]. To widen the breadth of the causal clustering framework, we will also be exploring extensions to other identification strategies, such as instrumental variable, mediation, and proximal causal learning.
7 Broader Impact
The proposed method provides general framework for causal clustering that is not specifically tailored to any particular application, thereby reducing the potential for unintended societal or ethical impacts. Nonetheless, it is important to note that the identified subgroup structure was constructed entirely based on treatment effect similarity, without accounting for faimness or bias.
10

---

8 Acknowledgements
This work was partially supported by Korea University Grant (K2407471) and the National Research Foundation of Korea (NRF) grant funded by the Korea govemnement (MSIT)(No. NRF- (1EAM336A1065595 This work was also partially supported by Institute of Information & commu- nications Technology Planning & Evaluation (ITPP) grant funded by the Korea government [NO.RS-2021 10221-1121130 1343, Artificial Intelligence Graduate School Program (Seoul National Univer- sity)] and the New Faculty Startup Fund from Seoul National University. Part of this work was completed while Kwangho Kim was a Ph.D. student at Carnegie Mellon University.
References
[1] Rana Husni AlMahmoud and Marwah Alian. The effect of clustering algorithms on question answering. Expert Systems with Applications, 122959, 2024.
[2] Kevin Arceneaux, Alan S Gerber, and Donald Green. Comparing experimental and matching methods using a large-scale voter mobilization experiment. Political Analysis, 14(1):37-66 2006.
[3] Susan Athey and Guido Imbens. Recursive partitioning for heterogeneous causal effects. Proceedings of the National Academy of Sciences, 133(27):7333736) 2016.
[4] Maria-Florina Balcan, Avrim Blum, and Nathan Srebro. A theory of learning with similarity functions. Machine Learning, 72(1-2):89-112, 2008.
[5] Maria-Florina Balcan, Yingyu Liang, and Pramod Gupta. Robust hierarchical clustering. The Journal of Machine Learning Research, 15(1):3831-871, 2014.
[6] Nicolás M Ballarini, Gerd Rosenkranz, Thomas Jaki, Franz König, and Martin Posch. Subgroup identification in clinical trials via the predicted individual treatment effect. PloS one, 13(10)=a005971, 2018.
[7] Omer Bobrowski, Sayan Mukherjee, Jonathan E Taylor, al. Topological consistency via kernel estimation. Bernoulli, 23(1):288-322 2017.
[8] Kailash Budhathoki, Mario Boley, and Jilles Vreeken. Discovering reliable causal rules. In Proceedings of the 202/ SIAM International Conference on Data Mining (SDM), pages 1-9.
SIAM, 2021.
[9] Luben MC Cabezas, Rafael Izbicki, and Rafael Stern. Hierarchical clustering: Visualization, feature importance and model selection. Applied Soft Computing, 141:110303, 2023.
[10] Ricardo JGB Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Pucific-Asia conference on knowledge discovery and data mining, pages 160-172. Springer, 2013.
[11] Shuai Chen, Lu Tian, Tianxi Cai, and Menggang Yu. A general statistical framework for 2017.
subgroup identification and comparative treatment scoring. Biometrics,
[12] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, and Whitney K Newey. Double machine learning for treatment and causal parameters. Technical report, cemmap working paper, 2016.
[13] Victor Chernozhukov, Mert Demirer, Esther Duflo, and Ivan Fernandez- Val. Generic machine learning inference on heterogeneous treatment effects randomized experiments, with an application immunization in india. Technical report, National Bureau of Economic Research, 2018.
[14] Sanjoy Dasgupta and Philip M Long. Performance guarantees for hierarchical clustering. Journal of Computer and System Sciences, 70(4):555-50) 2005.
[15] Raaz Dwivedi, Yan Shuo Tan, Briton Park, Mian Wei, Kevin Horgan, David Madigan, and Bin Yu. Stable discovery of interpretable subgroups via calibration in causal studies. International Statistical Review, 88:S135-S178, 2020.

---

[16] Brian Eriksson, Gautam Dasarathy, Aarti Singh, and Rob Nowak. Active clustering; Robust and efficient hierarchical clustering using adaptively selected similarities. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 260-268, 2011.
[17] Martin Ester, Mans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density- algorithm for discovering clusters in large spatial databases with noise. In Kdd, volume 96, pages 226-231, 1996.
[18] Brittany T Fasy, Jisu Kim, Fabrizio Lecci, Clement Maria, and Vincent Rouvreau. Tda: statistical tools for topological data analysis. Software available at https://cran. r-project. org/package= TDA, 2014.
[19] Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, Larry Wasserman, Sivaraman Balakr- ishnan, Aarti Singh, al. Confidence sets for persistence diagrams. The Annals of Statistics, 42 (6):2301-2339, 2014.
[20] Jared C Foster, Jeremy MG Taylor, and Stephen J Ruberg. Subgroup identification from randomized clinical trial data. Statistics in medicine, 30(24):287722880, 2011.
[21] Justin Grimmer, Solomon Messing, and Sean J Westwood. Estimating heterogeneous treatment effects and the effects of heterogeneous treatments with ensemble methods. Political Analysis, 25(4):413-434, 2017.
[22] Michael Hahsler, Matthew Pickenbrock, and Derek Doran. dbscan: Fast density-based clustering with Journal of Statistical Software, 91:1-30, 2019.
[23] Nima Hejazi, Wenjing Zheng, and Sathya Anand. framework for causal segmentation analysis with machine learning in large-scale digital experiments. Conference on Digital Experimentation at MIT, (8th annual), 2021. URL
www.aiiii..gggaaaaooooae /abs///////// /2111
01223
[24] Alexander Hinneburg, Daniel A Keim, et al. An efficient approach clustering in large multimedia databases with noise. In KDD, volume 98, pages 58-65, 1998.
[25] Shoubo Hu, Zhitang Chen, Vahid Partovi Nia, Laiwan Chan, and Yanhui Geng, Causal inference and mechanism clustering of mixture of additive noise models. Advances in neural information processing systems, 31, 2018.
[26] Biwei Huang, Kun Zhang, Pengtao Xie, Mingming Gong, Eric P Xing, and Clark Glymour. Specific and shared causal relation modeling and mechanism-based clustering. Advances in Neural Information Processing Systems, 32, 2019.
[27] Kosuke Imai, Mare Ratkovic, et al. Estimating treatment effect heterogeneity in randomized program evaluation. The Annals of Applied Statistics, (1)):443447) 2013.
[28] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[29] Anil Jain. Data clustering: 50 years beyond k-means. Pattern recognition letters. 31(8): 651-666, 2010.
[30] Anil K Jain, M Narasimha Murty, and Patrick J Flynn. Data clustering: a review. ACM computing surveys (CSUR), 31(3):264-333 1999.
[31] Nathan Kallus. Recursive partitioning for personalization using observational data. In Interna- tional conference on machine learning, pages 1789-1799 1798. PMLR, 2017.
[32] Edward H Kennedy. Semiparametric theory and empirical processes in causal inference. In Statistical causal inferences and their applications in public health research, pages 141-167. Springer, 2016.
[33] Edward H. Kennedy. Nonparametric causal effects based on incremental propensity score interventions. Journal of the American Statistical Association, O(a):0-0, 2018.
12

---

[34] Edward H Kennedy. Semiparametric doubly robust targeted double machine learning: review. arXiv preprint arXiv:2203.06466, 2022.
[35] Edward H Kennedy. Towards optimal doubly robust estimation of heterogeneous causal effects. Electronic Journal of Statistics, 17(2):300- 3049,, 2023.
[36] Brian P Kent, Alessandro Rinaldo, and Timothy Verstynen. Debacl: A python package for interactive density-based clustering. arXiv preprint arXiv:1307.8130 2013.
[37] Jisu Kim, Jaehyeok Shin, Alessandro Rinaldo, and Larry Wasserman. Uniform convergence rate of the kemel density estimator adaptive intrinsic volume dimension. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 3398- 3407, Long Beach, California, USA, 09-15 Jun 2019. PMLR. httptt httt::::/proceeeee m1 r. wre.srss/ss 9 9e html
[38] Kwangho Kim, Jisu Kim, and Edward H Kennedy. Causal effects based on distributional distances. arXiv preprint arXiv: 1806 02935, 2018.
[39] Kwangho Kim, Jisu Kim, and Edward H Kennedy. Causal k-means clustering. arXiv preprint arXiv:2405.03008. 2024.
[40] Hans-Peter Kriegel and Martin Pfcifle. Density- based clustering of uncertain data. In Proceed- ings of the eleventh ACM SIGKDD international conference on Knowledge discovery data mining, pages 672-677, 2005.
[41] Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1655 1664, 2016.
[42] Sören R Künzel, Jasjeet S Sekhon, Peter J Bickel, and Bin Yu. Meta-learners for estimating heterogeneous treatment effects using machine learning. arXiv preprint (.X6v:7706003455 2017.
[43] Ilya Lipkovich, Alex Dmitrienko, and Ralph D'Agostino Sr. Tutorial in biostatistics: data- driven subgroup identification and analysis in clinical trials. Statistics in medicine, 36(1): 136-196, 2017.
[44] Win-Yin Loh, Luxi Cao, and Peigen Zhou. Subgroup identification for precision medicine: comparative review of methods. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, (5))e1332, 2019.
[45] Alex Markham, Richeek Das, and Moritz Grosse Wentrup. distance covariance-basse kernel for nonlinear causal clustering in heterogeneous populations. In Conference on Causal Learning and Reasoning, pages 542-558. PMLR, 2022.
[46] Xinkun Nie and Stefan Wager. Quasi-oracle estimation of heterogeneous treatment effects. Biometrika, 108(2):299-311 2021.
[47] Thomas Ondra, Alex Dmitrienko, Tim Friede, Alexandra Graf, Frank Miller, Nigel Stallard, and Martin Posch. Methods for identification and confirmation of targeted subgroups in clinical trials: systematic review. Journal of biophurmaceutical statistics, (6(1))99-119) 2016.
[48] W Qi, Ameen Abu-Hanna, Thamar Eva Maria van Esch, Derek de Beurs, Yuntao Liu, Linda Flinterman, and Martijn C Schut. Explaining heterogeneity of individual treatment causal effects by subgroup discovery: An observational case study in antibiotics treatment of acute rhino-sinusitis. Artificial Intelligence in Medicine, 116: 102080, 2021.
[49] Rosalba Radice, Roland Ramsahai, Richard Grieve, Noemi Kreif, Zia Sadique, and Jasjeet Sekhon. Evaluating treatment effectiveness in patient subgroups: a comparison of propensity score methods with an automated matching approach. The international journal of biostatistics, 8(1), 2012.
13

---

[50] Alessandro Rinaldo, Larry Wasserman, et al. Generalized density clustering. The Annals of Statistics, (8(5):2678-2722 2010.
[51] Patrick M Schnell, Qi Tang, Walter W Offen, and Bradley Carlin. A bayesian credible subgroups approach to identifying patient subgroups with positive treatment effects. Biometrics, 72(4):1026-100 1036, 2016.
[52] Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In International conference machine learning, pages 3076-3085. PMLR, 2017.
[53] Mark J van der Laan and Alexander R Luedtke. Targeted learning of an optimal dynamic treatment, and statistical inference for its mean outcome. 2014.
[54] Mark Van der I Laan, Eric Polley, and Alan Hubbard. Super learner. Statistical applications in genetics and molecular biology, 6(1), 2007.
[55] Aad W Van Der Vaart and Jon A Wellner. Weak convergence. In Weak convergence and empirical processes, pages 16-28. Springer, 1996.
[56] Tyler VanderWeele. Outcome-widd epidemiology. Epidemiology (Cambridge, Mass.), 28(3):
399, 2017.
[57] Tyler VanderWeele, Shanshan Li, Alexander C Tsai, and Ichiro Kawachi. Association between religious service attendance and lower suicide rates among us women. JAMA psychiatry, 73(8): 845-851, 2016.
[58] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(523):122--1242 2018.
[59] Tong Wang and Cynthia Rudin. Causal rule sets for identifying subgroups with enhanced treatment effects. INFORMS Journal on Computing, 34(3):626-1163,, 2022.
[60] Larry Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
[61] Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions on neural networks, (6(3):645-675 2005.
[62] Weijia Zhang, Thuc Duy Le, Lin Liu, Zhi-Hua Zhou, and Jiuyong Li. Mining heterogeneous causal effects for personalized cancer treatment. Bioinformatics, 33(15):237--3378 2017.
[63] Lihui Zhao, Lu Tian, Tianxi Cai, Brian Claggett, and Lee-Jen Wei. Effectively selecting a target population for a future comparative study. Journal of the American Statistical Association, 108 (502):527-539, 2013.
[64] Wenjing Zheng and Mark Van Der Laan. Asymptotic theory for cross-validated targeted maximum likelihood estimation. Working Paper 273, 2010.
14

---

Appendix
A Robust Hierarchical Clustering
This section summarizes definitions and theoretical results in Balcan et al. [5].
We first define clustering problem (U,1) as follows. Assume have data set U of N objects. Each point Jr' E U has true cluster label T(x)) in [Ci,..., }. Further we let C(u") denote a cluster corresponding the label U(''), and RC(a") denote the size of the cluster C(z').
The good-neighborhoog property in Definition A. is a generalization of both the y-strict separation and the a-good neighborhood property in Balcan et al. [5]. It roughly means that after portion of points are removed, each point might allow some bad immediate neighbors but most of the immediate neighbors are good. a, can be viewed as noise parameters indicating the proportion of data susceptible to erroncous behavior.
Definition A.1 (Property 3 in [5I), Suppose clustering problem (U,1) with |U] = N. and a similarity function d: U x U + R. We say the similarity function satisfies (a, -goodd neighborhood property for the clustering problem (U, 1), if there exists U' C U of size (1 - - so that for all points μ' E U we have that all but oN out of their now"") nearest neighbors in belong to the cluster C(p)).
In the inductive setting, Algorithm in Balcan al. [5] uses a random sample over the data set and generates a hierarchy over this sample, and also implicitly represents a hierarchy over the entire data set. When the data satisfies the good neighborhood properties, Algorithm in (5) achieves small error on the entire data set, requiring only small sample size independent of that of the entire data set, as in Theorem A.I
Theorem A.1 (Theorem 11 in (.). Let d be a symmetric similarity function satisfying the (ox, v-- good neighborhood for the clustering problem (U,1). As long as the smallest target cluster has size greater than 12(v + NN,, then Algorithm 2 in (5) with parameters = mi log minta.e) produces a hierarchy with a pruning that has error at most v + 5 with respect to the true target clustering with probubility least 5.
B Proofs
Throughout the development, we let P denote the conditional expectation given the sample operator f. as in f() f())dP(2). Notice that (f( ( is random only f depends on samples, in which case P(f) & E(f). Otherwise P and E can be used exchangeably. For example, if f is constructed on a separate (training) sample D = (Z,, .... Z..). then {f(z)] = f(z) D for a new observation ~~ P. Lastly, we let d2 IR9 R R be the Euclidean distance on R2, i.e.,
de(r, v) = || vll2.
We present the following basic lemma which we will use throughout the proofs. Lemma B.I. Under Assumption A7
(a) The conditional expectation of 1| pll2 is bounded by the estimation error of Pai iee.
P (l /=ll2) - Σ 1ia Me Mallz,1-
(2)
(b) Under Assumption A2 for 5 (0,1), EE |P()) MGall can be bounded with proba- bility at least 1 ò as
log(1/0)
Pi - 10ll2
1
S Σ liaa -Hali + By
71
15

---

Proof of Lemma B.7
(a) It is immediate to see that
P [lp M0l122] =P
(Pa(X) - (a()))
P (l) - (x)1l
Σ liaa Malle,1
(b) Noting that Assumption A2 implies 0 5 ||ac]] - moll22 S /BB a.s., by Hoeffding's inequality
get
nt22
P
Σ
(C)) moll2 P [ m0l12) zt] S exp
122
Hence for any 8 > applying BV 1og(1/0) gives
pi moll2 S [l] - mo [22 BV log (og(1/8)
=
2 8.
n
Then applying 2
gives
(1)(1/8)
A -M0112 - > 11aa Malll + B
21- 5.
Proof of Proposition 3.1
We rewrite Proposition 3.1 with detailed constants relation.
Proposition B.2. Let D denote the single, average, complete linkage between sets of points, induced by the distance function such that d(x,, y) S C C||æ - yll, for some constant 0. Then under Assumption Al for any two sets S₁, S2 in {p() and their estimates S S2 with {Po))
- S 2C
Σ l1ãa - -Malloo aEA
Proof of Proposition B.2 Recall that given pair of points (un(X1) ... My (X,)) 82
(pi (X2), .... (Xx) ).), and their estimates 31 = (īi (Xi),..., D., (X,)). 32 (X2), .... (X2)) for VX1, X2 X. To prove the theorem, first upper bound the maximum discrepancy between d(s1, 52) and d(3), 82). Since our distance function satisfies
d(r,y) < C C| x - -y11
for any x, E RRP we may get
d(s1, 82) d(51, 32)
< (l))((i)) - 11 (X2) (p(x)) x(x+))l
(x(X)) Mx(x))
< 2C
1l Ma 11,
aEA
where the first inequality follows by ||~|||
|| || vll1.
16

---

Let (21",82")= arg min (2) and 87 82 denote their estimates, Then by the definition of #2
single linkage we have
(2) DD,,, S2)
min d(si; 82) d(ss, x2) aeA
< [d(š), 82)
x 2C Σ 1l - pa lac
aεA
The same logic applies to the complete and average linkages.
Proof of Theorem 3.2
Recall that we μ denote a point in the conditional counterfactual mean vector space given X, A. We also use the notation U == {P()).....
where μ(() 's are i..d. samples from IP. Further by Assumption A3 we assume that every distribution satisfying the good neighborhood property in Definition 3.J has density bounded by Pp < co. We begin with introducing some useful lemmas before proving our main theorem.
((N)) ((v)),
Lemma B.3. Under Assumptions
A3
sup
(μ E B(w,r + B))B(wrr)) & C18,
WERT 20
where C₁ some constant that depends on Pus B, and q.
Proof. Let Dg be the g-dimensional Lebesgue measure. By Assumption A22 supp(p,) C
[-2B, 2B),, and hence for any w E Ra and r, > O,
Xa (BB(w, + 8) B(, r)) n nupp(pp)) S X ((B(wr + n 2B)²).
Now, bound À-- 1 (w, considering that the map & (B (w. t) (- 2 - ÖB( t + u) n [-B u. 2B + u] by up(w + tu) + (t + u)v for unit vector satisfies ||p(z) ((v)) | yll. have
2B,2B for any TR. First, note that for any 2 0, by
\ 1 (0B n 2B, 2B)9) s \ u)
2 u, 2B + vl9))
And hence
2B
(OI(w,, t) n n[-2B,
28
Xy 10 1) 12BB,
Jo AG-1 (OB(w, u) 1-2B - u, 2B
u, + u/() du
2(1 B), + 1)
1 4
Xq-1 OB (B((wl+uu)
du
1
>g
B(w, 1+ B() 1))
-2(1 B, 2(1
2
$ Ag [1 ([-2(1 2(1 + BB 2(1 + | S eA'B"
and hence
X (OB( () 2B, - 2221 1a----a-1 Ba-1
17

---

Then X ((B(w, r ( ( is bounded as
/ (0, )d)
/ c225- B pdl 62 13 qs.
And hence for all w E R2 and 0, Under Assumption
A3
Plu E B(w, r + B(,, r)) S Pp
Ag (dw)
(BBW..+t)) (B(w. (BBrr:+o//BBBrrr)))nnppp
22 1-- '89-1s..
qs.
Lemma B.4. Suppose U (u(1):... ...))......... M(N) are i..d. samples from P. With probability 8N.
U
(BW,, + 5) (B(W,)))
sup WE m>0
(μ E B(w, r + + B),Brr
N
1
1
(
8
2
log
+
log
+
log
N
ÖN
N
N
ÖN
where C2 a constant depending only on q, B, Pμ-
Proof. For R9 and r.s O, let Buns.
B(w,r r s))B(w,r), and let F,
[LB 189, r 0}. Then
U (B(w, r + B)(, sup weRt w
P (4c E B(w,r+
N
f(u() E [F(M())]
sup feF,
Now, for E 199 and O, let Bw, B(w,r) and Burr R R&B(w,r) and let H (Bar : R 0} and H BBm.r R9, 0). Then the VC dimension of H or H no greater than q + Therefore, let s(H, N(H.N) and N) be shattering number H. and H. respectively, then by Sauer's Lemma for N 2 2.
e.N
4+2
e.V 4+2
s(H,N) <
and
s(H, <
9 2
2
Now, let G. = (Buns w R2,r > 0}. then G. c AnB: A H, B E H... and hence for N 2 q + 2,
cN
24+1
s(G,,N) s(H, (7H,
Then, for N (2q + 4)3
s(9,, (2q 4)3) < (2e(2q + 2))
< (220t4)20t = 2(2g+4)²
18

---

so VC dimension of Go is bounded by (2q + 4) Then from Theorem 2.6.4 in Van Der Vaart and Wellner [55].
4))
(
M(Fs.11-1 (1.6) S K(2g + 4)²
2((20+1)--1)
88 8K + 2)
for some universal constant K. Now, for all f Fs. we have Ef² S CB. from Lemma B.3 Hence, by Theorem 30 in Kim et al. [371, with probability 1 8N.
f((()) E [f(mm))]
sup FEF.
N
i=1
1
My Cas N
2Ag C35
Cys
Coslog( ox +
log( by
0
log( (2Ag) +
log
N
N
N
where V4 2((2q 4)2 1) and
Ag
8K (q + 2)e.
Hence, it can be simplified as
1 N
1 log
1
(
1
sup fEF
Σ f((() E [f(())) S C2
log
log
ŌN
where C2 is a constant depending only on q, B, Pn.
Corollary B.5. Suppose U = (m(a)- M(N) are ii.d. samples from P.. Under Assumption A3
with probability 8N. have
UN (B(Ww, r 8) B(W,))) sup WERY +>00
S Co
+
log
+
log
N
N
EN
N
where C3 a constant depending only q, B, Pyr
Proof.
IUN (IB(w, (BW(,))
sup
wER1,
sup wE
P E ((w, B)
U n (B(,, r + 8) B(w, r)) IP (u E B(w,r+ + s)\B(urr))
sup WE R0
N
Then from Lemma
B.3 and B.4 with probability 1 - 8N.
sup
UU
(B(w, s) ((WBB)
1
< C2s
log
+
log
+
log
N
< C C2
log
+
8
log
+
s
+
log
N
N
2
N
1 log
1
!
C3 + i
+
log
N
where C3 = max { + 3 C2, 2/
C2
19

---

Lemma B.6. Suppose U = ( P(N) are i...d samples the mixture distribution P Pa.
defined in Definition 3.1 Then with probability 1- 8N. the distance d2 satisfies (a', (o',v/) (a',v')-good neighborhood property for the clustering problem (UN, ,1), where
(VN log ÖN
and v ='= (1
a' a'=a+0
log ÖN
Proof. For any óN (0, 1), by Hoeffding's inequality we have
1
Σ (P() ~ Pnaise 2
B
log
N
N
5N
with probability at most 6x/2. /2. Again by Hoeffding's inequality, for all points p' E UN
have N
1 1 Huo ~ Po and mO E B(p \ C(C)) 2 a +
B
log 2 ÖN
N
with probability at most /2, Paluro B() C(2))
by the given condition.
Therefore by definition, it follows that with probability at least 1 - 8N the distance d2 satisfies
(a V log 2 by V V log ōN -good neighborhood property.
Proof of Theorem 3.2
Proof. From Lemma B.6 the distance d2 satisfies (a', "'d,z')gooll property for the clustering problem (U-) .1.. So there exists subset U' C U of size (1 V' such that for any point μí E U' all but aN out of "C())) neighbors in U' belongs to the cluster C(u'), For each μ' E U', let ue be the distance to the nuur nearest neighbor of p' in U', i.e.
TU inf fr 2 O: IU' (B r) 2 nownnn
(4)
Then it follows
I0' BBBBB ru mu (CC()) S N'N.
Now letting E.Ed ll
Malloo we define
U (B(H), a + 47) TV rV
== sup
N
e'Ell
Then by Corollary B.5 under Assumption
it follows that with probability 1 8N
IU' n (B(y', r + 47) (B(',
sup
N
1
Y
1
< 4C3
+ N
log
+
log
JN
N
Hence,
1
1
log -1)
E O 7
log
N
ÖN
Now we consider estimates of UN (and correspondingly U'). For each μí E U.\, let jí' be estimate of p', and let UN = {jz nl E UV}. and correspondingly. O' (ī p² E EU) c ÜN. On U. define a cluster label i ÜN + -CI,...,, } as
i(')) = I(p'),
i.e., the cluster label i on fi' coincides with the true cluster label on p.. Let C(ji)) denote a cluster corresponding i(A²), and define C(P') = {p C(p) C(A')) as the set of á values for which ((A) matches O(²"). Then we have
nownnn = "'Caarrrr-
20

---

Now, note that d2(H,, p²) I rur implies d2(,, R() S " + 2%, and hence f E U' rur,p)))
implies O' n BB ru 22). Thus, follows that
Ü BB n + + 2 ( rrr now)nn "C("n)0
(5)
Therefore, we define T as the distance to the "crannn nearest neighbor of j in Ü' similar to as
D == inf {o 00: 0: ('' r) 2 n }
then, from 5), f is bounded by
i S ru +
Also, note that (2 rV., 2y implies d2(u, n²) S ru. .N' 4y, and thereby E Ü B(Ai, ror + 27) implies μ E U' n BBd',, ru + 4y). Thus we have
Ū TU (((1))
n B C(4)
IU' n B(p' no. " (C(x)) IU' n (B(yl, nur + B7)
(a' +E)N,
which leads to
Ü n Bp'', (ijl', for (t NO(')) s 10 nB no + 21)) no & (a' + +)NN
Consequently, the distance de satisfics (a' + (e,z') g-oodd property for the clustering problem (Ū. i). Then as long as the smallest target cluster has size greater than 12(p/ +a +E) Theorem A. limplies
that Algorithm of Balcan et [5] with n θ "ii(("'+e,")) log [min(a++s produces hierarchy with a pruning that is (v' -o)-close to the target clustering with probability
O
Proof of Theorem
First, give the following new result on bounding the Hausdorff distance between sets in the counterfactual function space.
Theorem B.7. Suppose that La. is stable and let H(.,) .) be the Hausdorff distance between two
sets. Suppose that Assumptions A7 A2 A3' and hold. Let E (0,1) and {hnIneN C. (0, hn) be satisfying
(log(1/h,,)) h/,,)) + log(2/8)
lim sup
< 0c.
nhg
Then, with probability at least 8,
(log(1/h,)) log(2/0/
H (Dnnn, Lbn CP,KBB
n/a
Σ Pa Palli + log(2/8) h2+1
hn 1)
min
In order to show Theorem B.7
need the following Lemma.
Lemma B.8. Suppose Assumptions A7 be satisfying
A2
A3'
and A4 hold. Let (0, 1) and {hn C. (0, ho)
(log(1/hg h/,))),)++++)0))))))))) + 1og(2/8) oc.
lim sup
nhg
Then, with probability at least P
-Pa..l
(log(1/hm)) + (2/5) nh% for some constant CP.K.B depending only P. K, B.
Σ 1l - Malli + +V /log(2/8) n. (ma))
S &CP.KB
min
hn
ha+1
21

---

For showing Lemma B.8 we note that Ih... Pho ol can be upper bounded as
P Ph., 1sx S liph.. Ph., bl.o + llph.. -Ph..
(6)
Therefore, in what follows we shall provide high probability bound for Il... - Ph. 2l in Lemma (B.9) and Ii,, Ph., ol in Lemma (8.10). Then applying these to (6) will conclude the proof.
The following from applying Kim et
37
Corollary 13].
Lemma B.9. Under Assumptions A/
A2
A33'
and A4
we let E (0, and (hn)nEN (0,
be satisfying
(log (1/h hn)),))))))))))) )) (2/() oc,
lim sup
nh?
then with probability at least 1 - it follows
(log(1/hm)) + log(2/0)
Pm... Ph. alc S C..
nha
where Cp,K depends only on P and K.
Proof. Consider [B(0, B + ho). Then by Assumption A2
for Ve E XX it follows
IP( wil2 1.
h
supp(K) C B(0, 1) from Assumption A4
implies that
11(1)
w
Ph., (w)
K
= 0 a.s.,
i=1
and consequently that Pa., (w) = 0 as well. Therefore,
Pp Ph.. 1loo
sup
PPh.. (w) Ph. (w)l
wEX
Under Assumption A3' P has bounded density so by Kim et al. 37 Proposition 5] we have that
[ p(w)dw
lim sup sup r-0
19
Note that under Assumption (A4). we have that (Kxx) K(y)) Mr || 2llz for any x, y R
and supp K') c (B, 1), which together implies that |||] S MK < co. Hence,
t sup (2(x) S / tM 2 M < oo.
||
Then applying Kim et al.
37 Corollary 13] gives that with probability at least 1 - 5,
sup Ph.,, (w) Ph., (w) S Cr, (log(1/1,))+ + log(2/0)
(8)
nhg
w
where Cr. depends only on P Pndd& K. Finally least 1 6,
7 and 8
together imply that with probability at
(log (1/h/hhh hmm) ) log(2/5)
PP.. Pho llo S C.P.K
nhς
Lemma B.10. Under Assumptions Al
A2
and A4
Then
CMrx.B B
1og(1/0)
ph... - Pho
11.0
min
[l] - Halli] +
hn
Ag+l
where CMp.3 B depends only Mr and B.
22

---

Proof. By Assumption A4 it follows that (x() - K()) - Mr I - vll for any 2, E IR and supp(K) B(0, 1), which together implies that (x) Kvy) S Mr and || S Mg. Thus
it follows
[K(x) K(y)l min (Mx 1 وااا MM) }
Now for any E I2, Ih,,, (w) ph. (w)) is upper bounded by
1
(()
w
M(a) w
PP.. (w) Ph., (w)l
K
K
ntin
hn
hn
15
|i - 11 l22
min
Mr
MR
n/n
hn
M
12
min
Σ
|1 m00l22 Mmn h
hn
72
Since this holds for any w E R4,
MR
Pm.. Ph. 1l
min
(m)) - p01l2 Im
h
n
Then under (A4), applying (3) from Lemma upper bounded as
B.1
gives that with probability 1 8. I1in.. ph. al is
Mr
1og(1/0) hn
pm... - Pho lloe 5
min |i - -Mall2 + 2B
hg+1
CMR hg+1
1Po - Malli + log(1/5)
<
min
ha
where CMRBB M max(1,2B)
Now we are ready to prove Lemma B.8
Proof of Lemma
B.8
As in
(6. we upper bound 1iph., Ph., 11 as Ph.. Ph., lboo S liā Ph. 11.0 + 11 Ph. 30
Then by Lemma B.9 and
B.10 with probability - d it follows that
Pm...
Pholl 1o
(log(1/ hha))))) + log(2/8)
CMx.B hg+t
min Σ 1l - Malli + log(2/8) hn
< CPpKV
+
nha
(log(1/hn)) + log(2/5)
11 - Malli + 1log(2/0) (2/0)
nn nen ma))
< CP.KKB
min Σ
nhy
ho+I
a
where Cr,KB depends only on P. K. B.
We are now in position to prove Theorem 4.1
23

---

Proof of Theorem 4.1
Recall that Linge is stable if there exist > 0 and C' H (L (4)) S CÇ.
such that, for all 0 < <
Proof. Let us define
(log(1/ha))++ + log(2/5) min Σ lI - Malli +
log(2/6)
To == CP.KBB
+ hg
hn {/))
nha
which is RHS the inequality in Lemma B.8
Suppose that we are given a sufficiently large n so that Ilpk.. Ph, oo < holds with probability for some constant a > O. We aim to show things: (a) for every
least 8 5 where nn a La,,t there exists E La... with | - yll S Crn, and (b) for every x E Lin. there exists y E La with || 2 I CTa.
To show (a), consider æ E Linnas Then by the stability property L there exists y -LhnltT such that | vll2 I Crn. Then Ph., (2) > + In which implies that
Ph., (v) 2 Ph.. (V) 11ph.. - Pho > Ph., (v) rn > t.
Hence we conclude y E Lhga with || - 8ll2 S CTn.
Similarly, to show (b), consider x LR... so that pn., (x) > t. Thus we have
Ph. (x) Z Pn. (x) p Ph., Iooo > Tn
which leads to E Lng, Then again by the stability property of L is there exists y E Linnt such that | - ull2 I Crn-
Hence by definition, we upper bound the Hausdorff distance H (La,er Lnne) by
Crp
(log(L/bn)) + 1og(2/8)
log(2/0) n
ln 1)
= =CCp,K.B
min
Σ 11 - -Mall
1--1
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly state the paper's contributions and scope in both the abstract and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Addressed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification: Assumptions are fully listed in the main text, and referenced in the statement
of each theorem/propposition in Sections 3 and
All the proofs are provided in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We provide all the information needed to reproduce the sinulation//epprrmmntt results in Sections and 5.2] Our simulation system is so simple, with error rates controlled directly, that it should straightforward to reproduce the results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Unfortunately, part of BLS dataset is no longer public. We plan to release quick tutorial code on Github shortly.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://ni cc/
public/ wwwdgeeeooeeduuunniieemmoo ss sonssoooooooo ollcy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See NeurlPS code and data submission guidelines (https
/ //nips. httccc/pbbbb wtcp/pbblcc/gee wpppliccguiiees...p.ppepppp...pe SCoeseubddeemeimee ss onPol icyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental settings are pretty simple and we include the necessary information about the details in our main text.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We present 1-standard deviation error bars in our simulation results in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
It does not require huge computing resources. A standard laptop should suffice.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our study conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
No societal impact of the work performed. See Section 7 for further details.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We clearly cited the original papers that produced the code package, and stated the source of datasets used for our experiments.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paaperswi haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "ADcbgmax99", "reviewer": "Reviewer_geg3", "summary": "The paper deals with problems arising in understanding treatment response/effects and in particular evaluating subgroup effects building on recent work using causal k-means clustering. The main contribution of the paper is to circumvent the k-means approach and suggest a hierarchical and also a density-based clustering approach. The authors present associated estimators with their proposed methods and rate of convergence, thus extending the framework of causal clsutering.\n\nThe paper is motivated by the study of heterogeneous treatment effects via clustering and highlights the drawbacks of prior work based on k-means. The authors extend this by applying density-based clustering which has the advantage of finding clusters with arbitrary shapes and sizes and appears to be more robust to noise and outliers. Similarly, the observe that hierarchical clustering has some advantages in scenarios where the data are nested or are forming hierarchies.\n\nThe main results are:\n\n-Th. 3.1: The authors analyze the robust hierarchical clustering algorithm appearing in prior works [5], in the context of causal clustering. Under certain assumptions, that are related to so-called good-neighborhood properties as defined in [5] the authors manage to show that having access to a small random subset of the data can allow for their algorithm to have small error on the entire data set.\n\n-Th. 4.1: Analogous statement for the density-based clustering methods.\n\nFinally the authors presented experiments for studying finite-sample properties of their proposed plug-in procedures using simulated data.", "questions": "-To improve the results, I was wondering if there are other notions of error, for which your results can be extended? What if we measure error for example on the hierarchy that is being found? There are various notions for comparing hierarchies in the literature and I believe this could be interesting and novel extension of your work.", "limitations": "-see above.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+analysis for robust hierarchical clustering and density-based methods seems interesting\n\n+natural algorithms and problems are well-motivated", "weaknesses": "-despite the well-motiaveted setting, the reviewer believes that the paper has a lack of novelty: the algorithms are already from previous works, and most of the approaches are what was expected. \n\n-presentation can be improved. As of now, it is a bit cryptic, as the main tasks/problems are not well-defined and rather are to be implied from the context. I would have loved to see a clean definition of the problem that is being solved, the challenges and the novel approach. As of now, I believe the results are a plug-in approach based on two well-studied algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable feedback. We would like to address each of your major concerns in the following. \n\n1. **[Novelty of the problem]** Thank you for pointing this out. First, we want to emphasize that the problem of causal clustering is novel; clustering on counterfactual outcomes provides a new framework for analyzing treatment effect heterogeneity, and as far as we know this approach has not addressed (or at the very least, formally addressed) in the literature before, except in Kim et al. (2024). It also differs significantly from other previous attempts in the cluster analysis literature that considered partially observed outcomes or clustering with measurement errors, since in our case the variable to be clustered consists of completely unknown counterfactual functionals (See Section 1.2 of Kim et al. (2024)). Due of the page limits, we just briefly describe the problem in Section 2 and refer readers to Kim et al. (2024) for details, which could confuse them about the problem's novelty. Based on the reviewer's comment, we will explicitly clarify on the problem, setting, and associated challenges.    \n     \n2. **[Contribution]** We would like to stress out that our main contribution is not on the algorithm side, i.e., the use of the robust hierarchical or density-based clustering algorithms. Rather, it is on the theoretical side where we provide conditions under which the plug-in estimator works for each algorithm for causal clustering framework. \n\n    -  The problem of causal clustering poses challenges which do not appear in the previous studies, as we cluster on unknown counterfactual functionals that is to be estimated nonparametrically. Surprisingly, a plug-in approach does NOT always works without strong extra conditions. Kim et al. (2024) showed that, in the case of k-means, even the plug-in estimator will fail without the margin condition, which requires local control of the probability around the Voronoi boundaries; without such structural assumptions, the error cannot be bounded.\n    - The main contributions of our work are found in Sections 3 and 4, where we prove that the two appealing off-the-shelf cluster-analysis techniques can be successfully adopted in the framework of causal clustering using simple plug-in methods without requiring extra strong structural assumptions as opposed to k-means, which requires the margin condition (kim et al. 2024). As outlined in the proof, verifying this is more complicated than one may think. (We will give a brief exposition why this could be a theoretically difficult task in the revised text.) Our plug-in approaches could also be readily extended to clustering with generic pseudo-outcomes, even outside the context of causal inference. This versatility may be considered an additional contribution.\n   \n3. **[Presentation]** As mentioned earlier, and as suggested by the reviewer, we will ensure that our revised paper is more self-contained. We believe this will help clarify the novelty of the problem and our key contribution, ensuring that readers do not experience any confusion.\n\n4. **[Ans to Question]** Thank you for this insightful question. There are two types of error we consider in our work: estimation error of the unknown counterfactual functionals (i.e., the identified regression functions $\\{\\mu_a\\}$) and error regarding to clustering accuracy. I guess your question is related to the latter, or more specifically, whether one may adopt other types of clustering algorithms that can incorporate uncertainty on the hierarchy that is being found. We completely agree that this could lead to fascinating future work, and we will include it in the revised manuscript's discussion section.\n\n\nWe hope the above response addresses your concerns. However, if there are any remaining issues, please feel free to let us know through your comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LossWUDwFX", "reviewer": "Reviewer_STix", "summary": "The authors propose an extension of existing causal (i.e., treatment effect heterogeneity) k-means clustering techniques to hierarchical and density-based clustering, including novel estimators and convergence guarantees.\n\n**Edit**: increased rating from 3 to 7 (with the understanding that more qualified people (ACs/PCs/ethicists) will look into the plagiarism concern)", "questions": "1. line 134: Is $d$ a distance function (which by definition is positive when evaluated on distinct objects) or some weaker notion with image $[-1, 1]$?\n2. line 164: Can the authors elaborate on why \"the true target hierarcy... is an infinite set of clusters\"?\n3. line 338: What are some examples of such subsequent learning tasks?", "limitations": "Assumptions are clearly stated throughout the text, and general limitations are explicitly discussed at the end.\n\nHowever, I would expect to see some discussion about how this work (which facilitates targeted interventions on specific subgroups) relates to issues of fairness/bias. At the very least, a more complete answer to Question 10 in the author checklist should be given, following the guidelines: \"If the authors answer NA or No, they should explain why their work has no societal impact\".", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The topic of causal clustering has already been addressed from variety of perspectives in previous work (e.g., kernel methods suitable for k-means, hierarchical, and density-based clustering, as well as focusing on heterogeneity in terms of causal structure or causal mechanisms), but this work nevertheless finds an original approach (hierarchical/density-based clustering for treatment effect heterogeneity), which is clearly motivated, has high quality theoretical justifications, and should be significant in the (theoretical and applied) causal inference community.", "weaknesses": "The main weakness (and why my overall rating is a 3 instead of more like a 6 or 7), is the inappropriate verbatim copying from reference [36] (Kwangho Kim, Jisu Kim, and Edward H Kennedy. Causal k-means clustering. arXiv preprint arXiv:2405.03083, 2024.), including the following (and I assume more):\n- lines 7,8: \"We present...\"\n- lines 18--20: mostly copied verbatim from abstract of [36]\n- lines 91--99: in its entirety\n- lines 104,105: \"If all coordinates...\"\n\nThe figures (espcially 4, which requires over 400% maginification) are too small to be legible on standard paper sizes, making it harder to understand or corroborate the results described in the text. Furthermore, the unreasonably small figures save up to a page of space, allowing more text to be squeezed into the page limit, which seems unfair considering the submission guidelines.\n\nI find the related work discussed in Section 1.2 to be lacking. I would expect to see some reference and discussion/comparison with other previous work on causal clustering (which has focused more on heterogeneity in terms of causal mechanisms and causal structure rather than treatment effect), for example including:\n- Hu, S., Chen, Z., Partovi Nia, V., Chan, L., & Geng, Y. (2018). Causal inference and mechanism clustering of a mixture of additive noise models. Advances in Neural Information Processing Systems, 31.\n- Huang, B., Zhang, K., Xie, P., Gong, M., Xing, E. P., & Glymour, C. (2019). Specific and shared causal relation modeling and mechanism-based clustering. Advances in Neural Information Processing Systems, 32.\n- Saeed, B., Panigrahi, S., & Uhler, C. (2020). Causal structure discovery from distributions arising from mixtures of DAGs. In International Conference on Machine Learning (pp. 8336-8345). PMLR.\n- Markham, A., Das, R., & Grosse-Wentrup, M. (2022). A distance covariance-based kernel for nonlinear causal clustering in heterogeneous populations. In Conference on Causal Learning and Reasoning (pp. 542-558). PMLR.\n\nMaybe experimental comparison against some of the above methods is also possible/desirable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thorough feedback. We have addressed each of your concerns as outlined below. \n\n1. **[Originality and related work]** Thank you for highlighting the connection between our research and other works in the literature on causal discovery or structural causal models. To our knowledge, there are three common ways to express causal/counterfactual quantities: (1) structural equations, (2) causal graphs or structural models, and (3) potential outcomes (counterfactuals). While these languages can complement each other, the target parameters, assumptions, notations, and techniques often differ. We acknowledge that the prior works you mentioned also address the notion of \"causal clustering.\" However, they fall into the second approach (in the context of learning *structural heterogeneity*), whereas ours is based on the third (learning *treatment effect heterogeneity*). This distinction is why we did not include the extensive body of work in causal discovery/structural causal models. To the best of our knowledge, Kim et al. (2024) were the first to formally study the task of analyzing treatment effect heterogeneity via clustering based on the (potentially multivariate) CATE within the potential outcomes framework. In our revised manuscript, we will clearly highlight this difference and define our \"causal clustering\" problem. Additionally, based on your comments, we will add a separate subsection in Section 1 explaining the connection between our approach and others in the causal structure learning literature.\n\n2. **[Figures and Presentation]** Thank you for pointing this out. We agree that some figures, particularly Figure 4, are too small. Since the essential idea to be presented is quite macroscopic (i.e., cluster patterns), we believe that expanding it slightly larger with increased font and legend size can alleviate this issue. We will address this in the amended text, and if necessary, we will move some figures to the Appendix.\n\n3. **[Inappropriate verbatim from [36]]** We appreciate your suggestion regarding this matter. Our reliance on the previous work of Kim et al. (2024) is mainly for describing the motivation, problem, and setup in Sections 1 and 2. The framework is novel within the community, and our intention is to present the problem accurately without distorting its description. (As mentioned above, our problem differs significantly from the causal clustering framework in the causal structure learning literature.) However, we acknowledge that we should avoid using verbatim as much as possible and rephrase where necessary. We will fully address this in the revised text.\n\n    Nonetheless, we would like to emphasize that Sections 3 and 4, which constitute the main contribution of our paper, are entirely original and do not contain any issues related to verbatim content from [36]. Therefore, in our opinion, this should not significantly diminish the value of our paper.\n\n4. **[Ans to Q1]** We apologize: it should be a distance with the image $[0,1]$. We will fix this.\n\n5. **[Ans to Q2]** We apologize for the confusion. As you noted, it is an erroneous expression, and part of the sentence should be revised as follows: \"... with respect to the true target clustering, because we build a set of nested clusters across various resolutions (a hierarchy) such that the target clustering is close to some pruning of that hierarchy.\"\n\n6. **[Ans to Q3]** These could be utilized, for example, to develop precision medicine or optimal policy. We will add specific examples in the discussion section.\n\n7. **[Ethics Review]** This is a very good point. In the last section, we will discuss how the discovered subgroup was formed simply based on similarity in treatment effect, without considering factors such as fairness/bias. We believe that discovering a \"fair subgroup\" would be an intriguing future project of our work.\n\n\bIf there are any remaining issues, please feel free to let us know through your comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hq1s2CUYIm", "reviewer": "Reviewer_Ykrk", "summary": "This work solves the task of clustering treatment-effect data based on their conditional treatment effect with a discrete set of treatments and continuous (possibly multivariate) effects. More specifically, they extend the framework of previous work on causal k-means which achieves the same, albeit which is now applied on density-based (hierarchical) clustering.\n\nSimilar to the work on causal k-means, the authors opt for clustering samples based on their signature in the CATE space, i.e., a Euclidean vector whose elements are the avg. treatment effect given each treatment, jointly with an appropriate plugin estimator. To bound the error of the resulting pruning tree, they first extend the concept of $(\\alpha,\\nu)-$good neighbourhood to incorporate a general distribution (in the original work the empirical one is is used) and then adapt the main result of that work to their extension. To extend this framework to hierarchical clustering they employ Balcan et al's (2014) method, which provides an algorithm that has low (up to O(n) ) complexity and is robust to outliers, among other traits. Importantly, they extend the error bounds of the latter method to the causal case, which shows a small discounting of the accuracy due to the added CATE estimation overhead.\n\nThey demonstrate their result on synthetic and real world datasets, which are nicely visualised for 2D.", "questions": "1. In your work you make an extensive ue of the density of the sample points $(X,Y)$; however, the Housdorff distance definition you provide (ln. 247) seems to be oblivious to this distribution, only sensitive to the envelope of these points. Could you comment on this?\n\n2. See questions on presentation above.\n\n3. You may comment on comparisons section, above.\n\n4. You may comment on the plug in estimator as mentioned above.\n\n5. The use of CATE as a clustering domain seems to have its merits; here, the conditioning set seems to be completely ignored, up to the estimation of these vectors, themselves. Say, two very different patients (in terms of X) that have similar CATE profiles would be clustered together; from a standard causal perpsective using a DAG-based SCM, this would amount to splitting the dataset in sub-parts (clusters) which might not be well aligned with the varialbes of the underlying SCM, and could make downstream structural causal learning tasks harder. Could you comment on this?\n\n6. Could you comment on my understanding of the hyperparameter need (see limitations)?", "limitations": "The authors make a good effort to be open on the criticisms of certain standard assumptions in the field of causality, which do not, however, hurt the validity of the method.\n\nAnother basic limitation that seems to be inherited from the use of Balcan et al's work which requires the a-priori specification of the $\\alpha, \\nu$ hyper parameters, for which there does not seem to be a good way to intuitively specify.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The work provides theorems to rigorously derive a bound on the error of the resulting outcome.\n2. The assumptions make sense and are well studied.", "weaknesses": "# Contextualisation\nThis work does mention several other methods closel or loosely related with the task at hand, however none of these other methods have been compared against in the experiments. Although this could well be justified as providing an isolated work providing the respective theory for this specific approach, the case that the authors make could be strengthened by comparing with other methods. For instance, those extracting causal rules, or a step-wise clustering approach that first estimates the CATE and then applies clustering on it. Other density based clustering methods could also be used, for instance hierarchical DBSCAN [1] which is also considered a robust method, or even with causal k-means on the estimated CATE vectors. The point here would not necessarilly be to justify the superiority of Balcan et al's method (which arguably is also not too concerned with this in the first place), but to also study experimentally the superiority of their theoretically superior results.\n\n```\n[1] Ricardo J. G. B. Campello, Davoud Moulavi, Joerg Sander: Density-Based Clustering Based on Hierarchical Density Estimates. In: Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, Berlin, Heidelberg 2013\n```\n\nAdditionally, this work borrows from two key works, the causal k-means and the Balcan et al's method, but the extensions and modifications of thie present work are contributions which can at some times be unclear.\n\n# Plug in estimator\nThe kernel density estimate can often be criticised due to its weaknesses, for instance its susceptibility to the curse of dimensionality, need for hyperparameter tuning, etc. How does the method depend on the choice of kernel, beside its Lipschitz constant?\n\n# Presentation\nFirst, I was bothered by the $\\equiv$ sign in line 180. This doesn't seem to be a standard or previously introduced notation. What is the advantage of using this over an equals sign? Do you want to stress that $\\mathbb C$ is some ball, itself?\n\nAdditionally, I believe it would be easier for the reader if you broke down the definition 3.1 of or provided intuitive explanations of the $\\nu$-strict and $\\alpha$-good parts of it, similar to the Balcan et al. work, mutatis mutandis for your distirbution-general extension.\n\nSome minor typos:\n* 115: us harness$\\rightarrow$us to harness\n* 200: have$\\rightarrow$has\n* 210: arbitrarily sized\n* The legend and labels in Figure 4 are too small to be legible when printed on paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable input and insights. We address each of your\ncomments below.\n\n1.  **\\[Clarification on contributions\\]** Thank you for bringing our\n    attention to this. The main contributions of our work is that we\n    have proved that the two appealing off-the-shelf cluster-analysis\n    techniques can be successfully adopted within the novel framework of\n    causal clustering, using simple plug-in methods without requiring\n    additional strong structural assumptions as opposed to k-means,\n    which requires the margin condition (kim et al. 2024). For example,\n    in Section 3, we demonstrate that the robust inductive hierarchical\n    clustering method (Balcan el al. 2014) may be applied to causal\n    clustering through the plug-in estimator with minimal assumptions,\n    and we analytically validate the associated costs in Theorem 3.1.\n    Verifying this is not as straightforward as one may imagine. We will\n    state our contributions more clearly in Section 1, particularly in\n    relation to kim et al. (2024) and key references in Sections 3 & 4.\n\n2.  **\\[Experimental comparison\\]** Relatedly, yes, we completely agree\n    that our work could be strengthened by experimentally comparing with\n    other methods such as hdbscan, if other methods require any special\n    assumptions that are not present in ours (like the margin-type\n    conditions as in k-means) to be employed in the causal clustering\n    framework. However, this would require a closer analysis at those\n    methods. If other alternatives do not require particularly stronger\n    assumptions and can be readily integrated into the causal clustering\n    framework as well (though this must be verified), then the problem\n    turns to which approach to use for specific data. Since each\n    clustering algorithm has its own pros and demerits, it is difficult\n    to conduct a fair comparison using experiments. Given these\n    circumstances, we believe that designing a fair experiment to\n    demonstrate the superiority of our proposed methods is not quite\n    straightforward, and that's outside the scope of this paper. (Please\n    let us know if we misinterpret your intention here). Following your\n    comment, however, we will provide a brief discussion of the\n    potential extension to other clustering algorithms.\n\n3.  **\\[Plug-in KDE\\]** As pointed out, our plug-in estimator\n    essentially inherits pros and cons of the standard KDE (in level-set\n    clustering). In theory and practice, the choice of the kernel\n    affects the performance of KDE through the bandwidth, and when the\n    bandwidth is appropriately chosen, the shape of the kernel has\n    little effect on the performance. In kernel density estimation\n    (KDE), Gaussian kernel has the advantage that the number of modes\n    monotonically decreases as the bandwidth increases (Silverman, 1981,\n    Using kernel density estimates to investigate multimodality). In\n    kernel regression, Epanechnikov kernel is the most efficient in the\n    constant term of mean integrated squared error, but other usual\n    kernels (including Gaussian) are at least \\~90% efficient. Other\n    than these effects, the shape of the kernel does not affect the\n    convergence rate and has little effect on learning error by less\n    than \\~10% on the constant. The choice of kernel has no effect on\n    our results (but it may in real data studies).\n\n4.  **\\[Issues with presentation\\]** Thank you for pointing these out.\n\n    -   We shall remove the $\\equiv$ signs, which had been often used to\n        emphasize notational \\\"equivalence,\\\" and replace them with\n        standard equal signs.\n\n    -   We totally agree it should be better to broke down the\n        definition 3.1 as in the original work of Balcan et al. Will do\n        that accordingly in the revised manuscript (or at least in the\n        appendix).\n\n    -   Thank you for correcting the typos; during revision, we will fix\n        everything and proofread thoroughly.\n\n5.  **\\[Ans to Q1\\]** As you have mentioned, the Hausdorff distance\n    $H(S_{1}, S_{2})$ is oblivious to the density but only sensitive to\n    the envelope: given that we already have enough points in a specific region, adding more points does not meaningfully change the Hausdorff distance. However, we are looking at the level sets $L_{t,h}=\\\\{w\\in \\mathbb{R}^{q}: p_{h}(w)>t\\\\}$ for $t>0$, and their estimators $\\hat{L}\\_{t,h}$ for $t>0$. Then the density information is encoded through the data points in the level sets. For example,\n    if one distribution has high density regions but the other does not,\n    then for a large $t>0$, the level set\n    ${L}\\_{t,h}$ for the first\n    distribution would be nonempty, while the level set for the second\n    distribution would be empty. Hence, although the Hausdorff distance\n    is oblivious to the density, the density is encoded through the\n    level sets $L\\_{t,h}$, and measuring the difference by the Hausdorff\n    distance behaves sensitively with respect to the density of data\n    points.\n\n7.  **\\[Ans to Q5\\]** We believe your insight is correct. We don't yet\n    have a good answer to how to reconcile with the related structural\n    causal learning tasks. As we leave comments for reviewer STix,\n    causal clustering using the SCM approach may yield different results\n    from ours. We will at least comment on this in the discussion\n    section, with the hope of opening up new options for subsequent\n    research.\n\n8.  **\\[Ans to Q6\\]** You are correct - just like Balcan et al (2014)\n    our estimator requires tuning the two noise parameters. We do not\n    propose any good solution for parameter selection in our paper.\n    Nonetheless, Balcan et al. have empirically showed robustness to\n    such parameter tuning, thus we believe our method can inherit this\n    property, albeit further work is needed because these parameters\n    play an essential part in our method. We will add this discussion in\n    the revised work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "keg4sJ6HtE", "reviewer": "Reviewer_xeku", "summary": "The paper aims to understand treatment effect heterogeneity and identify and evaluate subgroup effects. It addresses the challenge of typically unknown subgroup structures by proposing a solution based on causal k-means clustering to assess effect heterogeneity. The approach is improved by integrating hierarchical and density-based clustering algorithms, providing a more nuanced and effective method for identifying and evaluating subgroup effects.", "questions": "1. Among the case studies, the number of covariates is very small. How does the convergence rate of \\hat{\\mu}_a change as the dimension of the covariate space increases? Specifically, how slow does it get in practice as the number of covariates grows? \n2. Do the authors have suggestions on the optimal number of covariates to limit to before applying this method in practice? \n3. Are there any methods the authors can recommend to help identify important covariates that modify the treatment effect?", "limitations": "The authors have addressed the limitations in their discussion section, acknowledging that this method is a useful tool for exploring subgroup structures. They recommend using other methods in combination with their proposed method to inform specific decisions. \n\nOne area for improvement is the interpretation of the subgroup cluster results, which poses another challenge. Could the authors explain how to better interpret the resulting clusters in their application example? Additionally, how can this information be utilized to inform decisions afterward? Providing more guidance on these aspects would enhance the practical applicability of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper exhibits several strengths across originality, quality, clarity, and significance: \n\nOriginality: The introduction of simple plug-in estimators, implementable with off-the-shelf algorithms, is notable. This approach opens new avenues for clustering with generic pseudo-outcomes and contributes to identifying homogeneous subgroups in treatment response. \nQuality: The paper thoroughly explores finite sample properties via simulation, with a setup similar to prior studies. The rate of convergence is presented, and the inclusion of standard error bars in the graphs adds to the reliability of the results. \nClarity: The experiments are straightforward and concise, with all necessary details provided. The graphs are clear and effectively convey the results. \nSignificance: The paper significantly contributes to the progression of methodologies for identifying homogeneous subgroups in treatment response.", "weaknesses": "The paper lacks a comparative analysis of the method's performance against existing methods in the empirical analysis section. Specifically, it does not demonstrate if the new method captures the underlying structure more accurately than other existing methods. Including such comparisons would strengthen the paper and make its contributions more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable comments and suggestions. We address each of\nthem below.\n\n1.  **\\[Experimental comparison\\]** Yes, we completely agree that our\n    work could be strengthened by experimentally comparing with other\n    clustering methods, especially if other methods require any special\n    assumptions that are not present in ours (like the margin-type\n    conditions as in k-means) to be employed in the causal clustering\n    framework. However, this would require a closer analysis at those\n    methods. If other alternatives do not require particularly stronger\n    assumptions and can be readily integrated into the causal clustering\n    framework as well (though this must be theoretically verified as in\n    our work), then the problem turns to which approach to use for\n    specific data. Because each clustering algorithm has benefits and\n    drawbacks, it is difficult to conduct a fair comparison using\n    experiments. Given these circumstances, we believe that designing a\n    fair experiment to demonstrate the superiority of our proposed\n    methods is not quite straightforward, and that's outside the scope\n    of this paper.\n\n    Furthermore, comparisons with other \\\"causal clustering\\\"\n    counterparts in the SCM literature appear unclear because they are\n    designed to analyze structural heterogeneity, whereas ours is\n    designed to analyze treatment effect heterogeneity. We may consider\n    some special data generation process where we may demonstrate\n    superiority of our method, yet this might not be convincing.\n\n    All in all, we believe that confining our work to presenting the\n    respective theory that the two appealing off-the-shelf\n    cluster-analysis methods can be successfully adopted within the\n    novel framework of causal clustering would suffice for the time\n    being. Nonetheless, following your comment, we will go over the\n    potential extension to other clustering algorithms in the discussion\n    section in the revised manuscript.\n\n2.  **\\[Ans to Q1\\]** This is a good question. The rate of convergence\n    of regression functions in nonparametric modeling is well studied\n    (e.g., Györfi, 2002). It depends on both the function space to which\n    the true $\\mu_a$ belongs and the estimator itself $\\hat{\\mu}_a$;\n    e.g., for $\\mu_a$ in the Holder class with smoothness $s$, given\n    $dim(X)=d$, the best (in minimax sense) rates are\n    $O(n^{-\\frac{s}{2s+d}})$. If $\\mu_a$ is not smooth enough, then\n    high-dimensional covariates will increase uncertainty of our\n    estimators.\n\n    In fact, in our simulation in Section 5.1., we incorporated the\n    effect of the number of covariates by directly controlling the\n    convergence rate through a parameter $\\beta$, i.e., by letting\n    $\\Vert \\hat{\\mu}_a - \\mu_a\\Vert = O_P(n^{-\\beta})$. The results are\n    presented in Figure 2 (we will magnify this figure in the revised\n    manuscript).\n\n3.  **\\[Ans to Q2\\]** In our opinion, there is no precise answer to this\n    question. As previously stated, the smaller the number of covariates\n    ($=d$), the lower the estimation error. However, additional\n    components also interact with $d$. For example, in density-based\n    clustering, we have bandwidth that is entangled with $d$, both of\n    which affect the error. More importantly, if we use only a small\n    number of covariates, the no-unmeasured confounding assumption\n    (Assumption C2) is likely to be violated; we usually collect as many\n    covariates as possible to ensure there is no nmeasured confounders\n    left. All of these factors must be considered simultaneously.\n\n4.  **\\[Ans to Q3\\]** This leads to an entirely different, but\n    interesting question. Given a collection of covariates, one can\n    accurately estimate the CATE function using approaches such as\n    Kennedy (2023), and then apply an algorithm to determine which\n    covariate (or combination of covariates) has the most impact on the\n    treatment effect. Or based on our methods, one can analyze the\n    covariate distributions across clusters and determine which\n    covariate results in the greatest distributional divergence in\n    subgroup effects. We will add this comment in our revised\n    manuscript.\n\n5.  **\\[Interpretation\\]** This is also a great question. One possible\n    interpretation is that each cluster has its own subpopulation from\n    which units are generated. Properties of each subpopulation could be\n    studied by analyzing distributional features, etc. However, as we\n    highlighted in the Discussion section as a shortcoming, while our\n    approach allows for efficient discovery of subgroup structures,, it\n    may be less effective for prescriptive applications (i.e., informing\n    specific treatment decisions). Thus, it is important to exercise\n    caution while attempting to interpret the observed clusters.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the important problem of treatment effect heterogeneity.  It does not present a new algorithm, but relies broadly on causal k-means clustering, and it presents a new and improved theoretical analysis that contributes insights.  There was a robust discussion with reviewers.  Initially two were positive and two were not, and one of the two who initially were not was swayed to be the most positive of all.  The authors should address the concerns of all reviewers in the revision, and especially should make the changes they described in their replies.  Most notably, they should rewrite the background text about which there was some discussion with reviewers, both to make the paper more self-contained and to not use text that previously appeared elsewhere.  There was also nice discussion with reviewers about possible next steps, and this would be nice to see summarized in a conclusions or future work section.
Decision: Accept (poster)