PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Agnostic Modeling: Adversarial Learning of Causal Graphs

Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, Michèle Sebag

arXiv:1803.04929v5stat.ML

TL;DR

Learning causal structure from observational data matters when randomized experiments are costly, unethical, or infeasible. SAM combines conditional-independence relations and distributional asymmetries in adversarial learning of sparse acyclic graphs. Across the evaluated settings, it most often ranks first, with stated exceptions for methods specialized to particular settings.

  • Problem

    Causal structure must often be inferred from observational data because randomized experiments can be costly, unethical, or infeasible.

    Source: §1 · p. 1

  • Method

    SAM learns conditional distributions with neural networks and uses adversarial optimization with sparsity and acyclicity constraints to discover causal graphs.

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

  • Results

    SAM most often ranks first and avoids catastrophic failures, though CAM dominates in additive-noise and Gaussian-process settings and GENIE3 does so for feedback-loop graphs on some networks.

    Source: §7 · p. 35

  • Takeaways & Limitations

    The authors suggest SAM can help practitioners prioritize exploratory experiments on real data without prior knowledge of mechanism type or data distribution.

    Source: §7 · p. 35

    In the general case, identifiability of causal graphs with neural-network mechanisms remains an open question.

    Source: §7 · p. 35

Abstract

from arXiv · show

A new causal discovery method, Structural Agnostic Modeling (SAM), is presented in this paper. Leveraging both conditional independencies and distributional asymmetries, SAM aims to find the underlying causal structure from observational data. The approach is based on a game between different players estimating each variable distribution conditionally to the others as a neural net, and an adversary aimed at discriminating the generated data against the original data. A learning criterion combining distribution estimation, sparsity and acyclicity constraints is used to enforce the optimization of the graph structure and parameters through stochastic gradient descent. SAM is extensively experimentally validated on synthetic and real data.

1. Introduction

The paper addresses learning causal structure from observational data, where randomized experiments may be costly, unethical, or infeasible. It introduces SAM, which combines conditional-independence information and distributional asymmetries in a continuous optimization approach to causal graph learning.

  • Observational causal discovery infers causal graphs from samples of a joint distribution, a problem of interest when randomized experiments are costly, unethical, or infeasible.Source: §1 · pp. 1–2
  • Prior approaches include score-based, constraint-based, hybrid, and distributional-asymmetry methods, while causal feature selection targets a variable’s Markov blanket.Source: §1 · p. 2
  • SAM is a continuous-variable causal discovery algorithm that seeks acyclic functional causal models using conditional independencies and distributional asymmetries.Source: §1 · p. 2
  • SAM learns each variable’s conditional distribution as a neural network and optimizes the Markov kernels in parallel through an adversarial mechanism.Sparsity and acyclicity constraints apply to the graph derived from those kernels.Source: §1 · p. 2
  • The method frames graph selection through compound structural and functional complexity scores, following an Occam’s razor principle.Source: §1 · p. 2

2. Observational Causal modeling: Formal Background

The background formalizes causal discovery with Functional Causal Models and their assumptions, then reviews graph-learning approaches and motivates SAM’s combination of conditional-independence and distributional-asymmetry information.

2.1 Functional Causal Models

  • An FCM pairs a directed acyclic graph with causal mechanisms, with each variable generated from its parents and a noise variable.The example gives X2 and X3 the parent X1, and X5 the parents X3 and X4.Source: §2.1 · p. 3

2.2 Notations and Definitions

  • A CPDAG represents Markov-equivalent DAGs through their shared skeleton and v-structures, leaving undirected edges for relationships whose direction is unresolved.Source: §2.2 · p. 4

2.3 Causal Assumptions and Properties

  • The framework assumes a DAG, mutually independent noise variables, faithfulness, and causal sufficiency, meaning no hidden confounders.Source: §2.3 · p. 4

2.4 Background

  • GES searches CPDAGs by local edge operations and, under the stated assumptions and score conditions, identifies the true CPDAG in the large-sample limit.FGES parallelizes subgraph optimization to increase computational efficiency.Source: §2.4 · p. 5
  • PC uses conditional-independence tests to recover a CPDAG, while MMHC selects parents and children before greedily orienting edges by Bayesian score.Source: §2.4 · p. 5
  • The approaches described can recover at best a Markov equivalence class, which may leave causal edge directions unresolved.Source: §2.4 · p. 5
  • Asymmetry-based identification extends beyond bivariate problems, but mechanism restrictions used for identifiability may be too strong for real-world data.GPI offers a non-parametric, complexity-based approach for the bivariate setting without restricting the mechanism class.Source: §2.4 · p. 6
  • SAM combines conditional-independence and distributional-asymmetry information, using adversarial learning and simultaneous structure/mechanism optimization to target CGNN’s data- and variable-scaling limitations.Source: §2.4 · pp. 6–7

3. Problem settings

The paper learns candidate causal graphs by fitting conditional mechanisms for each variable while imposing sparsity and acyclicity. Structural loss identifies the true graph’s Markov equivalence class under stated assumptions, while parametric loss uses distributional asymmetries to distinguish equivalent graphs.

3.1 Markov Kernels as functional causal mechanisms

  • For each variable, SAM learns a conditional mechanism and selects its parent variables using observational data.A binary structural gate marks whether a variable is used to generate the target; each mechanism also has parameters and a noise variable for unobserved causes.Source: §3 · p. 7, §3.1 · p. 7

3.2 Learning independent Markov kernels

  • SAM jointly learns the conditional mechanisms by optimizing conditional log-likelihood, whose decomposition includes a conditional mutual-information term.The learning task includes both mechanism fitting and selection of a minimal parent subset.Source: §3.2 · p. 8

3.3 Structural loss

  • The structural loss selects a minimal parent set using conditional dependence and sparsity; without acyclicity it identifies the true graph’s moral graph.The feature-selection solution converges toward each variable’s Markov blanket in the large-sample limit.Source: §3.3 · pp. 8–9

Theorem 1 (CPDAG identification by structural loss minimization)

  • Under CMA, CFA, and CSA, minimizing structural loss identifies the true graph’s Markov equivalence class in the large-sample limit.The theorem states convergence in probability for DAGs in the equivalence class and a larger loss for DAGs outside it, for some λS > 0.Source: Theorem 1 (CPDAG identification by… · p. 9, §3.3 · p. 9
  • The structural loss cannot distinguish equivalent DAGs; in the bivariate case, X → Y and Y → X have the same large-sample loss.The parametric loss is introduced to address this limitation.Source: Theorem 1 (CPDAG identification by… · p. 9

3.4 Parametric loss

  • The parametric loss regularizes mechanism complexity to exploit distributional asymmetries and disambiguate graphs within the true CPDAG.The method controls mechanism capacity using a Frobenius-norm penalty on its parameters.Source: §3.4 · p. 10, §3.5 · pp. 10–11

3.5 Discussion

  • SAM trades off data fit, structural sparsity, and functional complexity, and can incorporate prior knowledge about mechanism types or noise distributions.The structural term penalizes edges, while the functional term penalizes mechanism parameters; neural networks and adversarial learning are used when little mechanism information is available, with a global acyclicity constraint coupling the kernels.Source: §3.5 · pp. 10–11

4. Structural Agnostic model

SAM models each variable’s conditional mechanism with a neural network and jointly fits the mechanisms and graph structure. Its learning criterion combines adversarial data fitting with complexity penalties and an acyclicity constraint.

4. Structural Agnostic model

  • SAM combines neural-network mechanisms, adversarial fitting, sparsity, and continuous acyclicity optimization to learn a causal DAG.A Bernoulli reparameterization trick jointly optimizes structural gates and mechanism parameters with stochastic gradient descent.Source: §4 · p. 11

4.1 Modeling each Markov kernel with a conditional generative neural network

  • Each Markov kernel is modeled as a conditional generative neural network, with independent variable generations computed in parallel.The mechanism uses the structural gate matrix to select variable inputs and Gaussian noise as an additional input.Source: §4.1 · pp. 11–12

4.2 SAM learning criterion

  • A shared discriminator estimates the fit terms by distinguishing observed data from partially generated data, while the objective penalizes structural and functional complexity.The structural term measures the number of parents; the functional term uses the Frobenius norm of mechanism parameters.Source: §4.2 · pp. 13–15

4.3 Enforcing the acyclicity of the causal graph

  • The acyclicity constraint couples parent-selection problems, and the Bernoulli reparameterization trick with Binary Concrete relaxation enables end-to-end stochastic-gradient training.The constraint removes effect variables from candidate parent sets, which in turn removes spouse variables.Source: §4.3 · pp. 16–17

5. First experimental analysis

The first experimental analysis probes SAM’s performance and sensitivity across synthetic graph mechanisms, initialization, the DAG constraint, and graph density. It finds that initialization and acyclicity matter, while performance is best at an intermediate graph density.

5.1 Synthetic dataset generation

  • Synthetic experiments use DAG datasets with 20 or 100 variables, consider six causal-mechanism categories, and generate each graph’s 500-sample dataset iid following the graph’s topological order.The number of parents for each variable is uniformly drawn from 0 to 5.Source: §5.1 · p. 17

5.2 Experimental settings

  • λS is the more sensitive parameter, with best values between 0.002 and 0.02 depending on the graph; λF is less sensitive.A low λF is preferable on datasets with complex mechanisms and interactions, while higher values can help simpler datasets avoid overfitting.Source: §5.2 · pp. 19–20, Figure 4 · p. 20

5.3 Sensitivity to SAM weights initialization

  • SAM’s results vary with neural-network initialization, so the authors average multiple runs and retain edges selected by a majority.Across 100 runs, 30 true-positive edges were selected in over half of runs, while 9 false positives and 14 false negatives crossed the same threshold.Source: §5.3 · pp. 20, 22, Figure 6 · p. 21

5.4 Impact of the DAG constraint

  • Without the DAG constraint, SAM selects more false positives, including edges between spouse nodes, and its global score degrades.It can select both directions of an edge and recover moralized-graph edges that are absent from the true DAG skeleton.Source: §5.4 · pp. 22–23, Figure 9 · p. 23, Figure 8 · p. 23

5.5 Sensitivity to graph density

  • At graph density 0.2, SAM performs best; results are lower at 0.1 and decrease slightly above 0.2 as more edges must be recovered.The authors attribute the improvement over density 0.1 to v-structures that facilitate edge orientation.Source: §5.5 · p. 24, Figure 10 · p. 24

6. Experimental validation on causal discovery benchmarks

The benchmark evaluation compares SAM with established causal-discovery methods across synthetic, simulated biological, and real biological data. SAM is robust across varied settings, with especially strong results on some complex and real-world tasks, while performance depends on the data and competing methods.

6.1 Different SAM variants

  • The benchmark tests full SAM against linear-only, MSE-loss, and combined linear/MSE variants to assess non-linear mechanisms and adversarial training.The reported results find the lesioned versions significantly worse except in linear-mechanism and additive-Gaussian-noise cases.Source: §6.1 · p. 25, §6.4 · p. 27

6.2 Baseline algorithms

  • The comparison includes score-based GES and GIES, hybrid MMHC, CCDr, LiNGAM, CAM, PC with four independence tests, and GENIE3.The authors also include GENIE3, which performs feature selection rather than DAG discovery per se.Source: §6.2 · pp. 25–26

6.3 Performance indicators

  • Methods are evaluated with AUPR and AUC for edge-ranking performance and SHD for graph errors at a causation-score threshold above 0.5.AUPR and AUC range from 0 to 1, with 1 optimal; SHD counts missing and redundant edges, with a reversal counted as one mistake.Source: §6.3 · p. 26

6.4 Experiments on synthetic datasets

  • On 20-node synthetic graphs, SAM ranks among the top three methods; it is surpassed on linear mechanisms and by CAM on additive-noise mechanisms.On complex non-linear cases, SAM significantly outperforms other non-parametric methods, and its lesioned variants perform worse except for linear and additive-Gaussian cases.Source: §6.4 · pp. 26–27, Figure 11 · p. 27
  • On 100-node synthetic graphs, SAM remains robust but is dominated by CAM on GP AM, GP Mix, and Sigmoid AM settings.SAM does not show catastrophic failure and performs reasonably on linear data; its computational cost scales well at 100 variables, while PC-HSIC was stopped after 50 hours.Source: §6.4 · p. 28, Figure 12 · p. 28

6.5 Simulated biological datasets

  • On SynTREN graphs, SAM performs well; on DREAM4, GENIE3 leads on networks 1, 2, and 5 while SAM is better on network 3; DREAM5 results degrade on Networks 3 and 4.On DREAM5 Network 1, SAM, GENIE3, and TIGRESS have similar best results; the authors tentatively link low scores on Networks 3 and 4 to interaction sets that may be inaccurate or incomplete.Source: §6.5 · pp. 29, 31, 32, Figure 13 · p. 29, Figure 15 · p. 30

6.6 Real-world biological data

  • On the flow-cytometry dataset, SAM significantly outperforms the other methods by AUPR and recovers the raf→mek→erk transduction pathway.The dataset contains 7,466 observational samples for 11 proteins, and SAM is run without the acyclicity penalty because the network contains feedback loops.Source: §6.6 · p. 33

7. Discussion and Perspectives

SAM combines structural independence and distributional asymmetries in a regularized adversarial framework for causal discovery. The authors report broad empirical robustness, while noting that neural-network causal graph identifiability remains open in the general case.

7. Discussion and Perspectives

  • The method combines structural independence and distributional asymmetries, using GAN-based learning with regularization to enforce sparse acyclic graphs.The model choices are supported by theoretical analysis.Source: §7 · pp. 33–35
  • Identifiability of causal graphs with neural-network mechanisms remains an open question in the general case.The authors suggest SAM can help prioritize exploratory experiments on real data without prior knowledge of mechanisms or the data distribution.Source: §7 · p. 35
  • SAM most often ranks first, avoids catastrophic failures, and scales to very good performance on DREAM5 Network 1 with about 1,500 variables.It can be dominated by methods tailored to additive-noise/Gaussian-process settings or graphs with feedback loops.Source: §7 · p. 35
  • Future work includes categorical and mixed variables, hidden confounders, interventions, and cyclic graphs.The proposed directions include dependent or shared noise variables, confounder proxies, and recurrent neural networks for feedback models.Source: §7 · p. 35

Appendices

Appendix A includes a table of notations used throughout the paper.

Appendices

  • Appendix A contains a table listing notations used throughout the paper.Source: Table 2 · p. 42

B. Structural loss: Proof of Theorem 1 and example

The structural loss is consistent under CMA, CFA, and CSA: asymptotically it does not separate DAGs in the true Markov equivalence class, but favors the true graph over DAGs outside it. The proof and examples show how conditional-independence patterns can distinguish a v-structure and how the structural loss identifies one in a linear-Gaussian example.

B. Structural loss: Proof of Theorem 1 and example

  • Under CMA, CFA, and CSA, the structural loss converges to zero for DAGs in the true graph’s equivalence class and asymptotically favors the true graph over DAGs outside it.For non-equivalent graphs, the stated result requires a positive sparsity weight satisfying the bound in the proof.Source: B. Structural loss: Proof of Theorem 1… · p. 43, Proof · pp. 44–45

Proof

  • Covered edge reversals connect equivalent DAGs without changing the global conditional-mutual-information score.A covered edge has the child’s parents equal to the parent’s parents plus the parent node.Source: Proof · p. 43
  • For the skeleton A − B − C, the structural score prefers A → B ← C when A and C are independent but become dependent conditioned on B.When A and C are dependent but conditionally independent given B, the chain equivalence class is preferred instead.Source: Proof · p. 45
  • In the linear-dependency, Gaussian-noise experiment, the structural loss statistically significantly identified the true v-structure with as few as 100 examples.The study generated 2,000 datasets and averaged discriminator fit loss over 128 runs; Figure 21 plots candidate-structure loss versus sample count.Source: Proof · p. 46, Figure 21 · p. 46

C. Parametric loss : illustration of Markov equivalence class disambiguation

This two-variable example tests whether functional regularization can distinguish causal directions when conditional-independence tests cannot. Across the tested regularization values, both fit and Frobenius losses favor X → Y.

C. Parametric loss : illustration of Markov equivalence class disambiguation

  • The example uses 500 samples from a two-variable nonlinear model, with X uniform on (−1, 1) and Y defined from a nonlinear function of X plus uniform noise.The plotted loss averages are over 32 runs, and error bars show standard deviations.Source: C. Parametric loss : illustration of… · pp. 46–47, Figure 22 · p. 47
  • Pearson correlation and conditional-independence tests cannot disambiguate the causal direction in this example.The Pearson coefficient is zero, nonlinear models are needed, and the setting has only two variables.Source: C. Parametric loss : illustration of… · p. 47
  • For all tested λF values, both Frobenius regularization loss and fit loss are lower for X → Y than Y → X, with a statistically significant difference (t-test, p-value 0.001).Figure 23 shows the losses across λF; solid lines denote X → Y and dashed lines denote Y → X.Source: C. Parametric loss : illustration of… · p. 47, Figure 23 · p. 48

D. Detail of the experimental results

SAM shows robustness across synthetic, realistic, and challenge datasets, while its relative performance varies by mechanism and task. On 100-variable graphs, its computational time favorably compares with CAM, and PC-HSIC exceeded the 50-hour limit.

20-variable artificial graphs

  • On 20-variable artificial graphs, SAM is robust across mechanism types, but GES dominates on linear mechanisms and CAM on GP AM and Sigmoid AM.The reported explanation is that GES is designed for linear mechanisms and CAM for additive noise.Source: D. Detail of the experimental results · p. 48, Table 3 · p. 49

100-variable artificial graphs

Realistic problems (SynTReN, GENIE3, and Cyto)

The Dream4 In Silico Multifactorial Challenge

The Dream5 Challenge

  • Dream5 results are reported for AUPR and AUC across three challenge graphs, but the supplied passages do not state which method performs best.The table captions identify the scores as organizer-reported best results for each method, without standard deviations.Source: Table 15 · p. 55, Table 16 · p. 55

E. Sensitivity to the sample size compare to other algorithms

SAM's results on 20-variable Gaussian-process graphs vary with sample size and noise type. CAM generally leads on additive-noise data, while SAM is more favorable on non-additive data above 500 points; SAM's performance is more sample-size dependent.

GP AM

GP Mix

Sample-size sensitivity

  • SAM's performance depends more on sample size than that of the other best competitors, which the paper explains by the data needs of its neural-network generators and discriminator.Source: E. Sensitivity to the sample size… · p. 56

F. Parametric loss : systematic experiment of Markov equivalence class disambiguation

The experiment tests whether SAM's parametric loss can orient edges within Markov equivalence classes when graphs have no v-structures. SAM performs well across the tested mechanisms, while ANM leads on additive-noise data.

Experimental setup

  • The experiment uses graphs with 20 variables and one parent per variable, so there are no v-structures and edge orientation is the target.It compares SAM with IGCI, ANM, and RECI on ten graphs per mechanism type.Source: F. Parametric loss : systematic… · p. 57

Results

  • No method can orient edges in Gaussian linear datasets because the variable pairs are completely symmetrical.The authors connect this to lower scores on linear synthetic mechanisms in the broader experiments.Source: F. Parametric loss : systematic… · p. 57
  • ANM achieves the best scores on additive-noise datasets, especially near-perfect results on GP AM, but performs less well than SAM on other noise types.The authors relate ANM's strength to its design for additive noise and Gaussian-process regression.Source: F. Parametric loss : systematic… · p. 57
  • SAM obtains overall good results across mechanisms compared with pairwise methods for disambiguating Markov equivalence classes.The comparison assesses edge orientation with AUPR and AUC, given the true graph skeleton.Source: F. Parametric loss : systematic… · p. 57, Table 17 · p. 57, Table 18 · p. 58

G. Robustness of the various methods to non-gaussian noise

With uniform rather than Gaussian noise, SAM has the best reported scores across datasets except those with additive noise. The authors report that distributional asymmetries in the linear setting let SAM's parametric fitting loss orient edges within a Markov equivalence class.

Experimental setup

  • The experiment uses 20-variable graphs with 500 points and uniform noise, while SAM retains Gaussian noise variables as generator inputs.Ten DAGs are generated for each mechanism type.Source: G. Robustness of the various methods… · p. 58

Results

Loading 1803.04929v5…