Basic Errors

This set of node and edge errors applies only to graphs with a one-to-one matching.

Nodes

True Positive

A true positive node is defined as a predicted node that matches to only one ground truth node. Additionally, the corresponding ground truth node cannot be matched to more than one predicted node. True positives are annotated on both the ground truth and the division graph.

False Positive

A false positive node is a node on the predicted graph does not match to a node on the ground truth graph. False positives are annotated on the predicted graph.

../_images/c128b765be1f8e67760e151e60049efb35591d4647db0a2931a2119e4e016b8d.png

False Negative

A false negative node is a node on the ground truth graph that is not matched to a predicted node. False negatives are annotated on the ground truth graph.

../_images/caa3b6d5fee33008872d08b6151eec28ac7d7a482bdd9e0e4dd0ff37bfcf1db3.png

Edges

True Positive

An edge in the ground truth is a true positive edge if both source and target node are true positives and the corresponding edge is present in the prediction. True positive edges are annotated on both the ground truth and the predicted graph.

False Positive

False positive edges occur in and are annotated on the predicted graph. A false positive edge can occur in several different scenarios when the edge fails to meet the criteria for a true positive.

Ex 1: Nodes 7 and 8 are not matched to any node in the GT.
Ex 2: While Nodes 5 and 6 are matched to nodes in the GT, an edge does not exist between the corresponding GT nodes 2 and 3.
Ex 3: Node 6 is not matched to a node in the GT.

../_images/e01338e8eac7e3bd431c8ab3439194fcdc7074357b2addf285e1897acb4c6966.png

False Negative

A false negative edge can occur in the ground truth graph when:

One or both of the nodes is not a true positive and matched to a node in the prediction
The matched nodes in the prediction do not also have an edge between them

../_images/e20e0135c43cac1010cd7f920b71feb3e95dc6883072fcd3e7ee057bf3b1a765.png

Skip Edges

Under default behavior, skip edges will be annotated as False Positive on the predicted graph and False Negative on the ground truth graph unless both graphs contain an identical skip edge. Similarly, skip edges on the predicted graph that do not exist in the ground truth graph will be annotated as False Positive, with corresponding False Negative annotations on the ground truth.

Ex 1: The skip edges are identical, they will be marked TP.
Ex 2: The GT skip edge is not present in the prediction. It is annotated as FN. Predicted edges are FP.
Ex 3: The predicted skip edge is not present in the GT. It is annotated as FP. GT edges are FN.

../_images/17908a40357ee6aa9e1e26f89cab1b071848a2b62417422fe25364aab8ef6bfa.png

Skip edges can be handled more permissively by setting relax_skips_gt=True and/or relax_skips_pred=True. In this scenario, an edge u -> v can be matched to an edge x -> y -> z if the the endpoint nodes are matched and the intermediate node (y) is not matched.

By relaxing skip edges on one or both of the graphs, the following cases can become correct. The skip edge itself will be annotated as a skip true positive (STP). Any matching edges on the opposite graph will also be annotated as STPs.

../_images/c63527c4f58304759ffc45491e96d9452d39b3dce907e023ef0aded7d6ac1b9d.png