PaperlayerView exact revision on arXiv

Source-linked AI summary

I-FLOP: Fast Learning of Order and Parents from Interventional Data

Liuting Chen, Alex Markham

arXiv:2608.28245v1stat.MLcs.LG

TL;DR

Causal structure learning from interventional data requires extending observational order-based methods to account for multiple environments and known intervention targets. The paper introduces I-FLOP, which combines a target-filtered pooled interventional score with FLOP’s efficient order search, and establishes asymptotic recovery of the true I-MEC alongside favorable empirical accuracy–runtime performance.

  • Problem

    Existing order-based FLOP is observational, while interventional structure learning must account for differing environments and exclude samples where the response variable is directly targeted.

  • Method

    I-FLOP extends FLOP with a target-filtered pooled interventional score while retaining reinsertion-based order search and warm-start grow–shrink updates.

  • Results

    Exact global score minimization asymptotically recovers the true I-MEC, while experiments report competitive scalability and superior I-CPDAG accuracy against established interventional baselines.

  • Takeaways & Limitations

    I-FLOP provides an order-based approach that incorporates known intervention targets while maintaining favorable accuracy–runtime performance on synthetic and real interventional data.

  • Takeaways & Limitations

    The framework assumes known hard interventions, linear-Gaussian mechanisms with strictly positive error variances, and conservative intervention designs, excluding nonlinear or deterministic mechanisms.

Abstract

from arXiv · show

We extend the FLOP (fast learning of order and parents) algorithm recently proposed by Wienöbst et al. (2026) from observational to interventional data. In particular, we use the interventional BIC score of Hauser and Bühlmann (2012), adapting it to be used with the iterative Cholesky-based score updates that are partly responsible for FLOP's speed. We show that, in the sample limit, I-FLOP recovers a DAG in the same interventional Markov equivalence class as the data-generating DAG. We compare I-FLOP to existing causal structure learning algorithms on real and simulated interventional data, where it performs favorably in terms of both performance and run time.

1. Introduction

I-FLOP extends fast order-based causal structure learning to known-target interventional data, addressing limitations of direct graph search and finite-sample CI testing. The paper introduces a target-filtered pooled score, proves asymptotic recovery of the true I-MEC, and reports favorable empirical performance.

  • Observational data identify only a Markov equivalence class, whereas interventions yield the finer interventional Markov equivalence class and orient more edges.
  • GIES searches the I-MEC with local greedy forward, backward, and turning moves but lacks global-optimality guarantees and can have exponential worst-case candidate-search complexity.
  • I-GSP uses conditional-independence tests for permutation search, whose finite-sample decisions can depend on sample size, test choice, and significance threshold.
  • Order-based search guarantees acyclicity by construction and supports efficient neighborhood exploration, while FLOP adds decomposable scoring, reinsertion search, and local parent-set updates.
  • I-FLOP extends FLOP with a target-filtered pooled local score for multi-environment interventional data with known targets.
  • In the sample limit, exact global minimization of this score identifies the true I-MEC, and experiments show competitive scalability and superior I-CPDAG accuracy versus GIES and I-GSP.

2. Preliminaries

The paper formulates known-target interventions within linear Gaussian structural equation models and represents causal uncertainty using interventional equivalence classes. I-FLOP optimizes a decomposable score over topological orders, using local warm-start updates and iterative perturbation-based search.

  • A linear Gaussian structural equation model associates each DAG with linear parent effects and jointly independent Gaussian errors having strictly positive variances.
  • Known-target hard interventions replace targeted variables’ structural equations with an intervention distribution while leaving non-targeted variables’ equations unchanged.
  • A topological order restricts each node’s candidate parents to preceding nodes, thereby inducing an acyclic graph and the ordered Markov property.
  • Positive error variances make the induced Gaussian distributions non-degenerate, so ordered, local, and global Markov properties are equivalent in this setting.
  • Observationally equivalent DAGs form an MEC, while DAGs inducing the same interventional Markov model under known targets form an I-MEC represented by an I-CPDAG.
  • I-FLOP retains FLOP’s decomposable-score search over topological orders, updating affected parent sets locally with warm-start grow–shrink procedures during reinsertion moves.
  • After local search reaches an order optimum, Iterated Local Search perturbs the order, restarts search, and retains the best-scoring result across restarts.

3. I-FLOP: order-based search for interventional data

I-FLOP extends order-based causal structure learning to known-target interventional data by scoring shared mechanisms only in valid environments and searching orders with local parent-set updates. Under stated assumptions, its pooled score supports fixed-order and global recovery guarantees, including asymptotic recovery of the true interventional Markov equivalence class.

  • Order-based search: I-FLOP searches over topological orders, restricting each node’s candidate parents to preceding variables and exploring orders through reinsertion moves.Parent sets and local scores are updated locally during reinsertion using warm-start grow–shrink rather than recomputing all nodes.
  • Target-filtered scoring: The algorithm scores node v using environments where v is not directly intervened upon, pooling observations that preserve v’s structural mechanism.Interventions on candidate parents may alter their distributions but do not invalidate an environment when the response node itself is untargeted.
  • Target-filtered scoring: The target-filtered pooled score remains node-wise decomposable and compatible with order-restricted parent sets, with a BIC penalty of 2 log N (|P| + 1).The local residual variance represents a shared linear mechanism fitted across the response node’s valid environments.
  • Recovery guarantees: Under Assumptions 1–4, target-filtered grow–shrink recovers the pooled local parent target from any initialization, and the fixed-order guarantee follows node-wise.These results justify the local parent-set selection used by I-FLOP.
  • Recovery guarantees: Under Assumptions 1–5, sparsest global residual-risk minimizers belong to the true I-MEC, and exact global empirical minimization recovers that class with probability tending to one.If the intervention target family fully identifies the DAG, the recovered equivalence class yields the true DAG.

4. Experiments

I-FLOP is evaluated against interventional baselines and FLOP variants on synthetic and real data. Across these experiments, it approaches the I-CPDAG in larger samples and offers strong accuracy–runtime performance.

  • The experiments compare I-FLOP with GIES, I-GSP, FLOP-obs, and FLOP-envwise on synthetic and real interventional datasets.Synthetic data use ER DAGs under linear-Gaussian SEMs, with one observational and multiple known-target hard-intervention environments.
  • 4.1. Finite-sample convergence: I-FLOP recovers the I-CPDAG in the large-sample limit, with structural Hamming Distance decreasing as sample size increases from 10^2 to 10^6 per environment.Figure 1 uses 20-node graphs, expected degree 2, one observational environment, and five known-target singleton hard interventions.
  • 4.2. Main accuracy and runtime comparison: I-FLOP achieves the lowest I-CPDAG SHD in both ER graph regimes, with a clearer advantage on denser graphs.GIES and I-GSP have substantially larger structural errors in the denser setting.
  • 4.2. Main accuracy and runtime comparison: I-FLOP is markedly faster than GIES in the denser setting while remaining substantially more accurate than I-GSP, yielding a favorable accuracy–runtime trade-off.Figure 2 evaluates linear-Gaussian ER DAGs with 1,000 samples per environment.
  • 4.3. Real interventional data: On the Causal Chamber Light Tunnel dataset, I-FLOP exhibits the best accuracy–runtime trade-off.The evaluated view contains 20 variables, one observational environment with 10,000 samples, and five singleton hard-intervention environments with 1,000 samples each.

5. Conclusion

The paper extends FLOP to known-target interventional data through a target-filtered pooled score and establishes asymptotic recovery guarantees. Experiments support favorable accuracy–runtime performance, while the framework remains limited by restrictive intervention and mechanism assumptions.

  • I-FLOP extends FLOP with a target-filtered pooled interventional score for multi-environment data with known intervention targets.It retains warm-start grow–shrink updates and reinsertion-based order search.
  • Exact global minimization of the target-filtered pooled score asymptotically recovers the true I-MEC under Assumptions 1–5.The theorem-level guarantee concerns the true interventional Markov equivalence class.
  • The fixed-prefix target-filtered grow–shrink update recovers the pooled local parent target in the large-sample limit under Assumptions 1–4.
  • I-FLOP achieves a favorable accuracy–runtime trade-off on synthetic interventional data and competitive performance on the Causal Chamber benchmark.
  • Limitations: The framework assumes known hard interventions, linear-Gaussian mechanisms with strictly positive error variances, and conservative intervention designs.These assumptions exclude deterministic or functional relationships with degenerate noise, nonlinear mechanisms, and uncertain intervention targets.

A.2. Proof of Proposition 4

The proposition characterizes the pooled regression support as the unique smallest parent set achieving the minimum pooled residual risk. This establishes the target-filtered local parent target used by the grow–shrink procedure.

  • The pooled population regression coefficient vector is unique because the pooled covariance matrix is positive definite and invertible.The argument uses positive definiteness of every relevant principal submatrix.
  • For any candidate set P contained in Z, the pooled residual risk equals the full-set risk exactly when P contains the support S of the full pooled regression.Here S is the support of the coefficient vector for regressing X_v on X_Z.
  • S is therefore the unique minimizer of smallest cardinality among candidate parent sets contained in Z.Other risk minimizers are precisely supersets of S.
  • If every single missing member of S leaves the risk unchanged when added, multivariate residual arguments imply that adding all missing members also leaves it unchanged.The proof uses the Frisch–Waugh–Lovell identity and positive definiteness of the corresponding Schur complement.

A.3. Proof of Theorem 5

The theorem proves that target-filtered grow–shrink reaches the pooled local parent target from any warm start. Applying this nodewise under a fixed order supports asymptotic recovery of the order-restricted graph.

  • The grow phase includes every member of the population minimizer M in the parent set.Otherwise, Proposition 4 provides a missing variable whose addition improves the relevant criterion.
  • During shrink, every strict superset of M admits a score-decreasing deletion of an extraneous parent.
  • Deleting a member of M is not score-improving, so the shrink phase preserves M while removing variables outside M.
  • A complete grow–shrink cycle returns M_pool^v(Z) in the limit, independently of the initial parent set.Thus target-filtered grow–shrink returns the pooled local target with probability tending to one from any warm start.
  • For a fixed order, applying the local result to every node yields simultaneous high-probability guarantees because the node set is finite.The resulting DAG uses parent sets restricted to each node’s predecessors in the order.
  • The score is decomposable after profiling out environment-specific intercepts, and targeted replacement mechanisms do not affect graph comparison.

A.6. Proof of Theorem 8

The proof shows that the population target-filtered pooled score is minimized by the true DAG and that every sparsest optimal DAG lies in the true interventional Markov equivalence class.

  • The target-filtered pooled score is equivalent, up to graph-independent terms, to the valid-environment structural-mechanism likelihood after profiling environment-specific intercepts.Known targeted replacement mechanisms contribute graph-independent nuisance terms.
  • The true DAG G⋆ attains the minimum population loss and therefore belongs to the set A of optimal population-fit DAGs.
  • Any DAG H in A has no population likelihood loss relative to the true known-target interventional distribution family, making the true distributions Markov with respect to H.
  • For any G in Amin, sparsity gives |E_G| ≤ |E_G⋆|, while interventional faithfulness identifies the minimum causal independence maps with the I-Markov equivalence class of G⋆.
  • Because every G in Amin is also a causal independence map, |E_G| ≥ |E_G⋆|; combining both inequalities yields equal edge counts and G ∈ G⋆.

A.7. Proof of Corollary 9

The consistency proof separates candidate DAGs by population fit and then uses the BIC complexity penalty to select sparsest population-optimal representations.

  • For every fixed DAG, valid-environment pooled residual variances are consistent under the assumed asymptotic environment sample proportions.
  • Any DAG outside A has strictly larger population loss than an optimal DAG in A.
  • The fit difference is order N, whereas the complexity-penalty difference is order log N, so population-fit differences dominate asymptotically.
  • Among DAGs in A, non-sparsest candidates differ from sparsest candidates only through Op(1) likelihood differences in the fixed-dimensional Gaussian models.
  • Since the DAG space is finite, the relevant convergence holds simultaneously across all candidate DAGs.
  • The BIC complexity penalty depends on parent-set sizes through |E_G| + |V|, so adding an edge increases the penalty relative to a sparser candidate.
  • The consistency argument therefore excludes nonoptimal population-fit DAGs first and distinguishes optimal DAGs by their sparsity.

Appendix B. Detailed Algorithmic Specifications

The appendix specifies reinsertion-based local order search, warm-start parent-set updates, and a justified short-circuit for target-filtered grow–shrink optimization.

  • Target-filtered reinsertion: Each adjacent swap updates only the two affected parent sets, enabling localized score updates during reinsertion.
  • Target-filtered reinsertion: Algorithm 2 starts from the current order and parent sets, then searches reinsertion positions for node v in both directions.
  • Target-filtered reinsertion: The best reinsertion state is retained whenever its local score improves on the current best state.
  • Target-filtered warm-start grow–shrink: Algorithm 3 applies target-filtered warm-start grow–shrink updates by adding or removing admissible parents until the parent set is unchanged.
  • Target-filtered warm-start grow–shrink: The δ = +u short-circuit is valid when the starting parent set is already a grow–shrink fixed point over the remaining admissible parents.Proposition 4 implies that if no admissible single-parent addition improves the score, no further local move can improve it.
  • Scaling setup: Figure 4 evaluates runtime and I-CPDAG SHD while varying sample size or graph size under one observational and five singleton hard-intervention environments.

Appendix C. Computational Scaling with Graph Size and Sample Size

I-FLOP scales favorably across sample and graph size: it maintains low I-CPDAG error with moderate runtime growth, while GIES becomes substantially more expensive and FLOP-envwise remains less accurate.

  • Scaling with sample size: As sample size increases, I-FLOP substantially reduces I-CPDAG SHD toward near-perfect recovery, while FLOP-based runtimes rise markedly beyond 10^4 samples.
  • Scaling with sample size: I-GSP improves with additional samples but retains noticeably higher structural error than I-FLOP and GIES.
  • Scaling with graph size: With increasing graph size, I-FLOP retains the lowest structural error and moderate runtime growth, whereas GIES reaches several hundred seconds at p = 100.
  • Scaling with graph size: FLOP-envwise stays computationally close to I-FLOP but consistently incurs higher recovery error, supporting target-based environment filtering.
  • GIES runtime: GIES runtime is decomposed into covariance/scatter precomputation, graph search, and wrapper execution under the same settings as Figure 4.
  • GIES runtime: The GIES search stage requires approximately 20 seconds and dominates end-to-end runtime, while covariance computation remains below one second at the largest sample size.
  • ILS diagnostic: Figure 6 reports mean BIC score, total SHD, and skeleton and orientation SHD across 50 seeds as the ILS budget increases, with interquartile shading.
  • GIES runtime: Small non-monotonic runtime changes at lower sample sizes reflect different greedy search trajectories and step counts rather than systematic computational savings.

Appendix D. Diagnostic ILS Trace on the Real Data Experiment

Increasing the ILS budget on the real data generally lowered the optimized BIC score but worsened mean SHD, with orientation errors driving the mismatch. The discrepancy plausibly reflects differences between the real optical interventions and I-FLOP’s linear-Gaussian assumptions.

  • Score–recovery mismatch: 21.55 BIC units: the mean total score decreased from ILS 0 to ILS 50, with 49 of 50 seeds achieving lower scores.The score decreased rapidly during the first several ILS steps before stabilizing.
  • Score–recovery mismatch: 29.42 to 30.12: mean total SHD increased as the ILS budget rose from 0 to 50.Mean skeleton SHD slightly decreased from 28.14 to 28.12, while mean orientation SHD increased from 1.28 to 2.00.
  • Seed heterogeneity: 27 seeds worsened, 14 improved, and 9 were unchanged in total SHD when comparing ILS 50 with ILS 0.Skeleton changes occurred in both directions, whereas orientation SHD increased for 20 seeds and decreased for none.
  • Score–recovery mismatch: The optimized lower BIC scores were not necessarily associated with closer reference-graph recovery under SHD.The one-sided orientation changes accounted for the net increase in mean total SHD.
  • Interpretation and scope: Causal Chamber interventions changed the support and operating regime of physical actuators rather than applying Gaussian mean shifts within the same assumed model.The synthetic experiments instead use a linear-Gaussian SEM with Gaussian shifts on intervention targets.
  • Interpretation and scope: On the real data, a lower total BIC score indicates improved fit under the linear-Gaussian scoring approximation, not direct evidence of improved physical-graph recovery.This distinction constrains how the ILS diagnostic should be interpreted.
Loading 2608.28245v1…