Graph GOSPA metric: a metric to measure the discrepancy between graphs
  of different sizes
Jinhao Gu Ángel F. García-Fernández Robert E. Firth Lennart Svensson
This paper proposes a metric to measure the dissimilarity between graphs that
may have a different number of nodes. The proposed metric extends the
generalised optimal subpattern assignment (GOSPA) metric, which is a metric for
sets, to graphs. The proposed graph GOSPA metric includes costs associated with
node attribute errors for properly assigned nodes, missed and false nodes and
edge mismatches between graphs. The computation of this metric is based on
finding the optimal assignments between nodes in the two graphs, with the
possibility of leaving some of the nodes unassigned. We also propose a lower
bound for the metric, which is also a metric for graphs and is computable in
polynomial time using linear programming. The metric is first derived for
undirected unweighted graphs and it is then extended to directed and weighted
graphs. The properties of the metric are demonstrated via simulated and
empirical datasets.