2023/08/23 by Dominic Schuhmacher, Schuhmacher, Dominic, Leoni Carla Wirth +1 · 1 citation
Agricultural and Biological Sciences · Physics and Astronomy · #05C80 #60B10 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Plant and animal studies #Primary 05C99 #Probability (math.PR) #Secondary 60B99
paper · pdf · doi:10.48550/arxiv.2308.12165
openalex publication_date 2023/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We introduce the Graph TT (GTT) and Graph OSPA (GOSPA) metrics based on optimal assignment, which allow us to compare not only the edge structures but also general vertex and edge attributes of graphs of possibly different sizes. We argue that this provides an intuitive and universal way to measure the distance between finite simple attributed graphs. Our paper discusses useful equivalences and inequalities as well as the relation of the new metrics to various existing quantifications of distance between graphs. By deriving a representation of a graph as a pair of point processes, we are able to formulate and study a new type of (finite) random graph convergence and demonstrate its applicability using general point processes of vertices with independent random edges. Computational aspects of the new metrics are studied in the form of an exact and two heuristic algorithms that are derived from previous algorithms for similar tasks. As an application, we perform a statistical test based on the GOSPA metric for functional differences in olfactory neurons of Drosophila flies.