mlsanityData to 7 Oct 2026

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

arXiv 2311.07596 ↗First posted 10 Nov 2023cs.SI cs.LG eess.SPcited by 3

Not on the map. Why?

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.

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

Builds on

12 of 47 references.

References · 12

  1. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  2. 2018Graph networks as learnable physics engines for inference and controlcited by 242
  3. 2018Connecting the Dots: Identifying Network Structure via Graph Signal Processingcited by 111
  4. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  5. 2022Relationformer: A Unified Framework for Image-to-Graph Generationcited by 67
  6. 2019GOT: An Optimal Transport framework for Graph comparisoncited by 64
  7. 2016Generalized optimal sub-pattern assignment metriccited by 33
  8. 2014Graph Matching: Relax at Your Own Riskcited by 27
  9. 2016A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithmscited by 17
  10. 2023On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharingcited by 16
  11. 2016A metric for sets of trajectories that is practical and mathematically consistentcited by 7
  12. 2020Graph Fourier Transform: A Stable Approximationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025From Target Tracking to Targeting Track -- Part I: A Metric for Spatio-Temporal Trajectory Evaluationcited by 2
  2. 2025A family of graph GOSPA metrics for graphs with different sizescited by 0
  3. 2026Beyond Chamfer Distance: Granular Order-aware Evaluation Metric For Online Mappingcited by 0