/DCOV

Identifiability of AMP chain graph

Primary LanguageMATLABGNU General Public License v3.0GPL-3.0

   

Documentation Status Maintenance License: GPL v3

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.

characterization

Identifiability

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

characterization

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

Contents

  • 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

  • #f03c15 Algorithm 1Learn a DAG structure over known chain components; characterization
  • #c5f015 Algorithm 2 AMP Chain graph identification from unknown chain components. characterization

Performance

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

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

Ask Me Anything ! 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!