A family of graph GOSPA metrics for graphs with different sizes

Jinhao Gu; Ángel F. García-Fernández; Robert E. Firth; Lennart Svensson

cs.SIJun 18, 2025

A family of graph GOSPA metrics for graphs with different sizes

Authors: Jinhao Gu, Ángel F. García-Fernández, Robert E. Firth, Lennart Svensson

Organizations: Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool L69 3GJ · IPTC, ETSI de Telecomunicación, Universidad Politécnica de Madrid, 28040 Madrid, Spain · STFC Hartree Centre, WA4 4AD Daresbury, UK · Department of Electrical Engineering, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden

Abstract

This paper proposes a family of graph metrics for measuring distances between graphs of different sizes. The proposed metric family defines a general form of the graph generalised optimal sub-pattern assignment (GOSPA) metric and is also proved to satisfy the metric properties. Similarly to the graph GOSPA metric, the proposed graph GOSPA metric family also penalises the node attribute costs for assigned nodes between the two graphs, and the number of unassigned nodes. However, the proposed family of metrics provides more general penalties for edge mismatches than the graph GOSPA metric. This paper also shows that the graph GOSPA metric family can be approximately computed using linear programming. Simulation experiments are performed to illustrate the characteristics of the proposed graph GOSPA metric family with different choices of hyperparameters. The benefits of the proposed graph GOSPA metric family for classification tasks are also shown on real-world datasets.

Figures & tables

	Node	Types of	Metric
	attributes	edge mismatches	property
MCS [ 9 , 10 ]	✗	1	D
GED [ 11 ]	✓	1	D
GCD [ 16 ]	✓	1	F
Graph OSPA & GTT [ 19 ]	✓	1	D
Graph GOSPA [ 23 ]	✓	2	D

TABLE I : Properties of graph distances. ’D’: implies that it is a metric for different number of nodes, ’F’: it is a metric for a fixed number of nodes.

Panel of Figure 2 — Fig. 1 : Example to illustrate the node and edge mismatch costs for the same ground truth graph $X$ , and two estimated graphs $Y$ . (a) Three assigned nodes, one unassigned node, one assigned edge mismatch and one half-assigned edge; (b) three assigned nodes, two unassigned nodes, one assigned edge mismatch, one half-assigned edge and one unassigned edge.

Optimisation	Cost function	Constraints
General	( 14 )	( 4 )-( 7 )
MIQP	( 22 )	( 4 )-( 7 ), ( 19 )-( 21 )
(Relaxed) QP	( 22 )	( 4 )-( 6 ), ( 19 )-( 21 ), ( 30 )
MILP	( 29 )	( 4 )-( 7 ), ( 19 )-( 21 ), ( 23 )-( 26 )
(Relaxed) LP	( 29 )	( 4 )-( 6 ), ( 19 )-( 21 ), ( 23 )-( 26 ), ( 30 )

TABLE II : Optimisation problems to compute the graph GOSPA metric family

Panel of Figure 4 — Fig. 2 : Plots of average graph GOSPA metric family errors (with the standard deviation shown as a shared area), GCD, GED and MCS, comparing the ground truth graph with (a) graphs with random Gaussian noise with increasing noise variance in node attributes; (b) graphs with random edge addition in adjacency matrix and small Gaussian noise in node attributes; (c) graphs with random edge removal in adjacency matrix and small Gaussian noise in node attributes; (d) graphs with different sizes.

Panel of Figure 5 — Fig. 3 : Plots of average graph GOSPA metric family with different hyperparameters $\beta$ and $\eta$ , comparing the ground truth graph with (a) graphs with random Gaussian noise with increasing noise variance in node attributes; (b) graphs with random edge addition in adjacency matrices; (c) graphs with random edge removal in adjacency matrices; (d) graphs with different sizes.

$(n_{X},n_{Y})$	(10,10)	(20,20)	(40,40)	(60,60)
Graph GOSPA	0.01	0.11	10.68	159.72
GED	28.53	>5000	-	-
GCD	0.02	0.18	8.75	200.17
Graph GOSPA family (LP)	0.02	0.30	28.22	3282.16
Graph GOSPA family (MILP)	1.93	>5000	-	-
Graph GOSPA family (QP)	14.16	304.81	406.09	>5000

TABLE III : Computational time over undirected graphs (CPU time in seconds).

	MUTAG	Letter-m	Letter-h	PTC (FM)	PTC (MM)	PTC (MR)
Graph GOSPA	89.47%	94.33%	91.78%	59.47%	57.35%	47.83%
GCD	86.84%	93.94%	88.44%	57.79%	52.94%	56.52%
GED	84.21%	89.33%	84.22%	58.77%	58.82%	52.17%
Graph GOSPA family	89.47%	95.78%	91.78%	64.29%	60.29%	57.94%

TABLE IV : Classification accuracy of the KNN classifiers on real-world datasets.

	Graph GOSPA	Graph GOSPA family
	( $c$ , $\epsilon$ , $\eta=0.5$ , $\beta=0$ )	( $c$ , $\epsilon$ , $\eta$ , $\beta$ )
MUTAG	(6.0, 1.73)	(3.0, 1.2, 0.8, 0.78)
Letter-m	(2.0, 1.19)	(2.0, 1.2, 0.55, 0.67)
Letter-h	(3.0, 1.19)	(3.0, 1.2, 0.8, 0.73)
PTC (FM)	(9.0, 0.1)	(6.0, 2.3, 0.03, 0.17)
PTC (MM)	(9.0, 1.73)	(1.0, 1.2, 0.86, 0.5)

TABLE V : Optimal hyperparameter obtained.

Explore similar work

$k$ -Nearest Neighbors in Gromov--Wasserstein Space
Jun 9, 2026Kaitlyn Hohmeier, Nicolas Fraiman, Caroline MoosmuellerGromov--Wasserstein Approximate Nearest-Neighbor Search
University of North Carolina at Chapel Hill, Department of Mathematics · University of North Carolina at Chapel Hill, Department of Statistics and Operations Research
Graph Matching Relaxations and Amortization for Supervised Graph Prediction
Sep 14, 2026Federico Méndez, Paul Krzakala, Gabriel Melo +3Graph Representation Learning Fused Sinkhorn-Localized Similarity
LTCI, Télécom Paris · Institut Polytechnique de Paris · CMAP, École Polytechnique
Diffusion enabled Optimal Transport distances for graph matching
Jul 7, 2026Iman Seyedi, Francesco ArchettiGraph Representation Learning Gromov--Wasserstein
Department of Computer Science Systems and Communication, University of Milano-Bi- cocca, 20126 Milan, Italy

Jun 9, 2026, stat.MLJ/K move · Enter open · S save

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

University of North Carolina at Chapel Hill, Department of Mathematics · University of North Carolina at Chapel Hill, Department of Statistics and Operations Research

Gromov--Wasserstein Approximate Nearest-Neighbor Search Metric Spaces Text-Attributed Graph Distance

Open paper AskPDF arXiv

The Gromov--Wasserstein (GW) distance provides a framework for comparing metric measure spaces, regardless of their underlying structure or geometry. For network-based data, it enables direct comparisons of graphs with different numbers of nodes, without requiring an embedding or other abstraction. Furthermore, through a variant of GW known as fused Gromov--Wasserstein (fGW), it is also possible to incorporate node features in addition to graph structure. In this work, we implement

k

-nearest neighbors (

k

-NN) classification using the GW and fGW distances. We prove the universal consistency of the GW-

k

-NN classifier on the space of equivalence classes of metric measure spaces with finite support and uniform probability measure. By viewing graphs as finitely supported metric measure spaces equipped with the pairwise distance metric and a uniform probability measure on the nodes, we obtain universal consistency of GW-

k

-NN for the space of graphs. Likewise for fGW-

k

-NN, we prove universal consistency on the space of weak isomorphism classes of structured objects consisting of metric measure spaces with finite support and uniform probability measure and feature maps into Euclidean space, thus establishing universal consistency on the space of node-attributed graphs. Our numerical experiments show that GW-

k

-NN and fGW-

k

-NN consistently perform well across multiple graph datasets, suggesting that metric classifiers such as

k

-NN work well in the GW framework.

Abstract

Explore similar work

kkk-Nearest Neighbors in Gromov--Wasserstein Space

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

Diffusion enabled Optimal Transport distances for graph matching

$k$ -Nearest Neighbors in Gromov--Wasserstein Space