Approximate Counting of Graphical Models Via MCMC Revisited
This work provides incremental improvements in counting graphical models, relevant for researchers in probabilistic graphical models and structure learning.
The paper extends prior MCMC sampling work by increasing the node count from 20 to 31 and computing additional approximate ratios for graphical models, including proving that the ratio of connected DAGs to DAGs asymptotically approaches 1.
In Peña (2007), MCMC sampling is applied to approximately calculate the ratio of essential graphs (EGs) to directed acyclic graphs (DAGs) for up to 20 nodes. In the present paper, we extend that work from 20 to 31 nodes. We also extend that work by computing the approximate ratio of connected EGs to connected DAGs, of connected EGs to EGs, and of connected DAGs to DAGs. Furthermore, we prove that the latter ratio is asymptotically 1. We also discuss the implications of these results for learning DAGs from data.