← All papers
First page of Graph Surgery and the Do-Operator: A Precise Correspondence for Acyclic Structural Causal Models

Graph Surgery and the Do-Operator: A Precise Correspondence for Acyclic Structural Causal Models

Satpreet Makhija

cs.AI Aug 18, 2026 · v2 cs.PL
All principal results on the do-operator and graph surgery for acyclic structural causal models are machine-checked in a Lean 4 development.
The $\operatorname{do}$-operator is described graphically by deleting arrows into its targets and functionally by replacing their mechanisms with constants. To call these operations equivalent is not yet a mathematical statement: one returns a graph and remembers only the targets, whereas the other returns mechanisms and also remembers the imposed values. We make a dependency-level comparison precise for deterministic acyclic structural causal models with finitely many endogenous variables. If $\operatorname{Graph}(F)$ extracts the dependencies of a mechanism family $F$, our main theorem is $\operatorname{Graph}(F^ι)=\operatorname{Surg}(\operatorname{Graph}(F),T_ι)$. Thus replacing target mechanisms removes exactly the dependencies removed by graph surgery. For a model $M=(G,F)$ whose graph may contain unused arrows, we characterize when the same equality holds with $G$ in place of $\operatorname{Graph}(F)$; it holds for every intervention exactly when $G$ records the dependencies of $F$ exactly. We then define the intervened model, characterize its run, show how sequential interventions combine, and prove that an outcome depends only on interventions at its actual dependency ancestors. All principal results are machine-checked in an accompanying Lean 4 development.

Interventions in structural causal models are described both graphically (deleting arrows into targets) and functionally (replacing mechanisms with constants), but these act on different objects and are not literally the same operation. A precise mathematical statement of their equivalence was lacking.

For deterministic acyclic structural causal models with finitely many endogenous variables, mechanisms are given a common domain so dependencies can be recovered from the functions themselves. The dependency graph Graph(F) is compared with graph surgery Surg after constant mechanism replacement. Sequential interventions, intervened models, runs, and dependence on ancestors are defined and analyzed. All principal results are mechanized in Lean 4.

The main theorem establishes Graph(F^ι)=Surg(Graph(F),T_ι), with a characterization of when the same equality holds for a supplied compatible graph (exactly when the model is exact). Sequential interventions combine by keeping the last assigned value, and an outcome depends only on interventions at its actual dependency ancestors. The Lean artifact pins dependencies and rejects proof placeholders or custom axioms.