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

arXiv: https://arxiv.org/abs/2311.07596 · HTML: https://mlsanity.com/paper/2311.07596/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 10 Nov 2023.

## Builds on (most cited first, 12 of 12)

- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Graph networks as learnable physics engines for inference and control](https://mlsanity.com/paper/1806.01242/) (2018)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [Relationformer: A Unified Framework for Image-to-Graph Generation](https://mlsanity.com/paper/2203.10202/) (2022)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Generalized optimal sub-pattern assignment metric](https://mlsanity.com/paper/1601.05585/) (2016)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithms](https://mlsanity.com/paper/1605.01177/) (2016)
- [On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing](https://mlsanity.com/paper/2303.10695/) (2023)
- [A metric for sets of trajectories that is practical and mathematically consistent](https://mlsanity.com/paper/1601.03094/) (2016)
- [Graph Fourier Transform: A Stable Approximation](https://mlsanity.com/paper/2001.05042/) (2020)

## Built on by (most cited first, 3 of 3)

- [From Target Tracking to Targeting Track -- Part I: A Metric for Spatio-Temporal Trajectory Evaluation](https://mlsanity.com/paper/2502.15842/) (2025)
- [A family of graph GOSPA metrics for graphs with different sizes](https://mlsanity.com/paper/2506.17316/) (2025)
- [Beyond Chamfer Distance: Granular Order-aware Evaluation Metric For Online Mapping](https://mlsanity.com/paper/2605.22578/) (2026)

## Abstract (arXiv)

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.