Federated Causal Discovery from Heterogeneous Data
Authors: Loka Li
Ignavier Ng
Gongxu Luo
Biwei Huang
Guangyi Chen
Tongliang Liu
Bin Gu
Kun Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Causal Discovery
Structure Learning
Federated Learning
Heterogeneous Data
Primary area: causal reasoning
TL;DR: In this paper, we propose a novel federated causal discovery method attempting to accommodate arbitrary causal models and heterogeneous data.

Abstract: Conventional causal discovery methods rely on centralized data, which is inconsistent with the decentralized nature of data in many real-world situations. This discrepancy has motivated the development of federated causal discovery (FCD) approaches. However, existing FCD methods may be limited by their potentially restrictive assumptions of identifiable functional causal models or homogeneous data distributions, narrowing their applicability in diverse scenarios. In this paper, we propose a novel FCD method attempting to accommodate arbitrary causal models and heterogeneous data. We first utilize a surrogate variable corresponding to the client index to account for the data heterogeneity across different clients. We then develop a federated conditional independence test (FCIT) for causal skeleton discovery and establish a federated independent change principle (FICP) to determine causal directions. These approaches involve constructing summary statistics as a proxy of the raw data to protect data privacy. Owing to the nonparametric properties, FCIT and FICP make no assumption about particular functional forms, thereby facilitating the handling of arbitrary causal models. We conduct extensive experiments on synthetic and real datasets to show the efficacy of our method. The code is available at https://github.com/lokali/FedCDH.git.

Published as a conference paper at ICLR 2024
FEDERATED CAUSAL DISCOVERY FROM HETEROGE- NEOUS DATA
Loka Li', Ignavier Ng', Gongxu Luo', Biwei Huang", Guangyi Chen' 12, Tongliang Liu', Bin Gu', Kun Zhang 1.2
Mohamed bin Zayed University of Artificial Intelligence
2 Cameegie Mellon University
3 University of California San Diego
[Longkang.li, kun. zhang @mbzuai ac.
ABSTRACT
Conventional causal discovery methods rely on centralized data, which is incon- sistent with the decentralized nature of data many real-world situations. This discrepancy has motivated the development of federated causal discovery (FCD) approaches. However, existing FCD methods may be limited by their potentially restrictive assumptions of identifiable functional causal models or homogeneous data distributions, narrowing their applicability in diverse scenarios. this pa- per, propose novel FCD method attempting accommodate arbitrary causal models and heterogeneous data. We first utilize a surrogate variable corresponding the client index account for the data heterogeneity across different clients. We then develop a federated conditional independence test (FCIT) for causal skeleton discovery and establish federated independent change principle (FICP) deter- mine causal directions, These approaches involve constructing summary statistics proxy of the raw data to protect data privacy. Owing to the nonparametric properties, FCIT and FICP make no assumption about particular functional forms, thereby facilitating the handling of arbitrary causal models. We conduct extensive experiments on synthetic and real datasets to show the efficacy of our method. The code is available at https: : / /tg/ttttuu thub. com lokal /FedCDF. git
INTRODUCTION
Causal discovery aims to learn the causal structure from observational data, attracting significant attention from fields such as machine learning and artificial intelligence (Nogueira al.) [202T). healthcare (Shen et al. 2020), economics (Zhang & Chan 2006), manufacturing (Vukovvć & Thal- mann 2022 and neuroscience (Tu et al., 2019). Recently, it has been facing new opportunities and challenges from the rapid growth of data volume. One of the key challenges is data decentralization. Traditionally, causal discovery is conducted at a centralized site where all data is gathered in one location. However, in real-world scenarios, data is often distributed across multiple parties, such as the healthcare data across various hospitals (Kidd et al., (022). Consequently. there has been in- creasing interest in federated causal discovery (FCD), which aims uncover the underlying causal structure of decentralized data with privacy and security concerns.
Existing FCD methods from observational data can be generally classified continuous- optimization-based, constraint-based, and score-based methods. Some continuous-optinizaaiii based methods extend NOTEARS (Zheng et 2018) with federated strategies, such NOTEARS- ADMM (Ng & Zhang 2022) that relies on the ADMM (Boyd et al. (001]) optimization method, FedDAG (Gao et al.] 2002) that employs FedAvg (McMahan 2017) technique, and FED-CD (Abyaneh et al., (022)) that utilizes belief aggregation. These methods might suffer from various technical issues, including convergence (Wei et al.) 2020 Ng et al. 2022), nonconvexity (Ng et al.) 2023), and sensitivity to data standardization (Reisach et al. 2021). As for score-based methods, DARLIS (Ye et al.) 2022) utilizes the distributed annealing (Arshad Silaghi 2004) strategy to search for the optimal graph, while PERI (Mian et al. 2023) aggregates the results of the local greedy equivalent search (GES) (Chickering 2002) and chooses the worst-case regret for each itera- tion. One constraint- based method, FEDC SL. (Wang al. 2023), extendes x² test to the federated

---

Published as a conference paper at ICLR 2024
Table 1: The comparison of related works about federated causal discovery from observational data.
Our FedCDH method could handle arbitrary functional causal models and heterogeneous data.
Method
Categury
Distriburion
Data
Causal Model
Ascumption
Identifiabiliy Requirement
Federated
Strategy
NOTEARS-DDMM ADMM Ng & Zhone 2002
Optimicttion based
Tomogenneus
Linear Caussian. EV
Yes
ADMM
NOTEARS-ML MLLA PAUDME INg
20122
Optinizaricu-al hased
Homogennoes
Nonlincar Additive Noss
Yes
ADMM
FedDAG et al [022
Optinizatien-nass
Hoterogenoous
Nonlincur Addliive Noise
Yes
FedAvg
Fed-CD
2323
Optinizatico-hasa
Hetzragenzous
Nonlinear Addiive Noise
Yes
Belief Aggregation
DARLIST 1c20
Score
Homogeneeus
Generalized Linear
Distributed Anmealing
PEXI Mian oa
Score based
Homogenexus
Gunssaan,
Voting
FedPC- (inangg
Constnint-husal
Homogenoous
Linea Guussian, NV
Na
Vating
Constrimm-busod
Hetzrogenoous
Athitrary Fasciions
No
Summtrry Statisties
version, however, this method is restrictive on discrete variables and therefore not applicable for any continuous variables. Other constraint-based methods, such as FedPC (Huang et al. 2022) aggregate the skeletons and directions of the Peter-Clark (PC) algorithm (Spirtes et al. (2000) by each client via voting mechanism. However, as shown in Table II most of these methods heav- ily rely on either identifiable functional causal models or homogeneous data distributions. These assumptions may be overly restrictive and difficult to be satisfied in real-world scenarios, limiting their diverse applicability. For instance, distribution shifts may often occur in the real world across different clients owing different interventions, collection conditions, or domains, resulting in the presence of heterogeneous data. Please refer to Appendix A2 for further discussion of related works, including those of causal discovery, heterogeneous data and FCD.
In this paper. we propose FedCDH, novel constraint Discovery from Heterogeneous data. The primary innovation of FedCDH lies in using summary statistics as a proxy for raw data during skeleton discovery and direction determination in fed- crated fashion. Specifically, to address heterogeneous data, we first introduce surrogate variable corresponding to the client or domain index, allowing our method to model distribution changes. Unlike existing FCD methods that only leverage the data from different clients to increase the total sample size, we demonstrate how such data heterogeneity across different clients benefits the identi- fication of causal directions and how to exploit it. Furthermore, we propose a federated conditional independence test (FCIT) for causal skeleton discovery, incorporating random features (Rahimi & Recht 2007) to approximate the kernel matrix which facilitates the construction of the covariance matrix. Additionally, we develop a federated independent change principle (FICP) to determine causal directions, exploiting the causal asymmetry. FICP also employs random features to approx- imate the embeddings of heterogeneous conditional distributions for representing changing causal models. It is important to note that FCIT and FICP are non-parametric, making no assumption about specific functional forms, thus facilitating the handling of arbitrary causal models. To evalu- ate our method, we conduct extensive experiments on synthetic datasets including linear Gaussian models and general functional models, and real-world dataset including fMRI Hippocampus (Pol-) drack et al. 2015) and HK Stock Market datasets (Huang et al. 2020).. The significant performance improvements over other FCD methods demonstrate the superiority of our approach.
approach for Federated Causal
2 REVISITING CAUSAL DISCOVERY FROM HETEROGENEOUS DATA
In this section, we will firstly provide an overview of causal discovery and some common assump- tions, then we will introduce the characterizations of conditional independence and independent change. This paper aims at extending those techniques from the centralized to the federated setting.
1) Causal Discovery with Changing Causal Models.
Consider d observable random variables denoted by V=(V1,..., Va) and K clients, and one client corresponds to one unique domain. In this paper, we focus on voriizonaally-patiiioon & Miril 2009), where each client holds a different subset of the total data samples while all the clients share the same set of features. Let & be the client index, and Ö be the domain index, Each client has ng samples, in total there are n samples, denoted by
data (Samet
where k, UE(1...,,K) K}.
LLinarr Gaussian model with equal noise variance (EV) (Peters & Bühlmann 2014) and nonlinear additive noise model (Hoyer et al. 2008) are identifiable, while linear Gaussian model with non-equal noise variance (NV) is not identifiable. Generalized linear model and arbitrary functional model are certainly not identifiable.
2

---

Published as a conference paper at ICLR 2024
n= -==== mg. The task of federated causal discovery is to recover the causal graph g given the decentralized data matrix VeRuxd.
When the data is homogeneous, the causal process for each variable V; can be represented by the following structural causal model (SCM): VI= where fa is the causal function, PA, is the parents of Vi, G is a noise term with non-zero variance, and we assume the e, 's are mutually in- dependent. When the data is heterogeneous, there must be some causal models changing across dif- ferent domains. The changes may be caused by the variation of causal strengths or noise variances. Therefore, we formulate the causal process for heterogeneous data as: fF=f(PA,, es, 0, (,)),, eb()), where Ü regarded as an observed random variable referred the domain index, the function fa or the distribution of the noise E is different or changing across different domains, both ((5) and (25) are unobserved domain-changing factors represented as the functions of variable Ü, (US) is the set of "pseudo confounders" that influence the whole set of variables and we assume there are L such confounders (25( (()) the minimum value for L can be 0 meaning that there is no such latent confounder in the graph, while the maximum value can be C3 = d(d+1) meaning that each pair of observed variables has hidden confounder), (,5) denotes the effective parameters of Vi in the model, and we assume that (?() is specific to Vi and is independent of 0,(35) for any izj. (3)) and (3() input U which is positive integer and output a real number. Let Gobe be the underlying causal graph over V, and Gang be the augmented graph over VUL ()))) [=1 For causal discovery with changing causal models, we follow previous work such as CD-NOD (Huang al. 2020) and make the following assumptions.
Assumption (Pseudo Causal Sufficiency). There is no confounder the dataset of one domain, but we allow the changes of different causal modules across different domains to be dependent.
Assumption (Markov and Faithfulness). The joint distribution over V U (T) (0)( is Markov and faithful to Gang-
To remove the potential influence from confounders and recover causal relations across different do- mains, causal discovery could be conducted on the augmented graph Gaug instead of Gobs- While (CS)U (2S)) == are unobserved variables, the do- main index U is observed variable. Therefore, U5 is introduced as the surrogate variable (Huang et al.) 2020) for causal discovery from heterogeneous data. An illustration given in Figure where the aug- mented graph with the unobserved domain-changing variables (25) and 0, (7) could be simplified by an augmented graph with just a surrogate variable Ü. If there is an edge between surrogate variable Ü and observed variable V; on Gaug. then it means that the causal model related to V; is changing across differ- ent domains, in other words, the data distribution of V, is heterogeneous across domains.
U
U
e
(a)
(b)
Figure 1: An illustration where the causal mod- of variables and Vj are changing across mains. (a) the graph with unobserved domain- changing factors (15) (3() and (7()) (b) the simplified graph with the surrogate variable U5
2) Characterization of Conditional Independence. Let X, Y, Z be random variables or sets of random variables, with the domains X', y, Z,, respectively. Define a measurable and positive definite kernel kx, and denote the corresponding reproducing kernel Hilbert space (RKHS) H.x Similarly, we define ky, Hy, lig and Hz. One of the most used characterizations of conditional independence (CI) is: X IL Y|Z if and only if P P = IP x PxizPyiz, or equivalently IP Fx = Pxxiz. Another characterization of CI is given in terms of the partial cross-covariance operator on RKHS.
Lemma (Characterization of CI with Partial Cross-covariance (Fukumizu al. 2007)). Let X A (X, kx e kxkg, and H be the RKHS corresponding to kg. Assume that H.x C L2x Hy C L2, Hz C 13z. Further assume that kky is a characteristic kernel on (X x 2) x V, and that Hz + R (the direct sum of two RHKSs) is dense (P2)).). Let Ex be the partial cross- covariance operator, then
EgyIz =0 = X V
3

---

Published as a conference paper at ICLR 2024
Based on the above lemma, further consider different characterization of CI which enforces the uncorrelatedness of functions in suitable spaces, which may be intuitively more appealing. More details about the interpretation of Σ 1z the definition of characteristic kemnll, and the uncorrelatedness-baseee characterization of CI, are put in Appendix A3.1
3) Characterization of Independent Change. The Hilbert-Schmidt Independence Criterion (HSIC) (Gretton et al., 2007) is a statistical measure used assess the independence between two random variables in the RKHS. We use the normalized HSIC to evaluate the independence of two changing causal models. The value of the normalized HSIC ranges from
and smaller value indicates that the two changing causal models are more independent. Let Â x be the normal- ized HSIC between P(X) and P(Y and 4 be the normalized HSIC between IPYY) and P(X Then, can determine the causal direction between X and Y with the following lemma.
Lemma 2 (Independent Change Principle (Huang et al., 2020 Let X and Y be two random observed variables. Assume that both X and Y have changing causal models (both of them are adjacent to U in Gaug). Then the causal direction between X and Y can be determined according to the following rules
i) If x < Av-x. output the direction X X-Y,
i) 1f 1 > DY-x- oulpul the direction Y
More details about the definition and formulation of Å x and Å x are in Appendix A3.2 It important to note that: once the Gaussian kernel is utilized, the kernel-based conditional inde- pendence test (Zhang et al. 2012) and the kernel-based independent change principal (Huang al. 2020) assume smoothness for the relationship of continuous variables.
3 FEDERATED CAUSAL DISCOVERY FROM HETEROGENEOUS DATA
In this section, we will explain our proposed FedCDH method in details. An overall framework of FedCDH is given in Figure? 2 Two key submodules of our method are federated conditional inde- pendent test (FCTT; Theorem and Theorem
5) and federated independent change principle (FICP; Theorem (6). which are presented Section 3. I and Section 3.2 respectively. We then illustrate how to construct the summary statistics and how implement FCIT and FICP with summary statis- ties (Thcorem [ in Section 3.3 Last but not least, we discuss the communication costs and secure computations in Section 3.4 For the proofs of theorems and lemmas, please refer to Appendix A4
3.1 FEDERATED CONDITIONAL INDEPENDENT TEST (FCIT)
1) Null Hypothesis. Consider the null and alternative hypotheses
Ho: IL Y Hi : X V Y
According to Eq. we can measure conditional independence based on the RKHSs. Therefore, we equivalently rewrite the above hypothesis more explicitly
Ho | X z llis = 0, Hi E
E Hs > 0.
33)
Note that the computation forms of Hilhert-Schmidt norm and Frobenius difference is that the Hilbert-Schmiin norm is defined in infinite Hilbert space while the Frobenius norm defined in finite Euclidean space. We here consider the squared Frobenius norm of the empirical partial cross-covariance matrix as an approximation for the hypotheses, given as
the same, and the
Ho : ||Cxriz = O, Hi :ICxvizzll 0,
(4)
where Cxviz= C( matrix with n samples, E2rizERAxh, Á=f(()ERmxk B=g(Y)ERRxh,, lo (eF and h denote the number of total samples of all clients and the number
corresponds to the partial cross-covariance
4

---

Published as a conference paper at ICLR 2024
Total Sample Size Global Covariance Tensor
Federated Conditional Independence (FOT)
Federated Independent Change Principle (FCCP)
Server
Sample Local
Sample Covariance Tensor
Sample Local Covariance Tensor
Siedessn Deconery Step
Suleman Disowary Stop 2
Biretion Deterniaation Step1
Ciruction Deternination Stp
Covariance Tensor
e
Ground-trun Gagh
Local
Local
Client
Client 2
Client K
Figure 2: Overall framework of FedCDH. Left: The clients will send their sample sizes and local covariance tensors to the server, for constructing the summary statistics. The federated causal dis- covery will be implemented on the server. Right Top: Relying on the summary statistics, we propose two submodules: federated conditional independence test and federated independent change prin- ciple, for skeleton discovery and direction determination. Right Bottom: An example of FCD with three observed variables is illustrated, where the causal modules related to V/2 and V/3 are changing.
of hidden features or mapping functions, respectively. Since X Z), then for each function f the input is X and the output f ("))ER". For each function g y the input is YER" and the output g² (Y))"".. Notice that Fx and Fy are function spaces, which are set to be the support of the process v2 cos( u +b). w follows standard Gaussian distribution, and b follows uniform distribution from [0, 2T.. We choose these specific spaces because this paper we use random features to approximate the kernels. [(Å Z) and E(B|2 Z) could be non-linear func- tions of Z which are difficult to estimate. Therefore, we would like to approximate them with linear Fz shares similar function space with Fy. We could estimate (2) with the linear ridge regression solution uz ((Z) and estimate E(g" (Z) with off (2) under mild conditions (Sutherland & Schneider 2015). Now we give the following lemma.
functions. Let q( ((Z)ER {q' (Z)
Lemma 3 (Characterization of Conditional Independence). Let I and g be the functions defined for the variables X and Y, respectively. Then X 11 Z is approximated by the following condition
B(Jg) 0, vs Fxiz and Vğ Friz,
where F (f x and Friz= g'=="" (Z), g'EFr).
Let 7 be a small ridge parameter. According to Eq. T and Eq. 5 by ridge regression, we obtain
Cxviz= = =Cx - CCz + 7) CZy.
(6)
2) Test Statistic and Null Distribution. In order to ensure the convergence non-degenerate dis- tribution, we multiply the empirical estimate of the Frobenius norm by n, and set it as the test statistic Ter=n|[cx11z Let K x1z be the centralized kernel matrix, given by K x12 & H RT X|2 H, where H-1-!11² and R A -(*))=(())=)( kernel ridge regression. Here, I refers to the nxn identity matrix and 1 denotes the vector of ones. We now define Ky Kyiz similarly. Let X and λlyz be the eigenvalues of K 2 and K Kyzz. respectively. Let {a .a......,y,, a denote i.i.d. standard Gaussian variables, and thus {af...., a..)) denote i.i.d. x2 variables. Considering i.i.d. samples from the joint distribution IP X we have
which can be seen the residual after
Theorem 4 (Federated Conditional Independent Test). Under the null hypothesis Ho (X and Y are conditionally independent given Z), the test statistic
Tei A nl|Cxriz2l2
5

---

Published as a conference paper at ICLR 2024
has the asymptotic distribution
ter L Σ 1J=1
- n²
Ax
Although the defined test statistics are equivalent to that of kernel-based conditional independence test (KCI) (Zhang et al. 2012), the asymptotic distributions in different forms. Please note that the large sample properties needed when deriving the asymptotic distribution Tcr ahove, and the proof is shown Appendix A4.2
Given that X TT YIZ, could introduce the independence between Rxiz and Ryjz, which leads to the separation between X Axzz, and Xyız.,J We show that this separated form could help to approximate the null distribution in terms of decomposable statistic, such as the covariance matrix.
We approximate the null distribution with wwo-parameter Gamma distribution, which is related the mean and variance. Under the hypothesis Hu and given the sample D, the distribution of Ter can be approximated by the I(k; 0) distribution: P(t) = (th-1 c I(k)), where = (Tcr /D)/Var(" ("/aa(TTT)))) and Ô Var(Ter (D)r//DD)BTTTTT (D). We propose to approximate the null distribution with the mean and variance in the following theorem.
Theorem (Null Distribution Approximation). Under the null hypothesis Hy (X and Y are condi-
tionally independent given 7), we have
B(feilD) = tr(Cx12) tr(Criz),
(8)
War(Fer = =21[xx F ||Cr ll
where R H - H Ryjz, and tr(-) means the trace operator.
For testing the conditional independence X IL YIZ, in this paper, we only deal with the scenarios where X and each contain single variable while Z could contain a single variable, multiple variables, or be empty. When Z is empty, the test becomes the federated unconditional independent test (FUIT), as a special case. We provide more details about FUTT in Appendix A5
3.2 FEDERATED INDEPENDENT CHANGE PRINCIPLE (FICP)
independent change principle (ICP) to evaluate the depen- dence between two changing causal models. However, existing ICP (Huang et al.) 2020) heavily relies on the kernel matrix to calculate the normalized HSIC. It may be challenging for decentral- ized data because the off-diagonal entries of kernel matrix require the raw data from different clients, which violates the data privacy in federated learning. Motivated by that, we propose to estimate the normalized HSIC with the following theorem.
As described in Lemma
Theorem (Federated Independent Change Principle). order to check whether two causal models change independently across different domains, can estimate the dependence by
||c ,10,,1122
11 11
áx = tr(C)) tr(())' Dy-x=
(9)
tr(Ct)--r(()
where VE(YIX), { Cx and Cx are specially covariance matrices, and cx.Cr.C "..''annd and Cj are -eccially-deiinned variance matrices.
3.3 IMPLEMENTING FCIT AND FICP WITH SUMMARY STATISTICS
More details given about how to implement FCIT and FICP with summary statistics. The proce- dures at the clients and the server are shown Algorithm I Each client needs to calculate its local sample size and covariance tensor, which are aggregated into summary statistics the server.
The summary statistics contain two parts: total sample size n and covariance tensor Cy. With the summary statistics proxy, substitute the raw data at each client for FCD. The global

---

Published as a conference paper at ICLR 2024
Algorithm 1 FedCDH: Federated Causal Discovery from Heterogeneous Data
Input: data matrix Dj E R gu at each client, k. 25 E (1,..., }}
Output: a causal graph g
Client executes:
1: (Summary Statistics Calculation) For each client k; use the local data Dj to get the sample size ny and calculate the covariance tensor CT₁ and send them to the server.
Server executes:
2: (Summary Statistics Construction) Construct the summary statistics by summing up the local
sample sizes and the local covariance tensors: = E n2. CT =E== CT..
3: (Augmented Graph Initialization) Build a completely undirected graph Go on the extended vari-
able set V U (8), where denotes the observed variables and surrogate variable. 4: (Federated Conditional Independence Text) Conduct the federated conditional independence test based on the summary statisties, for skeleton discovery on augmented graph and direction determination with changing causal module. In the end, get intermediate graph G1.
5: (Federated Independent Change Principle) Conduct the federated independent change princi- ple based on the summary statistics, for direction determination with two changing causal mod- ules. Ultimately, output the causal graph g.
statistics are decomposable because they could be obtained by simply summing up the local ones, such as n= > == Th and 4 K kk=1 nBCTT. Specifically, we incorporate the random Fourier features (Rahimi & Recht 2007). because they have shown competitive performances to approxi- mate the continuous shift-invarian kemelss. According the following Lemma, could derive decomposable covariance matrix from an indecomposable kernel matrix via random features.
K
Lemma (Estimating Covariance Matrix from Kernel Matrix). Assuming there are i.i.d. samples for the centralized kernel matrices K,,, Ky, Kn. and the covariance matrix Ca.y, we have
tr( tr(Ka.)) x tr( (x) (1)² = (1(( (w((x)) = n2 tr tr Ky) =o tr( (z) (z)) where x. YERR, Ka, Ky, K ERRxR Co. ERAXA, 2w (ar) ERrxh is the centralized random fea- ture, (x) Dar ( (cos(wr bi)..... cos( wn +b,)) and &w (TT), and similarly for )w and ow w is drawn from PPw)) and b is drawn uniformly from [0, 2m].
(10)
T 2w (w (v) ) = 11 ( = n² 12
In this paper, and the delta kernel for discrete variables such as the surrogate variable U. It is important to note that this surrogate variable Ü is essentially a discrete variable (more specifically, a categorical vari- able, with no numerical order among different values), and common approach to deal with such discrete variables is to use delta kemnel. Notice that Cz.y denotes the covariance matrix for vari- able sets x and y. which is sample-wise decomposable because - मे Σ kmm T&Car, where Crein corresponds
random features approximate the Gaussian kernel for continuous variables
the local covariance matrix of variable sets 2& and yı at the k-th client. Here, we have Fk: ER CCo..y. ERixh_ In the augmented graph, there are d' d'=d+1 variables (d observed variables and one surrogate variable), thus we could construct a global covariance tensor CI d' xdd xhxh by summing up the local ones C ERd xd' xhxh
Theorem (Sufficiency of Summary Statisties). The summary statistics, consisting total sample size n. and covariance tensor Cy, are sufficient to represent all the statistics for FCD, including Tci in Eq. 7 E(īcr(D) and Var(Ter in Eq. and i and Dy in Eq. 9
According to the above theorem, with the total sample size n and the global covariance tensor CT at the server, it is sufficient to conduct FCIT and FICP in the FCD procedures. More details about skeleton discovery and direction determination rules will be given in appendix[A6
3.4 COMMUNICATION COSTS AND SECURE COMPUTATIONS
We propose construct summary statistics without directly sharing the raw data, which has already preserved the data privacy some extent. The original sample size of raw data is in R where
7

---

Published as a conference paper at ICLR 2024
1.00
1.00
Skeleton F.
0.75
Skeleton SHD
40-
Direction F
0.75
Direction SHD
40
0.50
0.50
20
20
0.25
0.25
0.00
0.00
10
20
10
20
30
20
30
20
30
Number of variables d
Number of variables d
Number variables d
Number variables
Skeleton SHD
Direction SHD
Skelcton F.
0.75
Direction Fi
0.75
0.25
0.25
10
20
30
10
20
30
10
20
30
10
20
50
Number of clients K
Number of clients K
Number of clients K
Number of clients K
1.00
1.00
Skeleton SHD
Direction SHD
Skeleton Fi
0.75
Direction
0.50
0.50
0.25
0.00
0.00
400
400
200
400
200 Number of samples
Number of samples
Number of samples
Number of samples ny
FedPC
NOTEARS-ADMM
FedDAG
FodCDH
Figure 3: Results of synthetic dataset on linear Gaussian model. By rows, we evaluate varying num- ber of variables d, varying number of clients K, and varying number of samples ng. By columns, we evaluate Skeleton F1 (t), Skeleton SHD (L), Direction F1 (1) and Direction SHD (4).
we assume n >> d', h. The constructed covariance tensor is in dimension Rd x x which could significantly reduce the communication costs when the sample size n large enough and the hidden dimension h is small enough. Furthermore, if each client is required to not directly share the local summary statistics, one can incorporate some standard secure computation techniques, such as secure multiparty computation (Crmeer et al., 2015), which allows different clients to collectively compute a function over their inputs while keeping them private, or homomorphic encryption (Acar al. 2018), which enables complex mathematical operations to process encrypted data without compromising the encryption. Please refer to Goryezka & Xiong (2015) for more about secure computation. worth noting that some secure computation techniques can introduce significant computation overhead. To further enhance privacy protection and computational efficiency, it would be beneficial to further improve our proposed method and leave for future explorations.
EXPERIMENTS
To evaluate the efficacy of our proposed method, we conduct extensive experiments on both synthetic and real-world datasets. For the synthetic datasets, consider the linear Gaussian model and general functional model to show that our method can handle arbitrary functional causal models. We ensure that all synthetic datasets have some changing causal models, meaning that they heterogeneous data. To show the wide applicability of our method, we run two real-world datasets, fMRI Hippocampus (Poldrack al. 2015) and HK Stock Market datasets (Huang al. 2020).
Synthetic Datasets. The true DAGs are simulated by Rédös model (Erdós et al. 1960 with
the number of edges equal to the number of variables. We randomly select 2 variables out of variables to be changing across clients. For the changing causal model, we generate according to the SCM: V-= ΣvyePA, (VV where E,E,, is the direct cause of V,. The causal strength of and the parameter a+ change across different client with index k. which are uniformly sampled from (0..5, 2.5) and (1(1, 3), respectively. We separately generate the data for each domain with different causal models and then combine them together. For the fixed causal model, we generate according V.= Eveer,, (iyʃi(V))te; +ei, We consider the linear Gaussian model with non-equal
8

---

Published as a conference paper at ICLR 2024
noise variances and the general functional model. For linear Gaussian model, f(VV)= and ea are sampled from Gaussian distribution with a non-equal variance which is uniformly sampled from 2).. For general functional model, f; is randomly chosen from linear, square, sinc, and tanh functions, and 6; follows uniform distribution 21( (00.5, 0.5) or Gaussian distribution ((0, 1)-
We compare our FedCDH method with other FCD baselines, such NOTEARS- (for linear case) (Ng & Zhang, 2022), NOTEARS-
NOTEARS-MLP-ADMM MLP-ADMM (for non-linear case) (Ng & Zhang 2022).
FedDAG (Gao et al. 2022) and FedPC (Huang et al.) 2022). We consider these baselines mainly because of their publicly available implementations. We evaluate both the undirected skeleton and the directed graph, denoted by "Skeleton" and "Direction" in the Figures. We use the structural Hamming distance (SHD). Fi score, precision, and recall as evaluation criteria. We evaluate variable
E (6. 12, 18, 24, 30) while fixing other variables such as K=10 and 10= We set client K 8, 16, 32} while fixing others such as d-6 and m0=100. We let the sample size in one client ny E (25, 50, 100, 200,400) while fixing other variables such as d=6 and K=10. Following the setting of previous works such as (Ng & Zhang] 2022), we set the sample size of each client to be equal, although our method can handle both equal and unequal sample size per client. For each setting, we run 10 instances with different random seeds and report the means and standard deviations. The results of Fi score and SHD are given in Figure 3 and Figure [A3 for two models, where our FedCDH method generally outperforms the other methods. Although we need large sample properties in the proof of Theorem 4 in practice we only have finite samples. According to the experiment of varying samples, we can see that with more samples the performance of our method is getting better. More analysis including the implementation details, the results of the precision and recall, the analysis of computational time, and the hyperparameter study, the statistical significance test, and the evaluation on graph density are provided in Appendix A7
Real-world Datasets. We evaluate our method and the baselines on two real-world dataset, fMRI Hippocampus (Poldrack et al. 2015) and HK Stock Market datasets (Huang et al. [020).. (i) fMRI Hippocampus dataset contains signals from d=6 separate brain regions: perirhinal cortex (PRC), parahippocampal cortex (PHC), entorhinal cortex (ERC), subiculum (Sub), CA1, and CA3/Dentate Gyrus (DG) in the resting states on the same person in 84 successive days. The records for each day can be regarded one domain, and there are 518 samples for each domain. We select 100 samples for each day and select K ( 8, 16, 32, 64) days for evaluating varying number of clients. We select K-10 days and select (25, 50, 100, 200,400) samples for evaluating varying number of samples. (ii) HK Stock Market dataset contains d=10 major stocks in Hong Kong stock market, which records the daily closing prices from 10/09/2006 08/09/2010. Here one day can be also seen as one domain. We set the number of clients to be KE 4, 6, 8, 10) while randomly select n4=100 samples for each client. All other settings are following previous one by default. More dataset information, implementation details, results and analysis are provided in Appendix A8
5 DISCUSSION AND CONCLUSION
Discussion. (i) Strengths: First of all, by formulating our summary statistics, the requirement for communication between the server and clients is restricted to only one singular instance, thereby substantially reducing the communication times. This is a marked improvement over other base- line methods that necessitate iterative communications. Additionally, the utilization of a surrogate variable enhances our capability to handle heterogeneous data. Furthermore, leveraging the non- parametric characteristics of our proposed FCIT and FICP, our FedCDH method can adeptly manage arbitrary functional causal models. (ii) Limitations: Firstly, the efficiency of our summary statistics in reducing communication costs may not be considerable when the sample size is small or the hid- den dimension h is large. Secondly, our method is designed specifically for horizontally horizootally-parrttionned partitioned federated data, hence cannot be directly applied to pertically-partitionn federated data.
This paper has put forth novel constraint-basee federated causal discovery method called FedCDH, demonstrating broad applicability across arbitrary functional causal models and heterogeneous data. We construct the summary statistics as a stand-in for raw data, ensuring the protection of data privacy. We further propose FCIT and FICP for skeleton discovery and direction determination. The extensive experiments, conducted both synthetic and real-world datasets, underscore the superior performance of our method over other baseline methods. For future research, will enhance our method to address more complex scenarios, such as vertically-partttionned
Conclusion.
partitioned data.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This material is based upon work supported by the Al Research Institutes Program funded by the National Science Foundation under AI Institute for Societal Decision Making (AI-SDM), Award No. 2229881. The project is also partially supported by the National Institutes of Health (NIH) under Contract R01HL159805, and grants from Apple Inc., KDDI Research Inc., Quris AI, and Infinite Brain Technology.
REFERENCES
Amin Abyaneh, Nino Scherrer, Patrick Schwab, Stefan Bauer, Bernhard Schölkopf, and Arash Mehrjou. Fed-cd: Federated causal discovery from interventional and observational data. arXiv preprint wwx.v:2221.038822 2022.
Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. A survey homomorphic en- cryption schemes: Theory and implementation. ACM Computing Surveys (Csur), 51()):1-35, 2018.
Muhammad Arshad and Marius C Silaghi. Distributed simulated annealing. Distributed Constraint Problem Solving and Reasoning in Multi-Agent Systems, 112, 2004.
Marcus Bendtsen. Regime aware learning. In Conference on Probabilistic Graphical Models, pD- 1-12. PMLR, 2016.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Vince D Calhoun, Robyn Miller, Godfrey Pearlson, and Tulay Adalı. The chronnectome: time- varying connectivity networks the next frontier in fmri data discovery. Neuron, 84(2):262-274, 2014.
Chandler Squires. causaldag: creation, manipulation, and learning of causal models. https///gthhbb.com//uhcclaaaasss 2018.
Rong Chen, Krishnamoorthy Sivakumar, and Hillol Kargupta. Learning bayesian network structure from distributed data. In Proceedings the 2003 SIAM International Conference on Data Mining, pp. 284-288. SIAM, 2003.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 507-5455 2002.
Ronald Cramer, Ivan Bjerre Damgård, et al. Secure multiparty computation. Cambridge University Press, 2015.
JJ Daudin. Partial association measures and an application to qualitative regression. Biometrika, 67 (3):581-590, 1980.
Dorit Dor and Michael Tarsi. A simple algorithm to construct a consistent extension of a partially oriented graph. Technicial Report R- 185, Cognitive Systems Laboratory, UCLA. 1992.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17760, 1960.
Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of condi- tional dependence. Advances neural information processing systems, 20, 2007.
Erdun Gao, Junjia Chen, Li Shen, Tongliang Liu, Mingming Gong, and Howard Bondell. Feddag: Federated dag structure learning, Transactions Machine Learning Research, 2022.
Slawomir Goryezka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5):463- 477, 2015.
10

---

Published as a conference paper at ICLR 2024
Kui Xiang Gou, Gong Xiu Jun, and Zheng Zhao. Learning bayesian network structure from dis- tributed homogeneous data. In Eighth acis international conference on software engineering, artificial intelligence. networking, and parallel/distributed computing (snpd 2007), volume 3, pp- 250-254. IEEE, 2007.
Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola. A kernel statistical test of independence. Advances in neurul information processing systems, 20, 2007.
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008.
Biwei Huang, Kun Zhang, and Bernhard Schölkopf. Identification of time deeedeennddnt causal model: A gaussian process treatment. In Twenty- Fourth international joint conference artificial intel- ligence, 2015.
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from beterogeneous/ionnaaiionnay data. The Journal of Machine Learning Research, 21(1): (111)3442233344 2020.
Jianli Huang, Kui Yu, Xianjie Guo, Fuyuan Cao, and Jiye Liang. Towards privacy-aware causal structure learning in federated setting. arXiv preprint M.Kiv:2211.06911 2022.
Brian Kidd, Kunbo Wang, Yanxun Xu, and Yang Ni. Federated learning for sparse bayesian mod- els with applications to electronic health records and genomics. PACIFIC SYMPOSIUM ON BIOCOMPUTING 2023: Kohala Coast, Hawaii, USA, 3-7 January 2023, pp. 484 495. World Scientific, 2022.
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclic- ity constraints. International Conference on Learning Representations, 2022.
Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35: 13104-13118 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiiiee learning deep networks from decentralized data. In Artificial intelli- gence and statistics, pp.
PMLR, 2017.
Osman Mian, David Kaltenpoth, Michael Kamp, and Jilles Vreeken. Nothing but regrets- preserving federated causal discovery. In International Conference on Artificial Intelligence and Statistics, pp. 9263-82788 PMLR, 2023.
Yongchan Na and Jihoon Yang. Distributed bayesian network structure learning. In 2010 IEEE International Symposium Industrial Electronics, pp. 1607-1611. IEEE, 2010.
Ignavier Ng and Kun Zhang. Towards federated bayesian network structure learning with continuous optimization. In International Conference on Artificial Intelligence and Statistics, pp. 6095-81111 PMLR, 2022.
Ignavier Ng, Sébastien Lachapelle, Nan Rosemary Ke, Simon Lacoste-Julien, and Kun Zhang On the convergence of continuous constrained optimization for structure learning. In International Conference on Artificial Intelligence and Statistics, 2022.
Ignavier Ng. Biwei Huang, and Kun Zhang. Structure learning with continuous optimization: A sober look and beyond. arXiv preprint 0rXiv:2304.021460 2023.
Ana Rita Nogueira, João Gama, and Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics Games, 8(3):003, 2021.
Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):2192228, 2014.

---

Published as a conference paper at ICLR 2024
Russell A Poldrack, Timothy O Laumann, Oluwasanmi Koyejo, Brenda Gregory, Ashleigh Hover, Mei- Yen Chen, Krzysztof Gorgolewski, Jeffrey Luci. Sung Jun Joo, Ryan Boyd, et al. Long- term neural and physiological phenotyping of single human. Nature communications, 6(1):
8885, 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Alexander Reisach, Christof Seiler, and Sebastian Weichwald. Beware of the simulated DAG! causal discovery benchmarks may easy to game. Advances in Neural Information Processing Systems, 2021.
Basil Saeed, Snigdha Panigrahi, and Caroline Uhler. Causal structure discovery from distributions arising from mixtures of dags. In International Conference on Machine Learning, pp. 8336-8344
PMIR, 2020.
Saeed Samet and Ali Miri. Privacy-preserving bayesian network for horizontally partitioned data. In 2009 International Conference on Computational Science and Engineering, volume 3, pp. 9-16. IEEE, 2009,
Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunities with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10 (1):1-12, 2020.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Peter Spirtes. An anytime algorithm for causal inference. In International Workshop Artificial Intelligence and Statistics, pp. 278-285. PMLR, 2001.
Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodological advances. Applied informatics, volume pp. 1-28. SpringerOpen, 2016.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional inde- pendence tests for fast parammettii causal discovery. Journal of Causal Inference, 7(1), 2019.
Danica Sutherland and Jeff Schneider. On the error of random fourier features. arXiv preprint wrXiv:1506.0278: 2015.
Ruibo Tu, Kun Zhang. Bertilson, Hedvig Kjellstrom, and Cheng Zhang. Neuropathic pain diagnosis simulator for causal discovery algorithm evaluation. Advances in Neural Information Processing Systems, 32, 2019.
Matej Vuković and Stefan Thalmann. Causal discovery in manufacturing: A structured literature review. Journal of Manufacturing and Materials Processing, 6(1):10, 2022.
Zhaoyu Wang, Pingchuan Ma, and Shuai Wang. Towards practical federated causal structure learn- ing, arXiv preprint arXiv:2306.094: 2023.
Dennis Wei, Tian Gao, and Yue Yu. DAGs with no fears: A closer look at continuous optimization for learning Bayesian networks. In Advances in Neural Information Processing Systems, 2020.
Robert F Woolson. Wilcoxon signed-rank test. Wiley encyclopedia of clinical trials, pp. 1-3, 2007.
Eric P Xing, Wenjie Fu, and Le Song. A state-space mixed membership blockmodel for dynamic network tomography. The Annals of Applied Statistics, 4(2):535-566, 2010.
Qiang Yang, Yang Liu, Yong Cheng, Yan Kang, Tianjian Chen, and Han Yu. Federated learning. Synthesis Lectures Artificial Intelligence and Machine Learning, 13(3):1-207, 2019.
12

---

Published as a conference paper at ICLR 2024
Qiaoling Ye, Arash A Amini, and Qing Zhou. Distributed learning of generalized linear causal networks. arXiv preprint wxXi:2201.091900 2022.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural
networks. In International Conference on Machine Learning, pp. 7154-7163, PMLR, 2019.
Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: An efficient dag structure learning approach. In International Conference on Machine Learning, pp. 12156-12166. PMLR, 2021.
Kun Zhang and Lai-Wan Chan. Extensions of ica for causality discovery in the hong kong stock market. In International Conference on Neural Information Processing, pp. 400-409. Springer, 2006.
Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. arXiv preprint arXiv: 2599, 2012.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprint arXiv: urXiv: 1202.3775 2012.
Kun Zhang, Biwei Huang, Jiji Zhang, Bernhard Schölkopf, and Clark Glymour. Discovery and visualization of nonstationary causal models. arXiv preprint wrxXiv:/50908000 2015.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with tears: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, 31, 2018
Fangting Zhou, Kejun He, and Yang Ni. Causal discovery with heterogeneous observational data. In Uncertainty in Artificial Intelligence, pp. 2383-2393. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2024
Appendix for
"Federated Causal Discovery from Heterogeneous Data"
Appendix organization:
A1 Summary of Symbols
15
A2 Related Works
15
A3 Details about the Characterization
16
A3.1 Characterization of Conditional Independence
16
A3,2 Characterization of Independent Change
18
A4 Proofs
18
A4.1 Proof of Lemma
19
A4.2 Proof of Theorem
19
A4.3 Proof of Theorem
21
A4.4 Proof of Theorem
22
A4,5 Proof of Lemma
23
A4.6 Proof of Theorem
24
A5 Details about Federated Unconditional Independence Test
24
A5.1 Null Hypothesis
25
A5.2 Null Distribution Approximation)
25
A6 Details about Skeleton Discovery and Direction Determination
25
A6.1 Skeleton Discovery,
25
A6.2 Direction Determination.
26
A7 Details about the Experiments on Synthetic Datasets
28
A7.1 Implementation Details
28
A7.2 Analysis of Fj and SHD
................................
28
A7.3 Results of Precision and Recall
29
................................
A7.4 Results of Computational Time
29
A7.5 Hyperparameter Study
................................
30
A7.6 Statistical Significance Test
31
A7.7 Evaluation Dense Graph
31
A7.8 Evaluation on the power of conditional independence test
32
A7.9 Evaluation the order of domain indices
32
A8 Details about the Experiments Real-world Dataset
33
14

---

Published as a conference paper at ICLR 2024
A8.1 Details about fMRI Hippocampus Dataset
33
A8.2 Details about HK Stock Market Dataset
34
A1
SUMMARY OF SYMBOLS
In order improve the readability of our paper, summarize the most important symbols and their meanings throughout the paper, as shown in Table A1
Table A1: Summary of symbols
Symhol
Meaning
Symbol
Meaning
d
the number of observed variables.
R
the total sample size of all clients. the data matrix, s R the sample size of 1-th client. the 1-th variable. i E {1....d].
the number of clients.
k
the client index, & E {l.... K). domain index. E {1. K).
flk VG
J((-)
the causal function of variable V,, the noise term V4 the effective purameter of V,
PAG
the parents V,- a set of "pseudo confounders". the number of "pseudo confounders". the augmented graph with d++1 variables.
&
L
G. Sate
the causal graph with d variables.
Guog
X. Y.
a set random variables. the domains for variables.
kx ky, liz Hx. Hy.
the positive definite kemels. the reproducing kemel Hilbert spaces. the normalized HSIC.
X
X & (X.
A
Σ
the cross-co-ariance operator in infinite dimension.
C
the covaicovare matrix in finite dimension.
the number of hidden features/mapping functions. the function spaces. A= ((X) R
10)a()).()
the mapping functions. the regression coefficients.
0,1
A
B
g(Y) Baxh.
the ridge purameter.
1
the identity matrix.
K
the centralized kernel matrix. the test statistic for conditional independence. the standard Gaussian variable.
H
the matrix for centralization, H 1 111". the residual for ridge regression. the xi variable.
Ter
R
the nonzero cigenvalues.
Tcr
the asymptotic statistic.
the parameters for Gamma distribution [(k,6)
C"
the specially-designed covariance matrix. dl (plus surrogate variable). local covariance tensor, Cr, R xe shach the intercepts for random features.
tr(-)
trace operator.
global covariance tensor, Cr E gd xd' xkxch the coefficients for random features.
CT
b
A2 RELATED WORKS
Causal Discovery. In general, there are mainly three categories of methods for causal discovery (CD) from observed data (Spirtes & Zhang 2016): constraint-based methods, score-based meth- ods and function-based methods. Constraint- methods utilize the conditional independence test (CIT) to learn a skeleton of the directed acyclic graph (DAG), and then orient the edges upon the skeleton. Such methods contain Peter-Clark (PC) algorithm (Spirtes & Zhang 2016) and Fast Causal Inference (FCI) algorithm (Spirtes) 2001). Some typical CTT methods include kernel-based
independent conditional test (Zhang al. 2012) and approximate kernel-based conditional indepen- dent test (Strobl et al. 2019). Score-based methods use score function and a greedy search method learn DAG with the highest score by searching all possible DAGs from the data, such Greedy Equivalent Search (GES) (Chickering) 2002). Within the score-based category, there is a continu- ous optinization-bant subcategory attracting increasing attention. NOTEARS (Zheng et 2018) firstly reformulates the DAG learning process as a continuous optimization problem and solves it using gradient-based method. NOTEARS is designed under the assumption of the linear relations between variables. Subsequent works have extended NOTEARS to handle nonlinear cases via deep neural networks, such as DAG-GNN Yu et al. 2019) and DAG-NoCurl (Yu et al. 2021). ENCO (Lippe et al. 2022) presents efficient DAG discovery method for directed acyclic causal graphs utilizing both observational and interventional data. AVCI (Lorch et al.) 2022) infers causal struc- ture by performing amortized variational inference
arbitrary data-generee generatieerg distribution.
These paniinous-optimmizaton baasza methods might suffer from various technical issues, including
convergence (Wei et al. 2020 Ng al. 2022), nonconvexity (Ng al. 2023), and sensitivity to
15

---

Published as a conference paper at ICLR 2024
data standardization (Reisach et al. 2021). Function- based methods rely the causal asymmetry property, including the linear non- Gaussins model (LiNGAM) (Shimizu et al. (006), the additive noise model (Hoyer et al., 2008), and the post-nonlinear causal model (Zhang & Hyvarinen 2012).
Causal Discovery from Heterogeneous Data. Most of the causal discovery methods mentioned above usually assume that the data is independently and identically distributed (i.i.d.). However, in practical scenarios, distribution shift is possibly occurring across datasets, which can be changing across different domains or over time, as featured by heterogeneous or non-stationary data (Huang) et al. 2020). To tackle the issue of changing causal models, one may try to find causal models on sliding windows for non-stationary data (Calhoun et al., 2014), and then compare them. Improved versions include the regime aware learning algorithm to learn a sequence of Bayesian networks that model a system with regime changes (Bendtsen) 2016). Such methods may suffer from high esti- mation variance due to sample scarcity, large type II errors, and a large number of statistical tests. Some methods aim to estimate the time-varying causal model by making use of certain types of smoothness of the change (Huang et al. 2015), , but they do not explicitly locate the changing causal modules. Several methods aim to model time-varying time-delayed causal relations (Xing et al.) 2010), which can be reduced to online parameter learning because the direction of the causal rela- tions is given (i.e., the past influences the future). Moreover, most of these methods assume linear causal models, limiting their applicability to complex problems with nonlinear causal relations. In particular, a nonparametric constraint-based method to tackle this causal discovery problem from non-stationary or heterogeneous data, called CD-NOD (Huang et al.) 2020). was recently proposed, where the surrogate variable was introduced, written as smooth functions of time or domain index. The first model-based method was proposed for heterogeneous data in the presence of cyclic causal- ity and confounders, named CHOD (Zhou et al., 2022). Saeed et al. (Saeed et al. 2020) provided a graphical representation via the mixture DAG of distributions that arise as mixtures of causal DAGs.
Federated Causal Discovery. A two-step procedure was adopted (Gou et al. 2007] to learn a DAG from horizontally partitioned data, which firstly estimated the structures independently using each client's local dataset, and secondly applied further conditional independence test. Instead of us- ing statistical test in the second step, a voting scheme was used to pick those edges identified by more than half of the clients (Na & Yang, 2010). These methods leverage only the final graphs independently estimated from each local dataset, which may lead to suboptimal performance as the information exchange may be rather limited. Furthermore, (Samet & Miri, (009) developed wrivacy-preserve method based on secure multiparty computation, but was limited to the discrete case. For vertically partitioned data, (Yang al. (019)) constructed an approximation
the score function in the discrete case and adopted secure multiparty computation. (Chen et al. 2003) devel- oped a four-step procedure that involves transmitting a subset of samples from each client to a central site, which may lead to privacy concern. NOTEARS- ADMM (Ng & Zhang] (022) and Fed-DAG (Gao et al. 2022 were proposed for the federated causal discovery (FCD) based on continuous opti- mization methods. Fed-PC (Huang et al., (2022) was developed as federated version of classical PC algorithm, however, was developed for homogeneous data, which may lead to poor performance on heterogeneous data. DARLIS (Ye et al.| (002)) utilizes the distributed annealing (Arshad & Silaghi 2004) strategy to search for the optimal graph, while PERI (Mian et al., 2023) aggregates the results of the local greedy equivalent search (GES) (Chickering 2002) and chooses the worst-case regret for each itcration. Fed-CD (Abyanch et al., 2022) was proposed for both observational and inter- ventional data based continuous optimization. F (Wang al. 2023) extended x² test to the federated version, however, this method is restrictive on discrete variables and therefore not applicable for any continuous variables. Notice that most of these above-mentioned methods heav- ily rely on either identifiable functional causal models or homogeneous data distributions. These assumptions may be overly restrictive and difficult to be satisfied in real-world scenarios, limiting their diverse applicability.
A3 DETAILS ABOUT THE CHARACTERIZATION
A3.1
CHARACTERIZATION OF CONDITIONAL INDEPENDENCE
In this section, we will provide more details about the interpretation of Σ Exy z formulated in Eq. 13 the definition of characteristic kernel shown in Lemma 9 which is helpful to understand the
16

---

Published as a conference paper at ICLR 2024
Lemma I in the main paper. We then provide the umcorrelatecdnes--bsse characterization of CI in
Lemma 10
First of all, for the random vector (X X V, the cross-covariance operator from Hy to Hx defined by the relation
(x = -B -x
(11)
for all f E Hx and g E Hy. Furthermore, we define the partial cross-covariance operator as
Σxy z Exy ΣxzΣzzEar.
(12)
If Ezz is not invertible, use the right inverse instead of the inverse. We can intuitively interpret the operator Σxyiz 1 as the partial cross-covariance between V(EH) and (o(Y), VgEHy) given {g( [), VgEHz).
Lemma 9 (Characteristic Kernel (Fukumizu al. 2007)). ). A kernel Kx characteristic, if the condition Ex-Px = [(X) (FfEH)) implies Px=Qx, where Px and Qx are two probability distributions of X. Gaussian kernel and Laplacian kernel are characteristic kermels.
As shown in Lemma if we use characteristic kernel and define X - (X, Z), the characterization
of CI could be related to the partial cross crvar-cov as Σ Σ = 0 > X TT YIZ, where
Exy 2 Exx ~22
(13)
Similarly, we can intuitively interpret the operator Σ Σx the partial cross-covariance between YfEH)) and
given {g( vgHH)).
Based on Lemma we further consider a different characterization of CI which enforces the uncorrelatedness of functions in suitable spaces, which may be intuitively more appealing. De- note the probability distribution of X Px and the joint distribution of (X, Y) as Pxy. Let L be the space of square integrable functions of X and y be that of (X,Y). Y). Specifically, T (J(X)(B(J2) o.), and likewise for y Particularly, consider the following constrained
L spaces:
Sx & (f 1 Z( 0),
Sy L [g E L3 [(g = 0}.
(14)
S 2 (g 1 - - [Eg 2) L3}.
They can constructed from the corresponding L spaces via nonlinear regression. From example, for any function f E Lix the corresponding function f' is given by:
f(x) f()- f(X) (7)),,
(15)
where (Z) E T.3 is the regression function of f(X) on Z. Then, we can then relate the different characterization of CI from Lemma | to the uncorrelatedness in the following lemma.
Lemma (Characterization of CI based on Partial Association (Daudin 1980)). Each of the fol- lowing conditions are equivalent to X IL YIZ
(z.) B(fg) = 0,4ʃ S and Vg E Sp.
(i.. B(fg') 0, V E Sx and Vg' E E
(16)
(Mi.. B(fğ) v E Sx and Vğ 122
(iv.) B(fğ') = 0, Vf E Sx and Vg' L²y
When (X, Y, Z) are jointly Gaussian, the independence is equivalent to the uncorrelatedness, in other
words, X Z is equivalent to the vanishing of the partial correlation cocfficient Pxy We can regard the Lemma 10 as generalization of the partial correlation based characterization of CI.
17

---

Published as a conference paper at ICLR 2024
For example, condition (i) means that any "residual" function of (X, Z) given Z is uncorrelated with that of (Y, 2) given Z. Here we can observe the similarity between Lemma] ] and Lemma T0 except the only difference that Lemma considers all functions in L spaces, while Lemma exploits the spaces corresponding to some characteristic kernels. If we restrict the function ff and in condition (ii) the spaces Hy and Hy, respectively, Lemma io then reduced to Lemma
Based on the two lemmas mentioned above plus the Lemma 1. our main paper.
we could further derive Lemma 3 in
A3.2 CHARACTERIZATION OF INDEPENDENT CHANGE
In Lemma 2 of the main paper, we provide the independent change principle (ICP) to evaluate the dependence between two changing causal models. Here, we give more details about the definition and the assigned value of normalized HSIC. A smaller value means being more independent.
Definition (Normalized HSIC (Fukumizu et al.) (007)). Given variables U and V, HSIC provides measure for testing their statistical independence. An estimator of normalized HSIC is given as
tr(MuMy)
HSICY
(17)
tr tr(Mu) tr(Mv)
where My and My the centralized Gram matrices, My HM Mv HMy H,
H = 1 -11", I is n x n identity matrix and is vector of n ones. How to construct My and My wifi be explained in the corresponding cases below. To check whether causal modules change independently across different domains, the dependence between I(X) and PY (X) and the dependence between PYY) and PP on the given data can be given by
tr(Mx MM1x)
tr tr Mx
4x-Y tr (r( tr tr(My
Dy-x=
(18)
tr(My) tr(Mxix)
According to CD-NOD (Huang et al. 2020), instead of working with conditional distribution P(X(Y) and [X). we could use the "joint distribution" IPX,,), which is simpler, for esti- mation. Here we use Y instead of Y to emphasize that in this constructed distribution X and Y are not symmetric. Then, the dependence values listed Eq. 18 could be estimated by
Âx-Y= = xrMxxMyx (r(M)) MyX))) Â = tr ( (r(My) (r(Mxy)'
(19)
where Mx A HM Mx & A Similarly, we define My, My and fryp. According (Huang al. 2020), we have
Ax A ((B)(C + -1I-
(20)
where Axx A (Crrs + + Axi; ((U) Raxh, y is a small ridge parameter, represents the feature map, and the surrogate variable indicating different domains or clients. Similarly, we define My and Āayjs-
Ar & 5(T)(Coos + CCoY
(21)
Moreover, Myx A HMyx H. Myx A AY PYxO Similarly, we define Mxv, Mxy and Axy.
Yyxi A (Co + 71)
(22)
A & (Cus + -
Eq. 19as as formulated above is helpful to further derive Theorem 5 in our main paper.
A4
PROOFS
Here, we provide the proofs of the theorems and lemmas, including Lemma Theorem Theorem
Theorem 6 Lemma]) and Theorem 8 in our main paper.
18

---

Published as a conference paper at ICLR 2024
A4.1 PROOF OF LEMMA
Proof: We define the covariance matrix in the null hypothesis as Cxriz = 1/ Σー= I(A:
B(A]Z))) - -B.--(() which corresponds to the partial cross-covariance matrix with n samples, C Cxriz A=f(X)ERux, B=g(Y))RR>,, {f(())}==)=xx ( Notice that Fx and Fy. are function spaces. n and denote the number of total samples of all clients and the number of hidden features or mapping functions, respectively.
Notice that Z(Å[Z) and TE [B] Z) could be non-linear functions of 7 which may be difficult to estimate. therefore, we would like to approximate them with linear functions. Let g( (Z)) {q' (r)()))}=)}< We could estimate [Z) with the ridge regression output uj q(Z) under the mild conditions given below.
Lemma 11. (Sutherland Schneider 2015) Consider performing ridge regression of f on Z. Assume that (i) Ei =0, O, fa is defined on the domain of X; (ii) the empirical kernel matrix of Z, denoted by Kz, only has finite entries (i.e., [|K2 loc < oc); (iii) the range of Z is compact, Z C Rd Then we have
IP [E(F - 2z (()) 2
he
(23)
where [Zf+ is the estimate of (T((f)) Z) by ridge regression, Co and are both constants that do not depend on the sample size n or the number of hidden dimensions or mapping functions h.
The exponential rate with respect to h in the above lemma suggests of ridge regression with a small number hidden features. Moreover, we could similarly estimate
approximate the output
E(g' (Z) with off (Z), because we could guarantee that [B(g' 0/ (Z)l 2 + for any fixed > 0 at exponential rate with respect to h.
Similar to the L spaces in condition (ii) of Lemma 10 we can consider the following condition to approximate conditional independence:
E(fō) = 0, 0, Fx12 and Vg E Friz, where
Fx12 ff = - B(f f E Fx}.
(24)
fyiz = g'
-Bgg Z2, Fr..
we could estimate IE(FIZ) and (E (2) by ui ()) and of a(2), respectively. Thus, we can reformulate the function spaces as
According to Eq.
23
Fxı2 = 1 = f - up (Z), E Fxh.
(25)
Friz= = (g g¹ = g¹ - uz (Z) Fr
Proof ends.
A4.2 PROOF OF THEOREM 4
Proof: Assume that there are n i.i.d. samples for X, X.Y, Z. Let K x12 be the centralized kernel matrix, H,
4(Z)
given by K x R2x o Ry z - Ri x1z where ((x==(())=1(}+--) (()) which can be seen as the residual after ridge regression.
Similarly, We could define Ky Kriz R Ry Ryiz - gl)).
(Y
Ryz
and Accordingly.
we let K Kxyiz - R RT Rz = R RT H. We
Figure Al: Given that X JL Y|Z, we could introduce the independence between Rxiz and Ryjz-
set the test statistic as Tc-=nI|C x 12 where
C - RT.
R Rr|z= R
RT HHHY
x
19

---

Published as a conference paper at ICLR 2024
Let Axiz and Yriz be the eigenvalues of K 2 and Krjz. respectively. Furthermore, we define the EVD decomposition K xxiz = VxizAx x VT '/2 where A x the diagonal matrix containing non non-negative eigenvalues X A1zz5 Similarly, we define Kyiz VrizAr12 V with eigenvalues Ayiz, Let 4xiz [ 2xiz,2 " 81z,n - 2z 1/2 Ziz and Øy iz = [0r 0212,2 , lrlz,n] - Ar v|z
On the other hand, consider eigenvalues X 12, and eigenfunctions " "xIz, of the kernel kxjz w.r.t. the probablity measure with the density P(ö), ie., X and "x|z, satisfy f 2xjz 'x2 "xIz, where we assume that x z,, have unit variance, i... Elu X i (X)] = 1. Similarly, we define kyiz. 1y12, and 1412,55 Let a,,)) denote i.dd.
P()) (i)
standard Gaussian variables, and thus {aî..... a² denote i.i.d Xi variables.
Lemma 12 (Kerel-bbaeed Conditional Independence Test (Zhang et al. 2012)). Under the null hypothesis that X and Y are conditional independent given Z, we have that the test statistic Ter a tr [ XxzzKr1z have the same asymptotic distribution as Tei & =ER" dx ag. where NR are eigenvalues of ww. w [wi...., w,),, W.,, with the vector wi obtained by stacking M, [ (Xi), (x12. (x..
(Y)). (Yi). (x,,, (X.)1" [
( (rlz,,
In the above lemma, their test statistic is equivalent to ours, due to the fact that
1
1
tr(K & z xk)22)=
tr(
(1 X/2 Ry (2
n1
1 tr((Ai x12 Ry 2 R4 Rx
!
| Ry 1 11:
(26)
1
|| xr ||Cxx
n xl|Cxrizzll..
However, their asymptotic distribution is different from ours. Based on their asymptotic distribution, we could go further. The first two rows of Eq. hold true because the commutative property of trace, namely, tr(AB) BA, refer to Lemma for more details. According the formulation of Rxiz and Ryiz, we have
[((x) = u² (Z) + Rxiz ((()) - of (Z) + Ryiz.
(27)
Based on the above formulations, we could easily draw the causal graph as shown in Fig. In particular, considering that X and Y are conditionally independent given Z, could further determine that R R and Ryjz are independent. namely, we have
LLZ + Rxiz 1L Ryiz.
(28)
As f(X) and g{Y) uncorrelated, then B(w.) 0. Furthermore, the covariance is E C Cov(w,) = IE [(w,w?") where w is defined in the same way as in Lemma 12 If Røjz 11 Ryiz, for k & i or I + j. we denote the non non-diagonal (ND) entries of E as eND. where
eND El / x z MY.z. Xy Ni
2.1
A Xy Mizz,ii2z.. X
(29)
O.
We then denote the diagonal entries of Σ as eD. where
eD
A A1 \i
E
x
2
E
1
(30)
20

---

Published as a conference paper at ICLR 2024
which eigenvalues of E. According to (Zhagg et al. 2012). X1zz converge in probability
X 1x12 Substituting all the results into the asymptotic distribution in Lemma T2 can get the updated asymptotic distribution
To
as 3 Ax12,
(31)
n2
where /3 is the number of nonzero eigenvalues * of the kernel matrices K x|z Consequently, Ter and Tor have the same asymptotic distribution. Proof ends.
A4.3 PROOF OF THEOREM 5
Proof: First of all, since on follow the x2 distribution with one degree of freedom, thus we have B(afy) and Var(a 2. According to the asymptotic distribution in Theorem 4 and the derivation Lemma] 7 we have
E(Ter||D)
1 Axiz,AAiza
Σ
n²
1
Σ
Axiz, E Arizs
n²
Ir Ir(K x12) 1r( (r(K)
(32)
n2
1 tr(Rxx z R x1 tr 2 R (2)
n²
1
n² tr(n Cx 2) ur(n Cr1z)
-tr(Cxiz) tr(Cr
where Rxiz and Rriz are defined in the proof of Theorem above. Therefore, B(Ter(D) tr(Cx12) (r( xr(y)))
Furthermore, aZ are independent variables across and j. and notice that tr K x -i x|2
and similarly tr( K2 1212) = E, 2z, Based on the asymptotic distribution in Theorem 4 we have
War (frf n 4
Σ
x
X2i2, 22, Var(a
x
Σ
2 Σ X2izs
(33)
n²
2
tr K2
x 2)
tr 12)
n²
Additionally, according to the similar rule as in Eq.
26 we have
tr( K2 x = t
RT
Rx
x12
=tr(R's R Rx1z Ri Rx(z)
||R 1 R Rx 12
(34)
1|n- 21i
=n211Cx1211?=
21

---

Published as a conference paper at ICLR 2024
Similarly, have tr K2yy) n² =>2|[rr Substituting the results into the above formula- tion about variance, we have 7. tr(K33 x122 (1( o x121|x n0||Cr|2lli. Thus,
Var(TerlD) 2 22 [|Cy/z/i 1|.. Proof ends.
A4.4 PROOF OF THEOREM 6
Proof:
According to the above-mentioned formulations, we have Mx & HMxH = uxxz
X Axu - H Axjo Based the rules of estimating covariance matrix from kernel matrix
in Lemma 6, have
tr(Mx)= tr(āxis (x
(35)
(C)( + +7T) " (Ux))"(HH(())))))) +-T)
(36)
=tr(Cxu(CCus + + HC(o) + +7)) (oxx))
1 tr(Cxe(CCov + Cooosss + +
(37)
tr(()).
(38)
Eq. 35 is obtained due to the trace property of the product of the matrices, as shown in Lemma 6. Eq. 36 is substituting from Eq. 20 Here we use Eq. [8r simple notation. We can that it can be represented with some combinations of different covariance matrices. Similarly, we have
1 tr(Cyu + " + 71) + 'Co)) =t(()))
tr (r(M))
(39)
7
n
Regarding the centralized Gram matrices for joint distribution, similarly we have
1
(r(Myx)= = ir(Civ.x), + + + +, -,))-(c,(xxxx) - tr(C));
n
(40)
tr(Mxy)= n
tr(C(x.y),o(Cous + + CCur + yI) Co,(x.)) -
n tr(Cz),
where tr(Myx) tr (r(Mxy) Furthermore, based on Lemma 6 and Eq.
22
we have
tr(Mx Myx) = tr(ūxooλiju "xx|Oςyx))
(41)
llūk oÂxX 13
(CHo + 771 +1 (Ho(O))) + 7 (c,,,x)))
(42)
|[Cxzs(Cerss + --)-~1 HO(U) -
1 Cxer + - + -
(43)
2 |I x1
(44)
Eq. obtained due the trace property of the product of the matrices, as shown in Lemma 6. Eq. is substituting from Eq. 20 and Eq. 22 Here we use Eq. 44 simple notation. We can see that it can be represented with some combinations of different covariance matrices. Similarly, we have
tr(My Mxy) Cro(Cus Cou + CC,
(45)
|c cy 112.
n?
22

---

Published as a conference paper at ICLR 2024
Substituting the equations above into Eq. we have
19
||C x 1 x tr(Ck) tr(C
y 1 tr(ct)-tr(()) +tx()))*
(46)
Proof ends.
A4.5 PROOF OF LEMMA
Proof: First of all, we incorporate random Fourier features to approximate the kernels, because they have shown competitive performances to approximate the continuous shift-invariant kernels. Lemma 13 (Random Features (Rahimi & Recht 2007)). For continuous shift-invariant kernel K.(,,, v) on I., we have:
K(x,y) y) = pl dw En (z
(47)
where (u is an unbiased estimate of K(x,, y) when w is drawn p(w).
Since both the probability distribution p(w) and the kernel entry ((x y) are real, the integral in Eq- 47 converges when the complex exponentials are replaced with cosines. Therefore, we may get real-values mapping by:
K(x, v) (x)) (g),
2u (x) &
V h ccos w1 + co, + bn))",
(48)
2 2w V (cos(w1y) + b1),,.., cos(wny bn))²
where w is drawn from p(w) and is drawn uniformly from 2T,. v, w, b E IR, and the random- ized feature map &w kernel we would like to approximate. Here in this paper, we choose to approximate Gaussian kernel as one of the characteristic kernels, and thus set the probability distribution p(w) the Gaussian one. Based on Eq. 48 we have
RAA. The precise form of p(w) relies on the type of the shift-invariant
tr (r.K) x (z)
(49)
where yER", K KR. Furthermore, benefiting from the commutative property the trace of the product of two matrices, we have
is the centralized random feature, (x)) H on (a))
t (1)) = tr(ō (2) Th (x)),
(50)
Since each random feature is centralized, meaning the zero mean for each feature, therefore, we have:
1 (r) (x) = tr( Ca.w) = tr(Cu.g);
(51)
where Cr.,y is the covariance matrix for variable and y, Cr.y E RRxxh, h is the number of hidden features.
For the second formulation, we have
tr K K_K, = (1) (1)
(52)
(10w( 3m (v)
||nCa..
n² In2l(aa.a 1|2.
23

---

Published as a conference paper at ICLR 2024
Together with Eq. 49 Eq.
50
Eq.
51 and Eq. 52 formulated above, could prove the Lemma in
the main paper. Proof ends.
A4.6 PROOF OF THEOREM
Proof.
The summary statistics contain two parts: total sample size and covariance tensor Cy E Rd''d xkxh, Let Cj B be the (i,j)-th entry of the covariance tensor, which denotes the covariance matrix of the i-th and the j-th variable.
With the summary statistics as proxy, we can substitute the raw data at each client. During the procedures of causal discovery, the needed statistics include Tor in Theorem 4 B(Tcr|D) and Var(Ter in Theorem and å x and Dy in Theorem
1) Based on the Eq. (7) the main paper, we have
Cxriz =Cy Cxz(Czz +1))
=[,,z), - ((x,2), + 1
(53)
= (Cxy - (Cxz + C2z) + + +
In this paper, we consider the scenarios where X and Y are single variables, and Z may be single variable, a of variables, or empty. Assuming that contains L variables. We have
L -x2, Czz = ΣΣ
L
L
CzY
E2x. Cxz = -x2= 2m1
Cz.2,
(54)
1
where C2,,, Cx2,, and C2,2, are the entries the covariance tensor Cy. According to Theo- rem 3, Tes A m|le nl|Cxrizzl?? Therefore, the summary statistics are sufficient to represent TcI.
2) Similar to Eq. 53 we have
C212 (Cxx 2Cxz + C2z)((xx Czz) (Cx) + Czz)
(55)
Cy = Crr - -r
(56)
Substituting Eq. 54 into Eq. 55 and Eq.
56 we can also conclude that the covariance tensor other words, the summary statisties are sufficient to
sufficient to represent Cxiz and Cr zz represent ( and Var(Ter (D).
3) As shown section
A4.3 we have
| x
|C 11?
Åx
(57)
tr(C') tr(ez)'
ir(C;) tr(C*))
where each components can be represented as some combinations of covariance matrices, as shown Eq. 37 Eq. 39 Eq. 40 Eq. [3] and Eq. 45 Therefore, the summary statistics are sufficient to
represent Â A and A
4) To sum up. we could conclude that: The summary statistics, consisting of total sample size and covariance tensor Cr, are sufficient to represent all the statistics needed for federated causal discovery.
Proof ends.
A5 DETAILS ABOUT FEDERATED UNCONDITIONAL INDEPENDENCE TEST
Here, provide more details about the federated unconditional independence test (FUIT), where the conditioning set Z is empty. Generally, this method follows similar theorems for federated conditional independent test (FCIT).
24

---

Published as a conference paper at ICLR 2024
A5.1 NULL HYPOTHESIS
Consider the null and alternative hypothesis
Ho YYY,
H1 : X 1 Y.
(58)
Similar to FCTT, we consider the squared Frobenius norm of the empirical covariance matrix as an approximation, given as
Ho 11 0, Hi 11=1C>xlli 0.
(59)
In this unconditional case, we set the test statistics as Tor nlICxrlii li and give the following theorem.
Theorem 14 (Federated Unconditional Independent Test). Under the null hypothests Ho (X and Y are independent). the test statistic
Tor 2 nl|Cxrrlls
(60)
has the asymptotic distribution
L Tu
A n
Σ 1,1=1
where Ax and λy are the eigenvalues of Kxx and Ky, respectively. Here, the proof is similar to the proof of Theorem thus refer the readers to section A4.2 for more details.
A5.2 NULL DISTRIBUTION APPROXIMATION
We also approximate the null distribution with two-parameter Gamma distribution, which is related the mean and variance. Under the hypothesis Hg and given the sample D, the distribution of Ter can be approximated by the I'xx, 0) distribution. Here we provide the theorem for null distribution approximation.
Theorem 15 (Null Distribution Approximation). Under the null hypothesis Ho (X and Y are inde-
pendent), we have
E (D) tr(Cx) tr(Cy), Var(Tur (D) = 2||Cx |/ |Cy 1
(61)
Here, the proof similar to the proof of Theorem thus we refer the readers to section A4.3 for
more details.
A6 DETAILS ABOUT SKELETON DISCOVERY AND DIRECTION DETERMINATION
In this section, we will introduce how we do the skeleton discovery and direction determination during the process of federated causal discovery. All those steps are conducted on the server side. Our steps are similar to the previous method, such CD-NOD (Huang et al. 2020), the core dif- ference are that we develop and utilize our proposed federated conditional independent test (FCIT) and federated independent change principle (FICP).
A6.1 SKELETON DISCOVERY.
We first conduct skeleton discovery on the augmented graph. The extra surrogate variable is intro- duced in order to deal with the data heterogeneity across different clients.
Lemma 16. Given the Assumptions 2 and 3 in the main paper, for each V, E V. V; and are not adjacent in the graph if and only they are independent conditional some subset of (V,īj # i).
25

---

Published as a conference paper at ICLR 2024
Proof. If Vi's causal module is invariant, which means that PA,) remains the same for every value of Ö, then V2 TT PAg. Thus, if V2 and Ü are not independent conditional on any subset of other variables, Vi's module changes with U. which is represented by edge between V; and U. Conversely, we assume that if V/'s module changes, which entails that V; and Ü are not independent given P PA, then V, and U are not independent given any other subset of V ((V).. Proof ends.
Lemma 17. Given the Assumptions 1, 2 and 3 in the main paper, for every V1, V3 E V. V; and V are not adjacent if and only if they are independent conditional on some subset of {Vill i, A j) U (0}.
Proof. The "if" direction shown based on the faithfulness assumption on Gong and the fact that (17(8)) U {0;(38)) is a deterministic function of 0s The "only if" direction is proven by making use of the weak union property of conditional independence repeatedly. the fact that all {1b(35)) and {0,(3) are deterministic function of U, the above three assumptions, and the properties of mutual information. Please refer to (Zhang et al. 2015) for more complete proof.
With the given three assumptions in the main paper, we can do skeleton discovery.
i) Augmented graph initialization. First of all, build completely undirected graph on the extended variable set (U(T), where V denotes the observed variables and Ü is surrogate variable.
ii) Changing module detection. For each edge 25 V,, conduct the federated conditional independence test or federated unconditional independent test. If they are conditionally independent or independent, remove the edge between them. Otherwise, keep the edge and orient V,.
iii) Skeleton discovery. Moreover, for each edge V; - Vj. also conduct the federated indepen- dence test federated unconditional independent test. If they are conditionally indepen- dent or independent, remove the edge between them.
In the procedures, how observed variables depend on surrogate variable Ü is unknown and usually nonlinear, thus it crucial to use a general and non- non-parametric conditional independent test method, which should also satisfy the federated learning constraints. Here, we utilize our proposed FCIT.
A6.2 DIRECTION DETERMINATION.
After obtaining the skeleton, we can go on with the causal direction determination. By introducing the surrogate variable U, it does not only allow to infer the skeleton, but also facilitate the direction determinations. For each variable V, whose causal module is changing (i.e., V - VJ), in some ways we might determine the directions of every edge incident V. Assume another variable V, which is adjacent to V,, then we can determine the directions via the following rules.
i) Direction determination with one changing module. When Vj's causal module is not changing. we can see 75 - V - Vj forms an unshielded triple For practice purposes, we can take the direction between 25 and V; as 25 Vi, since we let 25 be the surrogate variable to indicate whether this causal module is changing or not. Then we can use the standard orientation rules (Spirtes et al. 2000) for unshielded triples orient the edge between V; and Vg. (1) If U and V; are independent conditional on some subset of { [Vill + j} which is excluding Vj, then the triple forms a V-structure, thus we have U + V; + Vg. (2) I and V; are independent conditional on some subset of (Vili * i} ((V}} which is including V,, then we have U + Vi V,. In the procedure, we apply our proposed FCIT.
ii) Direction determination with two changing modules. When Vj's causal module is chang- ing, we can see there is special confounder J between Vi2 - Vy. First of all, mentioned above, we can still orient V + V, and 25 - Vy. Then, inspired by that P(cause) and P(effect|cause cause) change independently, we can identify the direction between V; and V, according to Lemma 1, and we apply our proposed FICP.
26

---

Published as a conference paper at ICLR 2024
Skeleton Precision
Direction Precision
1.0
Skeleton Recall
1.0
Direction Recall
1.0
1.0
0.5
0.5
0.0
0.0
0.0
0.0
10
10
10
Number of variables
Number of variables
Number of variables
Number of variables
Skeleton Precision
1.5
Direction Precision
1.5
1.0
Skeleton Recall
Direction Recall
1.0
1.0-
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
30
Number of clients
Number of clients
Number of clients
Number clients
Skeleton Precision
Direction Precision
1.0
Skeleton Recall
2.0
Direction Recall
1.0
1.0
0.5-
0.5
0.0
0.0
0.0
200
200
Number of samples
Number of samples
Number of samples
Number of samples
FodPC
NOTEARS-ADMM
FedDAG
FedCDH
(a) Precision and recall on linear Gaussian model.
Skeleton Precision
1.5
Direction Precision
1.5
2.0-
Skeleton Recall
1.0
Direction Recall
0.5
0.5
0.5
10
20
10
20
10
20
30
10
20
Number of variables
Number of variables
Number of variables d
Number of variables d
Skeleton Precision
2.0-
Skeleton Recall
1.5
Direction Precision
1.0
Direction Recall
0.5
0.5
10
20
30
10
20
30
10
20
30
10
30
Number of clients K
Number of clients K
Number of clients K
Number of clients K
Skellton Precision
Dircetion Precision
1.0
Skeleton Recall
1.0
Direction Recall
1.0
0.5
0.5
0.0
0.0
0.0
200
400
400
200
Number of samples
Number of samples
Number of samples
Number of samples
FedPC
NOTEARS-MLP-ADMM.
FedDAG
FedCDH
(b) Precision and recall general functional model.
Figure A2: Results of the synthetic dataset on (a) linear Gaussian model and (b) general functional model. By rows in each subfigure, evaluate varying number of variables d, varying number of clients K, and varying number samples vg. By columns each subfigure, we evaluate Skeleton Precision (1), Skeleton Recall (1), Direction Precision (f) and Direction Recall (t).
27

---

Published as a conference paper at ICLR 2024
A7 DETAILS ABOUT THE EXPERIMENTS ON SYNTHETIC DATASETS
More details about the synthetic datasets are explained in this section, including the implementation
details in section A7.1 the results analysis of Fi and SHD in section 77.2 the complete results of precision and recall in section A7.3 the computational time analysis in section (A7.4 the hyperpa-
rameter study on the number of hidden features / in section [A7.5] the statistical significance test for
the results in section A7.6 and the evaluation on dense graph in section A7.7
A7.1 IMPLEMENTATION DETAILS
We provide the implementation details of our method and other baseline methods.
FedDAG Gao al. 2022 Codes are available at the author's 's Github repository https:
//github.. com/ E dunGAo (aaunGAA//FeDAG The hyperparameters are set by default.
(Ng & Zhang 2022): Codes are available at the author's Github repository https:: / //gittu.b...... com/ ignavierng/
NOTEARS-ADMI and NOTEARS-MLP-ADEE
hotears- admm) The hyperparameters are set by default, e.g., set the threshold level to 0.1 for post-processing.
FedPC (Huang et al. 2022): Although there is no public implementation provided by the author, considering that is the only constraint-based method among all the existing works for federated causal discovery, we still compared with it. We reproduced it based on the Causal-learn package https: ///gt//ggttta com/po///oooooo py why ccasallleaann Im- portantly, we follow the paper, set the voting rate as 30% and set the significance level to 0.05.
FodCDH (Ours): Our method developed based on the CD-NOD (Huang et al. 2020) and KCI (Zhang et al.] 2012) which are publicly available in the Causal-learn package https: / /ggthub...... com/ py www.whhhhheeeeeee http//ausalleaaee
We set the hyperparameter /t to 5, and set the significance level for FCIT to 0.05. Our source code has been appended in the Supplementary Materials.
and FedDAG, the output is directed acyelic graph (DAG), while FedPC and our FedCDH may output a completed partially directed acyelic graph (CPDAG). To ease comparisons. use the simple orientation rules (Dor & Tarsi 1992) implemented by Causal-DAG (Chandler Squires] (018) to convert CPDAG into a DAG. We eval- uate both the undirected skeleton and the directed graph, denoted by "Skeleton" and "Direction" as shown in the Figures.
For NOTEARS-ADMM,
A7.2 ANALYSIS OF F AND SHD
We have provided the results of Fi and SHD in the main paper as shown in Figure and Figure here we provide further discussions and analysis.
A3
The results of linear Gaussian model are given in Figure 3 and those of general functional model are provided Figure/A3 According to the results, we observe that our FedCDH method generally outperforms all other baselines across different criteria and settings. According to the results of our method both of the two models, when d increases, the F1 score decreases and the SHD increases for skeletons and directions, indicating that FCD with more variables might be more challenging. On the contrary, when K and n4 increase, the F1 score grows and the SHD reduces. suggesting that more joint clients or samples could contribute to better performances for FCD.
In linear Gaussian model, NOTEARS-ADMM and FedPC generally outperform FedDAG. The rea- son may be that the front two methods were proposed for linear model while the latter one was specially proposed for nonlinear model. In general functional model, FedPC obtained the worst per- formance compared to other methods in direction Fi score, possibly due to its strong assumptions on linear model and homogeneous data. FedDAG and NOTEARS SEITEARS-MLP-ADAA MLP-ADMM revealed poor results regarding SHD, the reasons may be two-fold: they assume nonlinear identifiable model, which may not well handle the general functional model; and both of them are continuous continuous-opiimizatinn optimizationn based methods, which might suffer from various issues such as convergence and nonconvexity.
28

---

Published as a conference paper at ICLR 2024
1.00
Skelcton F.
0.75
Skeleton SHD
30-
40
Direction Fr
0.75
Direction SHD
30
20
20
0.25
10
0.25
10
10
20
30
10
20
30
10
20
30
10
20
30
Number of variables d
Number of variables d
Number of variables d
Number of variables
1.00
Skeleton F
0.75
Skoleton SHD
Direction Fy
0.75
Direction SHD
+
0.25
0.25
10
20
30
10
20
30
0.00
10
20
30
10
20
30
Number of clients K
Number of clients K
Number of clients
Number of clients
1.00
Skelcton F.
0.75
Skeleton SHD
Direction Ft
0.75
Direction SHD
?
0.50
0.25
0:25
2
200
400
200
400
200
400
200
400
Number of sumples ny
Number of samples My
Number of samples fll
Number of samples m FedCDH
FedPC
NOTEARS-MLP-ADMY
FedDAG
Figure A3: Results of synthetic dataset on general functional model. By rows, we evaluate vary- ing number of variables d, varying number of clients K, and varying number of samples na- By columns, we evaluate Skeleton Fi (t), Skeleton SHD (L), Direction Fi (t) and Direction SHD (4).
A7.3 RESULTS OF PRECISION AND RECALL
In the main paper, have only provided the results of Fj and SHD, due the space limit. Here, we provide more results and analysis of the precision and the recall. The results of average and standard deviation are exhibited in Figure A2] According to the results, we could observe that our FedCDH method generally outperformed all other baseline methods, regarding the precision of both skeleton and direction.
Moreover, in the linear Gaussian model, NOTEARS ADMM generally achieved the best perfor- mance regarding the recall although it performed poorly in precision, the reason might be that NOTEARS-
assumed homogeneous data distribution, which might face challenges in the scenarios with heterogeneous data. In the general functional model, when evaluating varying num- bers of clients K and samples FedDAG performed the best with respect to the recall, however, neither FedDAG nor NOTEARS-ME A-MM- obtained satisfactory results in the precision, the rea- methods, which might potentially
son might be that both of them are www.:ooosooiiiiiiiiioooooooo suffer from various issues such as convergence and nonconvexity.
A7.4 RESULTS OF COMPUTATIONAL TIME
Existing works about federated causal discovery rarely evaluate the computational time when con- ducting experiments. Actually, it usually difficult measure the exact computational time in real life, because of some facts, such the paralleled computation for clients, the communication time costs between the clients and the server, and so on. However, the computational time signif- icant factor to measure the effectiveness of a federated causal discovery method to be utilized in practical scenarios. Therefore, in this section, for making fair comparisons, we evaluate the com- putational time for each method, assuming that there is paralleled computation (meaning that record the computational time at each client and server and then simply add them up) and no extra communication cost (indicating zero time cost for communication).
We evaluate different settings as mentioned above, including varying number of variables d, varying number of clients K, and varying number of samples ng. We generate data according linear
29

---

Published as a conference paper at ICLR 2024
Table A2: Results of computational time for varying number of variables d, varying number of
clients K, and varying number of samples rag. We report the average and standard deviation over 10 runs. This the synthetic dataset based on linear Gaussian model.
Data Sizes
Methods
d K
77k
FcdPC
NOTEARS-ADMM
FedDAG
FedCDH (Ours)
6
3.87 L 1.97s
14.10 1: 1.89s
136.92 1 21.50s
8.14 1 2.47s
12
32.01 1 3.54s
28.33 1 2.46s
321.84 1 65.94s
62.69 7.77s
18
100
39.58 4.75s
35.13 1: 2.89s
398.27 149.51s
98.57 9.23s
24
84.05 + 7.64s
40.01 + 2.94s
715.80 +: 268.93s
172.11 18.18s
30
94.03 + 9.48s
56.35 + 3.91s
1441.13 + 519.04s
232.35 26.67s
0.72 0.24s
7.04 0.64s
50.38 + 11.29s
3.88 + 1.49s
2.07 + 0.73s
9.07 = 0.77s
85.08 + 15.68s
5.24 = 1.74s
6
100
3.64 1.54s
10.80 = 0.78s
114.81 + 29.67s
8.01 = 2.32s
5.79 2.59s
19.40 = 2.51s
342.34 62.28s
12.60 2.98s
32
14.08 + 4.44s
30.56 = 2.88s
714.06 + 137.31s
20.30 = 4.37s
0.48 0.10s
13.06 1 1.91s
125.77 1. 20.64s
3.75 1.29s
50
1.47 0.64s
13.75 = 2.51s
+ 20.38s
5.74 1.618
6
10
100
3.87 + 1.97s
14.10 = 1.89s
136,92 + 21.50s
8.14 2.47s
200
16.52 + 3.63s
14.68 = 2.23s
138.67 = 31.91s
13.78 3.75s
400
51.10 6.87s
15.90 = 2.54s
140.37 34.42s
22.86 4.55s
Gaussian model. For each setting, we run 10 instances, report the average and the standard deviation of the computational time. The results are exhibited in Table A2
According to the results, we could observe that among the four FCD methods, FedDAG is the least efficient method with the largest time cost, because uses two-level structure handle the het- erogeneous data: the first level learns the edges and directions of the graph and communicates with the server to get the model information from other clients, while the second level approximates the mechanism among variables and personally updates on its data to accommodate the data hetero- geneity. Meanwhile, FedPC, NOTEARS-ADMA and our FedCDH are comparable. In the setting of varying variables,
method exhibited unsatisfactory performance among the three methods, because the other two methods, FedPC and NOTEARS-ADMI are mainly for homogeneous data. However, in the of varying variables, NOTEARS-ADMM is the most ineffective method, be- cause with the increasing of clients, more parameters (one client corresponds to one sub adjacency matrix which needs be updated) should get involved in the optimization process, therefore, the total processing time can also increase by a large margin. In the scenario of varying samples, FedPC the slowest one among the three methods.
A7.5 HYPERPARAMETER STUDY
We conduct experiments on the hyperparameter, such as the number mapping functions hidden features h. Regarding the experiments in the main paper, we set h to 5 by default. Here in this sec- tion, we set (5, 10, 15, 20, 25, 35,300).4 d 6,
10, n4 100 and evaluate the performances. We generate data according to linear Gaussian model. We use the Fi score, the precision, the recall and the SHD for both skeleton and direction. We also report the runtime. We run 10 instances and report the average values. The experimental results are given in Table
According to the results, we could observe that with the number hidden features h increasing, the performance of the direction is obviously getting better, while the performance of the skeleton may fluctuate a little bit.
Theoretically, the more hidden features larger h we consider, the better performance of how closely the random features approximate the kernels should be. When the number of hidden features approaches infinity, the performance of random features and that of kernels should be almost the same. And the empirical results seem to consistent with the theory, where a large can lead to a higher F score and precision for the directed graph.
30

---

Published as a conference paper at ICLR 2024
Table A3: Hyperparameter study on the number hidden features h. We evaluate the Fi score, precision, recall, and SHD of both skeleton and direction. We report the average over 10 runs. This the synthetic dataset based on linear Gaussian model.
h Metries
Skeleton
Direction
Timel
Fj
Precision
Recallf
SHD
Precisiont
Recall
SHD
5
0.916
0.980
0.867
0.9
0.721
0.765
0.683
2.0
8.14s
10
0.916
0.980
0.867
0.9
0.747
0,810
0.700
2.0
8.87s
15
0.907
0.980
0.850
1.0
0.762
0.818
0.717
1.8
10.57s
20
0.889
0.980
0.833
0.767
0.833
0.717
12.72s
25
0.896
0.980
0.833
0.789
0.838
0.750
20.93s
30
0.896
0.980
0.833
1.1
0.825
0.873
0.783
1.4
37.60s
Table A4: Test result of statistical significance of our FedCDH method compared with other base- line methods. We report the p values via Wilcoxon signed-rank test (Woolson 2007). synthetic dataset based on linear Gaussian model.
This is the
Parameters
[FedCDH vs. FedPC)
[FedCDH vs. NOTEARS ADMM]
[FedCDH vs. FedDAG)
S-Fi
S-SHD
D-Fi
D-SHD
S-Fi
S-SHD
D-F:
D-SHD
S-F.
S-SHD
D-F
100
0.00
0.05
0.01
0.12
0.00
0.11
0.10
0.00
0.01
0.01
12
10
100
0.00
0.01
0.01
0.01
0.00
0.00
0.15
0.00
0.00
0.00
0.11
0.00
18
10
100
0.00
0.01
0.00
0.01
0.00
0.00
0.03
0.00
0.00
0.00
0.02
0.00
24
100
0.01
0.01
0.00
0.01
0.01
0.01
0.01
30
10
100
0.00
0.01
0.00
0.00
0.00
0.01
0.00
0.00
0.00
0.00
6
2
100
0.00
0.00
0.01
0.01
0.01
0.00
0.21
0.01
0.00
0.00
0.03
0.00
100
0.00
0.01
0.00
0.01
0.01
0.01
0.01
0.00
0.00
0.01
0.01
0.00
0.00
16
100
0.00
0.01
0.01
0.02
0.00
0.00
0.10
0.03
0.00
0.00
0.07
0.00
32
100
0.00
0.00
0.00
0.00
0.00
0.00
0.04
0.01
0.00
0.00
0.03
0.00
10
50
0.00
0.01
0.01
0.00
0.01
0.00
0.99
0.03
0.00
0.00
0.02
0.00
10
200
0.00
0.01
0.01
0.02
0.00
0.00
0.03
0.02
0.00
0.00
0.11
0.01
400
0.00
0.01
0.01
0.01
0.00
0.03
0.00
0.01
0.01
Moreover, the computational time is also increasing. When h is smaller than 20, the runtime creases steadily. When h is greater than 20, the runtime goes up rapidly. Importantly, we could see that even when small, such as 5, the general performance of our method is still robust and competitive.
A7.6 STATISTICAL SIGNIFICANCE TEST
In order to show the statistical significance of our method compared with other baseline methods on the synthetic linear Gaussian model, report the p values via Wilcoxon signed-rank test (Woolson) 2007]. as shown in Table A4 For each baseline method, we evaluate four criteria: Skeleton FI (S- FI), Skeleton SHD (S-SHD), Direction F1 (D-FI), and Direction SHD (D-SHD).
We set the significance level to 0.05. Those values higher than 0.05 are underlined. From the re- sults, we can see that the improvements of method are statistically significant at 5% significance level in general.
A7.7 EVALUATION ON DENSE GRAPH
As shown in Figure in the main paper, the true DAGs are simulated using the Erdös-Rényi model (Erdös et al. 1960) with the number of edges equal to the number of variables. Here consider more dense graph with the number edges are two times the number variables.
evaluate synthetic linear Gaussian model and general functional model, and record the Fi score and SHD for both skeleton and directed graphs. All other settings are following the previous ones by default.
31

---

random Published as a conference paper at ICLR 2024
1.00
1.00
Skeleton SHD
100
Direction SHD
100-
Skeleton F
0.75
Direction Fr
0.75
0.50
50
0.50
0.25
0.25
0.00
0.00
20
30
20
30
30
10
30
Number variables d
Number variables
Number variables
Number v'rriaalle
FedPC
NOTEARS-ADMM
FedDAG
FedCDH
1.00
1.00
Skeleton SHD
Direction SHD
100
Skeleton Fr
0.75
100
0.75
Direction
0.50
0.50
0.00
0.00
Number variables d
Number of variables
Number variables
Number of variables
FedPC
NOTEARS-MLP-ADMNN
FedDAG
FodCDH
Figure A4: We evaluate on synthetic linear Gaussian model (Top Row) and general functional model (Bottom Row) when the number of edges are two times the number of variables. By columns, we evaluate Skeleton F1 (1), Skeleton SHD (L), Direction Fi (f) and Direction SHD (J).
According to the results as shown in Figure A4 we can see that our methods still outperformed other baselines in varying number of variables. Interestingly, when the generated graph is more dense, the performance of FedPC will obviously go down for various number variables.
A7.8 EVALUATION ON THE POWER OF CONDITIONAL INDEPENDENCE TEST
Here added new set of experiments compare the power of our proposed federated conditional independence test and the centralized conditional independence test (i.e., kernel-based conditional independence test (Zhang al., 2012)).
We followed the previous paper (Zhang et al. 2012) and used the post-nonlinear model (Zhang & Hyvarinen 2012) generate data. Assume there are four variables W,, X, Y, and Z. X ((f(W) ex). Y (WW) + ey), and Z is independent from both X and Y. f and are functions randomly chosen from linear, square, sin and tan functions. Ex. ey. W and Z are sampled from either uniform distribution 4(-0.5, 0.5) or Gaussian distribution (0, 1). ex and ey are random noises. In this case, X and Y are dependent due to the shared component of W. Since Z is independent from both X and Y, therefore, we have X 1 Z Here we set the significance level to 0.05, and the total sample size varies from 200, 400, 600, 800 to 1000. For federated CIT, we set the number of clients to 10, therefore, each client has 20, 40, 60, 80, or 100 samples. We run 1000 simulations and record the power of the two tests. From the result in Figure A5 we
that the power of our federated CIT almost similar to that of centralized CIT. Particularly, when the sample size reaches 1000, both of the two tests achieve power with more than 95%.
A7.9 EVALUATION THE ORDER OF DOMAIN INDICES
In this section, we aim to find out whether the order of domain indices will impact the results. Theoretically, there should be no impact on the results when it takes different values because this domain index Ü is essentially discrete variable (more specifically, a categorical variable, with no numerical order among different values), a common approach deal with such discrete variable to use delta kernel (based Kronecker delta function), and therefore it is reasonable features to approximate the delta kernel for discrete variables.
Empirically, have added one set of experiments to evaluate whether the order of domain indices will impact the results. We have one set of domain indices and run our FedCDH on the syn-
thetic linear Gaussian model with varying number variables d {6. 12, 18, 24, 30) while keeping K = 10 and n, 100, other settings are the same as those in our main paper. Then, we randomly shuffle the indices for different domains, denoted by "FedCDH+SSuffle""
32

---

900 Published as a conference paper at ICLR 2024
1.0
0.8
Power
0.4
0.2
Federated CIT
Centralized CIT
200
300
400
500
600
700 800
1000
Number samples
Figure A5: Comparison regarding the power of test between federate conditional independence test and the centralized conditional independence test.
Skeleton SHD
Direction SHD
Skeleton Fr
0.75
0.75
Direction
0.25
0.25
10
20
30
10
20
30
10
20
30
10
20
Number of variables d
Number of variables d
Number of variables d
Number of variahles d
FedCDHHSShufll
FedCDH
Figure A6: Evaluation on the order of domain indices on linear Gaussian model. We evaluate vary- ing number of variables d. By columns, we evaluate Skeleton Fi (f), Skeleton SHD (L), Direction F1 (f) and Direction SHD (L).
As shown in Figure A6 the results turned out that: the performances between the two sets of dif- ferent domain indices are quite similar, and we may conclude that has no obvious impact on the results when the domain indices take different values.
A8 DETAILS ABOUT THE EXPERIMENTS ON REAL-WORLD DATASET
A8.1 DETAILS ABOUT FMRI HIPPOCAMPUS DATASET
We evaluate our method and the baselines on fMRI Hippocampus (Poldrack 2015). The direc- tions of anatomical ground truth are: PHC + ERC, PRC - ERC, ERC DG, DG CAI, CAI + Sub, Sub ERC and ERC + CAI. Generally, we follow a similar setting as the experiments on synthetic datasets. For each of them, we use the structural Hamming distance (SHD), the F1 score as evaluation criteria. We measure both the undirected skeleton and the directed graph. Here, consider varying number of clients K and varying number of samples in each client nag
The results of Fj score and SHD is given Figure A7 serve that our FedCDH method generally outperformed all other baseline methods, across all the criteria listed. The reason could be that our method is specifically designed for heterogeneous data while some baseline methods assume homogeneity like FedPC and NOTEARS-MLP-ADEE thermore, our method can handle arbitrary functional causal models, different from some baseline methods that assume linearity such FedPC. Compared with method, FedDAG performed much worse, the reason might be its nature the continuous optimization, which might suffer from various issues such convergence and nonconvexity.
According to the results, we could ob-
fur-
33

---

Published as a conference paper at ICLR 2024
Skeleton SHD
Direction SHD
Skeleton Fi
11.6
Direction Fi
0.6
10.0-
7.5
7.5-
0.4
5.0
20
20
Number of clients K
Number of clients K
Number of clients K
Number of clients
12.5
12.5
Skeleton Fi
0.5
Skeleton SHD
10.0
Dircction Fy
0.6
Direction SHD
10.0-
0.4
0.4
3.8
5.0-
0.2
0.2
Number of samples
Number of samples
Number of samples
Number of samples
FodPC
NOTEARS-MLP-ADMA
FedDAG
FedCDH
Figure A7: Results of real-world dataset IMRI Hippocampus (Poldrack et al. 2013). By rows, we evaluate varying number of clients K and varying number of samples n2.. By columns, we evaluate Skeleton Fi (t), Skeleton SHD (1), Direction F1 (f) and Direction SHD (4).
Skeleton Fi
Skcleton SHD
15
Direction F1
Direction SHD
15-
0.6
0.6
10-
0.4
0.4
2.5
5.0
10.0
2.5
5.0
7.5
10.0
2.5
5.0
7.5
10.0
2.5
5.0
7.5
10.0
Number of clients K
Number of clients K
Number of clients K
Number of clients
FedPC
NOTEARS-MLP-ADMMN
FedDAG
FedCDH
Figure A8: Results of weal-world dataset HK Stock Market (Huang et al. 2020 We evaluate varying
number of clients K, and we evaluate Skeleton Fi (1), Skeleton SHD (L), Direction Fi (t) and Direction SHD (J).
A8.2 DETAILS ABOUT HK STOCK MARKET DATASET
We also evaluate HK stock market dataset (Hunng al. 2020) (See Page 41 for details about the dataset), The HK stock dataset contains 10 major stocks. which are daily closing prices from 10/09/2006 08/09/2010. The 10 stocks are Cheung Kong Holdings (1), Wharf (Holdings) Limited (2), HSBC Holdings plc (3), Hong Kong Electric Holdings Limited (4), Hang Seng Bank Ltd (5), Henderson Land Development Co. Limited (6), Sun Hung Kai Properties Limited (7), Swire Group (8). Cathay Pacific Airways Ltd (9), and Bank of China Hong Kong (Holdings) Ltd (10). Among these stocks, 3, 5, and belong to Hang Seng Finance Sub-index (HSF), 1, 8, and belong to Hang Seng Commerce and Industry Sub-index (HSC), 2, 6. and 7 belong to Hang Seng Properties Sub-index (HSP), and 4 belongs to Hang Seng Utilities Sub-index (HSU).
Here one day be also while randomly select =00000 samples for each client. All other settings are following previous ones by default. The results are provided in Figure A8, According to the results, can infer that our FedCDH method also outperformed the other baseline methods, across the different criteria. Similar to the analysis above, our method is tailored for heterogeneous data, in contrast to baseline methods which assume homogeneity. Additionally, our approach
domain. We set the number of clients to be (2, 8, 10)
like FedPC and capable of handling arbitrary functional causal models, setting it apart from baseline methods like FedPC that assume linearity. When compared to our method, FedDAG exhibited significantly poorer performance. This could be attributed its reliance on continuous optimization, which may encounter challenges such as convergence and nonconvexity.
34


Reviews:
[{"review_id": "ppkl53uVGX", "reviewer": "Reviewer_71ck", "summary": "The authors propose a novel constraint-based federated causal discovery method, FedCDH, specifically tailored for heterogenous data distributions mostly existent in FL. Novelty is twofold: Using summary statistics as a surrogate for skeleton discovery and introducing a surrogate variable to model distribution changes. The paper is very well written and shows promising results.", "questions": "(1) Why the assumption \" We set the sample size of each client to be equal.\" is required? Data heterogeneity can come in number of samples, too. Having unequal samples across clients is realistic.\n\n(2) How the datasets are divided into clients is unclear to me.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) Topic is very relevant causal inference and ICLR communities. \n\n(2) Nicely written paper with lots of background material and well-documented code.\n\n(3) Federated causal discovery from heterogeneous data is challenging in theoretical and realistic experiment settings. \n\n(4) Ability to operate over general functional models.", "weaknesses": "(1) Communication cost for small sample size.\n\n(2) Why have a maximum number of clients of 10?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DHcyU86aAI", "reviewer": "Reviewer_j4X7", "summary": "This work addresses the problem of federated causal discovery, where one wishes to recover the causal structure of some domain given datasets from multiple independent sources. The authors address this problem by proposing a procedure that leverages summary statistics, rather than individual observations, from each source. The work proposes KCIT, and in order to allow for the adaptation to the federated setting random fourier features are used for an approximation. The work also proposes a federated version of the individual change principle, also leveraging summary statistics. Empirical results are provided which show favorable performance.", "questions": "All of my questions are largely laid out above. In general, it would be good to get a sense of the finite sample behavior of the proposed method.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper proposes a very sensible extension to existing work on conditional independence testing and the invariance condition to the federated learning setting. The authors lay out the proposed method well, and the approach is easy to follow and understand. In addition, the experimental results show nice performance in comparison to other methods.", "weaknesses": "In my view the largest issue with this method is that there are a few places that lack sufficient specificity. The authors use the kernel conditional independence test as a basis, but don't appear to specify the necessary assumptions on the underlying functional forms, same for the invariance principle. It also isn't clear to me how we should expect the behavior of the federated approach to compare to its non-federate counterpart, e.g., what assumptions are necessary on the number of samples per domain? What is loss of power between the federate and non-federated tests? The authors appeal to random fourier features, which seems necessary (or at least some approximation appears to be necessary) but it isn't clear to me under which conditions we should expect this algorithm to not pay a price for this approximation. I certainly could be missing something, but the proofs provided appear to rely on large sample properties, but it's really unclear to me when those start to kick in, e.g. when should we expect the test to converge? How many samples before the summary statistics applied to the random Fourier features become a reliable representation of the underlying distribution for a given source?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8QJKenDJnR", "reviewer": "Reviewer_SgBE", "summary": "The paper proposes a constraint-based federated causal discovery method suitable for heterogeneous data. That is, the paper assumes different but related structural causal models at each client and seeks to discover the global structural causal model where local differences are modeled using domain-specific effective parameters for each variable and a set of domain-specific the pseudo-confounders. The paper proposes to use the Hilbert-Schmidt independence criterion and a (federated) independent change principle, based on the partial cross-covariance operator on a reproducing kernel Hilbert space, which captures non-linearities in the relationship of variables based on the chosen kernel. To make computations tractable, it approximates the kernel with random Fourier features. It shows that these criteria can be computed from summary statistics based on the kernel matrices.", "questions": "**Questions:**\n- why assume $L$ hidden confounders? How is L set in practice? Could we simply choose $d$ or $2^d$? In the theoretical evaluation, $L$ is assumed to be equal to the number of datapoints n which goes to infinity. Isn't that a problematic assumption, or did I misread the proof of Thm. 4?\n- How does sharing local kernel matrices affect privacy?\n\n**Detailed Comments:**\n- The notation with bold $\\mathbf{\\psi}$ and normal $\\psi$ is visually hard to distinguish.\n- The formulation with an underlying causal graph and an augmented causal graph is not clear to me. For me it made sense to either assume an underlying \"augmented\" graph that captures local differences, or to assume an underlying graph and local interventions - these interventions are then modeled via the augmented graph. If the latter is the case, this should be clarified.\n- Is it necessary to consider $\\mho$ an observable variable? In the experiments, some additional information is used to decide the domain, but in general this is rarely possible. E.g., in [1] the domain is infered. What happens if you assumed that every client has a different domain and $\\mho$ is the client index? \n\n\n[1] Mian, Osman, Michael Kamp, and Jilles Vreeken. \"Information-theoretic causal discovery and intervention detection over multiple environments.\" Proceedings of the AAAI Conference on Artificial Intelligence, AAAI-23. 2023.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- federated causal discovery is a relevant and interesting problem\n- the method is well motivated and theoretically sound\n- good empirical performance", "weaknesses": "- the method requires that the different domains are known in the application", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qOlfQTVfUz", "reviewer": "Reviewer_157B", "summary": "In this paper, the authors propose a novel FCD method attempting to accommodate arbitrary causal models and heterogeneous data. Specifically, they first utilize a surrogate variable corresponding to the client index to account for the data heterogeneity across different clients. Then they develop a federated conditional independence test (FCIT) for causal skeleton discovery and establish a federated independent change principle (FICP) to determine causal directions. These approaches involve constructing summary statistics\nas a proxy of the raw data to protect data privacy. Owing to the nonparametric properties, FCIT and FICP make no assumption about particular functional forms, thereby facilitating the handling of arbitrary causal models. Extensive experiments on synthetic and real datasets could show the efficacy of the proposed method.", "questions": "Please see the weakness.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper features a detailed theoretical analysis and addresses a highly challenging problem.", "weaknesses": "This paper is relatively difficult to read, and it is not very comprehensible, making it not conducive for others to follow and reproduce the work. This paper presents a list of theorems, but I haven't seen a clear explanation of the specific challenging problem you have addressed. The relationship between these theorems and the contributions of the paper is quite ambiguous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G3ozj7k6O9", "reviewer": "Reviewer_VxyA", "summary": "This paper focuses on the problem of federated causal discovery from heterogeneous data, and proposes a novel constraint-based method called FedCDH, which can accommodate arbitrary causal models and heterogeneous data. It constructs the summary statistics to protect data privacy and further proposes federated conditional independence test (FCIT) and federated independent change principle (FICP) for skeleton discovery and direction determination. The experimental results on synthetic and real datasets show the efficacy of the proposed method.", "questions": "1. In the penultimate paragraph of page 2, the authors say ‘Let k be the client index, and ℧ be the domain index’, what’s the difference between client and domain?\n2. In the last paragraph of page 2, the authors say ‘When the data is heterogeneous, there must be some causal models changing across different domains. The changes may be caused by the variation of causal strengths or noise variances.’ The authors should better clarify what is the change of causal models.\n3. In the first paragraph of page 3, ψ(℧) and θi(℧) are functions of ℧, and ℧ is a positive integer from 1 to k. Actually, ℧ is a value defined by the authors, and does it have an impact on the results when it takes different values?\n4. In the fourth paragraph of page 3, as indicated by the authors, ℧ and Vi are connected by unobserved domain-changing variables ψ(℧) and θi(℧), so what does it mean of ‘If there is an edge between surrogate variable ℧ and observed variable Vi on Gaug’?\n5. The authors should improve the presentation quality of the paper and fix typos. For example:\n(1) In the second paragraph of page 5, ‘therefore, we would like to …’ -> ‘Therefore, we would like to …’.\n(2) In the second paragraph of the Section of A6.4 Results of Computational Time, ‘The results are exhibited in Table A3.’ -> ‘The results are exhibited in Table A1’.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The paper addresses the issue of heterogeneous data in federated causal discovery and relaxes the assumptions of causal models, which are critical problems.\n2. The paper proposes a novel constraint-based method for effectively conducting federated causal discovery from heterogeneous data.\n3. The paper provides detailed proofs for the presented theorems and lemmas. Extensive experiments demonstrate the effectiveness of the proposed method.", "weaknesses": "1. The paper conducts numerous experiments; however, it should provide a more in-depth analysis of the underlying reasons behind the experimental results, rather than just stating the observations.\n2. The section of method overuses symbols, leading to difficulties in understanding.\n3. The presentation of this paper can be largely improved for clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)