dodiscover.metrics.structure_hamming_dist(true_graph, pred_graph, double_for_anticausal=True)[source]#

Compute structural hamming distance.

The Structural Hamming Distance (SHD) is a standard distance to compare graphs by their adjacency matrix. It consists in computing the difference between the two (binary) adjacency matrixes: every edge that is either missing or not in the target graph is counted as a mistake. Note that for directed graph, two mistakes can be counted as the edge in the wrong direction is false and the edge in the good direction is missing; the double_for_anticausal argument accounts for this remark. Setting it to False will count this as a single mistake.

true_graphinstance of nx.Graph or nx.DiGraph

The true graph as an instance of a MixedEdgeGraph with only one type of edge.

pred_graphinstance of nx.Graph or nx.DiGraph

The predicted graph. The predicted graph and true graph must be the same type.

double_for_anticausalbool, optional

Whether to count incorrect orientations as two mistakes, by default True


The hamming distance between 0 and infinity.


SHD is only well defined if you have a graph with only undirected edges, or directed edges. That is, we only consider a Bayesian network, or a causal DAG as candidates. If there are more than one type of edge within the network, then SHD can be called on a sub-graph of that edge type. For example, say you would like to compare a PAG, where there are directed, undirected, bidirected and edges with circular endpoints. Currently, there is no known way of comparing two PAGs systematically. Therefore, one can compare PAGs via the number of circle edges, or the SHD of the undirected, bidirected, directed edge subgraphs.