  We address the problem of finding a minimal separator in an
Andersson-Madigan-Perlman chain graph (AMP CG), namely, finding a set Z of
nodes that separates a given nonadjacent pair of nodes such that no proper
subset of Z separates that pair. We analyze several versions of this problem
and offer polynomial-time algorithms for each. 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 et al., 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. In particular, 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.
