Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm
Authors: Mathieu Chevalley
Patrick Schwab
Arash Mehrjou
Venue: ICLR 2025 Poster (2025)
Keywords: causality
causal inference
causal discovery
interventional data
single-variable interventions
causal structure learning
Primary area: causal reasoning

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.

Published as a conference paper at ICLR 2025
DERIVING CAUSAL ORDER FROM SINGLE- VARIABLE INTERVENTIONS: GUARANTEES & ALGORITHM
Mathieu Chevalley!.21
Patrick Schwab
Arash Mchrjou" 1.31
.ii.ai 2ETH Zürich
3 MPI for Intelligent Systems
ABSTRACT
Targeted and uniform interventions to a system are crucial for unveiling causal re- lationships. While several methods have been developed leverage interventional data for causal structure learning, their practical application in real-world scenar- ios often remains challenging. Recent benchmark studies have highlighted these difficulties, even when large numbers of single-variabl variable intervention samples are available. In this work, we demonstrate, both theoretically and empirically, that such datasets contain wealth of causal information that can be effectively ex- tracted under realistic assumptions about the data distribution. More specifically, we introduce novel variant of interventional faithfulness. which relies com- parisons between the marginal distributions cach variable across observational and interventional settings, and introduce score causal orders. Under this assumption, we are able to prove strong theoretical guarantees on the opti- mum 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, highlight- ing significant potential for further enhancements under realistic assumptions.
INTRODUCTION
Causal structure learning is pivotal for understanding complex systems, aiming to discover causal relationships from data. This field spans disciplines such as biology (Meinshausen al., 2016 Yu et al. 2004). medicine (Farmer et al.) 2018 Joffe et al.] [2012 Feuerriegel et al. [2024). and social sciences [Baum-Snow & Ferreiral 2015); Imbens & Rubin (2015), where causal insights drive informed decision-making and deepen understanding of underlying processes. Tradi- tionally, causal discovery has relied heavily on observational data, primarily because expansive interventional experiments are often impractical or costly in many application domains. The inherent limitations of observational data necessitate assumptions about data distribution to ensure identifiability beyond the Markov equivalence class (Spirtes al., (2000, [Shimizu et al.) (006)] Hoyer et al. 22088.. However, the emergence of large-scale interventional data, especially in single-cell transcriptomics data (Replogle et al.) [2022) Datlinger al.) 2017 2016), introduces both new opportunities and challenges.
2021 Dixit et al.
Interventional data, characterized by targeted alterations to a system, offers a unique perspective for causal discovery. These controlled interventions reveal causal mechanisms often obscured in observational studies. As such, many causal discovery methods using interventional data have been proposed (Brouillard et al. 20200 Lorch et al., 2022 Lopez et al. 2022 Hauser & Bühlmann, 2012]. However, their practicality remains challenging. For example, recent benchmarks the gene network domain (Chevalley al. 2023 2022) demonstrate that simpler models based on straight- forward statistical comparisons between observational and interventional distribution outperforms established causal discovery methods, particularly when many single-variable interventions
Correspondence to m. 1eteval1ey97@gaa .com, arash@di stantvantagepo com

---

Published as a conference paper at ICLR 2025
available. The motivation for this research thus stemmed from these recent advances in applying causal discovery techniques to gene network inference. Our methodology, including the use of the Wasserstein distance, aligns with evaluation metries for predicted graphs established in the benchmark by Chevalley et al. (2022). Additionally, a component of our algorithm builds upon and formalizes approaches from leading models in gene network inference, such those highlighted
in the CausalBench challenge (Kowiel et al.) [2023 Nazaret & Hong. 2023 Deng & Guan] [023] Chevalley et al. 2023). This work not only addresses critical domain of application but also
enhances the theoretical framework surrounding contemporary advancements in the field (Yu et al.,
2004 Chai et al. 2014 Akers & Murali [021]
Hu et al. (020).
Here, we study further the potential of single-variable interventional data for causal structure discovery, which we reduce to finding the causal order (topological order) of the variables. Even though the causal order represents a superset of the true causal relationships, it is useful per se. Intuitively and informally, correlations are more likely to be causations if they follow the causal order. More practically, it can for example be used to guide experimental design, as it greatly reduces the hypothesis space. As a specific example, in biology, a task of interest is to select pairs of genes to intervene on, which is space much larger than single gene interventions. For target gene that let us assume lies in the middle of the causal order, the number of candidate double interventions goes from (2) down to (3). where d is the number of variables.
To find the causal order, we introduce a data-based score to rank candidate causal orders, and we establish theoretical guarantees its optimum, providing upper-bounde spper-bounds on the expected error de- pending on the graph density and on the probability for a variable to be intervened on, that also hold for large scale settings. Crucially, our approach makes light assumptions on the data distributions, requiring only what we call c-interventional faithuuun faithfulness, which characterizes the strength of changes in marginal distributions between observational and interventional distributions. We then introduce a novel algorithm called INTERSORT that leverages this assumption to derive the causal order.
Our empirical evaluations on diverse simulated datasets (linear, random Fourier features (oorch et al. 2022), neural network (Nazaret et al., 2023; Brouillard et al., 2020) and single cell (Dibaeinia & Sinhal 2020) with various noise distributions), which are close replications of real-world systems and follow common practice in the field, confirm our theoretical results. The efficacy of our approach accurately determining the causal order from interventional data signifies a notable advancement in causal inference. INTERSORT outperforms the four baselines, namely PC (Spirtes et al., 2000), GIES (Hauser & Bühlmann 2012), DCDI (Brouillard et al. 2020) and EASE (Gnecco et al. (02T) almost all settings. It is also robust to data normalization (Reisach ct al. 2021). which IS failure mode of many recently proposed continuous optimization causal discovery methods. Moreover, our empirical results show that Intersort makes more efficient use of interventional information compared to existing approaches which is a critical advantage especially in domains where interventions costly and sometimes impossible to perform. This suggests that the task of identifying causal structures with many single-variable interventions may be more feasible than previously believed. Moreover, our method demonstrates similar performance and robustness across different types of simulated data, emphasizing its reliability and versatility.
Our method relies on c-interventional faithfulnees which is a lighter version of many of the existing assumptions in causal discovery literature, while still providing theoretical guarantees. Realistic assumptions on the data distributions are crucial, as many application domains such as gene expression data, the validity of common assumptions in the field may be unverifiable or known to not hold. Furthermore, many methods catastrophically fail when their assumptions do not hold, rendering them inapplicable (Montagna et al. 2023a Heinze- Deml et al. 2018).
RELATED WORK
Causal ordering Even though the causal order does not contain the full causal information as does not uniquely identify the causal graph, it can subsequently be used with for example penalized regression techniques to recover the edges (Bühlmann et al. 2014, Shimizu et al. 201 l). Also, the correct causal order is useful in itself as fully connected graph can be constructed from it which describes the interventional distributions (Peters & Bühlmann, 2015 Bühlmann et al., 2014). More recently, following the discovery of Reisach et al. (2021) that identified an artifact in simulated datasets where sorting variables by variance appears to recover the causal order under certain con- ditions, many algorithms to recover the causal order from observational data have been proposed,
2

---

Published as a conference paper at ICLR 2025
for example via score matching (Rolland et al. 2022 Montagna al. 2023a b). To our knowledge,
another work aiming to infer the causal order from interventions comes from Tian & Pearl (2001), which builds seminal works such as Cooper & You (1999); (Spiress et al. (2000). [Tan & Pearl (200T) focus on causal discovery from passive interventions, where shifts in distributions arise natu- rally. Our work brings two major contributions: first, propose score-based approach, in contrast to the rule-based algorithm of TTan & Pearl (2001), which opens the door for large class of opti- mization tools and offers better scalability, and second, we provide extended theoretical results in terms of upper- boupding the expected error of our algorithm, especially in cases where only a subset of the variables intervened on whereas (Tian Pearl (200T) argues mainly about the recovery of the true causal order when "all"" variables are intervened. Adjacently, methods like DirectLiNGAM (Shimizu et al. 2011 infer causal orderings from observational data under -on-Gaassiantty assump- tions. As such, they score orderings based on fitted parameters, making it sensitive to distributional assumptions. By leveraging interventional data, our approach relaxes distributional assumptions and provides more robust framework for causal ordering. Eberhardt et al. (2005 2006) explored the theoretical bounds on the number of experiments required for full causal structure identification. Our work complements these findings by focusing on deriving causal orderings from single-vane variiale interventions under light assumptions, which can be more practical in large-scale applications.
3 CAUSAL ORDER: DEFINITIONS
We here introduce our framework for causality following Pearl (2009) and we follow the notations of |Peters et al.) (017)) We also present the definition of a causal order as well as a divergence to measure how faithfully a causal order recalls the causal information.
Statistical metric Let (M, d) be metric space, and let P(M) be the set of probability measures over M. We define D ((MM)P(MM) + [0, oo) as a distance between probability measures on M.
Distribution We consider set of random variables X = (X1...., Xa) indexed by V (), with associated joint distribution Px. We denote the marginal distribution of each random variable as Px,, E.
Causal Graph We write G= = (V, F)) DAG between variables VV, E. C V such that (v, v) g E for all V. We write A9 the d adjacency matrix, where A (1, = = (i.j) E E. We note Pa, the parents of j. where
a parent (i.j) E E. We note DE; the descendants of in graph g. j is a descendant of if there is a directed path from i to j. We note AN the ancestors of i in graph G. is ancestor of if there is directed path from j to
Causal Order
Given causal graph 9, we call permutation of the variables:
л {1, .1.... ......... d} - {1,..., d). causal ordering of the variables in G if it satisfies T(i) T()) if E DE Peters et al. 2017). A permutation is bijective mapping of the indices to new indices.
For causal graph, causal ordering always exists, but may not be unique. We note the set of causal orderings II", and any member of II* as x*. We can rearrange the variables according to a permutation æ, and we write the new associate adjacency matrix AÅ. where A is upper triangular π E IT". Lastly, we define Λ = A + A0 +... + A the transitive closure of the adjacency matrix. It straightforward to show that A (i.j) 0 if and only if there is a directed path from j only if A (i,j) )) > 0. A is of e
x
i to in G. Furthermore, there may be total causal effec also upper-triangular.
Top Order Divergence Dzop To measure the discrepancy between a permutation & and a graph G. we use the top order divergence (Rolland et al. 2022). The top order divergence Dtop (f1..., (1,..,, x (1,...,d) x (II,..,d) dj + [I. [I.... + Ny is defined as:
(9, = Σ A (i.)).
(())=(())
Drop counts the number of edges that cannot be recovered given topological order or said differently, the number of false negative edges of the fully connected DAG corresponding to m.
"There is total causal effect of if there exists some Ñ such that X, Jr X, in p ( (Definition 6. 12 in Peeeess al. (217h)
3

---

Published as a conference paper at ICLR 2025
As such, it represents lower bound the structural hamming distance (SHD) achievable when constrained to a particular topological order. Observation 1. The divergence Drop can also be written as G, v) = Diej A (i.
Lemma 1. Let n² E II* be causal ordering for G. Then Drop (G x²) = 0. (Rolland et al. 2022
SCMs and interventions An acyclic structural causal model (SCM) C = (S, PN) is determined by collection of d assignments 8j E S. S 1= d, such that for each assignment 8j defines X,
Xj : f (a. Nyy,
where Pa, V V is the set of variables on which directly depends on and Px: is a joint distribution the noise variables N = (N1,-., Na) that is jointly independent (Peters et al. 2017]. The associated graph G that connects variables to their parents is assumed to be acyclic.
Distribution with Intervention PX ((C.do(X.:NN.)) An intervention is then defined replacement of a subset of the structural assignments an SCM C, such that no cycle is created. In this work, we consider intervention on a single variable, where the structural assignment is replaced by new ran- dom variable independent of the parents. We denote the new distribution entailed by an intervention PoC.d((x We denote I S (1...d) the set of nodes that are intervened on. We also assume
that for each intervention, we have access to the interventional distribution Px P do. k I. The set of interventional random variables is denoted as Ñ = U
4 C-INTERVENTIONAL FAITHFULNES!
We here introduce the main assumption of our work that we name interventional faithfulness. Akin to the common assumption of faithfulness of joint distribution with respect to the true graph, which assumes that all d-separations in the graph are reflected by conditional independences in the entailed distribution, e-interventional faithfulness assumes that all paths in the graphs revealed by changes in distribution under intervention above a significance threshold e. This assumption is also similar how Mooij et al. (016) define causality as the existence of interventions inducing change in distribution. The main difference with comparable assumptions made in the literature is that this definition depends on statistical distance and significance threshold, instead of an oracle of the statistical dependence. We formalize our assumption as follows:
Definition Given the distributions pC,(0) and PC.do(X===e)) Vk E I, we say that the tuple (N.C) C) is e-interventionally faithful to the graph G associated to C if for all i + j, E I,j E V,
D (C.10) ,xx (C.d)(x.=N.) > eeif if and only if there is directed path from i to in G.
The concept of interventional faithfulness, where interventions on a node cause significant devia- tions in the distribution of downstream nodes, is discussed in various contexts. It aligns closely with the notion of "c-faithfulness" in causal graphs, where interventional distributions respect the causal structure and result in significant changes in downstream nodes (Shanmugam et al.) 2015 Squires et al.] 2020), and with the notion of "inffuentiality" TTian & Pearl (2001), Definition 2). Assumption 4.4 in Yang et al. (2018) explicitly states that interventions on upstream nodes should affect downstream nodes. The causal Markov condition and faithfulness for both observational and interventional distributions also support this idea (Addanki & Kasiviswanathan 2021). The use of interventional data to improve the identifiability of causal models is another related concept, em- phasizing how interventions can reveal causal relationships not identifiable from observational data alone (Hauser& & Bühlmann 2014).
Lemma 2. If all interventions in have full support and all directed paths in 9 imply a total causal effect, then (Ñ,C) is e-interventionally faithful for = (Follows from Proposition 6.13 in Peters ee al. (2017).)
Lemma 3. Consider a linear structural causal model C defined by the equations X, Eieri, BiyX; + N,, where Big are the weights representing causal effects, drawn in- dependently from a continuous distribution, and N, are noise variables that are independent of each other and of the parent variables, each with a distribution having full support. Let the Ñ; be distributions with full support. Then, (Ñ, C) is almost surely e-interventionally faithful for = O, the total causal effect along any directed path is non-zero with probability one.
4

---

Published as a conference paper at ICLR 2025
Remark. If (N,C) is e-interventioally faithful for O, then it is also e-interventionally faithful
for all 0 < << min (Px,
(0) P v(i.)) e E: D (Px) xx, pC.do(X.: 0}
Lemma B shows that the e-interventionally faithful assumption covers large class of SCMs. We leave further theoretical work to characterize how large the class of e-interventionally faithful (N,C) tuples as future work.
LATENT CONFOUNDERS
Until now, we have assumed that all causal variables are observed, an assumption called causal suf- ficiency. We here discuss how the notion of interventional faithfulness and the results of this paper are applicable to the case where only a subset of the causal variables are observed. This is a common situation in practice either because we want to focus on subset of variables which are of our inter- est, or because we are certain about the existence of unobserved confounders. To that end, we take the common formalization of marginalized SCMs, that marginalizes the latent confounders from the joint distribution and gives rise to a new SCM where the effects of marginalized variables are now reflected in functional dependencies among observed variables. Therefore, some variables become confounded as they depend on the same noise variables. An important property of acyclic SCMs that they are closed under marginalizations and that their marginalization respects the latent pro- jection (Bongers et al., (202). The latent projection describes how to construct a new graph among the remaining variables, representing the appearance of confounders, or dependent noise variables, with bidirected (hyper) edges (Vermal 1991 Evans 2016 2018b). Those two representations referred to as Acyclic Directed Mixed Graphs (ADMGs) Vermal 1991; Andrews et al.) 2022 Verma & Pearl 2022 Richardsonn] 2003) and mDAGs (Evans 2016 2018a| Bongers et al.] [0211) For our purpose, both representations are equivalent, and we thus focus on ADMGs. For the DAG G of the subset of variables V c Vs (V', E", B), where B is set of bidirected edges, and the marginalized SCM as C'. Proposition 1. If the tuple (N C)) is e-interventionally faithful to the graph G associated to C, then for any marginalization V C V, the marginalized SCM C' and the subset of interventional distributions N' = UKEzn [N&} is c-interventionally faithful to (V', E') from the projected ADMG g' = (V", E', B).
original SCM, We write the projection
This result derives directly from the fact that ancestral relationships are preserved in the projected graph, and that the (interventional) distributions induced by the marginalized SCM correspond to the marginals of the distributions induced by the original SCM (Bongers et al. 2021). As such, our
algorithm is applicable settings with confounders on subsets of variables, and the theoretical guarantees hold for the projected DAG (V', E'). However, we note that we here implicitly assume that there is no selection bias in the sampling process (e.g.. preferential inclusion of certain data points experiments), and that latent confounders remain stable across conditions.
6 A SCORE ON CAUSAL ORDERS
Given observational distribution PX and set of interventional distributions P (pf.do . E I), I C V. we define the following score for permutation n, for some statistical distance D :P(M) x P(M) + 10),), e 0.c>:
D, Pine,
Σ
(D (pe)) Px, p -c)
*() (EEEEE)EEL
+ +
D( D(22)00)
Intuitively, the sum quantifies how the causal order corresponds to strong causal effects. The rescaling from the second term by a factor of ensures that effects higher than will force the optimal solution to have क (i) < TT)) by inflating their weight compared to effects smaller than e. Usually, we can set the e of eq. (I) to the same value of e-interventional faithfulness as the input dataset, unless it is equal to zero. However, the remark in section 4 ensures the existence of suitable e in that case, as it can be chosen in a data-driven way by taking a non-zero value for smaller than the smallest non-negative distance.
Theorem Assume that we are given (C,(0) and pe (eddo(Xe==A)) Vk I and I V, such that (N,C, C) is e-interventionally faithful for some e > O, and let Topt E arg max, S(x). Then Drop (G Nopt)= Drop ( (,,,,,,77 n²))
5

---

Published as a conference paper at ICLR 2025
The above theorem shows that in the where observe interventions all the variables, we are guaranteed to find a valid topological order by maximizing our score when the data is e-interventionally faithful. Similar results were proven for this case where all the variables are intervened (Hauser & Bühlmann] 2012; Tian & Pearl, 2001). We now turn to the case where variables have probability of being intervened smaller than one. In that case, the error will not be zero in expectation, and we thus aim to upper-bound the expected error as measured by Drop. We first prove an important property of the optimum our proposed score. Lemma 4 shows that for given edge, a single intervention among large set of candidate variables is sufficient to correctly order the two variables of an edge.
Lemma 4. Assume that we are given pC.(() and P Vk I, such that (Ñ, C) is e- interventionally faithful for some O, and let Topt E arg max, S(1)). Let (i,5) E E, then if I or for some k E A AAN k I, then Topc(() < Fopr(f).
We now this result to derive graph dependent upper- to the expected error, given uniform probability for a variable to be intervened. We leave theoretical derivations for other intervention distributions, for example data dependent intervention selection, future work.
Theorem 2. Assume that we are given (C)(1) and Px p Yk E I, such that (N,C) is e- interventionally faithful for some >> O, and let I be chosen uniformly at random, where Pint ==
P(i Iyvi V,O Pint < 1, then EE[rop Topti] S E(s)e - -Pnne) PaNn))ANN (ANG))AN U(NAAN?
7 RELAXATION OF E- --INTERVENTIONAL FAITHFULNESS
We now look at the case where e-interventional faithfulness may not be fully fulfilled and we derive some bounds for that setting. We consider the worst case to be the one where interventions only reveal direct causal relationships, i.e., only children are affected by a node intervention such that the distance is larger than We can hypothesize that real distributions lie continuum between those two extremes, that is, some interventions have an e-strong effect only on children and other interventions have effect on more downstream variables. This restricted setting also covers the case when multiple paths between two variables and j "cancel out" the causal effect of on j. In that restricted setting, we can rewrite lemma 4 as follows:
Lemma 5. Let (i,j) E E, then j E I or for some kt E Pa \. Pa k E I, then Tope < π. Topt (j).
is then straightforward that the bound on Drop for Topt in that case is: Theorem 3. Let I be chosen uniformly at random, where Pint == P(i E IYvi E V,O < Pint < 1, then (Doopp(9 (G, opp)) & Eiijeeg(1 -Pine) U
Now that the bound only depends on the parent of the variables, it becomes possible to find closed form for the expectation of Drop for particular graph distribution.
Theorem 4. Let I be chosen uniformly at random, G be a random Erdos-Renyi directed acyclic graph with edge probability Pe. where Pint == P(i E Iyvi E V,O Pint then E DoDr (g, Topt)) S p-pp))e)
(1 PintPe) [-(I-pont
We also have a looser, but independent of pes bound
Pint
PintPe
E[Drop (G, Topt (1-Pin))²
Pint
The natural next step is to look at how the bound behaves as goes to infinity. More precisely, let's look at the normalized error [[Dee]( P
If pe is fixed, we simply get lim [G <
expect the edge probability to depend on the num- ber of variables. A common assumption is that the expected number of edges per variable is constant.
However, in realistic scenarios,
Pint
Lemma 6. Let E 1(d-1) Pe (dd - 1), where e > 0, E IR. is a constant, then (1 e Pine
limg++o (DDoppS.aappl (1-Pint)²
1
Pint
P
The above lemma shows that the expected error as d goes to infinity is O(d), providing strong guarantee on Topt even in a large scale setting.

---

Published as a conference paper at ICLR 2025
8 INTERSORT
Given that our score for causal order eq. (T) is optimized over a set of permutations, finding the optimum by exhaustively trying all possible solutions becomes intractable as the number of variables grows larger. We thus develop an algorithm to tractably find a solution that optimizes for our proposed score in eq. ( This algorithm consists of two steps. The first step uses different score to find an initial solution. In the second step, this solution is refined by performing a local search using original score eq. (
8.1 INTERSORT STEP 1: FINDING AN INITIAL SOLUTION
To find an initial solution, we design a score, similar to eq. (T. but this time on graphs. The intuition is that we want to score edges directly, and edges (i,j) that have a distance
D (pC110) _xx ( greater than e should be on the upper-triangular part. We thus write this new score Smit follows:
Sinst G,,,D.I,PP .Pmt==
E
,xx, D (P2,,0) p2 - c[G
(2)
(KJ)EG,EZ
Then, aim to find DAG G that maximizes this score.
Gopt arg max Sinit (G,c, Pins) GEGDAG
(3)
Once again, the search over all possible DAGS is computationally expensive. We thus design approximation algorithm based the following heuristic: the highest values D (C.100) , X, -.CddoX N.). which can be seen as score on the corresponding edge (i,j), should be edges in the solution DAG to maximize the score Smitt. To do so, we sort the edges based on this "edge score" from highest to lowest. We then construct our solution by adding the edges following the sorted order, adding an edge only if it does not break the acyclity of the solution. We
then stop adding edges when those have a score Dij D (pC,(()) .Px, - Nx)) lower than in the matrix D (Dig). The topological order of this solution Gopt for Siiit is then used initial condition for our original objective of maximizing S. The runtime of this algorithm is dominated by the sorting step. which O(d [Z] log(d [Z]).. We call this procedure SORTRANKING and illustrate it in algorithmm in the appendix.
8.2 INTERSORT STEP 2: A LOCAL SEARCH FOR Topt
Starting from the initial solution found by maximizing eq. we then perform a greedy local search to optimize our original objective eq. ( At each step, given a current solu- with higher
tion, we search in close neighbourhood set for a candidate permutation score than our current solution. To derive the neighborhood set, we introduce an operator Σ {(1,...d) + [1]] - ([1,..d)
{1,... defined such that for given set of per- mutations II, EIII returns a new set of permutations II'. Each permutation æ E II is modified by applying (1, (1,..d) >> (1, - ((1,..d) - (1,...d)), which for each variable i V, returns all the permutations such that . (2) takes any of the other d possible values. a takes one permuta- tion input and return set permutations which is (dd). ). The total number of applications of 2,, denoted as kt directly defines the neighborhood size which is (d22)) This definition allows us to explore varying depths of the search space, which is (d!), by controlling k, thereby balancing be- tween the breadth of the search and the computational resources required. A smaller & value implies a tighter search around the initial solution and encode our confidence in the initial solution, optimiz- ing runtime at the potential cost of missing broader, potentially better solutions. In our experiments, we use l: 1. We then stop once an iteration of the algorithm brings no improvement to the score. This procedure, that name LOCALSEARCH. is described in algorithm B the appendix. Our com- plete algorithm for finding the causal order is called INTERSORT (see algorithm [ in the appendix).
Now arises the question of how close the solutions from the approximation algorithm INTERSORT are to the optimum of eq. [ We evaluate this empirically for graphs with 5 variables, where computing the exact solution still viable. The results presented in fig. Ia As can be observed, the mean D Drop scores of the two algorithms are very close and have overlapping confidence intervals (at level 95%).
7

---

Published as a conference paper at ICLR 2025
ttp of Intersort for variables
D_ top of Intersort for 30 variables
Upperbound Thm
Upperbound Thmn Upperbound Thm Intersort
30
Upperbound Thm
Intersort
20
10
0.2886
0.3077
0.3033
0.38
0.1669
A5772
0.6134
6,707
0.7623
0.811
0.866
0.9231
0.9333
1.0006
0.5588
0.7377
03901
100
1.177
1,118
A7734
1,458
15803
1,6700
2,006
2.236
2.3703
2,9516
3.3541
Effective intervention ratio
Effective intervention ratio
(a) Simulation with 5 variables
(b) Simulation with 30 variables
Figure 1: Simulation and comparison between the two bounds, and between Intersort and the exact Topt- For each setting, we draw 20 graphs per setting, where setting is the tuple (Pint- Then, for each graph, we run the algorithm on 10 configurations, where each configuration corresponds to a draw of the targeted variables following Pint- For both 5 and 30 variables, we have Pint (0.25, 0.33, 0.5, 0.66, 0.75). In the 5 variables setting on the left, we have Pe E (0.5, 0.66, 0.75). In the 30 variables settings the right, we have Pe E {0.05, 0.1, 0.2]. The settings are ordered on the x-axis following what we call the effective intervention ratio Pins. We observe that the error is TPc approximately monotonic when ordered by the effective intervention ratio.
We note that more refined algorithms could be developed solve this optimization over permuta- tions. For example, for large d, the local search may become computationally expensive. However, for the purpose of this study, we find the proposed algorithm have satisfying properties, as scales to settings with 30 variables and finds a solution close to the optimum. We also report results for scale-free network modelled with the Barabasi-Albert distribution [Albert & Barabásil (2002) in the appendix in fig. 3] which supports the generality of our approach. We also report the performance of SORTRANKING that the score can be optimized at scale, even though as the error is above the upper-bounds for many settings. As such, we leave further algorithmic development for large scale settings potential future work.
large scale settings in figs. 4 and [S] The results demonstrate
observe room for improvement,
ESTIMATING THE DISTANCES FROM L.D.D SAMPLES
We now turn to the question of computing the statistical distances between observational and interventional distributions from real samples. Indeed, until now, assumed access population distributions, such that D(P, Q) = 0 if and only if P = Q. However, in real world setting, we may only assume that we have access to i.i.d samples from the distributions, that is {X*) PC.(0) and for j E [1....,d} d}, {X
Px Co.dol (odo(((=N,))) where no....., nd E are the sample sizes of the observational set and of the interventional sets. Given this setting, require statistical distance with the following properties: should be applicable to sample distributions, the distance between i.i.d samples should converge to the distance between the population distribution to infinity, with some guarantees on the convergence rate. distance that fulfills all those criteria is the Wasserstein distance Villani al. (2009). More specifically, it converges to the population
goes
distance in O vlan /
where n is the number of samples. We recall the definition of this distance
in the appendix.
10 EMPIRICAL RESULTS
We now evaluate Intersort on simulated empirical data and compare its performance to various baselines. The graphs are simulated from Erdos-Renyi distribution (Erdós et al.) 1960). with an expected number of edges per variable E (1, We follow a setup close to (Lorch et al. 2022) to simulate data from linear and random Fourier features (RFF) additive functional relationships. We also apply the models to simulated single-cell data from the SERGIO (Dibacinia & Sinha 2020) model, using the code from Lorch al. (2022) (MIT License, v1.0.5). Lastly, apply on neural network functional data following the setup of Brouillard et al. (0220) and using the implementation of Nazaret et al. (023) (MIT License, vO.1.0). We run the models varying
8

---

Published as a conference paper at ICLR 2025
Model Type
Madel Type FASE
FASE
60
PC
40
DCDI
DCDI
GIES
Intersort
Intersort
30
20
10
23.33
50.0
73.33
100.0
23.33
50.0
73.33
100.0
Fraction intervened variables (%)
Fraction of intervened variables (%)
(a) Linear 30 variables
(b) RFF 30 variables
60
Madel
Model Type EASE
EASE
50
PC
DCDI
40
DCDI
ÇRES
Intersort
100p
30
20
10
10
50.0 Froction variables intervened (%)
100.0
100.0
Fraction of intervened variables (%)
(c) NN 30 variables
(d) GRN 30 variables
Figure 2: Comparison the performance of the baselines and our model INTERSORT across diverse data domains presented (linear, RFF, NN and GRN data), for 30 variables. The x-axis corresponds to the fraction of variables that have been targeted by an intervention. The y-axis the performance of causal ordering prediction better). The violins are order from left to right: EASE, PC, DCDI, GIES, Intersort. Results for 10 and 100 variables can be found in the appendix (figs. and 8)
measured by the Diop metric (see section 3 lower is
levels of intervention, where the ratio of intervened variables in (25%, 50%, 75%, 100%]. The data is always standardized based on the mean and variance of the observational dataset, which removes the Varsortability (Reisach et al.) 2021) artefact the data. For the RFF and linear domain, the distribution of the noise is chosen uniformly random from uniform Gaussian (noise scale independent from the parents), heteroscedastic Gaussian (noise scale functionally dependent on the parents), and Laplace. For the neural network domain, the noise distribution is Gaussian with fixed variance. We run on 10 simulated datasets for each domain and each ratio of intervened variables. We simulate 5000 samples for the observational datasets and 100 samples for each interventions, which is setting similar to real single cell transcriptomics datasets (Replogle et al. 2022).
Choosing appropriate baselines compare to is not trivial, given that, to our knowledge, our setting of predicting the causal order from interventional data has not been considered in the literature, as the focus prior literature has been on observational data (Reisach et al., 2021: Bühlmann al. 2014 Rolland et al., 2022. Shimizu et al.) (011). As such, we construct causal orders from the CPDAG predicted by two standard methods, namely PC (Spirtes et al. 2000 and GIES (Hauser & Bühlmann, 2012), by creating DAG from the oriented edges and then computing the topological order of this DAG. PC is a constrained based method relying on conditional independence tests to estimate the structure of the graph. We run the implementation of Zheng al. (2024) (MIT License, causal-learn 1....3). GIES is an extension to interventional data of the GES model (Chickering (002), which score based method that greedily adds and removes edges the estimated CPDAG. We

---

Published as a conference paper at ICLR 2025
the Gaussian BIC score, and run the package implementation of Gamella (2022) (BSD 3-Clause License. v0.0.1). Additionally, we compare to EASE (Gnecco et al. 2021), which is a method that aims to learn the causal order from observational data, leveraging the insight that extreme tail-values reveal the causal order. Given that interventions can lead to extreme values not present in the obser- vational data, we also compare this method. For EASE, we our own Python implementation of the algorithm. Lastly, we compare to DCDI (Brouillard et al. 2020), which is continuously differ- entiable causal discovery model that can leverage interventional data. For Intersort, we use = 0.3 for the linear, RFF and neural network domain, and 0.5 for the single-cell domain. We set c = 0.5. We compute the Wassertein distances with the SciPy python package (Virtanen al. 2020).
The results for each method on the different types of data considered are displayed in fig. 2 where the distribution of the Prop score of each model plotted against the ratios of intervened variables considered. As can be observed, INTERSRTT performs well on all data domains, and shows decreasing error as more interventions are available, exhibiting the model's capability to capitalize on the interventional information to recover the causal order across diverse settings. Compared to the baselines, only GIES in the linear domain and DCDI in the neural network domain at 25% and 50% perform better. These experiments demonstrate that c-interventional faithfulness is fulfilled by a diverse set of data types, and that this property can be robustly exploited to recover causal information. Only when strong assumptions about the data distributions are fulfilled, such as linear data for GIES, can better results be obtained in low intervention settings.
11 DISCUSSION AND CONCLUSION
We note that INTERSORT's performance could still be improved in various ways. For example, a more scalable closer to the optimum upproximation algorithm could be designed. Scalability of Intersort in its current form is mainly constrained by the LOCALSEARCH component, for which alternative optimization techniques could be employed variable sets. Also, the optimal parameter c could be chosen in a data dependent way instead of using fixed value. Lastly, other statistical distances, especially ones that converge faster to in terms of number of samples when the two distributions are equal, could lead to better results. We leave such potential improvements as future work. Another question that may need further investigation is the e-interventional faithfulness assumption. We argue that it is not any stronger than common assumption in the literature such as faithfulness, and lemma 3 shows that it already covers a sizeable set of SCMs. Furthermore, our empirical results demonstrate that it probably holds for a rather large class of SCMs. We also derive theoretical results for a relaxation of this assumption in 7 An interesting direction of theoretical work would be to further analyze the intricate relationship between the statistical distance D, the number of variables d, the parameter 6, the interventional random variables Ñ, and the sample size for non-asymptotic settings. For example, our framework makes it amenable to study the strength of the interventions needed to reveal the causal descendants above a statistically significant threshold.
enhance efficiency and manage larger
In this study, introduced INTERSORT, innovative algorithm designed to uncover the causal order from interventional data by optimizing for a new proposed score on causal orders. We intro- duced the c-interventional faithfulness assumption and proved that interventional datasets fulfilling it have strong guarantees in terms of upper-bounds on the expected error of the optimum of our score. The performance of INTERSORT and the validity of our theoretical findings was extensively demon- strated on a diverse set of simulated datasets, across functional relationships, noise types and graph densities. INTERSORT has demonstrated superior performance when compared to established bench- marks such as PC, GIES, DCDI and EASE. The robustness and versatility of INTERSORT underscore the potential of the c-interventional faithfulness assumption to reshape causal inference methodolo- gies. We envision that this work should spearhead new model development based on our proposed perspective on dataset with high numbers of single variable interventions. This includes downstream tasks such as causal discovery, for example by reconstructing the graph given the estimated causal or- der. It could inform active intervention selection as well, as designing a policy to choose which vari- ables to target next may lead to better guarantees than our results based interventions selected uni- formly at random. All these directions and method developments can have real world impact on crit- ical application domains such as biology, from which this work and its assumptions were inspired.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE
The authors thank Djordje Miladinovic, Aleksei Triastcyn and Lachlan Stuart for feedback and edits on the manuscript. The authors also thank Prof. Nicolai Meinshausen for valuable suggestions on the theoretical part, as well as Prof. Stefan Bauer for discussions about related work and relevance of the project. MC, AM and PS are employees and shareholders of GSK plc.
REFERENCES
Raghavendra Addanki and Shiva Kasiviswanathan. Collaborative causal discovery with atomic in- terventions. Advances in Neural Information Processing Systems, 34:12761-12773, 2021.
Miklós Ajtai, János Komlós, and Gábor Tusnády, On optimal matchings. Combinatorica, 4:259- 264, 1984.
Kyle Akers and TM Murali. Gene regulatory network inference in single-cell biology. Current Opinion in Systems Biology, 26:87-97, 2021.
Réka Albert and Álsert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Bryan Andrews, Gregory F Cooper, Thomas S Richardson, and Peter Spirtes. The m-connecting imset and factorization for admg models. arXiv preprint arXiv:2207.0896 207022077.,6,, 2022.
Nathamiel Baum-Snow and Fernando Ferreira. Causal inference in urban and regional economics. In Handbook of regional and urban economics, volume 5, pp. 3-68. Elsevier, 2015.
Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M Mooij. Foundations of structural causal models with cycles and latent variables. The Annals of Statistics, 49(5): 2021.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21 01-21865-21877 2020.
Peter Bühlmann, Jonas Peters, and Jan Ernest. Cam: Causal additive models, high-dimensional order search and penalized regression. 2014.
Lian En Chai, Swee Kuan Loh, Swee Thing Low, Mohd Saberi Mohamad, Safaai Deris, and Zalmiyah Zakaria. A review on the computational approaches for gene regulatory network con- struction. Computers in biology and medicine, 48:55 65.5-65,222 2014.
Mathieu Chevalley, Yusuf Roohani, Arash Mehrjou, Jure Leskovec, and Patrick Schwab. Causal- Bench: A Large-scale Benchmark for Network Inference from Single-cell Perturbation Data. arXiv preprint 10. 2022.
Mathieu Chevalley, Jacob Sackett-Sanders, Yusuf Roohani, Pascal Notin, Artemy Bakulin, Dariusz Brzezinski, Kaiwen Deng, Yuanfang Guan, Justin Hong, Michael Ibrahim, Wojciech Kotlowski, Marcin Kowiel, Panagiotis Misiakos, Achille Nazaret, Markus Püschel, Chris Wendler, Arash Mehrjou, and Patrick Schwab. The CausalBench challenge: A machine learning contest for gene network inference from single-cell perturbation data. arXiv preprint 230.. 2023.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 30755)5007-554, 2002.
Gregory F.
Cooper and Changwon Yoo. Causal discovery from a mixture of experimental and obser- vational data. In Proceedings of the Fifieenth Conference on Uncertainty in Artificial Intelligence, UAI'99, pp. 116-125, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606149.
Paul Datlinger, André F Rendeiro. Christian Schmidl, Thomas Krausgruber, Peter Traxler, Johanna Klughammer, Linda C Schuster, Amelie Kuchler, Donat Alpar, and Christoph Bock. Pooled crispr screening with single-cell transcriptome readout. Nature methods, 14(3):297-301, 2017.

---

Published as a conference paper at ICLR 2025
Paul Datlinger, André F Rendeiro, Thorina Boenke, Martin Senekowitsch, Thomas Krausgruber, Daniele Barreca, and Christoph Bock. Uttra-igh-throughh single-cell ra sequencing and per- turbation screening with combinatorial fluidic indexing. Nature methods. 18(6):635-666 642, 2021.
Kaiwen Deng and Yuanfang Guan. A supervised Hightgbm-basee approach to the gsk. ai causalbench challenge (ielr 2023). 2023.
Payam Dibaeinia and Saurabh Sinha. Sergio: single-cell expression simulator guided by gene regulatory networks. Cell systems, 11(3):252-271, 2020.
Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles Fulco, Livnat Jerby-Amon, Nemanja D Marjanovie, Danielle Dionne, Tyler Burks, Raktima Raychowdhury, et al. Perturb-seq: dissecting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. cell, 167(7): 1853-1866, 2016.
Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAr05, pp. 178-184, Arlington, Virginia, USA, 2005, AUAI Press. ISBN 0974903914.
Frederick Eberhardt, Clark Glymour, and Richard Scheines. N-1 experiments suffice to determine the causal relations among n variables. Innovations in machine learning: theory and applications, pp. 97-199 12, 2006.
Paul Erdös, Alfred Rényi, et al. On the evolution of random graphs. Publ, Math. Inst. Hung. Acad. Sci, 5(1):11-600 1960.
Robin Evans. Markov properties for mixed graphical models. In Handbook of graphical models, pp. 39-69. CRC Press, 2018a.
Robin Evans. Graphs for margins of bayesian networks. Scandinavian Journal of Statistics, 43(3): 625-648, 2016.
Robin Evans. Margins of discrete bayesian networks. 2018b.
Ruth E Farmer, Daphne Kounali, A Sarah Walker, Jelena Savović, Alison Richards, Margaret T May, and Deborah Ford. Application of causal inference methods in the analyses of randomised controlled trials: systematic review. Trials, 19:1-14, 2018.
Stefan Feuerriegel, Dennis Frauen, Valentyn Melnychuk, Jonas Schweisthal, Konstantin Hess, Ali- cia Curth, Stefan Bauer, Niki Kilbertus, Isaac S Kohane, and Mihaela der Schaar. Causal machine learning for predicting treatment outcomes. Nature Medicine, 30(4):99 968, 2024.
Juan Gamella. gies python package, 2022. URL hettp:://gtthubb.com//aaaaa gies
Nicola Gnecco, Nicolai Meinshausen, Jonas Peters, and Sebastian Engelke. Causal discovery in heavy-tailed models. The Annals of Statistics, 49(3): 2021.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Reseurch, 13 (1):2409-2464, 2012.
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-92) 2014.
Christina Meinze-Deml. Marloes H Maathuis, and Nicolai Meinshausen. Causal structure learning. Anmual Review of Statistics and Its Application. 5:371-391, 2018.
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008
12

---

Published as a conference paper at ICLR 2025
Xinlin Hu, Yaohua Hu, Fanjie Wu, Ricky Wai Tak Leung, and Jing Qin. Integration of single-cell multi-omics for gene regulatory network inference. Computational and Structural Biotechnology 2020.
Journal,
Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sci- ences. Cambridge university press, 2015.
MichaelJoffe, Manoj Gambhir, Mare Chadeau Hyam, and Paolo Vineis. Causal diagrams in systems epidemiology. Emerging themes epidemiology, 9(1):1-18, 2012.
Marcin Kowiel, Wojeiech Kotlowski, and Dariusz Brzezinski. Causalbench challenge: Differences in mean expression. 2023.
Romain Lopez, Christiistiin Hütter, Jonathan K Pritchard, and Aviv Regev. Large-scale differen- tiable causal discovery of factor graphs. arXiv preprint arXiv:2206.0788 2022.
Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. arXiv preprint arXiv:2205. 12934, 2022.
Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113(27)7361-7366 2016.
Francesco Montagna, Atalanti Mastakouri, Elias Eulig, Nicoletta Noceti, Lorenzo Rosasco, Dominik Janzing, Bryon Aragam, and Francesco Locatello. Assumption violations in causal discovery and the robustness of score matching. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp. 47339-47378. Curran Associates, Inc., 2023a. URL aageeaaarsaaaaa33eeee222222eeee2
Francesco Montagna, Nicoletta Noceti, Lorenzo Rosasco, Kun Zhang, and Francesco Locatello. Causal discovery with score matching additive models with arbitrary noise. In Mihaela van der Schaar, Cheng Zhang, and Dominik Janzing (eds.), Proceedings of the Second Conference on Causal Learning and Reasoning, volume 213 of Proceedings of Machine Learning Research, pp. 726-751, PMLR, 11-14 Apr 2023b. URL montagna23a html
Joris M Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schölkopf. Dis- tinguishing cause from effect using observational data: methods and benchmarks. Journal of Machine Learming Research, 17(32):1-102, 2016.
Achille Nazaret and Justin Hong. Betterboost-inference of gene regulatory networks with perturba- tion data. 2023.
Achille Nazaret, Justin Hong, Elham Azizi, and David Blei. Stable differentiable causal discovery. arXiv preprint arXiv:231111026. 2023.
Judea Pearl. Causality. Cambridge university press, 2009.
Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs. Neural computation, 27(3):771-799) 2015.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Alexander Reisach, Christof Seiler, and Sebastian Weichwald. Beware the simulated dag! causal discovery benchmarks may be easy to game. Advances in Neural Information Processing Systems, 34:27772-27784. 2021.
Joseph M Replogle, Reuben A Saunders, Angela N Pogson, Jeffrey A Hussmann, Alexander Lenail, Alina Guna, Lauren Mascibroda, Eric J Wagner, Karen Adelman, Gila Lithwick- Yanai, et al. Mapping information genotype-phenoyy landscapes with genome-scale perturb-seg securb--q..... Cell, 2022.
13

---

Published as a conference paper at ICLR 2025
Thomas Richardson. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 30(1):145-157, 2003.
Paul Rolland. Volkan Cevher, Matthäus Kleindessner. Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear addi- tive noise models. In International Conference Machine Learning, pp- 18741-18753, PMLR, 2022.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721): 523-529, 2005.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learn- ing causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvarinen, Yoshinobu Kawahara, Takashi Washio, Patrik Hoyer, Kenneth Bollen, and Patrik Hoyer. Directlingam: A direct method for learning a linear non non-gaussian structural equation model. Journal of Machine Learn- ing Research-JMLR,
2011.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation-basee causal structure learning with unknown intervention targets. Conference on Uncertainty in Artificial Intelligence, pp. 1039-1048 PMLR, 2020.
Jin Tian and Judea Pearl. Causal discovery from changes. In Jack S. Breese and Daphne Koller (eds.), UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, August 2-5, 2001, pp. 512-521. Mor- gan Kaufmann, 2001. URL /tRLL/tttts:::ddspittttttt
/ sayttpssalllllllllll.ll @eeettiileeee.sss..... http://slpppie 1dd=1
T. S. Verma. Invariant properties of causal models. Technical Report R-134, UCLA Cognitive Systems Laboratory, 1991.
Thomas S Verma and Judea Pearl. Equivalence and synthesis of causal models. In Probabilistic and causal inference: The works of Judea Pearl, pp. 221-236. 2022.
Cédric Villani al. Optimal transport: old and new, volume 338. Springer, 2009.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nel- son, Eric Jones, Robert Kern, Eric Larson, Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 10.1038//41592-11 592-019-0066-22.
Karren Yang. Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. In International Conference on Machine Learning, pp. 5541- 5550. PMLR. 2018.
Jing Yu. Anne Smith, Paul P Wang, Alexander Hartemink, and Erich D Jarvis. Advances to bayesian network inference for generating causal networks from observational biological data. Bioinformatics, 20 (11188)359443666 3603, 2004.
Yujia Zheng, Biwei Huang, Wei Chen, Joseph Ramsey, Mingming Gong, Ruichu Cai, Shohei Shimizu, Peter Spirtes, and Kun Zhang. Causal-leam: Causal discovery in python. Journal of Machine Learning Research, 25(60)11-8, 2024.
14

---

Published as a conference paper at ICLR 2025
A PROOFS OF THEOREMS
Proof of Lemma Recall that for a linear SCM, the total causal effect between any pair (i, is equal the sum of the products of the weights along each paths from to j. Given that the weights are continuously random and independent, the probability that the sum is exactly 0 is 0. As such, the tuple (N, C) is e-interventionally faithful for e = 0 almost surely.
Proof of Theorem 7 Let D be d x d matrix containing all the distances, where D(i,j) D (..100 pr. For the case of every variables being intervened on, we can set 0. X;
We are going to prove that Appe is upper-triangular, and from that it follows that Drop(G, Topt) = 0.
We know that such permutation exists, for any n²,, Ax- is upper- -rian-rriangular..
Second, note that given that (N, C)) is interventionally faithful, A has the non zero entries the same position than the matrix D. We thus need to show that for any Dr that is not upper-triangular, then E arg max S(r). Then we compute:
S(x*)= =
E
(D(i,)) - E)
x² ("()<an"())
d. (d
Σ D(i,))
x' (0)x)((
ΣD (i.5) d- (d (d-1)
2
Then, let be such that D has some non-zero entries in the lower-triangular part. Then:
S(**) = Σ
D(i.) > 0, )(
which implies that x & arg max, S(T).
Proof of lemma 4 Let & be a variable that satisfies the condition, that is, E I and k E AND A Then, for this the hypothesis implies that D (PC-(0) Px, (()) > c and
D (Pp (pe.10) , (c)) = 0. We thus need to show that given those distances, Topt is such that (i)e < (T).
Let's note that only distances that are larger than contribute positively to the score. All the dis- tances that are equal to contribute -c to the sum. As such, necessary condition for an optimal contribute to the sum, which hap-
Co.do(X,:-N, permutation is that all distances D (pC,(0) X.
pens only if Topt (i) < (f). Given that (Ñ,C) is c-interventionally faithful, we have that any II are such that all distances larger than contribute S(Tr), which shows existence of such permutation. Topt thus must have that Tope < Topt (j). If E I, then with the same argument we have Topt (i) Tope
remains to show that Topt (1) Tope (k) if & I. We have D (PC.(0), (C)d((Xe:=Ne) Xx,
which contributes negatively to the score if Tope (k) TTppe(i) (i). So changing Tope (i) < Topt (k) improves the score by e, as & This implics that Tope must be smaller than Topt (k)).
Lastly, if j E I, but not and no l E ANO. ANÇ, we need to show that we still have Tops (1) < Topt (j). With the same argument as before, having Tipe (i) < Tope (j) can only improves the score & T. This concludes the overall proof.
15

---

Published as a conference paper at ICLR 2025
Proof of theorem
E| Dropp( (9, Topt)] = E
Σ (1)2
(1.))E
Σ
(o))))))))))
(1.))
= Σ P(Tope(() (i) > Tope
(3,))9
Now let's look at P( (i) > Topt (i)), where there is an edge from i to j in the graph. Let's note the condition of lemma 4 as C.
P(Tope (1) > Topt (i)) P(Topee (i) Tope (j) -C))))()() (() > Tppe
P(Tope (1) > Topt (j) P(-CC)
P(Tope(i) Tope -C))-C) ANY U U \ ANY k $ I)
P(Tope(i) Topt (1) Pint) IANJUUMANPI
S (1 Pint) P UANTUA)AANN
We can then take the sum over all the edges to conclude the proof.
Proof of theorem 4 Without loss of generality, we assume that the variable are already in the causal order. We then write the error as sum on all the upper-triangular elements that contain an edge and for which the variable are misplaced by Topt.
d 1 d
E[Drop Topt) = E
Σ
i=
j=i+1
d d
P((t,) E E, Tope(t) > Topl (7))
1=
Σ Pe P(Tope > (t) E E)
We now upper-bound the probability of error given the existence of an edge:
P(Tope > ( F. < PiEIIAAE j.k Paf A Pa = h I)
j-1
(1 Pint)
II
P(k E Paf Ak Pa k I)
II k=i+1
P(k E Paf = = K
k=1
(1 Pint )
II P(k Pag = k II
k=++1
j-1
(1 Pint) )
II (1 P(k E Pag A E)E
k=++1
(1 Pint)
)
P
Plugging this back into the original sum and working out the geometric sums:
16

---

Published as a conference paper at ICLR 2025
d-1
EiDrop (9, Topt S Pe(11 Pint )
(1 PinePe)
im jmi+1
d-1 d-i-1
=Pe(1 - Pine) )
(1 PintPe) )
iml
0
d-1
(1 PintPe) d-i
=Pe(1
Pint)
PintPe
im
d-1
Pe Pint)
d
Dint d
PintPe
i=0
-Pint) 2
PintPe)
Pint
(1 -Pint)
(1 PintPe)
d (1 PintPe)
Pint
PintPe
(1- 1-Pins)
[PintPe d - (1 - PintPe) + (1 - -PintPe) 2+1]
Pineee
(1 Pint)" d
Pint
Proof of lemma 6
First, we can rewrite the equation Pe to get Pe 3. Then, plugging it into the
bound we get:
(1 Pint)
1 (1 DintPe) )dr
D(op (9, Topt)) 5
d (1 PintPa)
Pint
PintPee
(1 Pint) )
d (1 Pint 9 d (1 Pint 7
Pint
d
Pint
Finally, we normalize by d and take the limit:
Diop (G. Topt)]
(1 - pine)
(1 Pint g)
lim 2-000 d
lim
(1 Pint z)
10000
Pint
Pint
11 - -Pint)
6 P-pine
Pint
Pint
B PEN AND PAPER EXAMPLE
We here spell out all the possible configurations for graph with 3 variables with the associated expected error of Topt in table | and appendix B Readers may find those example useful to build intuition how the algorithm works.
17

---

Published as a conference paper at ICLR 2025
Table I:
Expected top-order divergence for graphs of size with of the three variables ob-
served under intervention.
Number edges
Adjacency Matrix
Transitive Closure
E[Drop Topt
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0
0
0
0
0 0
0
0
0
0
0
0
1
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Table 2: Expected top-order divergence for graphs of size 3, with out of the three variables ob- served under intervention.
Number edges
Adjacency Matrix
Transitive Closure
E E[Drop Topt))
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
3
2
0
0 1 0 0 1
0
0
0
0
0
0
0
1
1
2
0 0
1
0
1
0
0
0
0
2
0
0
0
0
0
0
0
0
0 1
0
3
0
0
1
0
0
1
18

---

Published as a conference paper at ICLR 2025
C PSEUDOCODES
Algorithm 1 Complete algorithm
1: procedure INTERSORT( S: score function eq. Q
D: statistical distance function,
index set intervened variables.
(C()) observational distribution,
X
Pine: interventional distributions
Initialize D as a zero matrix size x
3:
for each (i.j) E [L..d] do
4:
if E I then
D < (PX) xx;
pC.do(X;=8(1)
5:
end if 7: end for
6:
Tince + SORTRANKING(D,e
Topt LOCAL Fimi, e, D,
((1)) P((0) Pine)
10: return Topt
11: end procedure
Algorithm Finding an initial solution
procedure SORTRANKING(D. matrix distances,
2: G t- emmpt directed graph
3: sorted_edges + sort edges in the d x d matrix of distances D in descending order
4: for each edge (i, j) in sorted_edges do and D(t,)) then
if there is no path from j Add edge from to j to
7: end if
8: end for
9: Wind +- topological order(G)
return mawst
11: end procedure
Algorithm Local search optimization
I: procedure LOCALSEARCH(T S: score function of cq. ([. D: statistical distance function, I: index
set of intervened variables, pC,(1), observational distributions. Pana: interventional distributions)
Teurrent f- Winst
3: Scurrent S(Feurrent, D,I, (C)()) Pint)
4: while True do
Heandiddttes E( (Teeerree)))
6: Theatt <- None
7:
for each Weandidate in Ilconddattss do
Smandidate f- S(Meandidatte e, D,I, (D) Pins)
9:
if Soandidate Scurvent then &- Reandidate
10:
11:
Scurrent Standidate break
12:
13:
end if end for
14:
15:
if Tnezt is None then break Teuerent +- Tuent
16:
18:
19:
end while
20:
return Teurrent
21:
end procedure
19

---

Published as a conference paper at ICLR 2025
D WASSERSTEIN DISTANCE
The W p- Wasserstinn distance between two distributions is defined as follows Viillan et al. 2009 :
Definition 2. The p- Wasserstein distance Wp between two probability measures P and Q on R" with finite p-moments, E (o),
UXax 11=111--0 y1l"d=(x,,))
w Q)
inf 7ET(P.))
(4)
where T(P, Q) the set of joint probability measure on IR I2d with marginal P and Q
In this work, we use p 1, and we have d = 1 as we only compute the distance between the marginal distribution of each variable. Let Pa and Qn be distributions of samples from / and of size n. We have that the distance (Pn.. Qn) tends to Wp(P, (.P.Q. Q) as n + +oc. Furthermore, for
2. Ajtai et 1984) show that:
BJW, Q.. (2(,,Q) = O VIn
(5)
vn
E DETAILS OF EMPIRICAL EVALUATION
E.I LINEAR AND RFF DOMAIN
Each causal variable ø, is defined with respect to its parents z(a()) through the equation:
Zz + (T G) = fy (Fpag) + hy (TPag))
(6)
Here, Ej represents additive, potentially heteroscedastic noise, where the noise scale hy (xp(t)) is modeled as:
hr(x) = log(1 + exp(g)
with (z) being nonlinear function. For the heteroscedastic case, we use random Fourier features with length scale 10.0 and output scale of 2.0.
To simulate interventions, the value of the intervened variable is set to fixed constant that is drawn from signed Uniform distribution between 1.0 and 5.0.
E.1.1 DOMAIN-SPECIPIC MODELLING
LINEAR Domain: The causal functions f, linear transformations:
fy("ra)) = w/ Trag + by
(8)
where wy and by are independently sampled for each transformation. As in we sample wy from a signed Uniform distribution between and 3, and by from a Uniform distribution between -3 and 3.
RFF Domain: Each ʃ3 is drawn from Gaussian Process (GP) approximated using random Fourier features:
M
[x(pgg) + SV
2
Σ
a
(m) cos
(
(w)))) Xpa + 8(m))
M
m=1
((0,I), I), and ((m) Uniform 2T), and the parameters bj. Cj. and the length scale Ej are sampled independently. The parameter M is set to 100. The length scale l, drawn from a Uniform distribution between 7.0 and 10.0, the output scale ej from Uniform distribution between 10.0 and 20.0 and the bias by from Uniform distribution between 3 and 3.
where (m) NO 1), (m() NN(00,
E.2 SIMULATION OF SINGLE-CELI GENE EXPRESSION DATA
As in Lorch et al. 2022), the SERGIO simulator by Dibaeinia & Sinha (020) to gener- ate realistic tigh-throughput scRNA-seq data, implemented the AVICI package by Lorch et al. 2022).
20

---

Published as a conference paper at ICLR 2025
E.2.1 SIMULATION PROCESS WITH SERGIO
SERGIO generates gene expression data snapshots from the steady state of dynamical system governed by the chemical Langevin equation. The system's evolution is influenced by master regu- lators (MRs) with fixed rates and non-linear interactions among genes defined by the causal graph G. Cell types emerge from variations in MR rates, contributing to biological system noise and type- sype-specific expression profiles.
E.2.2 PARAMETERS FOR SIMULATION
To simulate cell types (5) across genes, SERGIO requires parameters such as interaction strengths & (Uniform between 1.0 and 5.0), MR production rates b (Uniform between 1.0 and 3.0), Hill coefficients y (2.0), decay rates À (0.8), and stochastic noise scales Ç (1.0), These are selected within recommended ranges to ensure realistic simulation. The values in parenthesis represents the parameter distributions we used. We did not simulate technical noise.
Intervention on variable corresponds to knocking out gene, that is, the expression of the gene is kept at O.
E.3 SIMULATION OF NEURAL NETWORK SAANRR--BASED DATA FOR CAUSAL DISCOVERY
In the context of simulating data for causal discovery, construct domain where the data is generated by a set of random fully connected neural networks. These networks serve as the backbone for defining the observational conditional distributions within simulated environment.
E.3.1 NEURAL NETWORK SPECIFICATION
Each neural network a multilayer perceptron (MLP) with a single hidden layer consisting of 10 neurons. Formally, the MLPs functions MLP R R', equipped with ReLU activation functions, mapping a a j-dimensional input to a scalar output. The output each MLP represents the mean f of the conditional distribution for the corresponding variable:
P)(z)(Fpa)) Nip MLP(Sngg), 1.0).
(10)
E.3.2 INTERVENTIONAL DATA GENERATION
For the simulation of interventional data, the procedure modifies the distribution of intervened nodes. Instead of being determined by the MLP, the distribution of an intervened node is fixed to marginal normal distribution:
()(z))d((z;)) (22 1.0).
(11)
This alteration simulates the effect of an intervention the data generation process.
F ADDITIONAL EXPERIMENTS
F.1 SIMULATIONS
Additional results for the simulation evaluations. Figure shows the performance of Intersort for scale-free networks of size and 30. Figures and 5 show the performance of SORTRANKING on large scale settings of 1000 and 2000 variables, for both scale-free and Erdos-Renyi networks. Figure 6 presents a possible heuristic for selecting variables to intervene on, and comparing to a random selection.
21

---

Published as a conference paper at ICLR 2025
D_ top of Intersort for variables
p_top of Intersort for 30 variables
Upperbound Thm
Upperbound Thmn Intersort
Intersort
Actual opt
Di09
0.2635
0.2988
0.3470
0.3044
0.3952
0.527
0.5976
0.6957
0.7888
0.7905
0.8964
1.1858
0.5089
0.6906
0.7509
0.9116
0.9682
1.1378
1.278
1,3812
1,7087
1,8222
1.9364
2.5561
2,9047
Effective intervention ratio
Effective intervention ratio
(a) Simulation with 5 variables
(b) Simulation with 30 variables
Figure 3: Simulation and comparison between the bounds of theorem for scale-free networks, and between Intersort and the exact Topt- For each setting, we draw 20 graphs per setting following Bareba scale-free distribution, with average edge per variable {1, 2. setting
the tuple (Pint,Pe,, where = d(d-1) Then, for each graph, we run the algorithm on 10 configurations, where each configuration corresponds to a draw of the targeted variables following Pint. For both and 30 variables, we have Pint {0.25, 0.33, 0.5, 0.66, 0.75). The settings are
2B(#edges),
ordered on the x-axis following what call the effective intervention ratio Pint We observe that
v the error approximately monotonic when ordered by the effective intervention ratio.
D top of SORTRANKING for 1000 variables
D top of SORTRANKING for 2000 variables
200
Upperbound Thm
Upperbound Thin
150
300
Dtop
200
50
3.2291
3,9538
4,2624
5,719
5,5901
6,4582
7,378
19077
025200
9.6873
1384
1003
11.88 16.86155
14,758
16.7705
4.5854
5.5908
6.0264
13798
7.9050
10.4355
12 0529
6964
11.799
15 15.8113
16. 7726
20,871
23,117
Effective Intervention rati
Effective intervention ratio
(a) Simulation with 1000 variables
(b) Simulation with 2000 variables
Figure 4: Simulation and comparison between the bounds of theorem for scale-free networks and SORTRANKING, For each setting, draw 2 graphs per setting following Barabasi-Albert scale- free distribution, with average edge per variable in 21, 2,333. 3). A setting is the tuple (pine, Pe), where
Pr. d(d-i) Then, for each graph, we run the algorithm on 1 configuration, where each config- uration corresponds to draw of the targeted variables following Piut- For both 5 and 30 variables, we have Pint E {0.25, 0.33, 0.5, 0.66, 0.75). The settings are ordered on the x-axis following what call the effective intervention ratio Pint Even though the objective can be approximately solved vPe
2E(#edges)
at scale, we observe room for improvement as the performance of SORTRANKING above the upper-bound in many settings.
22

---

Published as a conference paper at ICLR 2025
D p.top SORT RANKING 1000 variables
D_tox top SORTRANKING for 2000 variables
1000
Upperbound Thm
100
Upperbound Thmn Upperbound
750
Upperbound Thm
SORTRANKING
SORTRANKING
Dtop
500
250
3.5355
4.6699
5.5901
7.071
7.379
7,9058
9.3336
10.4355
11.1003
14.758
16.7705
20.871
23:717
25.0
33.0
35.3553
50.0
$3,900
66.0
70.7106
73.7902
75.0
93. 338
106.00 106.086
111 8138033
147 31.38844
167.705
20
Effective intervention ratio
Effective intervention ratio
(a) Simulation with 1000 variables
(b) Simulation with 2000 variables
Figure 5: Simulation and comparison between the two bounds and SORTRANKING, For each set- ting. we draw 2 graphs per setting, where setting is the tuple (Pime. Pe). Then, for each graph, we the algorithm
configurations, where each configuration corresponds a draw of the targeted variables following Pint- For both 5 and 30 variables, we have Pint E (0.25, 0.33, 0.5, 0.66, 0.75). In the 1000 variables setting on the left, we have Pe E (0.005, 0.002, 0.001). 3. In the 20000 variables settings on the right, have Pe E {0.0001, 0.00005, 0.00002). The settings are ordered on the x-axis following what we call the effective intervention ratio Pint Even though the objective can
be approximately solved at scale, we observe room for improvement as the performance of SOR- TRANKING is above the upper-bound many settings.
D top of Intersort for 30 variables
Upperbound Thm 4
20
Upperbound Thm 2
Worst selection
Random selection
10
selection
5
6059
1,278
Effective intervention ratio
Figure 6: Simulation of scale free networks with average edge per variable in (1,2,3) for 30 vari- ables. We report the performance of Intersort with various intervention selection policies. We evaluate three policies: selecting the 10 variables with the most children, selecting 10 variables random, and selecting the 10 variables with the fewest children. This corresponds to setting with 30% of intervened variables. We can thus hypothesize that a potential approach for intervention selection is to estimate the connectivity of the non -on-inner variables.
F.2 EMPIRICAL DATA
Results for the empirical evaluation for the smaller setting of 10 variables (fig. 7 Figure 8 shows the performance of SORTRANKING for 100 variables. in training time for the baselines the neural network data type.
the empirical difference
23

---

Published as a conference paper at ICLR 2025
Model Type
Model Type
EASE
DCDI
DCDI
20
GIES
Intersort
Intersort
0,500
D.500
15
10
20.0
50.0
70.0
100.0
20.0
50.0
70.0
100.0
Fraction of intervened variabless (%)
Fraction Intervened variables (%)
(a) Linear 10 variables
(h) RFF 10 variables
Model Type EASE
Model Type
EASE
PC
FC
20
DCDI
GIES
GIES
100
15
10
50.0 Froction variables intervened (%)
100.0
70.0
100.0
Fraction of intervened variables (%)
(c) NN 10 variables
(d) GRN 10 variables
Figure 7: Comparison the performance of the baselines and our model INTERSORT across diverse data domains as presented, for 10 variables. The x-axis corresponds to the fraction of vari- ables that have been targeted by an intervention. The y-axis the performance of causal ordering prediction measured by the Drop metric (see section
24

---

Published as a conference paper at ICLR 2025
Model Type SORTRANKING
80
Model Type
30
SORTRANKING
70
60
50
10
30
40
20
30
20
10
25.0
50.0
75.0
100.0
25.0
50.0
75.0
100.0
Fraction intervened variables
Fraction of intervened variables (9%
(a) Linear 100 variables
(b) RFF 100 variables
Model Type
Model Type
SORTRANKING
SORTRANKING
120
60
100
18
40
40
10
20
25.0
50.0
25.0
100.0
Froction variables intervened (%)
Fraction intervened variables 196)
(c) NN 100 variables
(d) GRN 100 variables
Figure 8: Performance our model SORTRANKING across diverse data domains as presented (linear, RFF, NN and GRN data), for 100 variables. The x-axis corresponds to the fraction of vari- ables that have been targeted by an intervention. The y-axis is the performance of causal ordering prediction measured by the Drop metric (see section
lower is better).
25

---

Published as a conference paper at ICLR 2025
Training Time for
Training Time for d (Grauped by Fraction)
(Grouped by Fraction)
Training Time (log scale. seconds)
Training Time (log Scale. secondsi
10a
Model EASE
Model
10
DCDI
10a-
GEE
PC
10'
DCDI
LASE
10y
10
10P
Fraction of Variabies Intervened 19))
Fraction Variabies Intervened
Training Time for d
10
(b) Training Time for
Relative Change in Training Time (d-30 d-10)
Reletive Change in Train Timr
10*
EASE
Intensort
GIES
10a
DCD1
40
60
80
100
Fraction of Variables intervened (%)
(c) Relative Change (d = 30 vs d = 10)
Figure 9: Training time analysis across different configurations for the NN data type. Plots (a) and (b) show the training time on logarithmic scale for d = 10 and d = 30, respectively. Plot (c) shows the relative change training time between 10 and d 30, also on logarithmic scale.
F.3 QUALITATIVE EXAMPLE ON REAL-WORLD DATA
PKC
PKA
P38
Jnk
Mck
Raf
PIP2
Pleg
PIP3
Figure 10: Output of Intersort on the flow cytometry data set of the Sachs et al. (2005) dataset, which measures the level of expression of phosphoproteins and phospholipids in human cells. Out of the 11 proteins, 5 (in red) where intervened on using reagents to activate or inhibit the measured pro- teins. The dataset comprises 5846 measurements, of which 1755 measurements and 4091 measurements are from the five different single node interventions. We here compare the predicted order of Intersort, using the Wasserstein distance and an epsilon value of 1.5, to the consensus true network consisting of 17 edges (Sachs et al. 2005). Intersort achieves Dtop of 3, where we color the edges the wrong direction in red.
observational,
G COMPUTATIONAL RESOURCES
The simulations of fig. I were run on an Apple MI Macbook pro. The experiments for figs. and were run on cluster with 20 CPUs, 16Gb of memory per CPU.
26


Reviews:
[{"review_id": "5GbnAwgIKo", "reviewer": "Reviewer_R6EY", "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.", "questions": "1. What are the main differences between the current work and (Tian and Pearl, 2013) in terms of faithfulness assumption and methodology?\n\n2. 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?\n\n3. In eq. (1), in the second term, why is there a coefficient of $d$?\n\n4. 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?\n\n5. 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.\n\n6. The pseudocode in Algorithm 1 is somehow useless. The most important parts (SORTRANKING and LOCACLSEARCH) are not described there.\n\n7. 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.\n\n8. What is the computational complexity of the proposed algorithm? It is also good to compare the algorithms in terms of runtime empirically.\n\n9. 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.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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. \n\nClarity: The paper is generally well-written.\n\nSignificant: 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. \n\nTheoretical 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). \n\nThe 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.\n\nTheoretical 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.", "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": "", "extra_scores": {}}, {"review_id": "bHNQzFFkPl", "reviewer": "Reviewer_WsAd", "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.", "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?\n2. 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?\n3. Could the authors elaborate on how the proposed framework could be extended to derive causal order over a subset of variables?\n4. Do the authors have any intuition on how this framework might be used to develop better causal discovery algorithms?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "* The paper introduces a new definition of faithfulness with both theoretical guarantees and empirical results.\n* It is well-written and clear.\n* Numerical experiments are designed in a sensible manner that adequately supports the claims.\n* 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.\n* Empirical experiments are conducted on a limited set of underlying models.", "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": "", "extra_scores": {}}, {"review_id": "yY5OzpEe0w", "reviewer": "Reviewer_PzaP", "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.", "questions": "Are there useful heuristics for choosing which variables to intervene on ($\\mathcal{I}$)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper presents an original solution to a significant problem: a method for directly learning the causal order using interventional data.\n * Although technically dense, the paper is surprisingly easy to read and well-organized.\n * The theoretical guarantees for optimality under a reasonable faithfulness assumption appear solid.\n * 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. \n * The main score objective (Equation 1) is difficult to understand and not explained much.\n\nMinor comments\n * Please define all the terms on like 152, like the noise variable $N_j$.", "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": "", "extra_scores": {}}, {"review_id": "Cbwn2XMxAU", "reviewer": "Reviewer_nPs4", "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.", "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?\n2. 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?\n3. In eq. (1), what does the second part mean? I scratch my head to understand it.\n4. 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.\n5. 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "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?\n2. 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?\n3. 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?\n4. 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.\n5. 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.", "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": "", "extra_scores": {}}, {"review_id": "yP4eOB02xV", "reviewer": "Reviewer_mrVM", "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.", "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?\n- How exactly is the algorithm implemented? E.g., which p-Wasserstein distance is chosen? Which algorithm is used to compute the distance?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is the first to estimate the causal order from interventional data\n- The paper contains several novel and theoretically grounded contributions, including the causal score as well as the algorithm to approximate it\n- Promising empirical results on simulated data", "weaknesses": "- As common in causal discovery, the method relies on generally untestable assumptions (e.g., epsilon interventional faithfulness)\n- The method relies on estimating distributional distances (e.g., Wasserstein distance) which can be statistically challenging\n- 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\n- The related work on causal discovery could be expanded\n\nMinor \n- Appendix B seems to be missing\n- There is some weird formatting on page 16 (Appendix C and D intersect)\n- 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", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)