Source-linked AI summary
Graph Surgery and the Do-Operator: A Precise Correspondence for Acyclic Structural Causal Models
Satpreet Makhija
TL;DR
Graph surgery and constant mechanism replacement are called equivalent for interventions, but they operate on different objects and graph surgery does not retain assigned values. This paper formalizes their correspondence at the dependency level for finite deterministic acyclic structural causal models and proves matching dependency graphs, with exactness conditions for supplied graphs and laws for sequential interventions and ancestor-based outcomes.
Problem
The paper addresses the need to make precise whether deleting incoming arrows and replacing target mechanisms by constants are equivalent intervention operations.
Method
The paper compares dependencies extracted after mechanism replacement with dependencies obtained by graph surgery for deterministic acyclic models with finitely many endogenous variables.
Results
Graph surgery and constant mechanism replacement yield the same dependency graph; supplied-graph equality holds for every intervention exactly when the model is exact, with sequential and ancestor-dependence theorems.
Takeaways & Limitations
The results provide a direct formal specification of the do-operator while keeping its graph-based and functional components distinct.
Takeaways & Limitations
Dependence on actual intervention ancestors is sufficient but not necessary because functional cancellation can make an ancestor intervention irrelevant to an outcome.
Abstract
from arXiv · showhide
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.
1 Introduction
The section formalizes intervention by comparing the dependencies preserved after graph surgery and constant mechanism replacement in deterministic acyclic structural causal models. It introduces the model framework and states results on exactness, sequential interventions, and dependency ancestors.
- Motivation: The do-operator replaces a target variable’s ordinary mechanism with an experimenter-supplied constant, motivating a formal semantics for the resulting model.The intervention do(A = a) holds A at a rather than computing it normally.
- Motivation: Graph surgery and mechanism replacement act on different objects, so their equivalence is made precise by comparing the dependencies that remain.Graph surgery cannot distinguish do(A = 0) from do(A = 1), whereas mechanism replacement retains imposed values.
- Model framework: The framework uses a causal model M = (G, F), where G permits dependencies and F computes values; exactness means G contains precisely F’s dependencies.Compatibility requires used dependencies to appear as arrows, but permits unused arrows.
- Main correspondence: For a simultaneous intervention ι, surgery deletes arrows entering its targets while F^ι replaces their mechanisms with supplied constants, yielding the same dependency graph either way.The central correspondence is: Graph(F^ι) = Surg(Graph(F), T_ι).
- Further results: The section also states results characterizing model-level correspondence, combining sequential interventions with later assignments overriding earlier ones, and restricting outcomes to actual dependency ancestors.These are identified as Corollary 1 and Theorems 2 and 3, respectively.
2 Structural causal models
This section defines deterministic acyclic structural causal models using mechanism families whose actual dependencies determine a dependency graph. Compatibility separates permitted graph edges from used mechanism dependencies, while acyclicity guarantees a unique world for each exogenous state.
- Definitions: A finite endogenous-variable system consists of nonempty value sets, complete assignments called worlds, and a nonempty exogenous-state space without requiring a probability law.Exogenous states may collect local disturbances, shared background factors, or other information fixed outside the endogenous equations.
- Definitions: Mechanisms share the domain U×X so their actual dependencies can be recovered directly rather than imposed through parent sets.A coordinate ignored by Fv contributes no arrow, while acyclicity permits evaluation in topological order.
- Definitions: Graph(F) contains exactly the arrows w →v for which changing only w can change Fv, recording actual rather than merely permitted dependencies.This dependency notion is witnessed by an exogenous state and two worlds differing only possibly at w.
- Definitions: A causal model is a pair (G, F) with acyclic G and compatible mechanisms, meaning every actual mechanism dependency is permitted by G; exactness means G = Graph(F).Thus G specifies permitted dependencies, whereas F determines which permitted dependencies are used, and unused arrows may remain in G.
- Evaluation: For any causal model, mechanism values depend only on a variable’s parents, and each exogenous state determines exactly one satisfying world, called Run(M, u).The parent result follows by changing nonparents one at a time; uniqueness follows from topological construction and induction.
3 The do-operator
The do-operator is formalized as a type-respecting partial intervention that deletes incoming graph arrows while replacing target mechanisms with imposed constants. These edits correspond exactly at the dependency level, with supplied-graph equality characterized by model exactness and intervened outcomes determined by unchanged non-target equations.
- Definitions: An intervention is a type-respecting partial map whose domain is the target set and whose values specify only targeted variables.A singleton intervention is written do(A = a), while the empty intervention is ∅.
- Definitions: Graph surgery preserves vertices and deletes exactly the arrows entering intervention targets, without recording imposed values.The imposed values instead enter through mechanism replacement, which sets each target mechanism to its assigned constant and leaves other mechanisms unchanged.
- Graph–mechanism correspondence: Theorem 1 establishes Graph(F^ι) = Surg(Graph(F), T_ι), so replacing target mechanisms removes exactly their dependency arrows.The proof separates targets, whose mechanisms become constant, from non-targets, whose dependencies remain unchanged.
- Agreement with the supplied graph: For a model M = (G, F), Graph(F^ι) is compatible with Surg(G, T_ι), and equality for a given intervention holds exactly when every unused arrow enters a target.Equality holds for every intervention if and only if M is exact, meaning G records F’s dependencies without extra arrows.
- Intervention equation: An intervened outcome assigns each target its intervention value and satisfies every original mechanism equation outside the target set.Acyclicity ensures these conditions determine exactly one world.
4 Sequential interventions
Sequential interventions combine into one intervention over the union of their targets, retaining the later value when targets overlap. This yields basic intervention laws and extends to any finite sequence, with equality of resulting models.
- 4 Sequential interventions: Theorem 2 represents sequential interventions ι followed by κ as one intervention on Tι∪Tκ that uses κ’s value wherever defined and otherwise ι’s.The combined intervention is defined as a partial map λ that prioritizes κ on overlapping targets.
- 4 Sequential interventions: Sequential intervention preserves exactly the surgically modified graph and mechanisms: κ constants replace targets of κ, ι constants remain at earlier-only targets, and all others retain Fv.Both intervention orders therefore produce identical graphs and mechanism families.
- 4 Sequential interventions: The basic laws state that empty interventions do nothing, repetition changes nothing, disjoint-target interventions commute, and overlapping targets retain the later value.At a shared target v, Do(Do(M, ι), κ) uses the constant κv.
- 4 Sequential interventions: For any finite sequence of interventions, parenthesization is irrelevant: the result equals one intervention collecting all targets and keeping each target’s last assigned value.The equality concerns the resulting models, not merely their runs.
5 Dependence on ancestors
An outcome on O is determined by interventions restricted to its actual dependency ancestors An_F(O): interventions agreeing there produce the same outcome. Therefore, targets outside An_F(O) can be discarded, although ancestor interventions may still be irrelevant because of cancellation.
- Dependence on ancestors: Theorem 3 states that interventions agreeing on An_F(O) yield identical outcomes on O for every exogenous state.An_F(O) contains O and every variable reaching O by a directed path in Graph(F).
- Dependence on ancestors: Topological induction proves agreement throughout An_F(O), because ancestor equations use only parents within that set.Targeted variables receive the same imposed values, while untargeted variables use the same mechanisms and equal parent values.
- Discarding targets outside the ancestors: Intervention targets outside An_F(O) may be discarded without changing the outcome on O.This follows by restricting the intervention to An_F(O); if no target lies there, the intervention can be omitted entirely.
- Limitations: The ancestor condition is sufficient but not necessary: cancellation can make interventions on an actual ancestor irrelevant to the outcome.With F_B=x_A and F_Y=x_A ⊕ x_B, do(A=0) and do(A=1) both produce Y=0 despite A being an ancestor of Y.
6 Related work
This section situates the paper’s dependency-level correspondence between graphical arrow deletion and functional intervention among structural-causal, diagrammatic, and mechanization-oriented work. It also distinguishes the dependency graph from a supplied graph with potentially unused arrows and identifies when graph surgery agrees on both.
- Structural causal models: Pearl’s structural-equation account pairs replacing selected equations by assigned values with deleting their incoming arrows, alongside related treatments of functional models and recursive intervention axioms.Peters, Janzing, and Schölkopf treat functional models, interventions, and causal graphs, while Halpern develops axioms for recursive models.
- Diagrammatic accounts: String-diagram approaches formalize causal-model syntax and semantics, whereas this paper studies how extensional dependencies change under intervention in ordinary deterministic structural causal models.Jacobs, Kissinger, and Zanasi interpret string diagrams as stochastic matrices and treat intervention syntactically; Lorenz and Tull extend the approach to broader causal-model classes.
- Mechanization: Theorem 1 gives a dependency-level formulation of the conjecture that incoming-edge deletion and constant replacement are equivalent, making it suitable for mechanization.The conjecture appears in Zhang’s thesis, which proposes a formal Coq proof as a next step.
- Graph distinctions: Corollary 1 characterizes exactly when surgery on the dependency graph and a compatible supplied graph agrees, even when the supplied graph contains unused arrows.The formulation separates the graph extracted from dependencies from a potentially nonminimal supplied graph.
7 Conclusion
The conclusion establishes that graph surgery and constant mechanism replacement agree after extracting dependencies. It also characterizes when supplied-graph surgery is exact, shows how interventions compose, and identifies the interventions relevant to an outcome.
- Graph surgery and constant mechanism replacement agree after dependency extraction.
- For a supplied graph, the equality holds for every intervention exactly when the starting model has no unused arrows; both constructions always have the same run.For an exact starting model, they are the same intervened model.
- The intervention equation characterizes outcomes, sequential interventions retain each target’s last assigned value, and outcomes depend only on interventions at actual dependency ancestors.These results keep the do-operator’s structural and functional components distinct.