  Bayesian causal discovery aims to infer the posterior distribution over
causal models from observed data, quantifying epistemic uncertainty and
benefiting downstream tasks. However, computational challenges arise due to
joint inference over combinatorial space of Directed Acyclic Graphs (DAGs) and
nonlinear functions. Despite recent progress towards efficient posterior
inference over DAGs, existing methods are either limited to variational
inference on node permutation matrices for linear causal models, leading to
compromised inference accuracy, or continuous relaxation of adjacency matrices
constrained by a DAG regularizer, which cannot ensure resulting graphs are
DAGs. In this work, we introduce a scalable Bayesian causal discovery framework
based on a combination of stochastic gradient Markov Chain Monte Carlo
(SG-MCMC) and Variational Inference (VI) that overcomes these limitations. Our
approach directly samples DAGs from the posterior without requiring any DAG
regularization, simultaneously draws function parameter samples and is
applicable to both linear and nonlinear causal models. To enable our approach,
we derive a novel equivalence to the permutation-based DAG learning, which
opens up possibilities of using any relaxed gradient estimator defined over
permutations. To our knowledge, this is the first framework applying
gradient-based MCMC sampling for causal discovery. Empirical evaluation on
synthetic and real-world datasets demonstrate our approach's effectiveness
compared to state-of-the-art baselines.
