Identifiability of AMP Chain Graph Models

This is an implementation of the following paper:

Wang Yuhao, and Arnab Bhattacharyya. "Identifiability of AMP chain graph models." arXiv preprint arXiv:2106.09350 (2021).

Updates:

Add a Python-version SFO, now you can choose either use Matlab or Python version SFO for learning unknwon chain components.

Background

Chain graph models contain both directed and undirected edges and can be used to represent both association and causation in real-world applications.

Chain graph models

Nodes can be disjointly partitioned into several chain components;
Edges between nodes in chain are undirected;
Edges between nodes in different chains are directed.

Identifiability

The partitioning of chain components and the topological order on the chain components are uniquely specified.

Video explanation

About chain graph models.
About this work

Introduction

We study identifiability of Andersson-Madigan-Perlman (AMP) chain graph models, which are a common generalization of linear structural equation models and Gaussian graphical models. AMP models are described by DAGs on chain components which themselves are undirected graphs.

For a known chain component decomposition, we show that the DAG on the chain components is identifiable if the determinants of the residual covariance matrices of the chain components are monotone non-decreasing in topological order. This condition extends the equal variance identifiability criterion for Bayes nets, and it can be generalized from determinants to any super-additive function on positive semidefinite matrices. When the component decomposition is unknown, we describe conditions that allow recovery of the full structure using a polynomial time algorithm based on submodular function minimization. We also conduct experiments comparing our algorithm's performance against existing baselines.

Prerequisites

Python 3.6+
- networkx
- argpase
- numpy
- scipy
- matplotlib
- torch: Optional.
R 4.0.0
- rpy2: Python interface, enables calling R from Python. Install rpy2 first.
- pcalg : Methods for Graphical Models and Causal Inference
- mgvc : Mixed GAM Computation Vehicle with Automatic Smoothness Estimation
- ggm : Graphical Markov Models with Mixed Graphs
- lcd :Learn Chain graphs via Decomposition Notes: lcd is a relatively old package and can be installed from here.
Matlab R2020b
- Python-Matlab : Calling Matlab from Python. Install Python-Matlab first.
- SFO : A Matlab toolbox for Submodular Function Optimization SFO(v 2.0).

data.py - generate synthetic chain graph data, including graph simulation and data simulation
evaluate.py - algorithm accuracy evaluation.
utils.py - simulation parameters, such as selecte graph type, node number, data type, graph degree, etc.
utils.R - prune, regression, etc.
main.py - main algorihtm.

Parameters

Parameter	Type	Description	Options
`n`	int	number of nodes	-
`c`	int	number of chain components	-
`a`	int	average node degree	-
`d`	int	number of samples	-
`plot`	Bool	plot chain graph or not	-
`graph`	str	graph for unknow/known chain components	`known`, `unknown`
`task`	str	choice which task to implement	`known_cc`, `unknown_cc`
`algorithm`	str	choice which algorithm	`known_dcov`, `unknown_dcov`
`regress_method`	str	methods for regression	`mgcv`, `np`

Running a simple demo

The simplest way to try out DCOV is to run a simple example:

$ git clone https://github.com/YohannaWANG/DCOV.git
$ cd DCOV/
$ python DCOV/main.py

Runing as a command

Alternatively, if you have a CSV data file X.csv, you can install the package and run the algorithm as a command:

$ pip install git+git://github.com/YohannaWANG/DCOV
$ cd DCOV
$ python main.py --graph known_cc --task eql_det --algorithm known_npcov --regress_method mgcv --n 50 --s 1000 --d 4 --operator det

Algorithms

Algorithm 1Learn a DAG structure over known chain components;
Algorithm 2 AMP Chain graph identification from unknown chain components.

Performance

Algorithm 1 (Known chain components)	Algorithm 2 (Unknown chain components)

''

Related Works

One paragraph in our related work section gives almost a complete history of work done on them! We summarized most of the related works below, it will also be updated accordingly.

https://github.com/YohannaWANG/Chain-Graph-Literature

Citation

@article{wang2021identifiability,
  title={Identifiability of AMP chain graph models},
  author={Wang, Yuhao and Bhattacharyya, Arnab},
  journal={arXiv preprint arXiv:2106.09350},
  year={2021}
}

Contacts

Please feel free to contact us if you meet any problem when using this code. We are glad to hear other advise and update our work. We are also open to collaboration if you think that you are working on a problem that we might be interested in it. Please do not hestitate to contact us!

YohannaWANG/DCOV