Federated Causal Structure Learning with Non-identical Variable Sets

$**Responses for “Questions For Authors” are as follows.**$

$**Q1**$. Does the term “an oracle of conditional independence tests” refer to perfectly accurate CI tests?

$**R1**$. Yes, “an oracle of conditional independence tests” refers to fully accurate CI tests.

$**Q2**$. Could the authors clarify the process of Alg.3?

$**R2**$. Algorithm 3 is proposed for implementing the designed two-level priority selection strategy (PSS). The inputs include the updated local causal graph Pag$_u^{c_k}$, sample size $n_k$, and stability matrix R$_s^{c_k}$ of each client, while the output is the global causal graph FedG over the integrated variable set $O$.

During aggregation, adjacencies are determined by comparing $val_{ij}$ (for $X_i$ and $X_j$) with 0. The computation of $val_{ij}$ depends on $w_{ij}^{c_k}$ and the sample size weight $w_{c_k}$. Specifically, if the relationship between $X_i$ and $X_j$ is stable, $w_{ij}^{c_k}$ is based solely on $w_{c_k}$. Otherwise, it is derived from the product of $w_{c_k}$ and the $w_{ij}$ value computed by each client (as Eq. (2)). Stability is encoded in the stability matrix, where each entry represents the stability score (2, -2, 1, -1) multiplied by the scaled p-value. Consequently, $w_{ij}$ is computed by dividing each entry by the corresponding stability score.

For orientation aggregation, only arrows are considered. If any local graph contains an arrow X→Y, it is incorporated into FedG as X $\circ\hspace{-0.43em}\rightarrow$ Y.

$**Q3**$. How does the communication cost scale with an increasing number of clients? Have you explored optimizations for reducing overhead?

$**R3**$. We have theoretically analyzed the communication cost of the proposed FedCDnv algorithm, which is $O(4md^2)$ and increases linearly with the number of clients. We are aware that the stability matrix R$_s^{c_k}$ contributes to communication costs. In future work, we will explore optimizations to reduce this overhead.

$**Q4**$. Can FedCDnv be extended to handle intervention data, given that CDUIOV explicitly models interventions?

$**R4**$. Yes, FedCDnv can be extended to handle interventional data. CDUIOV learns causal structures over the integrated set of variables from interventional datasets across multiple domains. It assumes that within each domain, interventions are performed on an identical set of variables. CDUIOV aims to address inconsistencies in causal relationships caused by unknown intervention targets and non-overlapping variable pairs. Therefore, when each client holds multiple interventional datasets, FedCDnv can integrate these local structures into a global causal graph while preserving data privacy.

$**Responses for “Weaknesses” are as follows.**$

$**Q5-1**$. Alg.3 seems a bit misleading.

$**R5-1**$. Please see R2.

$**Q5-2**$. Limited real-world dataset evaluation, with most results relying on benchmarks.

$**R5-2**$. We have conducted experiments using the real-world Sachs dataset, which consists of measurements from 11 phosphorylated proteins and phospholipids in individual cells. The experimental results are presented in Table 1 and Table 6. In addition, this study also has real-world applications. We found the eICU Collaborative Research Database (eICU-CRD) (link https://physionet.org/content/eicu-crd/2.0/), a real-world dataset available on the PhysioNet website, as a motivating example for applying FedCDnv (See R2 of Reviewer 2 for details).

$**Q5-3**$. There is no discussion of worst-case performance, making it unclear how FedCDnv behaves under extreme heterogeneity.

$**R5-3**$. In the experimental section, we analyzed the worst-case performance of FedCDnv under increasing heterogeneity. When the observed variables differ across clients, the data distribution of each client also varies. We experimentally evaluated the impact of different values of $\delta$ on FedCDnv's performance, where a lower $\delta$ indicates fewer overlapping variables and greater variation in sample distributions. Fig. 12 shows that as $\delta$ decreases from 95% to 60%, FedCDnv's performance drops by approximately 10%.

$**Responses for “Questions For Authors” are as follows.**$

$**R1**$. Our method handles distributed data with varying samples distributions, where the observed variable sets are non-identical. We also experimentally evaluate the impact of $\delta$ on FedCDnv's performance. A lower $\delta$ indicates fewer overlapping variables and greater variability in the sample distribution. Fig.12 shows that as $\delta$ decreases from 95% to 60%, FedCDnv's performance drops by approximately 10%.

$**R2**$. The "union" operation is applied only in the first aggregation phase, where adjacencies and arrowheads of all local graphs are transferred to a global graph. This global graph is then used to update the local graph in each client, without altering their skeletons and can even learn new orientations by using Zhang’s [2008 AI] rules (as illustrated in Fig. 3). The experiments in Figures 4-6 show a significant improvement in F1-orie.

$**R3-1 for Theorem 3.1**$. Theorem 3.1 assumes that <X,Y> is a non-overlapping variable pair. Under case (2.c), if A o→ X ←o Y o→ B holds, then any dataset observing X will not observe Y, indicating that $A_X^{G}$ cannot be {A,Y}.

$**R3-2 for Lemma 3.2 (First)**$. Sorry for this misunderstanding. $Z_n$ is the set of variables that appear in non-overlapping variable pairs. We will clarify it in the revised version.

$**R3-2 for Lemma 3.2 (Second)**$.

For case (1): Since the ground truth is unknown, we must consider both case(1) and case(2). When the condition in Lemma 3.2 is satisfied, either case (1) or (2) occurs, but we do not know which one occurs, which prevents us from guaranteeing the correctness of the learned relationships. Therefore, Lemma 3.2 claims it is non-definite.

For case (2): Due to the unknown ground truth, as long as there exists any case where the learned relationship is non-definite, then the learned relationship is considered non-definite. Therefore, the situation that "they are learned as non-causal" no longer needs to be considered.

$**R3-3 for Lemma 3.3**$. The proof does not assume that X and Y are adjacent in the local graph. It only assumes that X and Y are not adjacent in the ground truth. Here, the learned non-causal relationship between X and Y does not satisfy the condition "{A,B} $\subseteq \mathcal{A}_X^G \cup \mathcal{A}_Y^G$" in Lemma 3.3, meaning the premise does not hold, and thus it cannot be discussed in Lemma 3.3.

$**R4**$. We use FDR to evaluate the reliability of FeddG by quantifying the proportion of false discoveries, where FeddG is the graph extracting only definite relationships from FedG. In contrast, recall is defined as True Positives / (True Positives + False Negatives). Since the denominator (True Positives + False Negatives) remains unchanged before and after extraction, the recall of FeddG (Rec-dC, Rec-dnC) is necessarily lower than (or equal with) that of FedG (Rec-C, Rec-nC). This is expected because FeddG is a subset of FedG, excluding non-definite relationships. The experimental results confirm this trend, as shown in the table below (Due to limited space, only a few are shown here).

$**R5**$. Thanks for your comment, but there is no [1] that you mentioned.

$**R6-1 for Weaknesses (lines 179-181)**$. Thanks for your comment. If the adjacency between $X_i$ and $X_j$ is not a bidirected edge but takes forms such as $X_i$ o—o $X_j$, $X_i$ o→ $X_j$ and $X_i$ ←o $X_j$, we provide a condition to address such cases. Specifically, if for every $G_{k_n} \subseteq$ {$G_{k_n}$}, there exists $Z \subseteq O_{k_n}$ such that $X⊥Y∣Z$ holds in $D_{k_n}$, and in every $G_{k_a}\in$ {$G_{k_a}$}, the variables in $Z$ are never observed simultaneously ($X_i,X_j \notin Z$), then the conflicting adjacency arises due to non-identical observed variable sets. We will clarify this in the revised version.

$**R6-2 for Weaknesses (line 200)**$. If $X_i$ and $X_j$ are adjacent in $G_{k'}$, $p_{ij}^{c_k'}$ represents the average p-value from independence tests between $X_i$ and $X_j$ across all possible conditioning sets in $c_k'$. If $X_i$ and $X_j$ are non-adjacent in $G_{k'}$, $p_{ij}^{c_k'}$ corresponds to the p-value associated with the separating set that renders them independent.

$**Responses for “Questions For Authors" are as follows.**$

$**Q1**$. Could the authors provide a real-world motivating example where FCD is used/needed and there are non-overlapping variables observed by clients?

$**R1**$. Thanks for your comment. A real-world example where non-overlapping variables are observed can be found in the eICU Collaborative Research Database (eICU-CRD, link https://physionet.org/content/eicu-crd/2.0/) [1-3]. It is a multi-center intensive care unit database covering over 200,000 admissions to ICUs across the United States between 2014-2015. In the "vitalPeriodic.csv" file, different ICU stays (identified by "patientunitstayid") record partially overlapping physiological variables, as shown below:

In general, clinical practice requires access to up-to-date patient data from hospitals, which is often distributed and privacy-sensitive. Due to regulatory constraints such as HIPAA and institutional policies, hospitals cannot directly share raw and up-to-date patient data for collaborative analysis. This creates a critical need for federated causal structure learning with non-identical variables sets, which allows clients to collaboratively infer causal relationships over integrated variables while keeping data decentralized and secure.

[1] Pollard, T., Johnson, A., Raffa, J., Celi, L. A., Badawi, O., & Mark, R. (2019). eICU Collaborative Research Database (version 2.0). PhysioNet. https://doi.org/10.13026/C2WM1R.

[2] Nakayama LF, Restrepo D, Matos J, Ribeiro LZ, Malerbi FK, Celi LA, Regatieri CS. BRSET: A Brazilian Multilabel Ophthalmological Dataset of Retina Fundus Photos. PLOS Digit Health. 2024 Jul 11;3(7):e0000454. doi: 10.1371/journal.pdig.0000454. PMID: 38991014; PMCID: PMC11239107.

[3] Goldberger, A., Amaral, L., Glass, L., Hausdorff, J., Ivanov, P. C., Mark, R., ... & Stanley, H. E. (2000). PhysioBank, PhysioToolkit, and PhysioNet: Components of a new research resource for complex physiologic signals. Circulation [Online]. 101 (23), pp. e215–e220.

$**Responses for “Other Comments Or Suggestions" are as follows.**$

$**Q2-1**$. Figure 1 is never mentioned/referenced in the text.

$**R2-1**$. Thank you for pointing this out. We apologize for the oversight. Figure 1 is used in the fourth paragraph of the introduction to illustrate spurious dependencies, but it was not explicitly referenced in the text. In the revision, we will embed Figure 1 within the fourth paragraph of the introduction.

$**Q2-2**$. Line 294 Section 4.1 should read "real-world data." The error bars in the figures are hardly visible. I suggest either using error bands, or also displaying the whiskers (lines). Tables 1 and 2 contain too many significant digits to be easily legible. I suggest reporting figures to 2 or max 3 decimal places.

$**R2-2**$. Thanks for your suggestions. We revised the errors and carefully checked the manuscript. In addition, for the error bars, we replaced them with whiskers (lines) to make them clearer. For Tables 1, 2 and 6, we retained three decimal places and revised them accordingly. Thanks again.

$**Q1**$. Theorems 3.2 and 3.3 only indicate that the relationship between variables X and Y is uncertain, but do not analyze under what conditions their relationship can be determined.

$**R1**$. Thanks very much for your comment. As stated in line 114 of the manuscript, we initially assume that all relationships among overlapping variable pairs are definite (or "correct"). Theorems 3.2 and 3.3 are proposed to detect which of these relationships become non-definite due to the influence of non-overlapping variable pairs. Therefore, the relationships that satisfy the conditions of Theorems 3.2 and 3.3 are non-definite, while all other relationships remain definite.

$**Q2-1**$. How does the proposed method aggregate the results obtained from different servers?

$**R2-1**$. Thanks for your comment. There are two aggregation stages.

(1) For the first stage, the server integrates the adjacencies and orientations of local causal graphs learned by all clients into a global graph. For adjacencies, a variable pair is considered adjacent if any client reports the adjacency between them. For orientations (there are three types of orientations: circle 'o', tail '-', and arrow '>'), only the identified arrows are included in the global graph.

(2) For the second stage, the server applies the proposed two-level priority selection strategy to aggregate all updated local graphs. First, for adjacency aggregation: a) First Priority Level: Check whether adjacency conflicts arise due to non-overlapping variable pairs, using Lemma 3.4; b) Second Priority Level: If the conflict is due to statistical errors, the final adjacency is determined by comparing $val_{ij}$ (for $X_i$ and $X_j$) with 0. The computation of $val_{ij}$ depends on two factors: $w_{ij}^{c_k}$ and the sample size weight $w_{c_k}$. Second, for orientation aggregation, the process is similar to stage (1).

$**Q2-2**$. The paper discusses taking the union of variable sets and the union of edge sets. When the relationships between two variables differ, such as X \\circ\hspace{-0.4em}-\hspace{-0.4em}\circ\ Y, X $\circ\hspace{-0.43em}\rightarrow$ Y, and X$\rightarrow$Y, what does the union of edges look like?

$**R2-2**$. When the relationships between two variables differ across clients, only identified arrows are included. For example, for X \\circ\hspace{-0.4em}-\hspace{-0.4em}\circ\ Y, X $\circ\hspace{-0.43em}\rightarrow$ Y, and X$\rightarrow$Y, the final relationship between X and Y will be X $\circ\hspace{-0.43em}\rightarrow$ Y.