PaperlayerView exact revision on arXiv

Source-linked AI summary

Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounders

Patrick Forré, Joris M. Mooij

arXiv:1807.03024v1stat.MLcs.AIcs.LG

TL;DR

The paper addresses causal discovery for non-linear structural causal models with cycles, latent confounders, and observational or interventional data. It extends σ-separation through σ-connection graphs and adapts a constraint-based ASP algorithm, demonstrating recovery of mSCM graph features on simulated data.

  • Problem

    Causal discovery lacks a method covering non-linearities, cycles, latent confounders, and multiple interventional data sets together, while existing separation criteria can fail for non-linear cyclic models.

    Source: §1 · p. 1

  • Method

    The paper introduces σ-connection graphs, proves σ-separation closed under marginalisation and conditioning, and encodes σ-separation in an ASP-based causal discovery algorithm.

    Source: §1 · p. 2, §3 · p. 7

  • Results

    The resulting algorithm is sound for oracle inputs and asymptotically consistent under mild assumptions, and recovers mSCM graph features on simulated data.

    Source: §1 · p. 2, §3.3 · p. 8

  • Takeaways & Limitations

    The framework extends constraint-based causal discovery to non-linear cyclic mSCMs with latent confounders and combinations of observational and interventional data.

    Source: §5 · p. 9

    The approach assumes no selection bias and σ-faithfulness, while strong σ-completeness remains unproved and direct intervention operators on σ-CGs are not investigated.

    Source: §2.2 · p. 6, §2.3 · p. 7

Abstract

from arXiv · show

We address the problem of causal discovery from data, making use of the recently proposed causal modeling framework of modular structural causal models (mSCM) to handle cycles, latent confounders and non-linearities. We introduce σ-connection graphs (σ-CG), a new class of mixed graphs (containing undirected, bidirected and directed edges) with additional structure, and extend the concept of σ-separation, the appropriate generalization of the well-known notion of d-separation in this setting, to apply to σ-CGs. We prove the closedness of σ-separation under marginalisation and conditioning and exploit this to implement a test of σ-separation on a σ-CG. This then leads us to the first causal discovery algorithm that can handle non-linear functional relations, latent confounders, cyclic causal relationships, and data from different (stochastic) perfect interventions. As a proof of concept, we show on synthetic data how well the algorithm recovers features of the causal graph of modular structural causal models.

1 INTRODUCTION

The paper develops causal discovery for non-linear cyclic models with latent confounders and interventional data by extending σ-separation to a new mixed-graph framework. It uses these results to adapt a constraint-based algorithm and demonstrates recovery of mSCM graph features on simulated data.

  • The paper addresses a gap left by existing methods, which generally handle only restricted combinations of acyclicity, linearity, latent confounding, and intervention settings.Source: §1 · p. 1
  • The proposed algorithm is presented as the first causal discovery method addressing non-linearities, cycles, latent confounders, and multiple interventional data sets together, while excluding selection bias and faithfulness violations.Source: §1 · p. 1
  • mSCMs provide the modeling basis because they support cycles, latent confounders, general non-linear measurable functions, arbitrary probability distributions, interventions, and marginalisations.Source: §1 · p. 1
  • σ-connection graphs extend mixed-graph σ-separation with directed, bidirected, and undirected edges, and the paper proves closure under marginalisation and conditioning.Source: §1 · p. 2
  • The method adapts a weighted conditional-independence approach by replacing d-separation and d-CGs with σ-separation and σ-CGs in Answer Set Programming.Source: §1 · p. 2
  • The authors demonstrate the algorithm on simulated data to recover features of mSCM causal graphs.Source: §1 · p. 2

2 THEORY

The theory develops modular structural causal models for cyclic, nonlinear systems with latent variables, then introduces σ-separation and σ-connection graphs to relate these models to observed conditional independences. It establishes graphical operations and criteria needed for causal discovery, while identifying assumptions and boundaries of the framework.

2.1 MODULAR STRUCTURAL CAUSAL MODELS

  • Loops are mutually reachable node sets; strongly connected components are their largest instances, while acyclic graphs contain only singleton loops.The loop set also includes intermediate non-trivial loops inside strongly connected components.Source: §2.1 · p. 3
  • mSCMs represent observed and latent variables with directed graphs, measurable mechanisms, latent-space probability measures, and globally compatible mechanisms over graph loops.They are summarized by M = (G+, X, P, g), and global compatibility is required because local compatibility need not suffice in cyclic nonlinear systems.Source: §2.1 · p. 3
  • mSCMs support well-defined marginalisations and interventions, including under cycles, because their construction incorporates globally compatible mechanisms for observable loops.The framework also allows general nonlinear measurable functions and arbitrary probability distributions, including mixtures of discrete and continuous distributions.Source: §2.1 · pp. 2–4

2.2 Σ-SEPARATION IN MSCMS AND Σ-CONNECTION GRAPHS

  • σ-separation generalizes d-separation on structured mixed graphs, preserving the conditional independences entailed by mSCMs in the presence of cycles, nonlinearities, and latent confounders.The induced σ-connection graph can lose information about a shared latent parent when it replaces that structure with bidirected edges, while retaining conditional independences.Source: §2.2 · pp. 4–6
  • In a nonlinear directed four-cycle, d-separation encodes extra conditional independences, whereas σ-separation captures the dependence observed in the example.The framework therefore requires σ-faithfulness for reverse inference from conditional independences, but strong σ-completeness remains unproved and is left for future research.Source: §2.2 · p. 6

2.3 MARGINALISATION AND CONDITIONING IN Σ-CONNECTION GRAPHS

  • σ-separation remains closed under marginalisation and conditioning, enabling the corresponding σ-connection graph operations required by the causal-discovery framework.The theory establishes equivalences for individual variables and for partitioned node sets, while leaving a direct intervention operator on σ-connection graphs unexplored.Source: §2.3 · pp. 6–7

3 ALGORITHM

The algorithm formulates causal discovery as weighted optimization over σ-CGs, encoding conditional-independence, marginalisation, conditioning, and intervention rules in ASP. It scores graph features by comparing optimal losses and is sound for oracle inputs and asymptotically consistent under mild assumptions.

3 ALGORITHM

  • ASP encodes σ-CGs, marginalisation, conditioning, and intervention rules so an off-the-shelf solver can optimize causal graphs against weighted independence statements.The loss uses σ-separation instead of d-separation and reduces σ-separation testing to non-adjacency after conditioning and marginalisation.Source: §3 · p. 7, §3.3 · p. 8, §3.2 · p. 8
  • Weighted statements encode independence or dependence under observational or interventional distributions, with finite weights as soft constraints and ±∞ as hard constraints.Positive weights support independence, whereas negative weights support dependence.Source: §3.2 · p. 8
  • Feature confidence is computed from the difference between optimal losses with and without an added hard constraint forcing that feature’s presence.The underlying graph may be non-identifiable even when individual features remain identifiable.Source: §3.2 · p. 8
  • The algorithm uses p-value-derived weights λ_j = log p_j − log α from conditional-independence tests performed under stochastic perfect interventions.The tests use partial correlation after marginal rank-transformation to standard-normal marginals.Source: §3.2 · p. 8
  • The feature-scoring algorithm is sound for oracle inputs and asymptotically consistent under mild assumptions.Source: §3.3 · p. 8

4 EXPERIMENTS

The experiments construct nonlinear mSCMs under a contraction condition, sample synthetic graphs with latent confounders, and evaluate causal-feature recovery using ROC and PR curves. The procedure recovers directed edges and benefits from interventional data.

4.1 CONSTRUCTING MSCMS AND SAMPLING FROM MSCMS

  • A contraction condition with Lipschitz constant L(xPaG+(S)\S) < 1 guarantees existence and uniqueness of loop functions and convergence of the iteration scheme to a unique limit.The resulting functions form a globally compatible system, enabling sampling from the mSCM.Source: §4.1 · pp. 8–9

4.2 RESULTS ON SYNTHETIC DATA

  • The experiments use 5 observed nodes, 2 latent confounders, edge probability p = 0.3, neural networks with tanh activations, and α = 10^-3.Weights are sampled from the L1-unit ball to satisfy the contraction condition.Source: §4.2 · p. 9
  • 300 simulated models are evaluated with partial-correlation tests and an ASP solver, using confidence scores to construct ROC and PR curves for directed and bidirected edges.The evaluation targets directed relations and latent confounders.Source: §4.2 · p. 9
  • Figure 4 reports ROC curves for identifying directed edges, with additional related curves provided in Supplementary Figures 6 and 7.Source: Figure 4 · p. 9

5 CONCLUSION

The paper develops σ-CGs and σ-separation for mSCMs, proves their stability under marginalisation and conditioning, and extends constraint-based discovery to nonlinear cyclic models with latent confounders and mixed intervention data. Synthetic experiments illustrate the algorithm’s effectiveness, while the study is restricted to stochastic perfect interventions.

5 CONCLUSION

  • σ-CGs generalize d-CGs, and σ-separation represents how mSCM conditional independencies behave under marginalisation and conditioning.Source: §5 · p. 9
  • The resulting discovery algorithm handles cycles, nonlinearities, latent confounders, and combined observational and interventional datasets.Source: §5 · p. 9
  • Synthetic experiments illustrate the effectiveness of the algorithm for recovering causal-graph features.Source: §5 · p. 9
  • The work restricts interventions to stochastic perfect surgical interventions, although the authors describe an extension through the JCI framework.Source: §5 · p. 9

A Σ-CG UNDER MARGINALISATION AND CONDITIONING

σ-separation remains stable when σ-CGs are marginalised or conditioned, provided the graph retains its σ-equivalence-class structure. The proofs transform open paths through eliminated or conditioned nodes while preserving the relevant separation relations.

A Σ-CG UNDER MARGINALISATION AND CONDITIONING

  • The σ-equivalence classes must be retained because marginalisation combined with conditioning can introduce cycles that affect the corresponding separation relation.Figure 5 contrasts the original DAG with its σ-CG representation and the transformed graph.Source: Figure 5 · p. 11
  • σ-separation is closed under marginalisation: separation in the original σ-CG is equivalent to separation after eliminating a node.The proof replaces path segments involving the marginalised node while preserving σ-openness.Source: A Σ-CG UNDER MARGINALISATION AND… · p. 11
  • σ-separation is closed under conditioning: separation in the original graph is equivalent to separation in the conditioned σ-CG.The proof handles fork, chain, and collider configurations while preserving the relevant triple situations.Source: A Σ-CG UNDER MARGINALISATION AND… · p. 11
  • Path transformations cover collider cases by rerouting through nodes in the same σ-equivalence class, preserving σ-openness after marginalisation or conditioning.Source: A Σ-CG UNDER MARGINALISATION AND… · pp. 11–12

B THE Σ-SEPARATION CRITERION FOR MSCMS

The section proves that observed variables in mSCMs obey σ-separation by translating cyclic directed mixed graphs into acyclic representations and extends the result to conditioning and marginalisation. These properties support constraint-based causal discovery, including under unknown selection bias.

C NEURAL NETWORKS AS MSCMS

The section constructs nonlinear mSCMs with neural-network mechanisms and establishes conditions ensuring that cyclic iterations converge to unique fixed points. Contractive weight conditions make the resulting component functions well-defined.

  • Neural networks serve as universal approximators for the nonlinear structural functions g_{v} in mSCMs.This choice preserves generality while retaining practical advantages of parametric models.Source: C NEURAL NETWORKS AS MSCMS · p. 13
  • If the recurrent weight matrices satisfy the stated norm bound for every non-trivial loop, the functions form a well-defined mSCM.Source: C NEURAL NETWORKS AS MSCMS · p. 13
  • For common activations including tanh, ReLU, sigmoid, LeakyReLU, and SoftPlus, the derivative bound can be set to C = 1.Source: C NEURAL NETWORKS AS MSCMS · pp. 13–14
  • A contraction condition on the recurrent weights ensures that cyclic neural iterations converge to a unique fixed point.The analysis also holds when error variables enter outside the activation function as additive noise.Source: C NEURAL NETWORKS AS MSCMS · p. 14
  • The construction’s compatibility follows because the unique solution for a larger loop also solves each nested subloop.Source: C NEURAL NETWORKS AS MSCMS · p. 14

D.1 SCORING FEATURES

The feature-scoring procedure evaluates whether graph features are identifiable from weighted conditional-independence constraints. Its scores are sound for oracle inputs and asymptotically consistent under consistent independence tests.

  • For oracle inputs with infinite weights, identifiable features receive C(S, f) = ∞ or −∞ according to whether they are true or false, while unidentifiable features receive 0.Source: §D.1 · p. 15
  • With asymptotically consistent independence-test weights, confidence scores converge in probability to ∞ for identifiable truths, −∞ for identifiable falsehoods, and 0 otherwise.Source: §D.1 · p. 15
  • The algorithm inherits soundness for oracle inputs and asymptotic consistency from the scoring method of [21].Source: §D.1 · pp. 14–15

D.2 ENCODING IN ANSWER SET PROGRAMMING

The algorithm encodes σ-connection-graph transformations as a computation graph implemented in answer set programming. It applies interventions, marginalisation, and conditioning in a fixed order because these operations do not commute.

  • The computation structure tests graph-implied independences by reducing intervened σ-CGs to two-variable sink graphs through graph operations.Source: §D.2 · p. 15
  • Interventions are performed first, followed by marginalisations and conditioning, because these operations do not commute.Source: §D.2 · pp. 15–16
  • The resulting computation graph is a tree because the highest-labelled removable node is selected at each stage.Source: §D.2 · p. 15
  • The ASP encoding adapts the d-separation implementation of by replacing d-separation with σ-separation and checking strongly connected components in non-collider cases.Source: §D.2 · p. 15

E EXPERIMENTAL RESULTS

The experiments evaluate detection of directed edges and latent confounders across intervention counts and graph encodings. Interventional data improves causal discovery, while allowing cycles matters more than the choice between σ-separation and d-separation in these simulations.

  • The experiments are additional visualisations of synthetic-data results and do not establish the expected larger separation differences for larger graphs with nested loops.Computational restrictions prevented enough experiments in that regime to gather empirical support, leaving the hypothesis for future research.Source: E EXPERIMENTAL RESULTS · p. 20
  • Interventional data improves detection of directed edges and latent confounders compared with the purely observational setting.Figure 6 compares 0 interventions with observational data combined with 1–5 randomly targeted single-variable interventions.Source: E EXPERIMENTAL RESULTS · p. 20, Figure 6 · p. 21
  • Allowing cycles produces substantially larger differences in detection performance than switching between σ-separation and d-separation.The larger encoding-related gap also affects detection of direct causal relations, whereas the σ-separation versus d-separation gap is largest for confounders.Source: E EXPERIMENTAL RESULTS · p. 20, Figure 7 · p. 22
  • Differences between σ-separation and d-separation are small in the simulation setting, especially relative to the effect of assuming acyclicity.Figure 7 compares σ-separation, d-separation allowing cycles, and acyclic d-separation using observational and five interventional datasets.Source: E EXPERIMENTAL RESULTS · p. 20, Figure 7 · p. 22
Loading 1807.03024v1…