💻 computer science

Global Constraint-Based Causal Structure Learning with Streaming Features

This paper introduces FCI-SF, the first globally consistent, constraint-based algorithm for causal structure learning with streaming features, which efficiently updates causal graphs as new data arrives while providing formal asymptotic guarantees and demonstrating superior accuracy and speed on both synthetic and real-world datasets.

Original authors: Jose M. De Miguel, Concha Bielza, Pedro Larrañaga

Published 2026-10-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jose M. De Miguel, Concha Bielza, Pedro Larrañaga

Original paper licensed under CC BY 4.0 (https://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

In the vast landscape of modern science, researchers often face a puzzle that grows more complex with every new piece of data they gather. Imagine trying to understand why a machine breaks down or why a patient improves after a treatment. The goal is to move beyond simple observation and discover the actual chain of cause and effect. This field, known as causal discovery, seeks to map out how different factors influence one another, distinguishing true causes from mere coincidences. For decades, scientists have relied on statistical tests to build these maps, but these methods usually require a complete list of all possible factors before they can begin. This works well in a controlled lab, but it struggles in the real world, where new information often arrives piece by piece over time, like a stream of news updates or a continuous flow of sensor readings.

This is where a new challenge arises: how do you update your understanding of a system when you don't know all the variables yet? Traditional methods would have to throw away their previous work and start over from scratch every time a new piece of data appeared, a process that is slow and wasteful. A team of researchers from the Universidad Politécnica de Madrid has developed a smarter way to handle this. They created a new method called FCI-SF, designed specifically for situations where features, or variables, arrive in a streaming fashion. Their approach allows the computer to learn from the past and build upon it, rather than forgetting everything and starting again.

The core of this new method is a strategy that respects the work already done. In the world of causal discovery, researchers look for patterns where two things are unrelated to each other once you account for a third factor. These patterns, called conditional independence, act like clues that tell the computer which connections to keep and which to discard. The researchers proved a fundamental rule for their new system: if two factors were found to be unrelated in an earlier stage, they will remain unrelated even as new factors are added later. This insight, which they call the independence preservation property, is the key that unlocks the ability to update the map without redrawing the whole thing. It means the algorithm can remember which connections were already ruled out and only focus its energy on testing the new possibilities introduced by the latest data.

To test this idea, the team ran extensive experiments using both computer-generated data and real-world datasets. They compared their new method against several existing techniques that try to solve the same problem. The results showed that their approach was not only accurate but also remarkably fast. In their tests, the new method was nearly twenty times faster than the next best alternative for streaming data. While other methods struggled to keep up with the growing volume of information, often taking days to process large sets of variables, this new algorithm handled the same tasks in a fraction of the time. It achieved this speed without sacrificing accuracy, maintaining a level of precision that matched the best methods used when all data is available at once.

The researchers also applied their method to a real biological problem involving the genetic network of the Arabidopsis thaliana plant, a common model organism in science. They simulated a scenario where genes were revealed one by one, mimicking how a biologist might discover new information over time. As the new genetic data arrived, the algorithm successfully updated its map of how the genes interact. The resulting structure aligned well with established biological pathways, correctly identifying known relationships and suggesting plausible new connections. This demonstrated that the method works not just in theory or on simple computer simulations, but on complex, messy data from the real world.

The team made their work available to the public through an open-source software package, allowing other scientists to use and build upon their findings. By providing a tool that is both theoretically sound and computationally efficient, they have offered a practical solution for a growing problem in data science. As the world generates more data than ever before, often in a continuous stream, the ability to learn from it incrementally without losing previous insights becomes increasingly vital. This new method offers a way to keep pace with that flow, turning a potentially overwhelming stream of information into a clear, evolving picture of cause and effect.

Technical Summary: Global Constraint-Based Causal Structure Learning with Streaming Features

1. Problem Statement

Causal discovery faces significant challenges in Streaming Features (SF) settings, where the set of variables describing a system expands progressively over time (e.g., real-time news in social networks or new measurements in long-lead flood prediction). Traditional constraint-based causal discovery algorithms, such as Fast Causal Inference (FCI), assume a fixed set of observed variables. Consequently, they must relearn the entire causal structure from scratch whenever a new batch of features arrives, leading to computational inefficiency.

Existing SF-specific methods are predominantly local (learning neighborhoods of variables one by one) and often rely on the assumption of causal sufficiency (no unobserved common causes). This assumption is particularly restrictive in SF settings, as a variable initially unobserved (a potential confounder) may become observable later. Furthermore, current SF approaches lack formal asymptotic consistency guarantees, meaning they do not theoretically guarantee the recovery of the correct Markov equivalence class even with perfect conditional independence (CI) information in the large-sample limit.

2. Methodology: FCI-SF

The authors propose FCI-SF, a global, feature-wise incremental extension of the FCI algorithm designed for the SF setting. Unlike local methods, FCI-SF updates the global causal structure (represented as a Partial Ancestral Graph, or PAG) whenever new features arrive.

Theoretical Foundation: Independence Preservation

A core theoretical contribution is the establishment of the Independence Preservation Property. The authors prove that if the data-generating distributions for the old features ( $P_{old}$ ) and the new features ( $P_{new}$ ) are latent projections of a single underlying distribution ( $P^*$ ) satisfying the causal Markov and faithfulness assumptions, then:

Any pair of features that are non-adjacent in the causal graph of the old features ( $G_{old}$ ) remain non-adjacent in the graph of the new features ( $G_{new}$ ).
New features may introduce new independencies, but they do not eliminate existing ones between previously observed variables.

This property allows the algorithm to reuse previously inferred structural information and CI tests, avoiding redundant computations.

Algorithmic Mechanics

FCI-SF follows the five phases of the standard FCI algorithm but modifies the skeleton discovery phases (1 and 3) to be incremental:

Input: The algorithm takes the previously learned PAG ( $P_{old}$ ), the separating sets ( $Sep_{old}$ ), the augmented dataset ( $D_{new}$ ), and the new features ( $H_{new}$ ).
Initialization (Phase 1):
- It constructs an initial skeleton by inheriting adjacencies from $P_{old}$ for the old features.
- It creates a complete undirected graph over the new features and connects every new feature to every old feature.
- It initializes separating sets for old feature pairs using $Sep_{old}$ .
Incremental CI Testing:
- The algorithm performs CI tests only if the conditioning set or the endpoints involve at least one new feature.
- Tests involving exclusively old features are skipped, as their results are preserved by the independence preservation property.
- However, if a new feature provides a separating set for a pair of old features that was previously unseparable, the edge between them is removed.
Orientation (Phases 2–5):
- After pruning the skeleton, the algorithm proceeds with standard FCI orientation rules (orienting v-structures and applying graphical rules $R1-R10$ ) to produce the updated PAG.

Theoretical Guarantees

The authors prove that FCI-SF is asymptotically consistent. In the large-sample limit, assuming a consistent CI test, the output of FCI-SF converges to the maximally informative PAG representing the latent projection of the true underlying causal graph onto the observed feature set.

3. Key Contributions

First Global Incremental Algorithm with Guarantees: FCI-SF is the first constraint-based algorithm for streaming features that is both global (updating the full graph) and possesses formal asymptotic consistency guarantees.
Handling Latent Confounding: Unlike most existing SF methods, FCI-SF explicitly accommodates latent confounding and selection effects, making it suitable for scenarios where new confounders may appear over time.
Independence Preservation Property: The paper establishes a theoretical result showing that edges removed in earlier stages of learning remain absent as new variables become observable, enabling the reuse of CI information.
Open-Source Implementation: The authors released a Python package implementing FCI-SF and all other state-of-the-art causal discovery methods for the SF setting, facilitating reproducibility and systematic comparison.

4. Experimental Results

The authors evaluated FCI-SF on both synthetic and real-world datasets.

Synthetic Experiments

Accuracy: FCI-SF achieved graphical accuracies (measured by F1 score, Hamming distance, and Cohen's $\kappa$ ) comparable to the standard FCI algorithm (which relearns from scratch) and significantly outperformed other SF-specific methods (S-CDFSF, CSBS, CSSU, PRCDSF, LiNGAM-SF).
Efficiency: FCI-SF was approximately 20 times faster than the second-fastest competing SF method (CSBS) and reduced execution time by 44% compared to rerunning FCI from scratch. It also halved the number of CI tests required compared to FCI-Stable.
Scalability: The method demonstrated substantial computational savings, particularly when incoming feature batches were small relative to the accumulated feature set.

Real-World Experiments

Self-Compatibility: On nine real-world datasets without known ground truth, FCI-SF achieved the best average rank in graphical self-compatibility (a metric assessing the mutual compatibility of structures learned from different variable subsets).
Biological Case Study: In an incremental analysis of the Arabidopsis thaliana isoprenoid network, FCI-SF recovered structures broadly consistent with established biological pathways (MVA and MEP pathways). The algorithm successfully identified causal directions consistent with known upstream-to-downstream progressions as new gene features were introduced.

5. Significance and Claims

The paper positions FCI-SF as a theoretically grounded and computationally efficient solution for incremental causal discovery. Its primary significance lies in bridging the gap between the computational efficiency required for streaming data and the rigorous theoretical guarantees (asymptotic consistency and handling of latent variables) traditionally associated with global constraint-based methods.

The authors claim that FCI-SF is the first algorithm to offer:

A global incremental approach for streaming features.
Formal asymptotic consistency guarantees in this setting.
Explicit handling of latent confounding without assuming causal sufficiency.

The work concludes that while graph operations like marginalization remain computationally demanding, FCI-SF provides a principled framework for updating causal models as data evolves, avoiding the prohibitive cost of relearning from scratch while maintaining high structural accuracy.