Causal Identification with Matrix Equations
Authors: Sanghack Lee
Elias Bareinboim
Venue: NeurIPS 2021 Oral (2021)
Keywords: Causal Inference
Causal Effect Identifiability
Causal Effect
Causality

Abstract: Causal effect identification is concerned with determining whether a causal effect is computable from a combination of qualitative assumptions about the underlying system (e.g., a causal graph) and distributions collected from this system. Many identification algorithms exclusively rely on graphical criteria made of a non-trivial combination of probability axioms, do-calculus, and refined c-factorization (e.g., Lee & Bareinboim, 2020). In a sequence of increasingly sophisticated results, it has been shown how proxy variables can be used to identify certain effects that would not be otherwise recoverable in challenging scenarios through solving matrix equations (e.g., Kuroki & Pearl, 2014; Miao et al., 2018). In this paper, we develop a new causal identification algorithm which utilizes both graphical criteria and matrix equations. Specifically, we first characterize the relationships between certain graphically-driven formulae and matrix multiplications. With such characterizations, we broaden the spectrum of proxy variable based identification conditions and further propose novel intermediary criteria based on the pseudoinverse of a matrix. Finally, we devise a causal effect identification algorithm, which accepts as input a collection of marginal, conditional, and interventional distributions, integrating enriched matrix-based criteria into a graphical identification approach.

Causal Identification with Matrix Equations
Sanghack Lee Graduate School Data Science Seoul National University
Elias Bareinboim
Department of Computer Science Columbia University New York, USA eböcs. cowwmbia. edu
Seoul, South Korea sanghackésmu.
Abstract
Causal effect identification is concerned with determining whether causal effect is computable from a combination of qualitative assumptions about the underlying system (e.g., causal graph) and distributions collected from this system. Many identification algorithms exclusively rely on graphical criteria made a non-trivial combination of probability axioms, do-calculus, and refined c-factorization (e.g-- Lee & Bareinboim, 2020). In a sequence of increasingly sophisticated results, it has been shown how proxy variables would not be otherwise recoverable in challenging scenarios through solving matrix equations (e.g., Kuroki & Pearl, 2014; Miao al., 2018). this paper, we develop a new causal identification algorithm which utilizes both graphical criteria and ma- trix equations. Specifically, we first characterize the relationships between certain graphically-drive formulae and matrix multiplications. With such characteriza- tions, we broaden the spectrum of proxy variable based identification conditions and further propose novel intermediary criteria based on the pscudoinverse of a matrix. Finally, we devise causal effect identification algorithm, which accepts input collection of marginal, conditional, and interventional distributions, integrating enriched matrix based criteria into a graphical identification approach.
be used to identify certain effects that
Introduction
Cause and effect relations one of the most common types of knowledge sought after throughout the empirical sciences. These relations are one of the main ingredients the construction of stable explanations, and usually underpin robust and generalizable decision-making strategies [9 26
There is a growing literature that aims to systematically find causal relations by fusing observations, experiments, and substantive knowledge about the phenomenon under investigation [19
3 20
Formally, the inferential target usually appears as the effect of a set of variables do(X = x) on another set of variables Y, which is written as Pyy do(x)) data-generating processes are commonly expressed as a causal graph G over endogenous variables V. There different lines of investigation that aims establish the quantity Px(y).
(y)). Assumptions about the underlying
First, one line of investigation attempts to exploit the non- nor-parae constraints encoded & to determine whether the quantity (y) (i.e., query) is uniquely computable from the different available distributions. For instance, Pearl's is celebrated method known as do-calculus provides a symbolic way of determining whether query be identified from G and observational data P(V) [8] A number of necessary and sufficient conditions were developed for systematically determining the
identifiability status of the query from observational data [8 29 23 9 For example, the causal effect Pa Py()) in Fig. ia identified by a back-door criterion as Pa(y) Σ., P(ylæ, u) P(u). Further methods were developed to identify the query from combination of observational and experimental distributions 2 [4 12 []]. The key ideas behind these methods are (i) to decompose the given causal query into standard factors (following Tian's c-factorization.
29
leveraging the graphical
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

W
W
(a)
(b)
(c)
(d) g
Figure 1: Causal graphs: (a) with a back-door condition; (b) with W as proxy for U: (c) with proxies W and Z for U. (d) A causal graph where causal effect (v() can be computed by estimating each of Pa. (t) (light blue, left) and Pr, (y) (light red, right) using MGT criterion.
constraints, and (ii) identify these factors individually, matching one of the available distributions. We call this the factorization-busee approach.
Another line of investigation attempts exploit assumptions about the relationship between unob- served confounders and the observable variables through the idea of proxy variables [5]
g
TO T5 32)
These methods rely the cardinality and complexity of these relationships, which will possibly lead to the invertibility of certain matrices. The focus is usually on local conditions involving the treatment X, the outcome Y. and the proxies W, Z for the set of unobserved confounders U; for example, see Fig. Tb Note that since U is unobserved, the effect of X on Y, i.e., P, is provably identifiable by standard graphical methods discussed earlier. Still, if the distribution of the proxy given the unobserved confounder is available P(W)U), in addition to P(X, Y, W), the quantity (v) can be computed under the invertibility of PUW)U), matrix representation of P(W U) where P(W)U),, = P(w;lu;) (see Eq. ( for detail). In case of Fig. Ic the causal effect (x is identified from P(X,Y N.YYY.W. W, Z) through the following
(2(y) = P(ylZ,z))((N 2,
(1)
where P[W 2, x) has rank matching the size of domain of the unmeasured confounder U. Al- though typically not framed in terms of identification with multiple datasets, this setting corresponds
to identifying Ps (y) with, e.g., marginal distributions {P(X, Y, P(W: X, Z)} or conditional
distributions Z P(W) Z, x), P(W)). We call this the proxy approach
Despite all the power and successes achieved by the factorization and proxy approaches. there exist still interesting cases not covered by any of them individually. To witness, consider the causal graph in Fig. [d and first notice that the effect is not identified from each approach. On the other hand, we combine both approaches, we are able to obtain the causal effect is identifiable and given by,
Px = Px(, = E, Pr (t) = =. PP 21, tPP x1,
(z2) (PWW)]] (P
x2) P(We))
where Pt.,, (v) and Pa. (t), the two factors of the query, are individually identified with the help of the proxy approach, i.e., Eq. I
Our goal this paper explicate how this can be accomplished from first principles. More broadly, we will develop flexible and general graphical identification approach that combines both the factorization and matrix equations (the underpinning idea of proxy-based methods). More specifically, our contributions are follows:
We connect the graphical and matrical approaches by characterizing matrix equations of probability distributions driven by graphical constraints in causal graph. This leads to better understanding of the identification through solving systems of equations.
2. Building on this new characterization, we generalize proxy-based criteria and devise novel intermediary pseudoinverse criteria so as to identify causal effect by utilizing the general inverse of a matrix and diverse collection of distributions.
We focus on discrete variables. Detailed discussion on a continuous case can be found in 15
We refer this
identification condition MGT criterion where the acronym MGT comes from the surnames of the authors in 15
'Recent work in this line of research use the term proximal causal inference (PCI) 25 27 33
27
generalizes the results in [5] to allow observed confounders well. (25 considered combining graphical and proximal approaches, similar to the motivational example.

---

3. We develop general identification algorithm that amalgamates graphical and matrical approaches. returning an identification formula for a causal query given a causal diagram and a set of marginal, experimental, and conditional distributions. We show that this method subsumes current state of the art in the literature.
2 Preliminaries
We follow notational conventions from literature on causal inference. We denote variable by an upper case letter Y, and its value is denoted by its corresponding lower case letter y in the domain Xy. A set of variables will be denoted by a bold capital letter Y with its value y. We may use U, instead of U, to emphasize the union of two disjoint sets. Given Z S W, w Z denotes the value of W consistent with w. Let a/ B (A B, a B) which retains B as set of variables and values of a excluding B. Without loss of generality, we refer Pz (W) a distribution. We may employ @ compared obxervational conditional to emphasize W 2 0, experimental or interventional Z
= 0, and marginal if Z ROWWW WUW'S S
We employ structural causal models (SCMs) I9 Ch. 7] as the semantical framework to represent a domain of interest. An SCM . is a quadruple (U, V. P(U). F). A set exogenous variables U, which follows P(U), is determined by factors outside the model. V is set of endogenous variables whose values are determined by functions F = [fi]vee such that Vi + f<(pa,. u,) where PA, VVVV) and U; U. Further, do(x) represents the operation of holding set X to a constant x regardless of their original mechanisms. Such intervention induces a submodel MM. which is M with fx replaced to x for X X. The distribution over V induced by the submodel is denoted by Px PV).. We may employ letter Q to denote an interventional distribution, e.g., Q = Pr-
Each SCM (model, for short) induces causal diagram (or causal graph) G (V.E), where each type of edge represents a different causal relationship among the variables: (i) X->Y if X is used as an argument of fy; and (ii) X++Y if Ux and Uy correlated. Given causal diagram G. familial relationships among its vertices are denoted by pa and an for parents and ancestors, respectively. Further, An is set of ancestors including its argument as well. We denote by 9xz an edge subgraph of & which removes edges incoming to X and outgoing from Z. Causal relationships among other variables are captured in G\ which is the subgraph of G over V.X. A vertex induced subgraph is denoted by 9 [[V'] where V C V. Causal effect identification relies heavily on standard graphical constraints imposed by causal diagram such as d d-separation (reading off conditional independence from the graph. [30 and do-calculus (equivalence among interventional probabilities) [8] which we present in the Appendix for completeness.
The latent projection (or projection, for short) of causal diagram is a causal diagram retaining the causal relationships among a subset of variables. We denote by G(V') the latent projection of onto V C V, the causal graph over V [I] Conditional independence (CI) statements and do-calculus IS on a projection are valid in G. vice versa. We formally define latent projection in
the supplementary material. The omitted proofs and derivations are also provided in [13
3 Characterization of Matrix Equations of Graphical Constraints
In this section, we present characterizations of graphical constraints in a given causal diagram G. leading to equations expressed as the multiplication of matrices. The characterizations will further advance our understanding underlying system compared to simple equivalence relationships such as conditional independence and do-calculus. To begin with, we denote by P the matrix representation of a distribution P where free outcome variables are rows and free condition or intervention variables correspond to columns. For instance, Pa, PC, C,, d) is [Ecl x [ matrix and P, (A, b|C, d) is a [A x [Ecl matrix. Further, we may use and / to represent two disjoint subsets such that B = B' B".
the constraints imposed over the distributions generated by the
Chain Rule with Conditional Independence The definitions of conditional and marginal distribu- tions naturally lead to a sum of a product of probabilities. Let Q = Pr be an arbitrary interventional distribution. Let A, B, C, and R be disjoint. A marginal probability over thain-rule-induced multi-
3

---

plication is expressed as
Q(a,b'cc) = Σ Q(alb, c)Q(jcc = c,)bi,,B",))((B"" b'(c).
Considering conditional independence, we can further enrich such a characterization.
Lemma 1. Given a causal diagram G. let Q = Pr for some r E IR where R ç V. Le D A B,C,E) and (E B C,D in
A, C, E be disjoint subsets of V If B", CB"",''""BBBbbbll
G R. then, ((A,b'c,,,,c) =
The lemma emphasizes the condition under which the result of multiplication is matrix not just row or column. A special case of the lemma is appeared in MGT criterion where the inverse of matrix multiplication P(W) Z, x) P(W[U, P) ((U)Z,)) is utilized so cancel out unknown distribution P(W = (( U, x))
Adjustment Criterion Given graph G and a causal effect of interest Px(y), the adjustment criterion 24 seeks set of covariates S V Y, called an adjustment set for a causal effect Py(y). which grants the following expression, Px(y) Σx P(y|x, z) P(z). Adjustment criterion generalizes back-door criterion [9.. Its matricized expression with employing Q = P, is
Qx(y)= Σ ((vlx, Qy/|x, ZZ)
This simple expression plays a central role in the identification with proxy variables.
In many settings, the left hand side (LHS) is the query of interest and two terms in the RHS usually available or to be inferred using other available quantities. However, substituting value y with Y, we can further yield (under invertibility assumption) Q(Z) Q(Y|x, x, -x-1Qx(Y+ (Y), which restores the covariate distribution of interest given a causal effect and conditional distribution.
decomposes causal effect Px(y) into the sum-product of c-factors (simply, factors) with respect to the given causal diagram G. Without loss of generality, let X be minimal such that no X' Ç X satisfies Px((y) + Px(y) (i.e., overriding X by an nX). For any projection H of G that preserves XU Y, the following holds:
C-Factorization C-factorization 22
Px(y)
Σ Px(x+)= ytly
Σ yt Y,EC(H(Y-1)
II
Pra (y+),
where Y = An Hx Ax (Y) and C(.) is the c-component decomposition (partitioning the variables in the graph based their connectivity through bidirected edges). Given query Px(y), we let o-factors FR = {X,, } where (Y,); form the c-component decomposition of H and X, = (aa)) The general identification method under -ustrll-bservaailiity described as finding H such that each factor is identified by one of the available distributions.
[2]] can be summarily
Let us denote X1, X; U U. We focus here on the sum-product a pair of factors at some la- tent projection H. which satisfies Px. Px, (y,) Axy (yiz) where the values are consistent [12]. Now consider the summation over x, Y,. Then,
5
x
Z
Y
Pxit (y,,, (y,)z,z) Px,,,r (Z))
(a) Euler diagram
(b)
To properly represent this a matrix multiplication, we should decide which variables will become rows and columns. Two matrices to be multiplied should share only Z. and other common variables, appearing in the two terms, non-matching variables, appearing intervention in left term and outcome in right term, need to be set to constants. To help understand, we illustrate in Fig. 2a the set relationships among X,, Y,, Xj, and Y, in the case of Z X, inY Y,-
Figure 2: (a) set relationships, (b) causal graph where the numbers correspond to the regions of (a) from the left right.
Therefore, Y, Y,nX, (the shared variables other than Z) and (X;UY,) \Z (the non-matching variables) are fixed. These fixed variables are not colored in Fig. 2a As result, we can obtain submatrix of Px,, YY, (Y., Z) as the multiplication of the submatrices of Px, (Y,) and Px, (Y,) obtained via fixing variables.

---

W
(a) (w(W)
(b) (W)
(c) (W(
(d) P. (W)
(c) Pa.. (W)
Figure 3: Causal diagrams admitting single- and double-proxy settings with surrogate experiments.
Lemma 2 (Matrix Equation of C-Factorization with Two Factors), Given a causal diagram G and experimental distribution = P. where a causal effect e-factorized Qx
En Qx. (y,) (gg) in projection H of G. the effect can be represented as matrix multi- plication, Z nY,, Further, the corresponding matrix equation
(xx (rt)) X NY,) / (XX,),
We illustrate a causal graph in Fig. 2b where each variable matches each region in the Euler diagram (Fig. 2ap. With Z = {6} and for an arbitrary instantiation of variables V22 V1, V3, and V7, Psseaies (V1, U2, 17) P Pv..es,2 Vo (V1, )2) Pe,,, (Vo, 07).
In this section, we connected different graphical constraints from chain-rule with conditional inde- pendence c-factorization incruce identification formulae to matrix equations. Results presented in this section are by no means complete yet cover, to the best of our knowledge, every sum-product expression appeared in both graphical and matrical identification approaches. Nevertheless, this suite of characterizations will provide fundamental understanding of the mathematical structures involved in the identification methods with matrical expressions.
4 Generalized Proxy-based Criteria
Equipped with the characterization from the previous section, we revisit single- and double-proxy settings [ more formally, which identify a causal effect through the combination of chain rule, adjustment crite- rion (c-factorization), and inverses of matrices given an observational distríbution and additional external study involving unobserved confounder. We investigate its extension capable utilizing other types available dis- tributions. Results presented in this section is crucial in adopting matrical approaches into a factorization based identification algorithm.
external study
P(W
available
P(y. Wix)
P(W x)
fR
1
Ply.U
P(U)x)
unobserved
Uly x)
query
P.
Figure 4: Schematic for single proxy setting. Gray and red lines are for ele- mentwise matrix multiplication and ad- justment criterion, respectively.
Single-Prow Proxy Setting We illustrate in Fig. the avail- able distributions and unknown distributions, considered in Fig. [b that can lead to (z).. In the figure, a matrix multiplication A B C' is represented B 5 A & C with positions annotated. First, note that (X, Y W grants P(W U, y) P(W
U) in a causal graph 9 central, which PUW)U), If P(WIU) is invertible the three distributions Ply, U(x),, (U) and (U)) are obtained where PvulU, x)) is computed by chain rule (Lemma Then, (v) is, with @ denoting elementwise division,
(P(WIU) 2 (PWW)))'P((la)))
P(W]D)- P(U)
(3)
Ply.(lz)
P(U|=))
However, this scheme would not work in restrictive conditions such as Fig. 5a
3b
This
challenging scenario can be handled if different external study is available altogether with a surrogate
In case of W has more categorical values than U/ one can coarsen W to W' ensuring that ((W is full rank. In other words, ((W)U) has full column rank.
5

---

experiment. For example, when only Y is independent to W given U and X, the availability of an external study P(W zz), instead of P(W and surrogate experiment P.(WW) (W), in addition to the observational distribution P(Y, W, x), suffices to identify the causal effect (see for the derivations for Fig. Sa 3bj. These examples suggest that we can generalize the single proxy-based criterion to take advantage of diverse collection of external studies and surrogate experiments.
Theorem 1. Given G, let X, Y, W, U, and R. be disjoint subsets of V, Q Q= for some r Xn.
and H = R. A causal effect Pr)((y) = Qx(y) is identifiable (1) U an adjustment admissible
set for Q in Hi (2a) (Y IL W U, X)x and Q(W U, x). Q(y, W[x) and Q(Wxx) are available where Q(WjU, x) has full column rank; or (2b) (Y A W U,X) and Q(W x, Y) and Q(Y, Wxx) are available where every Q(W X. y') has full column rank for y' E Iv; (3) and Z' = (XUY) Z with z' consistent with x y such that (Z 1 W U, W Z') in Hi and U is an adjustment admissible set for Qz (W) in H.
Qz () is available for Z C
The theorem presents a sound condition to elicit the causal effect through combining various distribu- tions especially when the given situation is more restrictive.
Double-Proxy Setting We now generalize MGT criterion to utilize distributions other than the origi- nally considered observational study. MGT criterion for a suuble-proxy setting relies on the following conditions to identify Pz(y) with P(X, Y, Z, W):
P(W)
R
P(
P X
Ply
U.x)
P
P(W
Ply 2,
P.01
(CI) U is an adjustment set for (y) in 9;
(C2) Y 1 Z X in 9;
O₂ (W)
R
(C3) Z, X T W| U in 9; and
Q(WU. s')
QUZZ/S. x)
QivlU.x) x)
Q(U)
(C4) P(W x,) has rank [Ro/)-
Q x
Qlyiz/Sxx)
Q,íyi
Under these conditions, algebraic relationships be- tween a causal effect (v) and other distributions can be illustrated as in Fig. Sa where the distributions form closed loop alternating between (i) distribu- tions with an unmeasured confounder and (ii) given distributions and a query. Among the four multipli- cations, Pa (2) corresponds to an adjustment criterion (C1) so as to (g) = Pvy x) PUU)
(b)
Figure 5: Schematics of (a) MGT criterion
and (b) its generalization (simplified)
Others are due to the chain-rule combined with CI. e.g.. (C2) P (yl (U x) P U x, 2) and (C3)
P(W]L) P(W JU, x. 2). With (C4), which implies that both P(W (U) and P(U'Z X) are invertible
under coarsening of W and Z if necessary [15] the causal effect Pz (y) can be expressed as Eq. !
by subsequently rewriting P(U|Z, .)) and P(y r)), and contracting P(W) = P(W (see
[ Appendix for an illustration).
To examine the possible extension of the setting, we relax (C3), where the CI grants the use of matrix multiplication leading to chain-rule P(W) = P(W and P(W|
U X), IL W U, Z). and, ultimately, dropping (C3) illustrated respectively in Fig. 3c 3d and 3e For concreteness, consider the first relaxation (Z IL W X). The assumption grants Given that surrogate experiment Pa is accessible, and it can be decomposed as P.. = P(W)U,))P(U) PU)) where U is also an adjustment admissible set for Ps (w), then, (x(y) identified. Other two relaxations turned out to be much more challenging, yet the causal effect can be identified by exploiting different surrogate experiments or additional external study (see 133 Appendix C for detail). Motivated by these examples, we present a theorem that extends MGT criterion with varying degrees of the assumption and data collection.
P(W P(U (011Z zr. One can consider three relaxed versions of (C3), namely, (Z 1L W
XX
P
P(W]U, PP
Theorem 2 (Generalized MGT Criterion). Given a causal graph G. let X, Y. Z, W. U. C be disjoint sets of variables where R can be empty. Let Q = Ps for some r E ÆR and H G.R. Ler some S S XUZ. A causal effect Q (x) = (xr(y) is identifiable in G if. for some z, (1) U is an adjustment
(XUZ) S: (4) U is an adjusiment set for (W) in H: (5) Q(W U, U.'') is invertible; (6) Q(U) Z'),
set for Qx(y) in H. (2) (Y IL Z U, X)x (3) (W 1L S' U,S) where S'
is invertible for some Z' C Z and Qlylz/(SUs Z') x), Q(W]z/(S U Z'), x), and Qx (W) are
available. Additionally, Q(W U, /Z') is available if Z' # 0.

---

The theorem broadens the applicability of the MGT criterion an identification template to range of collection of distributions. Although the conditions involved in generalizing MGT criterion non-trivial, we can similarly draw (simplified) big picture of the generalized criterion as in Fig. 5b The key idea is relaxing the C3 condition for a set of variables while considering sets of variables (explicitly) and interventional distributions.
We have established generalized identification criteria exploiting proxy variables The purpose of both criteria aligns well with the philosophy of general identification 14 SO that they can be smoothly integrated into graphical approaches.
Pseudoinverse and Intermediary Criteria
Now, present novel identification condition for challenging setting that neither previous matrical nor graphical approaches could handle. In the setting, the probability of interest is expressed
as the multiplication of three matrices and is identifiable through employing the pseudoinverse of matrix, without an invertibility assumption. Let P()) denote the pseudoinverse of P())
Lemma (Base Intermediary Criterion). Let {P1, P2, Ps. PA} distributions. Let {P,) )i=i be their
matrix representations. If submatrices [i of (P+]i= satisfy P' = P'Pp'P's and PiPP' P/P
and P are given, then, P (P)PP) (P))
Proof. By the given condition, the associativity of matrix multiplications, and the property of pseudoinverse Pplp P. P PPPP' P'z (P Pp
Although the lemma itself is rather general, we concretely characterize distributions satisfying Lemma with respect to chain-rule (Sec. 5.1 and c-factorization (Sec.
5.1 Chain-Rule-basedl Intermediary Criterion
We start by characterizing an intermediary criterion with a chain-rule using a simple illustrative example. Let Q be an arbitrary interventional distribution. One way to decompose Q(a, b, c d) into three probabilities is Qalb, e, (b)( (cl(d. Let probability of inter- est its marginal Q(ald) Es. ((a b, cld) where the following distributions are available: Q(BIC, d), Q(ACC, d), and ((B(d). If the first term Q(alb, c, equal to Q(al ba d). the term can be multiplied by Q(bld) = E. Qblcc (cl(d) Hence, the matricized expression becomes,
Figure 6: Causal diagrams where chain- rule intermediary criterion is applica- ble to identify P(ald) given d(a(C,d). P P(BIC,d) and P(Bld).
Q(A(C,))
QAAdd) Q(A d) Q Q(BIC, Q (BCC
Q(Bld)
for any E Dp. Two illustrative examples where this expression is applicable (i.e., (C JL B) in G) are shown in Fig. 6 Now, propose a chain-rule intermediary criterion.
Lemma 4 (Chain-Rae Rule Intermediary Criterion). Given causal diagram G, ler A, B, C, C. and R be disjoint subsets of V with D and can be empty. Let B B' U B" and C C= C C" where B' and C' are not emply. Given interventional distribution Q Pr. iC 11 A C in GRR and
Rnd Q(a, b", tr, c" d) = =bb Q(a[b, c, d)Q(ble, d)Q(cld)) then,
Q(A,b", d" Q(A,A"IIC dd Q(B',b"IC', c" d), "i).dt(BBBBBbb (BB''",c"ldd) c"(d).
*As mentioned earlier. 27 extends the MGT criterion by allowing observed confounders C.. Roughly, this understood replacing U in Fig. with U and C where C' not necessarily marginalized out that the resulting distribution may contain C. 'n case of continuous variables. ((B can be understood as linear operator on Hilbert spaces. See [6 for more detailed discussion the existence and uniqueness of pseudoinverse for bounded linear operator.
7

---

Additional CI allows the criterion to return a matrix, which can then be nested into other equation.
Corollary 1. Given Lemma f if (D
A, B" C) and (D B C) in G.R. then
Q(A,b", c D) = Q c"") Q(B', b"""", c'") Q(B',,",
These results advance current knowledge of the causal or non-causal identification with fragments of information presented as conditional distributions, which is often under-studied.
5.2 C-Factorization-basel Intermediary Criterion
We proceed to characterize an intermediary criterion where a matrix equation corresponds to c-factorization resulting three factors, extending the case of pair of factors (Lemma Concretely speaking, we are interested in the matrix form of
Pxc (ye)
Σ Px. (y:) Pxx (vx) Σ Px. Pxs
where Z S X, NY, and W C X, Y are disjoint sets of variables be marginalized (the order among the three factors is irrelevant since they are invariant up to renaming.) In addition, available distributions are the form Px, (Y,), Px., \Y, (Y ZZ), and Px,,, (Y,s) (W)
Theorem 3 (C-Factorization Intermediary Criterion). Let G be causal diagram and Q Pr- Let Qxe (ye) be c-factorized as Eq. 44.. Let X be a subset of Xx excluding the rest five sets, (Y, Y, Yk. X,, X.). Y is similarly defined. If S (X; n (Yx))X and W C n Ys, then (ye! V a submatrix of Qx,(,,) becomes Qx x x
_X,
Q xx/xt (y./Yt) = Q(x,)y,)) ((ri)) A2) Qx,/w(y,/2) Q (x ((yga (W)Z).
The theorem imposes an additional constraint that Z should be disjoint to X2 compared to naively interpreting the three-matrix multiplication as two individual matrix multiplications as seen in Lemma 2 (we depict the sophisticated set relationships among W. Xs, Ys. and Z in Appendix DD (3) Briefly speaking, given that the summation over W nested (Eq. (4 D. (X, U ,Y,,), ) W is fixed along with Y, xx Thus, X; n Y, X can't be part of Z. In other words, the constraints imposed in the original expression asymmetrically affect what Z can be but not what W can be.
\
The implication of this result is immediate. It was previously unknown whether the identification procedures by Lee and Bareinboim 12 (GID-PO) and Lee and Shpitser [T]] (Lemma 3 and 6) taking marginal and interventional are complete. Now, we show a negative result.
Proposition GID-PO [2] and Lemma and [T are not complete.
Proof. Consider causal graph X A B Y and distributions P(X, B), P(A. B). and P)A,Y). (v) is identified as ( A) A)tP which is not solvable by 12 11
In this section, we developed novel intermediary criteria by characterizing both chain-rule and factorization with respect to matrix mulriplications of three matrices exploiting the pseudoinverse, which has never been employed in the context of causal identification the best of our knowledge.
A Unifying Causal Identification Algorithm
We present causal identification algorithm ID-ME (Alg. D taking collection of marginal, con-
ditional, and interventional distributions and causal graph G approaches such as generalized proxy-varte variable based criteria (Sec. andd [ 10 15) intermediary criteria (Sec. D.. and factorization approaches 223
$ The algorithm integrates different
Taking a causal query (y), causal graph G, and distributions DD, it refines the given query by removing redundant interventions based on Rule 3 of do-calculus, i.e., Px(y) (x) for
"We omit some details on whether some variables are tixed (e.g.. PB( versus Pa (B)). Without loss of generality, every distribution contains no redundant conditions and interventions, which can be obtained through repeatedly applying rules of do-calculus.

---

Algorithm 1 ID-ME
1: function ID-ME(X. y. D)
Input: x, y value assignments for query Px(y); a causal diagram; TD collection of distributions
Output: a formula for Px(y) made with or FAIL.
2:
X, G' f- (nnx((Y))))))) ( x, G[An
X--expandCG, D) unless ID unconditional 4: F+ +- For TTD is unconditional and nonmarginal else U(Forea IXY
3:
5:
F", F" <- empty dictionary, F+
6:
for all Px,(,,) E F" and (P&(V ED Y. x, & CZUV do update FF,F" with ID-RC(Px, xx, (Y.), G. P2(V
7:
8:
for all Px, (Y.) E F" do update F,, F. with PROXY(Pxx (Y.).
9: repeat update F", FF with CF-INT(G', F", and CF-INV(G', FIIVIG",F',F'" FF,F") until F' not changed
10: return exact-cover(G", F=)
minimal subset X' C X. Further, G' a copy of causal graph is obtained through pruning 9 only to the ancestors of Y. However, note that the original G is kept intact be used the proxy criteria later where proxies can be non-ancestors of Y. e.g., Fig. Tb Then, the algorithm proceeds the following three parts: 1) expanding the given distributions D; 2) c-factorizing the query (y) and identifying each factor; and 3) combining identified c-factors IF' to elicit the causal query.
First, the algorithm expands the given distributions (expand in Line 3). A given conditional distri- bution Pz ( (T' can be understood as a distribution Pz P2(V') under a selection bias, which might hinder identification of a e-factor. By multiplying another distribution equal to, e.g., (T" we can obtain distribution with more outcome and less bias, (V'V', T'). Chain rule closure [II] describes a state of set of distributions where no new distribution with a smaller condition can be added to the collection. Function expand contains procedure for chain rule closure along with chain-rule matrix inversion (Lemma D and chain-rule intermediary criterion (Lemma enjoying the matrical approach especially relevant to conditional distributions.
The next part enumerates c-factors (Line 4) and attempts to identify every c-factor based on available distributions (Lines 5-8). An algorithm for identifying c-factor given a single unconditional and non- non-marginal distribution has been thoroughly studied (e.g., Identify 20 and ID
(3) ), and is a
building block for general identification 22 14]. Dealing with a marginal or conditional distribution,
one should consider (i) whether the condition the conditional distribution in ID can be negligible with respect to identifying the c-factor or (ii) whether matrix equations can be utilized (e.g., simple inverse or generalized proxy criteria). ID-RC (Line 7) is an identification module modified to handle and PROXY (Line 8) refers to generalized proxy criteria.
conditional distribution
The last part (Lines 9-10) attempts to map the identified c-factors to the causal effect (y Once subset of c-factors are identified from the previous step, the algorithm proceeds to examine whether some of the unidentified factors in FF" can be further inferred from the individually identified factors F', i.e.. whether a simple inverse (CF-INV implementing Lemma 2 or the intermediary criterion over c-factors (CF-INT implementing Thm. 3 can be invoked (Line 9). Then, we finally elicit a causal effect if a valid combination of identified c-factors exists (exact-cover in Line 10 checking Eq. 2
The algorithm coherently integrates existing methods and the newly developed machinery in the previous sections. Whenever ID-ME returns a formula, evaluation the formula leads to the quantity (y)).. Further, ID-ME strictly subsumes the union of aforementioned methods in way that not only returns it a formula whenever some of the methods returns one given the same problem instance but also can output novel formulae for the problems that cannot be answered by any of them as demonstrated through examples and by Prop.
Theorem 4. ID-ME is sound.
Theorem 5. ID-ME strictly subsumes proxy criteria R 75 GID(-PO) 14 12 mID, elD M.
Finally, we discuss the time complexity of ID-ME through examining the complexity of algorithms concerning subset of problem instances ID-ME can handle. First, the state of the art identification conditions with distributions marginal, experimental, but unconditional 122 involve finding latent projection where the corresponding set of e-factors are identified. It is conjectured that requires time exponential in V [1]] Next, dealing with conditional distributions through expanding

---

them takes time exponential in V (e.g., chain rule closure MT].. As result the algorithm generally runs in time exponential in [ which we speculate that this complexity reflects a fundamental trade off between expressive power and tractability within causal inference, as already observed in 12
Conclusion
In this paper, we studied the use of matrix equations in causal identification given general distributions. In particular, we characterized matrix equations made of distributions driven by graphical constraints, deepening our understanding on algehraic constraints imposed by the graph (Lemmas [ and 2 in Sec. 3 We generalized proxy-based identification methods cover broad spectrum of problem instances beyond the identification problems with observation study and optional external study (Thms and 2 in Sec. F. We developed novel intermediary criteria that identify a query by utilizing the pseudoinverse of the center matrix within the multiplication of three matrices (Lemma 4 and Thm. B in Sec. 5.. Finally, we provide causal identification algorithm (Alg. | in Sec. 6 integrating several existing identification results to produce identification formula for causal query given a causal graph and distributions that can be marginal, experimental, and conditional harnessing the power of matrix equations and (pseudo)inverses, As future research direction, it will be crucial to devise a statistically efficient estimator for identification formulae involving matrix inversion.
Acknowledgments and Disclosure of Funding
Sanghack Lee supported by the New Faculty Startup Fund from Scoul National University. Elias Bareinboim was supported in part by funding from the NSF, Amazon, JP Morgan, and The Alfred P. Sloan Foundation.
References
[1] S. Banerjee and A. Roy. Linear Algebra and Matrix Analysis for Statistics. Boca Raton: Taylor Francis, 2014.
[2] E. Bareinboim and Pearl. Causal inference by surrogate experiments: z-identifiability. In N. de Freitas and K. Murphy, editors, Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 113-120, Corvallis, OR, 2012. AUAI Press.
[3] E. Bareinboim and J. Pearl. Causal inference and the data-fusion problem. Proceedings the National Academy of Sciences, 1 01577455-33523 2016.
[4] E. Bareinboim and J. Tian. Recovering causal effects from selection bias. S. Koenig and B. Bonet, editors, Proceedings of the 29th AAAI Conference Artificial Intelligence, pages 1475-3481, Palo Alto, CA, 2015. AAAI Press.
[5] R. Carroll, D. Ruppert, L. Stefanski, and C. Crainiceanu. Measurement Error in Nonlinear Models: A Modern Perspective. Boca Raton: Chapman & Hall/CRC, 2nd edition, 2006.
[6] O. Dukes, I. Shpitser, and E. J. T. Tchetgen. arXiv:2109.1 11944.
Proximal mediation analysis. 2021.
[7] D. Geiger, T. Verma, and J. Pearl. Identifying independence in Bayesian networks. In Networks, volume 20, pages 507-534. John Wiley, Sussex, England, 1990.
[8] S. Greenland and T. Lash. Bias analysis. In K. Rothman, S. Greenland, and T. Lash, editors, Modern Epidemiology, pages 845-380 Lippincott Williams & Wilkins, Philadelphia, PA, 3rd edition, 2008
[9] Y. Huang and M. Valtorta. Pearl's calculus of intervention is complete. In R. Dechter and T. Richardson, editors, Proceedings of the Srrenty-Sccond Conference on Uncertainty in Artificial Intelligence (UAI 2006), pages 217-224. AUAI Press, Corvallis, OR, 2006.
[10] M. Kuroki and Pearl. Measurement bias and effect restoration in causal inference, Biometrika, 101:423-44 437, 2014.
10

---

[11] J. R. Lee and I. Shpitser. Identification methods with arbitrary interventional distributions as imputs, 2020. urXiv:2004.01157.
[12] S. Lee and E. Bareinboim. Causal effect identifiability under partial-observabiiiyy In Pro- ceedings of the 37th International Conference on Machine Learning, volume 119. PMLR, 2020.
[13] S. LLee and E. Bareinboim. Causal identification with matrix equations. Technical Report R-70, Columbia Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University, 2021.
[14] S. Lee, J. D. Correa, and E. Bareinboim. General identifiability with arbitrary surrogate experiments. In Proceedings of the Thirty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence, Corvallis, OR, 2019. AUAI Press.
[15] W. Miao, Z. Geng, and E. J. Tchetgen Tchetgen. Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika, 105(4))987-993, 2018. ISSN 0006-3444.
[16] M. Z. Nashed. Generalized inverses, normal solvability, and iteration for singular operator equations. In L. B. Rall, editor, Nonlinear Functional Analysis and Applications, pages 311 359, Academic Press, 1971.
[17] Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, CA, 1988.
[18] J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669 090066666668,,6 1995.
[19] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000.
[20] Pearl and D. Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, 2018.
[21] I. Shpitser. Appendum "on the validity of covariate adjustment for estimating causal effects". 2012.
[22] I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semi- Markovian causal models. In Proceedings The Twenty-First National Conference on Artificial Intelligence, pages 1219-1226. AAAI Press, 2006.
[23] I. Shpitser and J. Pearl. Identification of joint interventional distributions recursive semi- Markovian causal models. In Proceedings of the Twenty-First National Conference Artificial Intelligence (AAAI 2006), pages 1219-1226. AAAI Press, Menlo Park, CA, 2006.
[24] I. Shpitser, T. VanderWeele, and J. Robins. On the validity of covariate adjustment for estimating causal effects. Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 527-536. AUAI, Corvallis, OR, 2010.
[25] Shpitser, Z. Wood-Doughty, and E. J. Tchetgen. The proximal id algorithm, 2021. arXiv:2108.068
[26] Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search. MIT press. 2000.
[27] E. J. T. Tchetgen, A. Ying, Y. Cui, X. Shi, and W. Miao. An introduction proximal causal learning, 2020. arXiv:2009.10987
[28] J. Tian. Studies in Causal Reasoning and Learning. PhD thesis. Computer Science Department, University of California, Los Angeles, CA, November 2002.
[29] J. Tian and J. Pearl. A general identification condition for causal effects. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pages 567-573, Menlo Park, CA, 2002. AAAI Press/The The MIT Press.

---

[30] T. Verma and J. Pearl. Causal networks: Semantics and expressiveness. In Proceedings of the Fourth Workshop on Uncertainty in Artificial Intelligence, pages 352-359, Mountain View, CA. 1988.
[31] T. Verma and J. Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence (UAI 1990). pages 220-227, Cambridge, MA, July 1990.
[32] Y. Wang and D. M. Blei. The blessings of multiple causes. Journal of the American Statistical Association, 114552))1574-1598 2019.
[33] A. Ying, W. Miao, X. Shi, and E. J. T. Tchetgen. Proximal causal inference for complex longitudinal studies, 2021.
12


Reviews:
[{"review_id": "kk7m0Tc-hYE", "reviewer": "Reviewer_9UEy", "summary": "This submission presents a unified theoretical view of graphical and matrix-based approaches to nonparametric causal identification. The authors use this unified view to produce a new identification algorithm that is sound, and covers a number of existing proxy-variable and observational/experimental identification algorithms. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While some theoretical arguments were challenging to follow (likely because of the condensed format of an 8 page conference paper), overall this submission makes a relevant and significant contribution to the field of causal inference. Moving from identification results based on the full observable joint distribution (as in the do-calculus) to sets of observational and interventional distributions is of practical value. My understanding is that this extends the existing identification algorithms using observational and interventional data to settings where the sets of observational variables are disjoint, as in the Kuroki and Pearl proxy variable setting.\n\nWhile my impression of the work is generally very positive, I think some changes could be made to make the content easier to contextualize in the literature. For example, I would suggest adding a table that describes how ID-ME relates to recent identification algorithms.\n\nBased on the summary of reviews at ICML 2021, it appears that previous reviewers encouraged the authors to emphasize the main theoretical results in the main body at the expense of exposition and examples. I respectfully disagree, and would rather see greater emphasis placed on intuition and examples throughout the main body of the paper and the theoretical details reserved for the appendix. Specifically, it would be helpful to clarify how graph structure relates to the resulting matrices a bit more intuitively.\n\nAs ID-ME is proven to be sound, but not complete it would helpful to understand these limitations in a bit more detail. Are there example graphs/queries the authors could point to where ID-ME does not provide complete identification results? Alternatively, do the authors expect that ID-ME is complete but that a proof of completeness is left to future work?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not addressed the societal impact, but that is appropriate given the theoretical content of the submission.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "eEEISxaYhmG", "reviewer": "Reviewer_kvzq", "summary": "This paper proposes an identification criterion which combines approaches from the graphical modeling community and matrix-based proxy variable based approaches which leverage matrix based criterion. The authors do so by first providing a characterization of the implied matrix equations of the distributions resulting from graphical criterion, then leverage these insights to define new criteria for matrix based approaches which appear to me to be a strict generalization of prior approaches and then unify them into a larger identification theory. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper to be a very strong contribution to the literature, with strong framing and a commendable level of theoretical rigor. The paper presents no experimental evidence, but given that this is clearly a theory focused paper I don't think that can be held against the work. My largest concern is that some of the entailed statistical inference procedures may be exceedingly difficult to estimate in practice. While I wouldn't recommend rejection based on this, perhaps the authors could make mention of it. Also, in Miao, et al. there is a requirement on the rank of the proxy variables, are no such assumptions necessary here? In general, it would be helpful if the authors placed necessary assumptions in a more well delineated fashion. As it stands, they are strewn throughout and often made opaque.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should make more plain the limitations of the proposed methodology in terms of what is practically realizable from data. I would also perhaps suggest a small motivating example to provide intuition.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "6805-NyIoqy", "reviewer": "Reviewer_iUkv", "summary": "This paper provides a graphical identification approach that combines both graphical and matrical approaches. In particular, they apply certain matrix chain-rule and inversion criteria, previously used in for example certain proxy-based approaches, to a matrix version of the C-factorization to arrive at a new causal effect identification algorithm. They show that their algorithm applies to cases that could not be identified with certain previous algorithms and thereby rendering them incomplete.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is quite well written and motivated. The overall storyline of the paper is clear, however I had the impression that the balance of the amount of material the authors would like to treat was suboptimal. For example, the authors revisit different proxy based approaches, which take a lot of space. I would move either the single-proxy or the double-proxy setting to the appendix, which gives additional space for, for example, a running example of the identification algorithm, which would have been helpful. Although the authors explain their main algorithm in Section 6, it is very difficult to understand the motivation of the steps they are taking without having any intuition on what is happening. This also would give more space for explaining C-factorization better and the example in that section. In particular, it was not clear to me how this example relates to C-factorization and what the actual point is that the authors are trying to make.\n\nThis leads me to another point, and that is, the notation. The conventions used, such as lower and upper case, back and forward slashes, accents and double accents and the different combination of those make this paper very hard to read, especially if their meaning change if applied in different combinations (such as thinking of / as \"complement/setminus\" or as a/B defined in line 161; and \\ defined as being consistent or as \"complement/setminus\" in line 144?), or if there are typos present (such as in line 158 which needs to be a forward slash?; or line 164 where there should be no sum over z, I think). For example, what does (x_{ij} \\ y_{ij}) / ( X_j \\ X_i \\ Y_i ) mean? Because of this notational overload I was unable to understand the results in all their detail and I was not be able verify any of the proofs of the paper. \n\nThe approach and results of this paper seem interesting and valuable. However, given the current state of the paper I would give it a marginally below accept, due to the imbalanced amount of material covered and the notational overload of the paper. I think that improving the notation and trading of some material for clarity would be a good idea to improve the overall readability and impact of the paper.\n\nMinor comments:\n - Lemma 3: Why the graph in the lemma?\n - Footnote 1: Put this in the main text: writing a distribution in matrix notation is very confusing if one does not know that the variables are discrete. Moreover, the MGT criterion is used in the paper many times without being defined in the main text.\n - line 81-82: What are W, Z and the union here?\n - line 91: State that it is acyclic somewhere? Or, not?\n - line 299: Here, $X^+_k$ and $Y^+_i$ have an ambiguous definition. Does this relate to the C-factor $Y^+$ definition?\n\nUpdate:\nAfter reading the response from the authors, I feel they have clarified my main concerns. I'm updating my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They clearly discuss the limits and implications of their work. Given their novel approach to causal identification by combining graphical and matrical approaches, I think this work has the potential of being a valuable contribution to NeurIPS.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper contains a solid and novel theoretical contribution. Authors should make sure that the remarks that convinced a reviewer to raise the score are sufficiently accounted for in the final version. Please take remarks on readability serious to help readers understand the challenging material. Abstract and introduction should be more explicit about the fact that not the full joint distribution of the observed variables are given, hence this is a method of merging information from distributions of subsets.  
Decision: Accept (Oral)