Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes

Gu, Jinhao, García-Fernández, Ángel F, Firth, Robert E and Svensson, Lennart (2024) Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes IEEE Transactions on Signal Processing, 72 (99). pp. 1-13. ISSN 1053-587X, 1941-0476

Access the full-text of this item by clicking on the Open Access link.

Text Graph_GOSPA_metric.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (727kB) | Preview

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	Measurement, Costs, Vectors, Size measurement, Reviews, Chemicals, Polynomials, Metrics, graph matching, generalised optimal sub-pattern assignment metric
Depositing User:	Symplectic Admin
Date Deposited:	29 Aug 2024 07:32
Last Modified:	23 May 2026 09:14
DOI:	10.1109/tsp.2024.3449091
Open Access URL:	https://arxiv.org/abs/2311.07596
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3184102
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.