Collaborative Causal Discovery with Atomic Interventions
Authors: Raghavendra Addanki
Shiva Kasiviswanathan
Venue: NeurIPS 2021 Poster (2021)
Keywords: causal discovery
intervention design
causality
causal inference
collaborative learning
clustering

Abstract: We introduce a new Collaborative Causal Discovery problem, through which we model a common scenario in which we have multiple independent entities each with their own causal graph, and the goal is to simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption, using Maximal Ancestral Graphs (MAG) to model the causal graphs, and assuming that we have the ability to actively perform independent single vertex (or atomic) interventions on the entities. If the $M$ underlying (unknown) causal graphs of the entities satisfy a natural notion of clustering, we give algorithms that leverage this property and recovers all the causal graphs using roughly logarithmic in $M$ number of atomic interventions per entity. These are significantly fewer than $n$ atomic interventions per entity required to learn each causal graph separately, where $n$ is the number of observable nodes in the causal graph. We complement our results with a lower bound and discuss various extensions of our collaborative setting.

Collaborative Causal Discovery with Atomic Interventions
Raghavendra Addanki University of Massachusetts, Amherst raddanki umass.sdd
Shiva Prasad Kasiviswamathan
Amazon kasivisw gmaii.comm
Abstract
We introduce new Collaborative Causal Discovery problem, through which model a common scenario in which we have multiple independent entities each with their own causal graph, and the goal simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption, using Maximal Ancestral Graphs (MAG) model the causal graphs, and assuming that we have the ability to actively perform independent single vertex (or atomic) interventions on the entities. the M underlying (unknown) causal graphs of the entities satisfy a natural notion of clustering, we give algorithms that leverage this property, and recovers all the causal graphs using roughly logarithmic in M number of atomic interventions per entity. These are significantly fewer than atomic interventions per entity required learn each causal graph separately, where n is the number of observable nodes in the causal graph. We complement our results with a lower bound and discuss various extensions of our collaborative setting.
Introduction
In this paper, we introduce new model for causal discovery, the problem of learning all the causal relations between variables in a system. Under certain assumptions, using just observational data, some ancestral relations well as certain causal edges can be learned, however, many observationally equivalent structures cannot be distinguished [Zhang, 2008a]. Given this issue, there has been growing interest in learning causal structures using the notion of an intervention described in the Structural Causal Models (SCM) framework introduced by Pearl [2009].
As interventions are expensive (require carefully controlled experiments) and performing multiple interventions is time-consuming, an important goal in causal discovery to design algorithms that utilize simple (preferably, single variable) and fewer interventions [Shanmugam et al., 2015]. However, when there are latents or unobserved variables the system, the worst-case, it not possible to learn the exact causal DAG without intervening every variable least once. Furthermore, multivariable interventions are needed presence of latents [Addanki et al., 2020].
Figure 1: Examples of M causal graphs constructed from Lung Cancer dataset [Lauritzen and Spiegelhalter, 1988]. Here, the causal graphs differ only in the presence of latents (nodes with dotted square box), but they could differ elsewhere too.
ly
D2
DM
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

On the other hand, in a variety of applications. there is no one true causal structure, different entities participating in the application might have different causal structures [Gates and Molenaar, 2012, Ramsey et al., 2011 1, Joffe et al., 2012]. For example, see figure 1. In these scenarios, generating a single causal graph by pooling data from these different entities might lead to flawed conclusions [Saeed et al., 2020]. Allowing for interventions, we propose new model for tackling this problem, referred here as Collaborative Causal Discovery, which in its simplest form states that: given collection of entities, each associated with individual unknown causal graph and generating their own independent data samples, learn all the causal graphs while minimizing the number of atomic (single variable) interventions for every entity. An underlying assumption is that each entity on its own generates enough samples in both the observational and interventional settings so that conditional independence tests can be carried out accurately on each entity separately. To motivate this model of collaborative causal discovery, let us consider two different scenarios.
(a) Consider health organization interested in controlling incidence of particular disease. The orga- nization has set of M individuals (entities) whose data it monitors and can advise interventions on. Each individual is an independent entity that generates its own set of separate data samples' In a realistic scenario, it is highly unlikely that all the M individuals share the same causal graph (e.g., see Figures 3a and 3b from Joffe et al. [2012] in Appendix A). would be beneficial for the organization to collaboratively learn all the causal graphs together. The challenge is, priori the organization does not know the set of possible causal graphs or which individual is associated with which graph from this set.
(b) An alternate setting is where, we have M companies (entities) wanting to work together to improve their production process. Each company generates their own data (e.g., from their machines) which they can observe and intervene on [Nguyen et al., 2016]. Again if we take the M causal graphs (one associated with each company) it is quite natural to expect some variation in their structure, more so because we do not assume causal sufficiency (i.e., we allow for latents). Since interventions might need expensive and careful experimental organization, each company would like to reduce their share of interventions.
The collaborative aspect of learning can be utilized if we assume that there is some underlying (unknown) clustering/grouping of the causal graphs on the entities.
Our Contributions. We formally introduce the collaborative causal discovery problem in Section 2. We assume that we have collection of M entities that can be partitioned into & clusters such that any pair of entities belonging to two different clusters are separated by large distance (see Definition 2.1) in the causal graphs. Due to presence of latents variables, we use a family of mixed graphs known as maximal ancestral graphs (MAGs) to model the graphs on observed variables. Each entity is associated with a MAG.
In this paper, we focus on designing algorithms that have worst-case guarantees on the number of atomic interventions needed to recover (or approximately recover) the MAG of each entity. We assume that there are M MAGs one for each entity over the same set of n nodes. Learning a MAG with atomic interventions, in worst case requires interventions (see Proposition 3.2). We show that this bound can be substantially reduced if the M MAGs satisfy the property that every pair of MAGs from different clusters have at least an nodes whose direct causal relationships are different. We further assume that entities belonging to same cluster have similar MAGs in that every pair of them have at most 3nn (3 < a) nodes whose direct causal relationships are different. We refer to this clustering of entities as (a., 3) -luusteeg (Definition 2.2). A special but important case is when / = O. in which case all the entities belonging to the same cluster have the same causal MAG (referred to as a-clustering, Definition 2.3). An important point to notice is that while we assume there is underlying clustering on the entities, it is learnl by our algorithms. Similar assumptions are common for recovering the underlying clusters, in many areas, for e.g., crowd-sourcing applications [Ashtiani et al., 2016, Awasthi et al., 2012].
We first start with the observation that under (a, 3) -)-clusteiing, even entities belonging to the same cluster could have different MAG, which makes exact recovery hard without making significant number of interventions per entity. We present an algorithm that using at most O( log(M/5) M/ 3)2) many interventions per entity, with probability at least 5 (over only the randomness of the algorithm), can provably recover an approximate MAG for each entity. The approximation is such
As is common in causal discovery, for the underlying conditional independence tests, the data is assumed to be i.idd. samples from the interventionallooeevvatnnn distributions.

---

that for each entity we generate MAG that is at most In node-distance from the true MAG of that entity (see Section 3). Here, A is the maximum undirected degree of the causal MAGs. Our idea is to first recover the underlying clustering of entities by using randomized set of interventions. Then, we distribute the interventions across the entities in each cluster, thereby, ensuring that the number of interventions per entity is small. By carefully combining the results learnt from these interventions we construct the approximate MAGs. For the number of interventions, the linear dependence on Á is not uncommon for learning causal graphs [Kocaoglu et al., 2017]. Moreover, most real-world causal bayesian networks are known to have small maximum degrees (see section 5).
Under the slightly more restrictive a-clustering assumption, we present algorithms that can ex- actly recover all the MAGs using at most min {O log( /8)/a.) ([log( (M/8)/a + k²)} many interventions per entity (see Section 4). Again, randomization plays an important role in our approach.
Complementing these upper bounds, give lower bound using Yao's minimax principle [Yao, 1977] that shows for any (randomized or deterministic) algorithm (2(1/a) interventions per entity is required for this causal discovery problem. This implies the 1/a dependence in our upper bound in the a-clustering case is optimal.
Finally, note about parameters. The (ax, ---llutteii is universal, in the sense that any collection of MAGs will satisfy the (a, -luustern property for some value of a, 3 (with a > 3). Ideally, would like in our problem instance, to be close to 1 and 3 to be close to O. In most real-world applications, we would also expect & to be relatively small and M >
n, k.
In Section 5, we show experiments on data generated from both real and synthetic networks with added latents and demonstrate the efficacy of our algorithms for learning the underlying clustering and the MAGs.
Related Work. A number of algorithms, working under various assumptions, for learning causal graph (or a causal DAG) using interventions have been proposed in the literature, e.g., [Eberhardt, 2007, Hyttinen et al., 2013, Hu al., 2014, Shanmugam al., 2015, Kocaoglu et al., 2017, Ghassami et al., 2018, Lindgren et al., 2018, Acharya et al., 2018, Bello and Honorio, 2018, Kocaoglu et al., 2019, Greenewald et al., 2019, Jaber al., 2020, Addanki al., 2020, 2021, Tadepalli and Russell, 2021]. Saeed et al. [2020] consider model where the observational data is from mixture of causal DAGs, and outline ideas that recover a union graph (up to Markov equivalence) of these DAGs, without any interventions. Our setting is not directly comparable to theirs, as we have entities generating data and doing conditional independence tests independently (no pooling of data from entities), but show stronger guarantees for recovering causal graphs, assuming atomic interventions.
2 Our Model and Problem Statement
In this section, we introduce the collaborative causal discovery problem. We start with some notations.
Notation. Following the SCM framework [Pearl, 2009], we represent the set of random variables of interest by L where V represents the set of endogenous (observed) variables that can be measured and L represents the set of exogenous (latent) variables that cannot be measured. We do not deal with selection bias in this paper. Let [V| n..
We assume that the causal Markov condition and faithfulness holds for both the observational and interventional distributions [Hauser and Bühlmann, 2012]. We use conditional independence (CI) tests of the form l u Z or w.ll do(w), Z, for some v, w E V and Z C V (See Appendix A for more details).
Throughout this paper, unless otherwise specified, a path between two nodes is an undirected path. A path of only directed edges is called directed path. is called an ancestor of e and descendant of u if u = v or there is directed path from u to v. A directed cycle occurs in G when u - v is in G and v is an ancestor of u.
Our Model. We assume that we have access to M entities labeled 1,..., M, each of which can independently generate their own observational and interventional data. Each entity i has an associated causal DAG D. over V U Ta, where T., represents the latent variables of entity In modeling the problem of causal discovery, complications arise in at least two ways:
3

---

(i) Latents. We allow some variables (called latents) in the causal DAG to be unobservable. As regular DAGs are not sufficient represent the observed distribution when there are latents, we use ancestral graphical models that have been proposed as an elegant and useful surrogate for DAG models with latent variables [Richardson and Spirtes, 2002].
A mixed graph containing directed (+-) and bidirected (++) edges is said to be ancestral if it has directed cycles, and whenever there is bidirected edge <> v, then there is no directed path from u to v or from V to u. An ancestral graph on V (observables) is said to be maximal, if, for every pair of nonadjacent vertices u, U, there exists set Z C V with u, V & Z such that and are m-sepaaated (similar to d-separation, see Definition A.2) conditioned on Z. Every DAG with latents (and selection variables) can be transformed into a unique maximal ancestral graph (MAG) over the observed variables [Richardson and Spirtes, 2002].
(ii) Uniqueness. Secondly, with just observational data, if the MAGs MI,...,, MM are Markoy equivalent, then, without additional strong assumptions they cannot be distinguished, even they are all structurally different. To overcome the problem of being not identifiable within an equivalence class, we allow for interventions on observed variables. In particular, we focus on atomic interventions in this paper, which are the simplest and most commonly used intervention type, modeled through the do-operator [Pearl, 1995]. As turns out, Maximal Ancestral Graphs (MAGs) are uniquely identifiable using atomic interventions.
Our objective will be to minimize these interventions. In particular, since each of these entities independently generate their own data, so we aim to reduce the number of interventions needed per entity. In causal discovery, minimizing the number of interventions while ensuring that they are of small size is an active research area [Pearl, 1995, Shanmugam et al., 2015, Ghassami et al., 2018, 2019].
Given the M entities, let M, denote the MAG associated with entity i (the MAG constructed from the DAG D,). Our goal is collaboratively learn all these MAGs , MM while minimizing the maximum number of interventions per entity.
To facilitate this learning, we make a natural underlying clustering assumption that partitions the entities based on their respective MAGs such that: (i) any two entities belonging to the same cluster have MAGS that are "close" to each other, (ii) any two entities belonging to different clusters have MAGS that are "far" apart. Before stating this assumption formally, we need some definitions.
For MAG M, = (V, E,), we denote the children (through outgoing edges), parent (through incoming edges), and spouse (through bidirected edges) of node u E V
ch, = t0 u u E.), pa, (w) = {u u ut u E.}, (u) = (u wulutee E.). (I)
Also, define an incidence set for a vertex v E V which contains an entry (v., type) for every node e adjacent to as
No(u) = =
(o, tail)
if + V E; if u v E. u + u E E.
(r, head)
c, bidirected)
Note that (w) is the undirected degree of u in M, MAGs that captures structural similarity between them.
We now define a distance measure between
Definition 2.1. Given two MAGs M₁ = (V. E.) and My = Eş), define the node-difference as {u E V (N( # Nu) and the node-distance as the cardinality of this set: ((M (diff My)]= [ N((u) & (y)
the set: diff (M,,
Intuitively, the node distance captures the number of nodes whose incidence relationships differ. It is easy to observe that the node distance is distance metric, and captures a strong structural similarity between the graphs. Two graphs M,, are identical iff d(M;;,,, = 0. For e.g., in Figure 2, we have two MAGS that satisfy d(Mi2, M1a) 2 as diff(MM Mis) {ar, =}, where d(M M21) = 3 as property on MAGs.
{I, y, J. We are now ready to define a simple clustering
However, in the presence of latents, even with power of atomic interventions, structure of causal DAG is not uniquely identifiable. (see, e.g., In Figure 4 in Appendix A). Similarly, we can show that using single vertex interventions, we also cannot exactly recover wider class of acyclic graphs like ADMGs (Acyclic Directed Mixed Graphs).

---

Ma
Mai
Figure 2: MAGs with (a 0.75, 0.5)- clustering. Every pair of graphs in Cj and C2 differ in least 3(= 0.75 4) nodes, while pairs of graphs within clusters differ by at most 2(= 0.5 x 4) nodes.
M
M
Ma
Algorithm 1 IDENTIFY-OUTNEE (u,
Algorithm 2 IDENTIEY-BIDIRECTED (U,, u) PAGU, of entity i
I: Input: node E V, PAG of entity
1: Input: node
Output: ch:(u)
2: Output: sp,(u)
3: ch:(u) = {v
# E U:}
3: sp,(u) {or u 4+ E (4.
4: for v E [T(u) such that uo-ov or uo-vo E U4
4: for v E [=( such that wo-on or ut-ov or
do
n E U4 do
5: u v do(u) then
5: if vulle do(u) and ull do(o) then
ch.(u) - chi(u) {u} 7: end if
sp, (w) + (
end
8: end for
8: end for
9: Return (u)
9: Return (u)
Definition 2.2 ((ar, 3)cclustei Let MI.... MM be a set of M MAGs. We say that this set of
MAGs satisfy the (or, 3) -lllustrii property. with a > B 2 0, if there exists partitioning of [M]
into sets (clusters) Ci...., C C [M] (for some E N) such that for all (i.5) E [M] [M]:
(i) i and j belong to same set (cluster), then d(M;,M, & Bn; (ii) i and ÿ belong to different sets (clusters), then d(Mi, M2) 2 on.
Under this definition, all the M MAGs could be different. See, e.g., Figure 2. With right setting of 39
capture any of possible M MAGs. Therefore, an algorithm such as FCI [Spirtes et al., 2000], that constructs PAGs might not be able to recover the clusters, as all the PAGs could be different, and the
between PAGs does not correlate well with the node-distance between corresponding MAGs (e.g., see Figure in Appendix A). We use the PAGs generated by FCI starting point for all algorithms and further refine them. We assume that PAGs generated correct (see Appendix B.1 for additional details). With this discussion, we introduce our collaborative causal graph learning problem follows:
Assumption: MAGs MI,..., MM (associated with entities 1,..., . respectively) satisfy- ing the (a, -clusttrii property
Access to each entity: Through conditional independence (CI) tests on observational and interventional distributions. Each entity generates their own (independent) data samples. Goal: Learn MI,..., while minimizing the max. number of interventions per entity.
An interesting case of the Definition 2.2 is when 3 = O.
Definition 2.3 (a-clustering). We say a set of MAGs Mı,..., Mas satisfy the a-clustering property. if and only if they satisfy (a, -lluutteni property.
Note that a-clustering is natural property, wherein each cluster is associated with single unique MAG, and all entities in the cluster have the same MAGs, and same conditional independences.
Causal Discovery under (a, (a,,3)-Clustering Property
In this section, present main algorithm for collaboratively learning causal MAGs under the (a. 3))ccuuttiig property. Missing details from this section are presented in Appendix C.
Definition 3.1 (Partial Ancestral Graph (PAG)). Let [M:] denote the Markov equivalence class of the MAG M; and represented by the Partial Ancestral Graph (or PAG) Us (V, F.). Edges F., have three kinds of endpoints given by arrowheads (+), circles (o-) and tails (-).
5

---

All our algorithms are randomized, and succeed with high probability over the randomness introduced by the algorithm. The idea behind all our algorithms to first learn the true clusters CT .i..... Cj using very few interventions. Once the true clusters are recovered, the idea is to distribute the interventions across the entities in each cluster and merge the results learned to recover the MAGs (Section 3.2). For our algorithms, lower bound for and upper bound for / is sufficient. In practice, clustering of the PAGs (generated from FCI algorithm) can provide guidance about these bounds on a, 3, or if we have additional knowledge that [] e, 1] and / E [0, e] for some constant > O, then, we can use binary search, that increases our intervention bounds by log"(ne)) - -2e)a factor. It is important to note that none of our algorithms require the knowledge of k
.....
Helper Routines. Let (u) denote all nodes that are adjacent to u in the PAG U, i.c., r,(x) = {ol (u, u) E.). Given the PAG U4 Algorithm DDENTIFY-OTTNE identifies all the outgoing neighbors of any node u in M₁. We look at edges of the form wo-ov or 4o in 24, incident on u, and identify if u + using the Cl-test w.llo do(u). This is based the observation that any node that is a descendant of u (including (u)( satisfies u J. v do(u). Algorithm
identifies all the bidirected edges incident on If there is an edge of the form uo-ov or ut-ov or 4o0v in the PAG, and v & ch.(u) and & (v), then it must be a bidirected edge.
Using these helper routines, we give an Algorithm RECOVERG (in Appendix B) that recovers any MAG M2 using n atomic interventions. Complementing this, we show that n interventions are also required. The missing details are presented in Appendix B.
Proposition 3.2. There exists a causal MAG M such that every adaptive or non non-adaptive algorithm requires (n) many atomic interventions recover M.
3.1 Recovering the Clusters
From the (ar -lllstttn definition, we know that a pair of entities belonging to the same cluster have higher structural similarity between their MAGs than a pair of entities across different clusters. Let us start with a simplifying assumption that 3 = (i.e., a-clustering). So, all the MAGs are separated by a distance of at least an. We make the observation that to identify that two MAGs, say M, and M, belong to different clusters, it suffices to find a node u from the node-difference set di, and checking their neighbors using Algorithms IDENTIPY-OUTNBR and IDENTIFY- BIDIRECTED. We argue that (see Claim D.3, Appendix D.2), with probability at least 1 - 5, we can identify one such node diff by sampling log (M/8)/a / nodes uniformly from V as (M, because now we have MAGs in the same cluster that are also separated by non-zero distance.
d( d(M,,,M,) 2 an.² However, this approach will not succeed when 3 * 0
Overview of Algorithm (a, [D]--BUNNEDDEGGREE We now build upon the above idea, to recover the true clusters Ci..... Cj when 3 * As identifying node u E (M,, M,) not sufficient, we maintain a count of the number of nodes among the sampled set of nodes S that the pair of entities i have the same neighbors, i.e., COUNT(i.j) = Enes (u) = (u)). Based on a carefully chosen threshold value for the COUNT(i, j), that arises through the analysis of our randomized algorithm, we classify whether a pair of entities belong to the same cluster correctly.
Overall, the idea here is construct graph P on entities (i.e., the node set of P is [M]) We include an edge between two entities i and j if COUNT(i,j) is above the threshold (1 (ax + [S Using Lemma 3.3, we show that this threshold corresponds to the case where if the entities same true clusters, then the COUNT value corresponding to the pair is higher than the threshold; and if they are from different clusters it will be smaller, with high probability. This ensures that every entity is connected only to the entities belonging to the same true cluster. We return the connected components in P as our clusters.
from
Theoretical Guarantees. In Algorithm (a, BJ--BOUNDEDDEGREE. we construct a uniform sample S of size (M/lg 3))),, and identify all the neighbors of S for every entity i [M]. As we use SEENTIFY-BIDIRECTO to identify all the bi-directed edges, the total number of interventions
$ For theoretical analysis, our intervention targets are randomly chosen, even with the knowledge available from PAGs, because in the worst-case the PAGs might contain no directed edges to help decide which nodes to intervene on. In practice, though if we already know edge orientations from PAG we do not have to relear them, and a biased sampling based on edges uncertainties in PAGs might be reasonable approach.

---

Algorithm 3 (2,,))-BUUNDEDDERRR)
1: Input: > 0, 3 0 (< a), confidence parameter 8 > 0, PAGs U1. .u....,uyy of M entities
2: Output: Partition of [M] into clusters
3: Let S denote a uniform sample of 4log(M/5) nodes from V selected with replacement.
[a-3)
4: for every entity & [M] and u E S do
5: ch,(u) <- IDENTIFY-OUTNBER (4,
6:
(P,(u) 6- IDENTIFY- B 7: pa,(u) + r.() (wh U (u))
8: Construct (u) (defined in (2))
9: end for
10: Let P denote an empty graph on set of entities [M]
11: for every pair of entities i do
12: Let COUNT(I. = Enes ((N = (u))
13: if COUNT(1,
- |S| then
Include an edge between and j in
15: end if
end for
17:
Return connected components in P
used by an entity for this step is at most |S]. Combining all the above, using the next lemma, we show that with high probability Algorithm (a,, ( B..DD--OUDEDDDEGREE recovers all the true clusters.
Lemma 3.3. If the underlying MAGs M satisfy (a.33 3)-ussteiiin property with true clusters Ci,-. -i.--- Ct and have maximum undirected degree A. Then, the Algorithm (a,, B3-- BOUNDEDDEGRES recovers the clusters Ci...., C% with probability at least - 8. Every entity i [M] uses at most 4(A + 1) loggMM/8) (a 3)² many atomic interventions.
3.2 Learning Causal Graphs from (a, --Clutteri
In this section, we outline an approach to recover a close approximation of the causal MAGs of all the entities, after correctly recovering the clusters using Algorithm (a, B)n----UDDDDDDRREE First, we note that since the (a, -llcltutg allows the MAGs even in the same cluster to be different, the problem of exactly learning all the MAGs challenging (with small of interventions) as causal edges learnt for an entity may not be relevant for another entity in the same cluster.
In the scenarios mentioned in the introduction, many entities in the same cluster sharing the same MAG. We provide an overview of A Algorithm (a, B)- RECOVERY that recovers one such MAG called dominant MAG for every cluster. Consider recovered cluster C and a partitioning S1 S of MAGs such that all MAGs in partition S are equal for all i. We call the MAG Midom corresponding
expect the clusters be
homogeneous, with
the largest partition Solom as the dominant MAG of Cr, The dominant MAG of a cluster is parameterized by 7a |/C= (fraction of the MAGs in the cluster that belong to the largest partition). We defer additional details of Algorithm (a, RECOVER to Appendix C.I.
Overview of Algorithm (a, 3) REEOVEEY. After recovering the clustering using Algorithm (a, B)- BOUNDED our goal is to learn the causal graphs. Using Algorithm (o,, REEOOEER, we show that
learn these graphs approximately up distance approximation of 3n..
In a cluster C we construct a partitioning of MAGs such that two MAGs belong to a partition they equal. The MAG corresponding to the largest partition is called the dominant MAG. Using our algorithm, we learn the dominant MAG correctly and return it as an output. As all the MAGs in the cluster satisfy (a. -cluutttg property, the dominant MAG is within distance of 3n from the true MAG and therefore is a good approximation of the true MAG.
For learning the dominant MAG, there are two steps. First, we select node uniformly at random for every entity and intervene on the node and its neighbors to learn all the edges incident on the node. Next, we construct the dominant MAG by combining the neighborhoods of each individual node. Let any node and T, denote the set of all entities which intervened on in the first step. Now, among all the neighborhoods identified by the entities in T.,, do not know which of them correspond to
7

---

that of the dominant MAG. In order to identify this, we use a threshold-basee approach and assign a score to every entity in Tu. The score of an entity is the number of entities in T, that has the same neighborhood of as that of entity i. Finally, we select the entity with the maximum score and assign the neighborhood of the entity as the neighborhood of u for the dominant MAG (Lines 12-15 in Algorithm (a, (a,,8)-RECCe EECVEEY) We argue that if the cluster size is large (see Theorem 3.4), the neighborhoods of nodes using entities with maximum scores are equal to that of the dominant MAG. This is because the dominant MAG has the largest partition size, and if sufficiently large number of entities (across all partitions) are assigned node u, then, many of them will be entities from the dominant MAG partition.
As the entities satisfy (a, -eluuttrri property, for all entities the recovered MAGs (dominant MAGs) are close to the true MAGs, and within a distance of at most 5n. Note that any MAG from the cluster is within a distance of at most Bin due to (a, -luustttni property, but naively generating a valid MAG from a cluster will require interventions on one entity from Proposition 3.2. Our actual guarantee is somewhat stronger, as in fact, for the entities whose MAGs are dominant their cluster, we do recover the exact MAGs. We have the result:
Theorem 3.4. Suppose M,, .M satisfy (a.3) clustering property. 2 1/2 and C = 22 log(n/M6) - 1)² for all a E [ki], then, Algorithm (ar, B)--RECOVERY recovers graphs MM,.... MM such that for every entity i E [M], we have d( d(Mi..M.) M.) S Bn with probability
1 1- 8. Every entity uses at most (A +) + + 1) log(M/6)/ - 3) many atomic interventions.
4 Causal Discovery under a-Clustering Property
In the previous section, we discussed the more general (a, -lllusteti scenario where we manage to construct good approximation to all the MAGs. Now, we show that we can in fact recover all the MAGs exactly, if we make a stronger assumption. Suppose the MAGS Mı,..., entities satisfy the a-clustering property (Defn. 2.3). Firstly, we can design an algorithm similar to Algorithm (ax SJ-BOUNDEDDEERRE (see Algorithm a- (-BOUNDEDDEGRRE
of the M
Appendix D.3) that recovers the causal MAGs exactly with O log( /a) many interventions per entity, succeeding with probability 1 - 8. Note that this has a better 1/a term in the intervention bound, instead of 1/a² (when 3 = 0) term arising in Theorem 3.4. In absence of latents, we can further improve it to (llo(MM/8)/o) many interventions per entity (see Algorithm NOLATENTS, Appendix D.2).
In this section, we present another approach (Algorithm a-GENERAL) with an improved result that requires fewer number of interventions, even when A is big, provided that each cluster has at least On (0))) entities. Missing details of Algorithm G-GENERAL are in Appendix D.4.
Overview of Algorithm a-GENERAL. First, using a similar approach as Algorithm (ax, BOUNDED we construct a uniform sample 5 C V, and find all the outgoing neighbors of nodes in S, for every entity i [M]. Then, we construct a graph on entities denoted by P, where we include an edge between pair of entities if the outgoing neighbors of the set of sampled nodes S, and the set of neighbors in PAGs associated with the entities (obtained from FCI) are the same. However, due to the presence of bidirected edges, it is possible that the connected components of P may not represent the true clusters CJ,.... Cr.
We make the observation that pair of entities i,j that have an edge in this P and from different true clusters, can differ only if there directed edge <- v in M, (or vice-versa). Intervening on both and will separate these entities, our main idea is to ensure that this happens. First, we show how to detect if there are least two true clusters in any connected component of P. Then, we identify all the entities belonging to these two clusters and remove the edges between these entities in P and continue.
node u such that has a bidirected edge u ++ in M,, and a
More formally, let Ti....,Tr The be the partition of [M]] provided by the K' connected components of PP and some of these can contain more than one true cluster, hence k < and we focus on detecting such events. Let क. [M] + V denote a mapping from the set of entities to the nodes in V such that (i) is chosen uniformly at random from V for every entity For every entity i, we intervene on the node (i). To detect that there are at least two clusters in given subset To of entities, we show that there are two entities i,j with an edge in P and for some node u E S, we can identify the neighbor e E [2(w) n T3 (u) such that u <-> V is an edge in M; and u + e is an edge in M, (or vice-versa). As there are at least Q(n log( M/)) entities in each of these two true clusters in T for
some i,j E Ta. we can show that 7 (1) n m = e with probability at least 1 8.
8

---

After detecting the event that component Ta of P contains entities from at least two different true clusters (say, č and C²2) due an edge (u, v) as above, we intervene on for every entity in T. By intervening on v (and u E S), we can separate all entities in Ta that belong to true clusters Cj and C; and remove edges between such entity pairs from P. We repeat this above procedure of refining P. In each iteration, we will have removed all edges between every pair of entities belonging to at least two different true clusters. Since there are at most k² different true cluster pairs, after ka iterations the connected components remaining correspond to the true clusters (with high probability). This can be done without knowing the value of k, by checking whether the connected components in P change or not after each iteration of the above idea.
Going from Clustering to MAGs. The idea of going from clusters to MAGs is simple and based on distributing the interventions across the entities in the cluster. Since under a-clustering, enti- ties belonging to cluster share the same MAG, combining the results is relatively simpler (see Appendix D.1). Combining the guarantees of a- G--GENERAL and o-BOUNDEDDEGGRER we have:
Theorem 4.1. If MAGs Mi...., MM M satisfy a-clustering property with true clusters Ci,...,C Ot such that minse[s] [Oğ] =
Then, there is an algorithm that exactly learns all these MAGs with probability at least 1 - 5. Every entity min linfOOl {O(A (og((M)))aa)) ((log(M/6)/< }²)} many atomic interventions.
Mn (M)
E [M]] uses
Lower Bound on the Number of Interventions. We now give a lower bound on the number of atomic interventions needed for every algorithm that recovers the true clusters the MAGs M1,M2,.... -MM- Since a lower bound under a-clustering is also a lower bound under (a,, 8)- clustering, we work with the a-clustering property here. First, we show that to identify whether given pair of entities i.j belong to the same true cluster or not, every (randomized or deterministic) algorithm must make (11/a) interventions for both and j.
Our main idea here is to use the famous Yao's minimax theorem [Yao, 1977] to get lower bounds on randomized algorithms. Yao's theorem states that average case lower bound deterministic algorithm implics a worst case lower bound on randomized algorithms. To show a lower bound using Yao's 's minimax theorem, deterministic algorithm requires (2(1/a)) interventions for distinguishing a pair of MAGs drawn from μ.. The construction of this distribution is presented in Appendix D.5. We summarize the result:
construct distribution μ on MAG pairs and show that every
Theorem 4.2. Suppose the underlying MAGs Mı,..., satisfy a-clustering property. In order to recover the clusters with probability 2/3, every (randomized or deterministic) algorithm requires (11/a) interventions for every entity in [M].
Experimental Evaluation
In this section, we provide an evaluation of our approaches on data generated from real and synthetic causal networks for learning MAGs satisfying (a, -9l-sterrii property. We defer additional details, results, and evaluation for a-clustering to Appendix E.
Causal Networks. We consider the following real-world Bayesian networks from the Bayesian Network Repository which cover a wide variety of domains: Asia (Lung cancer) (8 nodes, 8 edges), Earthquake (5 nodes, 4 edges), Sachs (Protein networks) (11 nodes, 17 edges), and Survey (6 nodes, 6 edges). For the synthetic data, we use Erdös- Rényi random graphs (10 nodes). We use the term "causal network" to refer to these ground-truth Bayesian networks.
Parameters. For each causal network, we start from the corresponding DAG, and generate M MAGs (one for each entity) split into & clusters that satisfy the (a,, -)-clusttriing property through random changes to the graph. We also randomly introduce two latents in each graph, and account for them in MAG constructions. For more details, refer Appendix E. We set number of entities M = 40, number of clusters & = 2. a = 0.60, 3 = 0.20, and dominant MAG parameter y = 0.90 for both the clusters. For the synthetic data generated using Erdös-Rény? model, we use 10, probability of edge 0.3.
Evaluation of Clustering. First, we focus on recovering the clustering using Algorithm (a, B)- BOUNDEDDEGREE, As a baseline. we employ the well-studied FCI algorithm based on purely observational data [Spirtes et al., 2000]. After recovering the PAGs corresponding to the MAGs using FCI, we cluster them by constructing a similarity graph (similar to (a, B)J-D-ODNEEEDEEEEEEE defined on the set of entities (refer Appendix E for more details). For Algorithm (a, ().-)))) BO- we first construct sample S, and perform various interventions based on the set S for every entity

---

Causal
FCI
(a, 8) S>-BBNDDDDDGGEE (Alg. 3)
Maximum
Network
Presision
Recall
Accuracy
Precision
Accurncy
Interventions
Earthquake
0.57 1: 0.18
0.94 + 0.013
0.58 +: 0.18
0.78 1 0.24
0.92 1 0.03
0.77 1 0.23
Survey
0.62 1: 0.21
0.94 + 0.013
0.62 1: 0.2
0.64 1: 0.23
0.97 0.02
0.63 1 0.23
Asia
0.57 + 0.18
0.94 = 0.013
0.58 + 0.18
0.92 4 0.14
0.96 + 0.03
0.91
+ 0.14
5
Sacks
0.52 0.12
0.94 0.01
0.52
1: 0.12
0.20
0.96 0.02
0.88 0.19
Endai-Rówyi
0.62 + 0.21
0.94 = 0.02
0.62 - 0.21
1.0 # 0.00
0.95 2 0.02
0.97
0.013
Table 1: In this table, we present the precision, recall and accuracy values obtained by our Algo- rithm (ar, BJ-BBOUNDEDEEGREE and using FCI. Each cell includes the mean value along with the standard deviation computed over 10 runs. The last column represents the maximum number of inter- ventions per entity including both Algorithms (a, BOUDDEDDDDDE and (a, 3) -E-CEEEYRY..
to obtain the clusters. We also implemented another baseline algorithm (GreeDY) that uses inter- ventions, based on greedy idea that selects nodes to set S in Algorithm (a, B)-BoUNDEDDEGREE by considering nodes in increasing order of their degree in the PAGs returned by FCI. We use this ordering to minimize the no, of interventions as we intervene on every node in S and their neighbors.
Metrics. We use the following standard metrics for comparing the clustering performance: precision (fraction of pairs of entities correctly placed in a cluster together to the total number of pairs placed in cluster together), recall (fraction of pairs of entities correctly placed in cluster together to the total number of pairs in the same ground truth clusters), and accuracy (fraction of pairs of entities correctly placed or placed in cluster to the total number of pairs of entities).
Results. In Table 1, we compare Algorithm (a, 3) BOUNDDDDDDGGEEE to FCI on the clustering results. For Algorithm (a,, BJ-DDENDDDDEEGREE we use sample S of size 1, and observe in Figure 8 (Appendix E), that this corresponds to about 3 interventions per entity. With increase in sample size, we observed that the results were either comparable or better. We observe that our approach leads to considerably better performance in terms of the accuracy metric with an average difference in mean accuracy of about 0.25. This is because FCI recovers partial graphs, and clustering based on the partial information results in poor accuracy. Because of the presence of a dominant MAG with in each cluster, observe that the corresponding entities are always assigned to the same cluster, resulting in high recall for both (a, B) --BBUDDDDDEGEEE and FCI. We observe a higher value of precision for our algorithms, because FCI is unable to correctly classify the MAGs that different from the dominating MAG.
Algorithm (a, --BOUNDEDDEGRES outperforms the GREEDY baseline for the same sample(S) size. For example, on the Earthquake and Survey causal networks, Algorithm (a,, 3) B--BBUDDDDDEEGEE obtains the mean accuracy values of 0.77 and 0.63 respectively, while GREEDY for the same number of interventions obtained an accuracy of only 0.487 and 0.486 respectively. For the remaining networks, the accuracy values of GREEDY are almost comparable to our Algorithm (a, (2,,3)-Bour BJ-NBDDDDDDEGGEE
After clustering, we recover the dominant MAGS using Algorithm (a, RECOOEEY and observe that the additional interventions needed are bounded by the maximum degree of the graphs (see Theorem 3.4). This represented the last column in Table 1. We observe that our collaborative algorithms use fewer interventions for dominant MAG recovery compared to the number of nodes in each graph. E.g., in the Rényi setup, the number of nodes n 10, whereas we use at most interventions per entity. Thus, compared to the worst-case, cutting the number of interventions for each entity by 40%.
Conclusion
We introduce new model for causal discovery capture practical scenarios where multiple entities with different causal structures. Under natural clustering assumption(s), we give efficient provable algorithms for causal learning with atomic interventions and demonstrate its empirical performance. Our model can be extended to the setting where all interventions are non-adaptive, and we plan to study it as part of future work. An interesting future direction would be use interventional equivalence classes of DAGs as part of the model, instead of the clustering assumption. This might require extending the interventional equivalence between DAGS studied in [Hauser and Bühlmann, 2012, Katz et al., 2019] to the setting without the causal sufficiency assumption and exploit that for learning.
10

---

Acknowledgements
The work was partially supported by NSF grants 1934846, 1908849, 1637536 and Adobe Faculty Research grant.
References
Jayadev Acharya, Amab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. Learn- ing and testing causal models with interventions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8469-9489 2018.
Raghavendra Addanki, Shiva Kasiviswanathan, Andrew McGregor, and Cameron Musco. Efficient intervention design for causal discovery with latents. In International Conference on Machine Learning, pages 63-73. PMLR, 2020.
Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Intervention efficient algorithms for approximate learning of causal graphs. In Algorithmic Learning Theory, pages 151-184. PMLR, 2021.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Advances in Neural Information Processing Systems, 2016.
Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability, Information Processing Letters, (1:(1-2):49 2012.
Kevin Bello and Jean Honorio. Computationally and statistically efficient learning of causal bayes nets using path queries. Advances in Neural Information Processing Systems, 31:10931-10941, 2018.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statisties, pages 294-322 2012.
Frederick Eberhardt. Causation and intervention. PhD Thesis, Carnegie Mellon University, 2007.
Kathleen M Gates and Peter CM Molenaar. Group search algorithm recovers effective connectivity maps for individuals in homogeneous and heterogeneous samples. Neurolmage, 63( 63(1):310-11 2012.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference on Machine Learning, pages 1724-1733. PMLR, 2018
AmirEmad Ghassami, Saber Salehkaleybar, and Negar Kiyavash. Interventional experiment design for causal structure learning. arxiv preprint arxiv 1910.05651, 2019.
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. In Advances in Neural Information Processing Systems, pages 14279-14288 14289, 2019.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13(Aug): 2409-2464, 2012.
Huining Hu, Zhentao Li, and Adrian R Vetta. Randomized experimental design for causal graph discovery. In Advances in neural information processing systems, pages 2339-2347, 2014.
Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer, Experiment selection for causal discovery. The Journal of Machine Learning Research, 14(1)3041-3071, 2013.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances Neural Information Processing Systems, 2020.

---

Michael Joffe, Manoj Gambhir, Mare Chadeau- Hyam, and Paolo Vineis. Causal diagrams in systems epidemiology. Emerging themes epidemiology, 9(1):1-18 2012.
Markus Kalisch, Martin Mächler, Diego Colombo, Marloes H Maathuis, and Peter Bühlmann. Causal inference using graphical models with the package pealg. Journal of Statistical Software, 47(11): 1-26, 2012.
Dmitriy Katz, Karthikeyan Shanmugam, Chandler Squires, and Caroline Uhler. Size of interventional markov equivalence classes in random dag models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3234-33-330 3243. PMLR, 2019.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. In Advances in Neural Information Processing Systems, pages 7018-7028, 2017.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. Advances in Neural Information Processing Systems, 2019.
Steffen Lauritzen and David Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, 1988.
Erik Lindgren, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Experimental design for cost-aware learning of causal graphs. In Advances in Neural Information Processing Systems, pages 5279-5289, 2018
Florence Jessie MacWilliams and Neil James Alexander Sloane. The theory of crror-correcting codes, volume 16. Elsevier, 1977.
Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimal conditional independence testing. The Annals of Statistics, 49(4):2151-217,, 2021.
Dang Trinh Nguyen, Quoc Bao Duong, Eric Zamai, and Muhammad Kashif Shahzad. Fault diagnosis for the complex manufacturing system. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 230(2):178-194, 2016.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-66) 688, 1995.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge university press, 2009.
JD Ramsey, Peter Spirtes, and Clark Glymour. On meta-analyses of imaging data and the mixture of records. Neurolmage, 57(2):323-330, 2011.
Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30 (4):962-1030, 2000.
Basil Saeed, Snigdha Panigrahi, and Caroline Uhler. Causal structure discovery from distributions arising from mixtures of dags. In International Conference on Machine Learning, pages 8336-8345.
PMLR, 2020.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In Advances in Neural Information Processing Systems, pages 3195-3203, 2015.
Peter Spirtes, Christopher Meek, and Thomas Richardson. An algorithm for causal inference in the presence of latent variables and selection bias. Computation, causation, and discovery, 21:1-252, 1999.
Peter Spirtes, Clark N Glymour, Richard Scheines, David Heckerman, Christopher Meek, Gregory Cooper, and Thomas Richardson. Causation, prediction, and search. MIT press, 2000.
Prasad Tadepalli and Stuart Russell. Pac learning of causal trees with latent variables. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 9774-9781, 2021.
12

---

Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, pages 222-227. IEEE, 1977.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9(Jul); 1437-1474, 2008a.
Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17):1873-1888)) 2008b.
13


Reviews:
[{"review_id": "osk2jCWvjNP", "reviewer": "Reviewer_8Ccq", "summary": "The main goal of the paper is to perform Collaborative Causal Discovery. The main contributions of the paper are the following\n* Define a new framework for collaborative discovery. The authors consider the case of several entities, each being associated to a DAG containing both observed and latent variables. The idea is to recover the so-called Maximal Ancestral Graph of each entities under a clustering assumption, stating that the MAG are more or less similar inside a cluster, and different when considering different clusters clusters\n* Under this clustering assumption, is provided an algorithm allowing to recover the MAG of each entity with a minimal number of interventions. The algorithm is a two step procedure, performing first a clustering of the entities and thereafter estimating the MAG of each entity\n* Numerical experiments complete the paper\n* In Appendix,  details about MAG are given as well as proofs on the minimality of the numbers of interventions to recover the causal graphs\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "* The problem addressed in this paper is relevant. Two scenarios where collaborative causal discovery can be performed are given that makes sense. I wonder how general this setting is and in particular if it is totally new or if it encompass already studied framework\n* The idea of considering MAG instead of DAG is well justified and is smart. Details are given on MAG in Appendix A. \n* I wonder if the notion of atomic intervention is the same for a MAG than a DAG.  Is there any do calculus in this setting? How in practice can we intervene on a MAG? Can you give any references? The reference given for MAG is a relevant one and explains quite well why MAG are interesting but details about interventions in this setting could help\n* Numerical experiments are performed on classical benchmark with no more than a dozen of nodes. How could be extended the approach when we have more variables? How can we decide of the number of latent variables when dealing with practical data\n* You only compare with FCI. I understand that you want to compare with algorithm dealing only with observational data but you mention also  other algorithm trying to minimize the number of interventions. Even if your setting is different, on the examples studied in Section 5, could some comparison be done?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Everything is OK from this point of view", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mpkkUQSGLb7", "reviewer": "Reviewer_8cR4", "summary": "The paper introduces an algorithm for learning causal graphs for multiple entities which share some underlying similarities with minimum atomic interventions. The goal is different from the well-studied problem of learning a causal graph from multiple environments in which the data distribution could differ and the aim is to recover a single global graph.\n\nThe problem is of learning independent causal graphs is posed from the perspective of finding clusters among the entities where entities in a cluster are closer in some distance metric in comparison to entities in other clusters. This property is termed as $(\\alpha,\\beta)$ clustering. The task is to minimize the number of interventions needed to recover the causal graphs while distributing the interventions across the clusters to minimize the total intervention cost. A lower bound of $\\Omega(\\frac{1}{\\alpha})$ interventions is shown to be necessary for recovering the clusters as well as the minimum number of atomic interventions needed.\n\nExperiments are performed on multiple datasets with a comparison to the standard FCI algorithm. Results indicate an overall improvement in the metrics for recovering the true causal graph.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The work is original with respect to introducing clustering as an approach to recovering the similarities in causal graphs across multiple entities. Although not directly related, the task of recovering causal graphs from multiple environments has some similarities with respect to recovering the commonalities across environments. It would be helpful to situate this work in the multi-environment premise and draw out the differences between the two paradigms. \n\nThe submission is technically sound and the claims are supported by theoretical and empirical analysis. Although it would be helpful to discuss the specific weaknesses of this work such as the relation with the dimensionality of the nodes, up to what extent does the method succeed when different entities have very few similarities, does it make sense to recover causal graphs for certain entities more accurately than others. For example, in settings such as healthcare where obtaining data from multiple entities (say hospitals) is difficult and hence it may not be possible to recover the causal graphs for different hospitals it would be useful to recover at least one causal graph more accurately to guide clinical decision-making. Similarly, it may not always be possible to collect data about all the nodes in all the entities, in such a case recovering partial causal graphs across entities to potentially recover a global graph is also an interesting direction.\n\nThe paper is well-organized. It is generally clear to read.\n\nThe approach can definitely guide further development in the field of causal discovery and opens up several interesting directions. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is little direct societal impact and accordingly no extensive discussion about it.\n\nOne consideration that can affect the direct application of this in real-world settings would be the high dimensional attributes that can result in dense and complex graphs.\nHow can the approach be applied in cases where the number of edges in the graph is magnitudes higher than the number of nodes? In such settings, identifying clusters can be computationally challenging.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "hFeAajfSDTn", "reviewer": "Reviewer_H6LC", "summary": "This paper proposes a method for causal discovery by aggregating data from different data sources into clusters. Those clusters are similar with respect to the underlying graphical structure that generates the data. Based on these clusters, the authors an efficient algorithm in terms of number of interventions required to estimate the underlying graph.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I enjoyed reading this technical paper that has also a convincing experimental evaluation. I am not familiar with the field so my comments here are based on my limited understanding of the different presented notions. The paper is well-written, although I would find more useful a better and more thorough literature review to understand how this paper relates to other works in the field. The article is well written, although quite dense in notation which requires going back and forth between the main text and the appendix.\n\nI have a couple of questions:\n\nFirst, the input to the $(\\alpha, \\beta)$-BoundedDegree algorithm contains the PAGs given by FCI. The results in Lemma 3.3 and Thm 3.4 are statements with high probability but with respect to the distribution introduced by the algorithm. What happens if the initial PAGs are incorrectly estimated?\n\nMore generally, I am surprised that there is no analysis of the initial graph estimation procedure that is based on conditional independence tests. Isn't the large number of simultaneous tests an issue? Your clustering algorithm is built on objects that are estimated and not ground truth or actual data samples, don't you take into account that uncertainty at all?\n\nThe $(\\alpha, \\beta)$-Recovery algorithm gives as output the dominant MAG for each entity, which Thm3.4 shows is close enough with high-probability to the true MAG. Does that imply that, even with an infinite number of atomic interventions, it is impossible to separate two MAGs from the same initial cluster?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "f5RJh-csItz", "reviewer": "Reviewer_Ec77", "summary": "The paper proposes an approach to learn multiple causal graphs, in the presence of latents, collaboratively and simultaneously by means of clustering and by performing atomic interventions.\nFirst, the work proposes the property $(\\alpha,\\beta)$-clustering where graphs in different clusters are \"different\" by a factor of $\\alpha$ at least, while graphs within the same cluster are \"different\" by a factor of $\\beta$ at most. Using this property, an approximate algorithm is proposed to (1) learn the clusters such that the $(\\alpha,\\beta)$-clustering property is satisfied, and (2) learn one dominant graph in each cluster assuming the clusters are more homogeneous.\nNext, a special case of the clustering property is considered where all the graphs within the same cluster are identical, i.e. $\\beta=0$, and a learning algorithm is proposed with a lower bound on the number of interventions required to learn the graphs than the general case.\nFinally, the proposed algorithms are evaluated using data generated from synthetic and real causal graphs.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "**Originality:**\nThe central idea of the paper on collaborative causal discovery using atomic interventions is somewhat original, some of the techniques such as learning a node's neighbours (Algorithms 1 & 2) are based on well-known techniques, and the related work is adequately cited.\n\n**Quality:**\nMy evaluation is based on the main body of the paper only and not the supplementary material. That being said, the work seems to be technically sound. However, a couple of issues are noted below:\n\n+ Using MAGs: Modeling the causal graphs using MAGs is a major weakness of the work when considering interventions. MAGs are attractive under Markov equivalence [27,28] and under soft interventions [10,14] because the true causal diagram (DAG with latents or ADMG) is not differentiable from its equivalent MAG. This is not true under hard interventions as considered in this work.\nFor instance, consider the causal graph $G=\\\\{ A\\rightarrow B\\rightarrow C, B\\leftarrow L \\rightarrow C \\\\}$ and the corresponding MAG $M=\\\\{ A\\rightarrow B\\rightarrow C, A\\rightarrow C \\\\}$. Both graphs are Markov equivalent, yet they are differentiable under $do(B)$.\nThe challenge discussed in lines 131-133 is a limitation in atomic interventions rather than a justification for adopting MAGs.\n\n+ $(\\alpha,\\beta)$-clustering: The parameters $\\alpha,\\beta$ are given to Algorithm 3 as input and it is probably not possible to obtain a valid clustering of the graphs for any pair of parameters. If so, then finding the right/convenient parameters for clustering is a search task by itself. This issue is reflected by the antecedent of Lemma 3.3. I appreciate your thoughts on this.\n\n+ Proposition 3.2: This lower bound is computed assuming that the PAG does not exist and we are learning the MAG purely from a sequence of atomic interventions. However, the algorithm \"RECOVERG\" clearly utilizes the PAG through Algorithms 1 & 2. I would assume that the bound could be improved in the presence of observational data represented by the PAG.\n\n**Clarity:**\nThe problem is well motivated in the introduction with real-world examples. Furthermore, the problem statement is clearly formulated and illustrated in Section 2. The rest of the paper could benefit from some examples to illustrate the algorithms and the key ideas, especially in Section 4 which feels somewhat dull (namely, \"Overview of Algorithm $\\alpha$-GENERAL\"). Also, the merging step in \"Overview of Algorithm $(\\alpha,\\beta)$-RECOVERY\" is ambiguous and further elaboration could be helpful.\n\n+ Minor typos:\n\nLine 399, \"scenarios where are multiple\" --> where *there* are multiple.\n\nLine 170, \"With right setting of\" --> with *a/the* right setting\n\n**Significance:**\nThe task of causal discovery is important to various fields and the proposed idea of collaborative learning through clustering and efficient interventions can be relevant to a wide audience. However, the work is limited by the issues raised in the \"Quality\" section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the limitations and potential negative societal impact of their work adequately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are favorable after author responses and discussion.

The paper considers collaboratively learning different MAGs which have a clustering property. Authors show an efficient way to learn all the MAGs, with the smallest number of atomic interventions per entity. It scales in the degree of the MAG and logarithmic in the number of MAGs.

The collaborative setting is novel, the interventional complexity under the clustering assumption is very interesting. This significantly expands the score of learning through intervention of related causal models that could be related but different (apart from being just intervened versions of each other).

Note: Reviewer 8Ccq indicated that she/he would raise the score to 7 but did not follow through after the discussion period. 
Decision: Accept (Poster)