Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm
causality;causal inference;causal discovery;interventional data;single-variable interventions;causal structure learning
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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?
* 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.
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.
* 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.
Yes
No ethics review needed.
Are there useful heuristics for choosing which variables to intervene on ($\mathcal{I}$)?
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.
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.
* 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$.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
- 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?
- 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
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.
- 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
@inproceedings{
anonymous2024deriving,
title={Deriving Causal Order from Single-Variable Interventions: Guarantees \& Algorithm},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=u63OVngeSp},
note={under review}
}
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 the notion 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
causality causal inference causal discovery interventional data single-variable interventions causal structure learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/3094d240ce44849d1f62548e7a3aa6bcd1209b6f.pdf
causal reasoning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/7512f23f64ee59167a2384cb25b26a9bcb297292.zip
Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission