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.

提出一种用于度量具有不同节点数量的图之间不相似性的测量方法，该方法基于泛化的最优子模式分配（GOSPA）度量对图进行了扩展，并包括与节点属性错误、缺失和虚假节点以及图之间的边不匹配相关的成本。该度量的计算基于在两个图之间找到节点之间的最优分配，并可能保留一些节点未分配，同时还提出了一种低界，该低界也是一种图度量，可以使用线性规划在多项式时间内计算。该度量首先针对无向无权图进行推导，然后扩展到有向和有权图，并通过模拟和实证数据集展示了其性质。