Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models

Summary

This paper studies structure learning problem for additive noise model (ANM) in both linear and nonlinear settings. It proposes a hybrid constraint based approach to learn the DAG by leveraging the local ancestral relationships. The algorithm consists of ordering search and edge discovery these two steps. Correctness is shown and simulation is conducted to compare with other approaches.

Strengths

- Though ANM is shown to be identifiable for a long time, e.g. by RESIT, the high computational complexity and hardness in nonparametric regression and CI tests stand as roadblock. The finer analysis and exploitation of local structure in the proposal show potential to tackle this task efficiently; - The introducing of the proposed method is well-written and easy to follow for researchers working in relevant area.

Weaknesses

- The main contribution of this work is the exploitation of local structure to reduce the number of nonparametric regression and CI tests. However, despite of the quick discussion below thm 3.7 and 4.5, there is no explicit and formal statement on these to emphasize the contribution, and also comparison with others, e.g. RESIT. - The experiments are preliminary. More setups should be considered to demonstrate the superiority of proposal: e.g. different graph types like scale-free graphs, different number of edges, different noise, recovery criterion like F1 for linear setting, more benchmarks like CAM, GSGES, etc. - See Questions.

Questions

- As the main contribution of the paper, why are the runtime results in the appendix? It is also spurious that the runtime for linear case is slower than the benchmarks in Figure 7; runtime for d=12 is faster than d=8 in Figure 8. There does not seem to be significant improvement empirically; - Since theoretically the number of nonparametric regression and CI tests are reduced, is it possible to establish some statistical guarantee and sample complexity dependence on the sparsity, e.g. in-degree?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No limitation is discussed in the paper.

Summary

In this paper, the authors present a causal discovery method by firstly determining the order of the causal variables, then determining the existence of edges between any two variables. The experimental results demonstrate the superiority of the proposed method compared to relevant methods.

Strengths

I thank the authors for their detailed clarifications, which address most of my concerns. I increase my score to 5. ------------------------------------ Despite the theoretical results simple, the idea and the method are interesting and somewhat novel. The theoretical results seem sensible.

Weaknesses

1. Lack of necessary discussions: I think there are some similar idea in the literature, such as [1], where they maintain the order of the variables. What is the advantage of this method on [1]? The proposed method should be compared to [1] as well. [1] L. Solus, Y. Wang, C. Uhler, and L. Matejovicova. Consistency guarantees for permutation based causal inference algorithms. ArXiv preprint arXiv: 1702.03530 (2017) 2. Lemma 4.1 is confusing. In the condition, it is required that $x_i$ is one of the parents of $x_j$. Why is it possible that $x_i$ and $x_j$ are not causally related? typo: Line 202: the

Questions

Could the authors further elaborate on Line 205 - 207? It is not quite clear to me why Alg. 1 cannot be used for the non-linear case. I am happy to adjust my score according to the authors' rebuttal.

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

No.

Summary

The paper presents theoretical results about extensions of the partial order induced by a causal DAG and uses these results to propose new constraint-based algorithms for ANMs. **Edit**: increased rating from 3 to 5, soundness from 1 to 2, and contribution from 2 to 3. **Edit 2**: increase rating from 5 to 6, after the authors fixed $A_{top}$ calculation; solid paper, but I think the impact of a hybrid causal discovery method like this is limited

Strengths

- Takes a simple idea (which seems original but also somewhat obvious from an order theory perspective) and turns it (creatively, originally) into causal discovery algorithms with contisency guarantees, broad applicability (ANMs), and good identifiability (specific DAG instead of MEC) - Very clearly written, as far as grammar, organization, motivation (but importantly, not mathematical notation) - Based on the theoretical results, the algorithms have potential to be very significant to the field of causal discovery

Weaknesses

1. The main (and fatal) weakness is the claims of strong performance in the abstract combined with the inadequate experimental results: 1. the abstract makes a claim of "achieving greater accuracy than current methods", but then the limited experiments only compare on simulated data (rather than real) to a few closely related algorithms (as opposed to a selection of classic or state-of-the-art methods, such as PC or GRaSP) in settings the authors have already explained are challenging for existing algorithms (very sparse DAGs, rather than a range of sparsities), and even then the proposed algorithm doesn't seem to do especially well. It also seems the NHTS algorithm is missing from the experiments. 2. A smaller but nonetheless important weekness is notation that contradicts mathematical conventions, making the writing unecessarily difficult: 1. consulting introductory texts on partial orders and order theory would help clear up some of the confusion. For example, a topological sort is conventionally a linear extension of a partial order, making the introduced terms "linear topological sort" and "hierarchical topological sort" confusing. Replacing the former introduced term with just "topological sort", "linear order", or "total order", and replacing the latter introduced term with something that more clearly indicates it is 'between' a partial order and a linear order (i.e., it extends the partial order, but not completely into linear order), would be more natural/conventional and easier to understand. 2. the authors seem to use $\mapsto$ to indicate the domain and image of the ordering functions, but $\mapsto$ conventionally denotes how a specific element in the domain is mapped to a specific element of the image, hindering precise and easy comprehension. 3. other notation in Definition 2.1, such as inconsistent/unexplained indexing of $\pi$ make the definition harder to understand/not rigorous 4. it's unclear what the difference between $x_j \dashrightarrow x_i$ (called a directed path) and $x_j \dashrightarrow \ldots \dashrightarrow x_k$ (called a front door path) is.

Questions

1. Aren't there just $d \choose 2$ (i.e., number of entries above the diagonal of a corresponding adjacency matrix) possible edges in a DAG for a given linear order, rather than the $d^2$ claimed on line 303? 2. Suggestion: Include more explicit theorem statements and proofs for the complexity results.

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

The authors have adequately described what assumptions their methods require (and hence to which settings the results are limited).

Summary

The paper mainly focuses on proposing efficient search algorithms for finding the hierarchical sort ordering (linear topological sort) of variables. As mentioned in Section 5, finding such hierarchical orders can significantly improve the efficiency of causal discovery of edges, making the algorithm tractable (traditional algorithms such as PC are exponential). The paper studies two cases: linear (LiNGAMs) and non-parametric, where a complete algorithm based only on path analysis is developed for the linear case, and a combination of path analysis and layer-wise search is developed for the non-parametric case. Both algorithms improve the discovery of hierarchical order.

Strengths

The paper is well structured and clearly written. The theoretical contributions, including the causal path analysis and corresponding algorithms, are interesting and also important in practice as can be told from the analysis of computational complexity. All results are properly formulated as definitions and theorems and proofs are included in the appendix. Experiments are also conducted and their results are discussed in depth in Section 6. In general, I enjoyed reading it.

Weaknesses

- In general, I suggest adding more examples to demonstrate the procedure of algorithms, probably for NHTS (Algorithm 2) so that we can see a clear cut between the two stages (root-identification and layer identification). - While the authors touched a bit at the beginning of Section 4, non-experts may benefit more if the paper could include additional details about the difference between the linear and non-linear cases (especially how they affect conditional independencies if any). - For definition 2.1, it will be great to provide a hierarchical topological sort that cannot be trivially converted to a linear topological sort; that is, we cannot simply add more layers to a hierarchical sort to obtain a linear topological sort. - Lemma 4.1 is a little confusing to me: if $x_i$ is a parent of $x_j$, how are PP1 and PP4 possible? $x_i$ must be a direct cause of $x_j$, right? Also, when you say "$x_i$ and $x_j$" are not causally related, does it mean that there is no directed edge from $x_i$ to $x_j$ or no directed path? Does "active path" mean any unblocked dependency path (backdoor or frontdoor)?

Questions

- I'm curious if it's all the results can also be explained using independencies (d-separations) instead of regressions? This allows us to think only in terms of graphs. I guess regressions in the non-parametric setting are equivalent to d-separations, how about the linear case? Are there any independencies that hold in the linear case but not in the non-parametric case? - For algorithm 1 (LHTS), is stage 2 really needed? It seems that stage 2 is a special case of stage 3 when mutual ancestors = $\emptyset$. - For experiments, the paper mentions a tradeoff between accuracy and encoded causal information. Would it be more fair to restrict the ordering length (say limit it to some length $k$) and compare the ordering accuracy?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

OK

Topological Ordering Evaluation for GES, GRaSP, GSP

We thank Reviewer rTf8 for appreciating the strength of our new experimental results (see attached PDF). In our experiments, $A_{top}$ is computed for methods that return an MEC in two steps: 1) we select one topological sort $\pi_{\mathrm{MEC}}$ permitted by the returned MEC, 2) we set $A_{top}$ equal to the percentage of edges that can be recovered from $\pi_{\mathrm{MEC}}$. Step 2) is identical for every method in our experiments; _as a representative example, we walk through how step 1) is done for GES._ We use the implementation of GES provided by the causal-learn [1] python package, which returns a 'completed partially directed acyclic graph' (CPDAG) $CG$. _A CPDAG is a compact matrix representation of a MEC of DAGs_, commonly used in the literature [2]. In particular, $CG[j,i]=1,G[i,j]=-1$ indicates $i\rightarrow j$, $CG[j,i]=G[i,j]=-1$ indicates $i-j$, i.e., there exists an edge between $i,j$ with an unknown orientation, and $CG[j,i]=CG[i,j]=0$ if no edge exists between $i,j$. To select a valid topological sort $\pi_{\mathrm{MEC}}$ from $CG$, we first initialize a list of sorted vertices $\pi_{MEC} = []$ and a list of unsorted vertices $U = ${$1,\ldots,|V|$}. We then iteratively sort one vertex at a time in $U$ into $\pi_{MEC}$: _in each iteration, we first determine the set of vertices $R\in U$ that have no parents in $U$_, i.e. $R = ${$i\in U: CG[j,i] ~!= 1 ~\forall j \in U, j \neq i$}. We then uniformly randomly select a vertex from $R$, remove it from $U$, and append it to $\pi_{MEC}$. After $|V|$ iterations, $\pi_{MEC}$ is valid with respect to $CG$: by construction, if $i\rightarrow j$, i.e. $CG[j,i]=1$, then $\pi_{MEC}(i) < \pi_{MEC}(j)$. We emphasize that, under the assumptions made by traditional discovery algorithms such as GES, all topological orderings contained within a MEC are _equally valid_: every such ordering corresponds to a DAG that satisfies every conditional independence constraint found in the data. Therefore, these algorithms _cannot distinguish between any ordering present in the MEC._ This motivates the uniformly random selection of one valid topological ordering from the MEC for downstream comparison with LHTS and NHTS. **Citations** - [1] Zheng et. al, Causal-learn: Causal Discovery in python, (2024). - [2] Perkovic et. al, Complete Graphical Characterization and Construction of Adjustment Sets in Markov Equivalence Classes of Ancestral Graphs, (2018).

Updated Evaluation for GES, GRaSP, GSP

We **agree** with Reviewer rTf8's description of the issue concerning the computation of $A_{top}$ for GES, GRaSP, and GSP, and apologize for the error. We thank Reviewer rTf8 for catching this mistake. Following Reviewer rTf8's suggestion, we update how $A_{top}$ is computed for GES, GRaSP, and GSP; we use the function `pdag2dag` provided by the `causal-learn` python package [1] to randomly select a DAG from returned CPDAGs (replacing step 1 in our previous official comment). Fortunately, we saved all of the raw results from the experiments in the attached PDF (true DAGs from each trial, returned DAGs/CPDAGs for each method, etc.): using the updated $A_{top}$ measure, we have re-evaluated the original results. We find that, although GES, GRaSP, and GSP show improved performance when measured by the updated $A_{top}$, _NHTS still has the highest median score in all experiments, supporting our claim of superior performance._ We are instructed not to post links to images, and are therefore unable to directly display the plots; instead, at the bottom of this comment we provide the original median $A_{top}$ for NHTS, and updated median $A_{top}$ for GES, GRaSP, and GSP in all experiments. Additionally, we respectfully note that 1) we have already processed the data to ensure it is sufficiently challenging, and 2) incorporated comparison to a variant of `sortnregress` . In Lines 314-316 of our original submission, we clarify that "data were standardized to zero mean and unit variance" _to avoid gameability by `var_sort_regress`_ [2], which uses marginal variance as an ordering criterion. The data generated for the new experiments were standardized through the same process. Furthermore, in Line 329 of our original submission we describe the benchmark `r2_sort_regress` [3], a scale invariant version of `sortnregress` which uses $R^2$ as an ordering criterion. _We had included `r2_sort_regress` as a benchmark in the new experiments, under the name "R2ST"_: R2ST was outperformed by NHTS in all experiments. **Updated Median $A_{top}$ Scores for NHTS, GES, GRaSP, and GSP** _Gauss, ER1, d=10_ - **NHTS: 1.00** | GES: 0.88 | GRaSP: 0.93 | GSP: 0.35 | _Gauss, ER2, d=10_ - **NHTS: 0.80** | GES: 0.65 | GRaSP: 0.70 | GSP: 0.48 | _Gauss, ER3, d=10_ - **NHTS: 0.84** | GES: 0.68 | GRaSP: 0.81 | GSP: 0.43 | _Gauss, ER4, d=10_ - **NHTS: 0.73** | GES: 0.52 | GRaSP: 0.65 | GSP: 0.54 | _Gauss, ER1, d=20_ - **NHTS: 1.00** | GES: 0.86 | GRaSP: 0.89 | GSP: 0.57 | _Gauss, ER2, d=20_ - **NHTS: 0.86** | GES: 0.85 | GRaSP: 0.84 | GSP: 0.53 | _Gauss, ER3, d=20_ - **NHTS: 0.83** | GES: 0.76 | GRaSP: 0.73 | GSP: 0.50 | _Gauss, ER4, d=20_ - **NHTS: 0.88** | GES: 0.61 | GRaSP: 0.57 | GSP: 0.44 | _Unif, ER1, d=10_ - **NHTS: 1.00** | GES: 0.74 | GRaSP: 0.85 | GSP: 0.47 | _Unif, ER2, d=10_ - **NHTS: 0.90** | GES: 0.70 | GRaSP: 0.62 | GSP: 0.49 | _Unif, ER3, d=10_ - **NHTS: 0.97** | GES: 0.64 | GRaSP: 0.66 | GSP: 0.46 | _Unif, ER4, d=10_ - **NHTS: 0.98** | GES: 0.59 | GRaSP: 0.57 | GSP: 0.39 | _Unif, ER1, d=20_ - **NHTS: 1.00** | GES: 0.75 | GRaSP: 0.69 | GSP: 0.60 | _Unif, ER2, d=20_ - **NHTS: 0.86** | GES: 0.77 | GRaSP: 0.73 | GSP: 0.57 | _Unif, ER3, d=20_ - **NHTS: 0.99** | GES: 0.66 | GRaSP: 0.70 | GSP: 0.51 | _Unif, ER4, d=20_ - **NHTS: 0.94** | GES: 0.59 | GRaSP: 0.63 | GSP: 0.54 | _Lapla, ER1, d=10_ - **NHTS: 0.97** | GES: 0.93 | GRaSP: 0.92 | GSP: 0.48 | _Lapla, ER2, d=10_ - **NHTS: 0.88** | GES: 0.70 | GRaSP: 0.76 | GSP: 0.50 | _Lapla, ER3, d=10_ - **NHTS: 0.82** | GES: 0.73 | GRaSP: 0.71 | GSP: 0.47 | _Lapla, ER4, d=10_ - **NHTS: 0.79** | GES: 0.75 | GRaSP: 0.70 | GSP: 0.43 | _Lapla, ER1, d=20_ - **NHTS: 0.89** | GES: 0.85 | GRaSP: 0.83 | GSP: 0.54 | _Lapla, ER2, d=20_ - **NHTS: 0.98** | GES: 0.86 | GRaSP: 0.79 | GSP: 0.51 | _Lapla, ER3, d=20_ - **NHTS: 0.73** | GES: 0.68 | GRaSP: 0.64 | GSP: 0.47 | _Lapla, ER4, d=20_ - **NHTS: 0.77** | GES: 0.63 | GRaSP: 0.65 | GSP: 0.53 | **Citation** - [1] Zheng et. al, Causal-learn: Causal Discovery in python, (2024). - [2] Reisach et. al, Beware of the simulated DAG! Causal discovery benchmarks may be easy to game, (2021). - [3] Reisach et. al, A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models, (2023).