Independence Testing-Based Approach to Causal Discovery under Measurement Error and Linear Non-Gaussian Models
Authors: Haoyue Dai
Peter Spirtes
Kun Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: causal discovery
measurement error
linear non-Gaussian models
transformed independent noise condition

Abstract: Causal discovery aims to recover causal structures generating the observational data. Despite its success in certain problems, in many real-world scenarios the observed variables are not the target variables of interest, but the imperfect measures of the target variables. Causal discovery under measurement error aims to recover the causal graph among unobserved target variables from observations made with measurement error. We consider a specific formulation of the problem, where the unobserved target variables follow a linear non-Gaussian acyclic model, and the measurement process follows the random measurement error model. Existing methods on this formulation rely on non-scalable over-complete independent component analysis (OICA). In this work, we propose the Transformed Independent Noise (TIN) condition, which checks for independence between a specific linear transformation of some measured variables and certain other measured variables. By leveraging the non-Gaussianity and higher-order statistics of data, TIN is informative about the graph structure among the unobserved target variables. By utilizing TIN, the ordered group decomposition of the causal model is identifiable. In other words, we could achieve what once required OICA to achieve by only conducting independence tests. Experimental results on both synthetic and real-world data demonstrate the effectiveness and reliability of our method.

Independence Testing-Based Approach to Causal Discovery under Measurement Error and Linear Non-Gaussian Models
Haoyue Dai
Peter Spirtes' Kun Zhang
Department of Philosophy, Carnegie Mellon University
Machhne Learning Department, Mohamed bin Zayed University of Artificial Intelligence hyda@cmu. edu ps7z@andrew. cmu.
cmu.edu edu kunz1@cmu. .dd
Abstract
Causal discovery aims to recover causal structures generating the observational data. Despite its success in certain problems. in many real-world scenarios the observed variables are not the target variables of interest, but the imperfect measures the target variables. Causal discovery under measurement error aims to recover the causal graph among unobserved target variables from observations made with measurement error. We consider specific formulation of the problem, where the unobserved target variables follow linear nan-Gaussi acyclic model, and the measurement process follows the random measurement model. Existing methods on this formulation rely on non-scalable ever-complete independent component analysis (OICA). In this work, propose the Transformed Independent Noise (TIN) condition, which checks for independence between a specific linear transformation of some measured variables and certain other measured variables. By leveraging the non-Gaussia and higher-order statistics of data, TIN is informative about the graph structure among the unobserved target variables. By utilizing TIN, the ordered group decomposition of the causal model is identifiable. In other words, we could achieve what once required OICA achieve by only conducting independence tests. Experimental results on both synthetic and real- world data demonstrate the effectiveness and reliability of our method
Introduction
Discovery of causal relations is a fundamental goal of science. To identify causal relations from observational data, known as causal discovery, has thus drawn much attention in various scientific fields, including economics, biology, and social science [45] 22 [I]. Methods for causal discovery be roughly categorized into constraint-based ones (e.g., PC 43].. score-based ones (e.g., Greedy Equivalence Search (GES) (8), and ones based structural equation models (SEM) 38 all these methods assume that the recorded values are values the variables of interest, which however, is usually not the case in real-world scenarios. Some variables may be impossible to observe or quantify, so recorded values are actually proxy of them (c.g., measure one's 's mental status by survey questionnaire), and some variables, though quantifiable, may subject error introduced by instruments (e.g., measure brain signals using functional magnetic resonance (fMRI)). The difference between quantities of interest and their measured value termed measurement error
EB:
51 Almost
PM2.5
Figure 1:
Example of measurement error. Gray nodes are latent underly- ing variables and white nodes are observed ones.
An online demo and codes are available at alttpp://aaa..tuuddderr//a/aaaaa
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Measurement eтror adversely impairs causal discovery [28 24 36 The measuring process can be viewed as directed edges from underlying variables of interest (unobservable) to measured values (observable), and the d-separation patterns on underlying variables typically do no hold on measured ones. Consider the causal effects from factory emissions ii to air quality & then to residents' lung health d' as shown in Figure [ while we only have corresponding measured quantities: chimney statisties id. PM2.5. and hospital reported cases 3 Though an and d's are independent given W iil and I are however dependent given PM2.5- If measurement error is severe, id and u even tend to be marginally independent [53] 36], which makes PM2.5 look like a collider (common child). One might thus incorrectly infer that, lung cancer causes air pollution. In fact, such measurement error is always a serious threat in environmental epidemiologic studies 30 10
Denote by X = {X, V the latent measurement cereentteeroo-ffie error-free variables and X = {X+]i=1 observed ones. While there are different models for measuring process [2
49 in this paper, we consider the random measurement error model [66), where the observed variables are generated from the latent measurement free variables X; with additive random measurement errors = (E,)
x; + F.p.
Measurement errors E are assumed to be mutually independent and independent of X. We assume causal sufficiency relative to X (i.e., no confounder of X who does not have a respective measurement), and focus on the case where X is generated by linear, non- Gau-Gaas,,,,, acyclic model (LiNGAM 38 . see 3.1 J. Note that here w.l.o.g.. the linear weights of (X; + x are assumed to be one (since we do not care about scaling). Generally, if observations are measured by
X, x, + E; with weights {ci]== not necessarily being one, all results in this paper still hold.
The objective of causal discovery under measurement error is to recover causal structure among latent variables X, denoted as G. a directed acyclic graph (DAG), from contaminated observations X. As illustrated by Figure [ causal discovery methods that utilize (conditional) independence produce biased estimation (see Proposition]]
[ for details). SEM-based methods also typically fail to find correct directions, since the SEM for X usually do not hold on X. Unobserved X are actually confounders of X. and there exists approaches to deal with confounders, such as Fast Causal Inference
(FCI 44 ). However, they focus on structure among observed variables instead of the unobserved ones, which is what we aim to recover here. With the interest for the latter, another line of research called causal discovery with latent variables developed, which this paper is also categorized to. However, existing methods
50 35 cannot be adopted either, since they typically require at least two measurements (indicators) for each latent variable, while we only have one for each here (and is thus more difficult task). Specifically on the measurement error problem, 16 proposes anchored causal inference in the binary setting. In the linear Gaussian setting, [33] presents identifiability conditions by factor analysis. A main difficulty here is the unknown variances of the measurement errors E, otherwise the covariance matrix of X can be obtained and readily used. To this end, 12] provides upper-bound of E and Rd develops a consistent partial correlations estimator. In linear non-Gaussian settings (i.e., the setting of this paper), (54] shows that the ordered group decomposition of G, which contains major causal information, is identifiable. However, the
corresponding method relies on over-complete independent component analysis (OICA [9] ). which is notorious for suffering from local optimal and high computational complexity identifiability results in [54] despite the theoretical correctness, is far from practical achievability.
39 18 Hence, the
The main contributions of this paper as follows: 1) We define the Transformed Independent Noise (TIN) condition, which finds and checks for independence between a specific lincar transformation (combination) of some variables and others. The existing Independent Noise (LN 40) and General- ized Independent Noise (GIN (50) conditions are special cases of TIN. 2) We provide graphical criteria of TIN, which might further improve identifiability of causal discovery with latent variables. 3) We exploit TIN on a specific task, causal discovery under measurement error and LiNGAM, and identify the ordered group decomposition. This identifiability result once required computationally and statistically ineffective OICA to achieve, while we achieve it merely by conducting independence tests. Evaluation on both synthetic and real-world data demonstrate the effectiveness of our method.
2 Motivation: Independence Condition and Structural Information
The example Figure D illustrates how the (conditional) (in (in)dependence relations differ between observed X and latent X, and thus lead to biased discovery results. To put it generally, we have,

---

Proposition 1 (rare d-separation). Suppose variables follow random measurement error model defined in Equation Q For disjoint sets of observed variables Z. Y. S and their respective latent ones Z. Y, S. d-separation Z Y holds, only when marginally Z L,Y, and Z Y hold.
By 'rare' we mean that the d-separation patterns among X usually do not hold among (except for rare marginal ones), since the observed variables are not causes of any other (though the latent variables they intend to measure might be). For example, consider the underlying G to be chain structure (FigurePai 2ah and fully connected DAG (Figure 2ch. There exists no (conditional) independence on either, and PC al gorithh will output just a fully connected skeleton on both cases. Then, without (conditional) independence (which is non- non-parametric) to be directly used, can we create independence, by leveraging the parametric assumption (LiNGAM) and benefit from non Gaussianity?
Naturally we recall the Independent Noise (IN) condition proposed in Direct-LiNGAM
40
Definition (LN condition). Let Y; be single variable and Z be set of variables. Suppose variables follow LiNGAM. We say (Z, Y,) satisfies IN condition, denoted by IN Y:), if and only if the
residual of regressing Y; on Z is statistically independent Z. Mathematically, let @ be the vector of regression coefficients, i.e., ت = cov(Y, Z) cov (Z, Z) - IN Y,) holds iff Y; TTZ 1 Z.
Here "cov" denotes the variance-covariance matrix. IN identifies exogenous (root) variables, based on which the causal ordering of variables can be determined (Lemma in 40 However, IN cannot be applied to measurement enror model. With hidden confounders (X) behind observed X. independence between regressor and residual typically does not exist on any regression among X. In fact, X follows errors-in- emorr--n-vvriaalls models 15 77, for which the identifiability w.r.t. G is not clear.
However, we might still benefit from this idea to leverage nausGansyyy of exogenous noises. exog Consider the Figure D example and abstract it to X1 - X2 4 X3 with {X; 4 X. 1-111 Although IN does not hold on any of X, interestingly, there exists linear transformation of observations
bX2- - X3, which contains only ( (Rg. F2, Fa} (Fi, and Foz are cancelled out) and shares no common non-Gaussian noise term with X1. Hence, by the Darmois-Skitovich theorem [21. bX2 X3 is
independent of Xj. This finding is echoed in Generalized Independent Noise (GIN 50) condition:
Definition 2 (GIN condition). Let Z and Y be two sets of random variables that follow LiNGAM. We say (Z, Y) satisfies the GIN condition, denoted by GZ Y). if and only if the following two conditions are satisfied: 1) There exists nonzero solution vectors w IR Y to equation cov(Z, Y)w O, and 2) Any such solution w makes the linear transformation w Y independent of Z.
Here Y denotes the dimensionality of Y. The intuition of GIN is that, despite no independent resid- ual by normal regression, it is possible to realize independent "psendo-residuuls" " (5) by regressing with "reference variables" ". [50] shows IN special case of GIN (Proposition 2), and further gives graphical criteria (Theorem 2). based on which a recursive learning algorithm is developed to solve the problem. Each latent variable is required to have at least two observations. Interestingly we find that, in mcasurement error models, if each latent variable X, has two measurements X,,, Xt., then the GIN condition be readily used to fully identify the structure of G, which is already breakthrough over existing methods [42 regard our more challenging task where each X, has only one measurement X,, natural question is that, can GLN also help? Given the example in Figure [
46
23 See Appendix B for the whole procedure. With
illlustrated above, the answer seems to be affirmative: GIN([X,), X (X.))) only holds for i 1, so the root can be identified. More generally:
Example 1 (GIN on chain structure). Consider cases where the underlying graph G is a chain structure with n (n 2 3) vertices and directed edges {X;
X 1--1 Figure 2a is example with n = 5. We find that GIN = X1 Y X 2255,4.5 holds (where X2,3,4,5 denotes (X2, X3, X4, ) same below), with solution w = [-bx - bey - bedz, xr, y, =]T, v, E R. TY cancels noise components in Y that are also shared by Z. and thus w Y 1L Z. However, GIN(X, (X, X)(X;) is violated for any other: * (see Example 12 for detailed derivation). With this asymmetry, the latent root X1 can be identified. Fur- thermore, GIN(X,, X,,1, holds for any = 1, ....,.,,,, n 2.
c
2
X4
X
(c)
X
X1
4
X1
X,
X.
X.
(a)
(b)
X
(d)
Figure 2: Graph structure & exam-
Example D might give us an intuition that by recursively testing GIN (over the newly found subroot and the remaining vari-
ples. For simplicity, observed X, measurement edges are omitted.
3

---

ables), we could identify the causal ordering of first n - 2 variables for any DAG. However, this is over-optimistic thanks to the sparsity of chain structure. Consider denser structure:
Example 2 (GIN on fully connected DAG). Consider cases where & a fully connected DAG with n (n 2 3) vertices and directed edges (X; + X for every i < J. Figure 2 is an example with 7 = 4. We first find that GXN,X1, X2,3,1) holds. However, in contrast to the chain structure,
GI, X3.4) does not hold there is no way to cancel both É1, from X3,4. More generally we
have: (2,(XiXX,,-p0 GIN(X1,2, x3, .., GIN(XI,-..sa (m)), k = 1)/2].
Since a fully connected DAG is the densest extreme, Example 2 might give us an intuition that GIN could identify at least the causal ordering of the first half of variables. Unfortunately, this is still over-optimistic, since we could not know beforehand the structure type of G.
Example 3 (GIN on chain structure with triangular head). Figure 2b shows a variation of chain structure, with edges X1 + X2, X1 - X3, X3 X2, and [X; - xx+1 We name it "chain structure with triangular head". Interestingly. GIN Xs.m.a), which is satisfied on Figure 2a is also satisfied here. E.g., in Figure 2b (n 5), the solution w [-dr - -eey, It, y] , 2, y K.
YY cancels E1,3 from Y. and thus Y I Z. Actually, the chain structure with triangular head Gvc is unidentifiable with chain structure Ge w.r.t. GIN conditions, i.e., for any two sets of observed variables Z,Y Y S X, GIN Y) holds on Gec if and only if GIN Y) holds on Gr. Consequently, if directly using any recursive algorithm by GIN as in Example D the output causal ordering would still be X2, X3, which is incorrect due to X3 + X2 in the triangular head.
The above examples show that it is not as simple as it seems to use GIN for one mne-measurement model: only part of the causal ordering can be identified, and worse yet, rather complicated error correction is needed to deal with possible incorrect orderings. However, after a closer look at the unidentifiable examples above, we find that actually more information can be uncovered beyond the GIN condition:
Example 4 (Asymmetry beyond GIN). 1) Consider Example 2 where only the root variable X₁ can be identified by GIN and X2.3,1 are unidentifiable, i.e., permutation of the labeling of X2,3,1 will still preserve the GIN condition over any two subsets Z, Y. However, there actually exists an asymmetry between X₂ and X3,4: we could construct linear transformation of X1,3.4: ed-be X, + dfte X3- d.
X2 s.t. it is independent of X2, while there exists no such linear transformation of X1,2,4 to be independent of X3. and also for X1,2,3 to X4. 2) Consider Examples ! and 3 where Ge and Goc unidentifiable w.r.t. GLN conditions. Let Z := X4 and Y == X1,2.3 GINTZ, Y) is violated on both graphs. However, an asymmetry actually exists: on Goc, we could construct aX1 - X2 + bX3 (which cancels E1,3) to be independent to X4, while this is impossible on Gc.
To put simply, the motivation of independent "pseudo-residual" behind GIN actually limits the power of non-Gaussi, with the coefficients vector w only characterized from variance-covvariacee matrix (2nd-order). There are actually two cases for GIN Y) to be violated: 1) though not all solution makes w Y 1 Z, there exists non-zero w s.t. T Z, and 2) there naturally exists no non-zero w s.t. w Y T Z. The original GIN cannot distinguish between these two cases. Hence in this paper, we first aim to distinguish between the two, generalizing GIN condition TIN condition.
3 With Transformed Independent Noise Condition
In the above discussion, one can that the presence of measurement error affects the conditional independence relations among the variables and the independent noise condition. However, we will show in Theorem the underlying error-fre free variables and the measured variables with error. In this section, we will formulate such independence conditions and investigate their graphical implications for error-free variables (i.e., variables generated by the LiNGAM without measurement error). In $ we will then extend the results to the measured variables. Please note that in contrast to other sections, the notation used in this section, including X, Y, and S, denotes error-free variables generated by the LiNGAM.
that specific type of independence conditions are shared between
3.1 Notations
Let G be a directed acyclic graph with the vertex set V(G) = [n] (1, nn and edge set E(G).. directed path P = (ig, "., (ix) ) in is sequence of vertices of G where there is a
directed edge from in to it+1 for any 0 < < k- 1. We use notation i ~ j to show that there

---

exists directed path from vertex to j. Note that single vertex is also directed path. i.e., i ~w i holds. Let Z S [n] be a subset of vertices. Define ancestors Anc(Z) = { : Z.j i}. Note that Z C (Z). Further let S be a subset of vertices. We use notation i Ae j to show that there exists directed path from vertex to without passing through S, i.e., there exists a directed path P = (2. ma, .). )) in G s.t. i. & S and my & S for any 0 H S k. Define ancestors outside S accordingly: for two vertex sets Y. denote ancestors of Y that have directed paths into without passing through S as AnCout(s) Y) == {j] E Y.j y 2). Note that the graphical definitions here also be translated to trek 47 language (see Appendix
C for details).
Assume random variables X {Xi)e are generated by LiNGAM w.r.t. graph G, i.e.,
X AX + E BE, with B (I A)
where E = (F: (ein)) are corresponding mutually independent exogenous noises. A is the adjacency matrix where entry A is the linear weight of direct causal effect of variable X; on Xj. A, # and only if there exists edge i + X can also be written directly as a mixture of exogenous noises = BB. If the entry of mixing matrix B e O, then i Anc( Note that here and in what follows, we use boldface letters A, B to denote matrices, and use boldface letters S, W, X, Y, Z with notation abuse: it can denote vertices set, respective random variables set, or random vector. When we say "two variables sets Z, Y", if not otherwise specified, Z, Y need not be disjoint.
3.2 Independent Linear Transformation Subspace and its Characterization
We first give the definition and characterization of the independent linear transformation subspace. Definition 3 (Independent linear transformation subspace). Let Z and Y be two subsets of random variables. Suppose the variables follow the linear non-Gaussian acyclic causal model. Denote:
Ωz,y == (w E R
w T 1 Zj.
By the property of independence, Iz,y is closed under scalar multiplication and addition, and thus is a subspace in R|Y|, In fact, SizyY can be characterized as nullspace as follows:
Theorem (Characterization of f2z,)). For two variables subsets Z and Y, Jzy satisfies:
Ωzy = null(Bt .zzoo((2...)
where mull(-) denotes nullspace. By, denotes the submatrix of mixing matrix B. with rows indexed by Y and columns indexed by nzcol (Bz.). nzcol(Bz..) denotes the column indices where the submatrix Bz,; has non-zero entries. nzcol (Bz.)) actually corresponds to the exogenous noises that constitute Z. Particularly, if assummig "if ~ then Bj + 0", then, (zcol(Bz..) = Ane(Z),
linear transformation W Y 1L Z if and only if w T shares common non-Gaussian exogenous noise components with Z.
Proof of Theorem iis straight-forward forward by the Hemmois-Skioovch theorem 21:
Example 5 (Revisiting examples in 2 from fzzyy perspective). For illustration, now we revisit the examples in 2 from the perspective of independent linear transformation subspace.
0
1
0
0
1
0
a + bc
1
0
0
0
ab
b
1
c
0
0
0
a ad
d
abc
be
c
cd
0
1
0
abed
bed
cd
1
cde
0
de
e
al a(d + bf + df +
f
1
(5)
Equation 55) shows the corresponding mixing matrix B for graph à in Figures 2a 2c re-
spectively. Suppose we have access to underlying variables X; and only focus on G. Colored blocks denote submatrices of B. 1) For the fully connected DAG (Figure 2 the right matrix), to identify the root X1, GIN 1.N(x is satisfied, corresponding to Oz.Y null( "). For (Z, Y) = (X2, Xa.4) or (X4, X122a), there exists no non-zero w s.t. w part and X2 X, af+e X, X1. because the stacked two parts of has rank < though GIN is still violated because cov(Z, Z Y) has rank < 2. 2) For the chain structure Ge (Figure 2a
Z, because the lower 2, X 11,44), we actually have
are full row rank. However, if we set (Z, Y) = (X,,
5

---

the left matrix) and chain with triangular head Gec (Figure 2b the middle matrix), GIN is satis- X4.5), with the By Ayn submatrices being
fied on 123,455). 2, 33,455, (X
respectively. Note that though the shape of submatrices are different between Ge and Cve. their ranks are always equal, and thus unidentifiable by GIN. However, let (Z, Y) == (X 4 X 1,2,3), an asymmetry actually exists: in Goc. X4 1 axx X2 bX 3. because in the right matrix has
rank 2 < 3, while in the left matrix
is full row rank, so there is no such independence in Gg.
3.3 Graphical Criteria of Independent Linear Transformation Subspace
$3.2 characterizes y by submatrix of B, which entails information on graph structure and edge weights. The following sections go one step further, explicitly exhibit the graphical criteria of flzy and investigate how fZzyY could help to identify the causal structure. We first give the assumption:
Assumption 1 (Rank faithfulness). Denote by B the parameter space of mixing matrix B consistent with the DAG G. For any two subsets of variables Z, Y C X, we assume that
rank By (uc(()))
max rank (B'y (An(()))) B'EB(G)
(6)
Roughly speaking, we assume there are no edge parameter couplings to produce coincidental low rank. This is slightly stronger than "nzcol (Bz.) Anc(Z)". See Appendix F.1 elaboration. In other words, the graphical criteria holds on a dense open subset of the edge parameter space. Note that Assumption D is the only other parametric assumption we make besides LiNGAM throughout the paper, where violation of Assumption I is of Lebesgue measure O, and LiNGAM is testable.
Graphically, we first define vertex cut, and then give the graphical criteria based on it:
Definition 4 (Vertex cut). Let W, Y, be three vertices subsets of VG) which need not be disjoint. We say that S is a vertex cut from W to Y, if and only if there exists no directed paths in G from W Y without passing through S. With basic notations $3. the following statements are equivalent:
1) is a vertex cut from W to Y; 2) Vi E W.j Y, i j does not hold; 3) As)out(s) (Y) W
Ø: 4) S's removal from G ensures there is no directed paths from W to Y!S..
More details on vertex cut are in Appendix C Note that trivially W itself and Y itself are vertex cuts.
Theorem (Graphical criteria of Y22 Let Z, Y be two subsets of variables (vertices), we have:
Y dim(Ozy) = min[[S] S is a vertex cut from (z)(Z) to Y
(7)
where dim (S2:y) denotes the dimension of the subspace Piy,y, iee, the degree of freedom of w.
By Theorem Y dim(Ozyy) is exactly the rank of BY,Anc(22) Theorem can then be proved by combinatorial interpretation of mixing matrices' determinants. See Appendix A for details.
From the graphical view, vertex cut S from Anc(Z) Y means that the causal effect from Z and the common causes of Z and Y. if there is any. must affect Y through S there is no any bypass. To interpret trek-separation 4i language, is equivalent to "(2, S) 1-separates (Z, Y
From the noise view, the noise components that constitute variables Z are exactly the exogenous noises corresponding to vertices Anc(Z). All these noises must contribute to Y (if any) via S, and thus Y can be written as Y = LS + Ey, where L denotes a linear transformation, and Ey 1 Z. Denote by S2,y the critical vertex cut from Z to Y the noise components of wT Y is exactly the exogenous noises corresponding to AnCout (Y).
Ane
Z
S
Y
3.4 Formal Definition of TIN
Ancousss YY)
With the graphical criteria given in 3.3 we could use it for structure inference as long as have the (dimension of) independent linear transformation subspace Ωz,Y- In $5 will comprehensively discuss methods to estimate Zg,y, while for now, could just safely suppose we have Ωy since independence is testable, theoretically one could get 22 least by traversing over Y
Figure 3: Illustra-
tion of vertex cut S from Anc(Z) to Y.
2See Definition 2.7 47 for definition of r-separation. See Appendix C for details.
"See Appendix D.I for definition. Roughly speaking. "critical" means smallest and last vertex cut.

---

Table 1: Examples of TIN on different (Z, Y) pairs over different graph structures in Figure 2
(2,
(a), (Ns. Nt. As])
((X1.Xa),
(X4. Xs]]
((Xa). (N,, A2. Xs))
((X1,.44) (Na.
Xs))
Geuph
(a)
(d)
(6)
(a)
(d)
TINIZ, Y)
1
2
2
}
2
And(2)
Nua
Xua
X.
X1a
X
Naa
X1a
X..a
X1.3
X1.2
Xa
X.
X1a.
X.
S2.y
Xx
Xs
N1.
X1
X1.
X1
XEA
Xa
Xa.
Xa.4
Naas
Xa.4
Aoten;(Y)
X1.0
Na.4.
Na.3
X6.
Xs.6
N9.43
X4,6
X1.0.4.5
X5
Xa
Definition 5 (TIN function). Let Z and Y be two subsets of observed random variables. Suppose variables follow LiNGAM. We define a function TIN as follows:
TIN(Z, Y) = Y - dim dim,Y)
(8)
TIN is a function that takes as input two random vectors Z, Y and returns an integer in range [0, | Note that this is different to IN GIN, which returns only bool value (satisfied not). GIN can be viewed as a special case of TIN, i.e. GZ, Y) is satisfied if and only if TIN Y) = rank(cov (Z, Y)) |Y] (where (an((cov()) (-) can be characterized by 47). IN can also be viewed as a special case of TIN, i.e., (Z, Y.) is satisfied if and only if TIN Z, Z U (X.)) = -Z]-
Example 6 (Review TIN graphical criteria on graphs), For better understanding of TIN, we demon- strate some representative examples of TIN over different graph structures. Results are shown in Table D We use the four graph structures in Figure 2 For illustration, assume we have access to latent variables to directly conduct TIN over X. Graphical criteria correspond to G. For readahility, we omit all notation. We assume there are 5 vertices in the fully connected DAG (Figure 2 con- sider for example, GXN X1 122,4,5) does not hold, since rank(cov( (Z, Y)) is only one (restricted by Z size). However, there exists w with degree of freedom I s.t. w Y JL Z - this corresponds to a 3-variables vertex cut 2,,,3 (Anc(Z) (Z) itself). Consider on Figure 2d (XI,(1,,,))) X4.6) 1, corre- sponding to the 1-variable vertex cut X4. This example shows that vertex cut does not necessarily yield d-separation pattern (but blocking, instead), since here Xs L X1
The graphical criteria for TIN over any two sets of variables Z, Y are given above. Interestingly, we find that special type of TIN is particularly simple in form and informative for structure inference:
Lemma (Graphical criteria of TIN on me-and--therr Assume we have access to all variables X on DAG G. For each singleton variable X; E X, let Z = {Xi} and Y = X XX.). we have,
{1
[Iud Anc ((x+))
X, a non-leaf node
TIN((X)..XXXX)
(9)
Anc( ((x,)) -1 X; is a leaf node
Due to page limit, here only give the main criteria TIN. See Appendix D for more properties.
4
TIN Condition-Based Method for Measurement Error Models
In S we propose TIN condition over general LiNGAM model and give its graphical criteria. In this section, we aim to exploit TIN on our specific task of interest: measurement error models.
4.1 Identifiability of Ordered Group Decomposition
Under our problem setting where X follows LiNGAM, identifiability results can greatly benefit from the non- Gon-siussiy of data. [54]] shows that the ordered group decomposition of G is identifiable. First review definitions:
Definition 6 (Pure leaf child). On DAG G, a vertex j is said to be "pure leaf child" of another vertex i, iff j is a leaf node with only one parent, i.
Particularly, if variable X, is a pure leaf child of X; in G, then X, and X, are naturally unidentifiable (e.g., X2 and X- in Figure 4. The reason is that the exogenous noise É, of leaf X; does not contribute to any other variables, just like its measurement noise Ej. Consequently, X; and X; can be viewed as two equally positioned measurements of X,, without any asymmetry.
Figure 4: An exam- ple of ordered group decomposition.
Definition (Ordered group decomposition). Consider the underlying causal model G. The ordered group decomposition can be defined by the following procedure: at each step, remove root vertices and their pure leaf children nodes (if any) from graph, and append the removed ones as a new group. Repeat this procedure to remove root vertices from the remaining graph, until the graph is empty.
7

---

This procedure is equivalent to Definition 2 in [54 See Figure order (color dark light). The ordered group decomposition is X2,7 + X3,6 X4.5.
roots are removed from graph in
4.2 Exploit TIN Identify Ordered Group Decomposition
Our task is to recover G over X by testing TIN over X. In notations above, X and X are strictly distinguished denote unobserved and observed variables. However, actually this can be escaped: Theorem 3 (Equivalence of TIN over latent and observed variables). For two disjoint observed variables subsets Z, Y, and their respective underlying latent variables subsets Z, Y,
TIN(Z, Y) = TIN(2, Y)
(10)
Theorem 3 can either be proved by graphical criteria, or by showing how the rank of submatrices of B is preserved among latent and observed variables. Interestingly, recall Proposition | we show the inequivalence of d-separation and IN condition held between X and X (raw independence). However, TIN condition, which essentially finds transformed independence, holds equivalently on latent and observed variables. With this equivalence, we can conduct TIN over observed variables X just as if we have access to the latent ones X. Thus the problem can be restated without measurement error: assuming causal sufficiency, by only using TIN over disjoint Z, Y, to what extent G identifiable?
Under this equivalent problem, Lemma D can be used directly to identify the ordered group decomposition of G: for each singleton observed variable X,, test TIN and assign an order ord(X,) == TIN([X;) (x))) Group variables with same ord, and then sort the groups by their orders. Obviously, the ordered groups obtained by this procedure is consistent with Definition 7
Example 7 (TIN on Figure 4. ord(X;)? are respectively 1.2. 4, 4, (can verify by charac- terization or graphically), so the group ordering is identified as X1 - X2,7 + X3,6 - X4.5.
5 Estimating Linear Independent Transformation Subspace Ωiz,Y
In the above sections we safely assume that we can always get S2z,Y. since theoretically independence is testable and w can be exhaustively traversed. In this section, give practical methods to estimate 12,Y. Due to page limit we only give a summary for each. Please see Appendix E for details.
5.1 Tackling Down to Subsets of Y
Theorem 4 (TTIN over Y subsets). For two variables sets Z, Y, TIN(Z, Y) = k (assume k >> 0). iff the following two conditions hold: 1) VY Y with YY|| k + 1 (if any), there exists non-zero w s.t. w Y 1 Z; and 2) 3Y' Y with Y'| = k. there exists no non-zero w
s.t. w 1 Z.
This transforms the task of estimating the dimension of Ωz,y to simpler one: counting size of the subsets Y'. Instead of all independence, here we only need to check existence of independence.
5.2 Constrained Independent Subspace Analysis (ISA)
Conduct Independent Subspace Analysis (ISA
48
over variables Z and Y in the following form:
I
Z Y
(11)
O WYY
where the de-mixing matrix is masked to only update the lower-right YY| x Y block W WYY, with upper-left |Z| x |Z| block fixed as the identity and elsewhere fixed as zero. The independence between WYY Y as group to Z is maximized. Since WYY invertible, its rows span the whole R | so the maximum number of rows that achieves W c.
Y 1 Z is exactly the dimension of f2,y
5.3 Stacked Cumulants: Ranks Stopped Increasing
Definition (Stacked 2D slices of cumulants). For two variables sets Z, Y and order & 2 2, define:
T Z.Y Z
(
where ((k) is matrix with c/)) = cum X, X; Xy). (12)
=
k- times
T
(k) Z.Y is (k- Z) x Y matrix that vertically stacks 2D cumulants slices between Z, Y with
orders from 2 to k. When k = 2 it is cov Y). Ranks of v (k)
Y.Y in the sequence k 2, 3, ... satisfies:
'There is actually trivial difference, depending how with multiple roots is considered. See Example B
8

---

TIM 2tggp
TW. 54
-
UNDAN
CANNE OPCA
055
HOTEARS
SconE
-55
-.0
NSR
-SR 300
-50
Faily DMG
KC ditaaneeee Booeer better)
26
dicance Goover
10
Figure 5: Distance to truth group ordering (lower better). implementations TIN + competitors.
Theorem 5 (rank( y (k) ( stopped increasing). For two variables sets Z, there exists a finite order
2 s.t. rank(U v (k+1)) rank v (k) 22 Moreover, (ZN Y) equals rank v (k)
(2 with this k.
2.Y
We will show detailed characterization and graphical criteria of (k) Z in Appendix E.1
5.4 TIN in Two Steps: Solve Equations, and then Test for Independence
Motivation of $5.3 is that independence yields zero cumulants (not only 2nd-order uncorrelatedness), ie., Pz S mull( v
(1) Y, ) for any 2 2. Hence, we could solve equations introduced at each order
Z:Y) makes T Z (similar to GIN procedure). More generally, S2z,y S mullcoo(f(ZZ), Y)) for any real-valued function f(-). E.g., solve equations
and then check whether all solution w E mull (V (k)
system (log(ZZ))))))) Y)u = 0; cov(sin(Z)) Y)w = O.... and test whether w Y Z holds.
Experimental Results
In this section, we evaluate the performance of TIN in recovering the ordered group decompo- sition of G under measurement error. Specifically, four implementations of TIN are evaluated:
TIN-subsets($ (.5se 15.1). TIN-ISA TIN-rank and (TIN-2steps($5. (5.4. We compare our
method with PC [43] GES
g ICA-LiNGAM BSJ Direct-LiNGAM 40) CAMME-OICA [54), Experiments are conducted on both synthetic and real-world data.
NOTEARS 55 and SCORE
32
6.1 Synthetic Data
While proposed method outputs correct ordered group decomposition for any à (without as- sumptions on graph structure), in the following simulation we consider specifically two cases: fully connected DAG (Figure 2c and chain structure (Figure 2a). of which the ordered group decomposition are both X1 ..... X, Xn-2, X,,,,,,,1 Xn-I.n- We consider G with the number of vertices n ..., ..., 10. Edges weights (i.e., the nonzero entries of matrix A) are drawn uniformly from [-0.9, 0.5) U [0.5, 0.9). Exogenous noises E are sampled from uniform U(0, 1] to the power of c, C ~ U(5, 7]. and measure- ment errors sampled from Gaussian A(0, 1) the power of e U22 4). Sample size is 000. Observations are generated by X, = X, + Fz. To show the effect of measurement error, we simulate with noise-to-sine signall ratio NSR var E.) var(X.)
(0.5, 1, 2, 3, 4). To evaluate the output group ordering, we use Kendall tau distance (22) to the ground-trutt (in range [0, 1]. the lower the better). For algorithms returning DAG/PDAG, its ordering is first extracted according to Definition Figure shows the results. Each column subplot indicates an NSR setting. The error bar is from 50 random generated instances. We can see that TIN-subsets and TIN are two best methods (ranks first on 68/ /80 cases), which steadily stick near x-axis. They both find/check independence by solving equa- tions cov (Z) Y)u 0. TIN-ISA slightly inferior (though still ranks 3rd), maybe due to the bias to independence (of w vectors) by ISA. TIN-rank fluctuates and performs worst (among TINs), especially on the fully connected dense case. This might be explained by higher order cumulants' sensitivity to outliers, and unreliable numerical rank tests (we simply SVD and thresholding).

---

Among the competitors, ICA-LINGAM and SCORE are the strongest two, which remain relatively stable with NSR growing larger (while e.g., Direct-LiNGAM deteriorates rapidly). Interestingly, they both perform much better on fully connected DAGs than on chain structures, and ICA-LiNGAM even performs better on larger graphs than on smaller ones. We will investigate the reason. Consider CAMME-OICA it relies heavily on mixing matrix parameter initialization, and thus performs gen- erally weak. Weak results by PC, GES might be because of the unfair setting for them: they output CPDAG and in both cases (fully connected and chain) here, naturally ordering (directions) can be determined. More experimental configuration and results discussions are in Appendix G.2
6.2 Real-World Data
Sachs's 33 is a real dataset that measures the expression levels of proteins in human cells under various phospholipids. The ground-truth graph structure [33 contains 17 edges on 11 variables (cell types), of which the ordered group decomposition is (plc.pkc)-(pip2-pipp wwt.ppp..pppp.33.3.3p jin.a.....j-.---.-.. [raf))+ {mek) } (kr..akt). Result given by TIN-subsets achieves the best distance score 0.33: (plc.pkc.p38] (raf,mee.ppjp www.e.ppp.pk..j.k... (pip3)> / This score on PC, GES, ICA-LiNGAM are 0.49. 0.69, 0.8 jnk
respectively. E.g.. PC outputs (raf.pka) /mek) |- ht.pl..ppp2..ppp.pkk..pp ( (erk,akt). Experiments
on another dataset, Teacher Burnout 4. also show TIN's good performance. See Appendix H.5
7 Conclusion and Discussions
In this work we define the Transformed Independent Noise (TIN) condition based on LiNGAM causal model, which finds and checks for independence between a specific linear transformation of some variables and others. We provide graphical criteria of TIN, which might further improve identifiability of the latent- variable problem. Specifically on causal discovery under measurement error, we exploit TIN achieve identifiability of ordered group decomposition.
We summarize the future work as three fold: 1) For the measurement error model, in addition to the special type (one-over-others) TIN over general Z, Y pairs can further improve identifiability. See Appendix F22 2) TIN now only considers the dimension of Sz,Y. while parameters might also help to recover edges weights. See Appendix [3 and 3) Reliable estimation of Ω can be formu- lated as an orthogonal research problem. We believe there exists more solutions. See Appendix
Acknowledgments and Disclosure of Funding
The authors would like to thank Georges Darmois, Viktor Skitovich, Bernt Lindström, Ira Gessel, Gérard Viennot, and Seth Sullivant for initializing the beautiful theorems that this work is built upon. Thank Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, and Zhifeng Hao for the GIN condition. Thanks to the anonymous reviewers and Joseph Ramsey, Zeyu Tang. Yujia Zheng, Ignavier Ng. Justin Ding, Mengyao Lu, Haoqin Tu, Qiyu Wu, Muyang Li, Jinkun Cao, and Jinhao Zhu for helpful feedback, proofreading, and discussions. The work was partially supported by the NSF under Project Number 5005000, by the CSS--Conveeeence Accelerator Track-D award #21 22144901, by by grant from Apple Inc., and by grant from KDDI Research
NHH-NHLB1 Inc.
References
[1] Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning lincar bayesian networks with latent variables. In International Conference on Machine Learning, pages 257- PMLR, 2013.
[2] Tineke Blom, Anna Klimovskaia, Sara Magliacane, and Joris M Mooij. An upper bound for random measurement error causal discovery. arXiv preprint arXiv:1810.07972 2018.
[3] John Adrian Bondy, Uppaluri Siva Ramachandra Murty, et al. Graph theory with applications, volume 290. Macmillan London, 1976.
[4] Barbara M Byrne Structural equation modeling with Mplus: Basic concepts, applications, and program- ming. routledge, 2013.
10

---

[5] Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. Advances in neural information processing systems, 32, 2019.
[6] Raymond J Camoll, David Ruppert, Leonard A Stefanski, and Ciprian M Crainiccanu. Measurement error in nonlinear models: modern perspective. Chapman and Hall/CRC, 2006.
[7] Andrew Chesher. The effect of measurement error. Biometrika, 78(3)451 462, 1991.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-552) -544,, 2002.
[9] George Bernard Dantzig and Delbert Ray Fulkerson. On the flow min theorem of networks. Technical report, RAND CORP SANTA MONICA CA, 1955.
[10] Jessie K Edwards and Alexander P Keil. Measurement error and environmental epidemiology: policy perspective. Current environmental health reports, 4(1):79-88, 2017.
[11] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er, Using bayesian networks to analyze expression data, Journal of computational biology, 7(3-4);601-623 620, 2000.
[12] Wayne A Fuller. Measurement error models. John Wilcy & Sons, 2009.
[13] Gessel and Gérard Viennot. Binomial determinants, paths, hook length formulae. Advances mathematics, 58(3):300-322 1985.
[14] Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola. A kernel statistical test independence. Advances in neural information processing syxtems, 20, 2007.
[15] Zvi Griliches and Vidar Ringstad. pror-in-the-variable bias in nonlinear contexts, Econometrica: Journal of the Econometric Sociery, pages 368-370, 1970.
[16] Yoni Halpem, Steven Horng, and David Sontag. Anchored discrete factor analysis. arXiv preprint arXiv:1511.03299 2015.
[17] Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlincar causal discovery with additive noise models. Advances in neural information processing systems, 21:6896696. 2008.
[18] Patrik O Hoyer, Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-gaussian causal models with hidden variables. International Journal of Approximate Reasoning, 49(2):362-377 2008.
[19] Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neurul networks, 13(4-5):411-44 177:411-430 1-430, 2000.
[20] Aapo Hyvärinen and Stephen M Smith. Pairwise likelihood ratios for estimation of non- aan-gaussian structural equation models. Journal of Machine Learning Research, (1lan):111-15::: 2013.
[21] Abram Meerovich Kagan, Calyampudi Radhakrishna Rao, and Yurij Vladimirovich Linnik. Characteriza- tion problems in mathematical statistics. Inleseentrss,,,nee, 1973.
[22] Maurice G Kendall. A new measure of rank correlation. Biometrika, (0(1/2):8199, 1938.
[23] Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1655-1664, 2016.
[24] Manabu Kuroki and Judea Pearl. Measurement bias and effect restoration in causal inference. Biometrika, 101(2)423-437, 2014.
[25] Bernt Lindström. On the vector representations of induced matroids. Bulletin of the London Mathematical Society, 5(1):85-90, 1973.
[26] Karl Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:96-1159, 1927.
[27] Judea Pearl. Causality. Cambridge university press, 2009.
[28] Judea Pearl. On measurement bias in causal inference. arXiv preprini arXiv:1203.3504, 2012.
[29] Dinh Tuan Pham and Philippe Garat. Blind separation of mixture of independent sources through quasi- quasi-maximum likelihood approach. IEEE transactions Signal Processing, 45(7):1712 1725, 1997.

---

[30] Sylvia Richardson and Walter R Gilks. A bayesian approach to measurement error problems in epi- demiology using conditional independence models. American Journal of Epidemiology. 143,6) 1993.
[31] Elina Roheva and Jean-Baptiste Sehy. Multi-trek separation in linear structural equation models. SIAM Journal on Applied Algebra and Geometry, (02mmer)).5()22788---7 5(2):278-303, 2021.
[32] Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models, In International Conference on Machine Learning, pages 18741-18753. PMLR, 2022.
[33] Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721 (11866521):523-355 ::523-529, 2005.
[34] Basil Saeed, Anastasiya Belyaeva. Yuhao Wang, and Caroline Uhler. Anchored causal inference in the presence of measurement error. In Conference on uncertainty in artificial intelligence, pages 619-628. PMIRR, 2020.
[35] Saber Salrhkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear non- non-gaussian causal models in the presence of latent variables. J. Mach. Learn. Res., 21:39 1, 2020.
[36] Richard Scheines and Joseph Ramsey. Measurement error and causal discovery. In CEUR workshop proceedings, volume 1792. page 1. NIH Public Access, 2016.
[37] Gideon Schwarz. Estimating the dimension of a model. The amnals of statistics, pages 461-464, 1978.
[38] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[39] Shohei Shimizu, Patrik O Hoyer, and Aapo Hyvärinen, Estimation of for latent factors. Neurocompating, 72(7-9):2224-000 2009.
linear non gan-gasssiin acyclic models
[40] Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik O Hoyer, and Kenneth Bollen. Directlingm: A dircet method for learning a linear non-gaussian structural equation model. The Journal of Machine Learning Research, 12:1225 1248, 2011.
[41] Ricardo Silva and Richard Scheines. Generalized measurement models. Technical report, CARNEGIE- MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE, 2005.
[42] Ricardo Silva, Richard Scheines, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(2), 2006.
[43] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 9(1::22-7,, 1991.
[44] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
[45] Peter Spirtes, Clark Glymour, Richard Scheines, and Robert Tillman. Automated search for causal relations: Theory and practice. Department of Philosophy technical report, 2010.
[46] Peter Spirtes. Calculation entailed rank constraints in partially non-linea and cyclic models. arXiv preprint 1xxiv:139..0044 2013.
[47] Seth Sullivant, Kelli Talaska, and Jan Draisma. Trek separation for gaussian graphical models. The Annals of Statistics, 1665)1666511685 2010.
[48] Fabian Theis. Towards general independent subspace analysis. Advances in Neural Information Processing Systems, 19, 2006.
[49] Tom Wansbeek and Erik Meijer. Measurement error and latent variables. A companion to theoretical econometrics, pages 162-179, 2001.
[50] Feng Xic, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances in Neural Information Processing Systems, 33:14891-14902, 2020.
[51] Kun Zhang and Aapo Hyvarinen. On the identifiability of the post- nonlinear causal model. arXiv preprint arXiv: 120..259.9 2012.
12

---

[52] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kerne--based conditional indepen- dence lest and application in causal discovery. arXiv preprini urXiv:1202.3775, 2012.
[53] Kun Zhang, Mingming Gong, Joseph Ramsey, Kayhan Batmanghelich, Peter Spirtes, and Clark Glymour. Causal discovery in the presence of measurement emoor: Identifiability conditions. UAI 2017 Workshop Causality: Learning. Inference, and Decision-Muking, 2017.
[54] Kun Zhang. Mingming Gong, Joseph D Ramsey, Kayhan Batmanghelich, Peter Spirtes, and Clark Glymour. Causal discovery with linear non gaussssni models under measurement error: Structural identifiability results. In UAL, pages 1063-1072, 2018.
[55] Xun Zheng. Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. DAGs with TEARS: Continuous Optimization for Structure Learning, In Advancex in Neural Information Processing Systems, 2018.
13


Reviews:
[{"review_id": "yfcp09bj2sA", "reviewer": "Reviewer_ZM5r", "summary": "This paper proposes an algorithm to learn an ordered group decomposition of the causal graph over variables $\\mathbf{X}$ which are not measured directly. In other words, each measured variable $\\tilde{X}$ is a proxy of a target variables $X_i$ such that $X_i = \\tilde{X}_i + E_i$, where $E_i$ is the measurement error. \n\nThe approach assumes the LiNGAM’s setting, I.e.:\n1) acyclic model\n2) causal sufficiency (no unmeasured confounders between the measured and also between the target variables), \n3) linear functions, and \n4) non-Gaussian error terms.\n\nFurther, it assumes a random measurement error model, where $X_i = \\tilde{X}_i + E_i$  and  $E_i$  are additive errors assumed to be mutually independent and independent of $X_i$. \n\nSpecifically, the authors propose the Transformed Independent Noise (TIN) condition, which checks independence between a particular linear combination of some variables and others. This condition generalizes the current approaches IN and GIN and provides information about the graphical structure over the measured variables, even when there are measurement errors. The authors show that the ordered group decomposition of the causal model is identifiable in this setting.\n\nThe proposed techniques were evaluated both through simulations and an application to real data. \n\n", "questions": "No further questions.", "limitations": "See sections above.\n\n", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper tackles an important and relevant problem. The considered assumptions are a bit restrictive. The parametric assumptions were well justified and motivated in the text and the theoretical contributions were illustrated through examples and seem solid. However, most of the proofs and intuitions were moved to the appendix, making the main part of the paper hard to read. \n\nA critical issue of the paper is that the assumption of causal sufficiency is not even mentioned in the paper.  When describing LinNGAM in line 49, the authors say that\n\n“the generating process for $\\mathbf{\\tilde{X}}$ is linear, non-Gaussian, acyclic model (LiNGAM)”.\n\nThen, in line 249, the authors say: \n\n“ Assumption 1 is the only one we make besides LiNGAM throughout  the paper, where violation of Assumption 1 is of Lebesgue measure 0, and LiNGAM is testable.” \n\nThe causal sufficiency assumption is not mentioned neither for LiNGAN nor for the proposed method. This is the strongest assumption and is NOT testable. Although it may be okay to make this assumption in this context, an appropriate justification must be provided. Further, it would be really appreciated if some simple examples illustrating what would happen if the causal assumption is violated. \n\nDisclaimer:  Apart from the discussion on causal sufficiency, the text is well-written and the problem is well-motivated. Examples also helped to understand the contributions. However, I didn't check the proofs in the appendix and I am not familiar with the previous methods (IN and GIN), so I cannot judge the novelty and soundness of the methods.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uqNkHfH43R4", "reviewer": "Reviewer_Pi4t", "summary": "The authors propose a generalization of the existing causal discovery approaches for learning the structure between latent variables in a parametric linear additive non-Gaussian structural causal model - under the assumption that each latent node has exactly one measurement node that is a child. ", "questions": "Thank you for your submission. I will be happy to increase my score after clarifications of the below. \n\n\"necessarily being one, all results in this paper still hold\"\nI guess this depends on the downstreat objective. This might not always be a valid assumption. \n\nAn example/insight for Prop. 1 would be useful.\n\n\"the GIN condition can be readily used to fully identify the structure of G, which is already a breakthrough over existing methods\"\nCan you elaborate on this? This was not identified by the previous authors? They only learned the partial graph? This statement is missing some context.\n\nCould you elaborate a bit on the recursion idea that is being hinted at for the GIN paper and that I believe will be used here as well? If the source node is discovered, one can get rid of its effect by conditioning on it. But here we only have access to its descendant. So we cannot condition. How can one recurse after the source is found?\n\nline172: \"while this is impossible on \\tilde{G}\"\nThis and other impossibility claims seem hard to check. Could you give some intuition on which mathematical tool can be used to verify this impossibility claim?\n\nAncestors in Theorem 1 probably means exogenous ancestors.\n\nAssumption 1 seems reasonable as an alternative formulation of faithfulness. \n\nThe method requires precise measurement model, which is a disadvantage, correct? If an observed node is caused by two latent variables, this will not work. Please verify.\n\nCould you please explain the proof of Theorem 2? I am a little concerned with the mapping to the max-flow min-cut formulation. Proof connects through B matrix, which is weighted - each edge has a weight potentially different from 1. Max-flow min-cut connection is valid for weighted or non-weighted. But using B matrix tells me that you are using the weighted version. But then we are making judgements about the rank of matrices which is typically not about the amount of max-flow determined by weighted edges. \n\nSpecifically the statement:\n\"the maximum amount of non-intersecting paths from source to sink is equal to the size of the minimum vertex cut from source to sink.\"\nMaybe I am not familiar with this version because if flow is on an edge weighted graph, I thought cut should also be counted as edge weighted.\n\nTheorem 3 should require some sort of guarantee that the measurement does not lose information. Can you formalize this?\n\nMy main concern is about finding the correct value \\omega for conducting the transformed independence tests. I also don't see how this statement follows from Theorem 4:\n\"This transforms the task of estimating the dimension of \\Omega(Z;Y) to a simpler one: counting size of the subsets Y0.\"\nOne still needs to search for existence of a w in these subsets.\n\nSection 5 in general is too short and is very hard to follow without any explanation. How do we find w_YY in (11)?\n\nline 367:\" then check whether all solution\"\nHow can we efficiently check all solutions if there are uncountably many? Please explain.\n", "limitations": "More like future work than the limitations and critique. Could be improved.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The exposition is very clear. Authors closely follow several examples and do it well. \n\n+ An important problem with some recent results. This work seems to generalize these for another special case of measurement graphs. \n\n- Presentation gets overly succinct in Section 5.\n\n- Some concerns with the theory. \n\n- Some parts of the algorithmic approach is unclear. \n\n- Emoji-based writing in the intro makes it hard to parse the text/the story.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bqd-ckTb1Nu", "reviewer": "Reviewer_G5xe", "summary": "In this paper, the authors study causal graph recovery among unobserved target variables from observations made with   measurement error. The authors propose  the Transformed Independent  Noise (TIN) condition, which checks for independence between a specific linear   transformation of some measured variables and certain other measured variables. By  utilizing TIN, the ordered group decomposition of the causal model is identifiable.  Experimental results on both synthetic and real-world data demonstrate the effectiveness and reliability of the method. ", "questions": "\n1. Is it possible to apply the method directly to causal structure recovery?", "limitations": "The paper can be strengthened with additional real-world examples and experimental results.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n 1. The paper is well written with good structures. Detailed illustrations and annotation make it easy to read.  \n\n  2. The methodology proposed by this paper and technical sections look solid and sound with technical details. \n\nWeaknesses:\n\n1. Experiments on more real-world datasets with measurement errors could make the paper stronger. \n\n2. Experimental comparison with other methods such as [1] and [2] on ordered group decomposition should be added.\n\n[1] Zheng, Xun, et al. \"Dags with no tears: Continuous optimization for structure learning.\" Advances in Neural Information Processing Systems 31 (2018). \n\n[2] Rolland, Paul, et al. \"Score matching enables causal discovery of nonlinear additive noise models.\" arXiv preprint arXiv:2203.04413 (2022).\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept