Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm

Authors: Mathieu Chevalley, Patrick Schwab, Arash Mehrjou
Primary area: causal reasoning
Keywords: causality, causal inference, causal discovery, interventional data, single-variable interventions, causal structure learning

Abstract:
Targeted and uniform interventions to a system are crucial for unveiling causal relationships. While several methods have been developed to leverage interventional data for causal structure learning, their practical application in real-world scenarios often remains challenging. Recent benchmark studies have highlighted these difficulties, even when large numbers of single-variable intervention samples are available. In this work, we demonstrate, both theoretically and empirically, that such datasets contain a wealth of causal information that can be effectively extracted under realistic assumptions about the data distribution. More specifically, we introduce a novel variant of interventional faithfulness, which relies on comparisons between the marginal distributions of each variable across observational and interventional settings, and we introduce a score on causal orders. Under this assumption, we are able to prove strong theoretical guarantees on the optimum of our score that also hold for large-scale settings. To empirically verify our theory, we introduce Intersort, an algorithm designed to infer the causal order from datasets containing large numbers of single-variable interventions by approximately optimizing our score. Intersort outperforms baselines (GIES, DCDI, PC and EASE) on almost all simulated data settings replicating common benchmarks in the field. Our proposed novel approach to modeling interventional datasets thus offers a promising avenue for advancing causal inference, highlighting significant potential for further enhancements under realistic assumptions.

Decision: accept (poster)
Reviewer scores: 5, 8, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1729085630027

thread_type:
official_review

<thread_object>
creator: reviewer_mrvm

<content>
summary:
The paper proposes a new method to infer the causal order of an (unknown) causal graph from interventional data. For this purpose, the authors introduce a new assumption (interventional faithfulness), a theoretically grounded score on causal orders, and a practical algorithm called intersort approximating the proposed score. Intersort is evaluated on simulated data.

strengths:
- The proposed method is the first to estimate the causal order from interventional data
- The paper contains several novel and theoretically grounded contributions, including the causal score as well as the algorithm to approximate it
- Promising empirical results on simulated data

weaknesses:
- As common in causal discovery, the method relies on generally untestable assumptions (e.g., epsilon interventional faithfulness)
- The method relies on estimating distributional distances (e.g., Wasserstein distance) which can be statistically challenging
- No experiments using real-world data are provided. I understand that benchmarking methods are challenging due to unknown causal ground truth, however, I think it would be nice to sketch an application of the method on real-world data and potentially obtain insights
- The related work on causal discovery could be expanded

Minor 
- Appendix B seems to be missing
- There is some weird formatting on page 16 (Appendix C and D intersect)
- There is no text in Appendix F.1/ F.2 so it is hard to understand which figures belong to which section. Also, Appendix G intersects with F2

questions:
- What would be an application in which one would only be interested in inferring the causal order and not the full graph/Markov equivalence class?
- How exactly is the algorithm implemented? E.g., which p-Wasserstein distance is chosen? Which algorithm is used to compute the distance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730101501658

thread_type:
official_review

<thread_object>
creator: reviewer_nps4

<content>
summary:
This paper proposed INTERSORT, an algorithm for causal discovery with interventional data, to find a casual relationship with distribution change after intervention. Theoretically, the upper bound of the error is provided for the optimal causal order. Experimental results on simulated and real-world datasets verify the effectiveness of the proposed method.

strengths:
The score of causal order is designed to identify causal relationships with the help of distribution change engendered by intervention. Theoretically, the upper bound of the expected error is provided for the optimal causal order.

weaknesses:
1. If setting the threshold following the Remark in Line 203, then it means every pair with distribution change after perturbation will be considered. Why not directly set it to 0, which means detecting distribution change directly?
2. The selection processes also have a large distance, however, this is not a causal relationship. Moreover, selection is common in gene regulatory networks. In your method, how to guarantee the ones you find are causal relations?
3. In eq. (1), what does the second part mean? I scratch my head to understand it. Could you provide descriptions of the symbols used in the equation?
4. In Algorithm 1, how many kinds of permutations will be considered. Usually, it will be non-traversable with an increase in the number of variables.
5. In the part of Distribution with intervention, ' the structural assignment is replaced by a new random variable independent of the parents' means the hard intervention right? Moreover, the author also mentioned that distribution after intervention can be accessed, do you have assumptions about the distribution of intervention? and why you need the distribution needs to be accessed.

questions:
1. If setting the threshold following the Remark in Line 203, then it means every pair with distribution change after perturbation will be considered. Why not directly set it to 0, which means detecting distribution change directly?
2. The selection processes also have a large distance, however, this is not a causal relationship. Moreover, selection is common in gene regulatory networks. In your method, how to guarantee the ones you find are causal relations?
3. In eq. (1), what does the second part mean? I scratch my head to understand it.
4. In Algorithm 1, how many kinds of permutations will be considered. Usually, it will be non-traversable with an increase in the number of variables.
5. In the part of Distribution with intervention, ' the structural assignment is replaced by a new random variable independent of the parents' means the hard intervention right? Moreover, the author also mentioned that distribution after intervention can be accessed, do you have assumptions about the distribution of intervention? and why you need the distribution needs to be accessed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730400729388

thread_type:
official_review

<thread_object>
creator: reviewer_pzap

<content>
summary:
Learning the topological ordering of the causal graph behind a set of variables is useful in a variety of scientific domains. For instance, when gene expressions are correlated, the causal order can help discern the structure of the regulatory network. This paper proposes a novel approach for ordering variables using many single-variable interventions. Strong theoretical guarantees and diverse empirical evaluations are presented.

strengths:
This paper presents an original solution to a significant problem: a method for directly learning the causal order using interventional data.
 * Although technically dense, the paper is surprisingly easy to read and well-organized.
 * The theoretical guarantees for optimality under a reasonable faithfulness assumption appear solid.
 * The approximation algorithm is computationally tractable and validated with a variety of benchmarks.

weaknesses:
* The majority of the analysis assumes access to oracle statistical distances between interventional distributions. Little attention is paid to the estimation of these distances using samples, and how they affect the sorting algorithm. 
 * The main score objective (Equation 1) is difficult to understand and not explained much.

Minor comments
 * Please define all the terms on like 152, like the noise variable $N_j$.

questions:
Are there useful heuristics for choosing which variables to intervene on ($\mathcal{I}$)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730453029498

thread_type:
official_review

<thread_object>
creator: reviewer_wsad

<content>
summary:
The paper introduces the concept of "interventional faithfulness," which relies on comparisons between the marginal distributions of each causal variable across observational and interventional settings, and also develops a scoring function for ranking causal orders of variables. Based on this concept, the authors 1) provide strong theoretical guarantees on the optimum of the proposed score and 2) propose INTERSORT to infer causal order from datasets containing large amounts of single-variable interventions. INTERSORT outperforms existing methods in various simulations, demonstrating the potential of the new theory for advancing causal inference in domains like biology.

strengths:
* The paper introduces a new definition of faithfulness with both theoretical guarantees and empirical results.
* It is well-written and clear.
* Numerical experiments are designed in a sensible manner that adequately supports the claims.
* This is an important and highly relevant contribution to the community, with developed theory that has the potential to further advance causality.

weaknesses:
* It’s unclear how the findings would generalize to different settings, such as different distributions over random interventional variables, or in the case of having discrete causal variables.
* Empirical experiments are conducted on a limited set of underlying models.

questions:
1. Are there scenarios where the proposed method cannot be applied? In other words, are there real-world systems that do not satisfy e-interventional faithfulness or its relaxations?
2. How could INTERSORT be extended to handle a large number of nodes? I presume for calculating distance, one could replace Wasserstein with e.g. MMD, but what would be the main bottleneck of the algorithm aside from the distance metric?
3. Could the authors elaborate on how the proposed framework could be extended to derive causal order over a subset of variables?
4. Do the authors have any intuition on how this framework might be used to develop better causal discovery algorithms?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730480245563

thread_type:
official_review

<thread_object>
creator: reviewer_r6ey

<content>
summary:
The authors considered the problem of recovering a causal order in structural causal models (SCM) under the causal sufficiency assumption (it seems that is the case but it is not clearly mentioned in the paper). They assumed that they have access to observational data and some single-variable interventional ones and used the changes observed in the marginal distributions of variables to recover a causal order. The authors introduced a notion of faithfulness (interventional faithfulness) and showed that a causal order can be recovered by maximizing a score (defined in (1)) if we have single-variable interventions on all the variables in the system. They proposed a heuristic algorithm (called INTERSORT) aiming to improve the score. The experimental results showed that in some specific settings, the proposed algorithm has a better performance compared to some of the previous work.

strengths:
Originality/Quality: The authors asserted at the end of the Related Work section that they are proposing the first algorithm to infer the causal order from the interventional data. I do not think this is true. First, (Tian and Pearl, 2013) is one of the earliest works using the changes in marginal distributions due to intervention in inferring some orders among the variables in the system (See Section 4 there). Second, there are extensive works on recovering an equivalence class of models from the observational and interventional data (whether the intervention locations are known or not). A few works are cited in the paper (such as GIES and DCDI). These works can also provide some information about the causal orders that are encoded in the recovered equivalence class. 

Clarity: The paper is generally well-written.

Significant: Based on what was mentioned, I think that the authors should carefully compare their methods with previous work (such as (Tian and Pearl, 2013) when $\epsilon=0$). Moreover, from the experimental results, it is not clear that the proposed algorithm indeed improves SOTA.

weaknesses:
Comparison with previous work: I think there is no clear comparison with previous work (especially with (Tian and Pearl, 2013)) and discussion about the advantages of the current approach. 

Theoretical result in a very limited setting: I think the assumption of having single-variable intervention on all the variables is very restrictive (what can we say in theory about the recovered causal order if a portion of variables are intervened on?). Moreover, the proposed algorithm is designed under the causal sufficiency assumption (which as far as I checked, is not clearly mentioned in the paper). 

The notion of interventional faithfulness: I think this assumption is an extension of "influentially" in (Tian and Pearl, 2013). The connection to that definition is not discussed in the paper.

Theoretical guarantee about INTERSORT: Although the authors used the term "approximation algorithm" in line 359, there is no theoretical guarantee about the quality of the output of INTERSORT.

questions:
1. What are the main differences between the current work and (Tian and Pearl, 2013) in terms of faithfulness assumption and methodology?

2. In lines 65-68, the authors are giving the advantage of knowing the order. Did they mean that the number of candidates is divided by 4 if we know that the target gene is in the middle of the causal order?

3. In eq. (1), in the second term, why is there a coefficient of $d$?

4. In Lemma 4, based on the chosen $p_e$, it seems that the graph is disconnected with high probability. Can the authors elaborate more on this?

5. In line 283, the authors argued that the expected error is growing with the order $O(d)$ and they mentioned that it is a strong guarantee. I think the upper bound on the expected error is $d^2$. Therefore, I am not sure this is indeed a strong result.

6. The pseudocode in Algorithm 1 is somehow useless. The most important parts (SORTRANKING and LOCACLSEARCH) are not described there.

7. Evaluating empirically does not imply the quality of the output of the algorithm in theory. I suggest removing the term "approximation algorithm" in line 359.

8. What is the computational complexity of the proposed algorithm? It is also good to compare the algorithms in terms of runtime empirically.

9. In Fig. 2, in some settings (such as NN 30 variables or GRN with a fraction of 23.33%), other methods have better performance. I think it is good to elaborate more on these cases in the experiment section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732367249143

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Authors General Response to reviews

comment:
We would like to express our gratitude to all reviewers for their thorough and constructive feedback on our manuscript. We are pleased that the reviewers recognized the novelty and theoretical contributions of our proposed method, INTERSORT, for inferring causal order from interventional data. The positive comments related to the soundness, presentation, and contribution of our work are greatly appreciated and affirm our effort to provide a well-founded and impactful addition to the field of causal inference.

## Highlights of Positive Feedback:
- **Originality and Contribution**: Many reviewers noted the originality of our approach in using interventional data to estimate causal order, highlighting the significance of our contributions to causal discovery (“important and highly relevant contribution” Reviewer WsAd, “several novel and theoretically grounded contributions” Reviewer mrVM).
- **Theoretical Foundation**: The theoretical underpinnings, including the development of the causal order score and the assumptions like ϵ-interventional faithfulness, as well as the theoretical guarantees even for subset of interventions, were acknowledged as sound and novel. (“ Strong theoretical guarantees and diverse empirical evaluations are presented” Reviewer PzaP)
- **Empirical Validation**: Reviewers appreciated the promising empirical results on simulated datasets, which support the effectiveness of our method compared to established baselines. (“Promising empirical results on simulated data” Reviewer mrVM, “ INTERSORT outperforms existing methods in various simulations” Reviewer WsAd)

## Summary of Main Concerns:
- **Intuition for the Score**: Most reviewers (Reviewer R6EY, Reviewer PzaP, Reviewer nPs4) requested clearer explanations of the scoring method we proposed. We have revised the manuscript to provide more intuitive explanations for Equation 1, detailing the rationale and impact of each component in the score to enhance its clarity and accessibility.
- **Section on Causal Confounders**: In response to feedback on clarifying the method’s applicability in the presence of latent confounders (Reviewer R6EY, Reviewer WsAd, Reviewer nPs4), we have added a new section discussing how our approach can be applied in these scenarios, leveraging Acyclic Directed Mixed Graphs (ADMGs) (Verma 1991, Richardson 2003) to model confounded causal relationships.
- **Comparison to related work**: To better position our contribution within the existing literature, we have expanded our discussion to include a more explicit comparison with the existing work, e.g. Tian and Pearl 2013. This comparison highlights how our score-based method differs from their rule-based algorithm and underscores the advancements and scalability offered by our approach.
- **Application on real-world data**: As suggest by Reviewer mrVM, we added a qualitative example of the output of Intersort on the real-world data of Sachs 2005, in Appendix F3, Figure 10.

All the revision to the text are colored blue in the revised manuscript. We sincerely appreciate the reviewers' valuable insights, which have significantly enhanced the quality and clarity of our manuscript. Thank you for your role in helping us refine our work.

References:

Jin Tian and Judea Pearl. Causal discovery from changes. arXiv preprint arXiv:1301.2312, 2013.

T. S. Verma. Invariant properties of causal models. Technical Report R-134, UCLA Cognitive Systems Laboratory, 1991.

Thomas Richardson. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 30(1):145–157, 2003.

Karen Sachs, Omar Perez, Dana Pe’er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721): 523–529, 2005
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces an approach for learning the order of a causal DAG model from single variable interventions. Reviewers found it useful, and I'm generally favourable to accept based on the framing of the algorithms being novel and for providing results others may want to build upon. But I believe scholarship could be improved, and the claims of originality better contextualized: for avoidance of doubt, the paper is not the first to address causal ordering learning from interventional data, a problem which broadly speaking is not hard under some typical assumptions. Some of my points below are mentioned by reviewer R6EY, and I'm disappointed that they are not addressed by the authors.

* I'm somewhat confused why the authors mention Tian and Pearl repeatedly as a key citation for their contribution. First, please correct the reference: Tian and Pearl's is a 2001 (!) paper from UAI. I see limited connections between the motivation of that paper and the presented paper. Tian and Pearl's main point was how to make use of natural experiments, while my interpretation is that the present contribution is motivated by experimental design. If the authors want to refer to a historical paper on using interventional data, it would make far more sense to refer to Cooper and Yoo's "Causal discovery from a mixture of experimental and observational data" (UAI, 1999). Tian and Pearl explain very clearly the connection between their paper and (last century's) literature on causal discovery from interventional data, please refer to them for details.

* As correctly mentioned in the paper, the notion of learning from pairwise orderings appears in LiNGAM-like algorithms, including DirectLiNGAM (Shimizu et al., 2011). Readers would benefit from an explicit discussion between methods at the more abstract level of being told pairwise directions, regardless of the source of data (observational vs experimental) and parametric family (linear or not). But claims such as "Reisach et al. (2021) that the causal order can be recovered by sorting the variable by variance in simulated datasets" are strangely phrased: causal order can *not* be recovered by variance in simulated datasets in general (!), only those which are either badly designed or, for some hopefully well-justified reason that is nothing but a very special case, follow a physical process where variance increases with depth of causal connection (e.g., some classes of additive error models with constant error term variance).

* Like reviewer R6EY, I'm surprised that papers like Eberhardt, Glymour and Scheines "On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables" (UAI, 2005) and the older "N-1 Experiments Suffice to Determine the Causal Relations Among N Variables" (published as a tech report in 2004) are not cited. Please do so, and explain the connections. Those papers solve a closely related (and to some extent, harder) problem than the one posed in this paper, using more classical faithfulness. In fact, a paper such as Saengkyongam and Silva "Learning Joint Nonlinear Effects from Single-variable Interventions in the Presence of Hidden Confounders" (UAI, 2020) jumps straight into the problem of causal effect identification with a given structure because it recognizes that ordering can be readily learned from the same data using methods such as simpler versions of Eberhardt et al. (as only ordering is necessary, instead of a full causal graph).

* broadly speaking, "interventional faithfulness" is not a novel concept as mentioned in the abstract, as numerous variants of it appear in papers where discovery with a mixture of interventional datasets take place, including some cited (any method which claims correctness of causal discovery with interventional data needs some notion of interventional faithfulness). The $\epsilon$ variant given here is novel to the best of my understanding, but it is worthwhile pointing to the reader that there are several $epsilon$-like variants of faithfulness, for instance the one found in Zhang and Spirtes "Strong Faithfulness and Uniform Consistency in Causal Inference" (UAI, 2003). The notion introduced in the paper is novel and worth discussing as far as I know, but it should be noticed that much work has been done in relaxing faithfulness assumptions (for instance, from the citations of Zhang and Spirtes). Tian and Pearl's influentially is a type of marginal faithfulness and has no extra degree of freedom.

If this paper is to be published at ICLR, I hope all of the above is addressed in the final version -- which I think it's doable and I'll assume good faith from the authors.