The CAUSALGRAPH Procedure

Time Requirements

The following table summarizes the approximate computational cost to perform various tasks by using the CAUSALGRAPH procedure. The computational costs are computed for a DAG that contains N nodes (variables) and M edges.

For certain tasks, such as listing all adjustment sets, the output might grow exponentially large with the size of the graph. For these tasks, the computational cost is given in terms of delay complexity. The delay complexity is the computational cost that is associated with producing each element of the output set (Takata 2010).

The time required to… Is roughly proportional to
Test an adjustment upper N squared
Find one adjustment upper N squared
List all adjustments upper N left-parenthesis upper N plus upper M right-parenthesis delay
List all minimal adjustments upper N cubed delay
Test an instrument upper N plus upper M
List all instruments upper N upper M delay
List local Markov properties upper N left-parenthesis upper N plus upper M right-parenthesis
List global Markov properties upper N left-parenthesis upper N plus upper M right-parenthesis delay

In general, the algorithms to test or find a single adjustment set have a computational cost proportional to left-parenthesis upper N plus upper M right-parenthesis (Van der Zander, Liśkiewicz, and Textor 2014). However, PROC CAUSALGRAPH always checks whether an adjustment set is minimal, and this operation is associated with a computational cost proportional to upper N squared.

By default, PROC CAUSALGRAPH sorts adjustment sets so that the smallest sets are printed first. You can use the MAXLIST= option in the PROC CAUSALGRAPH statement to limit the printed output, but this does not change the computational cost unless you also specify the NOSORT option in the same statement.

In certain situations, you might simply want to ascertain whether any adjustment set exists, regardless of which variables that adjustment set includes. To do this efficiently, you can request a single adjustment set by combining the NOSORT option with the MAXLIST=1 option. This enables the procedure to quickly find and display a single adjustment set. In the special case where you specify METHOD=ADJUSTMENT together with the NOSORT and MAXLIST=1 options in the PROC CAUSALGRAPH statement, the procedure switches to an even more efficient algorithm (Van der Zander, Liśkiewicz, and Textor 2014). For an illustration, see Example 37.2.

Last updated: December 09, 2022