pith. sign in

arxiv: 2409.00417 · v1 · submitted 2024-08-31 · 💻 cs.LG · stat.ME

Learning linear acyclic causal model including Gaussian noise using ancestral relationships

Ming Cai , Penggang Gao , Hisayuki Hara This is my paper

Pith reviewed 2026-05-23 21:14 UTC · model grok-4.3

classification 💻 cs.LG stat.ME
keywords causal discoverylinear causal modelsGaussian noiseancestral relationshipsdistribution equivalencePC-LiNGAMtime complexity
0
0 comments X

The pith

An algorithm identifies distribution-equivalence patterns of linear causal models with Gaussian disturbances using ancestral relationships at lower time complexity than PC-LiNGAM.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops an algorithm to learn the distribution-equivalence pattern of linear acyclic causal models that include Gaussian noise. It builds on a causal ancestor finding method by generalizing it to handle Gaussian disturbances, then uses those ancestral relationships to determine the pattern. The key advantage is reduced time complexity compared to the PC-LiNGAM hybrid approach, which can require factorial time in the worst case. A reader would care because many real-world causal systems involve Gaussian noise, and faster identification makes the method practical for more variables.

Core claim

By generalizing the causal ancestor finding algorithm to account for Gaussian disturbances, the distribution-equivalence pattern of a linear causal model can be identified with lower time complexity than PC-LiNGAM.

What carries the argument

The generalized causal ancestor finding algorithm that recovers ancestral relationships in the presence of Gaussian disturbances.

If this is right

  • The algorithm identifies up to the distribution-equivalence pattern even when Gaussian disturbances are present.
  • It achieves lower time complexity than the PC-LiNGAM method.
  • It relies on ancestral relationships rather than exhaustive search over permutations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Scaling to larger variable sets becomes more feasible for causal discovery tasks involving mixed noise types.
  • The approach may combine with other constraint-based methods to further improve efficiency in high-dimensional settings.
  • Real-world applications in economics or biology could adopt this for quicker model learning under Gaussian assumptions.

Load-bearing premise

The generalization of the causal ancestor finding algorithm correctly handles Gaussian disturbances while preserving recovery of the ancestral relationships needed for distribution-equivalence patterns.

What would settle it

A simulation on a known linear causal model with Gaussian noise where the algorithm outputs an incorrect distribution-equivalence pattern that differs from what PC-LiNGAM recovers.

Figures

Figures reproduced from arXiv: 2409.00417 by Hisayuki Hara, Ming Cai, Penggang Gao.

Figure 2
Figure 2. Figure 2: illustrates a procedure of the PC-LiNGAM. Diamond nodes repre [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 2.1
Figure 2.1. Figure 2.1: An example to illustrate the PC-LiNGAM when handling a directed [PITH_FULL_IMAGE:figures/full_fig_p007_2_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: illustrates how the proposed method identifies a DEP. In Figure [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 3.1
Figure 3.1. Figure 3.1: An example to illustrate the proposed method when handling a [PITH_FULL_IMAGE:figures/full_fig_p013_3_1.png] view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: An example to illustrate how Algorithm 3 outputs an incorrect [PITH_FULL_IMAGE:figures/full_fig_p014_3_2.png] view at source ↗
Figure 3.3
Figure 3.3. Figure 3.3: An example to illustrate the flow of Algorithm 4 to handle the [PITH_FULL_IMAGE:figures/full_fig_p016_3_3.png] view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: CPU time of the proposed algorithm and the PC-LiNGAM against [PITH_FULL_IMAGE:figures/full_fig_p019_4_1.png] view at source ↗
Figure 4.2
Figure 4.2. Figure 4.2: CPU time and estimation accuracy of the proposed algorithm and [PITH_FULL_IMAGE:figures/full_fig_p019_4_2.png] view at source ↗
read the original abstract

This paper discusses algorithms for learning causal DAGs. The PC algorithm makes no assumptions other than the faithfulness to the causal model and can identify only up to the Markov equivalence class. LiNGAM assumes linearity and continuous non-Gaussian disturbances for the causal model, and the causal DAG defining LiNGAM is shown to be fully identifiable. The PC-LiNGAM, a hybrid of the PC algorithm and LiNGAM, can identify up to the distribution-equivalence pattern of a linear causal model, even in the presence of Gaussian disturbances. However, in the worst case, the PC-LiNGAM has factorial time complexity for the number of variables. In this paper, we propose an algorithm for learning the distribution-equivalence patterns of a linear causal model with a lower time complexity than PC-LiNGAM, using the causal ancestor finding algorithm in Maeda and Shimizu, which is generalized to account for Gaussian disturbances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proposes an algorithm to identify the distribution-equivalence pattern of a linear acyclic causal model with Gaussian disturbances. It generalizes the causal ancestor finding procedure from Maeda and Shimizu to handle Gaussian noise and asserts that the resulting method has lower time complexity than PC-LiNGAM while recovering the same equivalence class.

Significance. If the generalization is valid, the result would supply a more scalable procedure for recovering distribution-equivalence classes in linear models that admit Gaussian noise, addressing the factorial worst-case complexity of PC-LiNGAM. The work extends prior causal-discovery algorithms and could support larger variable counts in mixed-Gaussian settings.

major comments (1)
  1. [Abstract] Abstract: the claim that the Maeda-Shimizu ancestor-finding algorithm can be generalized to Gaussian disturbances while still recovering the ancestral relations needed for distribution-equivalence patterns is asserted without any derivation, proof sketch, or example. This generalization is the single load-bearing step for both soundness and the stated complexity improvement; if it fails to return correct ancestors under all-Gaussian noise, the subsequent pattern-recovery step is unsound.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and constructive feedback. We address the single major comment below and will revise the manuscript to strengthen the presentation of the generalization.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that the Maeda-Shimizu ancestor-finding algorithm can be generalized to Gaussian disturbances while still recovering the ancestral relations needed for distribution-equivalence patterns is asserted without any derivation, proof sketch, or example. This generalization is the single load-bearing step for both soundness and the stated complexity improvement; if it fails to return correct ancestors under all-Gaussian noise, the subsequent pattern-recovery step is unsound.

    Authors: We agree that the abstract asserts the generalization without supporting detail. In the revised manuscript we will expand the abstract with a concise proof sketch (or a short illustrative example) showing why the Maeda-Shimizu ancestor-finding procedure remains valid under Gaussian noise and still recovers the ancestral relations required for the distribution-equivalence pattern. The full derivation will remain in the body of the paper; the abstract change will make the soundness claim explicit while respecting length constraints. revision: yes

Circularity Check

0 steps flagged

No circularity; extends external Maeda-Shimizu ancestor finding via explicit generalization

full rationale

The derivation chain rests on generalizing the cited Maeda-Shimizu causal ancestor finding algorithm to Gaussian disturbances and then applying it to recover distribution-equivalence patterns. The abstract and description present this generalization as a novel algorithmic step rather than a reduction to fitted parameters, self-definitions, or load-bearing self-citations. The referenced prior work has non-overlapping authors and is treated as an independent external input. No equations or claims in the provided material reduce by construction to the target result; the method is positioned as building on (not presupposing) the cited algorithm. This is the common case of an independent algorithmic contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.0 · 5683 in / 905 out tokens · 22008 ms · 2026-05-23T21:14:01.023257+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 1 internal anchor

  1. [1]

    Andersson, David Madigan, and Michael D

    Steen A. Andersson, David Madigan, and Michael D. Perlman. A charac- terization of Markov equivalence classes for acyclic digraphs. The Annals of Statistics, 25(2):505–541, 1997

    work page 1997

  2. [2]

    Learning causal graphs using variable group- ing according to ancestral relationship

    Ming Cai and Hisayuki Hara. Learning causal graphs using variable group- ing according to ancestral relationship. arXiv preprint arXiv:2403.14125 , 2024. 20

    work page arXiv 2024

  3. [3]

    SADA: A general frame- work to support robust causation discovery

    Ruichu Cai, Zhenjie Zhang, and Zhifeng Hao. SADA: A general frame- work to support robust causation discovery. In International Conference on Machine Learning, pages 208–216. PMLR, 2013

    work page 2013

  4. [4]

    Optimal structure identification with greedy search

    David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research , 3:507–554, 2002

    work page 2002

  5. [5]

    Harald Cram´ er.Random variables and probability distributions . 36. Cam- bridge University Press, 2004

    work page 2004

  6. [6]

    Analyse g´ en´ erale des liaisons stochastiques: etude parti- culi` ere de l’analyse factorielle lin´ eaire.Revue de l’Institut international de statistique, pages 2–8, 1953

    George Darmois. Analyse g´ en´ erale des liaisons stochastiques: etude parti- culi` ere de l’analyse factorielle lin´ eaire.Revue de l’Institut international de statistique, pages 2–8, 1953

    work page 1953

  7. [7]

    Global identifiability of linear structural equation models

    Mathias Drton, Rina Foygel, and Seth Sullivant. Global identifiability of linear structural equation models. The Annals of Statistics , 39:865–886, 2011

    work page 2011

  8. [8]

    The dual PC algorithm and the role of Gaussianity for structure learning of Bayesian networks

    Enrico Giudice, Jack Kuipers, and Giusi Moffa. The dual PC algorithm and the role of Gaussianity for structure learning of Bayesian networks. International Journal of Approximate Reasoning , 161:108975, 2023

    work page 2023

  9. [9]

    A kernel statistical test of independence

    Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Sch¨ olkopf, and Alex Smola. A kernel statistical test of independence. Ad- vances in Neural Information Processing Systems , 20, 2007

    work page 2007

  10. [10]

    Hoyer, Aapo Hyvarinen, Richard Scheines, Peter Spirtes, Joseph Ramsey, Gustavo Lacerda, and Shohei Shimizu

    Patrik O. Hoyer, Aapo Hyvarinen, Richard Scheines, Peter Spirtes, Joseph Ramsey, Gustavo Lacerda, and Shohei Shimizu. Causal discovery of linear acyclic models with arbitrary distributions. In Proceedings of the Twenty- Fourth Conference on Uncertainty in Artificial Intelligence, UAI2008 , pages 282–289, 2008

    work page 2008

  11. [11]

    Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bern- hard Sch¨ olkopf

    Patrik O. Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bern- hard Sch¨ olkopf. Nonlinear causal discovery with additive noise models. Advances in Neural Information Processing Systems , 21, 2008

    work page 2008

  12. [12]

    Hoyer, Shohei Shimizu, Antti J

    Patrik O. Hoyer, Shohei Shimizu, Antti J. Kerminen, and Markus Palvi- ainen. Estimation of causal effects using linear non-Gaussian causal models with hidden variables. International Journal of Approximate Reasoning , 49(2):362–378, 2008

    work page 2008

  13. [13]

    Independent component analysis

    Aapo Hyv¨ arinen, Juha Karhunen, and Erkki Oja. Independent component analysis. Studies in Informatics and Control , 11(2):205–207, 2002

    work page 2002

  14. [14]

    Aapo Hyv¨ arinen, Kun Zhang, Shohei Shimizu, and Patrik O. Hoyer. Esti- mation of a structural vector autoregression model using non-Gaussianity. Journal of Machine Learning Research , 11(56):1709–1731, 2010

    work page 2010

  15. [15]

    Estimating high-dimensional directed acyclic graphs with the PC-algorithm

    Markus Kalisch and Peter B¨ uhlman. Estimating high-dimensional directed acyclic graphs with the PC-algorithm. Journal of Machine Learning Re- search, 8(3):613–636, 2007. 21

    work page 2007

  16. [16]

    A fast PC algorithm for high dimensional causal discovery with multi-core PCs

    Thuc Duy Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu, and Shu Hu. A fast PC algorithm for high dimensional causal discovery with multi-core PCs. IEEE/ACM Transactions on Computational Biology and Bioinfor- matics, 16(5):1483–1495, 2016

    work page 2016

  17. [17]

    RCD: Repetitive causal discovery of linear non-Gaussian acyclic models with latent confounders

    Takashi Nicholas Maeda and Shohei Shimizu. RCD: Repetitive causal discovery of linear non-Gaussian acyclic models with latent confounders. In International Conference on Artificial Intelligence and Statistics , pages 735–745. PMLR, 2020

    work page 2020

  18. [18]

    Strong completeness and faithfulness in Bayesian net- works

    Christopher Meek. Strong completeness and faithfulness in Bayesian net- works. In Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, UAI’95, pages 411–418, 1995

    work page 1995

  19. [19]

    An analysis of variance test for normality (complete samples)

    Samuel Sanford Shapiro and Martin Bradbury Wilk. An analysis of variance test for normality (complete samples). Biometrika, 52(3–4):591–611, 1965

    work page 1965

  20. [20]

    Hoyer, Aapo Hyv¨ arinen, Antti Kerminen, and Michael Jordan

    Shohei Shimizu, Patrik O. Hoyer, Aapo Hyv¨ arinen, Antti Kerminen, and Michael Jordan. A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research , 7:2003–2030, 2006

    work page 2003

  21. [21]

    Hoyer, and Kenneth Bollen

    Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyv¨ arinen, Yoshinobu Kawahara, Takashi Washio, Patrik O. Hoyer, and Kenneth Bollen. Directlingam: A direct method for learning a linear non- Gaussian structural equation model. Journal of Machine Learning Re- search, 12:1225–1248, 2011

    work page 2011

  22. [22]

    On a property of the normal distribution

    Viktor Pavlovich Skitovich. On a property of the normal distribution. Doklady Akademii Nauk , 89:217–219, 1953

    work page 1953

  23. [23]

    An algorithm for fast recovery of sparse causal graphs

    Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review , 9:62–72, 1991

    work page 1991

  24. [24]

    Causation, prediction, and search

    Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2001

    work page 2001

  25. [25]

    Parcelingam: A causal ordering method robust against latent confounders

    Tatsuya Tashiro, Shohei Shimizu, Aapo Hyv¨ arinen, and Takashi Washio. Parcelingam: A causal ordering method robust against latent confounders. Neural Computation, 26(1):57–83, 2014

    work page 2014

  26. [26]

    An algorithm for deciding if a set of observed independence has a causal explanation

    Thomas Verma and Judea Pearl. An algorithm for deciding if a set of observed independence has a causal explanation. In Proceedings of the 8th Conference on Uncertainty in Artificial Intelligence, UAI’92 , pages 323–

    work page

  27. [27]

    Learning causal structures based on divide and conquer

    Hao Zhang, Shuigeng Zhou, Chuanxu Yan, Jihong Guan, Xin Wang, Ji Zhang, and Jun Huan. Learning causal structures based on divide and conquer. IEEE Transactions on Cybernetics , 52(5):3232–3243, 2020

    work page 2020

  28. [28]

    On the Identifiability of the Post-Nonlinear Causal Model

    Kun Zhang and Aapo Hyv¨ arinen. On the identifiability of the post- nonlinear causal model. arXiv preprint arXiv:1205.2599 , 2012. 22 A. Appendix A.1. Some basic facts on the linear causal model This section summarizes some basic facts necessary for the proof of Theorem 3.1 and 3.3. Consider the linear acyclic model (3.1). Denote by bj,i the (j, i)-elemen...

    work page internal anchor Pith review Pith/arXiv arXiv 2012