Learning DAGs from Data with Few Root Causes

Summary

The paper studies a new causal discovery method, in which it assumes that the DAG data is produced by few data-generating events whose effect percolates through the DAG. They propose a simple but effective method to learn the true DAG based on the few roots assumption. The proposed method outperforms baselines in various settings.

Strengths

1. The few roots assumption is reasonable. And the paper motivates it well. 2. The proposed solution is simple and effective. 3. The paper conducts experiments on both synthetic and real-world datasets, indicating the effectiveness of the proposed method.

Weaknesses

1. It is not clear why the objective function Eq.(10) contains noise. It needs more clear explanation and derivation here. 2. I wonder whether the proposed method could find the root nodes at the same time rather than just learning the DAG. 3. The proposed method could not achieve the best results on real-world datasets. Hence, I doubt the few roots assumptions satisfy the real-world scenarios. BTW, it is better to say the network is a protein network rather than a gene network.

Questions

Please reply to the questions in the weaknesses. I am willing to raise the score if all the concerns are solved.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper considers a new setting of linear DAG learning problem. Based on a linear transform of linear SEM, authors propose to study a new setting where there are few "root causes", with potential measurement noise in the data. Identifiability is proved and the true DAG is shown to be the global minimizer of the L0-norm of the vector of "root causes", under a specific distribution on the "root cause" variables.

Strengths

- a new setting for the linear DAG learning problem - useful identification result (Thm. 3.2) with a complete proof

Weaknesses

- the new setting and its motivating example are not sufficiently convincing. - authors only consider specific distribution on the "root causes" variables, making theoretic result somewhat limited - some results are trivial from the literature (e.g., Thm 2.1)

Questions

- My first concern is about the new setting of learning linear DAGs; it is not clear whether the new setting is indeed meaningful in practice. In the pollution model example, it is stated that "the relevant DAG data is triggered by sparse events on the input size and not by random noise ", and "We assume a DAG describing a river network. The acyclicity is guaranteed since flows only occur downstream. .. We assume that the cities can pollute the rivers." In this example, why do we need to learn DAGs? The graph structure can be more accurately obtained by getting the information of flows. As such, I suggest authors give more practical examples in the context of DAG learning, to make the new setting indeed meaningful. - root causes: in the DAG learning literature, "root causes" generally refer to the source nodes of DAGs. Not sure if it is suitable to use a (somewhat) conventional name to refer to something new in the same context. * Theorem 2.1 is not new and may be not stated as a theorem. * Regarding Thm 3.1: similarly, the result simple follows from the LiNGAM result, by assuming a specific distribution on the "root causes", so maybe consider put it as a lemma or proposition. Besides, in the experiments in the supplementary material, I can see LiNGAM failed. Can you explain why? After all, the linear SEM falls exactly into the setting of LiNGAM if there no measurement noise. * after Eq. 8, "Among all possible DAG matrices, the solution of the optimization problem (8) is the one that minimizes the number of the root causes X": can you give more details about this claim? * This may be a bit picky, but only sparse graphs (with edge/node=2 and 3) are considered. Please try other degrees of graphs. (But this is not very important and may be added after the rebuttal.) * please use \cite, \citet properly; e.g., line 131 line 181-182 Overall, I like the new setting of learning linear DAGs, but every new setting should be validated with more examples/details. I look forward to author response.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Authors discussed a limitation that the proposed method only works for few root causes in the paper. To me, another important limitation is the specific distribution assumption on the "root causes", as the proof heavily depends on this assumption.

Summary

This paper considers learning of linear SEMs (weight matrix) under a data generation process that differs from the common formulation. It is assumed that each sample is generated from only few number of non-zero noise variables in which the set of noise variables is stochastic. The main theoretical result is identifiability of the weight matrix via an L0 norm objective. A relaxation of the objective with an L1 norm loss is used for extensive synthetic experiments and shown to be effective for learning the weight matrix under the proposed data generation mechanism.

Strengths

- Sparse root causes are an interesting concept to explore. - Experiments on synthetic data demonstrate strong performance. Specifically, the proposed algorithm is fast and seems to scale up well, and when the assumptions are violated slightly, the algorithm still yields reasonable results.

Weaknesses

- While the sparse root causes assumption is interesting, it is not well-motivated. For the pollution example, if I understand correctly, the top left and bottom left nodes do not really play “causal” roles in the sense that they are deterministic mediators in the system, and the whole causal system can be represented without using those nodes. In this sense, “few root nodes” become the effective causal nodes. Am I missing something? The numerical evaluations using real data also do not provide much help for motivation. - NNZ is not a strong metric when SHD is already provided, and the only edge of the proposed algorithm in the real data experiments is this metric. - Presentation can be improved. For instance, Theorem 2.1 formulation of the linear SEM is trivial. Similarly, having $N_c$ and $N_x$ separately is superfluous; having a single small variance, not necessarily isotropic noise suffices for the description.

Questions

- The authors can elaborate on the Weaknesses item 1. - An additional question for the presentation. In L103-105, “The high-level intuition is that it can be reasonable to assume that, with the viewpoint of (3), the relevant DAG data is triggered by sparse events on the input size and not by random noise.” At first, I thought that you only consider a fixed subset of the nodes that have “random noise” with large magnitudes at each sample. If that was the case, the data is not i.i.d, the events are sparse on the input size, but it doesn’t necessarily occur on the same set of variables and I was puzzled with the importance of the proposed mechanism. Then I realized in Theorem 3.1 that at every sample, the non-zero noise variables are chosen randomly and it made sense (please correct me if I misunderstood anything). For a paper that proposes a new data generation model, the presentation should have been cleaner. - Theorem 3.2.. Given a large enough but finite number of samples, but not a sample complexity result. This is a rather weird statement. - Note: figure 2 has Möbius as the algo name. Perhaps it’s forgotten in the main text.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The limitations of this work are discussed very clearly in Section 6. I thank the authors for that paragraph.

Summary

This paper presents a new formulation of linear SEM by specifying a structure on the noise variables, which seems to impose zero-inflated distrbutions to achieve the "few roots" modelling goal. Identifiablity is given and guarantee for $L^0$ minimization estimator is provided for a special noise-free case. The minimization problem is further formulated into continuous optimization and numeric experiments are conducted.

Strengths

- The idea of the new formulation is interesting, based on the illustrative river pollution example. - The experiments consider many different setups, also including real datasets. The proposed algorithm shows comparable performance in the simulation study, though not by much.

Weaknesses

- The motivation of the proposed formulation needs more elaboration, see questions. And the current definitions of "few roots" and "negaligible noise" in (6) are not formal or clear. - Thm 3.2 only works for noise-free setting, thus there is no guarantee for consistency of $L^0$ minimization estimator for general model (4) beyond noise-free. - Neither the related work and experiments discuss or compare with constraint-based methods, even the basic PC algorithm. Is it becaus we lose Markov property and faithfulness in this new formulation?

Questions

- Thm 3.1 is proved by transforming the proposed model into a non-Gaussian DAG model. Just want to clarify: is the proposed formulation covered by the orginal DAG model? If so, are all other DAG learning approaches applicable? In that case, how do the authors justify the superiority of the new formulation beyond the empirical experiments? - In Figure 2(a) and (b), the SHD and SID for mobius are larger than others at the beginning but drop in the end, any explanation on that?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Lmitations are discussed in Section 6.

Thanks for response

My major concern has been mostly resolved. I believe that authors can make the setting more practically convincing in future revision. An additional suggestion is to add a dicussion regarding LiNGAM's performance, as the thoery part depends on LiNGAM's. From my point of view, it is even better to have a more through investigation, e.g., some extra experiments. I will increase my score accordingly.

Thanks for the rebuttal

Thanks to the authors for the rebuttal. The additional results have solved my concerns. I hope the authors could include the new results in the final version. I would like to raise my score to reflect the changes.