Counterfactual Graphical Models: Constraints and Inference
Authors: Juan D. Correa
Elias Bareinboim
Venue: ICML 2025 spotlightposter (2025)
Keywords: Counterfactual inference
Graphical Models
Constraints
Primary area: general_machine_learning->causality
TL;DR: Constraints and inference using graphical models for counterfactual reasoning

Abstract: Graphical models have been widely used as parsimonious encoders of constraints of the underlying probability models. When organized in a structured way, these models can facilitate the derivation of non-trivial constraints, the inference of quantities of interest, and the optimization of their estimands. In particular, causal diagrams allow for the efficient representation of structural constraints of the underlying causal system. In this paper, we introduce an efficient graphical construction called Ancestral Multi-world Networks that is sound and complete for reading counterfactual independences from a causal diagram using d-separation. Moreover, we introduce the counterfactual (ctf-) calculus, which can be used to transform counterfactual quantities using three rules licensed by the constraints encoded in the diagram. This result generalizes Pearl’s celebrated do-calculus from interventional to counterfactual reasoning.

Counterfactual Graphical Models: Constraints and Inference
Juan D. Correa
Elias Bareinboim²
Abstract
(Age)
Graphical models have been widely used as par- simonious encoders of the constraints underlying probability models. When organized in a struc- tured way, these models can facilitate the deriva- tion of non-trivial constraints, the inference of quantities of interest, and the optimization of their estimands. In particular, causal diagrams enable the efficient representation of the structural con- straints of the underlying causal system. In this paper, we introduce efficient graphical con- struction called Ancestral Multi-world Networks that sound and complete for reading counterfac- tual independences from a causal diagram using d- d-separation. Moreover, we introduce the cown- terfactual (ctf-) calculus, which can be used transform counterfactual quantities using three rules licensed by the constraints encoded in the di- agram. This result generalizes Pearl's celebrated do-calculus from interventional to counterfactual reasoning.
X
(Treatment)
(Survival)
Figure I. A causal diagram over three variables.
we recover some state of affairs, perform a change in the sequence of events, and let hypothetical situation to play out. More generally, counterfactuals are important com- ponent in the construction of explanations regarding why certain events occurred the way they did (Pearl 2000 Pearl & Mackenzie 2018 Bareinboim et al. 2020).
One fundamental topic of study in counterfactual reasoning is understanding the various quantities, the constraints on their relation, and the types of inferences allowed across vari- ous counterfactual worlds. Specifically, counterfactual quan- tities evoke hypothetical conditions that could contradict the factual evidence, underpinning different applications involv- ing blame and responsibility, credit assignment, and more individualized types of decisions (Pearl 2000). Examples of such quantities include the effect of treatment on the treated (Heckman 1992 Pearl 22000,, path--pactttpte effects (Pearl 2001 Avin et al. 2005). and causal and spurious variations
1. Introduction
Counterfactuals form the basis of important notions across human cognition that require retrospective thinking, where must compare what did happen in the real world versus what would have happened under some different hypothet- ical conditions. Given the impossibility of observing an alternative outcome once an action is taken, counterfactu- als evoke "what if?" questions whose answers can only be approached by imagining hypothetical conditions contrary to this factual evidence. For instance, questions such as "what would be the death rates had the vaccination started two weeks earlier?" "given that I arrived late, would have been on time had I taken the subway instead of the taxi?" require us to earry out a mental experiment where
Zhang & Bareinboim 2018 Plečko & Bareinboim 2024).
There are also quantities such as the probability of necessity (PN), probability of sufficiency (PS), and the probability of necessity and sufficiency (PNS) that relate to fundamental aspects of how events are related and can explain the other. For example, consider the causal diagram in Figure Jover the variables age, trealment, and survival. The counterfac- tual event (Y, = X = x') refers to the survival of a person (Y = 1) that gets a treatment X = x when they would naturally decide not to get treated (x'). Such queries depict a quintessential counterfactual situation, since we aim to evaluate world that contradicts the factual one in which the person was not treated.
'Department of Computer Science, Universidad Autónoma de Manizales. Manizales. Colombia DDpaatment of Commputer Science, Columbia University, New York, United States. Corre- spondence to: Juan D. Correa <jcorrea@ www.ae@aaatttttu....o.m
In the first part of our paper, we revisit and generalize counterfactual constraints - exclusion and independence restrictions, and consistency (Pearl) (0000) and show how they follow from the Structural Causal Model semantics. Specifically, we introduce a new graphical representation
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Counterfactual Graphical Models: Constraints and Inference
that encodes independences between counterfactual random variables, which we call Ancestral Wolti-Worlddddi Network (AMWN). Based on this new data structure, we formally show that the d-separation criterion is complete for read- ing such constraints based on a causal graph and a set of counterfactual variables. Compared with the prior litera- ture, the newly proposed method improves over the Twin Networks (Balke& & Pearl 1994). for which d-separation is not complete, and from Single World Intervention Graphs (Richardson & Robins 2013), which consider a single inter- vention at time. AMWN also differs from Netti-Nettwors and Counterfactual Graphs (Shpitser & Pearl 2007), which were conjectured to be complete but require constructing a possibly exponential number of graphs to test separation among counterfactual variables rather than events.
x and z are consistent if they share the common values for X n Z. We also denote by Z the value of X Z consistent with and by xnZ the subset of x corresponding to variables in Z. We assume the domain of every variable is finite.
We represent qualitative assumptions using causal graphs, denoted with a calligraphic letter, e.g., G, etc. Given a graph G. Swx is the result of removing edges coming into variables in W and going out from variables in X. g[W] denotes a vertex-inducee subgraph, which includes W and the edges among its elements. We use kinship notation for graphical relationships such parents, children, descen- dants, and ancestors of a set of variables.
We base our analysis on the Structural Causal Model (SCM) paradigm (Pearl, 2000). An SCM M is a 4-tuple (U, V P(u)), where U is a set of exogenous (latent) variables; V is set of endogenous (observable) variables; FF is collection of functions such that each variable V; E V is determined by function fi E F. Each f. is mapping from a set of exogenous variables U; S U and set of endogenous variables Pa; C V {V} to the domain of V.. Uncertainty is encoded through a probability distribution over the exogenous variables, P(U).
In the second part of the paper, and building on the con- straints and AMWN construction, we formulate a set of three rules for counterfactual inference called Counterfac- tual Calculus (ctf-calculus). Compared with the litera- ture, our rules are more general than Pearl's celebrated do-caleulus (Pearl 1994 1995) for interventional reasoning, since it allows for the transformation of counterfactual quan- tities to infer the implied equality constraints. Moreover, we show that the counterfactual calculus is complete for identifying counterfactuals from observational and interven- tional distributions. This set of rules also differs from the Potential Outcome Calculus (po-calculus) (Malinsky et al. 2019), which has been shown to hold if and only if the cor- responding do-caleulus rules hold. While po-calculus rules require counterfactual variables to follow certain patterns in terms of interventions and require pre-processing steps to be used for certain identification tasks, we propose rules supporting more general mixes of interventions, which, com- bined with probability axioms, are sufficient for deciding counterfactual identification.
An SCM M induces a causal diagram 9 where V is the set of vertices, there is directed edge (V, - Vt) for every Vi E V and V E Pa,. and bidirected edge (1/2 <--+ V2) for every pair V1, Vj E V such that U. nU, * 0 (V; and V, have a common exogenous parent) (Bareinboim et. 2020) We assume that the underlying model is recursive. That is, there are no cyclic dependencies among the variables.
SCMs allow us define counterfactual quantities with pre- cision based on the Pearl's Causal Hierarchy (PCH) (Pearl & Mackenzie 2018 Bareinboim et al.) 2020 This hier- archy is divided into three layers (Figure 2 the first one (C,) captures the notion of "seeing," that is, observing a cer- tain phenomenon or reality and possibly making inferences about it. The second (L2) allows one to represent the no- tion of "doing", that is, intervening (or deliberately acting) in the environment to bring about certain state of affairs. Modifying an SCM gives natural valuations for quantities of this kind, as defined next.
More specifically, our contributions are as follows:
1. Graphical criteria: a sound, complete, and efficient procedure to test conditional independences among counterfactual variables using d-separation on a modi- fied causal diagram.
2. Inference rules: a set of inference rules for coun- terfactual reasoning that are sound and complete for counterfactual identification from observational and experimental distributions.
Definition 1.1 (Submodel). Let M be a causal model, X a set of variables in V, and x a particular realization of X. A submodel My of M is the causal model
Mx = (U, V Fx, P(U)), where
(1)
Proofs can be found in the supplemental material.
Fx - (/+ V & X] U -
(2)
Definitions and Background. We denote variables by capital letters, X, and values by small letters, x. Bold letters, X represent a set of variables and x a set of values. The domain of variable X is denoted by Val(X). Two values
That is, performing an external intervention (or action) is modeled through the replacement of the original (natural) mechanisms associated with some variables X with a con- stant x, which represented by the do-operator. The impact
2

---

Counterfactual Graphical Models: Constraints and Inference
L:: P(V)
for whenever the solution of f& is equal x. While Sa is fixed as a constant x: in Fz (as illustrated in Figure } for any unit U u for which X = I, the result of these two systems of equations coincide.
SCM
Czi P(Vx)
Ls: P(Vi[Ki] V2xx)).-..)
Both models will match in the value of every observable, i.e., for u' = {u X X() = x}.
Figure Every SCM induces different distributions each layer of the PCH.
X
Yuu') Z(u')=Zz(u') (4)
of the intervention on an outcome variable Y commonly called the potential response:
Moreover, the probability of the corresponding random vari- ables follows from averaging P(U) for those u, and then:
Definition 1.2 (Potential Response). Let X and Y be two
sets of variables in V, and u be a unit. The potential re- sponse (u( is defined the solution for Y of the set of equations Fx with respect to SCM M (for short, Y M, (u)).
P(Y, = y, y. =x) x)
Σ, I[Y2(u) = = y, X(u) = x] P(u) (5)
That is, (u) = (u).
Σ ([) = x = P(u) (6)
In other words, Y M, (u) is obtained through the compu- tation of (u) in the submodel MMx On the other hand, the meaning of every term in the counterfactual layer (Lg) can be directly determined from a fully specified structural causal model, described in the sequel:
P(Y y, = x)).
(7)
Again, this so because Yz(u) = Y(u) for those u for which X (u) = x. More generally, when considering all the endogenous variables, we have:
Definition 1.3 (Counterfactual Distribution Valuation). An SCM M = (U,V. F. P(U)) induces family of joint distributions over counterfactual events Yx,..., Zw. for
P(Y,, X P(Y x),
(8)
In other words, once we restrict our attention to the set of units that generate X x, then the variations of Yz, and Z, are consistent with the variations of Y, and Z, respectively.
any Y, Z X, W C V, P. (yx, Aw) is given by:
Σ, u (u) = y..... Zw (u) z P(u).
(3)
Intuitively, once X takes the value x, naturally, other vari- ables in the model behave the same as if X had been fixed to x by intervention, for instance, Y- = y
Let W. ((W)), (W.)....... represent an arbitrary set of counterfactual variables such that W; E V and T; S V for = 1, We assume throughout this paper that all the distributions generated by the models are positive.
More broadly, consistency does not depend on the indepen- dence structure among the exogenous variables, P(U), and follows from the relationships within the structural mecha- nisms F.
2. Counterfactual Constraints
The following characterizes this family of constraints across endogenous variables:
We begin by stating three types of constraints that hold over counterfactuals random variables: consistency (Section 2.
Lemma 2.1 (Consistency). Given SCM M and X,Y E V, T. be any combination of counterfactuals, and let x be a value in the domain of X. Then,
exclusion (Section 2.2). and independence (Section 2.3 which we detail in the following subsections.
2.1. Consistency Constraints
P(Y,, XT. = x) = P(YY.,,, = =x).
(9)
Consistency constraints relate to the interplay between ob- serving a variable taking a particular value and the effect of an intervention that fixes this variable to the same value. To ground this idea, consider an SCM M over endogenous variables V = (X, Y, 2} and suppose we are interested in studying the joint counterfactual event (Y, y. x²). Following the proper semantics (Theorem 1.2 the value of variable X is given by the solution of the system of equa- tions F associated with M, X X()), for each unit U- = u. Similarly, the value of Y, is given by the solution of the sys- tem Fr, Y, (u), for the same unit The event X- = x occurs
As suggested by the term T. in Theorem 2.1 consistency between observations and interventions not only occurs for interventions that fix a variable to a constant value (e.g.. do (X = x)) but is also true with interventions that set a variable to match another counterfactual variable, as dis- cussed next.
One way to interpret such a statement is through the indepen- dence of the mechanisms that give value to each of the endogenous variables in the system in conjunction with the locality of the intervention.
3

---

Counterfactual Graphical Models: Constraints and Inference
[u X = x)
(u)
These two steps allow us reason about nested counterfac- tuals and transform them into expressions involving non- nested ones.
Fx
Fx.
F
fz
f
fx
f/2
2.2. Exclusion Constraints
fx
Although the semantics of counterfactuals allows one to consider a variable Yt for arbitrary Y E V and T S V. some counterfactual variables are not entirely free to vary depending on the topology and the sparsity of the causal system. For example, consider the simple chain graph in Figure 4[a) and the counterfactual variables Y2 and Yz2- To understand the relationship between these two variables, we write the corresponding sub-models M₁ and Mazi
fg
fg
fy
(X x, Y.)
(Yx,)
(a) Mechanisms involved in generating the event (Y,, X = 4).
(b) The variable Yx, results from forcing X to take the value (u) for every u.
X. fx(Us)
X t Zeo t Yu t fv(2,Ug).
Figure 3. Representation of the mechanism involved in generating counterfactual events. The gray boxes represent data-generating mechanisms that transform a particular unit U into coun- terfactual event over the observable variables. Each rectangle is copy of the mechanisms of the structural causal model. Depend- ing the counterfactual of interest, the mechanisms share some functions (e.g. fa and fy in (a)), redefine others (fa and ft in (a)), or contain functions that require the evaluation of separate set of mechanisms (e.g. fz in (b)) to compute nested counterfactual.
F.
Z c=
F===
Y. t fr(2,Uw)
(13)
Note that for each unit U u, the variables Y, and Y.z are the same. Intuitively, once the value of Z is fixed by intervention, the only source of variation for the variable Y in both M, and MMz comes from Uy so intervening on X is irrelevant. In some sense, the intervention on X can be excluded without any changes in the value of Y, which gives the name exclusion restriction.
and
2.1.1. 1. NESTED COUNTERFACTUALE
So far we have considered counterfactuals of the form Yz, where the subscript x indicates that an intervention do (X = z has been performed in the system. We turn our attention to interventions that could be expressed as do (X X,), and represent settings where the variable X is set to behave another counterfactual variable, say X.- This operation is illustrated in Figure 3(b) In other words, the value of X, is computed in a sub-model F, (figure's s r.h.s)) and used to replace the natural mechanism fo (in the Lh..s). A random variable Y in such a system is represented with a counterfactual of the form Yx,, which called a nested counterfactual.
In graphical terms, an intervention on variable X could affect another variable Y only if there exists causal (di- rected) path from X to Y in e Although in Figure 4(a) there is such path, the same is severed once Z is intervened on. This observation can be stated more generally in the form of an operator used to exclude interventions from a given counterfactual variable as follows:
Lemma 2.3 (Exclusion operator). Let Yx be a counterfac- tual variable, G a causal diagram, and
Yg such that Z Xn Ann)n((Y)))) and z X (14)
The nesting means the target counterfactual internally refers to another nested world (possibly multiple times).
Then, Y. Yx holds for any model compatible with G. Moreover, this trunsformation is denoted as ||Yx|| Yz.
Corollary 2.2 (Counterfactual Unnesting (CU)). Let Y, E V. Z S. V. and let z be a set of values for Z. Then, the nested counterfactual P(Yr.x, = y) can be written with one less level of nesting as:
Note that by keeping X (n An(Y)sx (Equation 14 ), the exclusion operator removes from the counterfactual' 's an- tecedent (i.e., subscript) variables that are not ancestors of Y (variables without causal paths to Y) as well as those ances- tors that once do (X) is performed are no longer ancestors of Y.
P(Yr.x.=1)) Σ, P(YT. =, = x). (10)
This statement follows from the law of total probability and consistency itself, i.e.:
For set Y.. define |Y.I= Uvey, ||]]]. The result of applying the exclusion operator to x. || is always equal to Yxx or an equivalent counterfactual variable with fewer variables in its antecedent.
P(Y..x. x. v)
Σ, P(Y T.
X2 zz)
(sum over X²) (11)
X₂
Σ, P(Y T.
U0 X₂
Ø
(consistency). (12)
II terms of SCM, this means there is sequence of functional substitutions such that X may appear in the argument set of Y.

---

Counterfactual Graphical Models: Constraints and Inference
convenient ignore nodes of variables fixed by intervention and reduce every variable with the exclusion operator. This results in the 3-plet network shown in Figure 5(b) In this new graph, d-separation can be used to tell that X and Yaw = Yu are separated given Ze = Z.
X
Z
Y
X
W
Y
(a) Chain causal structure.
(b) Causal diagram over 4 variables.
Figure 4. Graphical structures used to illustrate exclusion and in- dependence constraints.
More generally, we can construct twin networks, 3-plet networks, or k-plet networks depending on the number of interventions in the separation statement. Then, use the ex- clusion operator merge nodes corresponding to variables that are deterministically the same. This method, however, includes many variables in the graph that we do not need to check. To improve efficiency, as we will show later, we discuss the concept of ancestors of a counterfactual.
One interesting feature of exclusion constraints is that they
are derivable from the order relative to the mechanisms, F, of the underlying SCM, .M". Other invariances from MM come from sparsity in P(U). as discussed in the sequel.
Definition 2.4 (Ancestors (of a counterfactual) (Correa et al. 2021). Let Yx be such that Y E V.X S V. Then, the set of (counterfactual) ancestors of Yx, denoted by An(Yx), consist of each W₂, such that W E Ann(Y) \ X (which includes Y itself), and z = x An())sx
2.3. Independence Constraints and the Counterfactual d-separation Criterion
The ability to represent multiple worlds simultaneously is fundamental aspect that sets apart the third layer of the PCH from the others. One could therefore consider probability expression involving variables from multiple worlds, such as Y2 and Z when x * z'.
This extends the idea that, in graphical terms, a variable can only affect another if the former is an ancestor of the latter. When counterfactuals are involved, some of those ancestors become irrelevant (by virtue of the exclusion operator). For example, for the graph in Figure44a)) X is an ancestor of Y, but is not (counterfactual) ancestor of Yg, because under do (Z), X cannot affect Y.. Similarly, Z is an ancestor of Y. but for Y, counterfactual ancestor is Zz. not X or Z.
At the structural level, multiple interventions entail different copies of the mechanisms F of the SCM, each for a different world (syntactically represented by a different subscript), but all sharing the same P(U). As implied by Equation 3 counterfactual distribution can be evaluated by passing the set of exogenous variables U through the different versions of those mechanisms, depending on which hypothetical world one aims to evaluate. This process can be mimicked and represented at the graphical level by a "meta" diagram incorporating different instances of the endogenous vari- ables produced by the various mechanisms and connecting different worlds through the U variables. This idea allows the evaluation of separation statements among nodes repre- senting counterfactual variables, which in turn imply condi- tional independences among the corresponding variables in the underlying distribution.
For a set of variables W., we define An(W.) as the union of the ancestors of each variable in the set. That is, An(W.) = Uw,ew, An(W)). For exam- ple, in Figure 4(b) An(Ynw) = (Yw, Z), An...) = (W An()) (X
We describe graphical construction called the Ancestral Multi- Network (AMWN), denoted G (G. Y.). This data structure is function of the original causal diagram G and the counterfactual variables Y. in the separation state- ment to be evaluated. Algorithm [ describes the procedure for creating an AMWN.
For conereteness, consider whether the causal graph in Fig-
ure 4(b) implies that (Yzw, W., IL X 7. Figure ((a) shows natural generalization of the twin network to 3 worlds, 3-plet network, for this graph and question. Note that the variables in the query involve three submodels: M,M and Maw, all depicted in the network sharing explicit unobservable variables.
For concreteness, let us consider again the evaluation of the separation query (Yaw, Wa IL X)) using the causal diagram in Figure 4(b) In line 1, the procedure computes An(Y (Y.). which will be added as nodes in the AMWN.
The associated directed arrows witness the ancestrality of the variables involved. For instance, Z is an ancestor (par- ent) of Y.,. hence Z and the arrow Z - Y.. must be present in the graph. Note that, at this point, the resulting graph is a subgraph of Figure but the rest of the graph is not rele- vant to evaluate the separation statement with d-separation. That is, (X, 11 Yr on top of (X,,,, Yr, Z.).
While seems that X is d-connected to Yzw given Zy in Figure 5(a) due to the active path X t- Z + U.
Zane Y rm, the exclusion operator reveals Z, 11
Z. This means that conditioning on Z is the same as conditioning on Z, and the separation holds.
Z.) can be judged using d-separation
In this sense, we should merge the nodes Z, Ze,, and Zew due to the deterministic relationship among them. It is also
The second part of A Algorithm T explicitly adds latent vari-
5

---

Counterfactual Graphical Models: Constraints and Inference
Algorithm AMWN-CONSTRUUTTHN Y.)
Input: Causal diagram & and a set of counterfactual variables Y.. Output: (Y the AMWN of 9 and Y..
1: Initialize a network g' adding the variables in An(Y.) to- gether with the directed arrows witnessing the ancestrality.
2: for each variable V V appearing more than once in G' do
3: Add node Uv and an edge Uv + Vx for every instance of V V.
Ur
4: end for
Z
5: for each bidirected V 4--+ W where V and W are in g' do
6: Add node Uvw and edges from it to Va and Wx, for every instance of Vx or Wx of W in G".
M
My
W
Yu:
7: end for
8: return G'.
Us
(b)
(c)
and collection of counterfactual distributions, Puts in- duced by the SCM associated with G. For counterfactual variables Xt, Yr, Z...
Figure 5. Based on the causal diagram in Figure 4bb and inter-
ventions do (az, w) do (z'), and do (0): 3-plet network (a), 3-plet network exclusion. (c) AMWN with the ancestors variables Yzw, We', ; X and Z.
(IXxIIJLI)YIII [Z.1)ea - ((XxeII [Z.I))...
Zu
Moreover, if an independence relationship cannot be in- ferred with the criterion, there exist least two models inducing the graphical model where the independence does not hold.
U²
Z
W
WA
U2F
Z
In other words, the d-separation criterion is sound for the counterfactual variables in the AMWN, that is, if |x,|ll and |Y'll are d-separated given |Z~||| |l in the diagram (X,,, Yr, Z.), then X, and Y, are independent given Z. in every distribution P... compatible with the causal diagram G. It is also complete because if d-separation does not hold in the AMWN, then independence cannot be guaranteed.
X
(a)
(b)
Figure 6. To judge the separation statement (Yzw TT X 2, W) in we construct AMWN (b)aadd and use d-separation.
a
ables U facilitate reasoning about the relations among variables appearing more than once in the graph with differ- ent subscripts and variables originally connected by latent
This result allows us use the construction of AMWN of g to test whether pair of counterfactual variables is independent in the probability distributions generated by the model compatible with G.
confounding 3
For instance, consider the causal diagram in Figure 6(a) and whether (Yzw X (Z, W)). The relevant set of ancestors (Y 2w, X, Z, W) (Yow: Zw, X, Z, W). The corre- sponding AWMN is shown in Figure 6(b) The node U₂ has been added and connected Z and Zue (line [ which come from the same original variable. There is also the node Uzn. that is connected to 7, 7n and X due to the bidirected arrow Z +- X in & (line D. By the d-separation criterion, the path X +--+ + Z + Yzu is active given { [Z, W). which leads to the conclusion that (Yow X X Z, W), as stated in the sequel.
Now, we examine the time complexity of constructing an AMWN. Let z be the number of different interventions in the separation query, and n, m be the number of nodes and edges, respectively. In line [ the set of counterfactual ancestors can be computed in time linear to the size of the graph, for each intervention appearing in Y.; hence the step takes time (z2(n + m)). Due to line I no more than latent nodes and on edges are added. Line adds m latent nodes and 22m edges at most. Overall, the construction takes (=z(n + m)). which polynomial the size of and Y..
Theorem 2.5 (Independence Constraints - Counterfactual d- d-separation (soundness)). Consider a causal diagram G
The resulting graph GA has O(z(n + m)) nodes and edges, hence running d-separation on top of it takes O(2(n m)) time (van der Zander et al. 2014). Compared with the clas- sical d-separation criterion, the time required to use AMWN increases by a factor of 2, the number of different worlds involved the query. Table summarizes the methods
'The exogenous variables shared across worlds are precisely the anchors of invariance in these settings. They represent precisely the identity of the units submitted to these different counterfactual conditions.
6

---

Counterfactual Graphical Models: Constraints and Inference
discussed, in terms of whether they allow for checking any separation constraints (among any counterfactual in the con- sidered worlds), if d-separation is complete for them, and the time complexity of the construction of the graph and check- ing the constraint Overall, the method based on AMWN is more general and efficient than previous algorithms in the literature.
Method
Any sep.
Complete
Time Complexity
Twin Network
Yes
No
O + m)
SWIG
No
Yes
O(n + m)
Multi-Networks
Yes
Conject.
O (n + m))
k-plet Network
Yes
Yes
(zn + m))
AMWN
Yes
Yes
(z + +))
Table I. Comparison of counterfactual independence graphical constructions. For each method, we look at whether it supports any separation query, whether it is complcte, and its time complexity.
3. The Counterfactual Calculus
Building on our understanding of the constraints discussed earlier, this section introduces the counterfactual calculus and how it can be used for counterfactual inference based on the assumptions encoded in causal diagram.
match. As mentioned earlier, consistency is essentially the probabilistic instantiation of the invariances that follow from the modularity and stability of the causal mechanisms of the underlying system.
In the spirit of Pearl's celebrated interventional calculus (do-calculus), its counterfactual counterpart allows one to transform expressions in the form P(y= x,) to other coun- terfactual quantities, including in observational (P(y x)) and experimental (P(y do (x))) forms, as licensed by the constraints encoded in the causal diagram. The counterfac- tual calculus consists of three inference rules based on the three types of constraints discussed earlier.
The second rule, independence (Section corresponds to a generalized version of d-separation for counterfactual events. Syntactically, it permits the addition/removal of counterfactual evidence in probability distribution.
The third rule, exclusion (Section 2.2 follows from the idea that interventions on variables without a causal path to the observed variable do not affect this variable and, therefore, can be dismissed 6
Theorem 3.1 (Counterfactual Calculus (ctf-cald ceff-calculs)), Let be a causal diagram, then for Y. X. Z. W, T, S V. the following rules hold for the probability distributions generated by any model compatible with G:
For concreteness, we illustrate next the use of the ctf- calculus rules for counterfactual identification tasks through few examples.
Rule 1 (Consistency rule- Obs./intervention exchange)
Example I (ETT in the Backdoor diagram). Consider the causal diagram in Figure Tadd the observational distribution as input, and the counterfactual distribution P(y- x') as the query. Using the etf-calculus, we can then write:
P(yT.x, XT,, w.) = P(yT,,XT,,
(15)
Rule 2 (Independence Rule - Adding/removing counter- factual observations)
Plyz (²)
P(yr Xt. w.) = P(yr w.) iY, 11 Xt W.) in GA, (16)
Σ. P(yx 2, 2, P((x) x²)
(Conditioning on Z)
(18)
Rule 3 (Exclusion Rule- Adding/removing interventions)
Σ P(ye 22, x P(z xx)
P(yxe, w -Pyy,,
(R3: [X} n An (Z) = 0)
(19)
fXnAn(( = 0 in Oz.
(17)
P(yez E,, x') (e)) P(z x²)
where GA is the counterfactual ancestral graph (G Y,U X.U N.WWW U.).
(RI: (Z, = 2 = Y, = Ynz))
(20)
Σ. P(yez 12,,') | |x)
The first rule of the calculus, consistency, was discussed in Section 2.1 One distinct feature of this rule is that does not depend on the graphical structure and allows for adding or removing interventions whenever specific observational context and the antecedent of the counterfactual (subscript)
=
(R3: (X} n An(Z) 0)
(21)
P(yez P, xx)
(R2: (X Tl Y.z ZZ) in GA (Figure 7(a)
(22)
FFurther details on this comparison are given in Appendix C.1 (Correa & Bareinboim 2024).
Σ Ply 2. P(z x')
nn m, 2, and d refer to the number of nodes, edges, (different) interventions, and maximum cardinality of any observable variable G. respectively.
'We provide comparison of ctf-caleulus and do-calculus in Appendix C.2 in (Correa Bareinhoim 2024).
7

---

(25) Theorem 3.2 (Soundness and Completeness for Counterfac- tual Identifiability). A counterfactual quantity Q = P(y,, x,) is identifuble from a given combination of observa- (26) tional and experimental distributions and a causal diagram G if and only if there exists a sequence of applications of the rules of ctf-calculus and the probability axioms that reduces Counterfactual Graphical Models: Constraints and Inference
Z
W
W
W
x''
Wz
x
Yus
W
Yo'w
X
Ya'w
X
(a)
(a)
(b)
(c)
Figure 7. (a) An AMWN based on Figure D and variable set Y. (Y.z: X, }} used derivation Example
(b)
Figure 8, Causal diagrams used in derivation Example
causal diagram used in Example
(R1: (Z = = Y)) (23)
(Condition on W;)
(31)
= E, P(ys Was x) P(w+)
The effect of the treatment the treated is then identifiable from P(x. 2, y) and g.
10
(R2: (Y, Il X W₂) in Gn (Figure ((c)
(32)
Example (Natural Direct and Indirect Effects). Consider the causal diagram in Figure 7bb) and suppose we wish to evaluate the natural direct (NDE) to understand how ex- ercising (X) affects cardiovascular disease (Y) by means other than affecting the cholesterol level (W), that acts as a mediator of this relationship. The NDE can be written in counterfactual language as
Σ Ply w, w,
(R1: (X W. W,Y, -)).
(33)
Finally, we get
NDE (v)= Σ (') P(w.). (34)
ND x (v) P(ya, P(yz).
(24)
The derivation of the first term of the NDE expression goes as follows:
by putting Equations 30 and 33
together.
The calculus guarantees the correctness of the reduction whenever such derivation from a counterfactual query to the probabilities over the observed distributions is available.
P(y,w,)
E, P(ystw, Wx)
(CU, cor. 2.2 sum over We + consistency)
Σ. P(yzro wxx P(wx)
(Chain rule)
- P(ysr Wzr ) P(wz)
(R2: (Ys Wa, W GA (Figure 8(a)
(27)
Q into a function of the available distributions.
Σ. P(yzte Wx) x') P(w..))
In other words, any derivation following the ctf-calculus is (28) correct (soundness) and, if any counterfactual is identifiable from certain observational (L1) and interventional (C2) dis- tributions, there must exist a sequence of applications of (29) the etf-caleulus that witnesses the mapping of the available distributions and the target effect (completeness).
(R2: (Yo' IL X Wx.) in GA (Figure 8(b))
P(yste |w, .(ux))
(R1: (X = x' + Wy W))
Σ P(y w,,x) P(Wz))
Since any causal effect can be written in counterfactual terms, it is only natural that etf-calculus subsumes do- calculus, as follows.
(R1: (W = w, X x' Yo' =Y) Y)).
(30)
Here, P(wx) cannot be further reduced to expression in terms of observational distributions.
Lemma 3.3 (etf-calculus - do-calculus reduction). ctf- calculus subsumes do-calculus.
For the baseline P(yx), the derivation goes as follows:
More details on the relationship between do-calculus and ctf-caleulus can found in Appendix C.2 in (Correa & Bareinboim, 2024
P(yx)
Σ. P(y, (ww)P(w))
8

---

Counterfactual Graphical Models: Constraints and Inference
4. Conclusions
ence. Technical Report R-60. In press., Causal Artificial Intelligence Lab, Columbia University, 7 2020.
In this paper, we first established consistency (Theorem 2.1 exclusion (Theorem 2.3 and independence constraints (Theorem 2.5) following from the SCM semantics. We showed that d-separation is complete for obtaining inde- pendence constraints from the causal diagram using an efñi cient graphical construction called Ancestral Multi- World Network (Algorithm D This constitutes the first efficient procedure for reading counterfactual independence. We then introduced a set of rules called counterfactual calculus (Theorem B.J). which can be used to transform target coun- terfactual quantities based on the constraints encoded in the diagram. Finally, we showed that counterfactual calculus is sound and complete for identifying counterfactuals from an arbitrary combination of observational and experimental distributions (Theorem 3.2) We hope the results in this paper can further our understanding and expand the tool- box for performing causal reasoning, closing a journey that started with Pearl's fundamental results on d-separation for observational distributions (circa 1986) and the do-calculus for interventional reasoning (1995). We now have more general machinery that allows for reasoning across the three layers of the causal hierarchy, including the very top: coun- terfactual relations.
Correa, J. D. and Bareinboim, E. Counterfactual graphical models: Constraints and inference. Technical Report R- 115, Causal Artificial Intelligence Lab, Columbia Univer- sity, August 2024. URL patps::/ ri15.pdf
htttts:://causaaiii /wccaaassaaaaaaa/aaa/....aaaaala nettslli.ne/ net/
Correa, D., Lee, S., and Bareinboim, Nested Coun- terfactual Identification from Arbitrary Surrogate Exper- iments. In Advances in Neural Information Processing Systems, volume 34, 2021.
Heckman, J. J. Randomization and Social Policy Evalua- tion. In Manski, C. and Garfinkle, I. (eds.), Evaluations: Welfare and Training Programs, pp. 201-230. Harvard University Press, Cambridge, MA, 1992.
Malinsky, D., Shpitser, I., and Richardson, T. A poten- tial outcomes calculus for identifying conditional path- specific effects. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3080-3088. PMLR, 2019.
Pearl, J. A probabilistic calculus of actions. In de Mantaras, L. and D. Poooolle (eds.), Uncertainty Artificial Intelli- gence 10, pp. 454 462. Morgan Kaufmann, San Mateo, CA, 1994.
Acknowledgements
This research is supported in part by the NSE, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foun- dation.
Pearl, J. Causal diagrams for empirical research. Biometrika, 82(4):669-66) 1995.
Pearl, J. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2000. ISBN 978-0-521-89560-6.
Impact Statement
This paper presents results that advance the field of Machine Learning, particularly in the area of Causal Inference. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Pearl, J. Direct and indirect effects. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intel- ligence, pp. 411-420. Morgan Kaufmann, San Francisco, CA, 2001.
References
Pearl, J. and Mackenzie, D. The Book of Why. Basic Books, New York, 2018. ISBN 978-0-465-09760-9.
Avin, C., Shpitser, I., and Pearl, J. Identifiability of Path- Specific Effects. In Proceedings of the Nineteenth In- ternational Joint Conference on Artificial Intelligence (ICAI-05), pp. 357-363, Edinburgh, UK, 2005. Morgan- Kaufmann Publishers.
Plečko, D. and Bareinboim, E. Causal fairness analysis: A causal toolkit for fair machine learning. Foundations and Trends@ in Machine Learning, 17(3):004-589 2024.
Richardson, T. S. and Robins, J. M. Single world interven- tion graphs: primer. In Second UAI workshop on causal structure learning, Bellevue, Washington. Citeseer, 2013.
Balke, A. and Pearl, J. Probabilistic evaluation of counter- factual queries. In Proceedings of the Twelfth National Conference on Artificial Intelligence, volume pp. 230- 237. MIT Press, Menlo Park, CA, 1994.
Shpitser. I. and Pearl, J. What Counterfactuals Can Be Tested. In Proceedings of the TwentyThird Conference on Uncertainty in Artificial Intelligence, pp. 352-359, AUAI Press, Vancouver, BC, Canada, 2007.
Bareinboim, E., Correa, J. D., lbeling, D.,, and Icard, T. On Pearl's Hierarchy and the Foundations of Causal Infer-

---

Counterfactual Graphical Models: Constraints and Inference
der Zander, B., Liskiewicz, M., and Textor, J. Construct- ing separators and adjustment sets in ancestral graphs. In Proceedings of UAI 2014, pp. 907-916, 2014. ISBN
9780974903900.
Zhang, J. and Bareinboim, E. Fairness in Decision-Making- The Causal Explanation Formula. In AAAI Conference Artificial Intelligence, 2018. doi: 10. 10.10166f.eeerry22000 09.003.
10


Reviews:
[{"review_id": "xo0eqdUws9", "reviewer": "Reviewer_GANy", "summary": "The paper introduces an efficient graphical construction called Ancestral Multi-world Network, which is sound and complete for interpreting counterfactual independencies from a causal diagram through d-separation. Furthermore, the authors propose the counterfactual (ctf-) calculus, which provides three transformation rules for deriving counterfactual quantities based on the constraints encoded within the diagram.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. \n\nTo address your question about a scenario where our method succeeds but the other approaches mentioned in Table 1 fail, let us consider the question of whether the causal graph in Figure 4(b) implies that $(Y_{xw}, W_{x'} \\perp X | {Z_x}')$. Figure 5(a) shows a 3-plet (triplet) network (a natural generalization of the twin network to 3 worlds) for this graph and question. The variables in the query involve three submodels: $\\mathcal{M}, \\mathcal{M_x}$, and $\\mathcal{M_{xw}}$, all depicted in the network sharing explicit unobservable variables. It seems that $X$ is d-connected to $Y_{xw}$ given ${Z_{x}}'$, because there is an active path $X \\gets Z \\to U_z \\to Z_{xw} \\to Y_{xw}$. However, as discussed in the manuscript (around line 262) and due to exclusion restrictions, conditioning on $Z_{x'}$ is equivalent to conditioning on $Z$, meaning the corresponding separation statement holds. This implies that the Twin Network alone leads us to infer a wrong conclusion. Although this example involves three worlds (to take advantage of the figure in the paper), the same argument could be made with only two of them.\n\nFor Single World Intervention Graphs (SWIGs), conditional independence among variables present in the SWIG can be read using d-separation, while the representation itself cannot capture cross-world restrictions on the counterfactual joint distribution. For instance, the separation of $X$ and $Y_x$ given Z cannot be judged using the SWIG for Figure 4(a) and intervention $X = x$ because Z does not appear in the resulting graph. These examples and some discussion on Shpitser & Pearl 2007 can be found in the supplemental material, section C.\n\nThe k-plet Network is a concept we use in the paper to refer to the extension of the Twin Network method to k worlds (2-plet network equals Twin Network). In the paper, we imply that when combined with the exclusion operator, the k-plet network method is complete, but it can further be optimized, leading to the discussion of AMWNs. We added proper discussion and clarification about this point in the paper. Thank you!\nAlso, as you pointed out, several definitions in the paper emphasize explanations about the notation and counterfactual variables. We will try to make those definitions more concise, maintaining the essence of the definition while moving additional explanations elsewhere.", "claims_and_evidence": "Yes, the claims presented in the paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked most of the proofs. However, for Lemma 2.3, Definition 2.4, and Theorem 3.1, providing a causal diagram would greatly enhance clarity and ease of understanding.", "experimental_designs_or_analyses": "There is no experimental designs or analyses.", "relation_to_broader_scientific_literature": "The paper generalizes Pearl's celebrated do-calculus from interventional to counterfactual reasoning. The proposed AMWN improves upon existing frameworks, including Twin Networks, Single World Intervention Graphs, and Multi-Networks. Additionally, the three rules introduced for ctf-calculus are more general than Pearl’s do-calculus and the Potential Outcome Calculus (po-calculus).", "essential_references_not_discussed": "Although the paper mentions the k-plet Network, it appears that no relevant references are provided.", "other_strengths_and_weaknesses": "**Strengths**:\n\n-Compared to Twin Networks and k-plet Networks, AMWN reduces complexity by requiring fewer variables for representing counterfactual scenarios.\n\n-Extends Pearl's do-calculus effectively to counterfactual reasoning.\n\n**Weaknesses**:\n\nMany definitions in the paper overly emphasize detailed explanations of variables. Although the paper compares AMWN to Twin Networks and SWIG, detailed experimental results quantifying performance improvements are not provided.", "other_comments_or_suggestions": "In definitions and lemmas, clearly explaining each variable would be helpful; additionally, providing accompanying causal diagrams would significantly enhance readability and understanding.", "questions_for_authors": "Could you provide a simple example illustrating a scenario where your method succeeds but the approaches listed in Table 1 fail—for instance, demonstrating that the Twin network algorithm is not complete, while yours is?", "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": "JmtKNuZhuZ", "reviewer": "Reviewer_RfwY", "summary": "The paper is focused on the graphical modelling and the (symbolic) calculus of counterfactual inferences within the framework of Pearlian structural causal models. There are two major contributions: (i) a novel graphical representation called Ancestral Multi-World Networks (AMWN), which efficiently encodes counterfactual independencies implied by causal diagrams (d-separation is complete wrt AMWNs); (ii)\na new set of inference rules called \"counterfactual calculus\" that extend Pearl's classical do calculus to counterfactuals (also sound and complete for those queries).", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work, pointing out typos, and providing suggestions, which we will incorporate into the manuscript.\nIn particular, we will clarify in the paper that the unnesting corresponds to a transformation that starts with a nested counterfactual and ends with an expression involving a counterfactual with one less level of nesting.\n\nAs far as we can tell, the original paper describing the Twin Network method by Balke & Pearl does not claim the method’s completeness for using d-separation to assess counterfactual independencies. However, in Shpitser & Pearl (2007), the authors discuss the incompleteness of the method to motivate multi-networks.\n\nAs you point out, “the idea of computing a CTF query in the twin network after the surgery might therefore lead to wrong conclusions”. For instance, in the example in Sec. 2.3, related to Figure 5 (a,b), some distinct nodes in the Twin Network may refer to counterfactual variables that are deterministically the same. In the example, conditioning on $Z_{x}'$ is the same as conditioning on $Z$. Because the Twin Network does not capture this constraint graphically, d-separation does not capture such independencies. We have also provided further discussion on this in section C of the supplemental material but will clarify this in the main text as well. Thank you!", "claims_and_evidence": "All the claims about the construction and soundness of the new graphical structure and the corresponding calculus are formally proved.", "methods_and_evaluation_criteria": "This is a theoretical paper with no experiments.", "theoretical_claims": "I checked the proofs of the main results but not those of the preliminary lemmas. I believe the results are correct.", "experimental_designs_or_analyses": "This is a theoretical paper with no experiments.", "relation_to_broader_scientific_literature": "The relation with the broader scientific literature is very clear.", "essential_references_not_discussed": "I think all the relevant references are properly cited.", "other_strengths_and_weaknesses": "This is a significant and influential paper for counterfactual inference. The work fills a gap in the earlier literature, and I might imagine lots of applications based on the calculus presented here. Of course, some results are pretty technical, but this is expected and the authors did an excellent job in giving additional information and insights in the supplementary material.", "other_comments_or_suggestions": "The sentence about \"transforming nested ctf into non-nested one\" might be misleading, as we have a sum in the transformation.\nThere are a few typos in the references (ex. \"(?)Ch. 7]pearl:2k\"). Moreover, in section 2.3., the test query is conditioned on Z intervened by setting X=x’ and not Z’ intervened setting X=x. \nSome of the material in S2 is not entirely novel. The authors should better make this explicit in their revised version.\nHas the lack of completeness of twin nets been explicitly stated in the original paper of Balke & Pearl?\n\nAs I can understand, the idea of computing a CTF query in the twin network after the surgery might therefore lead to wrong conclusions. If so, it would be nice to emphasize this point in the paper.", "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": {"ethical_review_concerns": "-"}}, {"review_id": "qM5X2TcAWS", "reviewer": "Reviewer_ajna", "summary": "The paper studies the identification of counterfactual queries. It studies the constraints induced by the casual graph: consistency, exclusion, and independence. The paper proposes a sound and complete method for testing independencies among counterfactual variables based on constructing a simplified graph (AMWN) and then testing d-separations on the graph. These constraints then lead to a set of sound and complete rules, called counterfactual calculus, for identifying counterfactual queries.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work, providing feedback, and giving suggestions.\n\nTo answer your question about the intuition for counterfactual ancestors (Definition 2.4), they are the counterfactual variables that are causally relevant to the variable in question. This extends the idea that, in graphical terms, a variable can only affect another if the former is an ancestor of the latter. When counterfactuals are involved, some of those ancestors become irrelevant (by virtue of the exclusion operator). For example, in a simple chain graph such as $X \\to Z \\to Y$, $X$ is an ancestor of $Y$, but it is not a (counterfactual) ancestor of $Y_z$, because under $do(Z)$, $X$ cannot affect $Y_z$. Similarly, $Z$ is an ancestor of $Y$, but for $Y_x$ the counterfactual ancestor is $Z_x$, not $X$ or $Z$. As suggested, we will include a brief discussion of this after the definition; your suggestion is appreciated.\n\nAs you point out, we did not mention in the main paper that ctf-calculus subsumes do-calculus. It is suitable for any task where the latter is complete, such as identification from observational distributions. We will add Lemma C.1 (in the supplemental material) “ctf-calculus subsumes do-calculus” and a brief discussion to the main text to make this fact clear to the reader. \n\nWe see your point about Figure 3, and that the meaning of the columns and edges can be confusing in the middle of so many models where elements have a well-defined meaning. In this figure, the gray boxes represent data-generating mechanisms that transform a specific unit $U=u$ into a counterfactual event over the observable variables. Each rectangle is a copy of the mechanisms of the structural causal model. Depending on the counterfactual of interest, the mechanisms share some functions (e.g., $f_z$ and $f_y$ in (a)), redefine others ($f_x$ and $f_x'$ in (a)), or contain functions that require the evaluation of a separate set of mechanisms (e.g. $f_x'$ in (b)) to compute a nested counterfactual. Following your suggestion, we will provide a better description of the graphical elements of the figure in the manuscript, thank you.", "claims_and_evidence": "Yes, proofs for all theorems were included in the supplementary.", "methods_and_evaluation_criteria": "Examples were provided in the paper to illustrate how the counterfactual calculus can be applied to identify counterfactual queries.", "theoretical_claims": "I reviewed the proofs in Appendix B.1, B.3, B.5, and C.2 in detail and skimmed through others. They look correct and rigorous to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper proposes a sound and complete method for testing independencies for general counterfactual variables, which improves upon the previous methods including [Balke & Pearl, 1994] (not complete), [Shpitser & Pearl 2007] (not efficient), and [Richardson & Robins, 2013] (restricted to a single world). \n\nMoreover, the paper proposes sound and complete rules for identifying counterfactual queries, which complement the previous algorithmic method in [Correa et al., 2021a]. As mentioned in Appendix E, this is an important contribution since the rules (counterfactual calculus) bring the potential to solve problems under more general setups.", "essential_references_not_discussed": "I'm not aware of any missing references.", "other_strengths_and_weaknesses": "- The paper is clearly structured and well-written. \n- The supplementary contains a huge discussion on the connection to other related frameworks.\n- The paper also included the examples (end of Sec. 3), which makes it easier for me to see how the rules can be applied.", "other_comments_or_suggestions": "- Figure 3 is a bit confusing to me since the meaning of the two columns and edges is missing. \n- While this was shown in the Appendix, I think it is worth mentioning in the main paper that counterfactual calculus can remove interventions (do operations) whenever they can be removed using do-calculus. Otherwise, it's unclear how it is complete for identification given the observational distributions. \n\nTypos:\n- Page 2: \"We base our analysis on the Structural Causal Model (SCM) paradigm *(?)Ch. 7]pearl:2k.*\"\n- Page 6, \"Algorithm 1: For each *edge* $V \\in \\textbf{V}$\"    ->   variable?\n- Supplementary Definition D.2:  \"conditions ??\",   Section E Q1: \"(see (?)Sec. 1.3]bar:etal2020 for details\"", "questions_for_authors": "Could you please provide some intuitions for the (counterfactual) ancestors in Definition 2.4? Maybe include it after the definition.", "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": "enPrOeHLRX", "reviewer": "Reviewer_JAeX", "summary": "The paper presents a novel framework for counterfactual reasoning using graphical models. The paper introduces two key contributions: Ancestral Multi-World Networks (AMWN) – a new graphical representation for counterfactuals, and Counterfactual Calculus (ctf-calculus) – a set of rules for transforming counterfactual expressions. The work extends Pearl’s do-calculus, allowing for more efficient and general counterfactual reasoning. \nAMWN is a graphical model that encodes counterfactual independence relationships. It builds upon Structural Causal Models (SCMs) and replaces traditional Twin Networks, which are computationally expensive. The paper provides an algorithm to construct AMWNs, ensuring they are both sound (correct) and complete (able to capture all relevant relationships). The model enables efficient testing of counterfactual independence using d-separation.\nCounterfactual Calculus (ctf-calculus) is a set of three transformation rules that generalize do-calculus to counterfactual settings: First, the consistency rule relates observations and interventions. Second, the independence rule uses d-separation to infer counterfactual independence. Third, the exclusion rule eliminates interventions that do not affect a variable.\nThese rules allow counterfactual expressions (e.g., $P(Y_x | X=x’)$ ) to be rewritten in terms of observable or interventional probabilities.\n\nThe approach is computationally efficient, reducing the complexity of counterfactual queries compared to existing methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work, providing feedback, and asking questions.\n\nWe refer next to the research mentioned in the review. Also, thank you for sharing the references. We describe the work as we understand it, but we would be happy to hear more about it from the reviewer. Regarding Ma et al (2022), the paper makes assumptions on the latent variables’ prior and the availability of an auxiliary variable. Based on these, they aim to identify the SCM that generates the data. They integrate the information on the SCM into the optimization process of a generative model to produce explanations. Compared to our approach, there are similarities in modeling the data-generating process as an SCM and then inferring counterfactual quantities based on the assumptions made over the SCM. On the other hand, in our framework, we make no assumptions about the distribution of the latent variables or the functional form of the mechanism of the SCM but assume a known causal graph. This setting is called non-parametric in the literature, which motivated Pearl’s Biometrika’s 1995 paper, where he introduced the do-calculus. Moreover, we do not attempt to identify the SCM as a whole but to identify particular (counterfactual) queries of interest in the form of independence constraints or probabilities. These are indeed the two main contributions of our paper, namely, graphical criteria and calculus for counterfactual identification.\n\nVo et al (2023) seems to focus on producing examples that counter the original outcome produced by a model (e.g. classifier). Moreover, it seems the validity of the counterfactual is measured in terms of whether the outcome can be overturned by the generated example. We believe our work is not directly comparable here since it seems this work does not address the causal structure of the underlying data-generating process. Having said that, we would be happy to understand the reviewer's suggestions, in case it implies some subtle connection we may have missed based on our cursory reading.", "claims_and_evidence": "The paper presents several claims that can be summarized in two areas. First, it claims AMWN is a sound and complete method for counterfactual independence reasoning and improves on existing graphical models (e.g., Twin Networks, Single World Intervention Graphs).\nThese assertions are supported by consistency and constraint definitions, nested (and unnesting) counterfactuals, exclusion operators, and a hierarchy of counterfactual relations. These are used for the key theorem on counterfactual d-separation (independence) \nSecond, the paper presents the CTF as a generalization of Pearl’s do-calculus (Theorem 3.1), resulting from counterfactual d-separation.", "methods_and_evaluation_criteria": "The proposed methods are theoretical. They introduce AMWN as a new representation of counterfactual graphical models. The paper defines ctf-calculus as a set of inference rules using d-separation in the AMWN framework to determine counterfactual independence.\nSince the work is theoretical, the evaluation criteria consist of the proofs. This includes computational complexity analysis compared with prior methods in terms of efficiency (Twin Networks, SWIG, and Multi-Networks).", "theoretical_claims": "The key claims are summarized in three theorems, among other lemmas. Theorem 2.5 (Counterfactual d-Separation) proves that d-separation in AMWN is both sound and complete. Theorem 3.1 (Counterfactual Calculus Rules) formally establishes the transformation rules for counterfactual expressions. Theorem 3.2 (Soundness and Completeness of ctf-calculus for Counterfactual Identifiability) shows that ctf-calculus can fully characterize counterfactual identification.", "experimental_designs_or_analyses": "The paper does not include empirical experiments or simulations", "relation_to_broader_scientific_literature": "The paper extends prior work on Pearl’s do-calculus and Structural Causal Models (SCMs). It improves on existing methods such as Balke & Pearl, 1994); AMWN overcomes the incompleteness of d-separation in Twin Networks; Richardson & Robins (2013), for which AMWN handles multiple interventions simultaneously; Shpitser & Pearl (2007); for which AMWN avoids the exponential graph explosion problem.\nThe literature review is strong, but an empirical comparison with recent causal inference models (e.g., deep learning-based causal models) could be useful.\n\n**** POST REBUTTAL\n\nthank you to the authors for their answer. Their comments can be helpful in improving the paper. I will maintain my positive score for this paper.", "essential_references_not_discussed": "I would suggest to discuss the counterfactual d-separation concept in the context of other graphical models criteria of independence. See for instance Ma et al, (2022), Vo et al. (2023) , etc.\n\nMa, Jing, et al. \"Clear: Generative counterfactual explanations on graphs.\" Advances in neural information processing systems 35 (2022): 25895-25907.\nVo, Vy, et al. \"Feature-based learning for diverse and privacy-preserving counterfactual explanations.\" Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.", "other_strengths_and_weaknesses": "Two observations on this work. First, the paper provides a general framework for counterfactual reasoning, unifying different causal inference tools. Second, the method is computational efficiency as AMWN provides a polynomial-time method for counterfactual independence testing.", "other_comments_or_suggestions": "Just a suggestion to rename the heading Any sep. in Table 1 for something more informative. Alternatively, it could be added to the caption.", "questions_for_authors": "How does your proposed idea compare to the works listed above?", "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:

Meta-review: This paper introduces AMWNs, a novel graphical framework for counterfactual reasoning that is both sound and complete for d-separation-based counterfactual independence. Additionally, it proposes a counterfactual calculus that generalizes Pearl’s do-calculus to handle counterfactual queries, filling a longstanding gap in the causal inference literature.

All four reviewers gave positive assessments, highlighting the paper's theoretical depth, rigorous proofs, and its significance in advancing counterfactual inference. The proposed framework addresses limitations in Twin Networks and SWIGs by avoiding graph blow-up and supporting general counterfactual transformations. The rebuttal addressed the main concerns raised by reviewers.

While the paper does not include experiments—understandable for a theoretical contribution—some reviewers noted that clearer visualizations (e.g., Figure 3), improved explanations of certain concepts (e.g., nested ctf reduction), and minor editorial refinements could enhance accessibility. Additionally, a brief discussion comparing AMWN's d-separation with other graphical independence criteria could strengthen the broader contextual framing.

Overall, the paper presents a significant contribution to the theory of causal inference. I recommend acceptance.
Decision: Accept (spotlight poster)