Download this article
 Download this article For screen
For printing
Recent Issues
Volume 15, Issue 1
Volume 14, Issue 2
Volume 14, Issue 1
Volume 13, Issue 1
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 2
Volume 11, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
 
Subscriptions
 
ISSN (electronic): 2693-3004
ISSN (print): 2693-2997
Author Index
To Appear
 
Other MSP Journals
Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks

Danai Deligeorgaki, Alex Markham, Pratik Misra and Liam Solus

Vol. 14 (2023), No. 2, 233–286
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.

Keywords
marginal independence, unconditional equivalence, Bayesian networks, causality, toric ideals, Gröbner bases, Markov chain Monte Carlo, intersection number, independence number, minimal covers
Mathematical Subject Classification
Primary: 62R01
Secondary: 13F65, 60J22, 62D20, 62H22
Milestones
Received: 30 September 2022
Revised: 12 January 2024
Accepted: 15 January 2024
Published: 16 May 2024
Authors
Danai Deligeorgaki
Department of Mathematics
KTH Royal Institute of Technology
Stockholm
Sweden
Alex Markham
Department of Mathematics
KTH Royal Institute of Technology
Stockholm
Sweden
Pratik Misra
Department of Mathematics
KTH Royal Institute of Technology
Stockholm
Sweden
Liam Solus
Department of Mathematics
KTH Royal Institute of Technology
Stockholm
Sweden