Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
This provides a metric for researchers and practitioners in graph analysis to compare graphs of varying sizes, but it is incremental as it builds on existing set-based metrics.
The paper tackles the problem of measuring dissimilarity between graphs of different sizes by extending the GOSPA metric to graphs, resulting in a metric that accounts for node attribute errors, missed/false nodes, and edge mismatches, with a polynomial-time computable lower bound validated on simulated and empirical datasets.
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.