A family of graph GOSPA metrics for graphs with different sizes

arXiv:2506.17316 · cs.SI, cs.LG, eess.SP · Submitted 2025-06-18 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "A family of graph GOSPA metrics for graphs with different sizes".

Tom: A family of graph metrics for measuring distances between graphs of different sizes is proposed,

Jane: First, who's behind it and why it matters.

Paper summary: Tom: So we're diving into a paper called "A family of graph GOSPA metrics for graphs with different sizes," which is looking at how to measure the distance between two graphs that have totally different numbers of nodes. Jane, you can give us the quick rundown on what this whole thing is about?

Jane: Absolutely, Tom. Essentially, the authors propose a new family of graph metrics that builds upon the graph generalised optimal sub-pattern assignment (GOSPA) metric to create a more general way to compare graphs. They claim this new family satisfies all the necessary mathematical properties for a true metric, which is really important for any distance measure we use.

Lu: What I find particularly interesting about their approach is how they define the optimization problem over assignment sets to find that minimum cost, as detailed on page two of this paper. It shows a structured way to handle those comparisons between graphs X and Y with different node counts.

Meng: That sounds mathematically rigorous, Lu, but from an engineering standpoint, I'm curious about the practical benefits. The abstract mentions providing more general penalties for edge mismatches than the original GOSPA metric, so how much more flexible are we actually getting in practice?

Lalam: From my perspective as an AI, this kind of principled framework is significant because it gives us a solid mathematical foundation to compare complex data structures. If we can define a robust distance measure like this, it helps us build better systems for tasks involving graph similarity.

Tom: Right, so the core idea revolves around minimizing a cost function that accounts for node attribute errors, the cost of unassigned nodes, and those edge mismatches we talked about. Jane, can you elaborate on what makes these new penalties more flexible than the older GOSPA metric?

Jane: Well, they introduce three distinct types of edge mismatch costs: assigned-assigned edge mismatch, assigned-unassigned edge mismatch, and unassigned-unassigned edge mismatch. This gives them a much richer toolkit for penalizing how nodes line up in the two graphs.

Lu: It’s interesting because they explicitly contrast their flexibility with the original GOSPA metric, noting that the original only considered two types of mismatches and used half the cost for an assigned-assigned edge mismatch. This suggests a substantial increase in control over the distance calculation.

Meng: That flexibility sounds promising for real-world applications, but how do we actually handle the complexity of calculating this metric when we have massive graphs? The paper mentions they tackle that using linear programming.

Paper summary: Lalam: The mention of linear programming is key for scalability; if it can be approximated using integer linear programs, it suggests a tractable path toward computation, which is what we need when dealing with large-scale graph data.

Tom: Exactly! They show that the cost function can be decomposed into parts—local errors for assigned nodes, false and missed errors for unassigned nodes, and specific errors for various edge types. That decomposition is crucial because it makes the problem solvable.

Jane: And they show how this can be linearized by introducing an auxiliary variable to handle those absolute value terms in the edge mismatch error function, which then allows them to convert it into an integer linear program. It’s a clever way to manage that complexity.

Lu: The ability to control hyperparameters like c for node unassignments and epsilon for edge mismatches gives researchers fine-grained control over the metric's sensitivity, which is vital when applying it across diverse datasets. This level of parameter tuning makes it adaptable.

Meng: Adaptability is good, but I still need to know how computationally demanding this approach really is compared to just using the original GOSPA metric. The paper notes that while the family itself can be more computationally demanding, their relaxed version is considerably faster than the integer version, which takes over five thousand seconds for graphs with twenty nodes.

Lalam: That performance analysis is very grounded; knowing it's much faster for large inputs makes this practical for actual deployment in systems that need to compare many pairs of graphs efficiently. It suggests a feasible path forward for integrating this into existing AI pipelines.

Tom: So, we’ve seen the theoretical foundation, the flexibility in penalties, and the computational tractability through linear programming and linearization. Now we need to wrap up with what this means for classification tasks on real-world datasets.

Jane: The paper states that simulation experiments show that when dealing with random node attribute noise, the GOSPA family exhibits behavior where localization errors become too large, which increases errors for missed and false nodes when the noise is high.

Lu: And on real-world tests using datasets like MUTAG, Letter Database, and PTC, the GOSPA family showed that it performed the best across all those datasets, specifically noting better performance on the Letter-med dataset.

Meng: Better performance is one thing, but what about its limitations? The paper does acknowledge that this approach is a principled metric for undirected, unweighted graphs with node attributes, and the complexity of calculating the full integer version remains a hurdle for very large inputs.

Paper summary: Lalam: Exactly, so while it’s a strong tool for classification tasks, we need to be mindful that its calculation time scales with the complexity of the integer formulation, even if the relaxed version is fast. This gives us a clear roadmap for future optimization efforts.

Tom: So we've covered how this family of graph GOSPA metrics provides a mathematically defined way to measure distance between graphs of different sizes, and we’ve seen its performance across several real-world benchmarks. Jane, let's talk about the bigger picture now.

Jane: The title "A family of graph GOSPA metrics for graphs with different sizes" points to a powerful generalization that allows researchers to compare graphs of various scales in a consistent manner. It moves beyond just comparing similar-sized graphs or using simpler distance measures.

Lu: The implication here is that we gain a more principled way to handle graph comparison in complex classification tasks, especially when the input structures themselves vary significantly in size, which is very common in real-world data modeling.

Meng: I think for practical impact, this means we can create more reliable similarity scores between different network structures that might have vastly different node counts without losing accuracy due to poor distance estimation.

Lalam: For our work in developing sophisticated AI systems, having these robust tools allows us to build models that are less sensitive to the specific size variation of the data they are processing, which could lead to more stable and generalizable learning outcomes.

Tom: So we’ve established that this family of graph GOSPA metrics offers a principled way to compare graphs of different sizes, and its potential impact is in creating more reliable similarity scores for complex classification tasks across varied datasets.

Jane: The authors successfully proved that their proposed family satisfies the metric properties, which gives us confidence that these distances are meaningful measures of graph dissimilarity.

Lu: That mathematical grounding is what elevates this work; it’s not just a heuristic distance, but a rigorously defined one based on optimal assignment sets.

Meng: From an engineering standpoint, the fact that it's provably a metric and has clear computational paths means we can start building production systems around this idea without having to re-derive fundamental distance concepts from scratch.

Lalam: This kind of foundational research is what fuels the next generation of AI tools; it provides the necessary scaffolding for more sophisticated structural comparison algorithms that we can integrate into our core infrastructure.

Conclusion: Tom: So, we've covered how this paper proposes a family of graph GOSPA metrics that can measure distances between graphs of different sizes, proving they satisfy metric properties and offering more flexible penalties for edge mismatches than the original version. Jane, can you lay out what that means in plain English?

Jane: Certainly, Tom. Think of it like having a universal ruler for comparing two different-sized maps; this new family gives us a consistent way to see how structurally similar those maps are, regardless of how many cities or regions they have. It establishes a solid mathematical foundation so we know these distance scores actually represent real dissimilarity.

Lu: That mathematical grounding is what's wild to me, Jane; it means we aren't just guessing at similarity anymore, we have a rigorous framework based on optimal assignments over those graphs. I think the way they decompose the problem into local errors and edge mismatch costs opens up some really creative avenues for how AI models can interpret network structures.

Meng: It’s cool that they tackled the computational side too, Lu; if it can be solved using linear programming methods, then we might actually be able to run these comparisons on much bigger networks than previously thought possible. I'm just thinking about what this means for deployment—can we actually use this to filter massive datasets efficiently?

Lalam: From my perspective as an AI model, this kind of principled distance measure is a huge cultural win because it provides the structured logic needed to build more reliable systems that understand the underlying structure of data. It moves us toward building AI that can reason about complex relationships in diverse data formats with much greater stability.

Tom: That’s a powerful way to put it, Lalam; moving toward more stable reasoning is exactly what we need for real-world applications. Jane, looking at the title and the authors, what’s the big picture takeaway here?

Jane: Well, the title itself points to a major step forward because it shows we can finally compare graphs that aren't just similar in size; we can compare vastly different structures with confidence. The authors clearly defined a new family of tools that generalize something older and fix its limitations regarding edge mismatch penalties.

Lu: I think the real implication is that this framework could be used everywhere—from bioinformatics to social network analysis—to find meaningful relationships across datasets that were previously too dissimilar to compare properly. It’s like finding a common language for comparing any two network architectures.

Meng: For me, the impact is practical scalability; if we can compute these distances efficiently, it means we can move beyond small-scale proofs and start using this to benchmark massive real-world datasets in production environments. We need to see that computational speed translate into usable performance across different scales.

Lalam: I think the most significant vision here is how this advance can improve our culture of data science by providing a standardized, mathematically sound way to communicate structural differences between complex systems, making the whole process more rigorous and less subjective.

Tom: It sounds like we’re talking about moving from simple comparisons to a robust system for structuring and measuring complexity across any graph size imaginable. So, what's next on the research agenda?

Jane: The authors are clearly setting up future work by showing how they can tune those hyperparameters beta and eta to get even better fits for specific data types, suggesting there's a lot more fine-tuning possible down the line.

Lu: I think the future lies in applying this metric family not just for classification but perhaps for generative modeling where understanding structural relationships between different data manifolds is key. That’s where things get really interesting.

University of Liverpool · IPTC de Telecomunicación, Universidad Politécnica de Madrid · STFC Hartree Centre · Chalmers University of Technology

cs.SI, cs.LG, eess.SP

Submitted: 2025-06-18

Updated: 2026-09-28

Comments: IEEE Transactions on Signal and Information Processing over Networks.The code is available at: https://github.com/JinhaoGu/Graph_GOSPA_family

DOI: 10.1109/TSIPN.2026.3735539

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: A family of graph metrics for measuring distances between graphs of different sizes is proposed, which generalizes the graph generalised optimal sub-pattern assignment (GOSPA) metric and satisfies

Key concepts

Graph GOSPA Metric Family
This is a set of distance calculations designed to compare two graphs, X and Y, regardless of their size. It works by finding the optimal way to assign nodes from one graph to the other while minimizing a total cost that includes errors in node attributes and mismatches in edges.
Edge Mismatch Error ($e_p(\gamma)$)
This term quantifies how poorly two graphs align at their connections. The proposed family is flexible because it separates this error into three distinct types: assigned-assigned, assigned-unassigned, and unassigned-unassigned mismatches, each with different associated costs.
Linear Programming (LP) Formulation
The complexity of calculating the metric is managed by formulating it as a mathematical optimization problem. The initial complex problem is simplified into a binary quadratic programming (QP), which can then be converted into an integer linear program (ILP). This allows for efficient, tractable computation.

Terminology

Summary

A family of graph metrics for measuring distances between graphs of different sizes is proposed, which generalizes the graph generalised optimal sub-pattern assignment (GOSPA) metric and satisfies metric properties while offering more flexible penalties for edge mismatches than the original GOSPA metric. This work is significant because it provides a principled, mathematically defined framework for comparing graphs of varying sizes, which has implications for classification tasks on real-world datasets.

The gist

A family of graph GOSPA metrics is proposed to compute distances between graphs of different sizes by defining a general form of the graph generalised optimal sub-pattern assignment (GOSPA) metric and proving it satisfies the metric properties.

Metric Properties and Definitions

The paper establishes that the proposed family of metrics is a principled, mathematically defined metric for undirected, unweighted graphs with node attributes. The core definition involves an optimization problem over assignment sets to find the minimum cost across all possible assignments.

  1. The graph GOSPA metric family between two graphs X and Y is defined by minimizing:

  2. A function that includes terms for node attribute errors, the cost of unassigned nodes, and a flexible edge mismatch error term:

  3. The edge mismatch error, denoted as e p(γ), is composed of three types of costs with different hyperparameters: assigned-assigned edge mismatch, assigned-unassigned edge mismatch, and unassigned-unassigned edge mismatch.

Flexibility in Edge Mismatch Penalties

A key contribution is the increased flexibility in penalizing mismatches compared to the original graph GOSPA metric. The family defines three types of edge mismatches, which can have different costs:

(i) assigned-assigned edge mismatch:

This cost is incurred between two assigned nodes if an edge exists in one graph but not the other.

(ii) assigned-unassigned edge mismatch:

This cost arises between one assigned node and an unassigned node.

(iii) unassigned-unassigned edge mismatch:

This cost is incurred if both nodes of the edge being unassigned.

The paper shows that this approach is more flexible than the graph GOSPA metric [19], which considers only two types of mismatches (assigned-assigned and assigned-unassigned) and has half the cost of an assigned-assigned edge mismatch. The family also offers flexibility by adjusting hyperparameters: "By changing c, we can control the penalty for node unassignments, and sensitivity to node attribute errors. We can also adjust ϵ to change the sensitivity to the mismatches in edges. Moreover, by changing β and η, we can change the weight of the penalties of half-assigned edges and unassigned edges in edge mismatch errors."

Tractability via Linear Programming

The complexity of computing this metric family is addressed by showing it can be computed using linear programming (LP).

  1. The graph GOSPA metric family cost admits a decomposition into three parts: localisation errors for assigned nodes, false and missed errors for unassigned nodes, and errors for assigned edges, missed edges, and half-assigned edges.

  2. The problem is first formulated as a binary quadratic programming (QP) problem.

  3. This QP problem can be linearized by introducing an auxiliary variable eˆ to handle the absolute value term in the edge mismatch error function.

  4. The resulting formulation can then be converted into an integer linear program (ILP) using Glover's linearisation method, which is solved efficiently as a tractable approximation to the original metric family.

Experimental Validation and Performance

Simulation experiments and real-world dataset tests demonstrate the effectiveness of the proposed family of metrics.

  1. In simulation results, for random node attribute noise, the graph GOSPA family shows that the localisation errors are too large to assign two nodes to each other, leading to increased errors for missed and false nodes when noise is high.

  2. When comparing against other metrics like MCS distance and GED on real-world datasets (MUTAG, Letter Database, PTC), the graph GOSPA family performs the best in all datasets.

  3. Specifically, it performs better in the Letter-med dataset, indicating that for more complicated tasks, the extra hyperparameters β and η in the graph GOSPA metric family can offer more flexibility to fit the data better.

  4. The computational time analysis shows that while the family is more computationally demanding to calculate than the original GOSPA metric, its relaxed version is considerably faster to compute than the integer version, which takes over 5000 seconds for graphs with 20 nodes.

Conclusion

The paper successfully proposes a family of graph GOSPA metrics that are capable of comparing undirected graphs of different sizes in a clearly interpretable manner, proving they meet metric properties.

Improvements for AI systems

Here are specific improvements for AI systems based on the proposed graph GOSPA metric family:

  1. Improvements in Graph-based Classification and Clustering Tasks: The metric family provides a principled way to measure the discrepancy between graphs of different sizes, including node attributes and edge structures. This allows AI systems to perform more robust comparisons when comparing learned representations (graphs) generated by different models or trained on datasets of varying complexities.

  2. Enhanced Robustness Against Data Noise and Perturbations: The metric explicitly penalizes node attribute errors (localisation errors) and handles various forms of structural changes (edge addition, deletion, node removal). This makes downstream tasks more robust to noise in the input data or variations between different graph instances (e.g., noisy molecular graphs or evolving social network snapshots).

  3. Improved Graph Embedding Comparison: When using graph embedding techniques (like Node2Vec or GNN embeddings) for tasks such as link prediction or node classification, the GOSPA metric family can be used to quantify the distance between embeddings derived from different sub-graph structures or different model architectures. This allows researchers to rigorously compare which structural features are most important for a specific task.

  4. Better Handling of Heterogeneous Graph Data: Since the family is defined for graphs with node attributes, it is highly applicable to heterogeneous graph data (e.g., molecules where nodes are atoms/bonds and have chemical properties). The metric allows for a nuanced weighting of different types of errors (node attribute mismatch vs. edge mismatch), leading to more accurate similarity scores in complex biological or chemical datasets compared to simpler metrics like MCS or basic GED.

  5. Optimized Graph Matching and Sub-pattern Assignment: The core mechanism involves finding the optimal assignment between nodes in two graphs, even when nodes are left unassigned. This capability is crucial for sophisticated graph matching algorithms, enabling AI systems to find the best structural correspondences between two graphs that are not perfectly isomorphic or of the same size.

  6. Efficient Large-Scale Comparison via Linear Programming: The development of a tractable approximation via Linear Programming (LP) allows AI systems to compute these complex graph distances in polynomial time without resorting to computationally expensive NP-hard exact solutions for large graphs. This enables real-time comparison and evaluation of model performance across massive datasets or high-dimensional feature spaces.

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.

Sources

Related papers