🤖 AI

Regret-Based Federated Causal Discovery with Unknown Interventions

This paper proposes I-PERI, a novel federated algorithm that enables causal discovery under unknown client-level interventions by recovering a union graph and orienting additional edges to achieve a tighter $\Phi$ -Markov Equivalence Class, while providing theoretical guarantees on convergence and privacy.

Original authors: Federico Baldo, Charles K. Assaad

Published 2026-06-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Federico Baldo, Charles K. Assaad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of hospitals trying to figure out how different diseases, treatments, and patient outcomes are connected. They want to build a "map" of cause-and-effect (a causal graph) to understand what causes what. However, there's a big problem: they can't share their patient data because of privacy laws. This is where Federated Learning comes in—a way for them to collaborate without ever seeing each other's private files.

The paper introduces a new method called I-PERI to solve a specific puzzle in this scenario: What if every hospital is doing something slightly different to their patients?

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The "One-Size-Fits-All" Mistake

Most previous methods assumed that every hospital was running the exact same experiment on the exact same patients. They assumed the "rules of the game" were identical everywhere.

The Reality: In the real world, Hospital A might treat patients with a specific drug, while Hospital B uses a different protocol, and Hospital C might just observe without intervening. These different actions are called interventions.

The Analogy: Imagine trying to figure out how a car engine works.
- Hospital A is driving the car normally.
- Hospital B has removed the spark plugs (an intervention).
- Hospital C has taped over the fuel injector (another intervention).
- If you try to combine their reports assuming they are all driving normally, you get a confused, wrong map of how the engine works.

2. The Solution: I-PERI (The "Regret" Detective)

The authors propose I-PERI, a two-step detective process that works even when the hospitals don't know exactly what interventions the others are doing, and they can't share their raw data.

Step 1: Finding the Common Ground (The "Skeleton")
First, the system tries to find the parts of the map that are the same for everyone.

The Analogy: The central server asks each hospital: "If I draw a map of the engine, how much does it 'regret' not matching your local reality?"
Instead of sharing their full maps, the hospitals only send back a number representing this "regret" (a score of how wrong the server's map is compared to their local data).
The server adjusts its map to minimize the total regret. This helps them agree on the basic structure (the "skeleton") of the causal graph, ignoring the parts that were broken by interventions.

Step 2: Using the Differences to Fill in the Blanks
This is the clever part. Once the basic map is built, the system looks at the differences caused by the interventions.

The Analogy: Remember the spark plugs? When Hospital B removed them, the engine behaved in a specific way that revealed a hidden connection.
I-PERI looks at how the interventions at different hospitals changed the "shape" of the data. If an intervention at Hospital A creates a specific pattern (like a "V-shape" in the data) that wasn't visible before, the server uses that clue to draw a specific arrow on the map.
The Result: They end up with a much more detailed map than they could have made with just observational data. The authors call this new, tighter map the $\Phi$ -CPDAG.

3. Privacy: The "Blindfolded" Collaboration

The paper emphasizes that this method is designed to be private.

The Analogy: The hospitals never hand over their patient lists or their full engine blueprints. They only hand over a single number (the "regret score") and a few encrypted hints.
The authors prove mathematically that even if someone tries to spy on these numbers, they cannot reverse-engineer the private data of any single patient. They use a technique called Differential Privacy, which adds a tiny bit of "static noise" to the answers to hide individual contributions, much like adding a little static to a radio signal so you can't hear a specific person's voice, but you can still understand the song.

4. What They Proved

It Works: They showed that if you have enough data, this method will eventually find the most accurate map possible given the constraints (the $\Phi$ -Markov Equivalence Class).
It's Better: In their tests (using synthetic data that mimics real-world scenarios), I-PERI built more accurate maps than other existing methods, especially when the hospitals had different treatment protocols.
It's Fast: It runs significantly faster than other complex methods.

Summary

I-PERI is a new way for decentralized groups (like hospitals) to build a shared map of cause-and-effect. It doesn't pretend everyone is doing the same thing; instead, it uses the differences in what they are doing (the unknown interventions) as clues to draw a more precise map, all while keeping everyone's private data completely hidden.

Technical Summary: Regret-Based Federated Causal Discovery with Unknown Interventions

Problem Statement

Causal discovery from observational data typically recovers a Completed Partially Directed Acyclic Graph (CPDAG), representing a Markov Equivalence Class (MEC). While recent Federated Causal Discovery (FCD) methods address data decentralization and privacy, they rely on the idealized assumption that all clients share an identical causal model unaffected by interventions. In real-world federated settings (e.g., multi-center hospitals), client-specific policies and protocols naturally induce heterogeneous and unknown interventions. These interventions alter local causal structures (e.g., removing incoming edges via structural interventions), rendering standard FCD algorithms ineffective as they cannot distinguish between missing edges due to interventions versus missing edges due to the underlying causal structure. Furthermore, existing methods for causal discovery with unknown interventions assume centralized data pooling, which violates privacy constraints, or require known intervention targets, which is often unrealistic in federated environments.

Methodology: I-PERI

The authors propose I-PERI (Intervention-PERI), a novel federated algorithm designed to handle unknown client-level interventions while ensuring differential privacy. I-PERI extends the PERI algorithm by leveraging structural differences induced by interventions across clients to refine the global causal graph. The method operates in two distinct phases:

1. Federated CPDAG Recovery (Phase 1)

The first phase aims to recover the CPDAG common to all clients, denoted as $C(G)$ , from which all client-specific graphs are derived.

Challenge: Standard regret functions fail here because structural interventions remove edges, causing the client's CPDAG to be a subgraph of the true global CPDAG. Directly minimizing regret would penalize the server for "missing" edges that were actually removed by interventions.
Solution: I-PERI introduces Directed-Consensus Masking ( $\mu$ $μ$ ). Before computing the regret, the server graph is masked against each client's graph. This operation:
- Retains edges present in both graphs.
- Removes edges present in the server but absent in the client (acknowledging they may be intervention-induced).
- Orients undirected edges in the server graph if the corresponding client edge is directed.
Optimization: The algorithm minimizes the worst-case regret over the masked graphs:
$\hat{G} = \arg \min_{H \in C(G)} \max_{k} \left( L(\mu(H, C(G^{\Phi_k})), D_k) - L(C(G^{\Phi_k}), D_k) \right)$
where $L$ is a consistent scoring function (e.g., BIC). This ensures the server converges to the CPDAG of the underlying causal DAG $G$ .

2. Orientation Refinement (Phase 2)

The second phase exploits the fact that structural interventions can transform shielded colliders into unshielded colliders (v-structures), thereby revealing edge orientations that are ambiguous in purely observational data.

Mechanism: I-PERI uses Undirected-Consensus Masking ( $\nu$ ). In this mask, undirected edges take precedence over directed ones. The algorithm penalizes the server for failing to orient edges that are oriented in client graphs due to intervention-induced v-structures.
Optimization: The regret is computed over the undirected-masked graph:
$R_k(H) = L(\nu(H, C(G^{\Phi_k})), D_k) - L(C(G^{\Phi_k}), D_k)$
The search space is restricted to partially directed graphs derived from the Phase 1 CPDAG.

Privacy Guarantees

I-PERI is designed with $\epsilon$ -differential privacy in mind. Instead of sharing local graphs or model parameters, clients compute local regrets and add Laplace noise before transmission. The paper provides theoretical bounds on the sensitivity of the regret function, ensuring that the addition of noise does not significantly compromise the utility of the global graph recovery while protecting individual data points.

Key Contributions

$\Phi$ -Markov Equivalence Class ( $\Phi$ -MEC): The authors define a new equivalence class, the $\Phi$ -MEC, which is strictly tighter than the standard observational MEC but looser than the I-MEC (which requires known interventions). It represents the best possible recovery in a federated setting with unknown interventions.
$\Phi$ -CPDAG: A representative graph for the $\Phi$ -MEC, obtained by orienting edges in the standard CPDAG based on v-structures revealed by client-level interventions.
I-PERI Algorithm: A two-phase federated algorithm that recovers the $\Phi$ -CPDAG without requiring knowledge of intervention targets or sharing raw data.
Theoretical Guarantees: The paper provides proofs for the convergence of I-PERI to the $\Phi$ -CPDAG as sample sizes approach infinity, assuming causal sufficiency and faithfulness. It also establishes formal differential privacy guarantees.

Experimental Results

The authors evaluated I-PERI on linear synthetic datasets against state-of-the-art baselines (PERI, FedDAG, NOTEARS-ADMM, FedCDH).

Performance: I-PERI consistently outperformed baselines in terms of Structural Hamming Distance (SHD) and F1 score across varying numbers of variables ( $p \in \{3, \dots, 20\}$ ), clients ( $K$ ), and sample sizes ( $n$ ).
Edge Orientation: The second phase of I-PERI successfully oriented additional edges that were ambiguous in the initial CPDAG, demonstrating the utility of leveraging intervention-induced heterogeneity.
Efficiency: I-PERI exhibited significantly lower computational runtime (orders of magnitude faster) compared to competing methods.
Robustness: The method remained effective when using different local discovery algorithms (PC and GES) and showed consistent performance across homogeneous and heterogeneous sample size settings.

Significance and Claims

The paper claims that I-PERI addresses a critical gap in federated causal discovery by moving beyond the unrealistic assumption of homogeneous, non-intervened data.

Leveraging Heterogeneity: Unlike traditional federated learning where client heterogeneity is often treated as a noise source to be minimized, I-PERI treats intervention-induced structural differences as a source of information to refine causal orientation.
Privacy-Preserving Discovery: The work demonstrates that high-quality causal discovery can be achieved without centralizing data or revealing intervention targets, relying instead on regret-based aggregation with differential privacy.
Theoretical Advancement: By defining the $\Phi$ -MEC, the paper establishes the theoretical limits of what can be identified in federated settings with unknown interventions, providing a tighter bound than observational data alone.

The authors note that the accuracy of I-PERI depends on the quality of the local CPDAGs learned by clients and that the theoretical guarantees rely on standard assumptions (causal sufficiency, faithfulness) which may be violated in complex real-world scenarios. Future work is suggested to extend the framework to settings with latent variables and selection bias.