# AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms

Journal of Artificial Intelligence Research (JAIR 2020)

## 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

- Designing a hybrid algorithm for learning AMP chain graphs that exploits minimal separators directly.
- Develop a learning algorithm that relaxes the faithfulness assumption.
- 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.