FedDAG: Federated DAG Structure Learning
Authors: Erdun Gao
Junjia Chen
Li Shen
Tongliang Liu
Mingming Gong
Howard Bondell
Venue: Accepted by TMLR ()

Abstract: To date, most directed acyclic graphs (DAGs) structure learning approaches require data to be stored in a central server. However, due to the consideration of privacy protection, data owners gradually refuse to share their personalized raw data to avoid private information leakage, making this task more troublesome by cutting off the first step. Thus, a puzzle arises: how do we discover the underlying DAG structure from decentralized data? In this paper, focusing on the additive noise models (ANMs) assumption of data generation, we take the first step in developing a gradient-based learning framework named FedDAG, which can learn the DAG structure without directly touching the local data and also can naturally handle the data heterogeneity. Our method benefits from a two-level structure of each local model. The first level structure learns the edges and directions of the graph and communicates with the server to get the model information from other clients during the learning procedure, while the second level structure approximates the mechanisms among variables and personally updates on its own data to accommodate the data heterogeneity. Moreover, FedDAG formulates the overall learning task as a continuous optimization problem by taking advantage of an equality acyclicity constraint, which can be solved by gradient descent methods to boost the searching efficiency. Extensive experiments on both synthetic and real-world datasets verify the efficacy of the proposed method.

Published in Transactions on Machine Learning Research (01/2023)
FedDAG: Federated DAG Structure Learning
Erdun Gao'
erdun hew.engggoo@ssuuee.....o edua.
School of Mathematics and Statistics, The University of Melbourne
Junjia Chen
cj11997050050sttunjjuuu......
Faculty of Electronic and Information Engineering, Xi'an Jiaotong University
Li Shen
shen&1100 com
JD Explore Academy
Tongliang Liu
tongliang, liu @sydney.. edu
TML Lab, Sydney AI Centre, The University of Sydney Deportment of Machine Learning, Mohamed bin Zayed University of Artificial Intelligence
Mingming Gong
trnggminn-gonn@uuimmee. edw..elldbeddeoooo..o
School of Mathematics and Statistics, The University of Melbourne
Howard Bondell
howard, bowdel/@@nimeell.l.....o edu
School of Mathematics and Statistics, The University of Melbourne
Reviewed on OpenReview: https: // openreview. net/ forum? id=MaWgBj261e
Abstract
To date, most directed acyclic graphs (DAGs) structure learning approaches require data to be stored in a central server. However, due to the consideration of privacy protection, data owners gradually refuse to share their personalized raw data to avoid private information leakage, making this task more troublesome by cutting off the first step. Thus, a puzzle arises: how do we discover the underlying DAG structure from decentralized data? In this paper, focusing
the additive noise models (ANMs) assumption of data, generation, take the first step in developing gradient-based learning framework named FedDAG, which can learn the DAG structure without directly touching the local data and also naturally handle the data heterogeneity. Our method benefits from a two-level structure of each local model. The first level structure learns the edges and directions of the graph and communicates with the server to get the model information from other clients during the learning procedure, while the second level structure approximates the mechanisms among variables and personally updates on its own data to accommodate the data heterogeneity. Moreover, FedDAG formulates the overall learning task continuous optimization problem by taking advantage of an equality acyclicity constraint, which can be solved by gradient descent methods to boost the searching efficiency. Extensive experiments on both synthetic and real-world dalasets verify the ellicacy of the proposed method.
1 Introduction
Bayesian Networks (BNs) have become prevalent over the last few decades by leveraging the graph theory and probability theory to model the probabilistic relationships among set of random variables, which can potentially provide mechanism for evidential reasoning (Pearl, 1985). The success of BNs has contributed to a furry of downstream real-world application problems in econometrics (Heekman, 2008), epidemiology (Greenland al., 1999), biological sciences (Imbens & Rubin, 2015) and social sciences (Marini
* Work done during an internship Explore Academy.

---

Published in Transactions on Machine Learning Research (01/2023)
& Singer, 1988). However, learning the graph structure of a BN from purely observational data remains significant challenge due to the NP-hard property, and therefore, cutting-edge research that has drawn considerable attention in both academic and industrial fields (Koller & Friedman, 2009; Jensen & Nielsen, 2007; Glymour et al., 2019; Zhong et al., 2018; Zheng, 2020).
men
2.5
0.0
Normalized SHDS
2.0
2.5
-10
1.5
25
25
-25
25
25
25
10
1.0
0
0.5
10
2.5
25
MCSL(AI
MCSL/Sop)
GS FedDeeD
Methods
(a)
(b)
Figure 1: (a) Visualization of heterogeneous data. Different colors represent data from different sources, while each sub-figure includes the distribution of one fixed dimension of data from all clients. (b) Normalizod structural hamming distances (SHDs) (4) of three methods, where MCSL (Sep) (Ng et al., 2022b) separately trains one model on local data while MCSL (All) trains one model all data, which is forbidden in FL.
Each BN is defined by a directed acyelic graph (DAG) and a set of parameters to depict the direction, strength, and shape of the mechanisms between variables (Kitson ct al., 2021). Over the recent decades, a bunch of methods (Spirtes et al., 2001; Chickering, 2002; Zheng, 2020) for discovering the DAG structure encoded among concerned events from the observational data have been proposed. In practice, however, finite sample problem bears the brunt of the performance decrease of DAG structure learning methods. Regularly (1) collecting data from various sources and then (2) designing the structure learning algorithm all collected data can serve direct and standard pipeline to alleviate this issue in this field. However, owing to the issue of data privacy, data owners gradually prefer not to share their personalized data with others (Kairouz et al., 2021). Naturally, the new predicament, how do we discover the underlying DAG structure from decentralized d has arisen. In statistical learning problems such as regression and classification, federated learning (FL) has been proposed to learn from locally stored data (McMahan et al., 2017). Inspired by the developments in FL, we aim to develop a federated DAG structure learning framework that enables learning the graph structure from the decentralized data. Compared to the traditional FL methods in statistical learning, federated DAG learning, a structural learning task, has the following two main differences:
Learning objective difference. Most of the previous FL rescarches focus on learning an estimator to estimate the conditional distribution P(Y[X) in supervised learning lasks, e.g., image classification (McMa- han et al., 2017; Li et al., 2020), sequence tagging (Lin et al., 2022), and feature prediction (Kairouz et al., 2021). However, DAG structure learning, an unsupervised learning task (Glymour et al., 2019), tries find the underlying graph structure among the concerned variables and the relationship mechanisms estimators to fit with the joint, distribution of observations.
Data heterogeneity difference. The setup of data heterogeneity in FL is mainly assumed to be caused by some specific distribution shifts such as label shift (the shift of P(Y)) Lipton et al. (2018) or covariate shift (the shift of P(X)) Reisizadeh et al. (2020), while federated DAG learning handles a generative model, which can allow the data heterogencity resulted from the joint distribution shift of all variables (Figure 1(a)). This would bring more challenges than the FL paradigm model design.
Notice that this paper, we restrict our scope define the privacy leakage by sharing the raw data of users.
2

---

Published in Transactions on Machine Learning Research (01/2023)
In this paper, we present FedDAG, a gradient-based framework for learning the underlying graph structure from decentralized data, including the case of heterogeneous data caused by mechanisms change. (1) To alleviate the data leakage problem, FedDAG inherits the merits of FL, which proposes to deploy a local model to each client separately and collaboratively learn a joint model at the server end. Instead of sharing raw data, FedDAG exchanges model info among clients and the server to achieve collaboration. (2) Taking into consideration of the first main difference between FedDAG and FL, a two-level structure consisting of a graph structure learning (GSL) part and a mechanisms approximating (MA) part, respectively, is adopted as the local model. (3) Benefiting from this separated structure, the second difference between FL. and FedDAG can naturally be handled by only sharing the GSL parts of clients during the learning procedure and locally updating the MA parts to get with data heterogeneity. Moreover, we provide the structure i conditions for learning DAG structure from decentralized data in Appendix A. Our contributions are summarized as follows:
We introduce the federated DAG structure learning task under the assumption that the underlying graph structure among different datasets remains invariant while mechanisms vary. We also show the structure identifiability conditions of DAG learning from the decentralized data.
We propose FedDAG, which separately learns the mechanisms local data and jointly learns the DAG structure to handle the data heterogeneity elegantly. Meanwhile, since 0 bits of raw data are shared, but only parameters of the GSL parts of models, the requirement of privacy protection is guaranteed, and the commmication pressure is relatively low.
We evaluate our proposed method on data following structure equation models of additive noise structure with variety of experimental settings, including sinulations and real datasets, against recent state-of-the- art algorithms to show its superior performance and the ability to use one model in all settings.
1.1 Potential applications of FedDAG
Compared to traditional DAG learning methods, the homogeneous data (no distribution shift) setup of our method brings one more assumption that local data cannot be directly collected owing to the consideration of privacy leakage. Then, we further extend our model to heterogeneous data, where mechanisms among variables may also vary among different local data. Therefore, our method could be directly applied to the applications of DAG structure learning, where privacy is also very important.
The first example can come from medical science. Exploring the underlying relations among concerned events from healthcare data can help understand the disease mechanisms and causes (Yang al., 2013). However, in real medical scenarios, the clinical data of patients are extremely sensitive and related to personal privacy, which faces stringent data protection regulations, such as HIPAA regulations (Annas, 2003). Each hospital may own finite clinical data for some rare diseases, which is not enough for DAG learning. How can hospitals cooperate to analyze the pathology while preventing sharing the private information (raw diagnostic data)? Naturally, this challenge can be addressed by our method. Depending on how each hospital collects data, e.g.; medical devices and survey design, the data in each hospital may not share the same distribution. The second example can come from the recommendation system (RS) (Wang et al., 2020b; Yang et al., 2020). Leveraging BN model into RS is becoming prevail to perform robust recommendations by de-confounding some spurious relations. As users pay more atlention to privacy and governments also exacerbate many strict. regulations like the general data protection regulation (GDPR) (Voigt & Von dem Bussche, 2017), it increases difficulties in collecting raw personal data to the server. Accordingly, we think that RS can also benefit from Fe learning.
2 Preliminaries
Additive Noise Models (ANMs). We consider a specific structural equation model (SEM), which is defined as a tuple M = F), where X' = {X,, X2, , .xa) is set of concerned variables. And F f2..f2... ff] is a set of functions. Each f. called the relationship mechanism of X,, maps e, U PA, to X,, Le. X, = f((PA,,)) 6)); where the PA, corresponds to the set including all direct parents of X; and es is
3

---

Published in Transactions on Machine Learning Research (01/2023)
the random noise. M can be leveraged to describe how nature assigns values to variables of interest (Pearl et al., 2016). In this paper, we focus on commonly used model named ANMs. They assume that
X; = (PA.) + Es, i= 1,2, 1.2,....dd
(1)
where 6 is independent of variables in PA, and mutually independent with any Gj for i ド-
Bayesian Networks (BNs). Let X= (X1, X2,..., Xa) ) be a vector that includes all variables in X' with the index set == {1, 2, ............... .d. and P(X) with the probability density function p(X) be a marginal distribution induced from M. A DAG g (V, [E) consists of nodes set V and edge set E C V2. Every SEM M can be associated with a DAG GM, in which each node i corresponds to the variable X; and directed edges point from PA; to X; for e [d].. A BN is defined as a pair (M) Then GM is called the graph structure associated with MM and P(X) is Markovian to GM. Throughout the main text, we assume that there is no latent variable* (Spirtes et al., 2001) and then p(X) can be factorizod as
d
p(X)= = PX.
(2)
2=1
according to GM (Lauritzen, 1996). Xpo, is the parental vector that includes all variables in PA;
Characterizations of Acyclicity. A DAG with d nodes can be represented by binary adjacency matrix B = B..l [aa] with B. (0, 1)dd for Vi [d.. NOTEARS (Zheng et al., 2018) formulates sufficient and necessary condition for B representing a DAG by an equation. The formulation is as follows:
- 0,
where Tr|-] means the trace of a given matrix. e e, here, is the matrix exponential operation. However, NOTEARS is only designed to solve the linear Gaussian models, which assume that all relationship mechanisms are linear. Therefore, the DAG structure and relationship mechanisms can be modeled together by a weightod matrix. To extend NOTEARS to the non-linear cases, MCSL (Ng et al., 2022b) proposes use mask M, parameterized by a continuous proxy matrix U, to approximate the adjacency matrix B. To enforce the entries of M to approximate the binary form, i.e., or 1, a two-dimensional version of Gumbel-Softmax (Jang et al., 2017) approach named Gumbel-Sigmoid is designed to reparameterize U and to ensure the diffcrentiability of the model. Then, M can be obtained element-wisely by
1
Mij = 1 +
(4)
Ui + Gumb;))/7}'
where is the temperature, Gumby g/y oij, ghy and di are two independent samples from Gumbel(0, 1). For simplicity but equivalence, st, and 5 also can be sampled from -log())((a)) with Uniform(0, 1). See Appendix D in (Ng et al., 2022b). MCSL names Eq. (4) Gumbel-Sigmoid w.r.t. U and temperature т, which is written as (U). Then, the acyclicity constraint can be reformulated as
( -d= 0.
(5)
3 Problem definition
Here, first describe the property of decentralized data and the data distribution shift among different clients if there exists data heterogeneity (Huang et al., 2020b; Mooij et al., 2020; Zhang et al., 2020). Then, we define the problem, federated DAG structure learning, considered in this paper.
Decentralized data and probability distribution set. Let C = {c1, .2. includes m different clients and s be the only server. The data Do R. xd in which each observation
Cm) be the client set which
PIn the intact graph structure of ANMs, we just fix directed edges from e X, and assume the distribution of q. Therefore, in this paper, g is only defined over the endogenous variables. Foor simplicity, we use [d] = 2 , d} represent the set of all integers from d. 4This assumption can he relaxed to some restricted cases with latent variables. See Appendix C.3 for details.
4

---

Published in Transactions on Machine Learning Research (01/2023)
Dj for Vi E [naa] independently sampled from its corresponding probability distribution pa (X), represent the personalized data owned by the client ct. Bey is the number of observations in D The dataset. D = 1D9, ........, ,.m is called a decentralized dataset and pe (X) = (x)) ... p (X)} is defined as the decentralized probability distribution set. If Ph (X) = P (X) for l1, k2 E [ml, then D is defined as a homogeneous decentralized dataset throughout this paper. The heterogeneous recent dataset is defined by assuming that there exists at least two clients, e.g., Ck₁ and Ok2 on which the local data are sampled from different distributions, i.e., pa,, (X) + perz (X).
Assumption 3.1. (Invariant DAG) For Vok, Pn* (X) (X) admits the product factorization of Eq. (2) relative to the same DAG g.
Remark 3.2. Tf pC (X) satisfies Assumption 3.1, then, each pox (X) E (x) is Markovian relative to g.
According to the general definition of mechanisms change in (Tian & Pearl, 2001), interventions can be seen as a special case of distribution shifts, where the external influence involves fixing certain variables to some prodetermined values. Actually, in general, the external influence may be milder to merely change the conditional probability of certain variables given its causes. In this paper, we restrict our scope by assuming that the distribution shifts across po (X) come from the changes of mechanisms in F distribution shifts of the exogenous variables in & (scc Appendix F.1 for detailed discussion). More justifications Assumption 3.1 are in Appendix F.2.
Assumption 3.3. For y if pct, (X) f pekz (X), the distribution shifts are caused by (1) 3 E [d], pa,, (X.))pa.)) # pes (X,) ); ie., f # S4 2k2
(2) B [d], pen (ei) & pe (E:).
Federated DAG Structure Learning. Given the decentralized dataset D consisting of data from m clients while the corresponding (X) satisfies Assumptions 3.1 and 3.3, federated DAG structure learning aims to identify the underlying DAG G from D.
4 Methodology
To solve the federated DAG structure learning problem, we formulate a continuous score-based method named FedDAG to learn the DAG structure from decentralized data. Firstly, we define an objective function that guides all models from different clients to federally learn the underlying DAG structure G (or adjacency matrix B), and at the same time also to learn personalized mechanisms for each client. As shown in Figure 2, for each client Ck. the local model consists of a graph learning part and a mechanisms approximation part. The GSL part is parameterized by matrix U E Raxd which would be the same for all clients finally". To make every entry of U to approximate the binary entry of the adjacency matrix, Gumbel-Sigmoid method (Jang et al., 2017; Ng et al., 2022b), represented U to a differentiable approximation of the adjacency matrix. The mechanisms approximation parts 1 ... f are parameterized by d sub-networks, each of which has d inputs and one output. Tn the learning procodure, the GSL parts (spocifically U**) of participating clients are shared with the server s. Then, the processed information is broadcast to each client for self-updating its matrix. The details of our method are demonstrated in the following subsections.
gr (U*), is further leveraged to transform
4.1
The overall learning objective
Now we present the overall learning objective of FedDAG as the following optimization problem:
Σ Sht (D* (** "0, U)
arg max &.U
(6)
1=1
subject to (U) E DAGs + h(U) = (r(ela-(U))) 0,
where 4h : ( $
T represents the MA part of the model on G-- S*x(.) is the scoring function for evaluating the fitness of the local model of client es and observations Do= For score-based DAG structure
Splease notice that GSL parts of different clients may not be the same during the training procedure. So we index them.
5

---

Published in Transactions on Machine Learning Research (01/2023)
Client C2
Client C2
Client Gyn
84
8cm
MA Part
Φ9
OGL. Part.
V
V
V
DAG-Stared Stared Module
V
V
Refing
m.)()
V
a.6
V
M.O
U
Um
X
X
X
Server
Figure 2: An overview of FedDAG. Each solid-line box includes the local model for each client. For client Ck the GSL part includes a continuous proxy U and gr),,, the Sumbel-Sigmoll function, which maps U to approximate the binary adjacency matrix. To approximate the mechanisms, the MA part uses $* including d neural networks. X represents observations on C and 8 is the predicted data. X firstly goes through the GSL part to select the parental variables and then the MA part to get X The server coordinates the FL procedures by leveraging U among clients.
learning, selecting a proper score function such as BIC score (Schwarz, 1978), generalized score function (Huang et al., 2018) or equivalently taking the likelihood of P(X) with a penalty function on model parameters (Zheng et al., 2018; Ng et al., 2022b; Zheng et al., 2020; Lachapelle et al., 2020) can guarantee to identify up the underlying ground-truth graph structure 9 because 9 supposed to have the maximal score over Eq. (6). Throughout all experiments in this paper, we assume the noise types are Gaussian with equal variance for each local distribution. And the overall score function utilized in this paper as follows,
nhA
d
8th (D*, th U
D
$5t 55 (0-(())))))
D Allg-
(7)
2nk
In our score function, we take the negative Least Squares loss and a sparsity term, which corresponds to the model complexity penalty in the BIC score (Schwarz, 1978). However, the global minimum is hard to reach by using the gradient descent method due to the non-convexity h(U). More details on discussions of the optimization results can found Appendix. C.
In this paper, instead of directly taking the likelihood of P(X), leverage the well-known results the density transformation to model the distribution of P(E), i.c., maximizing the likelihood pou (E Fot ,)) for Vea C (Mooij et al., 2011). According to Eq. (1), have = X; f(PA.)). That is to say, modeling P(E) can be achieved by an auto-regressive model. To get 6,, the first step is to select the parental set PA, for X, This can be realized by B(; i] X, where means the element-wise product. In our paper, for client Ck we predict the noise by E; = X, ( X); where (U) is to approximate B and P.(-) is parameterized by a neural net work to approximate ft. The specific formulation S would depend on the assumption of noise distributions.
oThe consistency of BIC for learning graphs ANMs discussed in Appendix C.5.

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 1 FedDAG
Input: D, C, Parameter-list {Aiinit Pinits htol, itaax Pmazs B, 7, r
2: Output: (U,(),) D,
3: # #Parameter Initializing
4: t ++ 1, Og + Cinits Pt. 5- Pinit
5: while S itmaz and h(U)) 2 heot and p S Pmaz do
#Sub-problen Solving
U1+1, Pe+1 + SPS(D, C, On, Pr, ilin r))
#Coefficients Updating
a++1 + 04 (+,+(((U ++
10:
if E( > (U,)( then
11:
P++1 = 3pt
12: else
13: Pt+1 = Pt
14: end if
15:
end while
4.2 Federated DAG structure learning
As suggested in NOTEARS (Zheng et al., 2018), the hard-constraint optimization problem in Eq- (6) can be addressed by an Augmented Lagrangian Method (ALM) to get an approximate solution. Similar to the penalty methods, ALM transforms a constrained optimization problem by a series of unconstrained sub-problems and adds a penalty term to the objective function. ALM also introduces Lagrangian multiplier term to avoid ill-conditioning by preventing the coefficient of the penalty term from going too large. To solve Eq. (6), the sub-problem can be written as
arg max $.U
S (Dot, th -
- on,((U)) P n(U)²
(8)
where a, and P. are the Lagrangian multiplier and penalty parameter of the t-th sub-problem, respectively. These parameters are updated after the sub-problem is solved. Since neural networks are adopted to fit the mechanisms in our work, there is closod-form solution for Eq. (8). Thercfore, we solve it approximately via ADAM (Kingma& & Ba, 2015). The method is described in Algorithms and 2. And in Algorithm 1, we share the same coefficients updating strategy as in (Ng et al., 2022b).
Each sub-problem as Eq. (8) is solved mainly by distributing the computation across all local clients. Since data is prevented from sharing among clients and the server, each client owns its personalized model, which is only trained on its personalized data. The server communicates with clients by exchanging the parameters information of models and coordinates the joint learning task. To achieve so, our method alternately updates the server and clients in each communicatin round.
Client Update. For each model of client Ck2 there are two main parts, named GSL part parameterized by U and MA part parameterized by oe,, respectively. Essentially, the joint objective in Eq. (8) guides the learning process. In the self-updating procedure as described in Algorithm 2, the clients firstly receive the updated penalty coefficients 04 and Pt and the averaged parameter Unew- Then, the renewed learning personalized score of client Gg is defined as SPa = S ()T+ Pt h(Uo)) it times of local gradicnt-based parameter updates are operated maximize its personalized score.
Server Update. After ÿ local updates, the server randomly chooses clients to collect their Us to the set U. Then, Us in U are averaged to get Unew- The other operation on the server is updating the a,, to 04++1 Pt+1- The detailed calculating rules are described at lines 8 - 14 in Algorithm 1. Then, the new penalty coefficients and parameters are broadcast to all clients. Notice that assuming that data distribution across clients is homogencous (no distribution shift), th of the chosen r clients can also be collected and averagod to update the local models of clients in the same way, which is named as All-Shared FedDAG (AS-FodDAG) in this paper. For clarity, name our general method as Graph-Shared (GS-FedDAG) to distinguish it from
7

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm Sub-Problem Solver (SPS) for FedDAG
Input: D, C, Parameter-list {are Pt, ilinn ft, r)
Output: Unew, Ti
Define SP 8 ach(UCC)) h(U
4: for in (1, ilsn) do
5: for each client c do
6:
#Self-updating
7: U D' + arg magmax4..co Sp
end for
if (% it = or in then
10:
# Aggregating: randomly select r clients and collect their Us into U, then, send U to the server U + Agg(r, C)
11:
12:
#Server Updating: average U JEl U
13:
Unew + Avg(U)
14:
# Broadcasting: distribute Unew to all clients
15:
C+ BD(Unew)
16:
for cach client C do
17:
#Clients Updating
18:
USa Unew
19: end for
20: end if
21:
end for
AS-Fed It is worth noting that AS-FedDAG can further enhance the performance in the homogeneous case but introduce some additional communication costs.
4.3 Thresholding
For continuous optimization, as illustrated in the previous work (Ng et al., 2022b), we leverage Gunbel- Sigmoid to approximate the binary mask. That is to say, the exact or 1 is hard to get. The other issue is raised by ALM since the solution of ALM only satisfies the numerical precision of the constraint. This is because we hot and itmaz maximally but not infinite coefficients of penalty terms formulate the last sub-problem. Therefore, some entries of the output. M WEg (U) will be near but not exactly 0 1. To alleviate this issue, l sparsity is added to the objective function. In method, since all mask values are in j0, 1], we take the median value 0.5 as the threshold to prune the edges, which follows the same way in our baseline method MCSL (Ng et al., 2022b). The ilerative thresholding method is also taken to deal with the case that the learned graph is cyclic. This may happen if the number of variables large (40 variables in our paper). Because, in nunerical optimization, the constraint penalty exponentially decreases with the number of variables. To deal with the cyclic graph, we one-by-one cut the edge with the minimum value until the graph is acyelic. Until now, all continuous search methods for DAG learning suffer from these two problems. It is an interesting future direction to be investigated.
4.4 Convergence analysis
Let us quickly review our method, For each client the model parameters include th and U% Each client optimizes its parameters on its own data D Like NOTEARS and its following works, our method can reach a stationary point instead of the global maximum (the ground-truth DAG). Then, we separate our discussion into homogeneous and heterogeneous data.
4.4.1 Homogeneous data
For the no distribution shift case, we have . T cm and U th Umm Our method named AS-FedDAG (All-Shared FedDAG) sets a central server, which regularly (1) receives all parameters

---

Published in Transactions on Machine Learning Research (01/2023)
(or U for GS-FedDAG), (2) averages these parameters to get &new and U and (3) broadcasts H and Unew to all clients during the learning procedures. AS-FedDAG benefits from an advanced technique named FedAvg (McMahan et al., 2017) for solving the FL problem in the homogeneous data case. FedAvg solves a similar problem by averaging all parameters learned from each client in the learning process.
4.4.2 Heterogeneous data
To solve the overall constraint-based problem, we take ALM to convert the hard constraint to soft constraint. with a series of increasing penalty co-efficiencies. The convergence of ALM for the non-convex problem has been well studied (Nemirovski, 1999) and presented in NOTEARS (Zheng et al., 2018). Thus, we only consider the convergence analysis of our method directly from the inner optimization, ie., the f-th sub-problem, as follows.
arg max 4
Shh (D th ,0. (U)) - unh(UU) Pt h(U)))
2
(9)
Here, for simplification, we just define that S (# U) - (D (e, Then, the overall optimization problem be reformulated as follows.
(U)) + anh(U) + h
m
arg min S(U, 1) 4.U
Σ
STx (U, o%).
(10)
Through the following part, we use Vu and V to represent the gradients of S(U, b) w.r.t U and Th respectively. And, we use Vo and V to represent the stochastic gradients calculated by a mini-batch of observations w.rtt U and rnt, respectively. Definition 4.1. (Partial Gradient Diversity). The gradient diversity among all local learning objectives as:
m
Sex (U,
VUS(U, 2) -
5082.
(11)
Note that the notation of gradient diversity is introduced (Yin et al., 2018; Haddadpour & Mahdavi, 2019) measurement to compute the similarity among gradients updated different clients.
A sssumptio 4.2. (Smoothness and Lower Bound). The local objective function (*) of the k-th client is differentiable for Vk E [m]. Also, S (U, ) is Ta--Tipshitt w.r.t U and Tuo w.r.t 4h, and S (U, 4 is La-Lipse Læ-Lipschizz w.r.t dea and Lœu w.r.t U. We also assume the overall objective function S-.
can be bounded by constant S* and denote AS,- = S(U,, -
The relative cross-sensitivity of Vuse w.r.t oc and S w.r.t U with the scalar
x max (Lu LaU) LLyla.
(12)
Assumption 4.3. (Bounded Local Variance) For each local data D k E [m], we can independently sample batch of data denoted as & c D Then, there exist constant du and óz such that
E
Vo Sex ($.
(
Vus $
E
Ve sh U) V (U, (U,
)
o
The bounded variance assumption is a standard assumption on the stochastic gradients (Haddadpour & Mahdavi, 2019; Pillutla et al., 2022).
Theorem 4.4. (Convergence of GS FeSDFeDAA).. For GS-FedDAG with all clients involved in the aggregation, for YO < < 1, under Assumptions 4.2, 4.9 and 4.1, and the learning rate for the U part set as (Lyitt)))) and the learning rate for the o port set as n/ (L) Then, for n, depending on the problem paramelers, we have
9

---

Published in Transactions on Machine Learning Research (01/2023)
112
Lu T
R.
V
Sa
Un:)
E
V
S
(
Un)
L
m
(13)
(AS 1222
(AS FodDAG,2
2//3
+ 0 (
VT
T2/3
where define the effective variance terms
T + 03
o 1 = -1 x1)
Tu
L
(14)
2
(
d PoDDAG,2 = -1+ x2)
+
LU
LU
L
itin
where ilin is the total slep of one inner loop used lines
in Algorithm 2.
From Theorem 4.4, we can see that the gradients So ( Us)) w.r.t U and Vus ( Un) w.r.t $ at the 1-th step can be bounded if we choose a proper 7, which affects the learning rates of the model.
The proof Theorem 4.4 can be borrowed from the proof of Theorem in (Pillutla et al., 2022). Notice that, in our theorem, we have assumed that all clients participate in the aggregation for simplification and the conclusion can be easily extended to the general partial participation case.
4.5 Privacy and costs discussion
Privacy issues of FedDAG. The strongest motivation of FL is to avoid personalized raw data leakage. To achieve this, FedDAG proposes lo exchange the parameters for modeling the graph. Here, we argue that the information leakage of local data rather limited. The server, receiving parameters with client index, may infer some data property. However, according the data generation model (1), the distribution of local data is decided by (1) DAG structure, (2) noise types/strengths,, and (3) mechanisms. The gradient information of the shared matrix is decided by (1) the learning objective and (2) model architecture, which are agnosticc to the server. Especially for the network part, clients may choose different networks to make the inference more complex. Moreover, suppose the graph structure is also private information for clients. In that case, this problem can be easily solved by selecting a client to serve as the proxy server". The proxy server needs play two roles, including training own model and taking on the server's dutios. Then, other clients communicate with the proxy server instead of real server in the communication round. Moreover, the aim of our work, and federated learning in general, is not to provide full solution to privacy protection. Instead, it is the first step towards this goal, i.e, data sharing between clients. To further protect privacy, more constraints need to be added to the federated lcarning framework, such as the prevention of information leakage from gradient sharing, which are studied under the privacy umbrella. To further enhance privacy protection, our method can also include more advanced privacy protection techniques (Wei et al., 2020b), which would be an interesting work be investigated.
Communication cost.. Since FedDAG requires exchanging parameters between the server and clients. Additional communication costs raised. In our method, however, argue that GS-FedDAG only brings rather small additional communication pressures. For the case of d variables, single communication only exchanges a d x d matrix twice (sending and receiving). For homogeneous data, which assumes that local data are sampled from the same distribution, one can also transmit the neural network together to further improve the performance since mechanisms are also shared among clients. The trade-off between performances and communication costs can also be controlled by r in Algorithm 2, i.e., enlarging or reducing r. Surprisingly, we find that reducing r does not harm the performance severely (see Table 17 in Appendix for detailed results). Morcover, the partial communication method, which only chooses information, is also leveraged to address the issue that not all clients are always online at the same time.
clients to exchange training
Notice that the DAG structure encoded the data not secret for the data owners (clients).
10

---

Published in Transactions on Machine Learning Research (01/2023)
5 Experimental Results
In this section, we study the empirical performances of FedDAG on both synthetic and real-world data. More detailed ablation experiments can also be found in Appendix D.
Baselines We compare our method with varions baselines including some continuous search methods, named NOTEARS (Zheng et al., 2018), NOTEARS-MLP (N-S-MLP, for short) (Zheng et al., 2020), DAG-GNN (Yu et al., 2019) and MCSL (Ng et al., 2022b), and also Iwo traditional combinatorial search methods named PC (Spirtes et al., 2001) and GES (Chickering, 2002). The comparison results with another method named causal additive models (CAM) (Bühlmann et al., 2014) are put in Appendix D.5. Furthermore, include a concurrent work named NOTEARS-ADMA, (Ng & Zhang, 2022), which also considers learning the Bayesian network in the federated setup. Since NOTEARS-ADE case and linear settings and pays less attention to the nonlinear cases, we only include the results on linear cases of NOTEARS-ADMM, in the main paper for fair comparisons. More detailed comparisons are shown in Appendix D.6. Moreover, we also compare our FedDAG with a voting method (Na & Yang, 2010) in Appendix D.4, which also tries to learn DAG from decentralized data. We provide two training ways for these compared methods. The first way named 'All data" is using all data to train only one model, which, however, is not permitted in FedDAG since the ban of data sharing in our setting. For the homogeneous data case, the results on this setting can be an approzimate upper bound of our method but unobtainable. The second one named 'Separated data' is separately training each siloed model over its personalized data, of which the performances reported are the average results of all clients.
also
focuses more on the homogeneous
Mctrics. We report two metrics named Structural Hamming Distance (SHD) and True Positive Rate (TPR) averaged over 10 random repetitions to evaluate the discrepancies between estimated DAG and the ground-truth graph G. See more details about SHD, and TPR in Appendíx B.3. Notice that PC and GES can only reach the completed partially DAG (CPDAG, or MEC) at most, which shares the same Skeleton with the ground-truth DAG G. When we evaluate SHD, we just ignore the direction of undirected edges learned by PC and GES. That is to say, these two methods can get SHD 0 if they can identify the CPDAG. The implementation details of all methods are given in Appendix B.
5.1 Synthetic data
The synthetic data we consider here is generated from Gaussian ANMs (Model (1)). Two random graph models named Erdös-Rényi (ER) and Scale-Free (SF) (detailed definitions are shown in Appendix B.1.) are adopted to generate the graph structure G. And then, for each node V22 corresponding to X, in G, we sample a function from the given function sets to simulate fi. Finally, data are generated according to a specific sampling method. In the following experiments, we take 10 clients and each with 600 observations (unless otherwise specified in some ablation studies.) throughout this paper. According to Assumption 3.1, data across all clients share the same DAG structure for both homogeneous and heterogeneous data settings. Due to the space limit, more ablation experiments, such as unevenly distributed observations, varying clients, dense graph, different non-linear functions, and different number of observations, etc., are put in Appendix D. All detailed discussions on the experimental results are in Appendix E.
5.1.1 Homogeneous data setting
Results on linear models. For a fair comparison, here, we also provide the linear version of our method. Since lincar data are parameterized with an adjacency matrix, we can dircctly take the adjacency matrix as our model instead of a GSL part and a MA part. During training, the matrix is communicated and averaged by the server to coordinate the joint learning procedures.
NOTEARS-ADMA is also a DAG structure learning method from decentralized data. Different from our averaging stralegy lo exchange training information among clients, the optimization problem is solved by the alternating direction method of multipliers (ADMM). From Table 1, we find that our method can consistently show its advantage in the lincar case. In the ER2 with 10 nodes sctting, our AS-FodDAG even better than NOTEARS with all training data. While it is possible and the detailed explanation can be found in A Appendix E.
11

---

Published in Transactions on Machine Learning Research (01/2023)
Table 1: Results on the linear model (Homogeneous data).
ER2 with 10 nodes
SF2 with 10 nodes
ER2 with 20 nodes
SF2 with 20 nodes
SHD
TPR f
SHD 4
TPR
SHD 4
TPR f
SHD
TPR
PC-All
9.0
0.14
1.3
0.07
1.9
0.19
22.3 1.8
0.48 = 0.08
GES-AII
7.5=10.1
0.22
4.1
0.80
25.2
0.16
22.1+
0.14
NOTEARS-AII
1.6116
0.93
1.1
0.921 0.05
2.0=277
0.94 0.06
6.94 7.0
0.86 0.12
SOTEARS-Sep
2.0
0.85
3.642.1
0.13
41424
1.92 0.00
0.10
ROTEARS-ADMI
4.7 8.9
0.89 0.12
4.4++3.0
0.86 + 0.09
5.9
0.007
10.7
0.82 0.08
AS-FodDAG
1.3 1 1.5 0.04
1.6
0.91 1: 0.06
3.9
0.01
9.4 = 6.7
0.82 0.12
Table 2: Results on the nonlinear ANM with GP (Homogeneous data).
ER2 with 10 nodes
SF2 with 10 nodes
ER2 with 40 nodes
SF2 with 40 nodes
SHD
TPR f
SHD
TPR f
SHD 4
TPR f
SHD
TPR.
PC
0.37 2.6
4.31
0.24
84.9 13.4
0.40 0.08
95.0 10.4
0.36
AlI data
GES
1.9
0.18
9.6
0.17
9.8
0.53 0.08
73.8 11.9
0.17:00.10
NOTEARS
16.5220..
0.01
14.51:11
0.09
7.22
0.08 0.03
7.
0.07 0.00
N-S-MLP
8.1
0.56
0.17
8.3428
0.51 0.16
4..3+
0.43 0.08
49.2
0.39 0.09
DAG-GNN
16.2422.
0.07
0.06
05:2++0.8
0.05
7.7
0.06 0.03
1.64
0.05
MCSL
1.5
0.90 0.08
1.6 1.2
0.91 0.07
25.4 19.1
0.68 0.14
31.6 10.0
0.59 0.19
PC
14.1
0.06
13.6
0.10
8.
0.211.0000
86.1
0.20
Sep data
GES
12.7
0.07
12.7
0:33 0.11
6.7
0:29 0.03
73.2
0.29 0:29
NOTEARS
16.5+2.00
0.04
14.6+10
0.09
7.31
0.08
70.7
0.003
N-S-MLP
8.5
0.13
8.7
0.53 145+10
6.9
0.41 0.06
5.5
0.39
DAG-GNN
15.7+22.3
0.01
0.10
7.55
0.02
1.8
0.002
MCSL,
7.14
0.83+0.00 0.08
6.9
0.84 0.08
77.3+
0.64
72.9 16.4
0.58 + 0.13
GS FedDAG
2.4+2.0
0.86
2.7 0.13
0.86 + 0.13
36.5
0.65 0.15
46.4
0.57 0.57 0.13
AS FedDAG
1.8
0.89
0.12
2.77
0.85 + 0.15
30.0 12.3
0.74 0.15
31.5 10.0
0.13
Results on the nonlinear model. For the nonlinear setting, all data are generated by an ANM and divided into 10 pieces. Each fi is sampled from Gaussian Process (GP) with RBF kernel of bandwidth one (See Table 14 and Table 15 in Appendix. D for results of other functions.) and noises are sampled from one zero-mean Gaussian distribution with fixed variance. We consider graphs of d nodes and 2d expected edges.
Experimental results are reported in Table 2 with nodes 10 and 40. Since all local data are homogencous, here, we also provide another effective training method named AS-FedDAG, in which the MA parts are also shared among clients. In all settings, AS-FedDAG shows a better performance than GS-FedDAG because more model information is shared during training. While GS-FedDAG can also show a consistent advantage over other methods. When separately training local models, all models suffer from data scarcity. Therefore, we can observe that both GS-FedDAG and AS-FedDAG perform better than the other methods in the fashion of separate training. NOTEARS and DAG-GNN, continuous search methods, obtain unsatisfactory results due to the weak model capacity and improper model assumption. In contrast, the BIC score of GES gets a linear-Gaussian likelihood, which is incapable to deal with non-linear dataa. With the number of nodes increasing, GS-FedDAG still shows better results than the closely-related baseline method MCSL. However, NOTEAES-MLP can show a comparable result with GS-FedDAG owing to the advantage over MCSL.
Here, we give a more detailed explanation of why our FedDAG method performs better than the baseline methods. For PC and GES, they can only reach the CPDAG (or MEC) at most, which shares the same skeleton with the ground-truth DAG. When we evaluate the SHD, we just ignore the direction of undirected edges learned by PC and GES. That is to say, these two methods can get SHD O if they can identify the true CPDAG. Therefore, the final results are not caused by unfair comparison. For PC, the independence test is leveraged to decode the (conditional) independence from the data distribution. Therefore, the accuracy would be affected by (1) the number of observations and (2) the effectiveness of the non-parumelric kernel independence test method. GES leverages greedy search with BIC score. However, the likelihood part of BIC in GES is Linear Gaussian, which is unsuitable for data generated by the Non-lincar model. NOTEARS
8 &llease find the ablation experiment with linear data and more discussions the experimental results in Appendix D.
12

---

Published in Transactions on Machine Learning Research (01/2023)
is a linear model but the mechanisms non-linear. The reason will be the unfitness between data and model. Therefore, the comparisons with GES and NOTEARS on linear homogeneous data are implemented in the Table 1. DAG-GNN is also a non-linear model. However, the non-linear assumption of DAG-GNN is not the same as the data generation model ANMs assumed in our paper. The second reason comes from its mechanisms opprozimation modules are compulsory to share some parameters. Both NOTEARS-MIA and MCSL have their advantages. Please refer to Tables 14 and 15, you will find that NOTEARS-MLP performs better when the non-linear functions are MIM and MLP while MCSL works better on GP and GP-add models.
Visualization of the learned DAG of FedDAG. We take an example of the AS-FedDAG optimization process on linear Gaussian model with NOTEARS as the baseline method and plot the change of estimated parameters in Fig. and Fig. 4. In this example, the number of nodes is set as 10 and the edges are 10. The data is simulated by ER graph and evenly assign observations on two different clients. In Fig. 3, we can see that the learned graph is asymptotically approximating the ground-truth DAG Bg, including the existence of edges and their weights. From Fig. 4, we can find that with the increase of the penalty coefficients, hosse decreases quickly. For learned graphs on the diffferent clients, can see that the SHD distance is smaller during the optimization procedures.
300
8 900
B 3000
B 9000
8
5-
5
18
18
15
18
10
15
5
10
15
5
10
15
10
15
10
15
10
Figure 3: Visualization of the learned graph during the optimization process. B n mcans the learned graph in the n steps. Best the final estimated DAG. Bg is the ground-truth DAG.
16
1500
SHD distance
0.4
abs distomec
0.06
9. 100
1000
loxs
0.04
2
0.2
10a
0.0
2
3
4
2
3
6
6
10000
20000
10000 20000
Slep
Step
Figure Parameters changing during the optimization process. The first three sub-figures include the changes of penally coefficients P, a, and the DAG constraint loss hoss. The fourth sub-figure records the é distance between two learned graphs the different clients. The fifth oub-figure records the SHD distance between two learned graphs on the different clients.
5.1.2 Heterogeneous data setting
As defined in Section 3, the heterogeneous data property of data across clients come from the changes mechanisms or the shift of noise distributions. To simulate the heterogencous data, we first generate a graph structure shared by all clients and then decide the types of mechanisms f and noises e, for i [d] for each client Ck. In experiments, for here is a weighted adjacency matrix with coefficients sampled from Uniform ([-2.0. - -0.5] 5] U [0.5, 2.0)), with equal probability. If being non-linear, f.at is independently sampled from GP, GP-add, MLP, or MIM functions (Yuan, 2011), randomly. Then, fixed zero-mean Gaussian noise is set to each client. with a randomly sampled variance from {0.8, 1}.
allow that f can be linear or non-linear for each client. If being linear,
We can see that the conclusion of experimental results on the heterogencous data setting is rather similar that of the homogeneous data. As can be read from Table 3, GS-FedDAG always shows the best performances
13

---

Published in Transactions on Machine Learning Research (01/2023)
Table Results on ANMs with heterogeneous data.
ER2 with 10 nodes
SF2 with 10 nodes
ER2 with 40 nodes
SF2 with 40 nodes
SHD
TPR
SHD
TPR
SHD
TPR
SHD
TPR
PC
22.3
0.11
3.0
0.11
15L9 14.2
0.27
152.5 5.4
0.26
GES
6.2
0.14
2.6
0.14
NaN
NaN
NaN
NaN 0.10
All diatit
NOTEARS
20.14:11
0.19
38.7
0.15
1618
0.39 0.07
178.1 33.0
N.S-MLP
5.0
0.87 0.07
2.37+333
0.88 + 0.07
344.4 71.9
0.32 0.08
$25.0 50.2
0.85 + 0.08
DAG-GNN
2.
0.19
16.6+:3.0
0.18
44.66+44..6
0.29 0.088
168.2 = 34.2
0.31 0.09
MCSL
4.44
0.75
1.00
0.81
118.6 18.1
0.08 0.11
126.9 = 16.5
0.59 0.112
PC
125
0.05
11.02.11
0.09
65.7 110
0.43 0.06
73.7
0,36 0.00
GES
1.
0.08
10.3
0.00
68.2 20.8
0.65 0.09
77.2 13.8
0.60 0.07
Sep data
NOTEARS
7.6
0.60
1.6
0.09
34.9
0.63 0.11
4.44
0.110
N-S-MLP
1.2
0.85
6.1
0.76
46.0 10.2
0.73 0.08
56.0
0.66 0.09
DAG-GNN
2.2
0.12
8.1
0.67 0.09
15.7
0.11
52.7 8.4
0.11
MCSL
9.2
0.06
8.0
0.71
76.1
0.53 0.09
78.1 6.3
0.47
AS FeIDAG FeIFe
3.4
0.97 0.04
2.7 1.6
0.90
35.9 17.0
0.84 +: 0.09
41.8 12.6
0.73 0.007
1.9++..6
0.99 + 0.02
2.6++1.3
0.93 + 0.07
24.3 + 10.2
0.86 0.09
33.9 10.9
0.73 0.09
across all settings. If taking all data together train one model using other methods, we can see that data heterogencity would put great trouble to all compared methods while GS-FedDAG plays pretty well. Here, also provide the experimental results of AS-FedDAG on this setting. We can find that the model misspecification problem would lead to unsatisfactory results, which motivate us to design the GS- Aed Moreover, GS- -SS-FeDAAG shows consistently good results with different numbers of observations on each client (see Table 16). NOTEARS takes sccond place at the sctting of 40 nodes because there are some linear data among clients, which also the reason that GS-FedDAG shows lower SHDs on helerogeneous data Table than Table 2. Compared with non-linear models, NOTEARS easily fits well with even fewer linear data.
5.2 Real data
We consider real public dataset named fMRI Hippocampus (Poldrack et al., 2015) to discover the underlying relationships among six brain regions. This dataset records signals from six separate brain regions in the resting state of one person in 84 successive days and the anatomical structure provide 7 edges as the ground truth graph (soe Figure 10 days, which can be regarded as different local data. It worth noting that though this data does not have real data privacy problem, in Table 4 we show part of the experimental results while others lie in Table 18). AS-FedDAG shows the best performance on all criteria while GS-FedDAG also performs better than most of the other methods.
(Appendix D). Herein, we separately select 500 records in each of the
use this dataset to evaluate the learning accuracy of our method. Here,
Table 4: Empirical results on fMRI Hippocampus dataset (Part 1)-
All data
Separate data
GS-FedDAG
AS-FeIDAG
PC
NOTEARS
MCSL
PC
NOTEARS
MCSL
SHD 4
9.0
5.0 0.0
9.0
8.7 1.3
8.0 1.9
8.3 1.7
6.4
5.0 0.0
NNZ
11.0=0.0
4.0
12.0+0.6
7.6
5.4=155
9.0
6.8
5.0
TPR
0.43
1.000
0.44
0.26
10.18
0.35 0..15
0.27
0.29 0.00
FDR
0.73
0.50 0.00
0.74 0.03
0.76
0.78
0.13
0.72+
0.60 0.00
6 Related work
Two mains, named constraint-based and score-based methods, push the development of DAG struc- ture learning. ceastraint-based methods, including SGS and PC (Spirtes et al., 2001), take conditional independence constraints induced from the observed distribution to decide the graph skeleton and part of the directions. Another branch of methods (Chickering, 2002) define score function, which evaluates the fitness between the distribution and graph, and identifies the graph with the highest score after searching
14

---

Published in Transactions on Machine Learning Research (01/2023)
the DAG space. To avoid solving the combinatorial optimization problem, NOTEARS (Zheng et al., 2018) introduces an equivalent acyclicity constraint and formulates a fully continuous optimization for searching the graph. Following this work, many works leverages this constraint to non-linear case (Ng et al., 2019; Zheng et al., 2020; Lachapelle et al., 2020; Zhu et al., 2020; Wang et al., 2021; Gao ct al., 2021; Ng et al., 2022b), low-rank graph (Fang et al., 2020), interventional data (Brouillard et al., 2020; Ke al., 2019; Scherrer et al., 2021), time-scries data (Pamfil et al., 2020), incomplete data (Gao et al., 2022; Geffner al., 2022) and ummeasured confounding (Bhattacharya et al., 2021). GOLEM (Ng et al., 2020) leverages the full likelihood and soft constraint to solve the optimization problem. Ng et al. (2022a), DAG-NoCurl (Yu et al., 2021) and NOFEARS (Wei et al., 2020a) focus on the optimization aspect.
The second line of related work is on the Overlapping Datasets (OD) (Danks et al., 2009; Tillman & Spirtes, 2011; Triantafillou & Tsamardinos, 2015; Huang et al., 2020a) problem in DAG structure learning. However, OD assumes that each dataset owns observations of partial variables and targets learning the integrated DAG from multiple datascts. In these works, data from different sites need to be collected on a central server.
The last line is federated learning (Yang et al, 2019; Kairouz et al., 2021), which provides the joint training paradigm to learn from decentralized data while avoiding sharing raw data during the learning process. FedAvg (McMahan et al., 2017) first formulates and names federated learning. FedProx (Li et al., 2020) studies the heterogeneous case and provides the convergence analysis results. SCAFFOLD leverages variance reduction by correcting client-shift to enhance training efficiency. Besides these fundamental problems in FL itself, this novel learning way has been widely co-operated with or applied to many real-world tasks such as healthcare (Sheller al., 2020), recommendation system (Yang et al., 2020), and smart transport (Samarakoon et al., 2019).
6.1 Concurrent work (NOTEARS-ADMM)
In NOTEARS-ADMM (Ng & Zhang, 2022), the authors also consider the same setting for discovering the underlying relations from distributed data owing to privacy and security concerns. The main advantage of our FedDAG over KOTEARS-ADMM is to handle heterogeneous data, which is very common in real applications. Then, NOTEARS-ADMI object with our method. Instead of taking an average to share training information, ADMM is taken to make the adjaconey matrix close. More detailed experimental comparisons can be found in Appendix D.6, from which we can see that our FedDAG performs better in most settings.
mainly considers the linear case, which shares the same learning
7 Conclusion and Discussions
Learning the underlying DAG structure from decentralized data brings considerable challenges to traditional DAG learning methods. In this context, we have introduced one of the first federated DAG structure learning methods called FedDAG, which uses two-level structure for each local model. During the lcarning procedure, each client tries to learn an adjacency matrix to approximate the graph structure and neural networks to approximate the mechanisms. The matrix parts of some participating clients are aggregated and processed by the server and then broadcast to each client for updating its personalized matrix. The overall problem is formulated as a continuous optimization problem and solved by gradient descent. Structural identifiability conditions are provided, and extensive experiments on various data sets are to show the effectiveness of our FedDAG.
The first limitation of our framework is with the no latent variable assumption, which is seldom right in real scenarios. While, a general framework, the advanced methods (Bhattacharya et al., 2021), which handle the no observed confounder casc, can be well incorporated with our method to deal with the federated setup (More details can be seen in Appendix C.3). Another limitation relies on privacy protection. As we said, we focus on the statistical and optimization perspectives of federated DAG structure learning and leave the problem of combining the advanced privacy protection methods (Wei al., 2020b) into our framework as a future work. The last limitation is to loose the invariant DAG assumption and allow the causal graph change among different clients, which is more common in the real world.
15

---

Published in Transactions on Machine Learning Research (01/2023)
Acknowledgement
LS is supported by the Major Science and Technology Innovation 2030 "Brain Science and Brain-like Research" key project (No. 20212D0201405) EG is supported by an Australian Government Research Training Program (RTP) Scholarship. This research was supported by The University of Melbourne's 's Research Computing Services and the Petascale Campus Initiative. This research was undertaken using the LIEF HPC-GPGPU Facility hosted the University of Melbourne. This Facility was established with the assistance of LIEF Grant LE110000000 TL was partially supported by Australian Research Council Projects DP180103424, DE- 19-1901,,,73, IC-190100031, DP- APP220100121, and FT-220100318. MG was supported by ARC DE210101624. HB was supported by ARC FT1 901 00374.
16

---

Published in Transactions on Machine Learning Research (01/2023)
References
George J Annas. Hipaa regulations: new era of medical-record privacy? New England Journal of Medicine, 348:1486, 2003.
Bryon Aragam, Arash Amini, and Qing Zhou, Globally optimal score-based learning of directed acyclic graphs in high-dimensions. In Advances in Neural Information Processing Systems, volume 32, 2019.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. aiv preprint arXio:1907.02899 2019.
Rohit Bhattacharya, Tushar Nagarajan, Daniel Malinsky, and Nlya Shpitser. Differentiable causal discovery under unmeasured confounding. In International Conference on Artificial Intelligence and Statistics, 2021.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 2020.
Peter Bühlmann, Jonas Peters, and Jan Ernest. Cam: Causal additive models, high digh-dimensional order search and penalized regression. The Annals of Statistics, 22(6))2526-2255) 2014.
David Maxwell Chickering. Optimal structure identification with greedy search. Journel of Machine Learning Research, 3(Nov):507-555 2002.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. International Conference on Machine Learning, 2021.
David Danks, Clark Glymour, and Robert Tillman. Integrating locally learned causal structures with overlapping variables. Advances in Neural Information Processing Systems, 2009.
Zhuangyan Fang, Shengyu Zhu, Jiji Zhang, Yue Liu, Zhitang Chen, and Yangbo He. Low rank directed acyelic graphs and causal structure learning. arXiv preprint Xit:22006.06611, 2020.
Erdun Gao, Ignavier Ng. Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous additive noise models. Advances in Neural Information Processing Systems, 2022.
Yinghua Gao, Li Shen, and Shu-Taa Xia. Dag-gan: Causal structure learning with generative adversarial 2021. Tomas Geffner, Javier Antoran, Adam Foster, Wenbo Gong, Chao Ma, Emre Kiciman, Amit. Sharma, Angus Lamb, Martin Kukla, Nick Pawlowski, al. Deep end-to-end causal inference. arXie preprint 2xxx:2202.00195 2022.
nets. In International Conference on Acoustics, Speech and Signal Processing, pp.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of cansal discovery methods based on graphical models. Frontiers in Genelics, 10:524, 2019.
Sander Greenland, Judea Pearl, and James M Robins. Causal diagrams for epidemiologic research. Epidemi- ology, pp- 37-48, 1999.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiu preprint arXiv:1910.11 14425, 2019.
James Heckman. Econometric causality. International Statistical Review, 76(1):1 27, 2008.
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlincar causal discovery with additive noise models. Advances in Neural Information Processing Systems, 2008
Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In International Conference on Knowledge Discovery & Data Mining, 2018.
17

---

Published in Transactions on Machine Learning Research (01/2023)
Biwei Huang, Kun Zhang, Mingming Gong, and Clark Glymour. Causal discovery from multiple data sets with non-identical variable sets. Associalion for the Advancement. of Artificial Intelligence, 34(06):10153-10111, 2020a.
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from leteengeneous//onssatioonnn data. Journal of Machine Learning Research, 21:1-53, 2020b.
Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
Eric Jang, Shixiang Gu, and Ben Poole. Calegorical reparameterization with gumbel-softmax. International Conference on Learning Representations, 2017.
Finn V Jensen and Thomas Dyhre Nielsen. Bayesian nelworks and decision graphs, volume 2. Springer, 2007.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawit, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Grutesor, Zaid Harchaoui, Chaoyang Hc, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Now Foundations and Trends, 2021.
Marcus Kaiser and Maksim Sipos. Unsuitability of notears for causal graph discovery. ar preprint arXiv:2104.05441, 2021.
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventious. arXiv preprint 1eX.:::100.0110 2019.
Diederik P Kingma and Jimmy Ba. Adam:: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Neville K Kitson, Anthony C Constantinou, Zhigao Guo, Yang Liu, and Kiattikun Chobtham. A survey of bayesian network structure learning. arXie preprint wxXi:2109.11441. 2021.
Daphnee Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien Gradient-baas based neural dag learning. In International Conference on Learning Representations, 2020.
Steffen Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Conference on Machine Learning and Systems, 2020.
Bill Yuchen Lin, Chaoyang He, Zihang Ze, Hulin Wang. Yufen Hua, Christophe Dupuy, Rahul Gupta, Mahdi Soltanolkotabi, Xiang Ren, and Salman Avestimehr. Fedulp: Benchmarking federated learning methods for natural language processing tasks. In Findings of the Association for Computational Linguistics, pp. 157 175, 2022.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning, pp. 3122-33 3130. PMLR, 2018.
Rui Liu and Han Yu. Federated graph neural networks: Overview, techniques and challenges. arXiv preprint Nii:2222.07256 2022.
18

---

Published in Transactions on Machine Learning Research (01/2023)
Margaret Mooney Marini and Burton Singer. Causality in the social sciences. Sociological methodology, 18: 347-409, 1988.
Brendan McMahan, Eider Moore, Damiel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communicttion efficient learning of doep networks from decentralized data. In International Conference on Artificial intelligence and statistics. PMLR, 2017.
Joris M Mooij, Dominik Janzing, Tom Heskes, and Bernhard Schölkopf. On causal discovery with cyclic additive noise models. Advances in neural information processing systems, 24, 2011.
Joris M Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21:1-108, 2020.
Yongchan Na and Jihoon Yang. Distributed bayesian network structure learning. IBEE International Symposium on Industrial Electronics, pp. 1607-1611, 2010.
Arkadi Nemirovski. Optimization ii: Standard numerical methods for nonlinear contimuous optimization. Lecture Note, 1999.
Ignavier Ng and Kun Zhang. Towards federated bayesian network structure learning with continuous optimization. In International Conference on Artificial Intelligence and Statistics, pp. 1095-8111. PMLR, 2022.
Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. A graph autocncoder approach to causal structure learning, Xie preprint or arXio:1911.074.00 2019.
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and dag constraints for learning linear dags. Advances in Neural Information Processing Systems, 33:17943-1799 17944, 2020.
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, pp. 1176-8198 PMLR, 2022a.
Ignavier Ng. Shengyu Zhu, Zhuangyan Fang, Haoyang Li, Zhitang Chen, and Jun Wang. Masked gradient- based causal structure learning. In SIAM International Conference on Data Mining, pp. 424-432 STAM, 2022b.
Nooshin Omranian, Jeanne MO Eloundou-Mbebi, Bernd Aneller-Roeber and Zoran Nikoloski. Gene regulatory network inference using fused lasso on multiple data sets. Scientific reports, 6(1):1-14, 2016.
Roxana Pamfil, Nisara Sriwattanaworachaii, Shaan Desai, Philip Pilgerstorfer, Konstantinos Georgatzis, Paul Beaumont, and Bryon Aragam. Dynotears: Structure learning from time-series data. International Conference on Artificial Intelligence and Statistics, 2020.
Judea Pearl. Bayesian netwerks: A model of self-activated memory for evidential reasoning. In Proceedings of the 7th conference of the Cognétive Science Society, University of California, Irvine, CA, USA, pp. 15-17, 1985.
Judea Pearl. Causality, Cambridge university press, 2009.
Judea Pearl, Madelyn Glymour, and Nicholas P Jewell. Causal inference in statistics: A primer. John Wiley & Sons, 2016.
Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometríka, 101 (1):21119,, 2014.
Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Identifiability of causal graphs using functional models. Conference on Uncerlainly in Artificial Intelligence, 2011.
19

---

Published in Transactions on Machine Learning Research (01/2023)
Jonas Peters, Peter Btihlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Sociely. Series B (Stalistical Methodology), pp. 947 1012, 2016.
Krishna Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. In International Conference on Machine Learning, pp. 17716-17758. PMLR, 2022.
Russell A Poldrack, Timothy O Laumann, Oluwasanmi Koyejo, Brenda Gregory, Ashleigh Hover, Mei-Yen Chen, Krzysztof J Gorgolewski, Jeffrey Luci, Sung Jun Joo, Ryan L Boyd, et al. Long-term neural and physiological phenolyping of a single human. Nalure Communicaliios,, 6(1):1- 15, 2015.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. arXiv preprint arXiv:2006.08907 2020.
Sumudu Samarakoon, Mehdi Bennis, Walid Saad, and Mérouane Debbah. Distributed federated learning for ultra-rcliable low-latency vehicular communications. IEEE Transactions on Communications, 68(2): 1146 1159, 2019.
Nino Scherrer, Olexa Bilaniuk, Yashas Annadani, Anirudh Goyal, Patrick Schwab, Bernhard Schölkopf, Michael C Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. Learning neural causal models with active interventions. arXiv preprint #xXi:2209.024320 2021.
Gidcon Schwarz. Estimating the dimension of a model. The Annals of Statistics, pp. 461-464, 1978.
Micah Sheller, Brandon Edwards, G Anthony Reina, Jason Martin, Sarthak Pati, Aikaterini Kotrotsou, Mikhail Milchenko, Weilin Xu, Daniel Marcus, Rivka R Colen, al. Federated learning in medicine: facilitating multi-institutional collaborations without sharing patient data. Scientific Reports, 10(1):1-12,
2020.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Peter Spirtes, Clark Glymour, Richard Scheines, et al. Causation, Prediction, and Search, volume 1. The MIT Press, 2001.
Jin Tian and Judea Pearl. Causal discovery from changes. In Uncertainty in Artificial Intelligence, pp- 512 521, 2001.
Robert Tillman and Peter Spirtes. Learning equivalence classes of acyelic models with latent and selec- tion variables from multiple datascts with overlapping variables. International Conference on Artificial Intelligence and Slatistics, 2011.
Sofia Triantafilon and Ioannis Tsamardinos. Constraint-basee causal discovery from multiple interventions over overlapping variable sets. Journal of Machine Learning Research, 16(1):2147-22)) 2205, 2015.
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152666):10-5555, 2017.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference Learning Representations, 2020a.
Xiaoqiang Wang, Yali Du, Shengyu Zhu, Liangjun Ke, Zhitang Chen, Jianye Hao, and Jun Wang. Ordering- based causal discovery with reinforcement learning. International Joint Conference on Artificial Intelligence, 2021.
Yixin Wang, Dawen Liang, Laurent Charlin, and David M Blei. Causal inference for recommender systems. In ACM Conference Recommender Systems, pp. 426 431, 2020b.
20

---

Published in Transactions on Machine Learning Research (01/2023)
Dennis Wei, Tian Gao, and Yue Yu. Dags with no fears: A closer look at continuous optimization for learning bayesian net works... Advances in Newral Information Processing Systems, 2020a.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. TEFE Transactions Information Forensies and Security, 15:3454-3469, 2020b.
Han Xie, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. Advances in Neural Information Processing Systems, 34:18839-18855 2021.
Jing Yang, Ning An, Gil Alterovitz, Lian Li, and Aiguo Wang. Causal discovery based on healthcare information. In International Conference on Bioinformatics and Biomedicine, pp- 71 71-73. IEEE, 2013.
Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang. Federated recommendation systems. Federaled Learning, pp. 225 209, 2020.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Tronsactions on Intelligent Systems and Technology, 10(2):1-19, 2019.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kamman Ramchandran, and Peter Bartlett.
Gradient diversity: a key ingredient for scalable distributed learning. In International Conference on Artificial Intelligence and Statistics, pp. 1998 2007. PMLR, 2018.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure learning with graph neural networks. International Conference on Machine Learning, 2019.
Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with curl: An efficient DAG structure learning approach. International Conference Machine Learning, 2021.
Ming Yuan. On the identifiability of additive index models. Stalisticn Sinica, pp. 1901 1911, 2011.
Keli Zhang, Shengyu Zhu, Marcus Kalander, Ignavier Ng, Junjian Ye, Zhitang Chen, and Lujia Pan. geastle: A python toolbox for causal discovery. arXiv preprint arXiv:2111.15155 2021.
Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. Conference on Uncertainty in Artificiol Intelligence, 2009.
Kun Zhang, Mingming Gong, Petar Stojanov, Biwei Huang, Qingsong Liu, and Clark Glymour. Domain adaptation as problem of inference on graphical models. Advances Neural Information Processing Systems, 2020.
Xun Zheng. Learning DAGs with Continuous Optimization. PhD thosis, Carnogic Mellon University, 2020.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. DAGs with NO TEARS: Continuous Optimization for Structure Learning. Advances in Neural Information Processing Systems, 31, 2018.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse nonparametric DAGs. In International Conference on Arlificial Intelligence and Statistics, 2020.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations, 2020.
21

---

Published in Transactions on Machine Learning Research (01/2023)
Appendix
Table of Contents
A Structure identifiability
23
B Implementations
24
B.1 Graph generation
24
B.2 SEM simulation
24
B.3 Detailed metrics
24
B.4 Hypar-parameters setting
B.5 Hyper-parase prper-parameters real-data setting
25
B.6 Model parameters
26
B.7 Training parameters
26
B.8 Sensitivity analysis of hyper hyper--pramenn parameters
27
C Discussions on our method
27
C.1 Novelty and contributions
27
C.2 Difference with graph neural network
.
................................
28
C.3 FedDAG framework
................................
28
C.4 Broader impact statement
29
C.5 The consistency results by BIC score
29
C.6 Does the global maximum of Eq. (6) correspond to the ground -ound-truthh DAG?
29
C.7 Can Algorithms and 2 solve Eq. (6)?
29
C.8 Can U finally satisfy the acyclicity constraint in Eq. (3)?
29
D Supplementary experimental details
30
D.1 Uneven distributions
................................
30
D.2 Varying clients
................................
30
D.3 Dense graphs
................................
D.4 Comparisons with voting method
................................
D.5 Comparisons with CAM
................................
D.6 Comparisons with NOTEARS-ADMM
32
More discussions on experimental results
Discussions Assumptions
33
F.1 Data heterogeneity
33
F.2 Invariant DAG assumption
33
22

---

Published in Transactions on Machine Learning Research (01/2023)
A Structure identifiability
Besides exploring effective DAG structure learning methods, identifiability conditions of graph struc- ture (Spirtes et al., 2001) are also important. In general, unique identification of the ground truth DAG is impossible from purely observational data without some specific assumptions. However, accompanying some specific data generation assumptions, the graph can be identified (Peters et al., 2011; Peters & Bühhmann, 2014; Zhang & Hyvarinen, 2009; Shimizu et al., 2006; Hoyer et al., 2008). We first give the definition of identifiability in the decentralized setting.
Definition A.1. Consider decentralized distribution set (X) satisfying Assumption 3.1. Then, G is said to be identifiable if (X) cannot be induced from any other DAG.
Condition A.2. (Minimality condition) Given the joint distribution P(X), P(X) Markovian to a DAG g but not Markovian to any sub-graph of g.
Condition A.3. (Cond. 19 in (Peters Bühlmann, 2014)) The triple (f,, P(X,), does not solve the lollowing differential equation Va,, By with v"(x, - ((x)) #0: 0:
I" -"' (- +
(") 8r
- 2"" + s'" + S" v (S")
<" = 5"
v"
f
Here, 5z and E = log P(Xi), and o: log P(ej) are the logarithms of the strictly positive densities.
Definition A.4. (Restricted ANM. Def. 27 in (Peters & Bühhlann, 2014)) Consider an ANM with d variables. This SEM is called restricted ANM if Vj E V,i E PA, and all sets S V with Pi)Mi CS C PA,Mi.), there is an ag with P(as)= > 0, s.t. the tripe
( D Xs zs), 2s),
X:
satisfies ConditionA.3. Here, the under-brace indicates the input component, of fj for variable X,. In particular, we require the noise variables to have non-vanishing densities and the functions f, to be continuous and three times contimuuuly differentiable.
Assumption A.5. (Faithfulness)) Let (X) satisfy Assumption 3.1. At least one distribution pes (X) e (X) meets Assumption A.6 and the other distributions are faithful to g.
Assumption A.6. Let a distribution P(X) with X = (X1, (2,,X2," X2,..., Xa)) be induced from a restricted ANM A.3 with graph 9, and P(X) satisfies Minimality condition w.r.t g.
Proposition A.7. Given pc (X) satisfying Assumption A.5, and then, G can be identified up from pc (X).
Proof. From Remark 3.2, we have Pot (X) (X) for Vca, is Markov with G. For cach e C with po (X)
does not satisfy Assumption A.6, the Completed Partially DAG (CPDAG) & (Pearl, 2009), which represents the CPDAG induced by G, can be identified (Spirtes et al., 2001). (1) That also says that these distributions can be induced from any DAG induced from M(G), including G definitely. Notice that skeleton = Skeleton(S) and any X; + Xy in & is also existed in g. Then, for those Ck with with pa (X) satisfying Assumption A.6, G can be identified. (2) That is to say, distributions satisfying Assumption A.6 can only be induced from G. Then, two kinds of graph, & and 9, are obtained. Therefore, & can be casily identified. With (1) and (2), per (X) E (X) for Vor can only be induced by G. Then, G is said to be identifiable
Future work is to relax our invariant DAG assumption to the invariant CPDAG assumption, which means that a group of DAGs across different clients share the same conditional independence. For this case, the generalized score functions (Huang et al., 2018) can be adopted to search for the Markov Equivalence Class. However, it is not straightforward to incorporate this method into our FedDAG framework since the score of this method is motivated by a kernel-based (conditional) independence test rather than penalized likelihood. Moreover, this method does not support a continuous search strategy. It would be interesting to explore the penalized seaiihodd-bseel method for this case and incorporate it into our framework.
23

---

Published in Transactions on Machine Learning Research (01/2023)
B Implementations
The comparing DAG structure learning methods used in this paper all have available implementations, listed below:
MCSL:
Codes are available gCastle https://githin
master/gcastle. The first author of MCSL added the implementation in this package.
NOTEARS and NOTEARS-MLP: Codes are available at the first author's GitHub repository https:
//github. h/g/thuu.ccom//unaaaaa hww.:/bb..coo/uuuheeggo//otterrr
NOTEAARS-ADMM:: Codes are available at the first author's GitHub repository https://github.com ignavieriggnnoeers-adeee
DAG-GNN: Codes are available the author's GitHuu repository DAG-GNN
PC and GES: the implomentations of PC and GES are available at causal-learn package repository bttps://causal-leate readthedocs http://hhcoo.../o/a/a/a///////ed html
CAM: the codes are available al CRAN R package Archive/CAM/
Our implementation highly based the existing Tool-chain named gCastle (Zhang et al., 2021), which includes many gradicnt-based DAG structure learning methods.
B.1 Graph generation
To simulate DAG for generating observations, we introduce two kinds of graph generation methods named Erdös-Rényi (ER) and Scale-Free (SF) graphs. To simulate the ER graph generation, we firstly randomly sample topological order and by adding directed edges where it is allowed independently with probability p d=-d where is the number of edges in the resulting DAG. To generate Scale-free (SF) graphs, we first take the SkarabasiAAbber model and then add all nodes one by one. From the above descriptions, we can find that the degree distribution of ER graphs follows a Poisson distribution, and the degree of SF graphs follows a power law: few nodes, often called hubs, have a high degree (Lachapelle et al., 2020).
2x
B.2 SEM simulation
In our experimental setup, for each client, we randomly choose a nonlinear type from the given four functions with equal probability in the heterogeneous data setting. The nonlinear function choice is totally the same as used NOTEARS-MT. (Zheng al., 2020). The details are as follows.
We simulate the SEM X; f5(()m, + Zj for all j [d] in the topological order induce by G.
GP: fy is drawn from the Gaussian process with RBF kernel with length-scale one.
GP-add: fy(Xpa,) ExEpa, (Xx), where cach fąx is from GP.
MLP: fj is randomly initialized MLP with one hidden layer of size 100 and Sigmoid act
MiM: also named as index model. fx(Xpa;) Emm Am EkEpa, Xa), where h tanh, h2 cos, hg sin, and each 0jnk is uniformly drawn from range [-2, -0.5] U (0.5.2].
B.3 Detailed metrics
SHD is a kind of measurement which defined calculate the Hamming distance between two partially directed acyclic graphs (PDAG) by counting the number of edges for which the edge type differs in both PDAGs. In PDAG, there exist four kinds of edges between two nodes: + j. i j, j, and i SHD just.
24

---

Published in Transactions on Machine Learning Research (01/2023)
counts the different edges between the two graphs. SHD is defined over the space of PDAGs, so can, of course, use it to calculate distances in DAG and CPDAG spaces.
True Positive Rate (TPR) and False Discovery Rate (FDR) are two common metrics in the machine learning community. True positive rate, also referred to as sensitivity or recall, is used to measure the percentage of actual positives which are correctly identified. The FDR is defined as the expected proportion of errors committed by falsely rejecting the null hypothesis. Let TP be true positives (samples correctly classified as positive), FN be false negatives (samples incorrectly classified negative), FP be false positives (samples incorrectly classified positive), and TN be true negatives (samples correctly classified negative). Then, FP
TP TPR TP4FN and FDR FP-TP-
B.4
setting
In all experiments, there is extra reper-parameter to adjust for PC (with Fisher-z test and p-value 0.01) and GES (BIC score). For NOTEARS, NOTEARS-MLP, and DAG-GNN, we use the default haper-parametors provided in their papers/codes. For MCSL, the hyper-parameterss that need to be modified are Pinit and B. Specifically, if experimental settings (10 variables and 20 variables) are the same as those in their paper, we just take all the recommended hyper- parem--arametess.. For settings not implemented in their paper (40 variables exactly), we have two kinds of implementations. The first one is taking a lincar interpolation for choosing the hyper-parameters. The second one is taking the same parameters as ours. We find that the second choice always works better. In experiment, we report the experimental results in second way. Notice that CAM pruning is also introduced to improve the performance of MCSL, which however can not guarantec a better result in our settings. For simplicity and fairness, we just take the direct outputs of MCSL.
Similar to MCSL (Ng et al., 2022b) and GraN-DAG (Lachapelle et al., 2020), we implement several experiments on simulated data with known graph structure to search for the hyper-parameters and then use these hyper- parameters for all the simulated experiments. Specifically, we use seeds from to 10 generate the simulated data to search for the best combination of hyper-parameters while all our experimental results reported in this paper are all conducted using seeds from 2021 to 2030.
B.5 Hyper-paramete parameters in real-data setting
Most DAG learning methods have hyper-parameters, more or less, which need to be decided prior to learning. Morcover, NN-based methods are especially sensitive to the selection of typer-parametors. For instance, Gran-DAG (Lachapelle et al., 2020) defines a really large hyper-parameteers space for searching the optimal combination, which even uses different learning rates for the first sub-problem and the other sub-problest MCSL and GS-FedDAG are sonsitive to the selection of Pinit and / when constructing and solving the sub-problem. As pointed out in (Kairouz et al., 2021), NOTEARS focuses more on optimizing the scoring term in the early stage and pays more attention to approximate DAG in the late stage. If NOTEARS cannot. find a graph near G in the early stage, then, it would lead to a worse result.
To alleviate this problem, one may choose to (1) enlarge the learning rate or take more steps when solving the first few sub-problems as Gran-DAG; (2) reduce the value of coefficient, Pinit to let the optimizer pay more attention to the scoring term in the early stages as MCSL. The other trick we find when dealing with real data is increasing l1 This mostly results from that real data may not fit well with the data generation assumptions most papers. Therefore, we choose to conduct a grid search to find the best combination of Pinit; 8,6 for DAG structure lcarning on real data.
In the practice of DAG structure learning, it is impossible to have G to select the hyper- srper-parameters. One common approach is trying multiple hyper-parameter combinations and keeping the one yielding the best score evaluated on a validation set (Koller & Friedman, 2009; Ng et al., 2022b; Lachapelle et al., 2020). However, the direct use of this method may not work for some algorithms, such as MCSL, NOTEARS-M MLP, and GS- A.. This mainly lies in the similar explanations of the property of the traditional solution of FL. In the late stage of optimization, the optimizer focuses heavily on finding a DAG by enlarging the penalty coefficient p. Then, the learning of relationship mechanisms would be nearly ignored. To address this problem, we first report the DAG directly learned by a combination of ceper-parameterss And then,
25

---

Published in Transactions on Machine Learning Research (01/2023)
replace the parameters part for describing the graph with the learned DAG. Afterward, we just take the score without DAG constraint to optimize the relationship mechanisms approximating part (which may not be the same name in the other algorithms). Finally, the validation set is taken to evaluate the learned model. The final byper-parameters used on the real dataset in our paper are as follows:
Table 5: The hyper-parameter used real data.
Parameters
Pinit
B
A6
Values
0.008
2
0.3
B.6 Model parameters
The GSL part in each local model is parameterized by a d matrix named U and the Gumbel-Sigmodl approach is leveraged for approximating the binary form. Each entry in U is initialized 0. The temperature is set to 0.2 for all settings. Then, for the relationship mechanism approximating part, we use 4 dense layers with 16 variables in each hidden layer. All weights in the Network are initialized using the Xavier uniform initialization. The number of parameters used in each method is shown in Table 6.
Table 6: Model parameters for each client with different nodes.
nodes
nodes
40 nodes
NOTEARS
100
400
1600
Mask of MCSL
100
400
1600
NN of MCSL
9930
19860
39720
B.7 Training parameters
Our GS-FedDAG and FedDAG reach this point and are implemented with the following We take ADAM (Kingma & Ba, 2015) with learning rate 3 x 10-2 and all the observational data Doh on each client are used for computing the gradient. And the detailed parameters used in Algorithms 1 and 2 are listed in Table 7.
Table 7: The hyper-parameters used on simulated data in this paper.
Parameters
Oiinit
hzol
itmaz
itinner
it
7
Pmaz
Values
1 10-10
25
1000
200
0.25
x 10
0.01
Notice that illustrated in MCSL (Ng al., 2022b), the performance of the algorithm is affected by the initial value of Pinit and the choice of 3. Since small initial of Pinit and would result in rather long training time. As said in (Kaiser & Sipos, 2021), MLE plays an important role in the early stage of training and highly affects the final results. Therefore, carefully picking a proper combination of Pinit and 3 will lead to a better result. In our method, we tune these two parameters via the same scale of experiment with seeds ~ 10. For each variable scale and training type, the parameters are adjusted once and are applied to all other experiments with the same variable scale. We find the combinations of the following parameters Table work well in our method. Our method also adopts & sparsity term on g- (U), where the sparsity coefficient d is chosen 0.01 for all settings.
26

---

Published in Transactions on Machine Learning Research (01/2023)
Table 8: The combinations of Pinit and 3 on simulated data in our method.
10 nodes
20 nodes
40 nodes
Pinit
Pinit
8
Pinit
B
AS-FedDAG
6 x 10-3
10
1 x 10-5
20
1 1 10-11 11
120
GS-FedDAG
6 10-3
10
x 10-5 5
20
1 1 10 -1
120
40
40
30
30
SHD
SHD
SHD
20
20
20
10
0
0
10
10" -1
10"
10"
1.0
0.8
0.6
0.6
0.6
TPR
TPR
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
10
10'
itn
A/
Figure 5: The sensitivity analysis of
B.8 Sensitivity analysis of hyper-parameters
Here, we show the sensitivity analysis of it, a'nnit, and At, From the experimental results in Figure 5, we find that our method is relatively robust to it That is to say, the it can be reduced to alleviate the pressure of communication costs while the performance can be well kept. A is the coefficient of l sparsity, which will affect the final results. Because we have no sparsity information of the underlying graph, we sot \ι 0.01 in all settings. When dealing with real data, we recommend the audiences adjust this parameter by using our parameter-tunin method provided in Section B.5. The results of ainit As discussed before, our method tries to maximize the likelihood term of the total loss in the early stages, which is important to find the final ground-truth DAG. If setting relatively large asnit, the carly learning stages would be affected. Therefore, we recommend directly taking Osnit as 0 in all settings.
exactly as expected.
C Discussions on our method
C.1 Novelty and contributions
Firstly, we acknowledge the contribution of our baseline method MCSL (Ng et al., 2022b), which performs well many settings and helps to guarantee the performance of our proposed method. We also appreciate the excellent baseline method FedAvg (McMahan et al., 2017), which provides an efficient federated learning way. Our FedDAG is highly inspired and benefits from these two works. The main contributions, which
27

---

Published in Transactions on Machine Learning Research (01/2023)
be taken by our proposed method, are (1) one of the first works that investigate the practical problem of DAG structure learning in federated setup and (2) further providing the FedDAG approach that can guarantee the privacy protection by avoiding the raw data leakage and allow the data heterogeneity across the clients. Another concurrent work NOTEARS-ADMI. (Ng & Zhang, 2022) also considers the same problem while our GS-FedDAG can (1) gain better performances in most of the settings, (2) well handle the nonlinear cases, (3) allow heterogencous data, and (4) provide a quite flexible federated DAG structure learning framework.
Discussions on the simple averaging Even though averaging is the simplest way to aggregating and exchanging information, we find it is quite an effective way to solve the federated DAG structure learning problem, which is an advantage of our method. Our simple averaging for homogeneous cases can nearly approach the same performance as using all data. For the heterogeneous cases, GS-FedDAG can still obtain satisfactory results. While, as future work, more advanced information aggregation methods (Wang et al., 2020a) can be well incorporated into our framework to boost the performances further.
C.2 Difference with graph neural network (GNN) learning
Four main reasons make DAG structure learning and GNN two different research lines. (1) Nodes in DAG represent variables, and directed edges describe the single-direction relation between different variables. In GNN, graph talks more about graph-type data, such as social networks, protein networks, and traffic networks. (2) Networks in DAG structure learning are leveraged to learn the relationship mechanisms, while networks in GNN are taken to achieve node embedding and feature extraction. (3) Learned DAG can be taken for interventional and counterfactual reasoning (Kitson et al., 2021). (4) DAG structure learning cares more about identifiability. It essential to identify the true underlying relationship of the observations preciscly. In the federated setup, most existing federated GNN (Xie et al., 2021; Liu & Yu, 2022) methods assume that the underlying graphs are known and localized. What is being learned in the federation is the weight aggregation of the GNN but not its graph. This also leads to the main difference between our federated DAG learning and federated GNN learning.
C.3 FedDAG as a framework
In this paper, we restrict our attention to the case that all concerned variables can be well observed. We also only take MCSL (Ng et al., 2022b) as the baseline method. However, all gradient- based methods can be incorporated into our AS-FedDAG framework to deal with homogeneous data. To deal with the heterogeneous data, we prefer that the baseline methods can separately learn the DAG structure and relationship mechanisms. The other baseline methods that can be easily combined into our framework are NOTEARS-MLP (Zheng et al., 2020) and DAG-GNN (Yu et al., 2019). Unfortunately, many works are not in this fashion, such GraN-DAG (Lachapelle et al., 2020), CD-RL (Zhu et al., 2020), and their following works.
Latent variables. In this paper, we carry with no unobserved common confounder assumption. Handling latent confounders is a fundamentally important but challenging problem in the traditional DAG structure learning, not to mention the federated sctup. Until now, the theoretical results on the structure idcntifiability of DAG learning with latent confounder are always too weak to be used in practice since too strict assumptions are taken. In the recent progress of the latent variables research, Bhattacharya et al. (2021) takes the acyelic directed mixed graphs (ADMGs) to describe the graphs with latent confounders. With different types of restrictions, three classes of propricties, named Ancestral graph, Acid graph, and Bow-free graph, are given. According to different proprieties, different graph constraints are given. For example, trace (eP) (eP)-d+ - Do B) = 0 is set for the Bow-free graph", where D is the adjacency matrix recording the directed edges and B records the double-directed edges. We can directly replace the constraint to incorporate this method in our framework. However, this method can only deal with the linear Gaussian case, which is somewhat limited.
Sse more details Section& (Bhattacharya et al., 2021)
28

---

Published in Transactions on Machine Learning Research (01/2023)
C.4 Broader impact statement
In federated learning, the server and some clients participale in this process. While as talked about above, the DAG is shared among all clients. FedDAG is motivated by the 'data on each client is not enough for identifying up the ground-truth DAG.' The graph information is not private for clients. For the server, it depends. In our previous motivations, we only cared about the 'raw data leakage" problem but did not consider the privacy of the graph. Some relations can be public in real-world scenarios, such as disease research. For these cases, our method can still work. However, graph structure may sometimes also be private information. This problem can be easily solved by picking one client as the proxy server.
C.5 The consistency results by BIC score
Actually, for linear additive noise models with Gaussian noises, the consistency results for maximizing the BIC score to identify the DAG (Markov Equivalence Class DAG) have been well established (Tian & Pearl, 2001; Huang et al., 2020a). For this case, with the DAG space constraint, the unique maximum of score function Scx (D**, t ,0*) with BIC score corresponds to the ground-truth DAG. Even for the high-dimensional consistency for linear Gaussian SEM when the model is identifiable (Aragam et al., 2019). Since the ground-truti truth G corresponds to each 8 the global maximum arg max.; U Σx=1 S* (D* & .U) with DAG constraint can lead to the ground-truth DAG graph. For nonlinear ANMs, however, even many practical methods, e-g., MCSL (Ng et al., 2022b), NOTEARS-MLP (Zheng et al., 2020), and CD-RL (Zhu et al., 2020), have been proposed to solve this problem by maximizing the BIC score, the theoretical results of consistency are still lacking and would be an interesting future work to be investigated. Therefore, our framework based on these methods inherits the theoretical limit for the nonlinear case. From our paper, however, empirical results can still show the method's 's effectiveness.
C.6 Does the global maximum of Eq. (6) correspond to the ground-truth DAG?
Firstly, for observations of identifiable ANMs on each client, the unique maximum of score function 8tx (DRr, (0,,, U*) with BIC score corresponds to the ground-truth DAG (Zheng et al., 2018; Ng et al., 2022b). Even for the high-dimensional consistency of linear Gaussian SEM the case when the model identifiable. Since the ground-trutal g corresponds each 8*x the global maximum arg max Ei=1 S (D&, ha, U with DAG constraint can lead to the ground-truth DAG.
C.7 Can Algorithms 1 and 2 solve Eq. (6)?
Unfortunately, the global maximum of Eq. (6) can not be well reached by the gradient-based optimization methods, which is mainly caused by the non-convex property of the acyclicity constraint. Firstly, discovering the ground-truth DAG is NP-hard problem. Traditional methods like PC and GES search the discrete DAG space to solve this problem, which is relatively time-consuming. Then, NOTEARS introduces an equality constraint (3) to formulate the DAG search problem as a continuous optimization problem, which can be easily solved by the gradient descent methods. However, the trade-off is that this equality roint is non-convex, which pushes us away from finding the ground-truth DAG (the global minima of (6)). That is to say, using gradient descent to solve (6) only can reach the local minima of (6). This similar conclusion stands for recent continuous optimization-basee CD methods such as GraNDAG (Lachapelle et al., 2020), DAG-GNN (Yu et al., 2019), and NOTEARS-MI. (Zheng et al., 2020).
C.8 Can U finally satisfy the acyclicity constraint in Eq. (3)?
For simplicity, please do not mind if we explain method by setting some parameters with specific values. Firstly, following NOTEARS (Zheng et al., 2018) and MCSL (Ng et al., 2022b), we take the Augmented Lagrangian Method (ALM) to covert the constrained optimization problem into a series of sub-problemns without the hard constraint but with two penalty terms. For the t-th sub- problem, the specific formulation of Eq. (8) related to a and Pt- a and Pt will be updated to 0,41 and pt+1 after solving the t-th sub-problem for 1000 steps (gradient descent step). When dealing with each sub-problem, each client locally updates its personalized model with acyelicily penally terms, which is indeed for the acyclicity constraint. During
29

---

Published in Transactions on Machine Learning Research (01/2023)
the 1000 steps, Us are averaged every 200 steps (Yes, the simple average is nothing with acyclicity). When finishing 1000 steps (also the 5-th 200 sleps is just finished), new Unew is obtained. Then, and Pt are updated to 0x++1 and Pt+1 to formulate the next sub-problem of ALM, which are described in steps 5~9 9 in Algorithm 1. Then, a new circulation begins. Therefore, we argue that (1) the acyclicity constroint is guaranleed by laking the acyclicity penallty when solving each sub-problem. (2) the convergence of U is supported by the convergence analysis of Personalized FedAug of heterogeneous data.
D Supplementary experimental details
D.1 Uneven distributions
For federated learning problems in the real world, different clients may own different amounts of observations. To verify the stability of our method, we simulate the setting of uneven distributions in different clients. For each client, the number of observations is randomly chosen from a list [20%, 40%, 60%, 80%] x n, where is the maximal observation. The experimental results are shown in Fig. 6, from which we can find that our method show relatively stable performance in this setting.
14
1.0
AS
0.5
0.6
04
0.2
300
600
200
Figure 6: Results of uneven distributions on different clients.
D.2 Varying clients
In this sctting, we now consider a fixed number of samples distributed across different clients. We conduct experiments for (2, 4, 6,8) clients and show the results in Fig. 7. With the increase in clients number, our method can show better performance.
1.0
AS-FeDDGG
AS-FoIDAG
AS FodDG
1.0
12
0.5
0.8
10
0.6
SHD
0.6
0.4
0.2
2
0
0.0
0.5
The cumber ef
The suzbo of dieistt
The sumberr of elicst
Figure 7: Results of performances with varying clients.
30

---

Published in Transactions on Machine Learning Research (01/2023)
D.3 Dense graphs
Our method is also implemented on some denser graphs. Experimental results in Table 9 and Table 10. From these experimental results, methods the denser graph setting. For the homogeneous case, both AS-FedDAG and GS-FedDAG obtain the nearly low SHD as MCSL trained on all data and far better than all methods trained on separated data. For the heterogeneous case, our GS-FedDAG still shows the best performance. Compared to NOTEARS in 20 variables case, GS-FedDAG shows similar SHD results but a much better TPR result. Therefore, how to reduce the false discovery rale of GS-FedDAG would be an exciting thing.
that our method shows consistently better performance
other
Table Results on nonlincar ANM with dense graphs (Homogencous data).
ER4 with 10 nodes
SF4 with 10 nodes
ER4 with 20 nodes
SF4 with 20 nodes
SHID L
TPR f
SHD 4
TPR f
SIID
TPR
SID
TPR
Sepp data All clnta
PC
3.2
0.29 0.07
18.9
0.37 0.16
9.5
0.006
6..2
0.30
NOTEARS
34.3 1.7
0.03
1.3
0.05
7.8
0.00
0.9
0.02 0.001
MCSL
15.5 5.9
0.15
4.5 3.1
0.83+
33.8 10.4
0.
19.8 7.5
0.69 0.11
PC
31.
0.14
2.58
0.01
6.1
0.13
60.9
0.10
NOTEARS
1.
0.03
2.07
0.06
6.9
0.03
62.3
0.03 0.01
MCSL
3..
0.61 0.09
4.3
0.78
49.3 11.8
0.63
5.67
0.73 0.007
GS-FedDAG
1.9
0.53 +: 0.12
3.0
0.18
35.4 10.9
0.53
20.7 5.1
0.09 0.008
AS-FedDAG
17.4448
0.53 + 0.12
5.5 2.8
0.79 + 0.11
40.7
0.100
24.1 + 5.8
0.71 0.09
Table 10: Results nonlinear ANM with dense graphs (Hetcrogencous data).
ER4 with 10 nodes
SF4 with 10 nodes
ER4 with 20 nodes
SF4 with 20 nodes
SHD 1
TPR 1
SHD 4
TPR 1
SHD 4
TPR 1
SHD 1
TPR:
Sep datt
PC
29.3 1.3
0.23 0,03
2.1
0.31 :: 0.06
71.9
0.19 0.03
0..7
0.22 0.03
NOTEARS
2.6
0.45 0.08
12.2
0.54 0.11
43.2
0.49 0.08
39.4 6.8
0.47 = 0.10
MCSL
2.2
0.52 0.07
1..7
0.65 + 0.07
6.7
0.33 -: 0.05
5.3
0.31 0.05
GS-FodDAG
8.5 3.7
0.84 0.09
4.5
0.93 0.07
40.7 14.5
0.74 0.07
39.9 10.8
0.68 0.07
D.4 Comparisons with voting method
There is another interesting research line (Na & Yang, 2010), which also tries to learn DAG from decentralized data. We add a DAG combination method proposed in (Na & Yang, 2010), which proposes to vote for each entry of the adjacency matrix to get the final DAG. From the experimental results Table 11, we can find that For PC and NOTEARS, the combining method seems to contribute little improvement. This is because the reported DAGs local clients are too bad get a good result. For MCSL, this combing method works well for improving performance. The reason is casy to be inferred from the results. For MCSL, DAGs reported by local clients are of bad SHDs but good TPR, which means that the False Discovery Rates (FDRs) are high. In contrast, the combing method can further reduce the FDRs and keep the TPRs still good. Then, SHD can be further reduced. Luckily, our GS-FedDAG still shows the best performances in all settings.
D.5 Comparisons with CAM
Here, add one more identifiable baseline named causal additive model (CAM) (Bühlmann et al., 2014), which also serves as bascline in MCSL (Ng et al., 2022b), GraNDAG (Lachapelle et al., 2020), and DAG-GAN (Yu et al., 2019). From results in Table 12 and 13, we can see that our methods always show an advantage over CAM. CAM also assumes a non-linear ANM for data generation. However, CAM limits the non-linear function to be additive. In normal ANM, X, f((Xpa.) + & while CAM assumes X; x Ex=xxxxipa (X, + 4, which limits the capacity of its model. From the above experimental results, that our methods show consistent. advantages CAM.
31

---

Published in Transactions on Machine Learning Research (01/2023)
Table 11: Comparison with the voting method.
Homogeneons data (GP)
Heterogeneous data
ER2 with 10 nodes
ER2 with nodes
ER2 with nodes
ER2 with 20 nodes
SHD
TPR
SHD 4
TPR 1
SHD J
TPR t
SHD 4
TPR t
Voting Sep data
PC
24
0.31 0.06
6.5
0.28 0.07
2.7
0.45 0.07
6.3
0.44 0.007
NOTEARS
1.0
0.06 0.04
0.11 3.07
7.6
0.10=0.11
15.0
0.62 0.009
MISLL
3.2
0.83 0,08
0.88 0.07 5.5
9.2
0.72=
2.8
0.50
PC
3.0
0.11
5.9
0.22
11.4
0.36 0.13
25.5
0.29 0.113
NOTEARS
0.11 1.26 0.0G
6.2
0.09
7.8
0.56 0.20
18.4 11.6
0.49 0.30
MCSL
8.0
0.85 + 0.16
1..1
0.88 0.06
6.2
0.13 0.71
10.1 4.6
0.79 0.09
GS-FRIDAG
2.4 + 2.0
0.86
0.12
6.2 4.0
0.10
1.9 + 1.6 NaN
0.99 + 0.02
6.2 + 4.7 NaN
0.89 + 0.09
AS-FADDAG
1.8 + 2.0
0.89 + 0.12
5.0 4.2
0.88 + 0.11
NaN
NuN
Table 12: Comparisons with CAM on nonlinear ANM (Homogeneous data-GP).
ER2 with 10 nodes
SF2 with 10 nodes
ER2 with 20 nodes
SF2 with 20 nodes
SHD L
TPR 1
SHD 4
TPR f
SHD
TPR
SHD J
TPR f
All data
CAM
2.5
0.09
9.1
0.81
214147
0.77,
26.6
0.75 0.07
Sep data
CAM
11.8
0.10
11.1=1.5
0.38 0.11
24.3
0.00
2608220
0.36 + 0.06
GS-FeDDAG
2.4
0.12
2.7
0.86 0.13
6.2
0.15
0.80 11.777.0
AS-FoDDAG
1.8 +: 2.0
0.89 0.12
2.5 2.7
0.15
5.0
0.88 + 0.11
7.8 - 5.5
0.80
D.6 Comparisons with NOTEARS-
In this subsection, we give the experimental comparisons with NOTEARS-ADME in detail to verify the advantage of our averaging strategy is simple but effective. Firstly, we conduct the results on lincar models, which are the main part in Ng & Zhang (2022). As shown in Fig. 8, even on linear models, our AS-FedDAG can consistently show its advantage over NOTEARS- ADMM. Then, for the nonlinear models, we consider two different functions named MLP and Gaussian process (GP). The results are presented in Fig. 9, from which we can see that FedDAG always show better performance over all settings. Since NOTEARS-ADMM can not handle heterogeneous data, we do not give the results on heterogeneous data for fair comparison.
E More discussions on the experimental results
Why does our method outperform other methods even some baseline methods using all data for training?
Let us first discuss the AS-FedDAG (All-Shared FedDAG), which shares all model parameters (both & and U) among all clients. If we set it as in AS-FedDAG, AS-FedDAG is totally the same as MCSL using all data for training, For simplicity, we mark all parameters (actually & and U) of client Oj together as 8** Let consider the t-th itcration when all clients receive the average parameters 0, from the server and update their parameters by 0,
For AS-FedDAG, firstly, we mark the gradients obtained by using the local data of client ot for k E [m] as ge Then each client Cs updates its parameters for one step by 85.t = 0, - Ir x gi", where Ir is the learning rate. Afterward, the server collects all parameters and averages them to get Q Em, 6th X
0, - Ir x Em, For MCSL, there is only one f. MCSL uses full gradient information, then 0.+1= - O2 Ir x >m 96" cv find that the updated parameters are totally the same. Then if it > 1, we average all parameters every it itcrations. Even though the exact updating procodures are not the same, the expectations of updated parameters are the same. This is why we say that MCSL trained on all data can serve as an approzimate upper bound of our method but unobtainable in our paper.
Em (0x sk)
m (the full gradient is just the average of gradients from all samples). We can
32

---

Published in Transactions on Machine Learning Research (01/2023)
Table 13: Comparisons with CAM on nonlinear ANM (Heeterogeneous data).
ER2 with 10 nodes
SF2 with 10 nodes
ER2 with 20 nodes
SF2 with 20 nodes
SHD J.
TPR 1
SHD 4
TPR
SHD
TPR 1
SHD
TPR 1
All data
CAM
31.9 1: 4.8
0.39 a: 0.15
31.8.1
0.31 0.177
104.6 =: 15.4
0.46 4. 1.155
116.9 =: 13.8
0.35 =: 0.07
Sep data
CAM
18.0 1.7
0.52 4 0.04
17.8
0.51 0.3
47.5 9.2
0.52 4: 0.04
6310
0.50 = 0.03
GS- GS-FeG
1.9 + 1.6
0.99 +: 0.02
2.6 i: 1.3
0.93 4: 0.07
6.2 1.7.
0.89 4: 0.09
11.5 4: 6.7
0.81 +: 0.14
a- AIBRANS 17600
1.82
Al 4446
1.0
30
845
0.42
0.80
0.23
0.80
Charriiio ded
(a) ERI with 10 nodes.
(b) ER2 with 10 nodes.
100
WITSASS 41600
5115
NITTAR-AN AMM
1400
5179
K55
5110
6009
2000
4179
0125
4158
Clecraton ockicias
(c) ERI with 20 nodes.
(d) ERI with 20 nodes.
Figure 8: Comparisons with NOTEARS-ADMM on the lincar model (IID).
In GS-FedDAG (Graph-Shared FedDAG) method, only all graphs are averaged. However, this partial cornmaaion-sharing mechanism also helps on benefiting information from other clients to find a better solution (Collins et al., 2021).
F Discussions on Assumptions
F.1 Data heterogeneity
The general heterogeneous data setup should include the distribution shift caused by interventions since interventions on certain variables would also lead to heterogeneous distribution. Previous work (Huang et al., 2020b) has investigated this case and proposes the CD-NOD algorithm, which enhances the PC method, to learn from heterogeneous data. However, CD-NOD needs to identify some edge directions by capturing the changing information among distributions. That is to say, this method which needs to gather all data and cause the raw data leakage, of course. In our paper, we restrict our attention to the ANMs, which care more about the mechanisms and noise shift among different clients. Moreover, finding the identifiability conditions for learning graphs from the general heterogeneous data (both mechanisms shift and interventional data) the federated setup is a challenging but important problem, which left for future work.
F.2 Invariant DAG assumption
Firstly, let us skip the homogencous data sctting of FedDAG, which only assumes all SEMs are totally the same but data are generated at different local clients. Then, we mainly talk about the heterogeneous setting that assumes SEMs vary, but. DAG is shared among different clients.
33

---

Published in Transactions on Machine Learning Research (01/2023)
SOTEARS-400
HOTEARS
10
(a) ERI with 10 nodes (GP).
(b) ER2 with 10 nodes (GP).
303
133
0.7
655
310
200
3-5
(c) ERI with 10 nodes (MLP).
(d) ER2 with 10 nodes (MLP).
Figure 9: Comparisons with NOTEARS-ADMM on nonlinear models (Homogeneous data).
Table 14: Results on nonlinear ANM with different functions (Homogeneous data, 10 nodes, ER2).
GP
MIM
MLP
CP-add
SHD
TPR
SHD
TPR
SHD 4
TPR
SHD
TPR
PC
15.3
0.37 - 0.10
11.044.9
0.60
0.166
11.8
0.61 0.114
14.0
0.19
All data
GES
1..0
0.10
9.6
0.11
15.
0.14
14.4
0.37
DAG-GNN
16.212.1
0.06
13.7424
0.26
18.2#3.3
0.36
1.3
0.21
NOTEARS
16.5+22.
0.05 + 0.04
12.1+332
0.34
13.3+3.4
0.35 0.35++0.15
13.4+222
0.23
0:23++0.0
N-S-MLP
8.1
1566-011
1.611
0.95
5.6 1.9
0.11
6.8
0.61
MCSL
1.9 1.5
0.90 0.08
0.7
0.97 0.06
12.7
0.38
1.94
0.91
PC
14.1
0.31 0.06
11.1
0.18
1..2
0.09
13.5
0.31
Sep data
GES
12.7
0.37
10.6
0.11
1..6
0.50
1..0
0.48 0.08
DAG-GNN
15.7
0.01
11.7
0.31
1..7=3.6
0.39
1.00
0.10
NOTEARS
16.5
0.04
1..3+3.0
0.32
13
0.35
133
0.24
N-S-MLP
8.6
0.16
2.8
0.93
1.3
0.11
7.
0.67 00113
MCSL
7.1
0.83
4.122.1
0.01
1..4
0.57
6.5
0.01
GS-FedDAG
2.4
0.86 0.12
2.1
0.90
11.1
0.27
2.6
0.87 0.09
AS-FedDAG
1.8
0.89 0.12
1.7
0.90
3.5
0.22
2.4
0.87 + 0.08
Fssentially, an SEM models the physical processes of a system and the generation process behind observations. Intuitively, different SEMs usually describe different systems. Then, naturally, the DAGs may be different. In the case that the deployed systems on different clients are not the same, our method will break down because of the model misspecification. Unfortunately, dcal with this case, and we leave it for future work.
not straightforward to extend our current framework
In this paper, we leave the variant causal graphs case aside and focus on the invariant graph case. This be explained by the fact that system can have various SEMs at different statuses (Huang et al., 2020b). In the real world, some cases can be supported by our assumptions. The first example can be fMRI recordings. As pointed in (Huang el al., 2020b), MMRI recordings are usually non-stationary because information flows in the brain may change with stimuli, tasks, and attention the subject. Our federated setting only has one more assumption that fMRI recordings among different clients cannot be shared. The sccond example can be causal gene regulatory network inference (Omranian al., 2016). The causal direction among genes, i.., which gene regulates which gene, is believed to be the same. However, the SEM mechanism could vary in
34

---

Published in Transactions on Machine Learning Research (01/2023)
Table 15: Results on nonlinear ANM with different functions (Homogeneous data, 20 nodes, ER2).
GP
MIM
MLP
GP-add
SHD
TPR
SHD
TPR
SHD
TPR
SHD
TPR
3..7=9.4
0.48 0.13
22.8
0.15
33.7
0.10
35.2
0.50 0.09
All data
875
0.16
2.1
0.78
44.9
0.65
41.74:16
0.08
DAG-GNN
32.
0.10
26.7
0.26
10.1
0.08
27.24:
0.24 0.08
NOTRARS
31.8+6.0
0.01
0.29
25.3+
0.40
25.6
N-S-MLP
18.2+4.5
0.52
0.94
8.0
0.86 0.07
0.70
MCSL
4.6
0.90 0.13
1.74
0.97 0.0g
0.12
1.9
0.92
PC
3.5
0.28 0.00
5.6
0.16
30.6+880
0.41 0.09
5.6
0.42 0.10
Sep duta
GES
5.5
0.04
8.7
0.61
34.4+11.3
0.52 0.09
29.3+
0.51 0.07
DAG-GNN
31.
0.12
2.88
0.26
34.1
0.07
26.5
0.27 0.05
NOTEARS
31.
0.11
2.9
0.29
25.4
0.02
25.6
0.29 0.06
N-S-MLP
1..5=4.7
0.07
6.9
0.92
0.86 0.07
3.3
0.70
MCSL
2.5
0.88 + 0.07
2.8
0.91
30.2
0.61
16.24 5.3
0.87 0.05
GS-FodDAG
6.2 4.0
0.85 0.10
2.8
0.93 = 0.05
21447799
0.11
8.1 +: 3.2
0.85 0.05
AS-RaDDAG
5.0 4.2
0.88 + 0.11
3.3 2.5
0.92
20.1 8.3
0.72 0.14
5.6 = 2.8
0.86 = 0.06
Table 16: Results on heterogencous sctting with the different mumber of observations, (20 nodes, ER2).
100
=30
=000
=900
SHD
TPR f
SHD
TPR
SHD
TPR
SHD
TPR
PC
55.5 2: 8.5
0.21 0.06
5.7
0.29 0.07
6.84
0.32 0.11
6.6
0.29 1 0.10
All data
GFS
82.8 + 13.7
0.38 0.12
96.4 1.44+144 14.9
0.48 + 0.08
102.9+13.66
0.51 0.088
106.3 + 14.3
0.50 0.11
DAG-GNN
61.7
0.30
56,8
0.30
57.7
0.38 0.008
57.9
0.32 0.008
NOTEARS
0.41
57.6
0.44
57.3 12.9
0.43 0.088
59.4 10.3
0.39 0.110
N-S-MLP
111.241444
0.12
10100 16.8
0.02
100.8
0.10
97.6 14.8
0.007
MCSL
49.0
0.62
10.0
0.10
9.6
0.73
3.7
0.00
5.90
0.00
6.3
0.44
27.9
0.47 0.088
Sep data
GES
3.31
0.18
31.6
0.00
3..0
0.00
30.5 10.7
0.01
DAG-GNN
2.29
0.66++0.08
2.0
0.60
18.5+:4.9
0.67 0.009
5.2
0.66 0.11
NOTEARS
16.3
0.61 0.008
15.5
0.00
15.0
0.62
1.92
0.61 0.009
N.S.MLP
68.0 6:00:... 5.4
0.80 +: 0.04
22.6
0.79 + 0.06
12.7 1: 2.6
0.80 0.05
11.8 2.8
0.80 0.05
MCSL
32.8,4 5.4
0.49 0.088
26.4 5.5
0.53
23.3 4.8
0.56++0.08
23.1 + 6.5
0.56 0.07
GS-FedDAG
11.6
0.83 = 0.11
7.1 6.1
0.12
6.2 4.7
0.89 - 0.09
6.0 5.5
0.91 =: 0.11
each individual due to individual properties, such as age, gender, etc. Also, the assumption that domain shifts can also come from the distribution shifts of the exogenous variables (noise terms our paper) has been widely accepted in the machine learning field, such as invariant causal prediction (Peters et al., 2016),
IRM (Arjovsky al., 2019).
35

---

Published in Transactions on Machine Learning Research (01/2023)
Table 17: Results on randomly selecting models- info of partial clients (heterogeneous data, 20 nodes, ER2).
Homogeneous data
Heterogeneous data
ER2 with nodes
ER2 with 20 nodes
ER2 with nodes
ER2 with 20 nodes
SHD 1
TPR f
SHD
TPR f
SHD 4
TPR f
SHD
TPR
10%
3.8 2.4
0.14
8.6
0.77
1.4
0.93 0.05
8.5
0.89 0.07
20%
2.0
0.81 0.12
6.7
0.13
2.5
0.97 1 0.04
8.2
0.87 0.09
50%
2.9
0.13
5.8144
0.85
1.
0.99
6.315.1
0.89
80%
1.7
0.14
6,0
0.10
1.3
0.99
5.9441
0.90
100%
2.0
0.86
6.2
0.85+
0.99 1.9
4.7
0.80
Table 18: Empirical results on fMRI Hippocampus dataset (Part 2).
All data
Separate data
GS-FodDAG
AS-FedDAG
GES
N-S-MLPP
DAG-GNN
GES
N-S-ML.
DAG-GNN
SHD
8.0
9.0
5.4
8.3 1.2
11.3
8.2
0.9
5.0 0.0
NNZ
11.0
1..0
0.8
8.5
1..4
1.7
0.6
5.0 0.0
TPR
0.00
0.40
0.00
0.44 0.11
0.17
0.11
0.29 - 0.00
FDR
0.000
0.75
0.52
0.11
0.78 1.0.5
0.80
0.72 0.111
0.60 0.00
PRc
PHc
ERc
Sub
DG
CA1
Figure 10: Anatomical causal-effect relationships of fMRI Hippocampus dataset
36


Reviews:
[{"review_id": "oux2lst24t", "reviewer": "Reviewer_8Jya", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S:\n1. It proposes a novel DAG learning method to handle the decentralized setting.\n2. Under mild assumptions, the proposed method achieves good empirical performance compared to various SOTA DAG learning methods including the most recent ones with gradient-based/ADMM optimization.\n\nW:\n1. It seems that assumption 3.1 is a sufficient condition for the method to work. I wonder if there is a possibility to further relax the assumption. Or in other words, can we allow the underlying DAG to be different for different subpopulations? For example, a group of DAGs sharing the same conditional independence?\n2. The work discussed communication time. It is better to explicitly write down the time complexity of communication w.r.t. r and d.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes federated DAG learning to enable decentralized learning which protects user privacy in the problem of DAG learning.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "See weakness.\nIn addition to that\n1. In 5.1.2, what does it mean by randomly sampling f_i^{ck} from GP, GP-add, MLP or MIM functions? How do you determine the parameters of those models? What is the probability to sample from each of those functions?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "p6M3bFZOto", "reviewer": "Reviewer_w1wx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses a new problem, which has not been only explored before. Even in comparison to the most similar setting of a concurrent work (Ng & Zhang, 2022), there is a clear improvement in settings with heterogeneous data.\n\n2. The paper is well-organized and well-written. This is a highly technical paper but it is not hard to understand the core idea thanks to the high-quality narrative. \n\n3. The experiments are well-organized and extensive.\n\nWeaknesses:\n\n1. The assumption of an invariant DAG across data silos is quite strong. I noticed that the authors had discussed this in F2 but the narrative there is somewhat incoherent -- there are two points: \n\n(1) \"Intuitively, different SEMs usually describe different systems. Then, naturally, the DAGs may be different. Following this logic, we would say yes that the invariant DAG assumptions among different SEMs are too strong\" ==> does this mean the assumption is not reasonable?\n\n(2) \"The assumption that domain shifts can come from the distribution shifts of the exogenous variables (noise terms in our paper) has been widely accepted, .... So there is no need to argue this one\" ==> I do not understand how this is related to the question \"Is our Invariant DAG assumption reasonable?\"  \n\nI am not quite sure I follow the stance of the authors on this matter from those narratives. But regardless, the assumption does appear a but unrealistic in my view. This is also one of my concerns in the previous review. Nonetheless, seeing that this is a relatively new problem and there is no existing work addressing anything beyond this setup, I would not consider this a serious dampener of the key contribution here. The authors should revise the discussion on this point though -- the current form of discussion is not very insightful.\n\n2. The current discussion of a related body of work in federated GNN (in C2) somehow misses a key difference between the two lines of work, which would strengthen the position of this paper: Most existing federated GNN assumes graphs are known and localized, what is being learned in federation is the weight aggregation of the GNN but not its graph. Citing some recent examples along this line would be good (not super important but for the sake of thoroughness)\n\n3. It is somewhat unclear what is the configuration for the reported performance of other continuous graph search method such as NOTEARS & DAG-GNN under the Separated Data partition of the tables. Are these averaged performance of siloed models or performance of their FedAvg variant (i.e., direct application of FedAvg on the entire parameterization of those methods)\n\n4. What is the performance of AS-FedDAG in heterogeneous setting in Table 3? If AS-FedDAG always outperforms GS-FedDAG, what is the motivation to personalize the conditional probabilities? Furthermore, what is the difference between AS-FedDAG and a coupling between FedAvg and variants of NOTEARS? \n\nI was under the impression that the position of this paper is unique because it allows personalization of the conditional probabilities and there is practical benefit to do so but seeing that AS-FedDAG (no personalization) outperforming GS-FedDAG (with personalization), I am a bit concerned about the practical merit of this position. \n\nBut perhaps this doubt will go away if the authors can elaborate more on the key differences between AS-FedDAG & FedAvg + variants of NOTEARS, as well as how the improved performance is tied to those differences. Or explain to me if I have misunderstood something. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "I have reviewed a previous version of this paper with a different positioning. This appears to be a re-positioning of the original paper following my suggestions, which is well done. I appreciate the effort the authors have spent to reposition the motivation of their work, which now highlights much better the key contribution. \n\nFor clarity, I quote my previous summary of this work below, which has been modified accordingly to the new position (the core content remains mostly the same).\n\n---\n\nThis paper expands on the previous work of NOTEARS (Zheng et al. 2018) and MCSL (Ng et al., 2022b) to develop a new federated structure learning framework. The structure is represented in terms of a directed acyclic probabilistic graphical model, which comprises (1) a DAG; and (2) a set of (learnable) conditional probabilities along its edges.   \n\nThe DAG is assumed to be the same (though unknown) across data silos but the conditional probabilities are heterogeneous. The conditional probabilities are therefore learned using local data (and are private to each silos) but the graph is learned collaboratively via a federated graph learning formulation with constraints. The constraint is adopted from NOTEARS (Zheng et al. 2018) & MCSL (Ng et al. 2022b) to enforced that the learned graph is a DAG, which defines a common differentiable search space on which direct application of FedAvg is possible. \n\nGoing by formulation, this work is very similar to a concurrent work of NOTEARS-ADMM (Ng & Zhang, 2022). But, the personalized setup for the conditional probabilities are different.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Revise & expand the discussion in C2 and F2 as I suggested above. In fact, F2 would really benefit from a rephrasing. The narrative in F2 is somewhat informal and partly disconnected from the main question it aims to answer (or perhaps this is the effect of the informal phrasing) -- e.g. \"The assumption that domain shifts can come from the distribution shifts of the exogenous variables (noise terms in our paper) has been widely accepted, .... So there is no need to argue this one\" --  this seems to be a response to another concern which got mixed up in the narrative.\n\n2. Addressing my questions no. 3. and 4. in the Weaknesses section, which seek clarification regarding the experiment setup of the other continuous graph learning baselines, as well as the practical merit of enabling personalization of the conditional probabilities.", "broader_impact_concerns": "There is still a concern about revealing local graph would leak information about clients. I raised this point before and the authors have responded to that with a detailed paragraph, which is fine except for a sentence that I do not get:\n\n\"However, graph structure sometimes may also be private information. This problem can also be easily solved by picking one client as\nthe proxy server.\" ==> private information would still then be leaked to the proxy server so how does this solve the problem? \n\nNonetheless, this is orthogonal to the main contribution (which focuses more on privacy compliance rather than privacy preservation against sophisticated attack) so it is fine to simply acknowledge the limitation.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "r4cDOHndR9", "reviewer": "Reviewer_MJsk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not have many technical comments. It makes sense to decentralize the causal graph discovery problem in the parametric ANM setting the way the authors are suggesting. However, there are several issues that should be addressed before acceptance.\n\nThe writing needs to be improved significantly. The use of the word IID throughout the paper is confusing. The paper also suffers many grammar mistakes. Experiments are slightly opaque in the sense that the proposed method outperforms even the centralized approaches and it is unclear why/how. The theoretical result is not related to the proposed method and does not add to the paper. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a decentralized method to learn causal graphs under the ANM assumption. The clients learn their own model and do not share the data but only the model parameters, which are then combined by a central entity and re-distributed back to the clients to continue their computation. Although the proposed method does not come with guarantees, there are several experiments that could be insightful. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "\"IID decentralized dataset\" throughout this paper.\nThis naming decision is a bit confusing. Independence is a property of different realizations in a dataset. How does a property among distributions imply the independence of samples?\n\nI believe the use of the word IID is very misleading throughout the paper. If I am understanding correctly, authors use IID when the distributions across different clients are the same. I recommend using \"no distribution shift\" or similar to describe this setting instead of IID. \n\nSection 3.1 seems redundant to me. It does not convey anything about the proposed algorithm. Under the parametric assumptions made in the paper, causal graph is already identifiable from one dataset. Why is it insightful to say it is also identifiable from several datasets? I recommend authors remove this section as it does not add anything to the paper. (see comments below for bringing in some results from appendix instead)\n\nSection 4:\n\"To solve the aforementioned problem\" I am not sure what problem is being referred to here (I know but this lacks clarity).\n\n\"relationship mechanisms \"\nplease drop the word relationship throughout the paper. the word mechanism already captures the causal relationship.\n\nSection E.1 should be in the main paper, not appendix.\n\n\"Why does our method outperforms other methods even some baseline methods using all data for\ntraining?\"\nThis section in the Appendix is very intriguing. But the explanation is not convincing. I am not sure how it's possible that the proposed method can **THAT SIGNIFICANTLY** outperform methods that use the full dataset - see Table 2 and Table 3. Also, can you add results in Table 1, i.e., in the linear setting, for methods that use full dataset as a sanity check? \n\nSection C.6 seems very important. I am not sure why it's deep in the appendix. In my opinion, it should be in the main paper. It discusses that the used objective function is sound, but the iterative process can only recover a stationary point of the loss. This is insightful and should be in the main text. \n\nThere are many grammatical mistakes and the paper should go through a spell check.\n\n\"for \\forall\" please drop the word for, throughout the paper.\n\nAppendix A.1:\"is also existed \" grammar.\n\npage 9:\n\"ADMM is used for address this issue\"\n\npage 11:\n\"see Figure ?? \"", "broader_impact_concerns": "I do not foresee adverse ethical implications of the proposed work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers with expertise in either federated learning or causal discovery who reviewed the original version of this manuscript agreed that the key contributions have been highlighted much better in this revised version. 
Decision: Accept (poster)