Structural Hamming distance （Structural Hamming Distance）

Structural Hamming distance （SHD） Is to compare the standard distance of the graph through the adjacency matrix . It includes calculating two （ Binary system ） The difference between adjacency matrices ： Every edge that is missing or not in the target graph is counted as an error . Please note that , For digraphs , Two errors can be counted : The side in the wrong direction is false , The side with good direction is missing ;double_for_anticausal The parameter explains this problem . Set it to " false " Will be regarded as an error .

python Of SHD The calling code is ：

cdt.metrics.SHD(target, pred, double_for_anticausal=True)

Where the parameters are ：

An example ：

from cdt.metrics import SHD
from numpy.random import randint
tar, pred = randint(2, size=(10, 10)), randint(2, size=(10, 10))
SHD(tar, pred, double_for_anticausal=False)

Reference resources ： 

https://fentechsolutions.github.io/CausalDiscoveryToolbox/html/metrics.html#:~:text=The%20Structural%20Hamming%20Distance%20%28SHD%29%20is%20a%20standard,the%20target%20graph%20is%20counted%20as%20a%20mistake.

False discovery rate （False Discovery Rate)

The false discovery rate is to judge all discovery The wrong and reverse proportions in , namely ：

among

It's complicated , Save it directly NOTEARS For the implementation process of several common judgment standards

def count_accuracy(B_true, B_est):
    """Compute various accuracy metrics for B_est.

    true positive = predicted association exists in condition in correct direction
    reverse = predicted association exists in condition in opposite direction
    false positive = predicted association does not exist in condition

    Args:
        B_true (np.ndarray): [d, d] ground truth graph, {0, 1}
        B_est (np.ndarray): [d, d] estimate, {0, 1, -1}, -1 is undirected edge in CPDAG

    Returns:
        fdr: (reverse + false positive) / prediction positive
        tpr: (true positive) / condition positive
        fpr: (reverse + false positive) / condition negative
        shd: undirected extra + undirected missing + reverse
        nnz: prediction positive
    """
    if (B_est == -1).any():  # cpdag
        if not ((B_est == 0) | (B_est == 1) | (B_est == -1)).all():
            raise ValueError('B_est should take value in {0,1,-1}')
        if ((B_est == -1) & (B_est.T == -1)).any():
            raise ValueError('undirected edge should only appear once')
    else:  # dag
        if not ((B_est == 0) | (B_est == 1)).all():
            raise ValueError('B_est should take value in {0,1}')
        if not is_dag(B_est):
            raise ValueError('B_est should be a DAG')
    d = B_true.shape[0]
    # linear index of nonzeros
    pred_und = np.flatnonzero(B_est == -1)
    pred = np.flatnonzero(B_est == 1)# The position of the node that is the parent node in the matrix we obtained （flatten In the following matrix ）
    cond = np.flatnonzero(B_true)# The position of the node that is the parent node in the real adjacency matrix （flatten In the following matrix ）
    cond_reversed = np.flatnonzero(B_true.T)# This function inputs a matrix , Returns the position of non-zero elements in the flattened matrix 
    cond_skeleton = np.concatenate([cond, cond_reversed])# It can splice multiple arrays at one time 
    # true pos
    true_pos = np.intersect1d(pred, cond, assume_unique=True)# Returns the sorted 、 Unique value 
    # treat undirected edge favorably
    true_pos_und = np.intersect1d(pred_und, cond_skeleton, assume_unique=True)
    true_pos = np.concatenate([true_pos, true_pos_und])
    # false pos
    false_pos = np.setdiff1d(pred, cond_skeleton, assume_unique=True)
    false_pos_und = np.setdiff1d(pred_und, cond_skeleton, assume_unique=True)
    false_pos = np.concatenate([false_pos, false_pos_und])
    # reverse
    extra = np.setdiff1d(pred, cond, assume_unique=True)
    reverse = np.intersect1d(extra, cond_reversed, assume_unique=True)
    # compute ratio
    pred_size = len(pred) + len(pred_und)
    cond_neg_size = 0.5 * d * (d - 1) - len(cond)
    fdr = float(len(reverse) + len(false_pos)) / max(pred_size, 1)
    tpr = float(len(true_pos)) / max(len(cond), 1)
    fpr = float(len(reverse) + len(false_pos)) / max(cond_neg_size, 1)
    # structural hamming distance
    pred_lower = np.flatnonzero(np.tril(B_est + B_est.T))
    cond_lower = np.flatnonzero(np.tril(B_true + B_true.T))
    extra_lower = np.setdiff1d(pred_lower, cond_lower, assume_unique=True)
    missing_lower = np.setdiff1d(cond_lower, pred_lower, assume_unique=True)
    shd = len(extra_lower) + len(missing_lower) + len(reverse)
    return {'fdr': fdr, 'tpr': tpr, 'fpr': fpr, 'shd': shd, 'nnz': pred_size}