Graph Mover's Distance: An Efficiently Computable Distance Measure for Geometric Graphs

• URL: http://arxiv.org/abs/2306.02133v1
• Date: Sat, 3 Jun 2023 15:06:12 GMT
• Title: Graph Mover's Distance: An Efficiently Computable Distance Measure for Geometric Graphs
• Authors: Sushovan Majhi
• Abstract summary: The geometric graph distance (GGD) has recently been studied as a meaningful measure of similarity between two geometric graphs. We propose in this paper the Graph Mover's Distance (GMD) which has been formulated as an instance of the earth mover's distance.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many applications in pattern recognition represent patterns as a geometric graph. The geometric graph distance (GGD) has recently been studied as a meaningful measure of similarity between two geometric graphs. Since computing the GGD is known to be $\mathcal{NP}$-hard, the distance measure proves an impractical choice for applications. As a computationally tractable alternative, we propose in this paper the Graph Mover's Distance (GMD), which has been formulated as an instance of the earth mover's distance. The computation of the GMD between two geometric graphs with at most $n$ vertices takes only $O(n^3)$-time. Alongside studying the metric properties of the GMD, we investigate the stability of the GGD and GMD. The GMD also demonstrates extremely promising empirical evidence at recognizing letter drawings from the {\tt LETTER} dataset \cite{da_vitoria_lobo_iam_2008}.

Related papers

• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening [19.09507367362567]
  This work studies graph coarsening from a different perspective, developing a theory for preserving graph distances. The geometric approach is useful when working with a collection of graphs, such as in graph classification and regression. Minimizing this difference can be done using the popular weighted kernel $K$-means method.
  arXiv  Detail & Related papers  (2023-06-15T04:47:26Z)
• 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)
• Distance Measures for Geometric Graphs [0.0]
  We study two notions of distance measures for geometric graphs, called the geometric edit distance (GED) and geometric graph distance (GGD) GED is based on the idea of editing one graph to transform it into the other graph, while GGD is inspired by inexact matching of the graphs. We show that GGD is $mathcalNP$-hard to compute, even if the distance is $mathcalNP$-hard to compute.
  arXiv  Detail & Related papers  (2022-09-26T17:35:29Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• PolarMOT: How Far Can Geometric Relations Take Us in 3D Multi-Object Tracking? [62.997667081978825]
  We encode 3D detections as nodes in a graph, where spatial and temporal pairwise relations among objects are encoded via localized polar coordinates on graph edges. This allows our graph neural network to learn to effectively encode temporal and spatial interactions. We establish a new state-of-the-art on nuScenes dataset and, more importantly, show that our method, PolarMOT, generalizes remarkably well across different locations.
  arXiv  Detail & Related papers  (2022-08-03T10:06:56Z)
• E-Graph: Minimal Solution for Rigid Rotation with Extensibility Graphs [61.552125054227595]
  A new minimal solution is proposed to solve relative rotation estimation between two images without overlapping areas. Based on E-Graph, the rotation estimation problem becomes simpler and more elegant. We embed our rotation estimation strategy into a complete camera tracking and mapping system which obtains 6-DoF camera poses and a dense 3D mesh model.
  arXiv  Detail & Related papers  (2022-07-20T16:11:48Z)
• Multiscale Graph Comparison via the Embedded Laplacian Distance [6.09170287691728]
  We propose the Embedded Laplacian Distance (ELD) for comparing graphs of vastly different sizes. Our approach first projects the graphs onto a common, low-dimensional Laplacian embedding space that respects graphical structure. A distance can then be computed efficiently via a natural sliced Wasserstein approach.
  arXiv  Detail & Related papers  (2022-01-28T12:13:08Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Distance-Geometric Graph Convolutional Network (DG-GCN) for Three-Dimensional (3D) Graphs [0.8722210937404288]
  We propose a message-passing graph convolutional network based on the distance-geometric graph representation: DG-GCN. It enables learning of filter weights from distances, thereby incorporating the geometry of 3D graphs in graph convolutions. Our work demonstrates the utility and value of DG-GCN for end-to-end deep learning on 3D graphs, particularly molecular graphs.
  arXiv  Detail & Related papers  (2020-07-06T15:20:52Z)
• Geometric Graph Representations and Geometric Graph Convolutions for Deep Learning on Three-Dimensional (3D) Graphs [0.8722210937404288]
  The geometry of three-dimensional (3D) graphs, consisting of nodes and edges, plays a crucial role in many important applications. We define three types of geometric graph representations: positional, angle-geometric and distance-geometric. For proof of concept, we use the distance-geometric graph representation for geometric graph convolutions. The results of geometric graph convolutions, for the ESOL and Freesol datasets, show significant improvement over those of standard graph convolutions.
  arXiv  Detail & Related papers  (2020-06-02T17:08: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.