bcause

A Branch-and-Bound Approach for Finding Optimal Causal Graphs

Developed by the Constraint Reasoning and Optimization Group
at the Department of Computer Science, University of Helsinki.

The program finds a minimum-weight causal graph with respect to given (in)dependence constraints.
Details on the algorithm can be found in [1], [2] and [3].

Usage

Usage: ./bcause [<flags>] <path to input file>

Flags for defining the search space:
  -n <number>     Limit the number of nodes/variables.
  -c <number>     Limit maximum conditioning set size.
  -d <number>     Limit maximum node degree.
  -b <number>     Limit maximum number of <-> edges.
  -a              Enforce acyclicity
  -s              Use sigma-separation instead of d-separation
  -w <number>     Only search for graphs that have lower weight than this.
  -f <string>     Force solutions to contain certain edges. For example:
                           -f "1<>2 2->3 3<-5"
                      or   -f edges.txt
                      ("1</>2 2/>3 3</5" enforces edge inexistence.)

Flags for tuning the search:
  -h <number>     Heuristic for selecting next node pair (X,Y) (default: 0)
                    0. Select pair most likely independent (edges absent)
                    1. Select pair most likely dependent (edge(s) present)
                    2. A hybrid of 0 and 1.
                    3. Branch randomly.
  -N              Enable dataset linking rules for CPLEX
  -R              Disable edge relevancy rules (not recommended)
  -C              Disable CPLEX (not recommended)
  -A              Apply further edge relevancy checks via separate algorithm
  -t <number>     Set the number of threads CPLEX can use (default: 1)
  -v              Enable verbosity (only for debugging purposes)

Input format

The input is a text file, in which each line corresponds to an independence test
result. Each line has the form:

i w x y c j

where

i     0 if the result is dependence or 1 if the result is independence
w     weight, a positive integer representing the reliability
x     the positive index of the first node (starting from 1)
y     the positive index of the second node
c     integer presentation of the conditioning set bit vector
      0 = {}, 1 = {1}, 2= {2}, 3 = {1,2}, 4 = {3}, 5 = {1,3}, ...
j     integer presentation of the intervention set bit vector

Downloads

The latest version can be downloaded here.
Contains added support for sigma-separation, interventions and dataset linking rules [1].

An older version can be downloaded here.
Note: This does not support interventions so every intervention set should be empty (i.e., j is 0 in the input format above).

References

[1] Learning Optimal Cyclic Causal Graphs from Interventional Data
Kari Rantanen, Antti Hyttinen and Matti Järvisalo.
In Proceedings of the International Conference on Probabilistic Graphical Models (PGM 2020),
pages ???—???. PLMR, 2020.

[2] Discovering causal graphs with cycles and latent confounders: An exact branch-and-bound approach
Kari Rantanen, Antti Hyttinen and Matti Järvisalo.
In International Journal of Approximate Reasoning,
volume 117, pages 29—49. 2020.

[3] Learning Optimal Causal Graphs with Exact Search
Kari Rantanen, Antti Hyttinen and Matti Järvisalo.
In Proceedings of the International Conference on Probabilistic Graphical Models (PGM 2018),
pages 344—355. PLMR, 2018.