Adaptive Bayesian Structure Learning of DAGs With Non-conjugate Prior

Technical Summary: Adaptive Bayesian Structure Learning of DAGs With Non-conjugate Prior

Problem Statement
The paper addresses the challenge of learning the structure of Directed Acyclic Graphs (DAGs) within a Bayesian framework, specifically for Gaussian DAG models. While DAGs are powerful tools for representing conditional independencies and causal relationships, determining the optimal graph structure is computationally intensive and statistically uncertain. Traditional Bayesian approaches often rely on conjugate priors, such as the Normal-Inverse-Gamma (NIG) distribution, to facilitate analytical tractability. However, the authors argue that these conjugate priors may not always yield the highest posterior probability or the most accurate structural learning, particularly regarding the inclusion of nodes and edges in the generating model. The primary goal is to develop a method that enhances posterior probability and computational efficiency while maintaining adaptability in structure learning.

Methodology
The authors propose a novel Bayesian structure learning approach utilizing a non-conjugate Normal-Gamma (NG) prior for the parameters of Gaussian DAGs.

1. Model Formulation:

   • The joint distribution of variables is modeled as a zero-mean Gaussian DAG, re-parameterized via a modified Cholesky decomposition ($\Omega = L D^{-1} L^T$).
   • The parameters consist of the diagonal elements $D_{jj}$ (conditional variances) and the lower triangular coefficients $L_{\prec j]}$ (regression coefficients).
   • Unlike the standard NIG approach where $D_{jj}$ follows an Inverse-Gamma distribution, the proposed method assigns $D_{jj}$ a Gamma distribution ($\Gamma$), while maintaining a Normal distribution for $L_{\prec j]}$ conditional on $D_{jj}$.

2. Theoretical Derivation:

   • The authors derive the marginal likelihood and the joint posterior density functions for the node parameters under this non-conjugate prior.
   • A key theoretical result involves the appearance of the Bessel function of the third kind ($K_\nu$) in the posterior and marginal density expressions. This mathematical property allows for the computation of posterior probabilities without the analytical simplifications typically afforded by conjugacy.

3. MCMC Algorithm:

   • To perform posterior inference, a Markov Chain Monte Carlo (MCMC) scheme is developed.
   • The algorithm explores the space of DAGs ($S_q$) using local operators: inserting, deleting, and reversing directed edges, ensuring the resulting graph remains acyclic.
   • The acceptance probability for transitioning between DAGs is calculated using the derived marginal likelihoods (Theorem 1) and the prior probability of edge inclusion.
   • The full conditional distributions for the parameters are sampled at each iteration to update the graph structure and parameters simultaneously.

Key Contributions

• Non-Conjugate Prior Implementation: The paper introduces the use of a Normal-Gamma prior for Gaussian DAGs, moving away from the standard Normal-Inverse-Gamma conjugate framework.
• Computational Efficiency via Bessel Functions: Contrary to the intuition that non-conjugate priors increase computational burden, the authors demonstrate that utilizing the Bessel function in the posterior calculation results in faster MCMC computation compared to the conjugate NIG model.
• Adaptive Sparsity: The proposed method exhibits "cautious" or conservative behavior regarding edge inclusion. It tends to include edges only when the inclusion probability is high, leading to sparser DAGs when the prior probability of edge inclusion is low.
• Enhanced Posterior Probability: The study claims that the proposed NG prior yields a higher posterior probability for the Maximum A Posteriori (MAP) DAG compared to the NIG prior.

Results
The methodology was evaluated through simulation studies and a real-world application:

1. Simulation Studies:

   • Performance Metrics: The NG model was compared against the NIG model across various sample sizes ($n=200, 300$) and node counts ($q=40, 50$).
   • Accuracy: The NG model demonstrated superior performance in Specificity (SP), False Negative Rate (FNR), Misspecification Rate (MISR), and Accuracy (AC).
   • Sensitivity Trade-off: The NG model showed lower Sensitivity (SE) and F1-scores compared to NIG. The authors attribute this to the model's conservative nature; with a low prior probability of edge inclusion, the NG model produces fewer true positives, resulting in lower sensitivity but higher specificity.
   • Computational Time: The computational time per iteration for the NG model was generally lower than that of the NIG model, even as the number of variables and sample size increased. The inclusion of the Bessel function did not introduce significant computational delays.

2. AML Data Analysis:

   • The method was applied to a dataset of Acute Myeloid Leukemia (AML) patients ($n=68$, $q=18$ proteins).
   • Convergence: Trace plots indicated good MCMC mixing and convergence.
   • Posterior Probability: The posterior probability of the MAP DAG estimated by the NG model was 0.769, significantly higher than the 0.0016 obtained by the NIG model.
   • Structural Estimates: Both the Median Probability Model (MPM) and MAP estimates were generated, showing consistent structural learning capabilities.

Significance and Claims
The paper claims that the proposed adaptive Bayesian structure learning approach offers a robust alternative to traditional conjugate priors. By employing a non-conjugate Normal-Gamma prior, the method achieves:

• Higher Posterior Probability: The resulting MAP DAG has a substantially higher posterior probability, suggesting a better fit to the data-generating process.
• Computational Advantage: Despite the theoretical complexity of non-conjugacy, the method is computationally faster than the conjugate NIG approach.
• Adaptability: The model adapts to the true structure by being conservative in edge inclusion, effectively filtering out spurious relationships when the prior suggests low edge density.

The authors conclude that this technique has potential applications in causal discovery and estimation, providing a more accurate and efficient tool for uncovering variable dependencies in multivariate scenarios.