论文标题
几何图的距离度量
Distance Measures for Geometric Graphs
论文作者
论文摘要
几何图是一个组合图，并具有从欧几里得空间中的嵌入中继承的几何形状。在两个几何图形的组合和几何结构中，在组合和几何结构中的（差异）相似性的有意义的表述都是模式识别的一个挑战性问题。我们研究了几何图的距离测量的两个概念，称为几何编辑距离（GED）和几何图距离（GGD）。尽管前者是基于编辑一个图以将其转换为另一个图的想法，但后者的灵感来自图形的不精确匹配。几十年来，这两个概念一直在归因于归因图之间的相似性衡量。但是，如果没有任何修改，它们将无法为几何图提供有意义的距离度量 - 甚至不再是度量标准。我们已经为几何图的上下文策划了它们相关的成本功能。除了研究GED和GGD的度量特性外，我们研究了两个概念的比较。我们通过证明距离为$ \ Mathcal {np} $ - 很难计算，即使图形是平面，并且允许任意成本系数，我们也很难计算GGD的计算方面。
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.
