Unpaired Multi-Domain Causal Representation Learning
Authors: Nils Sturma
Chandler Squires
Mathias Drton
Caroline Uhler
Venue: NeurIPS 2023 spotlight (2023)
Keywords: linear structural equation models
causality
representation learning
independent component analysis
structure identifiability
multiple views
graphical model

Abstract: The goal of causal representation learning is to find a representation of data that consists of causally related latent variables. We consider a setup where one has access to data from multiple domains that potentially share a causal representation. Crucially, observations in different domains are assumed to be unpaired, that is, we only observe the marginal distribution in each domain but not their joint distribution. In this paper, we give sufficient conditions for identifiability of the joint distribution and the shared causal graph in a linear setup. Identifiability holds if we can uniquely recover the joint distribution and the shared causal representation from the marginal distributions in each domain. We transform our results into a practical method to recover the shared latent causal graph.

Unpaired Multi-Domain Causal Representation Learning
Nils Sturma
Chandler Squires
Technical University of Munich Munich Center for Machine Learning
LIDS, Massachusetts Institute of Technology Broad Institute of MIT and Harvard
nils. www.sstttuuude.ccmm de
csquiresGmit, .eteemiiteddu. edu
Mathias Drton
Caroline Uhler
Technical University Munich Munich Center for Machine Learning mathias drton@tum.cm de
LIDS, Massachusetts Institute of Technology
Broad Institute of MIT and Harvard cuhl eellerrmit...m
Abstract
The goal of causal representation learning is to find a representation of data that consists of causally related latent variables. We consider setup where has access to data from multiple domains that potentially share a causal representation. Crucially, observations in different domains are assumed be unpaired, that is, we only observe the marginal distribution in each domain but not their joint distribution. In this paper, we give sufficient conditions for identifiability of the joint distribution and the shared causal graph in a linear setup. Identifiability holds if we can uniquely recover the joint distribution and the shared causal representation from the marginal distributions in each domain. We transform our results into practical method to recover the shared latent causal graph.
Introduction
An important challenge in machine learning is the integration and translation of data across multiple domains (Zhu et al.) [017]] ZZuang et al.] 2021). J. Researchers often have access to large amounts of un- paired data from several domains, e.g., images and text. It then desirable to learn probabilistic cou- pling between the observed marginal distributions that captures the relationship between the domains. One approach tackle this problem is assume that there is latent representation that is invariant across the different domains (Bengio et al. 2013 Ericsson et al.) 2022). Finding a probabilistic cou- pling then boils down learning such a latent representation, that is, learning high-level, latent vari- ables that explain the variation of the data within each domain as well as similarities across domains.
In traditional representation learning, the latent variables assumed to be statistically independent, see for example the literature on independent component analysis (Hyvärinen and Oja 2000) Comon and Jutten 2010 Khemakhem al. 2020). However, the assumption of independence can be too stringent and a poor match to reality. For example, the presence of clouds and the presence wet roads in image may be dependent, since clouds may cause rain which may in cause roads. Thus, it is natural to seek causal representation, that is, a set of high-level causal variables and relations among them (Schölkopf et al. 2021 Yang et al. 202Tb). Figure illustrates the setup of multi-domain causal representation learning, where multiple domains provide different views on shared causal representation.
Our motivation to study multi-domain causal representations comes, particular, from single-cell data in biology. Given population of cells, different technologies such as imaging and sequencing
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

provide different views on the population. Crucially, since these technologies destroy the cells, the observations are uncoupled, i.e., a specific cell may either be used for imaging or sequencing but not both. The aim is to integrate the different views on the population to study the underlying causal
mechanisms determining the observed features in various domains (Butler et al. 2018 Stuart et al.
2019: Liu et al., 2019: Yang et al.; 2021a; Lopez et al., 2022 Gossi et al. [023] Cao et al. 2022). Unpaired mullii-omaan example, images of similar objects are captured in different environments (Beery et al.
data also appears in many applications other than single-cell biology. For
2018 8 large
biomedical and neuroimaging data sets are collected in different domains (Miller et al.
2016 Essen
et al. 2013 Shafto et al. 2014 Wang et al. 2003), or stocks are traded in different markets.
In this paper, we study identifiability of the shared causal representation, that is, its uniqueness in the infimite data limit. Taking on the same perspective as, for example, in [Schölkoof et al. (202T) and (Squires et al. (2023), we assume that observed data generated in two steps. First, the latent variables / = (Zi)ieH are sampled from distribution Pz. where Pz is determined by an unknown structural causal model among the latent variables. Then, in each domain e E {I...., m). the observed vector X R is the image of a subset of the latent variables under a domain- speciffc, injective mixing function Je- That is,
X = ge (Zs.),
where Se S H. is a subset of indice.. priori, it is unknown whether a latent variable Z, with i E Se is shared across domains or domain-specific. Even the number of latent variables which are shared across domains is unknown. Moreover, we only observe the marginal distribution of each random vector X but none of the joint distributions over pairs Xe, X for & f. Said differently, observations across domains are unpaired. Assuming that the structural causal model among the latent variables as well as the mixing functions are linear, our main contributions are:
1. We lay out conditions under which we can identify the joint distribution of X X
2. We give additional conditions under which we are able to identify the causal structure among the shared latent variables.
In particular, identifiability of the joint distribution across domains enables data translation. That is. given observation x in domain e, translation to domain f can be achieved by computing X|X = z]. Furthermore, identifying the causal structure among the shared latent variables lets us study the effect of interventions the different domains.
The main challenge in proving rigorous identifiability results for apply existing results for single-domain data in each domain separately. Even if the causal structure of the latent variables in a single domain identifiable, remains unclear how to combine multiple causal structures, i.e., in which way latent variables are shared. We circumvent this problem via a two-step approach: First, we extend the identifiability of linear independent component analysis (Comon] 1994 Hyvärinen and Ojal 2000 Eriksson and Koivunen 2004 Mesters and Zwiernik 2022) to the multi-domain setup, which allows us to identify the joint distribution and distinguish between shared and domain-specific latent variables. Moreover, we identify an "overall mixing matrix" " and, in second step, exploit sparsity constraints in this matrix to identify the causal structure among the shared latent variables. This leverages recent results on causal discovery under measurement error in single domains that also exploit sparsity (Xie et al.] 2020); Chen et al.) [202)] Xie et al., [022] Huang ee al. 2022). Although we emphasize that our focus in this paper is on identifiability, our proofs also suggest methods to learn the joint distribution as well as the shared causal graph from finite samples. We provide algorithms for the noisy setting and, moreover, we analyze how the number of domains reduce uncertainty with respect to the learned representation.
data is that we cannot
The paper is organized follows. In the next paragraphs we discuss further related work. Section 2 provides a precise definition of the considered setup. In Section we consider identifiability of the joint distribution. Using these results, we study identifiability of the causal graph in Section
We conclude with a small simulation study as a proof of concept for the finite sample setting in Section[5] Due to space constraints, the detailed discussion of the finite sample setting is deferred to the Appendix. Moreover, the Appendix contains all proofs, discussions on the necessity of our assumptions, and additional examples and simulation results.
Multi-domain Integration. Motivated by technological developments for measuring different modalities at single-cell resolution, several methods have been proposed recently for domain

---

21
Z
Z4
2
Z5
27
Z
X
X3 ET
X2
Figure 1: Setup. A latent causal representation where multiple domains X provide different "views" on subsets of the latent variables Z₁. The domains may correspond to different data modalities such images, text numerical data. Crucially, the observations across domains are unpaired, i.e., they arise from different states the latent causal model.
translation between unpaired data. The proposed methods rely on a variety of techniques, including
manifold alignment (Welch al. 2017 Amodio and Krishnaswamy 2018 Liu et al. 2019). matrix factorization (Duren et al. 2018), 8), correlation analysis (Barkas et al., 2019: /Staart et al.) 2019).
coupled autoencoders Yang and Uhler 2019), optimal transport (Cao al. 2022) regression analysis (Yuan and Duren (2022), and semisupervised learning (Lin et al. (022)) Implicitly, these methods presume the existence of a shared latent space where the different modalities either completely align or at least overlap. However, to the best of our knowledge, none of these methods have rigorous identifiability guarantees, i.e., the methods are not guaranteed to recover correct domain translation mapping even for infinite data. Our work advances the theoretical understanding of multi-domain integration by providing identifiability guarantees on recovering the shared latent space.
Group Independent Component Analysis. The primary tool that we use for identifiability is linear independent component analysis (ICA) (Comon, 1994 Eriksson and Koivunen 2004). Many works extend ICA to the multi-domaii setting. These methods primarily come from computational neuroscience, where different domains correspond to different subjects studies. However, to the best of our knowledge, all prior works require pairing between samples. These works can be categorized based on whether the samples
assumed be voxels (Calhoun et al.) 2001 Esposito et al. 20055,
time points (Svensén et al. 2002] Varoquaux et al. 22099 Hyvärinen and Ramkumar (013), or either (Beckmann and Smith 2005 Sui al. (2009). For reviews, see Calhoun et al. (2009) and Chabriel al.)
(2014). Related are methods for independent vector analysis (Kim et al. (2066] Anderson et al. [014]
Bhinge al. 2019) and multiset canonical correlation analysis (Nielsen 2002 Li al. [ Klami
et al. (2014). which allow the latent variables to take on different values in each domain but still require sample pairing. Most of the mentioned methods lack identifiability guarantees, only newer work (Richard et al. (2021) provides sufficient conditions for identifiability. Furthermore, all mentioned methods assume that every latent variable is shared across all domains, while our setup allows for shared and domain-specific latent variables. Some methods, e.g.. Lukic e.g..Lukic et al. (2002), Maneshi et al. (2016), and Pandeva and Forré (2023), permit both shared and domain-specific components, but only consider the paired setting. In this paper, we extend these results to the unpaired setting.
Latent Structure Discovery. Learning causal structure between latent variables has a long history. e.g., in measurement models (Silva et al. 2006). One recent line of work studies the problem under the assumption of access interventional data (e.g., Liu al. 2022 [Squires particular, [Squirss et al. (2023) show that the latent graph is identifialle if the interventions are sufficiently diverse. Another line of work, closer ours and not based on interventional data, shows that the graph is identified under certain sparsity assumptions on the mixing functions (Xie et al.) 2020, Chen et al., 2022; Xie et al. 2022; Huang et al. 2022). However, these methods are not suitable in our setup since they require paired data in single domain. One cannot apply them in each domain separately since would be unclear how to combine the multiple latent causal graphs, that is, which of the latent variables are shared. In this work, we lay out sparsity assumptions on the mixing
2023). In
3

---

functions that are tailored to the unpaired multi-doman setup. The works of Adams et al. (2021) and Zeng et al. (202T) may be considered closest to ours as they also treat setting with multiple domains and unpaired data. However, our setup and results are more general. Adams et al. (202) assume that the number of observed variables are the same in each domain, whereas we consider domains of different dimensions corresponding to the fact that observations may be of very different nature. Further, we allow for shared and domain- speciifcc latent variables, where the number of shared latent variables is unknown, while in Adams et al. (2021) it is assumed that all latent variables are shared. Compared to Zeng et al. (2021), we consider a general but fixed number of observed variables, while Zeng et al. (2021) only show identifiability of the full model in setup where the number of observed variables in each domain increases to infinity. On a more technical level, the conditions in Zeng et al. (2021) require two pure children to identify the shared latent graph, while we prove identifiability under the weaker assumption of two partial pure children; see Section 4 for precise definitions.
Let N be the set of nonnegative integers. For positive n E N, we define [n] = (1.....,m) n). For a matrix M E l we denote by MA. the submatrix containing the rows indexed by A C [a] and the columns indexed by C [b]. Moreover, we write Mg for the submatrix containing all rows but only the subset of columns indexed by B. Similarly, for a tuple = (Z1....,
Notation.
we
denote by zB the tuple only containing the entries indexed by B. A matrix Q = Qo E RPxP is a signed permutation matrix if it can be written as the product of a diagonal matrix D with entries
Dui E {+1} and permutation matrix Qo with entries (Qo)ij L i=)((() where is permutation on p elements, Let P be a p-dimensional joint probability measure of a collection of random variables Yy...., .Yp. Then denote by P. the marginal probability measure such that Y, P,. We say that P has independent marginals if the random variables Y; are mutually independent. Moreover, we denote by M # the d-dimensional push-forward measure under the linear map defined by the matrix M E RRdxp_ If Q is a signed permutation matrix and the probability measure P has independent marginals, then Q# P also has independent marginals. For univariate probability measures use the shorthand (-1) #1 P
2 Setup
Let H = [h] for h 2 1, and let 2 = =Z1, Zx) be latent random variables that follow linear structural equation model. That is, the variables are related by a linear equation
2 = AZ + E,
(1)
with x h parameter matrix A = (a.)) and zero-mean, independent random variables E (E1,...,EN) that represent stochastic errors. Assume that we have observed random vectors X E Rd in multiple domains of interest
[m]] where the dimension de may vary across domains. Each random vector is the image under a linear function of a subset of the latent variables. In particular, assume that there is subset L C H representing the shared latent space such that each X is generated via the mechanism
x²=
(1.
(2)
where Le C H. \, L. We say that the latent variable Z1. are domain-specific for domain E [m]] while the latent variables Ze are shared across all domains. As already noted, we are motivated by settings where the shared latent variables Zc capture the key causal relations and the different domains are able to give us combined information about these relations. Likewise, we may think about the domain- specific latent variables Zi, as "noise" in each domain, independent of the shared latent variables. Spe- cific models are now derived from ( by assuming specific (but unknown) sparsity patterns in A and G Fach model is given by a "large" directed acyelic graph (DAG) that encodes the multi-domain setup. To formalize this, we introduce pairwise disjoint index sets Vj,..., Vm, where V. indexes the coordinates of Xe, i.e., X = (X, : U E Vz) and Vz| = d.. Then V V1 U ...... U Vm indexes all observed random variables. We define an m-domain graph such that the latent nodes are the only parents of observed nodes and there are no edges between shared and domain-specifie latent nodes.
Definition 2.1. Let be a DAG whose node set is the disjoint union H UVV- = H U V1 U... U Vnn- Let D be the edge set of G. Then G is an m-domain graph with shared latent nodes L = [4] C H if the following satisfied:
1. All parent sets contain only latent variables, i.e., pa(u)= = (w w - u E D} C H for all HUV.

---

3
4
2
5
Vi
V2
Compact version of 2-domain graph G2 with five latent nodes and two domains V1 and V2. All observed nodes in each domain are represented by single grey node. We draw a dashed blue edge from latent node h H. domain Ve S if h Se pa(V... ). The random vectors associated to the two domains are uncoupled. that is, we do not observe their joint distribution.
Figure 2:
2. The set L consists of the common parents of variables in all different domains, i.e., u E & and only if pa(v) pa(w) for Ve, V with +
3. Let J. = S. \ L be the domain-specific latent nodes, where S, = pa (V.) = Unev, C
H. Then there no edges in D that connect node in L and node U Je. or that connect a node I. and node in y for any e # f.
To emphasize that given DAG is an m-domain graph we write 9m instead of G. We also say that Se is the set of latent parents in domain and denote its cardinality by se |Sel- Note that the third condition in Definition 2.1iionnnnndoooo does not exclude causal relations between the domain domain-specific latent variables, that is. there may be edges v for v, w E Ie- Since the sets Ie satisfy Ie n Iy
for e # f. we specify w.l.o.g. the indexing convention Ig = {e + > [7 and h = L Ee=1 [ee.
l Σ i= |T
Example 2.2. Consider the compact version of 2-domain graph in Figure 2 There are h
latent nodes where = {1, 2} are shared and I = (3, 4] and /2 = (5) are domain-specific. A full
m-domain graph is given in Appendix B
Each m-domain graph postulates statistical model that corresponds the structural equation model in ①1 and the mechanisms in (2). with potentially sparse matrices and G For two sets of nodes W. H U V. we denote by Dwy the subset of edges DwY = {y Moreover, let I Pwy be the set of real [W] x [Y] matrices M = (mwyy with rows indexed by W and columns indexed by Y, such that the support given by Dwy, that may = 0 if y
E D
W, E Y).
Dwy.
Definition 2.3. Let 9m = (H U V, D) an m-domain graph. Define the map
&g Dvn x RRD - TR. [
G-
Then the multi-domain causal representation (MDCR) model M(Gm) is given by the set of probability measures Px = B. where B E lm((g.... and P is an h-dimensional probability measure with independent, mean-zero marginals P, E H. We say that the pair (B, P) is a representation of Px E M(Gm).
Definition 2.3 corresponds to the model defined in Equations [ and 2 If E M(Gm) with representation B, P),, then Px is the joint distribution of the observed domains X (X) ......"",,, The distribution of the random variables E; in Equation ( is given by the marginals P.. Moreover, for any matrix G IR. Dvx
denote the submatrix G Gv..s. xdx which coincides with the matrix Ge from Equation (2). For the graph in Figure 2 we compute a concrete example of the matrix B in Example B. in the Appendix. Importantly, the rest of the paper assume only observe the marginal distribution Px in each domain but not the joint distribution Px-
Ultimately, we are interested in recovering the graph Gc (C, Dr.)) among the shared latent nodes. We proceed by a two-step approach: In Section we recover the representation (B, P) the joint distribution Px. To be precise, we recover a matrix B that is equal to B up to certain permutations of the columns. Then we use the matrix B to recover the shared latent graph Ge in Section 4 and show that recovery possible up to trivial relabeling of latent nodes that appear in the same position of the causal order.
5

---

3 Joint Distribution
To identify the joint distribution Px, we apply identifiability results from linear ICA in each domain separately and match the recovered probability measures P: for identifying which of them are shared, that is, whether or not E C. Let 9m be an m-domain graph with shared latent nodes L, and let Px E M((m) with representation (B, P). Recall that B = G(I - - with G E R RDvx and A E IR PxH. We make the following technical assumptions.
(CI) (Different error distributions.) The marginal distributions P;, E H. are non-degenerate, non-symmetric and have unit variance. Moreover, the measures are pairwise different to each other and to the flipped versions, that is, P. o P3 and P. + -P, for all i, E H with i i j. Subsequently, we let d be a distance on the set of univariate Borel probability measures such that
P5) # and d(P,, PP)) # 0 for i #
(C2) (Full rank of mixing.) For each [m], the matrix G Gvc.s. E Rdxx. is of full column rank.
By not allowing symmetric distributions in Condition (CI) we assume in particular that the distributions of the errors are non-Gaussian. Nou-Sausyyy together with the assumptions of pairwise different and non-symmetric error distributions allow us to extend the results on identifiability of linear ICA to the unpaired multi-domain setup and to identify the joint distribution. In particular, the assumption of pairwise different error distributions allows for "matching" the distributions across domains to identify the ones corresponding to the shared latent space. Non-symmetry accounts for the iign-indeterminacy of linear ICA when matching the distributions. We discuss the necessity of these assumptions in Remark 3.2 and, in more detail, in Appendix C Note that Condition [CT) always satisfied in generic sense, that is, randomly chosen probability distributions on the real line pairwise different and non-symmetric with probability one. Finally, Condition (2) requires in particular that for each shared latent node k E L there is at least one node E Ve in every domain E [m] such that & E pa(v).
Under Conditions (CT) (C2) we are able derive a sufficient condition for identifiability of the joint distribution. Let PP)) be the set of x p signed permutation matrices. We define the set of signed permutation block matrices:
II {diag( c. Vn...... V.n.) W E SP(() and Vr SP(())))
Our main result the following.
Theorem 3.1. Let Fm be an m-domain graph with shared latent nodes [6], and let Px E M(Gg) with representation (B, P). Suppose that m 2 2 and that Conditions ( CI and (C2) are satisfied. Let
(C, B, P) be the output of Algorithm Then E and
B- v and P TT
for a signed permutation block matrix V IT.
Theorem 3.1 says that the matrix B is identifiable up to signed block permutations of the columns.
Under the assumptions of Theorem 3.1 it holds that B4 P is equal to Px. That is, the joint distribution of the domains identifiable.
Remark 3.2. While Theorem 3.1 is sufficient condition for identifiability the joint distribution, we emphasize that pairwise different enror distributions are in most cases also necessary; we state the exact necessary condition in Proposition in the Appendix. Said differently, if one is willing to assume that conceptually different latent variables also follow a different distribution. then identification of these variables is possible, and otherwise (in most cases) not. Apart from pairwise different error distributions, non-symmetry is then required to fully identify the joint distribution whose dependency structure is determined by the shared latent variables. If the additional assumption on non-symmetry is not satisfied, then it is still possible to identify the shared, conceptually different latent variables, which becomes clear by inspecting the proofs of Theorem 3.1 and Proposition
The non-identifiability of the joint distribution would only result in sign indeterminacy, that is, entries of the matrix / could have a flipped sign.
Remark 3.3. By checking the proof of Theorem 3.1 the careful reader may notice that the statement of the theorem still holds true when we relax the third condition in the definition of an m-domain

---

Algorithm 1 IdentifyJoinn
Input: Probability measures Px- for all [m]]
2: Output: Number of shared latent variables matrix B and probability measure P with indepen- dent marginals.
3: for e [m] do
4: Linear ICA: Find the smallest value 3, such that Px= = = Pd for a matrix B E R x5.
and an dimeenssioaa probability measure pe with independent, mean-zero and unit-variance marginals P..
5: end for
6: Matching; Let é be the maximal number such that there are signed permutation matrices (Q")ee(m) satisfying
a(((")) #P ((0))) T #P =0
for all i i I,..., and for all f + e. Let (1....,
7: Construct the matrix B and the tuple probability measures P given by
I(Q') #P'
[''Q
[ [B'Q'lanE
[(Q') #P" [(Q')*#P'11_ (auve
B
and P
1TQQ" (
[[Qmm)T T pm (3
8: return B.
graph. That is, one may allow directed paths from shared domain-specific latent nodes but not vice versa. For example, an additional edge + 4 between the latent nodes 1 and 4 would be allowed in the graph Figure In this case, the dependency structure of the domains is still determined by the shared latent space. However, the structural assumption that there are no edges between shared and domain-specific latent nodes is made for identifiability of the shared latent graph in Section 4
Remark 3.4. The computational complexity of Algorithm[ deppedds on the complexity of the chosen linear ICA algorithm, to which make calls. Otherwise, the dominant part is the matching in Line 6 with worst case complexity O(m max.g[m] d:),, where we recall that m is the number of domains and de is the dimension of domain
In Appendix D we state complete version of Algorithm [ for the finite sample setting, In particular, we provide a method for the matching in Line based on the two-sample Kolmogorov- Smmirov test. For finite samples, there might occur false discoveries, that is, distributions are matched that are actually not the same. With our method, we show that the probability falsely discovering shared nodes shrinks exponentially with the number of domains.
4 Identifiability of the Causal Graph
We return to our goal of identifying the causal graph Gr = (C, Dec) among the shared latent nodes. By Theorem 3.1 we can identify the representation (B, P) of Px MMGm) from the marginal distributions. In particular, we recover the matrix B B for a signed permutation block matrix V E II. Moreover, we know which columns correspond to the shared latent nodes. That is, we know that the submatrix Bg obtained by only considering the columns indexed by L -= E [C] is equal to Be c. where VA 2 E SP(().
Problem 4.1. Let B Im((9...) for m-domain graph Gm with shared latent nodes L. Given BC V. c with V 4 signed permutation matrix, when is it possible to identify the graph Gc?
2022) and Dai et al. (2022) show that, in the one-domain setting with independent additive noise, the latent graph can be Identified each latent variable has at least two pure children. We obtain a comparable result tailored to the multi-domain setup.
Recently, Xie et al.
Definition 4.2. Let 9m = (HUV, V, D) be an m-domain graph with shared latent nodes L C H. For k E L, we say that observed node e V is partial pure child of k if pa(v) N [k).
7

---

Algorithm 2 Identify ShanedfyShareGGrahh
1: Input: Matrix 8 E IR Vixe
2: Output: Parameter matrix A E Rext
3: Remove rows B from the matrix B that are completely zero.
4: Find tuples (insj))KE with is + ju such that
(i) rank( fi..eehee = for all & E C and
(ii) rank(B (fe..))..)) = 2 for all k q E L with k +
5: Let I = (11......24 ie} and consider Bi,c R
6: Find two permutation matrices R1 and R2 such that W = R₁ e is lower triangular.
7: Multiply each column of W by the sign of its corresponding diagonal element. This yields a new matrix W with all diagonal elements positive.
8: Divide each row of W by its corresponding diagonal element. This yields a new matrix W with all diagonal elements equal to one.
9: Compute Å = T (W')-1
return A.
For partial pure child v E V, there may still be domain-specific latent nodes that are parents of e. Definition 4.2 only requires that there is exactly one parent that in the set L. This explains the name partial pure child; see Example B.2 in the Appendix for further elaboration.
W.l.o.g. assume in this section that the shared latent nodes topologically ordered such that i --> j E Dec implies i < j for all j E L. We further assume:
(C3) (Two partial pure children across domains.) For each shared latent node E 4. there exist two partial pure children.
(C4) (Rank faithfulness.) For any subsets Y V and W C L, we assume that
rank BB,w)=
max B'elm(@am.)
rank (ank(Byyw).
The two partial pure children required Condition C3) may either be distinet domains or in single domain. This is sparsity condition on the large mixing matrix G. In Appendix [C we discuss that the identification the joint latent graph is impossible without any sparsity assumptions. We conjecture that two partial pure children are not necessary, but we leave it open for future work to find a non-trivial necessary condition. Roughly speaking, we assume Condition (Cattion[[C]]
(C4) that no configuration of edge pa- rameters coincidentally yields low rank. The set of matrices B E =Im (g...) ) that violates
(C4) is a sub- set of measure zero Im(@g..) with respect to the Lebesgue measure, Note that our conditions do not impose constraints the graph Gc. Our main tool to tackle Problem 4.1 will be the following lemma.
Lemma 4.3. Let B E Im((g..) for m-domain graph Gm. Suppose that Condition (C4) is satisfied and that there are no zero-rows in Bg. Let v, w E V. Then rank( B (w,ww.c)) = 1 if and only if there is node k C such that both and are partial pure children of k.
The condition on no zero-rows in Lemma 4.3 is needed since we always have rank (v.w).c)) S one of the two rows is zero. However, this is no additional structural assumption since we allow zero-rows when identifying the latent graph; c.f. Algorithm 2 The lemma allows to find partial pure children by testing ranks the matrix Bc. If (1, and (f2, f2) partial pure children of two nodes in L, we make sure that these two nodes are different by checking that rank B (2)...) =
For DAG consistent with the DAG, i.e., E S(G) if and only if (i)) < a(j) for all edges i + D. The following result is the main result of this section.
DV, we define S(G) to be the set of permutations on V elements that are
Theorem 4.4. Let B BV with B E Im
Im(dg.) ) and W E 11, and define B Be to be the input of Algorithm 2 Assume that Conditions (C3) and (C4) are satisfied, and let À be the output of Algorithm Then A= Ac, for a signed permutation matrix Qa with a E S((c). Moreover, if G 0 for G Dyx whenever is a pure child of k. then Qo a permutation matrix.
8

---

Theorem 4.4 says that the graph 9C can be recovered up to a permutation of the nodes that preserves the property that + j implies i < j; see Remark 4.5 Since the columns of the matrix B are not only permuted but also of different signs, we solve the sign indeterminacy column-wiss in Line 7 before removing the scaling indeterminacy row-wise in Line
g In case the coefficients of partial pure children are positive, this ensures that Qo is a permutation matrix and we have no sign indeterminacy. In Appendix D we adapt Algorithm 2 for the empirical data setting, where we only have Bg R Bede. Remark 4.5. Let A be the output of Alg. 2 Then we construct the graph G. = (L,, Dcc)) ) as the graph with edges + i E Dec if and only if Aij + O. Condition (C4)ensuss that Ge is equivalent to Ge in the sense that there is permutation Example 4.6. As highlighted in the introduction, the unpaired multi-domain setup is motivated by applications from single-cell biology. For example, consider the domains of (i) gene expression and (ii) high-level phenotypic features extracted from imaging assays (e.g. McQuin et al. 2018). We argue that the requirement of two partial pure children is justifiable on such data as follows. The condition requires, for example, that for each shared latent variable, (i) the expression of some gene depends only upon that shared latent variable plus -ooaiin-ppccffic latent variables, and (ii) one of the high-level phenotypic features depends only on the same latent feature plus domain-specific latent variables. Many genes have highly specialized functions, so (i) is realistic, and similarly many phenotypic features are primarily controlled by specific pathways, so (ii) is justified.
S(Gc) such that Dec {o) arj) : + Dec).
Remark 4.7. In Algorithm 2 we determine the rank of a matrix by Singular Value Decomposition, which has worst case complexity Omm min (n, m)) for an X matrix. Since Line 4 is the dominant part, we conclude that the worst case complexity of Algorithm is ().
Simulations
In this section we report on a small simulation study to illustrate the validity of our adapted algorithms for finite samples (detailed in Appendix D). We emphasize that this should only serve as proof of concept as the focus of our work lies on identifiability. In future work one may develop more sophisticated methods; c.f. Appendix G The adapted algorithms have a hyperparameter 7, which is a threshold on singular values to determine the rank of matrix. In our simulations we use 7 0.2.
Data Generation. In each experiment we generate 1000 random models with é = 3 shared latent nodes. We consider different numbers of domains m (2,3) and assume that there are Te 2 domain-specific latent nodes for each domain. The dimensions are given by de = d/m /m for all e E [m]] and d = 30. We sample the m-domain graph 9m on the shared latent nodes as follows. First, we sample the graph Gc from an Erdös-Rényi model with edge probability 0. 75 and assume that there are no edges between other latent nodes, that is, between L and H \ L and within H: \ C. Then we fix two partial pure children for each shared latent node k E L and collect them the set W. The remaining edges from L to V W and from H to V are sampled from an Rényi model with edge probability 0.9. Finally, the (nonzero) entries of G and A are sampled from Unif(==00225 1)). The distributions of the error variables coincide, that is, ne = n for all e E [m]. and consider n E (1000, 2500, 5000, 10000, 25000).
specified in Appendix E For simplicity, we assume that the sample sizes
First, we plot the average number of shared nodes in our experiments in Figure (a). Especially for low sample sizes, we see that fewer shared nodes are detected with more domains. However, by inspecting the error bars we also see that the probability of detecting too many nodes i >> E decreases drastically when considering 3 instead of 2 domains. This suggests that the number of falsely detected shared nodes is very low, as expected by Theorem [D3] Our findings show that more domains lead to more conservative discovery of shared nodes, but whenever a shared node is determined this is more certain. Moreover, measure the error in estimating B3 in Figure (b), that is, the error in the "shared" columns. We take
Results.
min 1/-"11 i WESP())
score B (Bz)
min vESP()
$77 /-1/211 111 2lc Bells if ifē> l.
where || ||ا denotes the Frobenius norm and 8g,7 = min (e, Σm de denotes the number
of entries of the matrix over which the norm is taken. In the cases l E, we also measure the

---

3.5
0.05
1.4
3.0
domains
1.2
2 domains
2.5
Median ScorGa
0.04
3 domains
Medlan scare:
2.0
0.03
1.5
0.02
1.0
domains domains
0.4
0.5
0.01
0.2
0.0
0.00
10
10
10
10
10'
Sample
Sample size
Sample
(a)
Figure 3: Results. Logarithmic scale on the axiis.. Error bars in (a) are one standard deviation of the mean and in (b) and (c) they are the interquartile range.
performance of recovering the shared latent graph Gz in Figure (c) by taking
min score A E.) OES(Ge) { AQ. Ac.olL..
As expected, the median estimation errors for Be and Ac.c decrease with increasing sample size. In Appendix [ we provide additional simulations with larger f. Moreover, we consider setups where we violate specific assumptions, such as pairwise different distributions (CI) two partial pure children (C3) The results emphasize that the conditions are necessary for the algorithms provided. The com- putations were performed on single thread of an Intel Xeon Gold 6242R processor (3.1 GHz), with total computation time of 12 hours for all simulations presented in this paper (including Appendix).
Discussion
This work introduces the problem of causal representation learning from unpaired multi-domain observations, in which multiple domains provide complementary information about set of shared latent nodes that are the causal quantities of primary interest. For this problem, in which we can provably identify the causal relations among the shared latent nodes. To identify the desired causal structure, we proposed a two-step approach where we first make use of linear ICA in each domain separately and match the recovered error distributions to identify shared nodes and the joint distribution of the domains. In the second step. identify the causal structure among the shared latent variables by testing rank deficiencies in the "overall mixing matrix" B. To the best of our knowledge, our guarantees are the first principled identifiability results for shared causal representations in general, unpaired multi-domain setting.
laid out setting
We proposed algorithms for recovering the joint distribution and the shared latent space making our proofs constructive. While our focus is on identifiability guarantees, we show in Appendix how our proofs give rise to algorithms for the finite sample setting. Moreover, we propose method to match approximate eтror distributions and show that the probability of falsely discovering shared nodes decreases exponentially in the number of domains. Our work opens up numerous directions for future work as we discuss in Appendix
Acknowledgments and Disclosure of Funding
This project was initiated while the first author was visitor the Eric and Wendy Schmidt Center of the Broad Institute of MIT and Harvard. The project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 883818 18), NCCIH/NIH (IDP2ATO12334 (DE-SC0023187) NSF (DMS- 165 1995), the MIT-IBM Watson Lab, and a Simons Investigator Award. Nils Sturma acknowledges support by the Munich Data Science Institute at the Technical University of Munich via the Linde/MDSI PhD Fellowship program. Chandler Squires was partially supported by NSF Graduate Research Fellowship.
ONR (N00014-22-1-211
DOE-ASCR
10

---

References
Adams, J., Hansen, and Zhang, K. (2021). Identification of partially observed linear causal models: Graphical conditions the non gaussian and heterogeneous cases. Ranzato, M., Beygelzimer, A., Dauphin, Y.. Liang. P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 22822- 22833. Curran Associates, Inc.
Ahuja, K., Mahajan, D., Wang, Y., and Bengio, Y. (2023). Interventional causal representation learning, In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings the 40th International Conference on Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 372-407. PMLR.
Amodio, M. and Krishnaswamy, S. (2018). MAGAN: Aligning biological manifolds. In Dy. J. and Krause, A.. editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 215-223, PMLR.
Anderson, M., Fu, G.-S,, Phlypo, R., and Adalt, (2014), Independent vector analysis: Identification conditions and performance bounds. IEEE Trans. Signal Process., 62(17))4399-4410
Bach, F. R. and Jordan, M. L. (2003). Kernel independent component analysis. J. Mach. Learn. Res., 3(1):1445
Barkas, N., Petukhov, V., Nikolacva, D., Lozinsky, Y., Demharter, S., Khodosevich, K., and Kharchenko, P. V. (2019). Joint analysis of heterogeneous single-cell RNA-seq dataset collections. Nat. Methods, 1688):695-698.
Beckmann, F. and Smith, multisubject 1MRI analysis. Neuroimage, 25(1):294-31) 311.
(2005). Tensorial extensions of independent component analysis for
Beery, S., Van Hom, G., and Perona, P. (2018). Recognition in terra incognita. In Ferrari, V., Hebert, M., Sminchisescu, C., and Weiss, Y., editors, Computer Vision ECCV 2018, pages 472-489, Cham. Springer International Publishing.
Bengio, Y., Courville, A., and Vincent, P. (2013), Representation learning: review and new perspectives. IEEE Trans. Puttern Anal. Mach. Intell. 35(8):1798-I8 -8288.
Bhinge, S., Mowakeaa, R., Calhoun, V. D., and Adalı T. (2019). Extraction of time-varying spatiotemporal networks using parameter-tuned constrained IVA. IEFF Trans. Med. Imaging, 38(7):1755-1725,
Buchholz, S., Besserve, M., and Schölkopf. B. (2022). Function classes for identifiable nonlinear independent component analysis. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D.. Cho, K., and Oh, A., editors. Advances in Neural Information Processing Systems, volume 35, pages 16946-16961. Curran Associates, Inc.
Butler, A., Hoffman, P., Smibert, P., Papalexi, E., and Satija, R. (2018). Integrating single-cell transcriptomic data across different conditions, technologies, and species. Nat. Biotechnol., 36(5):411 1-40.
Calhoun, V. D., Adali, T., Pearlson. G. D., and Pekar, J. J. (2001). A method for making group inferences from functional MRI data using independent component analysis. Hum. Brain Mapp., 14(3):140 140--110-111
Calhoun, V. D., Liu, J., and Adalı, T. (2009). A review of group ICA for fMRI data and ICA for joint inference of imaging, genetic, and ERP data. Neuroimage, 45(1): 163-17..
Cao, K., Gong, Q. Hong, Y., and Wan. L. (2022). A unified computational framework for single-cell data integration with optimal transport. Nat. Comm.. 13(1).
Cardoso, J. and Souloumiae, A. (1993). Blind beamforming for non- non-gaussian signals. IEE Proceedings F Radar and Signal Processing, 140())332..
Chabriel, G., Kleinsteuber, M., Moreau, E., Shen, H., Tichavsky, P., and Yeredor, A. (2014). Joint matrices decompositions and blind source separation: A survey of methods. identification, and applications. IEEE Signal Process. Mag., 31(3):34 43.
Chen, Xie, F., Qiao, J., Hao, Z., Zhang, K., and Cai, R. (2022). Identification of linear latent variable model with arbitrary distribution. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6);6350
Comon, (1994). Independent component analysis, a new concept? Signal Process., 36(3)-877-34.
Comon, P. and Jutten, C. (2010). Handbook of Blind Source Separation: Independent Component Analysis and Applications. Elsevier.

---

Dai, H. Spirtes, P., and Zhang, K. (2022). Independence testing-basedd approach to causal discovery under measurement error and linear non-gaussian models. In Koyejo. S., Mohamed, S., Agarwal, A., Belgrave, Cho. K., and Oh, A., editors, Advances in Neural Information Procexsing Systems, volume 35, pages 15524-27366.. Curran Associates, Inc.
Duren, Z., Chen, X., Zamanighomi, M., Zeng, W. Salpadhy, T.. Chang, H. Y., Wang. Y., and Wong. (2018). Integrative analysis of single-cell genomics data by coupled nonnegative matrix factorizations, Proc. Narl. Acad. Sci., 11 11(33))7723-7722
Ericsson, L.. Gouk, H., Loy, C. C., and Hospedales, T. M. (2022). Self-supervised representation learning: Introduction, advances, and challenges. IEEE Signal Process. Mag. 39(3):22-6..
Eriksson, J. and Koivunen, V. (2004). Identifiability, separability, and uniqueness of linear ICA models. IEEE Signal Process. Lett. 1 117)):01-604
Esposito, F., Scarabino, T., Hyvärinen, A., Himberg, J., Formisano, E., Comani, S., Tedeschi, G., Gochel, R., Seifritz, E., and Di Salle, F. (2005). Independent component analysis of fMRI group studies by self-organizing clustering. Neuroimage, 25(1):193-205
Essen, D. C. V. Smith, S. M., Barch, D. M., Behrens, T. E., Yacoub, E., and Ugurbil, K. (2013). The WU-minn human connectome project: An overview. Neuroimage, 80:62-79.
Gentle, J. E. (1998). Numerical linear algebra for applicaations in statistics. Statistics and Computing, Springer- Verlag, New York.
Gessel, I. and Viennot, G. (1985). Binomial determinants, paths, and hook length formulac. Adv. in Math., 58(3):300-321.
Gossi, F., Pati, P., Chouvardas, P., Martinelli, A. L.,, Kruithof-de Julio, M., and Rapsomaniki, M. A. (2023). Matching single cells across modalities with contrastive learning and optimal transport. Brief. Bioinform. 24(3):bbad130.
Huang. B., Low, J. Xie, F., Glymour. C., and Zhang, K. (2022). Latent hierarchical causal structure discovery with rank constraints. In Koyejo, S., Mohamed. S., Agarwal, A., Belgrave, D., Cho. K., and Oh, A., editors, Advances Neural Information Processing Systems, volume 35, pages 5549-5561. Curran Associates, Inc.
Hyvärinen, A. (1999). Fast and robust fixed-point algorithms for independent component analysis. IEEE Trans. Neural Netw. 10(3):626-634.
Hyvärinen, A. Oja, E. (2000). Independent component analysis: algorithms and applications. Neural Netw., 13(4):411443) 1-430.
Hyvärinen, A. and Ramkumar, P. (2013). Testing independent component patterss by inter-subject inter- session consistency, Front, Hum. Neurosci., 7:94.
Khemakhem, I., Kingma, D., Monti, R., and Hyvärinen, A. (2020). Variational autoencoders and nonlinear ICA: unifying framework. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research. pages 2207-2217. 2.LL
PMLR.
Kim, T., Lee, I., and Lee, T.W. (2006). Independent vector analysis: definition and algorithms. In 2006 Fortieth Asilomar Conference on Signals, Systems and Computers, pages 1399-13396. IEEE.
Klami, A.. Virtanen. S., Leppäaho, E., and Kaski, S. (2014). Group factor analysis. IEEE Trans. Neural Netw. Learn. Syst., 26(9):2136-2147
Li, X.L.,, Adalı, T., and Anderson, M. (2011). Joint blind source separation by generalized joint diagonalization of cumulant matrices. Signal Process. 91(10):2314 4322.
Lin, Y., Wu, T.-Y,, Wan, S., Yang, J. Y., Wong, W. H., and Wang. Y. (2022). scJoint integrates atlas-scale single-cell RNA-seq and ATAC-seq data with transfer learning. Nat. Biotechnol, 40(5):003-77
Lindström, B. (1973). On the vector representations of induced matroids. Bull. London Math. Soc., 5:85-90.
Liu, J., Huang, Y. Singh, R., Vert, J.-P., and Noble, W. S. (2019), Jointly embedding multiple single-cell omics measurements. In Huber, K. T. and Gustield, D., editors, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019), volume 143 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:13, Dagstuhl, Germany. Schloss Dagstuhl Degstuhl-Leibni-- Zentrum fuer Informatik.
12

---

Liu, Y., Zhang, Z., Gong, D., Gong. M., Huang, B., Hengel, A. v. d., Zhang, K., and Shi, J. Q. (2022). Identifying weight-variant latent causal models. arXiv preprint arXiv:2208.1411 14153.
Lopez, R.,. Tagasovska, N., Ra, S., Cho. K., Pritchard, J., and Regev, A. (2022). Learning causal representations of single cells via sparse mechanism shift modeling. In NewriPS 2022 Workshop on Causality for Real-world Impact.
Lukie, S., Wemiic, M. N., Hansen, L. K., and Strother, S. C. (2002). An ICA algorithm for analyzing multiple data sets, Proceedings. International Conference on Image Processing, volume pages 821 824. IEEE.
Lyche, T. (2020). Numerical linear algebra and matrix factorizations, volume 22 of Texts in Computational Science and Engineering. Springer, Cham. With foreword by Geir Dahl.
Maneshi, M., Vahdat, S., Gotman, J., and Grova, C. (2016). Validation of shared and specific independent component analysis (SSICA) for between-group comparisons in IMRL. Front. Neurosci. 10:417.
McQuin, C., Goodman, A., Chernyshev, V., Kamentsky, L., Cimini, B. A., Karhohs, K. W. Doan, M., Ding. L., Rafelski, S. M., Thirstrup. D., Wiegracbe, W., Singh, S., Becker, T., Caicedo, J. C., and Carpenter, A. (2018). CellProfiler 3.0: Next-generation image processing for biology. PLOS Biol., 16(7)==0005970.
Mesters, G. and Zwiemik, (2022). Non-independent components analysis. arXiv preprint arXiv:2206. 13668.
Miller, K. L.. Alfaro-Almann Aitaaoo, F., Bangerter, N. K., Thomas, D. L.. Yacoub, E., Xu, J.. Bartsch, A. J., Jbabdi, S., Sotiropoulos, S. N., Andersson, J. L. R., Griffanti, L.,, Douaud, G., Okell, T. W., Weale, P., Dragonu, I., Garratt, S., Hudson, S., Collins, R., Jenkinson, M., Matthews, P. M., and Smith, S. M. (2016). Multimodal population brain imaging in the UK biobank prospective epidemiological study. Nat. Neurosci, 19(11)1123--156.
Nielsen, A. A. (2002). Multiset canonical correlations analysis and multispectral, truly multitemporal remote sensing data. IEEE Trans. Image Process., 11 113):293-305.
Pandeva, T. and Forré, P. (2023). Multi-view independent component analysis with shared and individual sources. In Evans, R. J. and Shpitser, I., editors. Proceedingy of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligenee volume 216 of Proceedings of Muchine Learning Research, pages 1639-1650. PMLR.
Richard, H., Ablin, P., Thirion, B., Gramfort, A., and Hyvärinen. A. (2021). Shared independent component analysis for multi-subject neuroimaging, Adv. Neural Inf. Process. Syst., 34:29962 29971.
Roeder, G., Metz, L.,, and Kingma. D. (2021). On linear identifiability of learned representations. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9030 90000-999,..000 PMLR.
Schölkopf. B., Locatello. F., Bauer, S., Ke, N. R., Kalchbrenner, N., Goyal, A., and Bengio, Y. (2021). Toward causal representation learning. Proc. IEEE, 10965)6612-634
Shafto, M. A., Tyler, L. K. Dixon, M., Taylor, J. R., Rowe. J. B., Cusack, R., Calder, A. J., Marslen-Wilson, W. D., Duncan, J., Dalgleish, T.. Henson, R. N., Brayne, C., and Matthews, F. E. (2014). The cambridge centre for ageing and neuroscience (cam-CAN) study protocol: a cross-sectional, lifespan, multidisciplinary examination of healthy cognitive ageing. BMC Neurol., 14(1).
Shimizu, S., Inazumi, T., Sogawa, Y., Hyvärinen, A., Kawahara, Y., Washio, T., Hoyer, O., and Bollen, (2011). DirectLiNGAM: a direct method for learning a linear non-Gaussian structural equation model. J. Mach. Learn. Res., 12:1225-1248.
Silva, R., Scheine, R., Glymour, C., and Spirtes, (2006). Learning the structure of linear latent variable models. J. Mach. Learn. Res., 191):49.
Squires, C., Seigal, A., Bhate, S. S., and Uhler, C. (2023). Linear causal disentanglement via interventions. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research. pages 32540-333000 32560. PMLR.
Stuart, T., Butler, A., Hoffmman P., Hafemeister, C., Papalexi, E., Mauck, W. M., Hao, Y., Stocckius, M., Smibert, P.. and Satiaa R. (2019). Comprehensive integration of single-cell data. Cell, 177(7):1888 1888-1902.
Sui, J., Adali, T., Pearlson, G. D., and Calhoun, V. D. (2009). An ICA-based method for the identification of optimal FMRI features and components using combined group-diseriminative techniques. Neuroimage, 46(1):73-88 86.
Svensén, M.. Kruggel, F., and Benali, H. (2002). ICA of fMRI group study data. Newroimage, 16(3):551-563.
13

---

van der Vaart, A. W. and Wellner, J. A. (1996). Weak convergence and empirical processev. Springer Series in Statistics. Springer-Verlag, Verlag, New York. With applications statistics.
Varoquaux, G., Sadaghiani, S., Poline, J. B., and Thirion, B. (2009). CanICA: Model-based extraction of reproducible group-level ICA patterns from IMRI time series. In Medical Image Computing and Computer Aided Intervention, page 1.
Wang. X., Hutchinson, R., and Mitchell, T. M. (2003). Training fmri classifiers detect cognitive states across multiple human subjects. Thrun, Saul, L., and Schölkopf, B., editors, Proceedings of the 16th International Conference on Neural Information Processing Systems, volume 16, pages 709-716, MIT Press.
Wang. Y. Drton, M. (2020). High-dimensional causal discovery under non-Gaussianity. Biometrika. 107(1):41-59.
Welch, J. Hartemink, A. J., Prins. F. (2017). MATCHER: manifold aligument reveals correspondence between single cell transcriptome and epigenome dynamics. Genome Biol., 18(1):1-19.
Xie, F, Cai, R., Huang, B., Glymour, C., Hao, Z., and Zhang, K. (2020). Generalized independent noise condition for estimating latent variable causal graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Adv. in Newral Inf. Process. Syst., volume 33, pages 14891-14902. Curran Associates, Inc.
Xie, F., Huang, B., Chen, Z., He, Y., Geng, Z., and Zhang. K. (2022). Identification of linear non non-Gaie GauGaassian latent hicrarchical structure. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 24370-24387, PMLR.
Yang, K. D., Belyaeva, A.. Venkatachalapathy, S., Damodaran, K., Katcoff, A.. Radhakrishnan, A., Shivashankar, G. V., Uhler, C. (2021a). Multi-domain translation between single-cell imaging and sequencing data using autoencoders. Nat. Comm., 12(1).
Yang. K. D. and Uhler, C. (2019), Multi nolti-domain translation by learning uncoupled autoencoders. Computational Biology Workshop, International Conference on Machine Learning.
Yang, M., Liu, F., Chen, Z., Shen, X., Hao, J., and Wang, J. (2021b). Causalvac: Disentangled representation learning via neural structural causal models. In Proceedings of the IEEE/CVF Conference on Computer Vision and pattern Recognition (CVPR), pages 9593-9602.
Yuan, Q. and Duren, 7. (2022). Integration of single-cell multi-omics data hy regression analysis on unpaired observations. Genome Biol., 23(1):1-19.
Zeng, Y., Shimizu, S., Cai, R., Xie, F,, Yamamoto, M., and Hao, Z. (2021). Causal discovery with multi-domai lingam for latent factors. In Zhou, Z.-H., editor, Proceedings of the Thirtieth International Joins Conference on Artificial Intelligence, IJCA/-21, pages 2097-2103. International Joint Conferences Artificial Intelligence Organization, Main Track.
Zhu, J.-Y., Park, T., Isola, P., and Efros, A. (2017). Unpaired image-to-image translation using cycle-eonsistent adversarial networks. In 2017 IEEE International Conference on Computer Vision (ICCV), pages 2242-2251.
Zhuang, F., Qi, 7 Duan, K., Xi, D., 7hu, Y., 7hu, H., Xiong, H., and He, Q. (2021). A comprehensive survey on transfer learning. Proc. IEFE, 109(1)433776
14

---

A Proofs
Proof of Theorem 3.1 Let Px MG)..) for m-domain graph 9m (HUV,)) with shared latent nodes L = E and representation (B, P). By Condition (CT) the measure P has independent, non-degenerate, non-symmetric marginals Pt. i H with mean zero and variance one. Moreover, since B E Im( ), we have B = G(I A) for matrices G E Rv and A E R
Fix domain [m]. Recall that denote by S. = pa(V.) C Ie the set of latent parents in domain e. Define the matrix
B = S.v....111 A) ") = GO - - S..5.
and observe that we can write Px. = B Ps. This is due to the fact that Gv,,H O and [[T- 1/-AA -) "). H.SS. 0 by the definition of an m-domain graph.
In particular, the equality Px= 1=# #ss shows that the representation in Line of Algorithm exists. Now, we show that is unique up to signed permutation by applying results on identifiability linear ICA. Since GO has full column rank by Condition (C2) and [(- A)- is invertible, the
matrix B also has full column rank. Let Px- = B #P P be any representation, where Be E Rdd and P is an fe-dimensional probability measure with independent, non-degenerate marginals P.- Due to Condition (CI) all probability measures P; are non-Gaussian and non-degenerate and therefore we have by Eriksson and Koivunen (2004 Theorem and 4) the identities
B = B'R and P = A (R") #Ps.
where A is Se Se diagonal matrix with nonzero entries and R is Se Se permutation matrix. In particular, have &, Se, which means that Be R and that pe is s.-dimensional probability measure. Line 4] also requires that each marginal PE has unit variance. This removes the scaling indeterminacy in (3) and we have
B B"R and P = T
where D is diagonal matrix with entries D E {+1}. In particular, this means that the distributions pe and Ps. coincide up to permutation and sign of the marginals.
The matching in Line 0 identifies which components of pe are shared. By Condition (CI) two components of different domains P. and Pj shared if and only if they coincide up sign, that is, if and only if d .P) = 0 or , 0 but not both since Condition of the error variables to be non-symmetric. We conclude that in each domain e E [mx] there exists an Se 8. signed permutation matrix Q such that
0. If their distribution coincide up to sign, than
either ((P..Pf = 0 or (
(C1) requires the distribution
d(((Q)) #P%) (PO)),((()) #PP =
for all I,..., and for all f * In particular, 7= and E ==
remains to show that ß B& and P T #P for a signed permutation block matrix II. By Equation (4) the distributions [(Q") #P and [(Q") #Po coincide, which means that
Pc Pl
#Ps.
#
(5)
V.
where Ve is an signed permutation matrix and v is an [el x |el signed permutation matrix. Importantly, the matrix T does not depend on the domain [m]. Hence, the matrix
te : Re De is signed permutation matrix with block structure as in Equation (5). Moreover,
we have
BOQ B = B (B2 Vr.,
15

---

which means that the matrix B can be factorized as
[B'Q
[B'Q")RN
B
[BTQQTL
1 Qm
(..0112)
B2 v
b.l 1
B7 VE
B [sm N Im
B2
Blailic
V L
11
=
V,
BE
Bm [sm]VC/
V mm
where V II Similarly, we have for all E [m]]
(V)) - T #Pc (V.1)) TPP1.)
(Q") # = PPs.
We conclude that
((Q))+#P11B
(V22 #Pc
[[Q')) #P 13,112
(1))) #1,
p=
1(Q2) T 1....V
(10 "..) #1
T
Pe
M
Pi
#
v T #P.
Pi
I..
Before proving Lemma 4.3 and Theorem 4.4 we fix some notation. Let 9m (V U H, D) be an m-domain graph. We denote by anc(r) k H there is directed path 1: + ... - in 9m
the ancestors of node v V. For subsets W C we denote anc(W) = Uvew anc(w). Moreover,
for _ H and E V, we write shortly (v) pa(v)
Proof of Lemma
4.3
Let B E Im(Øg.... ). Then we can write B = G (I A) with
Gvi.
Gv
G=
GVm.C
Gvm
Moreover, observe that, by the definition of an mn-omain- ggrap,, matrix Bv.c factorizes as
Bv. = Gv. 1)_.,
Now, suppose that i and j are partial pure children fixed node C. Then (ta(t) [k} (j). In particular, the only entry that may be nonzero in the row Gj is given by Gs and the only entry that may be nonzero the row Gj.C given by Gyk- Thus, we have
Bic Gig A) "), Gik (5x[(T A) -1.c.
GEC
Similarly, it follows that Bj.C- = - This means that the row Bj.c is multiple of the row B.g and we conclude that rank( (nnk(Bu)).c) 1. Equality holds due to the faithfulness condition (C4) which implies that Bi * 0 and By * 0, i.c.. B c is not the null matrix.
16

---

For the other direction suppose that rank B (i.))..)) .c) = 1. By applying the Lindström Gennnn-Geee----eee -iiennot
Lemma (Gessel and Viennot 1985 Lindström 1973) equivalently as in Dai et al. (2022) and 2), it can be seen that
Theorem I
rank ((..).c) S min ([S) S vertex eut from anc (C) to (i.5]),
where S is a vertex cut from anc(C) to {i.j} if and only if there exists no directed path in Gm from (C)( to { without passing through S. Moreover, equality holds in (6) for generic (almost all) choices of parameters. Since we assumed rank faithfulness in Condition (C4) we exclude cases where the inequality is strict and therefore have equality. By the definition of an m-domain graph we have that anc(E) (C) L. Thus, if rank ( = 1, there must be a single node k E L such that {k} is vertex cut from L to {i But then it follows that i and j have to be partial pure children of & by the definition of an m-domain graph and by using the assumption that there are no zero-rows in Be. C
To prove Theorem 4.4 we need the following auxiliary lemma.
Lemma A.1. Let = (V, D) be a DAG with topologically ordered nodes V == [p] and let M be
lower triangular matrix with entries Ma # for all i = 1, ...... .p and M.j * 0 if and only if there a directed path j +..... -..-- in G. Let Qa and Qa2 be permutation matrices. Then the matrix
Qo, MQo, is lower triangular if and only if 02 = of and 02 E S(G).
Proof of Lemma A.I By the definition of permutation matrix, we have
[Qo, MQu,li M Ma, (0) or, equivalently, (Q0. Maj-
(7)
First, suppose that 02 = oj and E S(G), and let i.j E [p] such that (1) < o2(i). Then, by the definition of S(G), there is no directed path + - in the graph G and therefore we have Mij = O. But this means that [Q,, MQ (Qozla(()e2()) = and we conclude that the matrix Q. MQ.. is lower triangular.
Now, assume that 2o is lower triangular, where d, and 02 are arbitrary permutations on the set [p]. Since M has no zeros the diagonal, we have Mü [Q,, M Qo2la, (())a(()) * 0 for all = ... .p. lower triangular. But this only possible the permutations coincide on all elements, i.e., we have 02 of It remains to show that o2 o, S(G). For any edge +
It follows that (i) 2 Ø2(1) for all i = 1,..., ..... because Qa, MQ.,, is
D we have that Ma # O. Recalling Equation 7 this means that [Q,, MQQzlog(()ra()) * O. But since Qo, MQ., is
lower triangular this can only be the case if x2(5) < (i) which proves that 02 E S(G))
Proof of Theorem 4.4 Each latent node in L has two partial pure children by Condition (C3) After removing zero-rows in Line of Algorithm 2 it holds by Lemma 4.3 that rank B ((,))c) and only if there is a latent node in L such that and j are both partall pure children of that latent node. Hence, each tuple (ik. f&x keE Line of Algorithm 2 consists of two partial pure children of
if
a certain latent node. The requirement rank [B* (b..).).c) 2 ensures that each pair of partial pure
children has different parent.
By the definition of m-domain-graph and the fact that B Bc, for 1 = de), we have the factorization
Bi,- = Br.c = Gr.c - -))_ = GI,elI - Ac,c) -V VVe.
(8)
where G E RVN, A E RRC and V is a signed permutation matrix. Let Q1 and Q2 be permutation matrices and let A be a diagonal matrix with non-zero diagonal elements and let D be diagonal matrix with entries in [+1]. Then we can rewrite Equation (
Bi.c = A - Ac.e) DQQ
M.M
Now, we apply Lemma A.I Since we assume throughout Dection[4than the nodes L are topologically ordered, the matrix M is lower triangular with no zeros on the diagonal. Moreover, by Condition (C4) we have Mj * 0 if and only if there is a directed path j . in Ge- In d we find other permutation matrices R2 and R₂ such that
W = R, Ra (Q2R2)
17

---

is lower triangular. Now, define the penmutation matrices Qo, = R1Q1 and Qo Q2R2. Then we have by Lemma A.1 that Q. = Qo and that 02 E S( Hence, the matrix W factorizes as W Q MQ Qa A(T Ac,e)
AQ. Ac,
where and D are diagonal matrices with the entries given by permutations of the entries of A and D. Lines 7 and 8 address the scaling and sign matrices A and D. In particular, we have that Ac,c)='Qer D' for another diagonal matrix D' with entries in {=1}, since each entry on the diagonal of W is equal to 1. Thus, we have
W = D'Q
À - (W"--
I - (D'Q, -I- -I-Ac,)) -c,
I --- Ac,,))m22 D'Q. Ac, D'.
Since Qr D' is signed permutation matrix with 02 E S(Cc), the first part of the theorem proved. If Gok > O whenever is a pure child of k, the matrix A only has positive entries which means that D' is equal to the identity matrix. This proves the second part.
B Additional Examples
The graph Figure is an m-domain graph corresponding to the compact version Figure 2 the main paper.
Example B.1. Consider the m-domain graph in Figure The linear structural equation model among the latent variables is determined by lower triangular matrices of the form
0
Q:1
0
0
043
Moreover, the domain-specific mixing matrices Go are of the form
0
9i1
912
gis
0
0
9b3
921
922
92a
G
and G
9
932
933
931
9
912
9ï3
941
942
943
944
961
962
0
Since the shared latent nodes are given by L. = {1, 2).
we have
Mi1
giz
g
121
O
823
0
0
O
932
933
934
J
912
943
G
911
O
0
0
921
932
0
0
923
942
0
943
951
952
0
and
(221g12 + +gl
912
9
0
0
921
0
423
0
0
021932
g32
0.39
+ 933
J34
021942 d4l
942
0430
44
943
Iás
G- B-G-(I-A)-
gii
0
0
a21952 + +
0
953
021033
932
0
0
0
021g22 941
962
0
0
92
a21952 g51
952
0
18

---

Figure 4: 2-domain graph with latent nodes and dimensions of the observed domains given by IV d1 = 4 and [V2 d2 5. We denote Ve fof...., á J. that is, the superseript indicates the domain a node belongs to.
Example B.2. Consider the m-domain graph in Figure 4 The partial pure children of node E L are given by [ug. of) and the partial pure children of 2 E are given by {ug. vz)- Moreover, by continuing Example B.T have that the matrix Bg is given by
021912 + 911 921
912
021932
932
021942 + 941
942
Be
911
021 922 921
932
021932
932
021 + 941
94p
@21 951
952
It is easy to see that the two submatrices
(22 (221932
and
(221332
932
have rank one. The first matrix corresponds the partial pure children {ug, vf in the graph in Figure 4 while the second matrix correspond to the partial pure children {ug, Ug). Note that the rank of any other 2 submatrix generically (i.e., almost surely) equal to
211
C Discussion of the Assumptions
In this section, we discuss aspects of Conditions (CI) (C3) that allow for identifiability. In particular, we discuss the necessity of pairwise different non-Gann non-Gaussian error distributions if one is not willing to make further assumptions. Moreover, we elaborate on the sparsity conditions the mixing matrix and explain why some sparsity assumption necessary.
Pairwise Different Error Distributions. Given any two potentially different m-domain graphs 9m = (H UV, D) and T. = (H V, D). identifiability of the joint distribution in multi-domain causal representation models means that
Bv Ass. By #P. for all E [m]] - B#P BBP=B4P
any representation (B, of distribution in M(Gm) and any representation (B, J3,77 P) of distribution in M(G)), where the matrices Bv,,s, and By have full column rank for all e [m]] The left-hand side says that the marginal distributions in each domain are equal, while the right-hand side says that the joint distributions are equal. If there are m-domain graphs, such that the left-hand sides holds but the right-hand hand side is violated, then we say that the joint distribution is not identifiable
We assume in this section that the marginal error distributions P.. i H. are non- Con-Gausiian and have unit variance, but are not necessarily pairwise different or non-symmetric. Then the right-hand side holds if and only if the number of shared latent nodes in each graph is equal, i.e., l = E, and there is signed permutation matrix V such that B B and P v/ #P. Here, the matrix w does
19

---

not necessarily have a block structure. The equivalence is implied by the identifiability of the usual, one-domain linear ICA ( see, e.g.. Buchholz et al. (2022) together with the fact that for i + E, we have [7| A [H] and, therefore, the distributions on the right-hand have support over different dimensional subspaces.
Theorem 3.1 shows that assumptions (CI) and (C2) are sufficient for identifiability of the joint distribution. In particular, we show that they imply identifiability in a stronger sense, namely, that follows from the left-hand side that l = l and B = By and P = Vr # P for a signed permutation V E II with block structure. The next proposition reveals necessary conditions for identifiabiltyy.
Proposition C.1. Let 9m be m-domain graph with shared latent nodes -= [d] and let Px M(mm) with representation P). Suppose that m 2 2 and that everything except the assumption about pairwise different error distributions in Conditions [CT] and is satisfied. Then, the joint distribution is not identifiable if one of the following holds:
(i) There is i.j E such that P; = PP or -P--P-
(ii) There is E L Cand j E for some [m]] such that P. P; P; P:
(iii) For all [m]] there is ig E Le such that P., Pj, P., -P, for all e # f.
Proof. For each of the three cases, we will construct another m-domain graph 9m (H U UUU D) such that for suitable representations (B, P) of distributions in M(Gm), the left-hand side of (9) holds, but the right-hand side is violated.
To prove the statement for case (i), let let i,j L and assume that P, Py. We define the m-domain graph G. = (H U VV, D) to be the almost same graph as Gm = ( H U V, D). we only "swap" the roles [m]] That is, for each E Ve, if there was an edge i > in D, we remove that edge from D and add the edge j + v instead, and vice versa. Otherwise, the graph 9m has the same structure as Gm. Now, let P P and define the matrix B to be the same matrix as B, except for the subcolumns Bv,,; == Bv.,, and Bv..j = Bv that is, we swapped Bv.,: and Bv... Then the pair (B, P)) is representation of some distribution in M(G.... Recall from the proof of Theorem 3.1 that Condition (C2) implies that the matrix Bv..s. has full column rank. Since we only swapped columns in B By it still has full column rank. Moreover, observe that the left hand side of (9) is satisfied since P, = Pj. that is, the marginal distributions on the single domains coincide.
of the latent nodes and j
arbitrary domain
However, now consider another domain I [m]] and the submatrices
Bv., By. and BrLuv,, =
(Bv..s Bv Bv Bv,j)
By.uv =
By
Byys)
Since all of the four subcolumns are nonzero and neither By is equal to Bv, nor By, is equal to B there is signed permutation matrix Ω such that By,uv,, By Hence, there is also no larger signed permutation matrix Vi such that B BV, We conclude that the right-hand side of (9) is violated and the joint distribution is not identifiable. Finally, note that the above arguments also hold if P. P, by adding "_" signs in appropriate places.
The proof for case (ii) works with exactly the same construction. That is, for i E L and j Le we swap the roles of i j on the domain e. Then, for any other domain f E [m]) we obtain the submatrices
Bv B 0
B
BBvs Bvy
Bv. 0
)
By.uV,,(1.)) =
and Bv.uv, =
By the same arguments as before, this shows that there is no signed permutation matrix v such that B = By and, hence, the joint distribution is not identifiable.
To prove case (iii), we consider slightly different construction. However, we also assume that
P.. = P., for all e + f. since for P., P., we only have to add some "_" signs in the following.
We define the m-domain graph T... (H V, D) by identifying the nodes ic, e [m]] with new
20

---

node k. That is, -= LU {k} and 7z = (U.etm) Le \ (ie)) For i E H. {k} and v E V, the
edge set D contains an edge i + if and only if the edge + v is in D. For the node k E H and E V, we put an edge k + v in D if and only if there is an edge le + in D for some [m].
By and Bv, := Bv.,.. for all [m]. Then the pair (B, P) is a representation of some distribution in M(G).. Moreover, each submatrix B Vv.33. is equal to Bv..s, up to relabeling of the columns. That is, the column that is labeled by ée
Now, define the matrix B such that By.
in Bv..s. now labeled by i in Bv. 3." We define the measure such that PiA( = PRAte and
Ps. = P:. for all e E [m]] Then the pair (B, P) is representation of some distribution in M(Gm) and, in particular, the left hand side of (9) is satisfied. That is, the marginal distributions coincide on each domain. However, the number of shared latent variables in both m-domain graphs is different
since we have f = l + 1. We conclude that the joint distribution is not identifiable
The proposition states that it is in most cases necessary that error distributions are pairwise different. However, in two cases the same error distributions still lead to identifiability. First, if i, Le. then the corresponding error distributions may be the same and the joint distribution is still identifiable. Similarly, if there are latent nodes iz in a few domains E [mm] such that the corresponding error distributions coincide, but there is at least one domain f e [m]] where there is no latent node with the same error distribution, then the joint distribution is also identifiable. Both can be seen by taking the the proofs of Theorem 3.1 and Proposition C.I together.
Gaussian Errors. Without additional assumptions to those in Section 3 it is impossible to recover the joint distribution the distributions of the errors & of the latent structural equation model in Equation (I) are Gaussian. In this case, the distribution of Z as well as the distribution of each observed random vector X is determined by the covariance matrix only. The observed covariance matrix in domain E [mm] is given by Σ = Co [Ge) However, knowing Σe gives no information about Zour. other than rank(E*) = [C] + Meel that is, we cannot distinguish which latent variables are shared and which ones are domain-specite This is formalized in the following lemma.
Lemma C.2. Let Σ be any d x d symmetric positive semidefinite matrix of rank p and let E be another arbitrary p x p symmetric positive definite matrix. Then there is G E RRdP such that Σ = GEGT.
Proof. Let > be a dxd symmetric positive semidefinite matrix of rank p. Then, has decomposition similar to the Cholesky decomposition; see c.g. Gentle (1998) Section 3.2.2). That is, there exists a unique matrix T,, such that = TT where T' is lower triangular matrix with p positive diagonal elements and - p columns containing all zeros. Define T to be the x p matrix containing only the non-zero columns of T.
On the other hand, let E be a symmetric positive definite p X p matrix. By the usual Cholesky decomposition (Lyche 2020 Section 1.2.1), there exists a unique p X lower triangular matrix L with positive diagonal elements such that = = LL Now, define G : TL-1 e Rdxp, Then,
Σ T-TTT = -T- L = GEG
Due to Lemma C.2 it is necessary to consider non-Gaussian distributions to obtain identifiability of the joint distribution.
Example C.3. In the Gaussian Figure Sharee a latent variable or not. Said differently, the observed marginal distributions may either be generated by the mechanism defined by graph (a) or graph (b) and there is way to distinguish from observational distributions only.
we cannot distinguish whether the two observed domains in
Sparsity Assumptions. Let B E lm((h...) for an m-domain graph 9m (HUV D) and suppose that we are given the matrix Bg Gv.e(T- Ac,c)-1, that is, we are given the submatrix with columns indexed by the shared latent nodes. Now, assume that the graph does not impose any sparsity restrictions on Gy.c, which means that the set I Pve of possible matrices Gy.c is equal to [ Then, the set of possible matrices Bg also unrestricted, that is, Bg can be any matrix in R x x|4 no matter the form of the matrix A P2c In other words, for arbitrary shared latent graphs
21

---

1
2
3
4
V1
22
V12
12
(h)
Figure 5: Compact versions of two 2-domain graphs. In both graphs, both domains have two latent parents, In setup (a) there is a shared latent parent while setup (b) there is not.
9c = (C, Dec) and arbitrary corresponding parameter matrices AC,c Recc don't get any restrictions on the matrix Bc. Therefore, it is impossible to infer Ac,C from Bg-
C33 requires that there are two partial pure children for every shared latent node k E C, which implies that there are 2 C] rows in Gv.c in which only one entry may be nonzero. While we show in Theorem 4.4 that this condition is sufficient for identifiability of Ac.c, we leave it open for future work find a necessary condition.
Condition
D Algorithms for Finite Samples
We adjust Algorithm such that it is applicable in the empirical data setting. That is, rather than the exact distribution Pxs, we have a matrix observations X E Rd. in each domain E [m]. The sample size n, might be different across domains. We denote Rmin = min.e (m] and Mmmax = max Ve. For implementing linear ICA on finite samples, multiple well developed algorithms are available, e.g.. FastICA (Hyvärinen] 1999 Hyvärinen and Oja, 2000), Kernll ICA (Bach and Jordan (003) or JADE (Cardoso and Souloumiac 1993). Applying them, we obtain measure P. which is an estimator of the true measure P. in Algorithm Line
The remaining challenge is the matching in Line of Algorithm [ For finite samples, the distance between empirical distributions is almost surely not zero although the true underlying distributions might be equal. In this section, we provide matching strategy based on the two-sample Kolmogorov- Smirnov test (van der Vaart and Wellner 1996, Section 3.7). We match two distributions if they not significantly different. During this process, there might occur false discoveries, that is, distributions are matched that are actually not the same. We show that the probability falsely discovering shared nodes shrinks exponentially with the number of domains.
For two univariate Borel probability measures P., Pj, with corresponding cumulative distribution functions F,, Fj. the Saamnogorov-Smimne distance is given by the L - -distance
dxs( (P., P3) = |F, F, llce
sup [x( F)(1))- sER
The two-sample Kolmogorov-Smimoo test statistic for the null hypothesis Ho d Pf) = 0 is given by
T(P: P/)
Belly mee +
dks( Pf.
(10)
is important to note that Pr not an empirical measure in the classical sense since it is not obtained from data sampled directly from the true distribution Pe In addition to the sampling error there is the uncertainty of the ICA algorithm. However, in the analysis we present here, we will neglect this error and treat Pe as an empirical measure. In this case, under Hg, the test statistic T(P: P.)) converges in distribution to ||]]] where B is a Brownian bridge from 0 to 1 (van der Vaart and Wellner 1996, Section 2.1). For given level E (0, 1), choose the critical value as 1) S a) and reject Ho if T(P; po. Ca-
Ca iinf(t: P([ B
Definition D.1. Let E (0, 1) and suppose the distributions {Pr pe and (Pf... ..... Pf } are
given for two domains e, f E [m]. Define
if TT I ca and T = min/minkerr, Tel minkers, Tel }
Ps (P: (P,) = 0 else,
22

---

where To = min min - We say that P Pf are matched if Qa (P, p/) 1.
Definition D.1 essentially states that two measures are matched the test statistic (10) is not significantly large and the null hypothesis cannot be rejected. Taking the minimum of T(P: P and
T(P;. -P.) accounts for the sign indeterminacy of linear ICA. For two fixed domains e, f [m]] if
it happens that the statistic T for multiple pairs (i,j) is small enough, then the pair with the minimal value of the statistic is matched. Note that one may use any other test than the Kolmogorov- Smimnov test to define matching in Definition D.I We discover shared latent node if it is matched consistently across domains.
Definition D.2. Let C' = (mm) be tuple with m elements such that ig [..]. Then we say that C' determines a shared node if Pa P.A) = 1 for all ie, i E EC
Inferring the existence of a shared node which does not actually exist may be considered a more serious error than inferring shared node determined by set C, where only some components of C are wrongly matched. In the following theorem we show that the probability of falsely discovering shared nodes shrinks exponentially with the number of wrongly matched components.
Theorem D.3. Let C = (i1...., im)) be tuple with m elements such that ie E [Fe)). Let N x R20 >> R2z a function that is monotonically decreasing
N and assume the following:
(i) P(dks(Pr
Pr. tot PT.) > x) S g(e. x) for all e E [m]] and for all x 2 O.
(ii) There is E S [mm] with |E| 2 2 and a constant k > such that dxs(Pr. p.f) 2 and : 2 K. for all E E, f E [m]] with # f.
Then
V Co. 0 of)
)))
181-1
P(C determines a shared node) S g Aminn max
/2 Amin
Proof of Theorem D.3 Let C' = (i1...., im) and g be as in the statement of the theorem. W.L.o.g.
we assume that E = (1..... [E]} and that T(P: P/.) < T(P - Pt,) Observe that C' determines a shared node if and only if
Qa(P: i.: (p))) = m Σ ekf
2
Now, we have
P Σ Sa Qa(P.. mKS
(m) (m)
=P
n n
aal Qa Pt. Pt) = 11)
lec
<P
n
(Tel s sca))
T(P:: P.,)) s ca (TPP s scat))
n
T(PS P,f) sca)
P
leef
S(Pr,Pyf s cx)) sat)
<P
(II)
ocf
By the triangle inequality we have
dks (P., P,,) S dks( Pr.) + dks Prc P,.)) dks( dxs P!))
(12)
23

---

Moreover, if e E E and f [m]. then we have by Condition (ii)
dks( P P.
3o 2 6.
(13)
Using 12 and 13 together with the fact v
Ra natny
Dmin
we obtain the following chain of
implications for E and f [m]]
T(PE. P..)) S ca
Delly
dxs( P (.;) S Ca
V ne +Ng
Panin
dks (Pi,
Pi P!,) dxs( Pi; P..) - desl (iss iq. P.,)) S
Mm Amin
K drs( (i, P...) dksl (Pf "s; Pif)) S Ca
mm
v 22 Ca
dRs Pr, P..) dxsl dxs(Pif, P..)
Timin
(des( P.. 2
k
Vinaax Ca ) or dks dxs(P/
p.. P.) p2))2
K
/mmax
Co
v2 Nmii
Temin
Now, consider the event DEEE.EEMm) ec,
(T(P: p..) S c. On this event, there cannot be two elements
e, J E E such that both
[ks 1o Pe
K
22 Mmin ca and
Vmmax
{ (kss(P,, p.f)
K
/mmax
Coi
2
2
/2 Ammn
To this recall that E' [m]. We conclude that it must hold {dks Pr. P.
v2 Paii for we
Momax
all but most one element of E. We denote this exceptional element by e" E E. Taking up get the following:
P
Σ l6<
PP
P..
(m)
(m)
[T(Pr, P.,)) S ca
SP
LeEE.fE[m) e<{
<
dks( Pe to:
2 k
Pmmax
Co
2
22 Amin
II eEB((e")
(ks Pe. P..) lo:
Tmmax
Ca
(14)
V2 Nunin
/mmax Cao 0
II eEBi(e*)
d P.) max
(15)
v2 nemin
|1|-1
K
Tmmax
5 Rmin: max
Ca.
(16)
/2 Dauin
The last three steps need more explanation: Equality (4) follows from the fact that domains
unpaired. That is, the distances dks (Pr_ Pt.) and des( p P.f pairwise independent for different
domains e, E [m]. Equality (15) is trivial since des( Pe P.) 2 0. Finally, Inequality (16) follows
from Condition (i) and that the function g is monotonically decreasing in n. We also used the fact
that EE {e+]] = -E|-1
Pe were an empirical measure the classical sense, then Condition (i) in Theorem D.3 translates to the well-known Kineezky-Kieeer-ollfee inequality, that is, the function is given by g(n, x)

---

Algorithm 3 dénntfyyoinDDisrbbuiiiiEEippiiil
Hyperparameters: 7 0, a E 10.
2: Input: Matrix of observations X RRdexne for all [m].
3: Output: Number of shared latent variables L, matrix B and probability measure P.
4: for E [m]] do
5: Linear ICA: Use any linear ICA algorithm obtain mixing matrix B Rdxx5 where
S. Lrank,(X'' T) Compute the matrix oj = (Ba)txe X E RR where (B*)t the
Moore-Penrose pscudoinverse of B
6: Scaling: Let A be & x &. diagonal matrix with entries A
(77 The
J la. Define
B ( and 17 (A9)-1/21je
7: Let Pe the estimated probability measure with independent marginals such that Pe empirical measure of the row n....
8: end for
9: Matching: Let i be the maximal number such that there is signed permutation matrix Q in
each domain [m]] such that
Da (1(Q9) (%) T =1
for all i and all * where 0₁ a/t with Eees 865g. Let Let (1,...,
Construct the matrix B and the tuple of probability measures P given by
[(Q1) T [(Q|) (P'') 1
IBQQ)a
[B'Q'I lakE
B=
and P
1BmQ
1TT [mmQun B
[[Q@M)T TT " (3.
return B.
Algorithm IédniifsShacdGGrahEEniica
1: Hyperparameters: >> 0.
2: Input: Matrix B" V
3: Output: Parameter matrix À e Rexe
4: Remove rows B with || y from the matrix B²
5: Find tuples (iR,Jk)KE) with the smallest possible scores omin (Bi (ss ).2. such that
(i) i + ju for all k L and {is, ju n (ig.jng 0 for all k, q E L such that k + g and (ii) mmin (Bite
y for all k q such that k + q.
6: Let / - (ii,...,ii, } and consider the matrix B c E Bx
7: Find two permutation matrices R₁ and R2 such that W = B is as close as possible to lower triangular. This can be measured, for example, by using Exe, W
8: Multiply each column of W by the sign of its corresponding diagonal element. This yields new matrix W with all diagonal elements positive.
9: Divide each row of W by its corresponding diagonal element. This yields a new matrix W with all diagonal elements equal to one.
Compute À 1 (W'--1
return A.
11:
25

---

2 eexp(-2nx)) Given tuple C = (d1..... im) that defines a shared node, Condition (ii) is an assumption on the number of wrongly matched components. The most extreme case is when the shared node does not actually exist and all components are wrongly matched. That is, the measures pe and P.G matched even though dks(P?, Pi,) * 0 and d the other hand, Σ < m,, then determines a shared node where the majority of the components are correctly matched.
i,
-P.)) - # for all e, E [m]] On
If g(n, 2) + for n + DO and the constraint v "Pmax/Dmii - O. In this case, the probability that a given tuple C' with wrong components E' determines a shared node goes zero for large sample sizes min As noted, the probability of falsely discovering a shared node decreases exponentially with the number of wrongly matched components |E In the extreme case, this means that the probability of falsely discovering shared nodes with all components wrongly matched, i.e., E [m]] decreases exponentially with the number of domains m.
the statement of the theorem becomes meaningful under
Theorem D.3 also tells us that the probability of falsely matching two measures P and P becomes zero if the sample size grows infinity and the linear ICA algorithm consistent. However, with finite samples we might fail to match two measures where the underlying true measures are actually the same, ie.. falsely reject the true null hypothesis Ho. Thus, we might be overly conservative in detecting shared nodes due to high family-wise error rate caused by multiple testing. We suggest correct the level a account for the amount of tests carried out. One possibility is apply Bonferroni-tyy -ype correction. The total number of tests is given by t = 2 Eees S. This means that an adjusted level is given by o, ox/ and instead of the critical value ca we consider the adjusted critical value Co.'
Algorithm Biis the finite sample version of Algorithm [ with the matching Ω, defined in Definition D.I To determine the number of independent components for the linear ICA step in each domain, we need to check the rank(X* (X*) We specify the rank of matrix M as number of singular values which are larger than a certain threshold y and denote by rank, (M).
In Algorithm we also provide a finite sample version of Algorithm 2 where we only have the approximation 3* = Bg z B for signed permutation matrix V For matrix M, we denote by min (M) the smallest singular value.
E Error Distributions in Simulations
We specify C (1,2,3), (4, 12 {6,7) and 13 = (8,99) 9}. Note that the set la does not exist if the number of domains is m = 2. The error distributions in all simulations are specified as follows if not stated otherwise.
L: Beta 2, 3), (eta E3 Xi.
I 51 ~ Gumbel(( (0, 1), Es LogNormal 1),
T2: 66 ~ Weibull(1, 2), 6 Exp(0.1),
I3: SkewNormal Eg (1e))ormal(2)),
where the overline means that each distribution standardized to have mean and variance 1. Figure 6 shows histograms of the empirical distributions.
F Additional Simulation Results
In this section, we make additional experiments. First, we consider another setup where all our assumptions are satisfied but we have more domains and more shared latent variables. Then, we also consider two setups where some of our assumptions are not satisfied.
Different Setup. We make additional experiments on a similar scale as Section 5 but with more shared nodes and less domain specific nodes. This time, we consider & = 5 shared latent nodes and [Ta| = domain-specific latent node in each domain. Moreover, we also consider m domains. The dimensions are given by de d/m for all e [m]] and d 48. The graphs and edge weights
26

---

05
0.8
0.2
06
03
01
62
0.0
09
25
50
25
08
25
59
7.
20
04
0.5
04-
03-
02
0.4
02
02
02
01
0.
04
0.
00
08
Figure 6: Histograms showing the frequency of 25000 values sampled from the random variables E; with distribution as specified in Appendix [ first row shows the empirical distributions from 61 E5 and the second from En 8g.
Each distribution has mean zero and variance one. The
0.030
2 domains
2.5
2 domains
Average ot
Modian scorts
0.025
3 domains
Medlan score
2.0
- 3 domains
3
0.020
4 dumnainns
1.5
4 domains
2 domains
1.0
0.010
3 domains
domains
0.005
0.5
0.0
10* Sample
10
10"
Sample
Sample
(b)
Figure 7: Simulation results for = 5 shared latent nodes. Logarithmic scale on the z-axis. Error bars in (a) standard deviation of the mean and (b) and (c) they the interquartile range.
are sampled equivalently as Section i the main paper. We also consider the same distribution of the еттоr variables as specified in Appendix where we specify & = {1. 2, 3, 4, 5). 41 = {6}. To (7). I3 = (8} and 14 = (9).
Figure Figure[sshows the results where the scores are equivalent as the main paper. Once again, we see that the estimation error for the matrices Bę and Ac,c decreases with increasing sample size. This supports our proof of concept and shows that the adapted algorithms are consistent for recovering Bg and Ac.c from finite samples.
Violated Assumptions. We consider the same setup as in the main paper in Section with / shared latent nodes, but we fix the number of domains to = 3. In this experiment, compare the results where data was generated such that all our assumptions are satisfied with two setups where we violate some of the assumptions. In the first setup, we violate Condition (CT) requires pairwise different error distributions. We specify the error distributions as follows.
C: Beta(2, 3), Beta(2,
x2.
4:: 54 ~ Beta(2, 3), E5 LogNormal (0, 1).
Iz: Eg ~ Beta(2, 5). E7 ~ LogNormal(0, 1),
Iz: Eg ~ x2. Ey ~ LogNormal 1).
where, as before, the overline means that each distribution is standardized to have mean 0 and variance In the second setup, we do not change the error distributions but we violate Condition (C3) that requires two partial pure children per shared latent node. In this experiment, do not make any sparsity assumptions on the mixing matrix Gv.c-
Figure shows the results of our experiments. As expected, we see in (a) and (b) that identifyability of the joint distribution fails if we do not require pairwise different error distributions. Recovering the joint distribution still works well in the second setup where we violate the partial pure children
27

---

3.5
0.08
Assump sefoffoc
2.0
Aaxump sufafee
3.0
Modian scorcs
Medlan score
2.5
0.06
pare chilkeen
1.5
pare
2.0
1.5
0.04
1.0
1.0
Auscmip selslae
0.02
0.5
0.5
0.0
pune dhiccrnn
0.00
0.0
10
10
10
10"
10'
Sample
Sample size
Sample
(a)
Figure 8: Simulation results where assumptions are not satisfied. Logarithmic scale on the r-axis. Error bars (a) are one standard deviation of the mean and in (b) and (c) they are the interquartile range.
conditions. However, identifying the shared latent graph is impossible in this setup, explained in Appendix[C] This is supported by the experimental results displayed in Figure (c), where we can that recovery of the shared latent graph does not work when the partial pure children assumption is not satisfied.
G Future Work
We see many directions for future work, which include the following.
Our work and algorithms rely on linear ICA. It would be interesting study more direct approach to recover the joint distribution and the causal graph. This might potentially be done by testing certain constraints implied by the model similar as the developments in the LiNGAM literature; see e.g. Shimizu et al. (001T) and Wang and Drton (2020).
Our results require non- non- Gaussianity and that both the latent structural equation model and the mixing functions are linear. We consider the linear setup
basis for any subsequent study
of nonlinear cases. For example, recent advances in non-linear ICA allow identifiaiility of up to linear transformations, see e.g. [Khemakhem et al. (2020), [Bcchholz et al. (2022) and causal representation might then be obtained from identifiability results for the linear model.
Roeder et al. (202T). Identifiability
Our sufficient condition for identifiability of the shared latent graph requires two partial pure children per shared latent node. In this regard, it would also be interesting to study necessary conditions; c.f. our discussion in Appendix C
This work focused purely on the observational case. However, considering interventional data can be expected to permit relaxing some conditions in both of the key steps, i.e., recovering the joint distribution and the shared latent graph. For example, recent work shows that interventional data allow for identification of the latent graph without sparsity constraints in a single-domain setup (Squires et al., 2023 Ahhua et al. 2023). Extending this to the multi-domain setup an interesting problem for future work.
It would be interesting study the statistical properties of our setup such theoretical bounds on the accuracy of recovering the matrices B and Ag,c as well as developing algorithms that meet these bounds. Currently, our adapted algorithms for finite samples determine the rank of a matrix by using a threshold for singular values. The algorithms depend on the choice of this parameter and would be worth studying optimal choices. Moreover, one might consider different methods for determining the rank of matrix.
There might be different matching strategies the estimated error distributions in the finite sample setting. For example, instead of matching pairwise consistently across all domains as we propose in Appendix D one might find an optimal matching by solving a linear program.
28


Reviews:
[{"review_id": "1FOEBXoSLa", "reviewer": "Reviewer_aPgx", "summary": "This work tackles the problem of learning the latent causal structure from multiple unpaired domains. Under a linear non-Gaussian condition, this work presents the identifiability guarantees for the joint distribution over the domains and the causal structure within the shared latent partition. Synthetic data experiments are presented to validate the theory.", "questions": "I would like to learn about the authors' response to the weaknesses listed above, which may give me a clearer perspective on the paper's contribution.", "limitations": "Please see the weakness section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is well-motivated and timely. Unpaired data are prevalent in the wild, and this work provides a rigorous treatment as the initial step to leverage such data in a principled manner.\n2. The paper is nicely written, and the theoretical analysis is clearly articulated with sufficient explanations.\n3. The theoretical techniques are clearly explained. Connections and attributions to prior work are appropriately introduced, which aids the assessment of this paper’s technical contribution.", "weaknesses": "1. The linear assumptions: practical multi-domain (modal) data-generating processes are often highly nonlinear, e.g., images and text. The applicability of the linear assumption may not be as appealing.\n2. The heterogeneous noise distributions: pairwise distinct exogenous distributions appear a strong assumption to me and can potentially oversimplify the technical challenge. I would be interested in learning about the necessity of such an assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review of our work and their supportive comments on the motivation of the problem and the presentation of the paper. We hope that the following responses addresses their remaining questions.\n\n# Response to the weaknesses\n\n### Linearity \nWe agree that the linear setting is somewhat idealized to give the identifiability problem in an unpaired multi-domain setting a theoretical treatment. In this paper, we focus on understanding the problem in the linear case, which we consider the basis for any subsequent study of nonlinear cases. For example, recent advances in nonlinear ICA allow identifiability up to linear transformations, see e.g. [1] and [2]. Identifiability of a *causal* representation might then be obtained from identifiability results for the linear model. \n\nThis is supported by examples in recent work where identifiability in the linear case led to significant progress to obtain identifiability in more general models. For example, the authors of [3] consider identifiability under interventional data in a nonlinear setup. They show identifiability by first proving identifiability up to linear transformations and then applying an identifiability result for linear setups [4]. \n\nTo conclude, we consider it as a very interesting follow-up work to study a nonlinear multi-domain setting, where we can \"combine\" identifiability of nonlinear ICA with our result on linear identifiability in multi-domains. \n\n[1] Variational Autoencoders and Nonlinear ICA: A Unifying Framework \\\n[2] On Linear Identifiability of Learned Representations \\\n[3] Learning Linear Causal Representations from Interventions under General Nonlinear Mixing \\\n[4] Linear Causal Disentanglement via Interventions \n\n### Noise distribution assumption\nMany thanks for raising the question of the necessity of pairwise different error distributions. Our paper proposes a constructive way to recover the joint distribution in a multi-domain causal representation model (Definition 2.3) from the marginal distributions. As pointed out, this relies on the assumption of pairwise distinct error distributions. Inspired by the reviewer's comment, we discuss the necessity in detail in the following.\n\n**Recap of identifiability**\\\nIn general, given two potentially different multi-domain graphs $G_m$ ans $\\widetilde{G}_m$ and any representations $(B,P)$ and $(\\widetilde{B}, \\widetilde{P})$, identifiability of the joint distributions in multi-domain causal representation models means the following: \n\n$B_{V_e,H}$#$P=\\widetilde{B}_{V_e,H}$#$\\widetilde{P}$ for all $e \\in [m]$ $\\implies$ $B$#$P=\\widetilde{B}$#$\\widetilde{P}$, \n\nwhere $M$#$P$ denotes the push-forward measure under the linear map $M$. The left-hand side means that the marginal distributions in each domain are equal, while the right-hand side means that the joint distributions are equal. Note that the right-hand side holds if and only if there is a signed permutation matrix $\\Psi$ (not necessarily with block structure) such that $B=\\widetilde{B}\\Psi$ and $P = \\Psi^{\\top}$#$\\widetilde{P}$. This is implied by the identifiability of the usual, one-domain linear ICA.\n\nTheorem 3.1 shows that assumptions (C1) and (C2) imply identifiability of the joint distribution. In particular, we show that they imply identifiability in a stronger sense, namely, that it follows from the left-hand side that $B=\\widetilde{B}\\Psi$ and $P = \\Psi^{\\top}$#$\\widetilde{P}$ for a signed permutation *block* matrix $\\Psi \\in \\Pi$.  Identification of the representation $(B,P)$ up to the equivalence class of signed permutation *block* matrices implies identifiability of the joint distribution, and it also allows for identifying the shared causal graph in a second step. \n\nNow, it is possible to discuss the necessity of pairwise distinct error distributions in two contexts: Is the assumption necessary for identifiability of the representation $(B,P)$ up to signed permutation block matrices? Is it necessary for identifiability of the joint distribution?\n\n**Role of distributional assumptions**\\\nAssume that $P_i = P_j$ or $P_i = -P_j$. Then four cases are possible: \\\n(i) $i,j \\in \\mathcal{L}$ \\\n(ii) $i \\in \\mathcal{L}, j \\in I_e$ \\\n(iii) $i \\in I_e, j \\in I_f$ for $i \\neq j$ \\\n(iv) $i,j \\in I_e$ \n\nIn cases (i) - (iii), identification of the representation $(B,P)$ up to a signed permutation block matrix is not possible. Moreover, in these three cases, it is also impossible to identify the joint distribution at all. \n\nIn **cases (i)-(ii)**, this can be seen by construction matrices $B$ and $\\widetilde{B}$ that can not be transformed into each other by any signed permutation matrix (without block structure), which implies that $B$#$P \\neq \\widetilde{B}$#$\\widetilde{P}$, but the marginal distributions are equivalent. \n\nIn **case (iii)**, it can be seen by constructing a counterexample where two joint distributions are supported on different dimensional subspaces, but the marginal distributions are again equivalent. \n\n***To summarize, pairwise different error distributions are necessary in cases (i) - (iii) to identify the joint distribution.*** We are more than happy to extend Appendix C and include this discussion and the counterexamples in our camera-ready version. \n\nOn the other hand, **case (iv)** would still allow identification of the representation $(B,P)$ up to a signed permutation block matrix and, therefore, also identification of the joint distribution. For the sake of a simplified presentation, we were not stating this explicitly in the paper, even though it becomes clear by checking the proof of Theorem 3.1. We will add a remark in the main body of the camera-ready version to clarify."}, {"review_id": "gB2xo0PBVL", "reviewer": "Reviewer_B2Nu", "summary": "- The paper considers causal representation learning from unpaired multi-domain data, with latent variables both shared and specific to domains.\n- Its key contribution is a new identifiability result for linear causal models with non-Gaussian noise, linear mixing function, and a number of other assumptions.\n- In addition, the authors develop a practical representation learning algorithm for this setting and demonstrate it on toy data.\n\nI've read the authors' rebuttal. They have addressed my concerns adequately.", "questions": "- See above.\n- Very minor suggestion: there are a few instances of `\\citet{}` that should be a `\\citep{}`. It speaks for the quality of the writing that I can't think of any other comments here.", "limitations": "- The paper is very clear about the (many) assumptions in the theory. It also openly acknowledges the limitations of the experiments.\n- I do not see any particular need for an extensive discussion of societal impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Causal representation learning is an interesting, relevant, and mostly unsolved problem.\n- The setting considered here (observational unpaired multi-domain data) is practical and well-motivated from single-cell biology applications.\n- The identifiability result is, to the best of my knowledge, novel, and substantially different from existing results.\n- As far as I can tell, it is also correct, though due to review overload I have not been able to check the proofs properly.\n- The paper is extraordinarily well-written. The authors manage to be precise, yet still provide intuitive explanations.", "weaknesses": "- The contribution made here has only one real weakness, and that is the host of strong assumptions underlying the identifiability result: 1D causal variables, linear causal model, no causal effects from shared to domain-specific latents, non-symmetric error distributions, different error distributions for each variable, linear mixing function, full-rank mixing function, observed variables include sufficient \"partially pure children\", and the list goes on. To put it bluntly, this list makes me wonder if this identifiability result present progress on the road to algorithms that work in practice on interesting real-world datasets.\n    - Of course, strong statements such as CRL identifiability require strong inputs, but these need not be in the form of model assumptions, they could also come from the data side. Perhaps it is a bit out of scope for this paper, but I would be curious if the availability of *interventional* data or some other form of auxiliary data would allow the relaxation of some of these model assumptions.\n    - While the authors do a good job in providing an intuition for why these assumptions are needed, I would like to know if there are any real-world problems that satisfy them all. This is partially discussed for single-cell data and a few of these assumptions, but could the authors provide a more complete example that ideally satisfies all assumptions?\n- There are no experiments to speak of, though I also don't think that all papers need experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments regarding the quality of our writing, the importance of the studied causal representation learning problem, and the novelty of our result. We hope that the following responses addresses their remaining questions.\n\n# Response to weaknesses\n\n*The contribution made here has only one real weakness, and that is the host of strong assumptions underlying the identifiability result: 1D causal variables, linear causal model, no causal effects from shared to domain-specific latents, non-symmetric error distributions, different error distributions for each variable, linear mixing function, full-rank mixing function, observed variables include sufficient \"partially pure children\", and the list goes on. To put it bluntly, this list makes me wonder if this identifiability result present progress on the road to algorithms that work in practice on interesting real-world datasets.*\n\nWe agree with the reviewer that the linear setting is idealized to give the identifiability problem in an unpaired multi-domain setting a theoretical treatment. However, as we discuss in the response to reviewer aPgx, identifiability in linear setups is often the basis for progress on identifiability results in more general, nonlinear setups. Moreover, the reviewer is correct that we make certain assumptions to obtain the identifiability result. But we want to emphasize that we also strongly focus on discussing their necessity, that is, whether or not they are the weakest assumptions possible. In Appendix C, we discuss the need for non-Gaussianity and sparsity on the mixing matrices. In addition, we again refer to the response to reviewer aPgx for a detailed discussion on the necessity of non-symmetric, pairwise different error distributions.\n\n*Of course, strong statements such as CRL identifiability require strong inputs, but these need not be in the form of model assumptions, they could also come from the data side. Perhaps it is a bit out of scope for this paper, but I would be curious if the availability of interventional data or some other form of auxiliary data would allow the relaxation of some of these model assumptions.*\n\nThis is a very interesting point. In this work, we intended to focus purely on the observational case. But for future work, considering interventional data would definitely allow relaxing some conditions in both, recovering the joint distribution and the shared latent graph. Intervention on latent nodes only has an effect on observed domains that are children of that latent node. Thus, we suspect that interventional data allows to identify the shared latent variables and recover the joint distribution. This would imply a relaxation of the distributional assumptions on the errors. Interventional data also allows identification of the shared latent graph without sparsity constraints, as proven in several recent papers on single-domain data (e.g. [1], [2]). Extending this to the multi-domain setup is an interesting problem for future work, and we believe it would allow us to drop the sparsity constraints.\n\n[1] Linear Causal Disentanglement via Interventions\n[2] Interventional Causal Representation Learning\n\n*While the authors do a good job in providing an intuition for why these assumptions are needed, I would like to know if there are any real-world problems that satisfy them all. This is partially discussed for single-cell data and a few of these assumptions, but could the authors provide a more complete example that ideally satisfies all assumptions?*\n\nWe thank the reviewer for raising this question. First of all, finding sufficient and necessary conditions for identifiability in causal representation learning is an important problem in itself. Understanding such conditions allows reasoning about whether or not a given data set satisfies these conditions and if causal representation learning is feasible. \n\nWhile provably certifying assumptions such as the distribution of latent variables and sparsity is challenging, for the data sets motivating our work, i.e., multi-domain data from single-cell biology, it is reasonable to believe that the assumptions are satisfied. This is argued in Remark 4.6, where we also cite a data set. In the remark, we do not discuss the conditions needed for identifiability of the joint distributions. However, assuming that the distributions of the latent variables are pairwise different and non-symmetric, which is for example satisfied almost certainly by randomly chosen probability distributions on the real line and can thus be considered a weak assumption, would be sufficient.\n\n# Questions\n\n*Very minor suggestion: there are a few instances of \\citet{} that should be a \\citep{}. It speaks for the quality of the writing that I can't think of any other comments here.*\n\nMany thanks for pointing this out; we will change it accordingly."}, {"review_id": "S4Zkpw1mep", "reviewer": "Reviewer_ny5v", "summary": "In this paper, the authors address unpaired multi-domain causal representation. In detail, the authors learn the representations of the observed data from different domains that consist of causally. To achieve this, the authors consider the data generation process where the relationship between the latent variables is linear. Based on this generation process, they prove that the joint distribution of observed data and the shared causal structures of latent variables are identifiable.", "questions": "Please refer weaknesses", "limitations": "Please refer weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors investigate the causal discovery with latent variables from different domains.", "weaknesses": "1.\tThere are several works about causal discovery with latent variables under linear and multi-domain case like [1], which also considers the shared causal structure among latent variables and provide identification guarantees. It is suggested that the authors should discuss these works.  \n2.\tMoreover, the authors discuss several works about domain translation between unpaired data and claim that none of these works have rigorous identifiability guarantees. However, Multi-domain image generation, image translation, and domain adaptation belong to the proposed setting, and [2][3] have addressed the multi-domain causal representation learning problem recently. And the authors do not consider these works. It is noted that [2][3] considers the multi-domain causal representation learning with nonlinear transformation, which seems to be more general than the proposed setting.  \n3.\tAs for the identification of joint distributions, it is not clear why the identification of $l, B$, and $P$ can identify the joint distributions of observed data from multi-domains.   \n4.\tIn section 3, the authors assume that the distribution of errors is non-Gaussian for the identification of linear ICA by not allowing asymmetric distribution. But some distribution like the Laplace distribution is symmetric and they can also satisfy the identification of linear ICA.\n5.\tAccording to this paper, the authors consider the structure of latent variables to be linear but flexible. In the simulation experiment, the authors only consider three shared latent variables, it is suggested that the authors should consider more latent variables and different structures.  \n6.\tBesides, it is suggested that the authors should consider more compared methods and employ other metrics like recall, and precisions to evaluate the performance of causal discovery.  \n\n[1] Causal Discovery with Multi-Domain LiNGAM for Latent Factors  \n[2] Multi-domain image generation and translation with identifiability guarantees  \n[3] partial disentanglement for domain adaptation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review, which raises several helpful points. We hope that our response addresses their remaining concerns.\n\n# Response to weaknesses\n\n**1.)** We thank the reviewer for pointing out reference [1], which is indeed related to our work, and we will gladly add and discuss this additional reference. In short, the authors of [1] also assume a linear data-generating process on multiple-domains $X=(X_1, \\ldots, X_m)$, where\n\n$X = GZ$ and $Z=AZ+\\varepsilon$,\n\nbut there are important differences. First, $G$ and $A$ are assumed to have block-diagonal structure. Additionally, the authors assume that $Z=H\\widetilde{Z}$ for $H \\in \\mathbb{R}^{|\\mathcal{H}|} \\times \\tilde{q}$ such that $H$ only has one non-zero entry in each row. This allows to rewrite the data-generating process as\n\n$X = GH\\widetilde{Z}=\\widetilde{G}\\widetilde{Z}$ and $\\widetilde{Z} = H^{\\dagger}AH\\widetilde{Z} + H^{\\dagger}\\varepsilon = \\widetilde{B} \\widetilde{Z} + \\widetilde{\\varepsilon},$\n\nwhere $H^{\\dagger}$ denotes the pseudo-inverse. \n\nThe authors are then able to prove that  $\\widetilde{B}$ and $G$ can be identified. However, this is different from the goal we pursue here. Indeed, the authors do not claim that the matrix $H$ would be identifiable in their Theorem 2. To our understanding, $\\widetilde{B}$ has a different interpretation for every possible $H$ in terms of learning the causal relations among the latent variables in $Z$. This said, the authors do consider a setting in Theorem 3, where the number of variables increases ($p \\to \\infty$), and consistent estimation of $H$ is possible. However, this differs from our setting, where we consider a general but fixed number of observed variables.\n\nAt a more technical level, the conditions in [1]  require two pure children, while we prove identifiability under the weaker assumption of two partial pure children.  \n\nAs noted, we will gladly add [1] to our references and discuss it.\n\n**2.)** Thanks for pointing out the related work on identifiability of the joint distribution. We agree that we should be more careful about our claims on identifiability in prior works and are happy to include the references. However, even though the related work gives identifiability guarantees of the joint distribution in a non-linear setup, it does not tackle identifiability of a *causal* representation. \n\n**3.)** This is clarified in the paragraph after Theorem 3.1: Since we recover $\\widehat{B}=B \\Psi$ and $\\widehat{P} = \\Psi^{\\top}$#$P$, we have that \n\n$\\widehat{B}$#$\\widehat{P}$ = $B \\Psi$#($\\Psi^{\\top}$#$P$) =  $B \\Psi \\Psi^{\\top}$#$P$ = $B$#$P$,\n\nwhere $M$#$P$ denotes the push-forward measure under the linear map $M$. Now, by Definition 2.3, the joint distribution $P_X$ is equal to the push-forward distribution $B$#$P$, which shows that the identification of $B$ and $P$ up to signed permutation block matrices $\\Psi \\in \\Pi$ allows for identifiability of the (observed) joint distribution $P_X$.\n\n**4.)** The reviewer is correct that we assume non-symmetric error distributions. This is a stronger assumption than non-Gaussianity, and it indeed excludes Laplace distributions. However, this assumption is necessary for identifiability of the joint distribution, as we explain in detail in our response to reviewer aPgx; also see our response to AWor. \n\n**5.)** We would like to clarify that we already have additional simulations in Appendix F, where we consider a completely different structure with five shared latent variables and fewer domain-specific nodes.\n\n**6.)** Like the reviewer, we believe that it would be nice to compare our methods to prior work. However, previous methods that work on single domains are not applicable: One might be tempted to apply them in each domain separately. However, it would be unclear how to combine the multiple latent causal graphs we get since it is unclear how to determine which variables are shared. Another idea would be to first identify the joint distribution (as we do in Section 3) and then apply the existing algorithms to the joint distribution. The single-domain methods are expected to perform poorly in this setting since they require the classical notion of pure children, whereas we require only \"partial\" pure children. On the other hand, the algorithm in the proposed reference [1] should be applicable. However, the identifiability results in [1] also require two pure children, which is why we expect it to perform poorly in the considered setups for our simulations. If code is readily available, we will demonstrate this behavior in additional simulations in the Appendix in our camera-ready version. \n\nIn our plots, we decided to compare the recovered parameter matrices itself with the correct parameter matrices. If the difference is zero, this, in particular, means that the support of the recovered graph is correctly recovered. On the other hand, recall, precision or f1-score only evaluate the graphical structure. However, we agree with the reviewer that they might give additional insight, and we can easily add these metrics."}, {"review_id": "M88p3uPD1w", "reviewer": "Reviewer_AWor", "summary": "The authors study the setting of unsupervised learning where observations belong to several domains, and we only observe the marginal distribution of each domain. A set of latent variables generates the observations, where a subset of latents are shared across domains. The authors provide the first identification results in this setting, assuming that the latents follow a linear SCM, and the observations are an injective linear transformation of the latents. With this model, identifying the (unobserved) joint distribution of the observations equates to identifying the latents. The mapping between the exogenous noises and the observations, as well as the distributions over the exogenous noises, are identified up to signed block permutation. With additional conditions, the authors also identify the causal graph for the latents up to a signed permutation consistent with the topological ordering of the latents. The authors validate their claims with a synthetic data experiment.", "questions": "This paper makes two contributions. The first is to extend identifiable single-domain linear ICA to the multi-domain setting. The second is to extend single-domain graph identifiability to the multi-domain setting. In both cases, can you intuitively describe what about the multi-domain setting prevents the existing results from holding automatically?\n\nFor example, if there are no shared latents, the joint can be identified by trivially applying linear ICA separately to each domain. What is the difficulty imposed by a subset of latents being shared, and how is this circumvented?", "limitations": "The authors made it explicit that this work is primarily about identifiability, and less about scalable algorithms and evaluation on realistic datasets.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a strong paper that provides the first identifiability results on multiple-domain unsupervised learning where the joint distribution of the observed variables is unobserved. These results are impactful, since this problem setup is well-studied and has practical applications in single-cell biology. Existing approaches are significantly limited by their lack of identifiability, so this paper makes a valuable contribution.\n\nThe writing style is rigorous, and definitions, assumptions, and results are explained precisely.", "weaknesses": "This paper could be improved with more context on how they are extending existing identification results to achieve theirs. Currently, the authors mention which existing results are being used, but do not provide an intuitive description on why they need to be extended, and how they do so.\n\nThe notation could be improved. Capital letters are used to denote matrices, probability measures, vector- and scalar-valued random variables, sets of nodes, and sets of edges. It would improve readability if you used font styles (e.g. lower-case bold for vectors) to differentiate them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the supportive review and helpful comments.\n\n*This paper makes two contributions. The first is to extend identifiable single-domain linear ICA to the multi-domain setting. The second is to extend single-domain graph identifiability to the multi-domain setting. In both cases, can you intuitively describe what about the multi-domain setting prevents the existing results from holding automatically?* \\\n*For example, if there are no shared latents, the joint can be identified by trivially applying linear ICA separately to each domain. What is the difficulty imposed by a subset of latents being shared, and how is this circumvented?*\n\nMany thanks for raising this question. As you correctly mention, we extend the identifiability of linear ICA in one domain to obtain identifiability of the joint distribution. Moreover, it is true that the joint can be identified by trivially applying linear ICA separately to each domain when there are no shared latents. This corresponds to the case where the observations of different domains are independent. However, if they are dependent, then the shared latent variables determine the dependency structure of the domains. Thus, it is crucial to determine which of the latent variables are shared and which ones are domain-specific. Assuming non-symmetric, pairwise different error distributions is a sufficient condition to \"match\" and identify shared distributions. As we discuss in detail in our response to aPgx, this condition is also necessary.\n\nApplying recent results on single-domain latent graph identifiability yields a similar challenge: We recover a latent graph in each domain, but how to integrate them? That is, how to determine which latent factors are shared across domains since they represent conceptually the same? We circumvent this problem by first recovering the joint distribution by extending linear ICA (as described above) and then recover the shared graph from the recovered *large mixing matrix* $\\widehat{B}$. Our conditions on sparsity, i.e., two partial pure children, are inspired by the results on single-domain graph identifiability that require pure children. However, we are able to relax the conditions since we use a different proof technique tailored to our setup, i.e., we exploit rank constraints in the *large mixing matrix* that we already identified. This allows us to show that two *partial* pure children *across* domains are sufficient, i.e., a total of 2 across *all* domains. In contrast, single-domain results would require 2 pure children in *every* domain, in addition to the fact that integrating each domain's different graph remains challenging. \n\nIn the camera-ready version, we are happy to add this intuition in the introduction in the paragraph where we talk about proof techniques.\n\n*The notation could be improved. Capital letters are used to denote matrices, probability measures, vector- and scalar-valued random variables, sets of nodes, and sets of edges. It would improve readability if you used font styles (e.g. lower-case bold for vectors) to differentiate them.*\n\nThank you for suggesting a better notation. This is helpful feedback, and we will make the suggested changes in the camera-ready version."}]

Author rebuttal:

Meta-review: This research addresses the challenge of discerning the latent causal relationships across multiple unrelated domains. In the context of a linear non-Gaussian scenario, this study provides assurances regarding the identifiability of the joint distribution spanning the domains and the causal structure within the common latent segment. To substantiate these theoretical findings, the paper includes synthetic data experiments.

The paper addresses a timely and well-motivated problem concerning the utilization of unpaired data, which is abundant in real-world scenarios. It offers a rigorous approach to leveraging such data in a principled manner, making it an important initial step. Hopefully more general results in the nonlinear setting can arise in the near future. All reviewers unanimously recommend acceptance of this work. The paper is well-written, and its theoretical analysis is presented clearly and with ample explanations. The explanations of the theoretical techniques are also well-detailed. I thus recommend acceptance of this paper.
Decision: Accept (spotlight)