Distance Measures for Geometric Graphs

• URL: http://arxiv.org/abs/2209.12869v1
• Date: Mon, 26 Sep 2022 17:35:29 GMT
• Title: Distance Measures for Geometric Graphs
• Authors: Sushovan Majhi and Carola Wenk
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A geometric graph is a combinatorial graph, endowed with a geometry that is inherited from its embedding in a Euclidean space. Formulation of a meaningful measure of (dis-)similarity in both the combinatorial and geometric structures of two such geometric graphs is a challenging problem in pattern recognition. We study two notions of distance measures for geometric graphs, called the geometric edit distance (GED) and geometric graph distance (GGD). While the former is based on the idea of editing one graph to transform it into the other graph, the latter is inspired by inexact matching of the graphs. For decades, both notions have been lending themselves well as measures of similarity between attributed graphs. If used without any modification, however, they fail to provide a meaningful distance measure for geometric graphs -- even cease to be a metric. We have curated their associated cost functions for the context of geometric graphs. Alongside studying the metric properties of GED and GGD, we investigate how the two notions compare. We further our understanding of the computational aspects of GGD by showing that the distance is $\mathcal{NP}$-hard to compute, even if the graphs are planar and arbitrary cost coefficients are allowed.

Related papers

• A Survey of Geometric Graph Neural Networks: Data Structures, Models and Applications [67.33002207179923]
  This paper presents a survey of data structures, models, and applications related to geometric GNNs. We provide a unified view of existing models from the geometric message passing perspective. We also summarize the applications as well as the related datasets to facilitate later research for methodology development and experimental evaluation.
  arXiv  Detail & Related papers  (2024-03-01T12:13:04Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words. A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
  arXiv  Detail & Related papers  (2024-02-04T12:29:40Z)
• 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 Mover's Distance: An Efficiently Computable Distance Measure for Geometric Graphs [0.0]
  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.
  arXiv  Detail & Related papers  (2023-06-03T15:06:12Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections [57.60094385551773]
  We propose a trainable framework for learning a deformable 3D geometry model from inhomogeneous image collections. We in addition obtain the underlying 3D geometry of the objects depicted in the 2D images.
  arXiv  Detail & Related papers  (2021-03-31T17:25:36Z)
• 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)
• 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)
• 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.