BayesDAG: Gradient-Based Posterior Inference for Causal Discovery

Summary

BayesDAG proposes a hybrid SG-MCMC sampling and variational inference for drawing samples from the posterior distribution of DAGs in the context of Bayesian structure learning. This work is closely related to a recently published "Yu et al., Dags with no curl, 2021" [NoCurl] where the space of DAGs is converted to the space of a skew-symmetric matrix, "W", and a potential vector,"p". The main difference is that [NoCurl] focuses on an optimization setting (to return a most probable DAG) while the focus of the current paper is on Bayesian inference (via sampling). They also mention that (for reasons that are not entirely clear to me) NoCurl approach optimization is challenging (due to uninformative gradients) and that this is due to the fact that the entries of the skew-symmetric matrix, W are continuous. To address this problem, they replace the continuous matrix W with a binary matrix. For this purpose, they slightly modify the theory presented in NoCurl (namely, replacing relu with step function). Then they reformulate the problem as a matrix permutation setting and finally propose an approximate solution for the latter formulation via Sinkhorn approach to learn latent permutations by the Gumble trick.

Strengths

1. This is a well-written paper addressing an important problem i.e. Bayesian structure learning. 2. The proposed approach is an interesting (albeit sophisticated) combination and modification of several algorithms and recent advances in the field. 3. Even though I did not follow why the continuous matrix W had to be replaced by a binary matrix in the first place, but I found the way they did it and managed to approximate its gradient, very interesting.

Weaknesses

1. As I mentioned in the summary section, a key contribution of this paper is the insight that it is better to replace the continuous matrix W (of NoCurl algorithm) with a binary matrix (see lines 101-104). But their justification for this claim does not seem convincing to me and should be explained better. To be more concrete: (a) Why should replacing a continuous matrix with a discrete matrix be helpful when we are relying on gradient information for optimization and sampling? (b) In line 100 they mention a "reported failure" of NoCurl. It would be great if the authors would provide a reference to where this failure is reported (Or if it is reported in the original NoCurl paper, the relevant section). 2. Given the close link of the present paper with the NoCurl approach, it would be great if the authors would compare their algorithm (with binary W) with an alternative approach where just like NoCurl, a continuous W would be used (and relu instead of step function, etc). 3. I see references to repositories that the authors have used but no link to their own code. Given that implementation of the proposed algorithm from scratch is by no means trivial, I encourage the authors to provide the code. Both for facilitating other researchers to use their algorithm as well as allowing the reviewers to check the reproducibility of the reported results.

Questions

Given that the Sinkhorn approach is approximate, how do you guarantee the DAGness of your graphs ?

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

3 good

Contribution

3 good

Limitations

N/A

Summary

The authors propose a method for the posterior inference of DAG structure *and* function parameters with potential applicability to arbitrary functional relations between nodes. The authors modify a novel characterization of DAGs, and interpret this characterization in terms of a sorting operation which can be relaxed to allow differentiability. The authors define priors on DAGs (in the alternative space) and function parameters and based on a specific model choice characterize likelihood. They use the resulting joint distribution to iteratively sample some parameters and conduct variational inference re. others. The authors examine the performance of their proposed methodology on various synthetic and real datasets.

Strengths

- The paper is very well written. It presents the previous work, motivation for current research, and reasoning behind methodological choices very clearly. - The paper utilizes recent, previous research intelligently and presents concrete innovations to solve well-defined problems. - Posterior inference in the DAG structure and parameter space without some of the limitations of previous work is valuable and is likely to inspire future work.

Weaknesses

- DAG model selection results have causal implications given specific model assumptions regarding generative model of the data. ANM is such a model assumption. However, it is unclear whether the identifiability results still apply in this case, given the priors defined on DAG structure and function parameters. I think the authors' work still would be valuable as only a DAG inference method; however, since the authors present their proposal as a causal discovery + inference method, this point needs further discussion. - I think the authors' presentation should be modified to make sure their inference method is more clearly understood. Given their initial presentation, including "posterior sampling" in the title, and frequent reference to Gibbs sampling throughout the text, leads the reader think that the authors will present results with a correct MCMC algorithm and produce a full posterior distribution. However, most promising results presented by authors include their iterative algorithm that samples from the posterior of some parameters and uses variational inference for others. This is fine as a methodological choice, but their presentation leads the reader to have higher expectations, which can become crucial depending on the use case of the reader. - Causal sufficiency assumption prevents using the current method in problems where unobserved confounding is likely. In my opinion this is acceptable given the difficulty of the problem.

Questions

- Are there any potential difficulties with using the authors' method with other SCM model assumptions / likelihoods? - What are grounds for baseline selection in experiments? I think this would be an important addition to the final text. - In 6.4, were there model misspecification in other methods as well?

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

I think the authors adequately address the limitations of their work overall, however see Weaknesses section above for some important caveats.

Summary

The paper proposes a Bayesian causal discovery method based on a novel parametrization of the binary DAG space and SG-MCMC. The proposed method does not rely on DAG regularization nor restricted to linear models, overcoming the limitations of prior approaches. Experimental results demonstrate the competitive performance of the proposed method compared to existing approaches.

Strengths

The paper is well-written and easy to understand. It is easy to follow the core idea of the proposed method. The proposed method is sound and well-motivated (i.e., there are apparent limitations of previous work but this method overcomes such issues.) Several techniques are employed smoothly to propose the method. Experimental results demonstrate the effectiveness and scalability of the proposed method.

Weaknesses

For the empirical evaluation, comparison with MCMC approach [1] is missing. Also, AUROC is not reported, which is widely used for the evaluation of uncertainty quantification in Bayesian causal discovery literature. The proposed method is claimed to be scalable and computational complexity is analyzed, but the actual computation cost (e.g., wall clock time) is not compared with DiBS. Computation resources they used are also not provided (e.g., CPU, GPU). Similarly, “per node degree 2” seems very limiting which results in a very sparse graph for large d. Large d will certainly affects the performance of likelihood computation and posterior sampling of W where more edges may demonstrate dependencies. [1] Improving markov chain monte carlo model search for data mining, 2003

Questions

Details of the weight-sharing mechanism (line 186) are missing. While the size of the networks is very small, how does it impact the performance of the proposed method other than reducing the total network parameters? Typo: (Line 230) focusonly

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.

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

3 good

Contribution

3 good

Limitations

Some of the assumptions can be viewed as limitations but I am fine with those (they are crucial to yields the proposed methods)

Summary

The paper proposes a novel Bayesian causal discovery (BCD) method that infer the posterior distribution $p(G|\mathcal{D})$ by projecting the DAG $G$ into an equivalent search space. Instead of sampling $G$, the method constructs the posterior distribution by sampling a binary matrix $W$ and potential vector $p$ with via MCMC sampling and variational inference. The Bayesian causal discovery method can scale up to 100 variables and achieves better accuracy on large datasets.

Strengths

- The idea of employing the projection framework from DAG-Nocurl paper is interesting. Especially, the difficulties of the sampling based posterior distribution estimation for DAG learning methods lie in the order of parents sampling. The potential function p automatically reserves the causal order. - The proposed method is a combination of sampling-based method and variational inference method. Compared to the state-of-art BCD methods that adopt VI, the proposed method achieves better SHD, especially on high-dimensional data.

Weaknesses

- (**Major**) The experiments are not comprehensive. There is a trade-off between efficiency and accuracy compared sampling-based approach to VI approach. Compared to the existing VI-based BCD methods, It is possible that the proposed approaches are more accurate but also suffer from low efficiency. Please refer to the question section for details. - (**Minor**) The tuning of hyperparameters such as scale of p and theta. Since the original framework of DAG-Nocurl is derived for continuous parameterization, the algorithm requires the tuning of additional hyperparameters, which increases the training difficulty. But I understand this is a minor concern.

Questions

My question focus on the experiment section: - It seems that the BayesDAG achieves better accuracy on cases $d>=70$. I wonder if authors can also show the efficiency (as in runtime) of different methods? I suspect that BayesDAG would take longer to converge than the VI-based approaches due to the Gibbs sampling procedure. The strength of BayesDAG is better demonstrated if it can achieve much better accuracy with a slight compromise on the efficiency. - Some synthetic data is generated based on the unidentifiable linear SEM with non-equal variances. How does the identifiability of the employed SEM affect the BayesDAG method (How does the non-equal variances assumption influence the Eq. (11))? - The paper only show the empirical results on $d\leq 100$ variables. I am wondering if authors can show BayesDAG can scale up to data with higher dimensions. The gradient-based causal discovery methods such as GraN-DAG can also scale up to 100 variables and finish within reasonable runtime with the help of GPU. - It would be better if the authors can compare to traditional scalable causal discovery methods such as FGES?

Rating

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

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

2 fair

Limitations

The idea of the paper seems interesting and the theory is sound. I concern that the Gibbs sampling procedure in the propose algorithm may compromise its efficiency and scalability.

Reviewer hANm: Have the authors addressed your concerns regarding the experiments?

Dear Reviewer hANm, The authors have replied to your concerns regarding the experiments and also added new results in their global reply's pdf. Could you please have a look and let us know if this changes your original assessment?

Reviewer zwvL: Have the authors addressed your concerns?

Dear Reviewer zwvL, Have the authors addressed the potential weaknesses raised in your review and your questions? Does their rebuttal change your assessment of the paper?

Reviewer R7H9: Continuous vs binary W and other issues

Dear Reviewer R7H9, Have the authors addressed these issues raised in your review and does this change your assessment of the paper?