Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: An EM-based method is described for doing causal discovery when some data entries are missing (MAR or MCAR). Different versions are proposed, which can deal with different variants of additive noise models. Experimental results show it tends to improve over imputation methods.
strengths_and_weaknesses: The problem is practically relevant and the theoretical analysis looks sound, though I did not check it closely. I think the clarity of the paper suffers somewhat from the large amount of material compared to the page limit.
questions: * What can you say about the running time of your method compared to other methods for the same task?

* The conclusion of appendix E (Convergence analysis) was unclear to me. Under what conditions is convergence guaranteed? Does this suffice to guarantee overall correct behaviour of the method (e.g. in the sense of finding the same graph as would be found without missingness, given enough data)?

Minor points:
* line 77: "include" -> "includes"; I recommend adding a comma before "and"
* line 78: "is no" -> "are no"
* line 80: "indicate" -> "indicates"
* line 83: 2nd formula about X should be about Y, and in {0,1}$^{N \times d}$
* line 106: "applys" -> "applies"
* line 115: "follow the fashion that": pick another word in place of "fashion" (then make the sentence grammatical)
* line 124: $\theta_{\mathcal{M}}$: is this a new notation?
* line 178: NL-ANM and LiNGAM are used without having been introduced, please mention the abbreviation when the work is cited earlier.
* line 231: "Completely Partial DAG" -> "Complete Partial DAG"
* line 278: I guess the "is" should be removed
limitations: -
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a method called MissDAG for learning causal structures in the presence of missing data. It assumes the data is missing at random (MAR) and the underlying causal model is an additive noise model (ANM). The paper derives expectation-maximization (EM)-based algorithms for maximizing a penalized log-likelihood score under different classes of ANMs including the linear non-Gaussian models, linear Gaussian models with equal noise variances, and nonlinear ANMs. The proposed MissDAG method is evaluated through synthetic and real data experiments.

strengths_and_weaknesses: The paper addresses an important problem of causal discovery in the presence of missing data. The existing work mostly focuses on structure discovery from discrete data while this work studies learning causal structures from incomplete data under ANMs. The proposed technical approaches are mostly standard techniques – its main contributions are deriving EM steps under different classes of ANMs. 

The experiments only compared with imputation methods as baselines, but not with existing work on causal discovery or Bayesian network (BN) structure learning from missing data, e.g. Structural EM [16], MVPC [60].  Why are MissDAG methods not empirically compared with existing works?

The writing is overall clear, but there are grammar issues here or there.

questions: Why are MissDAG methods not empirically compared with existing work on causal discovery or Bayesian network (BN) structure learning from missing data?

What are the sizes of the models (the number of variables $d$) in LiNGAM and NL-ANM experiments shown in Fig. (3)?

What is the running time of MissDAG vs. baselines in the experiments?

How well does MissDAG scale to larger models?

limitations: The paper did not discuss the limitations of the proposed approach. One limitation I see is that the proposed approach may be too slow to learn large models which I believe is a well-known issue in the EM-type of algorithms for learning BN structures from missing data. The largest models tested in the experiments contain 20 variables. How well does MissDAG scale to larger models?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The method proposed copes with the missing data problem in causal discovery by maximising the expected likelihood of the visible part of observations using the expectation-maximisation framework. 
strengths_and_weaknesses: Strengths. The paper is well written. The technical details are provided, and the results of numerical experiments are convincing. 

Weaknesses. The EM algorithm to treat missing data is quite a standard approach. Its extension to the current problem is rather straightforward. Difficult cases, such as latent common causes or cyclic graph are not considered.

A DAG is not necessarily a causal graph, as far as I know. Section 4 is focused on an extension of EM to DAGs. It seems that there is nothing specific for causal inference in this contribution. 

In Related Work: the papers cited are quite old. There is much recent work on missing data processing (but not necessarily for DAGs). 

questions: Questions. In Section 3, in notations,  X \in R^{N \times d} is repeated twice; the second should be Y? 

I found it not easy to follow Section 4.1.1. It is stated that "benefiting from the well-researched results of density transformation...": it might be well-researched but not extremely well known, and it is not easy to understand where equation 7 comes from. 

I am not sure that the notation in equation 8, where X comes twice (on the left and on the right) is successful. 

The explanation what "SHD" stands for comes a little bit late in the text.  

limitations: I guess that the method is not scalable (since it relies on the EM).
From the causal viewpoint: it is assumed that there is not any latent confounders and there are no cycles in the graph.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of causal discovery when parts of the observation matrix are missing. The proposed method called “MissDAG” is an EM-like procedure: the E-step estimates the expected data log-likelihood as a function of the unknown causal graph and parameters by marginalizing out/sampling the missing values given the graph and parameters estimated in the previous step; the M-step then maximizes this expected data log-likelihood function with respect to the unknown causal graph and parameters. In an empirical evaluation, the work shows that MissDAG results in better graph recovery in terms of SHD/F1 scores than using other imputation methods.
strengths_and_weaknesses: The motivation of the paper and the introduction are convincing. It makes sense to use EM to account for missing values in this context, and it has been done by previous work (e.g. [15, 54]). The array of imputation baselines and considered settings are likewise comprehensive and show the efficacy of MissDAG in the context of causal discovery. Since we are interested in the _causal_ graph, it would make sense to also show metrics like the structural intervention distance (SID), which is closer to our interests in causal inference.

While the overall presentation structure of the paper is fine, the presentation of the various subparts and subsettings in the methods section (Section 4) is quite convoluted, making it hard to parse the key challenges and their proposed solutions. I think the exposition could be improved by first introducing the E-step and M-step and their different levels of difficulty (exact vs. approximate posteriors) without reference to a specific generative model yet (such as LGM, LiNGAM, NL-ANM). Then, to separate the MissDAG algorithm from the specific generative model assumptions, specific instantiations of these steps could be presented in an additional Section 5 that gives certain closed forms, as for instance in the linear Gaussian case.

Further points/questions about the presentation:
- Figure 3: “$\Sigma$ (sufficient statistic) can be a criterion for distribution recovery.” What is your justification for that? In this paper, the goal is causal structure learning and not (observational) distribution recovery, so the work should give some motivation to show this figure and metric. 
- Line 46: “the consistent approach”. What is the consistent approach that is meant here? This is related to the previous point about Figure 1, which is referenced in this sentence.
- Figure 6(b): What is a “history”? This is never explained anywhere.
- In line 56, you mention the concept of “ignorability” when stating your main contribution, even though this concept was never introduced at this point of the manuscript. It would be good if a sentence earlier in the introduction explains this notion and why it is needed.
- I do not understand the point of introducing Eq. (2) and/or $\phi$, since it is never used in the later sections of the paper. Can you provide some motivation? Also, why is “ignorable missingness” (Assumption 1, line 95) important? This is not motivated explicitly and never picked up again later in the manuscript, and unless the reader is very familiar with this literature already, it may be difficult to relate to the other parts of the paper.
- Line 124: What is “$\theta_\mathcal{M}$”? This notation is not used anywhere else.
- Line 128: What do you mean by imputing “the missing entries by the functions of $X_M$”? Do you mean the distributions of $X_M$?
- Line 168-169: “we also plug in the DAG constraint as an inductive bias for optimization.” The DAG constraint is hardly an inductive bias, more a hard constraint (line 74), which usually makes the structure learning problem harder to solve and not easier. Please consider rephrasing.
- Line 189-190: “… the exact formulation of each noise distribution is agnostic.” What is meant by this? This is most likely a wrong usage of the word “agnostic”.
- Line 205-206: This is imprecise. You should indicate that $x^j_{im}$ are samples from the posterior $p(\mathbf{X}_{m} | X_o, \theta^t)$.
- Lines 299-300: “Different from the BN learning methods, our method is specifically designed for causal discovery, where identifiability of the underlying causal graph is critical.”
I do not agree with this statement. There is no inherent difference between causal discovery algorithms from observational data using a score- or constraint-based approach and algorithms for learning a BN. For certain classes of BNs (such as the ANM ones studied in this work), the true causal structure achieves highest likelihood, which is why these models are deemed “identifiable” from observational data. In fact, NOTEARS itself is a method for BN structure learning and used pervasively in this work as a causal discovery algorithm.

Typos and minor suggestions:
- Abstract (lines 6-7): “… a two-step method may suffer from suboptimality, as the imputation algorithm is unaware of the causal discovery step.”
This sentence is vague, especially since MissDAG is not “aware” of the causal discovery step either: MissDAG uses an estimated causal model to approximate the expected data log-likelihood. What does it mean to be “aware” of the causal discovery step? Formulations about efficiency and/or bias as in lines 42-45 would be more convincing.
- Line 21: “concerned variables” -> consider rephrasing as, e.g. “variables of interest”
- Line 83: typo, the second $\mathbf{X}$ should be a $\mathbf{Y}$
- Line 87: typo, I believe “observed portions” should be “observed positions”
- Line 118: “a graph learning part $\theta_\mathcal{G}$”. It appears as though this is the causal graph. If so, it may be clearer to use $\mathcal{G}$ as the notation (similar to line 75 or 171), since the causal graph is usually considered to be separate from the parameters or functions parameterizing an SCM.
- Line 119: “While in …, … .“ This sentence is grammatically incorrect.
- Line 125: “which relates the estimation … to the same parameters estimation”. This sentence is grammatically incorrect. 
- In my opinion, the related work section would work better as Section 3. Otherwise, it is not transparent from the beginning what the gap in the state of the art is that MissDAG sets out to fill, especially since EM-like approaches have previously been used for BN structure learning.


questions: Method:

A main question arising in Section 4 concerns the likelihood term $p(\mathbf{X} | \theta)$ (Section 4.1.1). Throughout the paper, we assume that the SCMs considered are *acyclic* (line 74 and 79). Thus, irrespective of the functional form and the noise distribution, the likelihood factorizes into a product of local conditionals $p_j(x_j | pa_j)$ (the Markov kernels). As a result, the likelihood is always trivial to evaluate conditional on the causal graph and parameters, especially for the additive noise models considered in this work.

Hence, I do not understand why this work introduces the complicated generalization in Eqs. (7)-(8) involving determinants and the Jacobian. This general form was used by [32] to handle *cyclic* SCMs, in which the likelihood is not trivially computable in the above, recursive form. However, the cyclic setting is not studied in this work. 

Later in the manuscript (Proposition 1, line 216), the authors even note that for a DAG, this additional term is 1 and can thus be dropped from Eqs. (7)-(8), which reduces the likelihood computation to the simple factorized computation always used in BN structure learning (This is even explicitly spelled out in lines 217-218). Unless I missed something essential about MissDAG and the incomplete data setting, this unnecessary complication in the likelihood somewhat indicates of a lack of familiarity with related work and the task of causal structure learning more generally. The whole of Section 4 could be significantly simplified and thus made more accessible when this is dropped.

Related to the above, I do not see why Eq. (10) needs to be so complicated. The likelihood in the linear Gaussian is trivial to evaluate and simply a product of Gaussian distributions with densities that are tractable to compute, without needing to introduce $\mathbf{T}$. It would also be straightforward to add a bias term to the linear Gaussian model instead of using the structural equation model notation in Eq (9), where each causal variable has zero mean.

Related work:

Please clarify the precise relationship to and contribution over the prior works [15] and [54]. It appears that their algorithms conceptually do the same EM procedure as MissDAG, except that MissDAG substitutes in more modern likelihood model assumptions and structure learning methods into the subcomponents of the algorithm. For instance, [54] states: “[Our algorithm] uses the current estimate of the structure and the incomplete data to refine the conditional probabilities, then imputes new values for missing data points by sampling from the new estimate of the conditional probabilities, and then refines the network structure from the new estimate of the data using standard algorithms for learning Bayesian networks from complete data.”

limitations: Overall, the paper presents an intuitive idea based on EM for the causal discovery problem from incomplete data, which is validated convincingly in experiments on simulated data but is not new in the literature [15, 54]. In addition, given the points brought up above, the presentation and derivation have room for improvement both in terms of writing and in terms of clarity and motivation of the mathematical derivations, which sometimes indicates a lack of familiarity with existing approaches to the problem (in particular, the point on computing the likelihood). This makes an otherwise clear and intuitive method, which appears to be effective empirically, very hard to parse and internalize. Since the idea and results are convincing overall, I am open to revising my scores if the issues raised have been addressed.
review_title: null

Meta-review: metareview: 
All reviewers were convinced by the scientific value and results about this paper and voted for acceptance. 
The authors did a good job addressing thoroughly the various concerned raised. 
As a result, two of the reviewers happily increased their score. 
A common concern remaining is the dense writing. The reviewers underlined the need 
for the authors to improve the clarity and presentation. Acceptance is recommended.
confidence: Certain
Decision: Accept