graphical_models.classes.dags.dag.DAG.greedy_optimal_single_node_intervention

DAG.greedy_optimal_single_node_intervention(cpdag=None, num_interventions=1)[source]

Greedily pick num_interventions single node interventions based on how many edges they orient.

By submodularity, this will orient at least (1 - 1/e) as many edges as the optimal intervention set of size num_interventions.

Parameters

cpdag – the starting CPDAG containing known orientations. If None, use the observational essential graph.
num_interventions – the number of single-node interventions used. Default is 1.

Returns

The selected interventions and the associated cpdags that they induce.

Return type

(interventions, cpdags)

Examples

>>> from graphical_models import DAG
>>> d = DAG(arcs={(0, 1), (1, 2), (0, 2)})
>>> ivs, icpdags = d.greedy_optimal_single_node_intervention()
>>> ivs
[1]
>>> icpdags[0].arcs
{(0, 1), (0, 2), (1, 2)}