Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

Qing Zhou; Stella Huang

arxiv: 2506.05590 · v3 · submitted 2025-06-05 · 📊 stat.ML · cs.LG

Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

Stella Huang , Qing Zhou This is my paper

Pith reviewed 2026-05-19 10:16 UTC · model grok-4.3

classification 📊 stat.ML cs.LG

keywords causal discoveryadditive noise modelDAG learningnonlinear modelsstructural consistencyconstraint-based algorithmedge orientation

0 comments

The pith

A sequential procedure orients edges in a partial DAG to recover the true causal graph under restricted additive noise models.

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

The paper develops a method to orient the undirected edges in a completed partial directed acyclic graph by testing which direction better fits a pairwise additive noise model. It proves that this sequential ranking and testing procedure recovers the full causal structure when the data comes from a restricted additive noise model. The approach is turned into a full algorithm that starts from an estimated CPDAG and produces a directed graph, with a consistency guarantee as the number of samples grows. This addresses limitations of prior nonlinear causal discovery methods that are either too slow or too restrictive.

Core claim

Under the assumption of a restricted additive noise model, the proposed sequential procedure, which ranks undirected edges by their adherence to the pairwise additive noise model and orients each edge by comparing log-likelihoods on the relevant subgraph, recovers the true causal DAG. The full algorithm is structurally consistent in the large-sample limit.

What carries the argument

The ranking of edges by how well they satisfy the pairwise additive noise model, followed by a likelihood-ratio test on the sub-graph of the two nodes and their already-oriented parents.

If this is right

The method runs faster than many competing nonlinear causal discovery algorithms.
It remains reliable even when the model assumptions are mildly violated.
It produces a directed graph that is guaranteed to be consistent with the true structure for large data sets.
Experiments show better performance than existing methods on both synthetic and real data.

Where Pith is reading between the lines

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

If the restricted ANM holds only approximately, the method may still provide useful approximate orientations that can be refined with additional data.
Combining this orientation step with other CPDAG estimation techniques could improve end-to-end causal discovery pipelines in high dimensions.
Extensions to time-series or interventional data might follow from the same likelihood-comparison idea.

Load-bearing premise

The observations are generated by a restricted additive noise model and the starting completed partial DAG is correctly estimated.

What would settle it

Generate data from a nonlinear model that violates the restricted additive noise assumption, run the algorithm on the true CPDAG, and check whether the recovered orientations match the true directions.

read the original abstract

Recent advances have established the identifiability of a directed acyclic graph (DAG) under additive noise models (ANMs), spurring the development of various causal discovery methods. However, most existing methods make restrictive model assumptions, rely heavily on general independence tests, or require substantial computational time. To address these limitations, we propose a sequential procedure to orient undirected edges in a completed partial DAG (CPDAG), representing an equivalence class of DAGs, by leveraging the pairwise additive noise model (PANM) to identify their causal directions. We prove that this procedure can recover the true causal DAG assuming a restricted ANM. Building on this result, we develop a novel constraint-based algorithm for learning causal DAGs under nonlinear ANMs. Given an estimated CPDAG, we develop a ranking procedure that sorts undirected edges by their adherence to the PANM, which defines an evaluation order of the edges. To determine the edge direction, we devise a statistical test that compares the log-likelihood values, evaluated with respect to the competing directions, of a sub-graph comprising just the candidate nodes and their identified parents in the partial DAG. We further establish the structural learning consistency of our algorithm in the large-sample limit. Extensive experiments on synthetic and real-world datasets demonstrate that our method is computationally efficient, robust to model misspecification, and consistently outperforms many existing nonlinear DAG learning methods.

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.

Desk Editor's Note private letter to a colleague

This paper gives a sequential ranking-plus-local-test method to orient edges in a CPDAG for nonlinear ANMs, with a recovery proof under restricted ANM and large-sample consistency.

read the letter

The main thing to know is that this paper offers a sequential procedure for orienting undirected edges in a CPDAG under nonlinear additive noise models. It ranks edges by how closely they fit a pairwise ANM and then decides direction with a log-likelihood test on a small subgraph of the candidate nodes plus already-oriented parents. They prove this recovers the true DAG under a restricted ANM and establish structural consistency in the large-sample limit. Experiments show it runs faster and beats several existing nonlinear methods on synthetic and real data. That combination of ranking, local testing, and the recovery result is the concrete advance over prior ANM identifiability work. The local subgraph focus keeps computation reasonable and avoids broad independence tests at each step, which is a practical plus. The soft spots sit where the guarantees meet reality. Recovery needs the data to match the restricted ANM exactly and the input CPDAG to be correct from the start. Because orientation is sequential, an early ranking error or test mistake from finite samples or mild misspecification can alter parent sets for later edges and break the inductive argument. The abstract claims robustness in experiments, but the strength of that claim depends on how far the violations went in the tests. This is for researchers working on causal discovery in statistics and machine learning who want methods for nonlinear relations that come with some theory and speed. A reader who needs a new orientation step with consistency results would find it worth reading. It deserves a serious referee because the algorithmic twist and the stated recovery result are distinct enough to merit full review.

Referee Report

2 major / 2 minor

Summary. The paper proposes a sequential procedure for orienting undirected edges in an estimated CPDAG by ranking them according to adherence to the pairwise additive noise model (PANM) and then using a log-likelihood comparison test on local subgraphs (candidate nodes plus already-oriented parents) to decide direction. The authors prove that the procedure recovers the true DAG under a restricted ANM assumption and establish structural learning consistency in the large-sample limit. They also present a full constraint-based algorithm for nonlinear ANM DAG learning and report experiments showing computational efficiency and outperformance on synthetic and real-world data.

Significance. If the recovery guarantee and consistency result hold, the work supplies a computationally lighter alternative to existing nonlinear causal discovery methods while retaining identifiability results under a restricted ANM. The explicit ranking-plus-local-test design and the large-sample consistency statement are concrete strengths that could be useful for practitioners who already have a reliable CPDAG estimator.

major comments (2)

[§4] §4 (Theoretical Analysis), recovery theorem: the inductive argument for exact recovery assumes both that the input CPDAG is correct and that every pairwise test correctly identifies the true direction under the restricted ANM. Because orientation is strictly sequential and each step augments the parent sets used in later tests, an early finite-sample error or mild violation of the restricted ANM can alter the conditioning sets for subsequent edges, breaking the induction. The manuscript does not provide a robustness or error-propagation analysis that would close this gap.
[§3.3] §3.3 (Statistical test): the log-likelihood comparison is performed on a subgraph consisting only of the candidate nodes and their currently identified parents. It is not shown that this local subgraph is Markov-equivalent to the relevant marginal of the full model when the remaining undirected edges are still present; a counter-example or additional faithfulness condition would be needed to guarantee that the likelihood ratio correctly ranks the two directions.

minor comments (2)

[§2, §4] Notation for the restricted ANM is introduced in §2 but the precise functional-form restrictions (e.g., on the noise distributions or the functional classes) are not restated when the recovery theorem is invoked in §4; repeating the definition would improve readability.
[Experiments] In the experimental section the authors report average SHD and runtime but do not include variance across random seeds or a sensitivity plot with respect to the CPDAG estimation error rate; adding these would make the robustness claim easier to evaluate.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We address each major comment below, providing clarifications on the theoretical assumptions and indicating the revisions we will make to improve the manuscript.

read point-by-point responses

Referee: [§4] §4 (Theoretical Analysis), recovery theorem: the inductive argument for exact recovery assumes both that the input CPDAG is correct and that every pairwise test correctly identifies the true direction under the restricted ANM. Because orientation is strictly sequential and each step augments the parent sets used in later tests, an early finite-sample error or mild violation of the restricted ANM can alter the conditioning sets for subsequent edges, breaking the induction. The manuscript does not provide a robustness or error-propagation analysis that would close this gap.

Authors: We agree that the exact recovery theorem in Section 4 is established under the idealized assumptions of a correct input CPDAG and error-free tests at every step, which is standard for such inductive proofs in causal discovery. The large-sample consistency result separately shows that the procedure converges to the true DAG as n grows, with errors vanishing in probability. We acknowledge that a dedicated finite-sample robustness analysis for error propagation in the sequential process is absent. In the revised manuscript we will add a clarifying paragraph in Section 4 that explicitly states these assumptions, discusses the potential for propagation under mild violations, and includes a short supplementary simulation study examining sensitivity to small early-stage errors. This addresses the gap without altering the main theorems. revision: yes
Referee: [§3.3] §3.3 (Statistical test): the log-likelihood comparison is performed on a subgraph consisting only of the candidate nodes and their currently identified parents. It is not shown that this local subgraph is Markov-equivalent to the relevant marginal of the full model when the remaining undirected edges are still present; a counter-example or additional faithfulness condition would be needed to guarantee that the likelihood ratio correctly ranks the two directions.

Authors: Under the restricted ANM and the faithfulness conditions used throughout the paper, the local subgraph with already-oriented parents isolates the relevant conditional distribution for the direction test because the additive noise terms remain independent of the parents. The ranking procedure further ensures that edges are oriented in an order that respects the partial order implied by the CPDAG. Nevertheless, we accept that an explicit argument linking the local likelihood ratio to the marginal of the full model (accounting for pending undirected edges) would strengthen the justification. In the revision we will add a short lemma or remark in Section 3.3 that derives this equivalence from d-separation in the partial DAG together with the ANM structure, and we will state any additional faithfulness requirement more clearly. If a counter-example arises under our assumptions we will report it; otherwise the added condition will close the gap. revision: partial

Circularity Check

0 steps flagged

No significant circularity; recovery proof is conditional on external model assumptions

full rationale

The paper's central claim is a proof that the sequential edge-orientation procedure recovers the true DAG under a restricted ANM (with correct input CPDAG) and establishes large-sample structural consistency. This is a standard conditional identifiability result: the ranking by PANM adherence and the log-likelihood comparison on local subgraphs are shown to select true directions because the data-generating process satisfies the model, not because the procedure is defined to output the input. No quoted step reduces the claimed recovery to a fitted parameter or self-citation by construction. The derivation remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The recovery proof and consistency result rest primarily on the domain assumption of a restricted additive noise model; no free parameters or new entities are explicitly introduced in the abstract description.

axioms (1)

domain assumption Data is generated according to a restricted additive noise model (ANM).
The proof that the sequential procedure recovers the true DAG explicitly assumes this model class.

pith-pipeline@v0.9.0 · 5764 in / 1258 out tokens · 42471 ms · 2026-05-19T10:16:49.253456+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We propose a sequential procedure to orient undirected edges in a completed partial DAG (CPDAG) ... by leveraging the pairwise additive noise model (PANM) ... We prove that this procedure can recover the true causal DAG assuming a restricted ANM.
IndisputableMonolith/Foundation/AlphaCoordinateFixation.lean J_uniquely_calibrated_via_higher_derivative unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the likelihood ratio test ... compares the log-likelihood values ... of a sub-graph comprising just the candidate nodes and their identified parents

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.