  Evaluating graphs learned by causal discovery algorithms is difficult: The
number of edges that differ between two graphs does not reflect how the graphs
differ with respect to the identifying formulas they suggest for causal
effects. We introduce a framework for developing causal distances between
graphs which includes the structural intervention distance for directed acyclic
graphs as a special case. We use this framework to develop improved
adjustment-based distances as well as extensions to completed partially
directed acyclic graphs and causal orders. We develop new reachability
algorithms to compute the distances efficiently and to prove their low
polynomial time complexity. In our package gadjid (open source at
https://github.com/CausalDisco/gadjid), we provide implementations of our
distances; they are orders of magnitude faster with proven lower time
complexity than the structural intervention distance and thereby provide a
success metric for causal discovery that scales to graph sizes that were
previously prohibitive.
