Matching a Desired Causal State via Shift Interventions
Year: 2022

Abstract:
Transforming a causal system from a given initial state to a desired target state is an important task permeating multiple fields including control theory, biology, and materials science. In causal models, such transformations can be achieved by performing a set of interventions. In this paper, we consider the problem of identifying a shift intervention that matches the desired mean of a system through active learning. We define the Markov equivalence class that is identifiable from shift interventions and propose two active learning strategies that are guaranteed to exactly match a desired mean. We then derive a worst-case lower bound for the number of interventions required and show that these strategies are optimal for certain classes of graphs. In particular, we show that our strategies may require exponentially fewer interventions than the previously considered approaches, which optimize for structure learning in the underlying causal graph. In line with our theoretical results, we also demonstrate experimentally that our proposed active learning strategies require fewer interventions compared to several baselines.

heading: 1 Introduction
text: Consider an experimental biologist attempting to turn cells from one type into another, e.g., from fibroblasts to neurons (Vierbuchen et al., 2010), by altering gene expression. This is known as cellular reprogramming and has shown great promise in recent years for regenerative medicine (Rackham et al., 2016). A common approach is to model gene expression of a cell, which is governed by an underlying gene regulatory network, using a structural causal model (Friedman et al., 2000; Badsha et al., 2019). Through a set of interventions, such as gene knockouts or overexpression of transcription factors (Dominguez et al., 2016), a biologist can infer the structure of the underlying regulatory network. After inferring enough about this structure, a biologist can identify the intervention needed to successfully reprogram a cell. More generally, transforming a causal system from an initial state to a desired state through interventions is an important task pervading multiple applications. Other examples include closed-loop control (Touchette and Lloyd, 2004) and pathway design of microstructures (Wodo et al., 2015).
With little prior knowledge of the underlying causal model, this task is intrinsically difficult. Previous works have addressed the problem of intervention design to achieve full identifiability of the causal model (Hauser and Bühlmann, 2014; Greenewald et al., 2019; Squires et al., 2020a). However, since interventional experiments tend to be expensive in practice, one wishes to minimize the number of trials and learn just enough information about the causal model to be able to identify the intervention that will transform it into the desired state. Furthermore, in many realistic cases, the set
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
of interventions which can be performed is constrained. For instance, in CRISPR experiments, only a limited number of genes can be knocked out to keep the cell alive; or in robotics, a robot can only manipulate a certain number of arms at once.
Contributions. We take the first step towards the task of causal matching (formalized in Section 2), where an experimenter can perform a series of interventions in order to identify a matching intervention which transforms the system to a desired state. In particular, we consider the case where the goal is to match the mean of a distribution. We focus on a subclass of interventions called shift interventions, which can for example be used to model gene over-expression experiments (Triantafillou et al., 2017). These interventions directly increase or decrease the values of their perturbation targets, with their effect being propagated to variables which are downstream (in the underlying causal graph) of these targets. We show that there always exists a unique shift intervention (which may have multiple perturbation targets) that exactly transforms the mean of the variables into the desired mean (Lemma 1). We call this shift intervention the matching intervention.
To find the matching intervention, in Section 3 we characterize the Markov equivalence class of a causal graph induced by shift interventions, i.e., the edges in the causal graph that are identifiable from shift interventions; in particular, we show that the resulting Markov equivalence classes can be more refined than previous notions of interventional Markov equivalence classes. We then propose two active learning strategies in Section 4 based on this characterization, which are guaranteed to identify the matching intervention. These active strategies proceed in an adaptive manner, where each intervention is chosen based on all the information gathered so far.
In Section 5, we derive a worst-case lower bound on the number of interventions required to identify the matching intervention and show that the proposed strategies are optimal up to a logarithmic factor. Notably, the proposed strategies may use exponentially fewer interventions than previous active strategies for structure learning. Finally, in Section 6, we demonstrate also empirically that our proposed strategies outperform previous methods as well as other baselines in various settings.

heading: 1.1 Related Works
text: Experimental Design. Previous work on experimental design in causality has considered two closely related goals: learning the most structural information about the underlying DAG given a fixed budget of interventions (Ghassami et al., 2018), and fully identifying the underlying DAG while minimizing the total number or cost (Shanmugam et al., 2015; Kocaoglu et al., 2017) of interventions. These works can also be classified according to whether they consider a passive setting, i.e., the interventions are picked at a single point in time (Hyttinen et al., 2013; Shanmugam et al., 2015; Kocaoglu et al., 2017), or an active setting, i.e., interventions are decided based on the results of previous interventions (He and Geng, 2008; Agrawal et al., 2019; Greenewald et al., 2019; Squires et al., 2020a). The setting addressed in the current work is closest to the active, full-identification setting. The primary difference is that in order to match a desired mean, one does not require full identification; in fact, as we show in this work, we may require significantly less interventions.
Causal Bandits. Another related setting is the bandit problem in sequential decision making, where an agent aims to maximize the cumulative reward by selecting an arm at each time step. Previous works considered the setting where there are causal relations between regrets and arms (Lattimore et al., 2016; Lee and Bareinboim, 2018; Yabe et al., 2018). Using a known causal structure, these works were able to improve the dependence on the total number of arms compared to previous regret lower-bounds (Bubeck and Cesa-Bianchi, 2012; Lattimore et al., 2016). These results were further extended to the case when the causal structure is unknown a priori (de Kroon et al., 2020). In all these works the variables are discrete, with arms given by do-interventions (i.e., setting variables to a given value), so that there are only a finite number of arms. In our work, we are concerned with the continuous setting and shift interventions, which corresponds to an infinite (continuous) set of arms.
Correlation-based Approaches. There are also various correlation-based approaches for this task that do not make use of any causal information. For example, previous works have proposed scorebased (Cahan et al., 2014), entropy-based (D’Alessio et al., 2015) and distance-based approaches (Rackham et al., 2016) for cellular reprogramming. However, as shown in bandit settings (Lattimore et al., 2016), when the system follows a causal structure, this structure can be exploited to learn the optimal intervention more efficiently. Therefore, we here focus on developing a causal approach.

heading: 2 Problem Setup
text: We now formally introduce the causal matching problem of identifying an intervention to match the desired state in a causal system under a given metric. Following Koller and Friedman (2009), a causal structural model is given by a directed acyclic graph (DAG) G with nodes [p] = {1, . . . , p}, and a set of random variables X = {X1, ..., Xp} whose joint distribution P factorizes according to G. Denote by paG(i) = {j 2 [p] | j ! i} the parents of node i in G. An intervention I ⇢ [p] with multiple perturbation targets i 2 I either removes all incoming edges to Xi (hard intervention) or modifies the conditional probability P(Xi|XpaG(i)) (soft intervention) for all i 2 I . This results in an interventional distribution PI . Given a desired joint distribution Q over X , the goal of causal matching is to find an optimal matching intervention I such that PI best matches Q under some metric. In this paper, we address a special case of the causal matching problem, which we call causal mean matching, where the distance metric between PI and Q depends only on their expectations.
We focus on causal mean matching for a class of soft interventions, called shift interventions (Rothenhäusler et al., 2015). Formally, a shift intervention with perturbation targets I ⇢ [p] and shift values {ai}i2I modifies the conditional distribution as PI(Xi = x+ ai|XpaG(i)) = P(Xi = x|XpaG(i)). Here, the shift values {ai}i2I are assumed to be deterministic. We aim to find I ⇢ [p] and {ai}i2I 2 R|I| such that the mean of PI is closest to that of Q, i.e., minimizes d(EPI (X),EQ(X)) for some metric d. In fact, as we show in the following lemma, there always exists a unique shift intervention, which we call the matching intervention, that achieves exact mean matching.1
Lemma 1. For any causal structural model and desired mean EQ(X), there exists a unique shift intervention I⇤ such that EPI⇤ (X) = EQ(X).
We assume throughout that the underlying causal DAG G is unknown. But we assume causal sufficiency (Spirtes et al., 2000), which excludes the existence of latent confounders, as well as access to enough observational data to determine the joint distribution P and thus the Markov equivalence class of G (Andersson et al., 1997). It is well-known that with enough interventions, the causal DAG G becomes fully identifiable (Yang et al., 2018). Thus one strategy for causal mean matching is to first use interventions to fully identify the structure of G, and then solve for the matching intervention given full knowledge of the graph. However, in general this strategy requires more interventions than needed. In fact, the number of interventions required by such a strategy can be exponentially larger than the number of interventions required by a strategy that directly attempts to identify the matching intervention, as illustrated in Figure 1 and proven in Theorem 2.
In this work, we consider active intervention designs, where a series of interventions are chosen adaptively to learn the matching intervention. This means that the information obtained after performing each intervention is taken into account for future choices of interventions. We here focus on the noiseless setting, where for each intervention enough data is obtained to decide the effect of each intervention. Direct implications for the noisy setting are discussed in Appendix G. To incorporate realistic cases in which the system cannot withstand an intervention with too many target
1To lighten notation, we use I to denote both the perturbation targets and the shift values of this intervention.
variables, as is the case in CRISPR experiments, where knocking out too many genes at once often kills the cell, we consider the setting where there is a sparsity constraint S on the maximum number of perturbation targets in each intervention, i.e., we only allow I where |I|  S.

heading: 3 Identifiability
text: In this section, we characterize and provide a graphical representation of the shift interventional Markov equivalence class (shift-I-MEC), i.e., the equivalence class of DAGs that is identifiable by shift interventions I . We also introduce mean interventional faithfulness, an assumption that guarantees identifiability of the underlying DAG up to its shift-I-MEC. Proofs are given in Appendix C.

heading: 3.1 Shift-interventional Markov Equivalence Class
text: For any DAG G with nodes [p], a distribution f is Markov with respect to G if it factorizes according to f(X) = Q i2[p] f(Xi|XpaG(i)). Two DAGs are Markov equivalent or in the same Markov equivalence class (MEC) if any positive distribution f which is Markov with respect to (w.r.t.) one DAG is also Markov w.r.t. the other DAG. With observational data, a DAG is only identifiable up to its MEC (Andersson et al., 1997). However, the identifiability improves to a smaller class of DAGs with interventions. For a set of interventions I (not necessarily shift interventions), the pair (f, {f I}I2I) is I-Markov w.r.t. G if f is Markov w.r.t. G and f I factorizes according to
f I(X) =
Y
i/2I
f(Xi|XpaG(i)) Y
i2I f I(Xi|XpaG(i)), 8I 2 I.
Similarly, the interventional Markov equivalence class (I-MEC) of a DAG can be defined, and Yang et al. (2018) provided a structural characterization of the I-MEC for general interventions I (not necessarily shift interventions).
Following, we show that if I consists of shift interventions, then the I-MEC becomes smaller, i.e., identifiability of the causal DAG is improved. The proof utilizes Lemma 2 on the relationship between conditional probabilities. For this, denote by anG(i) the ancestors of node i, i.e., all nodes j for which there is a directed path from j to i in G. For a subset of nodes I , we say that i 2 I is a source w.r.t. I if anG(i) \ I = ?. A subset I 0 ⇢ I is a source w.r.t. I if every node in I 0 is a source w.r.t. I . Lemma 2. For any distribution f that factorizes according to G, the interventional distribution f I for a shift intervention I ⇢ [p] with shift values {ai}i2I satisfies
EfI (Xi) = Ef (Xi) + ai,
for any source i 2 I . Furthermore, if i 2 I is not a source w.r.t. I , then there exists a positive distribution f such that EfI (Xi) 6= Ef (Xi) + ai.
Hence, we can define the shift-I-Markov property and shift-interventional Markov equivalence class (shift-I-MEC) as follows. Definition 1. For a set of shift interventions I, the pair (f, {f I}I2I) is shift-I-Markov w.r.t. G if (f, {f I}I2I) is I-Markov w.r.t. G and
EfI (Xi) = Ef (Xi) + ai, 8 i 2 I 2 I s.t. anG(i) \ I = ?.
Two DAGs are in the same shift-I-MEC if any positive distribution that is shift-I-Markov w.r.t. one DAG is shift-I-Markov also w.r.t. the other DAG.
The following graphical characterizations are known: Two DAGs are in the same MEC if and only if they share the same skeleton (adjacencies) and v-structures (induced subgraphs i! j k), see Verma and Pearl (1991). For general interventions I, two DAGs are in the same I-MEC, if they are in the same MEC and they have the same directed edges {i! j|i 2 I, j /2 I, I 2 I, i j}, where i j means that either i ! j or j ! i (Hauser and Bühlmann, 2012; Yang et al., 2018). In the following theorem, we provide a graphical criterion for two DAGs to be in the same shift-I-MEC. Theorem 1. Let I be a set of shift interventions. Then two DAGs G1 and G2 belong to the same shift-I-MEC if and only if they have the same skeleton, v-structures, directed edges {i! j|i 2 I, j /2 I, I 2 I, i j}, as well as source nodes of I for every I 2 I.
In other words, two DAGs are in the same shift-I-MEC if and only if they are in the same I-MEC and they have the same source perturbation targets. Figure 2 shows an example; in particular, to represent an MEC, we use the essential graph (EG), which has the same skeleton as any DAG in this class and directed edges i ! j if i ! j for every DAG in this class. The essential graphs corresponding to the MEC, I-MEC and shift-I-MEC of a DAG G are referred to as EG, I-EG and shift-I-EG of G, respectively. They can be obtained from the aforementioned graphical criteria (along with a set of logical rules known as the Meek rules (Meek, 1995); see details in Appendix A). Figure 2 shows an example of EG, I-EG and shift-I-EG of a four-node DAG.

heading: 3.2 Mean Interventional Faithfulness
text: For the causal mean matching problem, the underlying G can be identified from shift interventions I up to its shift-I-MEC. However, we may not need to identify the entire DAG to find the matching intervention I⇤. Lemma 1 implies that if i is neither in nor downstream of I⇤, then the mean of Xi already matches the desired state, i.e., EP(Xi) = EQ(Xi); this suggest that these variables may be negligible when learning I⇤. Unfortunately, the reverse is not true; one may design “degenerate" settings where a variable is in (or downstream of) I⇤, but its marginal mean is also unchanged:
Example 1. Let X3 = X1 + 2X2, with EP(X1) = 1 and EP(X2) = 1, so that EP(X3) = 3. Suppose I⇤ is a shift intervention with perturbation targets {X1, X2, X3}, with a1 = 1, a2 = 1, and a3 = 1. Then EPI (X3) = 3, i.e., the marginal mean of X3 is unchanged under the intervention.
Such degenerate cases arise when the shift on a node Xj (deemed 0 if not shifted) exactly cancels out the contributions of shifts on its ancestors. Formally, the following assumption rules out these cases.
Assumption 1 (Mean Interventional Faithfulness). If i 2 [p] satisfies EP(Xi) = EQ(Xi), then i is neither a nor downstream of any perturbation target, i.e., i /2 I⇤, anG(i) \ I⇤ = ?.
This is a particularly weak form of faithfulness, which is implied by interventional faithfulness assumptions in prior work (Yang et al., 2018; Squires et al., 2020b; Jaber et al., 2020).
Let T be the collection of nodes i 2 [p] for which EP(Xi) 6= EQ(Xi). The following lemma shows that under the mean interventional faithfulness assumption we can focus on the subgraph GT induced by T , since I⇤ ⇢ T and interventions on XT do not affect X[p]\T .
Lemma 3. If Assumption 1 holds, then any edge i j with j 2 T and i /2 T has orientation j i. Conversely, if Assumption 1 does not hold, then there exists some i j, j 2 T , i 62 T such that j ! i.

heading: 4 Algorithms
text: Having shown that shift interventions allow the identification of source perturbation targets and that the mean interventional faithfulness assumption allows reducing the problem to an induced subgraph, we now propose two algorithms to learn the matching intervention. The algorithms actively pick a shift intervention It at time t based on the current shift-interventional essential graph (shift-ItEG). Without loss of generality and for ease of discussion, we assume that the mean interventional faithfulness assumption holds and we therefore only need to consider GT . In Appendix D, we show that the faithfulness violations can be identified and thus Assumption 1 is not necessary for identifying the matching intervention, but additional interventions may be required.
Warm-up: Upstream Search. Consider solving for the matching intervention I⇤ when the structure of GT is known, i.e., the current shift-It-EG is fully directed. Let UT = {i|i 2 T, anGT (i)\T = ?} be the non-empty set of source nodes in T . We make the following key observation. Observation 1. UT ⇢ I⇤, and the shift values are ai = EQ(Xi) EP(Xi) for each i 2 UT .
This follows since shifting other variables in T cannot change the mean of nodes in UT . Further, the shifted means of variables in UT match the desired mean (Lemma 2). Given the resulting intervention UT , we obtain a new distribution PUT . Assuming mean interventional faithfulness on this distribution, we may now remove those variables whose means in PUT already match Q. We then repeat this process on the new set of unmatched source nodes, T1, to compute the corresponding shift intervention UT1 . Repeating until we have matched the desired mean for all variables yields I⇤. We illustrate this procedure in Figure 3.
The idea of upstream search extends to shift-It-EG with partially directed or undirected GT . In this case, if a node or nodes of GT are identified as source, Observation 1 still holds. Hence, we solve a part of I⇤ with these source nodes and then intervene on them to reduce the unsolved graph size.
Decomposition of Shift Interventional Essential Graphs: In order to find the source nodes, we decompose the current shift-It-EG into undirected components. Hauser and Bühlmann (2014) showed that every interventional essential graph is a chain graph with chordal chain components, where the orientations in one chain component do not affect the orientations in other components.2 By a similar argument, we can obtain an analogous decomposition for shift interventional essential graphs, and show that there is at least one chain component with no incoming edges. Let us separate out all of the chain components of shift-It-EG with no incoming edges. The following lemma proves that all sources are contained within these components. Lemma 4. For any shift-I-EG of G, each chain component has exactly one source node w.r.t. this component. This node is a source w.r.t. G if and only if there are no incoming edges to this component.
These results hold when replacing G with any induced subgraph of it. Thus, we can find the source nodes in T by finding the source nodes in each of its chain components with no incoming edges.

heading: 4.1 Two Approximate Strategies
text: Following the chain graph decomposition, we now focus on how to find the source node of an undirected connected chordal graph C. If there is no sparsity constraint on the number of perturbation targets in each shift intervention, then directly intervening on all of the variables in C gives the source node, since by Theorem 1, all DAGs in the shift-I-MEC share the same source node. However, when the maximum number of perturbation targets in an intervention is restricted to S < |C|, multiple interventions may be necessary to find the source node.
After intervening on S nodes, the remaining unoriented part can be decomposed into connected components. In the worst case, the source node of C is in the largest of these connected components. Therefore we seek the set of nodes, within the sparsity constraint, that minimizes the largest connected component size after being removed. This is known as the MinMaxC problem (Lalou et al., 2018), which we show is NP-complete on chordal graphs (Appendix D). We propose two approximate
2The chain components of a chain graph are the undirected connected components after removing all its directed edges, and an undirected graph is chordal if all cycles of length greater than 3 contain a chord.
Algorithm 1: Active Learning for Causal Mean Matching Input: Joint distribution P, desired joint distribution Q, sparsity constraint S.
1 Initialize I⇤ = ? and I = {?}; 2 while EPI⇤ (X) 6= EQ(X) do 3 let T = {i|i 2 [p],EPI⇤ (Xi) 6= EQ(Xi)}; 4 let G be the subgraph of shift-I-EG induced by T ; 5 let UT be the identified source nodes in T ; 6 while UT = ? do 7 let C be a chain component of G with no incoming edges; 8 select shift intervention I by running CliqueTree(C, S) or Supermodular(C, S); 9 perform I and append it to I;
10 update G and UT as the outer loop; 11 end 12 set ai = EQ(Xi) EPI⇤ (Xi) for i in UT ; 13 include perturbation targets UT and shift values {ai}i2UT in I⇤ and perform I⇤; 14 end
Output: Matching Intervention I⇤
strategies to solve this problem, one based on the clique tree representation of chordal graphs and the other based on robust supermodular optimization. The overall algorithm with these subroutines is summarized in Algorithm 1. We outline the subroutines here, and give further details in Appendix D.
Clique Tree Strategy. Let C(C) be the set of maximal cliques in the chordal graph C. There exists a clique tree T (C) with nodes in C(C) and edges satisfying that 8C1, C2 2 C(C), their intersection C1 \ C2 is a subset of any clique on the unique path between C1, C2 in T (C) (Blair and Peyton, 1993). Thus, deleting a clique which is not a leaf node in the clique tree will break C into at least two connected components, each corresponding to a subtree in the clique tree. Inspired by the central node algorithm (Greenewald et al., 2019; Squires et al., 2020a), we find the S-constrained central clique of T (C) by iterating through C(C) and returning the clique with no more than S nodes that separates the graph most, i.e., solving MinMaxC when interventions are constrained to be maximal cliques. We denote this approach as CliqueTree.
Supermodular Strategy. Our second approach, denoted Supermodular, optimizes a lower bound of the objective of MinMaxC. Consider the following equivalent formulation of MinMaxC
min A⇢VC max i2VC fi(A), |A|  S, (1)
where VC represents the nodes of C and 8 i 2 VC , fi(A) = P
j2VC gi,j(A) with gi,j(A) = 1 if i and j are the same or connected after removing nodes in A from C and gi,j(A) = 0 otherwise. MinMaxC (1) resembles the problem of robust supermodular optimization (Krause et al., 2008). Unfortunately, fi is not supermodular for chordal graphs (Appendix D). Therefore, we propose to optimize for a surrogate of fi defined as f̂i(A) = P j2C ĝi,j(A), where
ĝi,j(A) =
( mi,j(VC A) mi,j(VC)
, i j in C, 0, otherwise.
(2)
Here mi,j(VC0) is the number of paths without cycles between i and j in C0 (deemed 0 if i or j does not belong to C0 and 1 if i = j 2 C0) and i j means i is either connected or equal to j. Comparing ĝi,j with gi,j , we see that f̂i(A) is a lower bound of fi(A) for MinMaxC, which is tight when C is a tree. We show that f̂i is monotonic supermodular for all i (Appendix D). Therefore, we consider (2) with fi replaced by f̂i, which can be solved using the SATURATE algorithm (Krause et al., 2008). Notably, the results returned by Supermodular can be quite different to those returned by CliqueTree since Supermodular is not constrained to pick a maximal clique; see Figure 4.

heading: 5 Theoretical Results
text: In this section we derive a worst-case lower bound on the number of interventions for any algorithm to identify the source node in a chordal graph. Then we use this lower bound to show that our
strategies are optimal up to a logarithmic factor. This contrasts with the structure learning strategy, which may require exponentially more interventions than our strategy (Figure 1).
The worst case is with respect to all feasible orientations of an essential graph (Hauser and Bühlmann, 2014; Shanmugam et al., 2015), i.e., orientations corresponding to DAGs in the equivalence class. Given a chordal chain component C of G, let rC be the number of maximal cliques in C, and mC be the size of the largest maximal clique in C. The following lemma provides a lower bound depending only on mC . Lemma 5. In the worst case over feasible orientations of C, any algorithm requires at least dmC 1S e shift interventions to identify the source node, under the sparsity constraint S.
To give some intuition for this result, consider the case where the largest maximal clique is upstream of all other maximal cliques. Given such an ordering, in the worst case, each intervention rules out only S nodes in this clique (namely, the most downstream ones). Now, we show that our two strategies need at most dlog2(rC + 1)e · dmC 1S e shift interventions for the same task. Lemma 6. In the worst case over feasible orientations of C, both CliqueTree and Supermodular require at most dlog2(rC + 1)e · dmC 1S e shift interventions to identify the source node, under the sparsity constraint S.
By combining Lemma 5 and Lemma 6, which consider subproblems of the causal mean matching problem, we obtain a bound on the number of shift interventions needed for solving the full causal mean matching problem. Let r be the largest rC for all chain components C of G: Theorem 2. Algorithm 1 requires at most dlog2(r + 1)e times more shift interventions, compared to that required by the optimal strategy, in the worst case over feasible orientations of G.
A direct application of this theorem is that, in terms of the number of interventions required to solve the causal mean matching problem, our algorithm is optimal in the worst case when r = 1, i.e., when every chain component is a clique. All proofs are provided in Appendix E.

heading: 6 Experiments
text: We now evaluate our algorithms in several synthetic settings.3 Each setting considers a particular graph type, number of nodes p in the graph and number of perturbation targets |I⇤|  p in the matching intervention. We generate 100 problem instances in each setting. Every problem instance contains a DAG with p nodes generated according to the graph type and a randomly sampled subset of |I⇤| nodes denoting the perturbation targets in the matching intervention. We consider both, random graphs including Erdös-Rényi graphs (Erdős and Rényi, 1960) and Barabási–Albert graphs (Albert and Barabási, 2002), as well as structured chordal graphs, in particular, rooted tree graphs and moralized Erdös-Rényi graphs (Shanmugam et al., 2015). The graph size p in our simulations ranges from 10 to 1000, while the number of perturbation targets ranges from 1 to min{p, 100}. We compare our two subroutines for Algorithm 1, CliqueTree and Supermodular, against three carefully constructed baselines. The UpstreamRand baseline follows Algorithm 1 where line 8 is changed to selecting I randomly from C without exceeding S, i.e., when there is no identified source
3Code is publicly available at: https://github.com/uhlerlab/causal_mean_matching.
node it randomly samples from the chain component with no incoming edge. This strategy highlights how much benefit is obtained from CliqueTree and Supermodular on top of upstream search. The Coloring baseline is modified from the coloring-based policy for structure learning (Shanmugam et al., 2015), previously shown to perform competitively on large graphs (Squires et al., 2020a). It first performs structure learning with the coloring-based policy, and then uses upstream search with known DAG. We also include an Oracle baseline, which does upstream search with known DAG.
In Figure 5 we present a subset of our results on Barabási–Albert graphs with 100 nodes; similar behaviors are observed in all other settings and shown in Appendix F. In Figure 5a, we consider problem instances with varying size of |I⇤|. Each algorithm is run with sparsity constraint S = 1. We plot the number of extra interventions compared to Oracle, averaged across the 100 problem instances. As expected, Coloring requires the largest number of extra interventions. This finding is consistent among different numbers of perturbation targets, since the same amount of interventions are used to learn the structure regardless of I⇤. As |I⇤| increases, CliqueTree and Supermodular outperform UpstreamRand. To further investigate this trend, we plot the rate of extra interventions4 used by CliqueTree and Supermodular relative to UpstreamRand in Figure 5b. This figure shows that CliqueTree and Supermodular improve upon upstream search by up to 25% as the number of perturbation targets increases. Finally, we consider the effect of the sparsity constraint S in Figure 5c with |I⇤| = 50. In line with the discussion in Section 4.1, as S increases, the task becomes easier for plain upstream search. However, when the number of perturbation targets is restricted, CliqueTree and Supermodular are superior, with Supermodular performing best in most cases.

heading: 7 Discussion
text: In this work, we introduced the causal mean matching problem, which has important applications in medicine and engineering. We aimed to develop active learning approaches for identifying the matching intervention using shift interventions. Towards this end, we characterized the shift interventional Markov equivalence class and showed that it is in general more refined than previously defined equivalence classes. We proposed two strategies for learning the matching intervention based on this characterization, and showed that they are optimal up to a logarithmic factor. We reported experimental results on a range of settings to support these theoretical findings.
Limitations and Future Work. This work has various limitations that may be interesting to address in future work. First, we focus on the task of matching a desired mean, rather than an entire distribution. This is an inherent limitation of deterministic shift interventions: as noted by Hyttinen et al. (2012), in the linear Gaussian setting, these interventions can only modify the mean of the initial distribution. Thus, matching the entire distribution, or other relevant statistics, will require broader classes of interventions. Assumptions on the desired distribution are also required to rule out possibly non-realizable cases. Second, we have focused on causal DAG models, which assume acyclicity and the absence of latent confounders. In many realistic applications, this could be an overly optimistic assumption, requiring extensions of our results to the cyclic and/or causally insufficient setting.
4The rate is calculated by (#Strategy-#UpstreamRand)/#UpstreamRandwhere # denotes the number of extra interventions compared to Oracle and Strategy can be CliqueTree, Supermodular or UpstreamRand.
Finally, throughout the main text, we have focused on the noiseless setting; we briefly discuss the noisy setting in Appendix G, but there is much room for more extensive investigations.

heading: Acknowledgements
text: C. Squires was partially supported by an NSF Graduate Fellowship. All authors were partially supported by NSF (DMS-1651995), ONR (N00014-17- 1-2147 and N00014-18-1-2765), the MITIBM Watson AI Lab, and a Simons Investigator Award to C. Uhler.

Review summaries:
This paper considers the problem of identifying a shift intervention to match a given joint distribution of a causal model to a desired joint distribution at the expectation level. It defines the causal mean matching criteria, shows the existence of shift interventions for matching the desired means, and characterizes the shift-interventional Markov equivalence class (shift-I-MEC), which is a more refined subclass of interventional MEC (I-MEC). This refinement is due to the interventions being a certain type of soft interventions, that is the shift interventions.  Following a chain graph decomposition of the interventional essential graph, clique tree and supermodular optimization approaches are proposed for active learning of the matching intervention for causal mean matching. A lower bound for the number of shift-interventions and upper bound for the proposed algorithms are provided. Importantly, the upper bound is a logarithmic factor of the lower bound. Proposed approach is compared to random search and structure learning based baselines in simulations with synthetic data. 

This submission considers the problem of choosing a set of continuous shift interventions to match a desired mean when causal graph structure is unknown. The authors present theoretical results relating shift interventional Markov equivalence classes standard Markov equivalence classes, and use this theory to develop a new online algorithm for causal graph structure learning. They present synthetic experiments demonstrating that the proposed methods require few interventions relative to other structure learning baselines.

This paper studies shift interventions, where interventions are performed by biasing the respective nodes. It is shown that to move a system to the desired state, it is sufficient to know the topological ordering of the causal graph. Active learning strategies are proposed for transforming the current state of a system to a desired state in as few interventions as possible. Worst case bounds are provided and compared to lower bounds.