When causal structure is learned from observational data alone, the answer is not a single causal graph. It is a family of graphs that fit the data equally well, called a Markov equivalence class. The family is summarized by one partially oriented graph, the CPDAG (completed partially directed acyclic graph). In a CPDAG an arrow means every graph in the family agrees on that direction, and an undirected edge means the family disagrees. Downstream tools are built on this object: intervention planners, effect-bounding methods, and model-collapsibility checks. Today every one of them recomputes it from scratch whenever the graph changes. That happens when a streaming learner adds or drops an edge, when an analyst edits a hypothesis, or when an experiment orients an edge.
We propose an incremental algorithm whose cost per edit scales with how much of the CPDAG actually changes, which we call the recourse, and not with the size of the whole graph. We pair it with a study of how that recourse depends on graph density. The central conjecture is that recourse is not monotone in density. In sparse graphs, edits stay local. In fully dense graphs there are no v-structures to create or destroy. The worst cascades happen in between, where removing one edge can create many colliders, which are patterns $A \to B \leftarrow C$ with $A$ and $C$ non-adjacent, and can orient a large region at once. If this holds, it tells practitioners when incremental maintenance pays off and when a cheap rebuild is the better choice.
Core Claim
A single edge edit to a causal graph changes the CPDAG through two mechanisms. First, it changes which triples are v-structures, either creating a new unshielded collider or shielding an existing one. Second, the four Meek rules then propagate orientations outward. These rules are local logical inferences that orient further edges so as to avoid cycles and avoid creating new colliders.
Edits that only add orientations are monotone, so forward propagation from the edited endpoints is enough. Edits that destroy a v-structure are different. They can un-orient edges whose direction was forced only through that collider. This is the causal analogue of edge deletion in dynamic transitive closure, the hard direction for maintaining reachability under edits.
Our claim is that both directions can be handled exactly, with work proportional to recourse plus a boundary term. The boundary term covers edges we must inspect to confirm that propagation has stopped. The locality certificate comes from the result in Active Structure Learning of Causal DAGs via Directed Clique Tree. That paper decomposes a CPDAG's undirected parts into "residuals" and proves that Meek orientations do not leak between them. We reuse that non-leakage property as the stopping rule for un-orientation as well as orientation. We also maintain the clique tree of each undirected component alongside the CPDAG, so that downstream planners can consume it without rebuilding.
Position Relative to Prior Work
Three groups of papers motivate this work. All three treat the equivalence class or its decomposition as static.
The first group consists of intervention planners. The Directed Clique Tree paper above builds its decomposition once per equivalence class. Adaptivity Complexity for Causal Graph Discovery runs multi-round intervention design by balanced partitioning on clique trees, but against a fixed ground-truth graph and with clique trees built fresh. Meek Separators and Their Applications in Targeted Causal Discovery shows that small separators split undirected components, with costs scaling in the clique number. In every case the clique structure that our method maintains is recomputed whenever orientations change.
The second group is verification. DSCS verifies collapsibility directly on the CPDAG in linear time using maximum cardinality search. Faster algorithms for Markov equivalence tests whether two ancestral graphs are equivalent in $O(ne^2)$. Both are batch procedures. DSCS also supplies a reusable method for us: maximum cardinality search is how we rebuild a clique tree locally inside a changed component.
The third group is dynamic causal discovery. Dynamic Causal Structure Discovery and Causal Effect Estimation models time-varying coefficients smoothly by global optimization. It does not handle discrete structural edits, and it does not maintain any data structure across edits.
Two further papers constrain the design.
Average Case Analysis of Fully Dynamic Reachability for Directed Graphs gets constant-time reachability queries only above density $m > n^{4/3}$, using sampled shortcut nodes. It works only on fully directed graphs, so it cannot represent undirected edges or Meek forcing. We therefore do not build on shortcut structures.
Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion documents fill-in blowup, meaning chordal completion adds many edges on hub-heavy graphs. This is a warning, but it partly does not apply here. The undirected components of a CPDAG are already chordal, so maintaining their clique trees requires no fill-in. That is one reason the problem is more tractable than general dynamic chordal embedding. The density risk instead moves to clique size and cascade size, which we measure directly.
Research Program
The first part is the update model. The maintained object is the CPDAG of an underlying DAG, plus a clique tree for each undirected component. We support three update types:
- A directed edge insertion or deletion in the DAG.
- An interventional orientation, where an experiment reveals the true direction of an edge and the target becomes the interventional essential graph.
- A skeleton edit from a streaming constraint-based learner. Here the learner adds or removes an adjacency, and only the triples containing the changed pair have their collider status re-decided from stored separating sets.
The first type is the clean algorithmic setting. The third is the practical one.
The second part is the algorithm, which has two phases.
The orientation phase handles new colliders and new interventional orientations. It runs forward Meek propagation from the affected triples, using a work queue. It then splits the touched undirected component and updates that component's clique tree locally with maximum cardinality search.
The retraction phase handles destroyed colliders. It first marks every arrow whose forcing derivation passed through the destroyed collider. To make this possible we store, for each oriented edge, a small set of "supporting" triples, in the spirit of truth-maintenance systems. The phase then tentatively un-orients the marked arrows and re-runs forward propagation over the marked region. Edges that are re-forced by other support keep their direction.
Correctness is checked against full recomputation on every update in every experiment.
The third part is theory. We aim to prove that the region touched by either phase lies inside the union of the residuals of the Directed Clique Tree decomposition that contain the edited endpoints, together with the residuals reached by chains of Meek rule 1 (orient $b - c$ as $b \to c$ when $a \to b$ and $a$, $c$ are non-adjacent). That would yield a bound of the form work $= O(\text{recourse} \cdot \Delta)$, with $\Delta$ the maximum degree inside the touched region. Whether the retraction phase admits such a bound in the worst case is open. A negative answer, a family of graphs where one deletion forces $\Omega(m)$ inspection with $O(1)$ recourse, would be an equally publishable outcome.
The fourth part is the density study. We measure the distribution of recourse per edit as a function of expected degree, on random graphs and on edit streams over real networks. Our working hypothesis is a peak at intermediate density, with negligible recourse at both extremes. In very sparse graphs, residual clique sizes are tiny, consistent with Randomized Experimental Design for Causal Graph Discovery. That paper reports the largest remaining undirected clique hovering around 2 or 3 on random graphs with 15,000 vertices. In near-complete graphs, few non-adjacent pairs remain, so few colliders exist. If the peak exists, we will give a simple rule for when to rebuild: rebuild from scratch when the estimated touched region exceeds a constant fraction of $m$.
Baselines
The naive reference point is full recomputation after every edit. For the first update type, this means converting the DAG to its CPDAG from scratch, which takes time linear in the number of edges. For the second, it means re-running Meek closure from the full set of known orientations. For both, it also means rebuilding every clique tree with maximum cardinality search. We use the reference implementations in causal-learn, re-implemented in the same language as our method so constant factors are comparable.
This baseline is cheap and exact, which is exactly why it is dangerous. We expect it to win on small graphs. Beating it means two things. The method must have lower median per-edit time on graphs of at least about 1,000 nodes. Its worst-case per-edit time must also stay within a small constant factor of a full rebuild.
The strongest simple competitor is component-local recomputation. After an edit, this baseline re-derives orientations only inside the undirected components containing the edited endpoints, plus their directed neighborhoods, and rebuilds those clique trees. It captures most of the locality we claim without any support bookkeeping. It can be wrong when changes leak through chains of directed edges into further components. So we report both its error rate, measured against full recomputation, and its speed. Our method beats it only if it matches this baseline's speed while staying exactly correct. If this baseline turns out to be both fast and nearly always correct, that is a real finding and we will report it as such.
For downstream consumers, the strongest existing numbers are static rebuild times. The Directed Clique Tree paper reports that its intervention policy handles 500-node graphs in roughly 10 seconds. DSCS reports verification on MUNIN (1,041 nodes) in under a second, against over 15 seconds for its DCR baseline. It also reports just over 150 seconds on synthetic graphs with 10,000 nodes and 9,000 targets. We rerun both on our hardware, using the same graph sequences. We then compare the cumulative cost over an edit stream of rebuilding their inputs against maintaining them incrementally.
The key ablation is forward-only propagation, our method with the retraction phase removed. It isolates the support bookkeeping. On streams containing collider-destroying edits it should produce incorrect CPDAGs, and we report how often it does and how many edges are wrong. A second ablation drops residual-based stopping and propagates until the queue empties, which tests whether the locality certificate saves work. All methods get identical update streams, a single CPU thread, and no tuning beyond the rebuild threshold. That threshold is selected on held-out random graphs.
Why not just…?
Why not just recompute the CPDAG from scratch? It is linear time. For small graphs and rare edits, this is the right answer, and we expect our experiments to show it. The case for incremental maintenance rests on three things. Graphs must be large (MUNIN-scale and up to 10,000 nodes). Edits must be frequent, as in intervention loops and streaming learners. Most important, the clique trees and separators used by the planners in Adaptivity Complexity for Causal Graph Discovery and Meek Separators must be rebuilt along with the CPDAG. The decisive measurement is the crossover graph size at which incremental maintenance wins on cumulative cost. If that crossover sits above any realistic graph size, the method has no practical value.
Why not just run Meek rules forward from the edited edge? That is complete for edits that only add orientations. It is unsound when an edit shields a collider, because arrows forced through that collider must be retracted. The forward-only ablation measures exactly how often this happens and how large the resulting errors are, broken down by density. If collider-destroying edits turn out to be rare in realistic streams, the simpler method may suffice, and we will say so.
Why not avoid equivalence classes by assuming nonlinear additive noise? Under nonlinear mechanisms with additive noise, as in Nonlinear causal discovery with additive noise models, every edge is in principle orientable, so there would be no ambiguity to maintain. But OCDB reports that functional methods such as DirectLiNGAM succeed on meteorology data and falter on protein signaling. Equivalence classes therefore remain the safe output when mechanism assumptions are uncertain. We do not run this comparison, because it is a different estimand rather than a competing algorithm.
Why not use dense matrix updates or dynamic reachability structures? Algebraic and array-based methods waste work on sparse graphs, as shown in All-Hops Shortest Paths and Array-based graph traversal. The shortcut structure of Alimonti et al. needs density above $n^{4/3}$ and has no notion of undirected edges or forced orientation. We include a dense-matrix Meek closure only as a timing reference on the densest random graphs.
Proposed Experiments
We use four groups of experiments.
The first uses random graphs. We take Erdős–Rényi DAGs with $n$ from 100 to 10,000 and sweep expected degree from 1 to about $n/4$. On each graph we apply streams of 10,000 random edits that mix insertions, deletions, and orientations. We record per-edit wall-clock time, recourse (the number of edge marks that change), edges inspected, and agreement with full recomputation.
The second uses the bnlearn networks Alarm, Hepar2, Pathfinder, and MUNIN under the same edit streams. Here the density structure is realistic and heterogeneous.
The third is an intervention loop. We run the Directed Clique Tree policy and the clique-tree partitioning planner on these networks. One arm uses incrementally maintained clique trees and the other rebuilds them, and we report total planning time over a full discovery run. The interventions chosen must be identical in both arms, which serves as a check that maintenance is exact.
The fourth is streaming learning. We sample data from the bnlearn networks, run an online constraint-based learner that emits skeleton edits as samples accumulate, and maintain the CPDAG under the third update type. We evaluate accuracy with the structure distance and effect distance metrics from OCDB, alongside update latency.
We do not use the German COVID-19 data. Its variation is in coefficients, not structure.
Three results would decide the outcome. First, the median recourse curve against density should show a peak at intermediate density; a monotone curve would refute the conjecture. Second, incremental maintenance should be exact on every edit and should beat component-local recomputation in cumulative time above a graph size we report. If it does not, we conclude that the simple local rebuild suffices. Third, the measured work-to-recourse ratio should stay bounded by local degree. If it grows with $n$ on some graph family, that is evidence for the worst-case lower bound rather than the conjectured upper bound.
References
- Active Structure Learning of Causal DAGs via Directed Clique Trees
- Adaptivity Complexity for Causal Graph Discovery
- Meek Separators and Their Applications in Targeted Causal Discovery
- DSCS: Fast CPDAG-Based Verification of Collapsible Submodels in High-Dimensional Bayesian Networks
- Faster algorithms for Markov equivalence
- Dynamic Causal Structure Discovery and Causal Effect Estimation
- Average Case Analysis of Fully Dynamic Reachability for Directed Graphs
- Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion
- Randomized Experimental Design for Causal Graph Discovery
- Causal-learn: Causal Discovery in Python
- Nonlinear causal discovery with additive noise models
- OCDB: Revisiting Causal Discovery with a Comprehensive Benchmark and Evaluation Framework
- All-Hops Shortest Paths
- Parallel Array-Based Single- and Multi-Source Breadth First Searches on Large Dense Graphs