Characterization and Learning of Causal Graphs from Hard Interventions

We thank the reviewer for the encouraging assessment and the detailed, constructive questions.

Limitation on the current algorithm

The learning algorithm we proposed is incomplete and requires the knowledge of the intervention targets. We leave these problems as future extensions. The algorithm can be expensive in runtime when the graph is large. Some techniques to speed up FCI (for example [1]) transfer directly to our algorithm..

Lack of visualizations in the main text

Due to the page limitation, we have to move the figures of examples with detailed explanation to the appendix. We will put some of them in the main text for the revision to better convey the concepts. Specifically, we will move Figure 1 in App. D on a detailed example of how to construct the twin augmented MAGs from the ADMGs to Section 4. We will also move Figure 2 in App. E on a detailed example of how to construct an $\mathcal{I}$-augmented MAG by combining the twin augmented MAGs and how it preserves the desired separations, to Section 5.

Clarification on hard interventions

The results are still valid for stochastic hard interventions. In deterministic interventions there is no randomness left in $X$, so conditioning on $X$ is harmless. In stochastic interventions $X$ does carry randomness, and putting it in the conditioning set may open collider paths (or block active paths), changing the independence structure. Therefore, the intervention target being in the conditioning set in d-separation statements should not be done if it is stochastic. We do that because there is no randomness left in the node to establish dependencies.

Necessity of augmented pair graphs

We start by introducing the generalized do-calculus rules under hard interventions. The rules map testable distributional invariances into graphical constraints which can be used for discovery. The augmented pair graph shows how these invariance statements are preserved when we are comparing two domains, especially for those statements across domains. Based on the augmented pair graphs, we further construct twin augmented MAGs and then put them together in a domain-centric $\mathcal{I}$-augmented MAG as the ultimate graphical representation. The $\mathcal{I}$-MAG in [3] integrates all domains into one graph. This is not applicable for soft interventions that does not modify the original causal graph. In our case, since hard interventions will modify the graphs, we have to use the domain-centric graphs to capture different graph skeletons in different domains. Therefore, while the $\mathcal{I}$-augmented MAGs are the ultimate graphical representation we use to characterize the equivalence class, the augmented pair graph is the first step of the construction of $\mathcal{I}$-augmented MAGs which differs from the case in [3] as the invariances statements under soft interventions can be preserved in one graph. This can also be seen from the set of do-calculus rules under soft interventions ([2]) which differs from the rules under hard interventions.

Experiments on learning small graphs

The experiments are focusing on empirically compare the size of $\mathcal{I}$-MEC under hard and soft interventions to show that hard interventions are, in general, more powerful than soft interventions in learning the causal graphs. The reason we did not compare with other methods that allows interventional data is that the output types vary and there is no unified global accuracy metrics that can measure the performance. For our learning algorithm, it returns a set of $\mathcal{I}$-augmented graphs, which represents a set of ADMGs. To witness, given an ADMG, we can construct the twin augmented MAGs and further $\mathcal{I}$-augmented MAGs following the steps in Def. 4.5 and Def 5.1. If the oriented arrowheads or arrowtails align with $\mathcal{I}$-augmented MAGs, this ADMG is entailed by the algorithm's outputs.

I-FCI [3] (this is named by some follow-ups) or $\psi$-FCI [4] returns a single augmented graph called I-PAG. Our experiments in App. G implicitly shows that Algorithm 1 performs better than them given that Algorithm 1's outputs entail a smaller size of $\mathcal{I}$-Markov equivalent ADMGs. Other interventional causal discovery methods aim at returning one single graph. Such methods (for example, [6], [7]) often impose parametric assumptions on the SEMs like linear causal model or additive Gaussian noise and so on. Such methods degrade sharply when the assumptions do not hold. Additionally, they are not compatible with latents. Their output graph is not guaranteed to fall into the $\mathcal{I}$-MEC either. Due to the various output types, we did not compare the performance of Algorithm 1 with other methods. We will add some small scale experiments to show how our learning algorithm works in the revision.

Faithfulness assumption

We recognize that there are weaker faithfulness assumptions. However, the soundness of Algorithm 1 requires h-faithfulness. The $\mathcal{I}$-MEC we defined is based on the generalized do-calculus rules and so as the learning algorithm and hence h-faithfulness is minimal for the algorithm to be sound.

Like classic faithfulness, the set of parameterizations that violate h-faithfulness has Lebesgue measure zero for standard SEM families with continuous noise if we consider linear models; i.e., it holds generically [5] (it also holds for many other models, see follow-ups of [5]). It is therefore no stronger in a measure–theoretic sense than ordinary faithfulness, but it is stronger logically: it rules out a few additional, finely-tuned parameter combinations that would create the extra cancellations specific to our Rules 1-4—those cancellations correspond exactly to our new Rules 1–4, so dropping h-faithfulness would break soundness. We can also put it this way. Imagine a causal graph under faithfulness assumption. It could be the case that for certain conditioning values $Z=z$, two variables $X$ and $Y$ that are d-connected are independent. While faithfulness covers the case that $X$ is dependent with $Y$ given $Z$ (when the dependency metric is averaged over all $z$), h-faithfulness is similar to saying $X, Y$ are dependent given every $Z=z$. This analogy is exact if the intervened node is a source node, but we believe it gives some insight on the leap from observational faithfulness to h-faithfulness

Name of MEC

We will adopt a clearer term like $\mathcal{I}$-Hard-MEC and mention its relation to prior “MEC” work in the revision.

Soft intervention remark

We will correct the sentence to: “A typical soft intervention leaves the graph unchanged, but special cases (e.g., edge deletion) are possible; our results do not rely on such deletions.”

Again, thank you for the positive evaluation and the helpful suggestions. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.

References:

[1] Colombo, Diego, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson. "Learning high-dimensional directed acyclic graphs with latent and selection variables." The Annals of Statistics (2012): 294-321.

[2] Correa, Juan, and Elias Bareinboim. "A calculus for stochastic interventions: Causal effect identification and surrogate experiments." In Proceedings of the AAAI conference on artificial intelligence, vol. 34, no. 06, pp. 10093-10100. 2020.

[3] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. "Characterization and learning of causal graphs with latent variables from soft interventions." Advances in neural information processing systems 32 (2019).

[4] Jaber, Amin, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. "Causal discovery from soft interventions with unknown targets: Characterization and learning." Advances in neural information processing systems 33 (2020): 9551-9561.

[5] Robins, James M., Richard Scheines, Peter Spirtes, and Larry Wasserman. "Uniform consistency in causal inference." Biometrika 90, no. 3 (2003): 491-515.

[6] Hauser, A. & Bühlmann, P. “Characterization and Greedy Learning of Interventional Markov Equivalence Classes of DAGs.” JMLR 13: 2409 – 2464, 2012.

[7] Wang, Y., Solus, L., Yang, K. & Uhler, C. “Permutation-based Causal Inference Algorithms with Interventions.” NeurIPS 2017.

We thank the reviewer for the helpful comments and apologize for the parts that were hard to follow.

Clarification of the main paper

We agree the exposition can be improved. Due to the page limitation, we had to move some figures that illustrate the concepts to the appendix which made the main text less readable. In the revision we will: 1) move Figure 1 in App. D to Section 4 to illustrate the construction of twin-augmented MAG and highlighting the extra edge that captures the hard-intervention constraints; 2) move Figure 2 to Section 5 to show how we construct $\mathcal{I}$-augmented MAGs by combining twin-augmented MAGs. A short narrative paragraph will precede each theorem to walk the reader through the intuition before the formal statement. We conclude the main idea of this paper below.

Background and our contribution:

Learning a causal graph from multiple hard-intervention distributions has two pillars:

(i) do-calculus, which maps cross-environment invariance statements to graphical separations;

(ii) equivalence-class characterizations, which say exactly what can be learned from those invariances.

For observational data this yields the well-known Markov Equivalence Class (MEC).

For interventional data, Hauser & Bühlmann [1] extended the idea to the I-MEC, but only for observed DAGs with no latents; later work (Yang et al. [2]) unified hard/soft interventions in the same fully-observed setting, and Kocaoglu ’19 [3] handled soft interventions with latent variables via an augmented MAG.

Our paper closes the remaining gap: hard interventions with latents.

Because a hard cut severs every parent of the target, its effect can be global (the dependencies between non-adjacent nodes can be affected) when hidden confounders exist (see example in Line 48). Such surgical property provides us with more testable conditional independence statements and which therefore, the augmented MAG structure in [3] fails in our setting.

We therefore:

1. Generalize do-calculus (Rules 1–4) under hard interventions (Prop. 3.2) and define h-faithfulness (Def. 6.1) accordingly as the assumption for the learning algorithm. The generalized do-calculus rules map the testable invariances between hard-interventional distributions to the graphical constraints on the (mutilated) graphs.

2. Build the augmented pair graph (Def. 4.3) and further, the twin-augmented MAG (TAM) (Def. 4.5) (Figure 1 in App. D shows a detailed example of how we construct TAMs from the original ADMGs through augmented pair graphs), which preserves all testable invariances without mutilating the original ADMG.

3. Prove Thm 4.7: a complete graphical characterisation of the $\mathcal{I}$-MEC based on the graphical structures of the TAMs—the first such result for hard interventions under latents.

4. Compress the TAMs that contain the same interventional domain into a single, lean $\mathcal{I}$-augmented MAG (Def 5.1) (Figure 2 in App. E shows a detailed example of how we construct the $\mathcal{I}$-augmented MAGs). The $\mathcal{I}$-augmented MAGs are more compact and preserve all the testable separation statements. The union graph of all the $\mathcal{I}$-Markov equivalent $\mathcal{I}$-augmented MAGs forms the $\mathcal{I}$-essential graphs (Def. B.8) which become the ultimate target of our discovery procedure.

5. Derive Algorithm 1, an FCI-style learner that outputs a tuple of $\mathcal{I}$-augmented graphs (which represents a set of valid ADMGs) using FCI orientation rules together with additional, sound orientation rules (example walk-through in App. F, Figure 3).

Together, these steps establish what is fundamentally learnable under hard interventions and provide a learning algorithm to achieve it. We will improve the main text, especially introduction and related works accordingly, to improve readability.

No comparison with other interventional methods

Unlike most causal discovery algorithms, the goal of our algorithm is not to return a single causal graph but a tuple of $\mathcal{I}$-augmented graphs that entail $\mathcal{I}$-Markov equivalent graphs; none of the listed algorithms outputs that object. Concretely, I-FCI [3] (known targets)/$\psi$-FCI [4] (unknown targets) assume soft interventions and cannot exploit the additional invariance constraints; applying them to our setting recovers a larger MEC (App. G). They use a single augmented MAG as the learning objective. JCI claims it works for any interventions but it's overly simplistic; the learned PAG is less informative (in [4] App. D shows that $\psi$-FCI can learn more than JCI). GIES, IGSP are score-based and aim at learning a single DAG under known targets; they neither guarantee inclusion-minimality nor provide equivalence-class certificates. Nevertheless, scores-based methods usually impose parametric assumptions like linear function or additive Gaussian noise to the causal models. Such methods are not robust when the underlying mechanism deviates from those assumptions. Additionally, GIES and IGSP assume no latents and therefore cannot return ADMGs. Because the outputs are of different types, a direct performance metric is unavailable to measure the performance of the methods; instead we reported a size comparison (Table 2) that quantifies empirically how much smaller the $\mathcal{I}$-MEC is vs. the soft $\mathcal{I}$-MEC produced by I-FCI/$\psi$-FCI. To compare with GIES and IGSP, we use the graph $[X\rightarrow Z \rightarrow Y, Z\leftarrow L \rightarrow Y]$ where $L$ is a latent variable. We take 100k samples from observational distribution and 100k samples from $P_Z$. For the setting where $X, Y, Z$ are binary, we generate a random CPT based on the true graph and sample from it. GIES returns $[Y\rightarrow Z \rightarrow X]$ which is completely wrong. IGSP returns $[X\rightarrow Z \rightarrow Y, X\rightarrow Y]$ which is the observational MAG of the true graph, but it cannot tell anything to judge if there is a latent confounder between $Z, Y$. Under the same setting, when the simulated dataset is from a linear Gaussian SEM, both GIES and IGSP outputs $[X\rightarrow Z \rightarrow Y]$ which catches the right causal ordering but still is wrong and does not belong to the MEC. In both settings, our algorithm is able to learn the graphs illustrated in Figure 3 (k) which preserve information from both domains. We use the python implementation of GIES by Olga Kolotuhina and Juan L. Gamella. The IGSP implementation is from the causaldag package.

We will make this distinction explicit in an extra sub section in App. G with the detailed experiment settings. We will also add the small scale experiments to compare the outputs of each method in the revision.

Meaning of “tuple of hard-interventional distributions”

Let $\mathcal{I} = \lbrace \mathbf{I}\_1, \ldots, \mathbf{I}\_m \rbrace$ be the set of intervention targets. The “tuple” is the collection $(P^{(1)}, \ldots, P^{(m)})$ where $P^{(j)}$ is the interventional distribution under the intervention target $\mathbf{I}\_j$. Proposition 3.2 is a generalization of Theorem 3.1. More specifically, Theorem 3.1 tells under what graphical constraints one can adjust the intervention or conditioning set from a given distribution. Proposition 3.2 generalizes the rules to any pair of arbitrary interventional distributions ($P_{\mathbf{I}}$ and $P_{\mathbf{J}}$ in the main paper). It is saying that for any pair of interventional distributions, the invariance statements hold under the corresponding graphical constraints. The new set of rules make the comparisons of testable invariances explicit.

Once again, thank you for the detailed feedback. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.

References:

[1] Hauser, Alain, and Peter Bühlmann. "Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs." The Journal of Machine Learning Research 13, no. 1 (2012): 2409-2464.

[2] Yang, Karren, 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.

[3] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. "Characterization and learning of causal graphs with latent variables from soft interventions." Advances in neural information processing systems 32 (2019).

[4] Jaber, Amin, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. "Causal discovery from soft interventions with unknown targets: Characterization and learning." Advances in neural information processing systems 33 (2020): 9551-9561.

Thank you for the thoughtful assessment and the detailed style notes.

Novelty based on existing machineries

Prior augmented-graph formalisms ([1], [2], [6], [7]) cover soft interventions only or assume no latents. Hard interventions add the surgical constraint “no incoming edges”, which induces new cross-environment distributional invariances (Proposition 3.2) that cannot be captured by those graphs. Nevertheless, the presence of latents would create non-local dependencies and can be affected by hard interventions on remote nodes. Our twin augmented MAG (TAM) embeds these additional constraints via the $F$ node edges and is thus more expressive than prior augmented graphs. This extension is what allows us to prove the first graphical characterisation of an $\mathcal{I}$-MEC under hard interventions with latents —- a result that did not exist.

Additional related works

Both papers assume the graph is known and derive algebraic constraints to decide the identifiability of parameters (if interventional distributions can be computed from the observational distribution) (Kivva [4]) or a minimum intervention cover (Kandasamy [5]). Our setting is like the inverse problem: our Twin-Augmented MAG translates cross-environment distributional invariance statements into d-separations without assuming the graph. These invariances are then used to (i) characterise the $\mathcal{I}$-MEC (Thm 4.7) with a compact graphical representation and (ii) drive Algorithm 1 for structure learning based on the graphical constraints corresponding to the invariances. Thus the two lines of work are complementary: one answers ‘Which causal effects are computable if the graph is known?’; the other answers ‘Which graphs are compatible with the data across multiple hard-intervention settings?’ We will include these additional related works and add this contrast at the end of Section 2.

Positivity assumption for the learning algorithm

In theory, Algorithm 1 does not require a strict global positivity assumption. All results rely solely on h-faithfulness. We are aware that “strictly positive distribution” is added in some works on discovery as a convenience. This is because within the space of strictly positive parameterisations the subset that violates Faithfulness sits on algebraic varieties of lower dimension—hence has Lebesgue measure 0 (see [3] and many follow-ups). In practice, with finite data, a zero or near-zero cell makes test statistics undefined or unstable, so implementations often impose minimum-count rules even when the theory would allow the zero.

We notice that the positivity assumption is required for identifiability (For example, [4], [5]). This is because that the manipulation of numerical expression explicitly require the denominator to be strictly positive. By contrast, structural discovery uses only qualitative independence relations. As long as we can evaluate a test where $P(S)>0$, no global support assumption is required.

Style/Notation issues

We will systematic­ally reorder definitions so every concept precedes first use for bidirected edge, inducing path, ancestor, and almost directed cycle. We will also fix any typos in the revision.

For the conditioning set in Rule 2, Line 179, we add $Z$ explicitly due to its clear connection with the corresponding $F$ node d-separation statements, which require conditioning although it is not necessary. We will add a clarifying comment in the revised manuscript.

In line 197/199, we will take the suggestion to add $P_{ \mathbf{I} \cup \mathbf{J} }(\mathbf{y}|\mathbf{w})$ to the equations to make it easier to understand. In the proof, we also show that using $P_{ \mathbf{I} \cup \mathbf{J} }$ as the intermediate distribution is both necessary and sufficient to derive the graphical constraint.

We will make ${\mathbf{R}_{\mathbf{I}}}$ and so on a global definition to avoid repeated definitions.

We will use \mathrm for notation of MAGs and twin augmented graphs.

For the definition of Augmented pair graph, we will add a sentence to indicate that $F^{(\mathbf{I}, \mathbf{J} )}$ is an auxiliary node for a pair of targets $\mathbf{I}, \mathbf{J}$. The superscript shows the targets. We omit the superscript when it is clear from the context which pair of targets we are looking at.

For the definition of twin augmented MAG, we will add a short sentence in Section 2 where we describe maximal ancestral graphs, on how to construct a MAG over an ADMG. In Line 260, we will replace $S$ with $V\in \mathbf{V}$ as a node such that $V^{(\mathbf{I})}$ or $V^{(\mathbf{J})}$ is adjacent to $F^{(\mathbf{I}, \mathbf{J} )}$ in $\mathrm{MAG}(Aug_{ (\mathbf{I}, \mathbf{J}) }(\mathcal{D}))$.

In Line 263, $Y$ is any node in $\mathbf{V}$. We intended to clarify that any separation statement like $F \mathrel{\perp\mspace{-10mu}\perp} Y^{(\mathbf{I})}$ for $Y \in \mathbf{V}$ is not directly testable from comparing the CIs using just $P_{\mathbf{I}}, P_{\mathbf{J}}$. We can only decide this separation to be true when both $F \mathrel{\perp\mspace{-10mu}\perp} Y^{(\mathbf{I})}$ and $F \mathrel{\perp\mspace{-10mu}\perp} Y^{(\mathbf{J})}$ hold and that motivates our construction of Twin augmented MAGs by adding extra edges to the $F$ node.

MAG construction example

Section 4 will gain an example (figure now in App. D) showing how we construct twin augmented MAGs starting from an ADMG. Section 5 will gain an example (figure now in App. E) showing how we compress twin augmented MAGs to an $\mathcal{I}$-augmented MAG. We believe this, together with the reordered definitions, will substantially improve readability.

We appreciate the constructive feedback. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.

References:

[1] Eaton, Daniel, and Kevin Murphy. "Belief net structure learning from uncertain interventions." Journal of Machine Learning Research 1 (2007): 1-48.

[2] Pearl, Judea. "Models, reasoning and inference." Cambridge, UK: CambridgeUniversityPress 19, no. 2 (2000): 3.

[3] Robins, James M., Richard Scheines, Peter Spirtes, and Larry Wasserman. "Uniform consistency in causal inference." Biometrika 90, no. 3 (2003): 491-515.

[4] Kivva, Yaroslav, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. "Revisiting the general identifiability problem." In Uncertainty in Artificial Intelligence, pp. 1022-1030. PMLR, 2022.

[5] Kandasamy, Saravanan, Arnab Bhattacharyya, and Vasant G. Honavar. "Minimum intervention cover of a causal graph." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, pp. 2876-2885. 2019.

[6] Yang, Karren, 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.

[7] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. "Characterization and learning of causal graphs with latent variables from soft interventions." Advances in neural information processing systems 32 (2019).

Dear Authors,

Thank you for your response.

With respect to novelty, I understand the difference between hard and soft interventions -- My concern was mainly on the technical novelty in the proof techniques. I did read the main paper and briefly went through Appendix, and I didn't find the technical leaps sufficient for the standards of NeurIPS. I understand this is a subjective concern, unfortunately there is no easy way to objectify this.

Also, with respect to existing literature on identifiability, I understand the differences between the problem statements. I was mainly curious in understanding the overlaps in techniques (I believe there should be a significant overlap).