causaldag.classes.dag.DAG.greedy_optimal_single_node_intervention

DAG.greedy_optimal_single_node_intervention(cpdag=None, num_interventions=1)

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

>>> import causaldag as cd
>>> d = cd.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)}