Regret-Based Federated Causal Discovery with Unknown Interventions

AI summary

Overview

Research area: Causal discovery and federated learning — specifically, learning causal graphs from data that is distributed across multiple clients (such as hospitals) that do not share their raw data.

Technical level: Advanced. The paper is heavily theoretical, building on graphical-model theory (d-separation, Markov equivalence classes, CPDAGs), score-based structure learning, and differential privacy.

Scope in one sentence: The paper defines a new, tighter equivalence class (the Φ-Markov Equivalence Class, represented by a Φ-CPDAG) for federated causal discovery when each client is subject to its own unknown interventions, and proposes I-PERI, a differentially private algorithm that recovers it by exchanging only regret values.

What This Paper Is About

Most causal discovery methods recover a completed partially directed acyclic graph (CPDAG) from observational data, and recent federated versions assume every client shares the same causal model. That assumption breaks down in practice: different hospitals, for instance, apply different treatment policies, diagnostic protocols, or patient inclusion criteria, which act as client-specific interventions that the server does not know about. This paper's goal is to recover as much causal structure as possible in a federated setting where those client-level interventions are unknown, while still giving formal privacy guarantees.

Key Contributions

1. A new equivalence class. The authors introduce the Φ-Markov Equivalence Class (Φ-MEC) for a set of unknown interventions in a federated setting. It is strictly tighter than the standard observational MEC, but looser than the ℐ-MEC that is attainable when interventions are known. They also define its graphical representative, the Φ-CPDAG.

2. A new algorithm, I-PERI. I-PERI (Intervention-PERI) extends the existing PERI algorithm with a two-phase approach: it first recovers the CPDAG common to all clients, then orients additional edges by exploiting structural differences induced by interventions across clients. It does not require knowledge of the intervention targets and works with any client-level causal discovery method that returns a CPDAG, such as PC or GES.

3. Theoretical guarantees. The paper proves convergence of I-PERI (Theorem 3.1 for the first phase, Theorem 3.3 for the full algorithm), characterizes the Φ-MEC graphically (Theorem 3.2), proves the uniqueness of the Φ-CPDAG within a Φ-MEC (Corollary 3.1), and establishes ε-differential privacy of the regret-sharing procedure (Lemma 3.1, Proposition 3.1).

4. Empirical evaluation. The algorithm is benchmarked against PERI, NOTEARS-ADMM, and FedDAG on synthetic data, across varying numbers of variables, clients, and per-client samples.

Main Findings

• Two masking operators do the work. Directed-consensus masking (μ) removes from the server graph any edges absent in a client graph and orients undirected server edges according to the client, so that edges missing at the client level — possibly removed by an intervention — are not penalized. Undirected-consensus masking (ν) instead removes edges that are oriented in the client but undirected in the server, letting undirected edges take precedence, which drives the orientation-refinement phase.

• Convergence to the Φ-CPDAG, not just the CPDAG. Under Assumption 2.1 (at least one client holds purely observational data), a consistent scoring function L, and known client-level CPDAGs, the server graph Ĝ converges to 𝒞(G) in the first phase and to Φ(G), the Φ-CPDAG, in the full algorithm, as the client sample sizes n¹, …, n^K go to infinity. Causal sufficiency and faithfulness are not stated explicitly in the theorems because the client CPDAGs are assumed available; when they are not, PC or GES can estimate them under those assumptions.

• The Φ-CPDAG sits between two known classes. Figure 5 illustrates that in a simple two-node case, interventions provide no extra information in the federated setting, so the Φ-CPDAG equals the observational CPDAG. When an intervention reveals a v-structure — for example, when a structural intervention on the parents of a shielded collider turns it into an unshielded one — additional edges in the observational CPDAG can be oriented, making the Φ-CPDAG tighter than the CPDAG but still looser than the ℐ-CPDAG.

• Φ-Markov equivalence has a clean graphical characterization. Two server graphs G¹ and G² belong to the same Φ-MEC if and only if they (1) have the same skeleton, (2) have the same v-structures, and (3) agree on which extra v-structures appear in some intervened mutilated graph. Notably, the definition does not require the two graphs to share the same intervention targets, nor does it require the intervened graphs to share the same skeleton (illustrated by Figure 4).

• The Φ-CPDAG is unique. Corollary 3.1 shows that if (G¹, Φ₁) and (G², Φ₂) are Φ-Markov equivalent, then their Φ-CPDAGs are identical — Φ₁(G¹) = Φ₂(G²).

• Privacy is quantified. Regret sharing leaks less than sharing local graphs or model parameters. The paper bounds the sensitivity of the regret function by (2M + 1) log r² + 𝒪(log n / n) under stated assumptions (probability uniformly lower-bounded by r, parameters bounded by M, partially differentiable score), and shows that adding i.i.d. Laplace noise of scale λ = Q/ε gives ε-differential privacy, where Q bounds the sensitivity. The authors note that their bound corrects a minor mistake in the original proof of Mian et al. (2023). They also note that reconstructing a client's local graph from the shared regrets and global graph is possible in principle but NP-hard (Chickering et al., 2004).

• Synthetic benchmark results. Table 1 reports average SHD (lower is better) and F1 (higher is better) over 10 random seeds as the number of variables p grows. I-PERI achieves the best SHD at p = 3 (1.53 ± 1.16 vs. PERI 3.16 ± 0.55, NOTEARS-ADMM 1.64 ± 1.06, FedDAG 3.01 ± 1.89), at p = 4 (2.87 ± 1.88 vs. 4.43 ± 1.13, 2.99 ± 1.44, 3.46 ± 2.39), at p = 8 (4.44 ± 3.04 vs. 8.40 ± 0.51, 8.44 ± 2.55, 6.68 ± 2.61), at p = 10 (9.85 ± 3.43 vs. 11.75 ± 2.21, 13.70 ± 3.27, 9.04 ± 4.52), and at p = 20 (27.8 ± 4.79 vs. 30.0 ± 10.02, 29.45 ± 6.29, 30.74 ± 5.55). I-PERI also has the highest F1 at p = 3 (0.75 ± 0.23). At larger p, I-PERI's F1 is 0.69 ± 0.19 (p = 4), 0.74 ± 0.16 (p = 8), 0.58 ± 0.16 (p = 10), and 0.51 ± 0.07 (p = 20), so it does not dominate on F1 at every graph size. The FedDAG F1 entries and the remainder of Table 1 are cut off in the available text, so those values are not reported here.

• Scaling behavior is shown graphically. Figure 6 reports results on linear synthetic data using PC to discover client CPDAGs, comparing SHD and F1 across baselines as the number of clients K increases (left) and as per-client sample size n increases (right), with error bars representing confidence intervals.

Methodology in Plain English

The starting point is PERI, a federated method that finds the graph minimizing the worst-case regret across clients — the gap between a candidate global graph's score and the client's own best graph's score — so that clients only ever transmit numbers, not graphs or data. PERI assumes every client sees the same, unintervened causal system.

I-PERI keeps the regret-based exchange but changes what is compared. In the first phase, before computing a client's regret, the server graph is masked against the client graph: edges the client does not have are dropped, and undirected server edges are oriented to match the client. This is essential because a client may be missing an edge purely because an intervention removed it, and penalizing that would prevent convergence. What remains penalized is the opposite case: edges present in the client graph but absent from the server graph. The server then greedily adds and removes edges, as in Greedy Equivalence Search, until the worst-case regret is minimized, yielding the CPDAG common to all clients.

The second phase then exploits a side effect of interventions: structurally intervening on a collider's parent can turn a shielded collider into an unshielded one, which creates a new v-structure and therefore new orientation information. Here the masking is changed so that undirected edges take precedence over directed ones — edges that were intervened on at the client level are removed from the mask, and undirected server edges stay undirected. Because the score considers both possible orientations of an undirected edge, minimizing the regret pushes the server graph to orient those edges the way the clients do. If a client only has observational or parametric-intervention data, this phase simply causes no further change.

Finally, the regret is made private by adding Laplace noise calibrated to the regret's sensitivity before it is sent to the server.

Why This Matters

Impact on research. Standard federated causal discovery assumes homogeneity across clients; this paper formalizes what is actually recoverable when that assumption fails. The Φ-MEC and Φ-CPDAG give the field a new identifiability target that is provably better than the observational MEC yet provably weaker than the known-intervention ℐ-MEC, and the regret-based formulation shows that useful orientation information can be extracted without ever revealing or inferring the intervention targets.

Real-world applications:

• Multi-hospital studies: hospitals apply different treatment policies, diagnostic protocols, and patient inclusion criteria, which act as unrecorded interventions; I-PERI lets them jointly learn a causal graph without revealing those policies or their patient data.
• Multi-site clinical trials: trials with distinct eligibility criteria and intervention strategies produce heterogeneous causal mechanisms that a single pooled analysis would misrepresent.
• Regulated data domains: any setting where data sharing is restricted by regulatory requirements, data ownership constraints, or privacy concerns rather than merely by logistics — the algorithm is differentially private by design, without relying on cryptography.
• Federated deployments across institutions, organizations, or devices: the method assumes only that each client can run a standard CPDAG-returning discovery algorithm locally (PC or GES) and report a scalar.

Industry relevance. Organizations that hold sensitive data in silos — healthcare networks, insurers, banks, and platforms with per-device data — need causal structure for decision-making but cannot pool records. An approach that exchanges only privacy-protected regret values, and that tolerates the fact that different sites genuinely operate under different policies, is directly deployable where pooled-data approaches and homogeneity assumptions both fail.

Future Directions

• Relaxing the observational-client requirement. Assumption 2.1 requires at least one client with purely observational data (Φᵏ = ∅). What happens when every client is intervened upon is left open.
• Unknown client CPDAGs and finite samples. The convergence theorems assume each client's CPDAG 𝒞(G_{Φᵏ}) is known; the paper only notes that PC or GES could estimate it under causal sufficiency and faithfulness. The finite-sample behavior of that pipeline is not characterized beyond the experiments.
• Recovering intervention targets. The authors observe that reconstructing a client's local graph from shared regrets and the global graph would reveal client-level interventions, but that this reconstruction is NP-hard. Whether that hardness translates into a practical privacy barrier, and how the Φ-CPDAG compares in tightness to other partially oriented targets, remain questions.
• Beyond structural interventions. The paper focuses on structural interventions because they are the most challenging case and states the algorithm remains sound with parametric interventions or none; the extent to which parametric interventions could be exploited for extra orientation is not pursued. Additional experimental details are deferred to the appendix, which is not included in the available text.

Target Audience

Researchers and graduate students in causal inference, federated learning, and privacy-preserving machine learning; methodologists working on multi-site or multi-institution data who need identifiability guarantees under heterogeneous, undocumented conditions; and practitioners in healthcare, insurance, or any regulated domain where causal structure must be learned without pooling data or disclosing site-specific policy. Readers should be comfortable with directed acyclic graphs, Markov equivalence classes, CPDAGs, d-separation, score-based structure learning, and the basics of differential privacy.

Authors’ abstract

Most causal discovery methods recover a completed partially directed acyclic graph representing a Markov equivalence class from observational data. Recent work has extended these methods to federated settings to address data decentralization and privacy constraints, but often under idealized assumptions that all clients share the same causal model. Such assumptions are unrealistic in practice, as client-specific policies or protocols, for example, across hospitals, naturally induce heterogeneous and unknown interventions. In this work, we address federated causal discovery under unknown client-level interventions. We propose I-PERI, a novel federated algorithm that first recovers the CPDAG of the union of client graphs and then orients additional edges by exploiting structural differences induced by interventions across clients. This yields a tighter equivalence class, which we call the $\mathbfΦ$-Markov Equivalence Class, represented by the $\mathbfΦ$-CPDAG. We provide theoretical guarantees on the convergence of I-PERI, as well as on its privacy-preserving properties, and present empirical evaluations on synthetic data demonstrating the effectiveness of the proposed algorithm.