Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

I have a couple of questions:

First, 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?

More 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?

The $(\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?
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The main goal of the paper is to perform Collaborative Causal Discovery. The main contributions of the paper are the following
* 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
* 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
* Numerical experiments complete the paper
* In Appendix,  details about MAG are given as well as proofs on the minimality of the numbers of interventions to recover the causal graphs

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
* The idea of considering MAG instead of DAG is well justified and is smart. Details are given on MAG in Appendix A. 
* 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
* 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
* 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?
limitations_and_societal_impact: Everything is OK from this point of view
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
First, 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.
Next, 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.
Finally, the proposed algorithms are evaluated using data generated from synthetic and real causal graphs.
main_review: **Originality:**
The 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.

**Quality:**
My 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:

+ 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.
For 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)$.
The challenge discussed in lines 131-133 is a limitation in atomic interventions rather than a justification for adopting MAGs.

+ $(\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.

+ 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.

**Clarity:**
The 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.

+ Minor typos:

Line 399, "scenarios where are multiple" --> where *there* are multiple.

Line 170, "With right setting of" --> with *a/the* right setting

**Significance:**
The 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.
limitations_and_societal_impact: The authors address the limitations and potential negative societal impact of their work adequately.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

The 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.

Experiments 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.
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. 

The 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.

The paper is well-organized. It is generally clear to read.

The approach can definitely guide further development in the field of causal discovery and opens up several interesting directions. 

limitations_and_societal_impact: There is little direct societal impact and accordingly no extensive discussion about it.

One 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.
How 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_title: null

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)