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

• URL: http://arxiv.org/abs/2311.07596v2
• Date: Tue, 27 Aug 2024 15:34:43 GMT
• Title: Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
• Authors: Jinhao Gu, Ángel F. García-Fernández, Robert E. Firth, Lennart Svensson,
• Abstract summary: This paper proposes a metric to measure the dissimilarity between graphs that may have a different number of nodes. 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.
• Score: 3.8823562292981393
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Geodesic Distance Between Graphs: A Spectral Metric for Assessing the Stability of Graph Neural Networks [4.110108749051657]
  We introduce a Graph Geodesic Distance (GGD) metric for assessing the generalization and stability of Graph Neural Networks (GNNs) We show that the proposed GGD metric can effectively quantify dissimilarities between two graphs by encapsulating their differences in key structural (spectral) properties. The proposed GGD metric shows significantly improved performance for stability evaluation of GNNs especially when only partial node features are available.
  arXiv  Detail & Related papers  (2024-06-15T04:47:40Z)
• Graph Parsing Networks [64.5041886737007]
  We propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph.
  arXiv  Detail & Related papers  (2024-02-22T09:08:36Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks [54.225220638606814]
  We propose a pseudometric for attributed graphs, the Tree Mover's Distance (TMD), and study its relation to generalization. First, we show that TMD captures properties relevant to graph classification; a simple TMD-SVM performs competitively with standard GNNs. Second, we relate TMD to generalization of GNNs under distribution shifts, and show that it correlates well with performance drop under such shifts.
  arXiv  Detail & Related papers  (2022-10-04T21:03:52Z)
• GEMS: Scene Expansion using Generative Models of Graphs [3.5998698847215165]
  We focus on one such representation, scene graphs, and propose a novel scene expansion task. We first predict a new node and then predict the set of relationships between the newly predicted node and previous nodes in the graph. We conduct extensive experiments on Visual Genome and VRD datasets to evaluate the expanded scene graphs.
  arXiv  Detail & Related papers  (2022-07-08T07:41:28Z)
• Embedding Graphs on Grassmann Manifold [31.42901131602713]
  This paper develops a new graph representation learning scheme, namely EGG, which embeds approximated second-order graph characteristics into a Grassmann manifold. The effectiveness of EGG is demonstrated using both clustering and classification tasks at the node level and graph level.
  arXiv  Detail & Related papers  (2022-05-30T12:56:24Z)
• Approximate Fr\'echet Mean for Data Sets of Sparse Graphs [0.0]
  In this work, we equip a set of graph with the pseudometric matrix defined by the $ell$ norm between the eigenvalues of their respective adjacency. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr'echet mean of a set of undirected unweighted graphs with a fixed size.
  arXiv  Detail & Related papers  (2021-05-10T01:13:25Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  We present an extensive survey of various exact and inexact graph matching techniques. A category of graph matching algorithms is presented, which reduces the graph size by removing the less important nodes. We introduce a novel approach to measure graph similarity using geometric graphs.
  arXiv  Detail & Related papers  (2020-12-30T18:51:06Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.