No project description provided
Project description
Extremely Greedy Equivalence Search
Extremely Greedy Equivalence Search (XGES) is an efficient algorithm for learning the structure of a causal graph from observational data. It improves upon the Greedy Equivalence Search (GES) algorithm with a more accurate search strategy and a more efficient implementation.
The algorithm is described in the paper "Extremely Greedy Equivalence Search" (see citation below)
In this repo, we provide:
- a pure python implementation of the algorithm in
xges/
available withpip install xges
.- it can optionally use
numba
for faster execution. - examples of usage are available in
examples/simple.py
.
- it can optionally use
- a pure c++ implementation of the algorithm in
src-cpp/
, which is at least ~10x faster than the python implementation (withnumba
). - code to reproduce the experiments in the paper in
evaluation/
.- an ad-hoc python wrapper calling the cpp executable is available in
evaluation/benchmarks.py
. - a notebook to generate the figures in the paper in
evaluation/paper.ipynb
.
- an ad-hoc python wrapper calling the cpp executable is available in
Using the python package
The python package can be installed with pip:
pip install xges
The package can be used as follows:
from xges import XGES
data = ...
xges = XGES()
pdag = xges.fit(data) # PDAG object representing the Markov equivalence class (MEC)
# PDAG object with only directed edges, representing an arbitrary DAG in the MEC
a_dag = pdag.get_dag_extension()
# networkx DiGraph object with two edges for undirected PDAG edges
networkx_pdag = pdag.to_networkx()
networkx_dag = a_dag.to_networkx()
adjacency_pdag = pdag.to_adjacency_matrix()
adjacency_dag = a_dag.to_adjacency_matrix()
Reproducing the experiments
The experiments can be reproduced by running the evaluation/benchmarks.py
script (after compiling the c++ code in src-cpp
).
The figures are generated in the notebook evaluation/paper.ipynb
.
Building the c++ code
Use the CMakeLists.txt file to build the code.
The code can be run with the following command:
xges --input data.npy --output out.csv --stats stats.csv -v1
The input file should be a numpy file with the data matrix. The output file
will contain the CPDAG. The stats file will contain some statistics collected
during the execution of the algorithm.
-v1
is the verbosity level. It can be set to 0, 1, or 2.
More options can be found by running xges --help
.
Citation
If you use this code, please cite the following paper:
@inproceedings{nazaret2021extremely,
title={Extremely Greedy Equivalence Search},
author={Nazaret, Achille and Blei, David},
booktitle={Uncertainty in Artificial Intelligence},
year={2024}
}
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file xges-0.1.6.tar.gz
.
File metadata
- Download URL: xges-0.1.6.tar.gz
- Upload date:
- Size: 29.0 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: poetry/1.8.3 CPython/3.11.5 Darwin/23.2.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab520c88692d050d817486e09bc9f08355bf3bb5dc8b73b3cea4dff803fdbab2 |
|
MD5 | a6f58653227d9900bb4e882ee1798491 |
|
BLAKE2b-256 | 7552c10050fe1f63a6efd9a1f73528b923c605d470728e5644217e75d9f9e8a9 |
File details
Details for the file xges-0.1.6-py3-none-any.whl
.
File metadata
- Download URL: xges-0.1.6-py3-none-any.whl
- Upload date:
- Size: 26.3 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: poetry/1.8.3 CPython/3.11.5 Darwin/23.2.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22f0de8dd32a274f96c1ed108f60332d4aa92a563f800bd2babada666963bb9c |
|
MD5 | 7ca95303b400aab242d13406c5feb7a1 |
|
BLAKE2b-256 | 61b9e84f983ea685b13bb728743630a56a18b40e6dc1f19c249749eb90efd367 |