Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks

Abstract

We consider the problem of estimating the marginal independence structure of a Bayesian network from observational data, learning an undirected graph we call the unconditional dependence graph. We show that unconditional dependence graphs of Bayesian networks correspond to the graphs having equal independence and intersection numbers. Using this observation, a Gröbner basis for a toric ideal associated to unconditional dependence graphs of Bayesian networks is given and then extended by additional binomial relations to connect the space of all such graphs. An MCMC method, called GrUES (Gröbner-based Unconditional Equivalence Search), is implemented based on the resulting moves and applied to synthetic Gaussian data. GrUES recovers the true marginal independence structure via a penalized maximum likelihood or MAP estimate at a higher rate than simple independence tests while also yielding an estimate of the posterior, for which the $20\%$ HPD credible sets include the true structure at a high rate for data-generating graphs with density at least $0.5$.

54 pages, 13 figures, 3 tables

References in corpus (5)

• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
• Representation Theory of the Symmetric Group in Voting Theory and Game Theory
• Directed Gaussian graphical models with toric vanishing ideals
• Marginal Independence Models