Towards standard imset for maximal ancestral graphs
Imsets, introduced by Studenỳ (see Studenỳ, 2005 for details), are an algebraic method for representing conditional independence models. They have many attractive properties when applied to such models, and they are particularly nice when applied to directed acyclic graph (DAG) models. In particular, the standard imset for a DAG is in one-to-one correspondence with the independence model it induces, and hence is a label for its Markov equivalence class.
We present a proposed extension to standard imsets for maximal ancestral graph (MAG) models, using the parametrizing set representation of Hu and Evans (2020). By construction, our imset also represents the Markov equivalence class of the MAG. We show that for many such graphs our proposed imset defines the model, though there is a subclass of graphs for which the representation does not. We prove that it does work for MAGs where there are no adjacent bidirected edges without an ancestral relation, as well as for a large class of purely bidirected models. If there is time, we will also discuss applications of imsets to structure learning in MAGs.
This is joint work with Zhongyi Hu (Oxford).
References:
Hu, Z. and Evans, R.J. Faster algorithms for Markov equivalence. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, 2020.
Hu, Z. and Evans, R.J. Towards standard imsets for maximal ancestral graphs. Preprint, available at arXiv:2208.10436, 2022.
Studenỳ, M. Probabilistic Conditional Independence Structures, Springer, 2005.