An Improved Lower Bound on Identifying Compelled Edges in a DAG

D. Wu (Canada)


Bayesian networks, compelled edges, equivalence class of Bayesian networks, algorithmic model


Identifying compelled edges in a DAG is an important task in learning Bayesian networks from observed data. Tra ditionally, a graphical algorithm was used to examine each edge in a DAG to determine if it is a compelled edge. In this paper, we introduce a new algorithmic model that is based on the algebraical characterization of equivalence classes of DAGs. This new algorithmic model provides an im proved lower bound for the worst case time complexity of identifying compelled edges.

Important Links:

Go Back