Learning Inclusion-Optimal Chordal Graphs
This work addresses a specific problem in probabilistic modeling for researchers in graph theory and machine learning, but it appears incremental as it builds on existing methods for chordal graph learning.
The paper tackles the problem of learning chordal graph structures from data, presenting a greedy hill-climbing algorithm that is proven to find inclusion-optimal structures under certain conditions, with evaluation on simulated datasets.
Chordal graphs can be used to encode dependency models that are representable by both directed acyclic and undirected graphs. This paper discusses a very simple and efficient algorithm to learn the chordal structure of a probabilistic model from data. The algorithm is a greedy hill-climbing search algorithm that uses the inclusion boundary neighborhood over chordal graphs. In the limit of a large sample size and under appropriate hypotheses on the scoring criterion, we prove that the algorithm will find a structure that is inclusion-optimal when the dependency model of the data-generating distribution can be represented exactly by an undirected graph. The algorithm is evaluated on simulated datasets.