AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms

Overview

In this work:

• We address the problem of finding a minimal separator in an AMP (Andersson, Madigan, and Perlman) Chain Graphs (CG), namely, finding a set Z of nodes that separates a given non-adjacent pair of nodes such that no proper subset of Z separates that pair.
• This paper offers polynomial time algorithms for learning AMP CGs. These include finding a minimal separator from a restricted set of nodes, finding a minimal separator for two given disjoint sets, and testing whether a given separator is minimal.
• To address the problem of learning the structure of AMP CGs from data, we show that the PC-like algorithm (Pena, 2012) is order-dependent, in the sense that the output can depend on the order in which the variables are given.
• We propose several modifications of the PC-like algorithm that remove part or all of this order-dependence.
• We also extend the decomposition-based approach for learning Bayesian networks (BNs) proposed by Xie, Geng, and Zhao (2006) to learn AMP CGs, which include BNs as a special case, under the faithfulness assumption.
• We prove the correctness of our extension using the minimal separator results.
• Using standard benchmarks and synthetically generated models and data in our experiments demonstrate the competitive performance of our decomposition-based method, called LCD-AMP, in comparison with the (modified versions of) PC-like algorithm.
• The LCD-AMP algorithm usually outperforms the PC-like algorithm, and our modifications of the PC-like algorithm learn structures that are more similar to the underlying ground truth graphs than the original PC-like algorithm, especially in high-dimensional settings.
• We empirically show that the results of both algorithms are more accurate and stabler when the sample size is reasonably large and the underlying graph is sparse.

Paper

Mohammad Ali Javidian, Marco Valtorta, and Pooyan Jamshidi. AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms To appear in Journal of Artificial Intelligence Research (JAIR).

Code

https://github.com/majavid/AMPCGs2019

Potential Extensions

1. Designing a hybrid algorithm for learning AMP chain graphs that exploits minimal separators directly.
2. Develop a learning algorithm that relaxes the faithfulness assumption.
3. Characterizing Markov blankets in AMP CGs and designing a Markov blanket-based algorithm for learning AMP CGs.

Acknowledgement

This work has been supported by

• AFRL and DARPA (FA8750-16-2-0042),
• ASPIRE grant from the Office of the Vice President for Research at the University of South Carolina.