Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a fully differentiable (i.e., continuous-space) method for Bayesian learning of Bayesian network structures as well as parameters. The proposed method (DiBS) is compared against several existing state-of-the-art methods on simulated and real data sets, and the results demonstrate very competitive performance.
main_review: This paper proposes a fully differentiable (i.e., continuous-space) method for Bayesian learning of Bayesian network structures as well as parameters. Authors propose a seemingly simple generative model (Fig. 1): a generative graph model is motivated by variational graph autoencoders and utilizes recent results on continuous characterization of acyclic graphs that are incorporated as priors in the generative model. Model inference is implemented with the Stein variational gradient descent, with the necessary technical terms being derived in the manuscript/appendix. The proposed method (DiBS) is compared against several existing state-of-the-art methods on simulated and real data sets, and the results demonstrate very competitive performance.

The manuscript is very clear and easy to read. To the best of my knowledge, this manuscript proposes a novel technique for structure/parameter learning for BNs that goes beyond the previous methods; it could even be fair to say that perhaps this manuscript opens a new direction for Bayesian learning for BN structure/parameters and for causal inference in general. Having worked on the BN learning in the past, I must say that I read the manuscript with great interest.  I have no real concerns about this work: all technical details seem correct, and simulations and results support the claims made in the manuscript.  I list some comments/suggestions and minor comments below that the authors can implement when revising their manuscript. 

1. Overall the literature review appears to be very comprehensive. While it is true that most of the MCMC techniques for BN structure inference assume a closed form for the marginal likelihood (which makes it easy to implement e.g. Metropolis-Hasting algorithm over structures), previous methods also include reversible jump MCMC methods for inferring both the structure and parameters (proposed at least in the context of dynamics BNs). 

2. Although Fig. 2 does not contain the most impressive results, I found it very convincing that the proposed method performs comparably with (or in terms of neg. (I-)MLL measures even slightly better than) the MC^3 for linear Gaussian BNs. 

3. Page 7, row 268: why did you use so few samples (S=30)?

4. Appendix D.5, results for d=50: can you discuss about possible reasons why the method performs worse for the case where closed form for the MLL is available? 

5. Sec. 7, phosphoproteomics data analysis: I would recommend authors to consider using neg. log.likel. measures on hold-out data in addition to comparing against the "ground truth network structure", as the ground truth may not be entirely correct (e.g. missing links). 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the structure learning problem, in which the goal is to find a directed graphical model (structure and parameters) that accurately models an observed dataset. The authors work in the Bayesian structure learning paradigm, defining a prior distribution over graphical models and aiming to infer a posterior. Rather than defining a discrete prior over the unknown graph structure $G$, the authors define a prior over a continuous latent variable $Z$, and a conditional distribution on $G$ given $Z$, such that the data likelihood, $P(D \mid Z) = E_{G \mid Z}(P(D \mid G))$, is differentiable with respect to $Z$. This enables gradient-based inference methods to be applied to the problem of inferring $Z$, marginalizing $G$—if the necessary gradients can be efficiently estimated. In principle, any gradient-based inference method could be applied, but the authors spell out details of a Stein Variational Gradient Descent procedure. This proposed technique, and a variant in which an additional reweighting step is applied, are evaluated on synthetic data, against MCMC-based and non-parametric bootstrapping baselines.
main_review: This paper presents a novel approach to the important but difficult problem of Bayesian structure learning. Bayesian approaches to the problem are conceptually appealing (define a prior over graphs, and the obvious data likelihood), but hard to implement in practice, because they involve combinatorial search over a high-dimensional discrete space. This paper applies recent advances in differentiable characterizations of graph "acyclicness" to formulate a structure learning model to which (some) gradient-based inference methods can be applied.

Although various components of this approach have been previously proposed (e.g., structure learning as continuous optimization, and "inner product" priors for edge probabilities in graphs), this work presents a valuable synthesis of these ideas into a coherent model and inference algorithm for Bayesian structure learning. The empirical validation is thorough, and I appreciated the variety of different metrics used to evaluate performance.

One aspect I found unsatisfying was the move from DiBS to DiBS+. The unweighted particle collection is already meant to represent the posterior; wouldn't weighting it by the unnormalized target "double-count," further concentrating the inferred posterior? That this performs better than DiBS using the metrics investigated here suggests either that something is off about the metrics (i.e., they do not reward proper uncertainty?), or that the inference algorithm is under-confident / producing higher-uncertainty estimates than it should. Or am I misunderstanding something? One question for the authors is whether you have tried applying a similar re-weighting to samples from the MC^3 baselines you consider (weighting according to the posterior densities they target).

Other minor questions:

* In the BGe marginal likelihood, is the likelihood 0 for graphs G with cycles?
* Maybe I missed it, but could you report -log p(D^{test} | G*, Theta*) for the true data-generating graph? This may help calibrate the negative log likelihood numbers you report.
* In Section 7, where does "the consensus network" come from?
limitations_and_societal_impact: Broader impact is explicitly discussed (with a focus on the potential positives), but I don't see an explicit discussion of limitations. Some questions that might be worth considering:

* Is it really the case that other black-box inference methods would be easy to apply to your examples (L332)? For example, I don't believe Hamiltonian Monte Carlo can easily make use of the gradient estimators you give in Section 4.3.

* The score function estimator (Eq 14) is often described as having unacceptably high variance. You appear to have used it successfully in Section 6.2, but do you expect it will scale to e.g. models with parameters $\Theta$ that can't be analytically marginalized, or to higher-dimensional data?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a new approach to posterior approximation in the context of structure learning based on the Stein Variational Gradient Descent (SVGD) procedure and the differentiable acyclicity constraint inspired from Zheng et al 2018. A continuous latent variable Z (parent of G only) is introduced in the model to allow the computation of the gradient of its posterior (with respect to Z) which in turn enables one to use SVGD to sample from P(G|D). This gradient can be estimated using the Gumbel-softmax trick or score function estimator. The framework is validated on synthetic data as well as the protein signaling dataset from Sachs et al..
main_review: Originality:

The method proposed is original, however, I believe two papers strongly related to this work have been omitted, namely, “Masked Gradient-Based Causal Structure Learning” by Ng et al. and “Differentiable Causal Discovery from Interventional Data” by Brouillard et al.. Both works leverage the Gumbel-softmax trick to learn an adjacency matrix (like this work), although without framing their approach as Bayesian (thus without learning a posterior distribution over graphs). The latter work frames its continuous constrained optimization problem as a stochastic relaxation of the original discrete combinatorial problem. Given the strong resemblance (when using a single particle), I believe it is important that the paper contrasts these approaches with theirs. An empirical comparison (with the single particle version) would also be interesting.

Quality:

The method proposed is well motivated and technically sound. I have not reviewed the proofs however. This is an interesting direction and I believe this a good paper. However, there are some things I would like the authors to clarify/adjust, mainly regarding experiments. I am open to revise my score once the following concerns are addressed:

L219: Could you provide some motivation for this “weighted particle mixture” modification? Does SVGD allow for this kind of modification or is it a contribution from the authors? This is especially important since it appears to be performing better in some cases.

I am under the impression that the metrics reported will favor methods which underestimate the uncertainty in the posteriors. For instance, if the samples from the approximate posterior (wrongfully) concentrate around the MAP estimator, E-SHD will be potentially lower than it would have been if the samples were coming from the actual posterior. I am not well-versed in Bayesian model selection so I don’t know what are the typical ways to evaluate the quality of the posterior, but I suspect it needs to somehow take into account proper uncertainty quantification. This aspect is studied in Appendix E.4 for a very special case of a graph with 4 nodes, allowing to compute the exact posterior and compare it with the one approximated by DiBS. I noticed that the number of SVGD iterations in this study is much smaller than in the experiment presented in the main paper (500 against 3000). I would like to see how the numbers from Table 4 change if one makes 3000 SVGD iterations. Does the uncertainty estimation remain the same? Given the importance that this work puts on being able to estimate p(G|D), I believe it would be important to make this kind of analysis on more graphs and more methods to see how DiBS compare. These experiments should also appear in the main text given their importance.

L268: Is 30 samples from the posterior enough to estimate the various performance metrics? It would be interesting to see how much the metrics vary when one repeats the sampling. Do the performance metrics change a lot when using more samples from the posterior?

Clarity:

The paper is well written and I enjoyed reading it. Here are a few things that might still be clarified:

In Section 4.3, titled “Black box bayesian inference”, I was not sure what the actual algorithm suggested was. I believe the title is a bit misleading since no specific inference procedure is suggested in this section. The first paragraph of the following section also implicitly mentions that some inference procedure was suggested above: “... translates learning discrete graph structures into an inference problem over the continuous variable Z.” As an outsider to the Bayesian approach, the only inference procedure I thought of after reading only 4.3 is *maximum a posteriori estimation* via gradient ascent. Later reading the paragraph at line 212 confirmed my guess. Please clarify.

Equation (15) felt a bit hard to interpret given that no explanation of the stein variational gradient descent was provided. Maybe adding some general explanation of this method in the background section would help, or maybe just refer to Algorithm 1 at the very beginning of Section 5.

Minor:

Equation (8): Why using E_{G | Z}[h(G)] instead of h(G_\alpha(Z)) ? After all, h was designed to take as input weighted adjacency matrices. 

Equation (17) if <u_i, v_j> = 0, the limit is ½ right? Probably not relevant since this concerns a set of measure zero. 

For each method, which thresholds were explored to compute the AUROC, and how were they selected? Also regarding the AUROC, how is p(g_ij = 1 | D) estimated? I assume by counting the proportion of graphs with g_ij = 1 among the 30 samples from the posterior? 

Confused by ijk in equation (8), I thought Z was a k x 2d matrix (line 129) 

How is E-SHD estimated? I am guessing via Monte Carlo estimation using the samples from the posterior. To clarify.

Significance:

I believe proper quantification of uncertainty in structure learning is important and this work makes an interesting contribution in that direction by using recent developments in continuous optimization for structure learning. This work has potential for impact.




limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a method called DiBS (differentiable Bayesian structure learning) for learning the structure of a Bayesian network (BN) from data based on a fully differentiable reparameterization of the relevant likelihood expressions, allowing for the use of continuous optimization-based Bayesian inference algorithms. This method allows for posterior inference of graph structure alone, or joint inference over structure and conditional distribution parameters. First, they augment the standard generative model of data from a Bayesian network with a continuous-valued latent variable of node embeddings such that the probability of each edge in the graph adjacency matrix can be modeled by the inner product similarity of node embeddings with a temperature parameter. The authors use a previously-introduced function of the adjacency matrix that calculates graph cyclicity to include a prior that encourages acyclic structure. They derive expressions that reformulate the necessary score functions in terms of gradients with respect to the new continuous latent graph representation, using the Gumbel-softmax trick to reparameterize the gradient where applicable and the score function gradient estimator otherwise. The method uses Stein variational gradient descent as the inference algorithm, optimizing a set of particles for the latent graph representation while annealing the temperature parameters to result in a final set of particles that correspond to adjacency matrices of valid directed acyclic graphs. A variant of the base method called DiBS+ that weights each particle by its unnormalized posterior probability is also explored. On synthetic data from linear Gaussian BNs, DiBS and DiBS+ show comparable performance to greedy search-based (BPC, BGES) and sampling-based ($\text{MC}^3$) algorithms across a variety of metrics when inferring structure alone, and comparable or better performance when jointly inferring structure and parameters. On synthetic data with nonlinear local conditionals parameterized by a neural network, DiBS/DiBS+ perform comparably to or better than sampling-based methods for joint inference across metrics. These results are also reflected on real data from a protein signaling network, where DiBS/DiBS+ achieve the best recovery of the true network and the most well-calibrated edge confidence scores in the joint inference setting.
main_review: This paper presents a very interesting approach for joint Bayesian inference of structure and parameters of graphical models using continuous optimization-based methods, with the overall presentation of the method being clear with sufficient detail. While the performance of DiBS is comparable to other methods for marginal posterior inference in the linear Gaussian setting, it still provides a competitive alternative to existing approaches. DiBS seems to particularly excel when applied to joint inference of structure and parameters, especially with nonlinear conditionals, which is relevant for a lot of real-world applications and presents this method as a potentially valuable tool for practitioners interested in this kind of inference for their data. Given that DiBS is also agnostic to the particular inference algorithm used (as the authors mention in their Conclusion), any advancements in Bayesian inference algorithms that require a differentiable likelihood could be applied to improve upon this framework. Overall, I believe this is a strong paper and recommend it for acceptance.
limitations_and_societal_impact: The authors briefly discuss the potential negative impacts, specifically the risk in taking a causal interpretation of the results of this method applied to real data without considering the necessary assumptions.
review_title: null

Meta-review: Reviewers agree that the proposed use of continuous embeddings for Bayesian learning of directed graphical models is innovative and potentially high-impact.  Reviews generally have very positive comments about the manuscript's clear presentation and promising experimental results.  In future revisions, please do better discuss the motivations for the "DiBS+" variant, and clarify the points about technical details and evaluation metrics that were discussed with reviewers.
Decision: Accept (Spotlight)