论文标题
使用平均分支距离比较嵌入式图
Comparing Embedded Graphs Using Average Branching Distance
论文作者
论文摘要
在平面中绘制的图形无处不在，这是由数据集引起的，这些方法包括从GIS分析到图像分类再到形状分析的多种方法。这种类型的数据中的一个基本问题是比较：给定一组这样的图表，我们可以对它们的几何形状“形状”在平面中捕获它们的几何形状？在本文中，我们通过简化的组合表示形式探讨了一种比较两个这样的嵌入式图的方法，称为无尾合并树，该图基于固定方向编码结构。首先，我们检查了旨在比较称为分支距离的合并树的距离的属性，并表明先前工作中定义的距离无法满足度量的某些要求。我们将其纳入一个称为平均分支距离的新距离函数中，以通过查看通过许多方向定义的合并树的分支距离来比较图。尽管存在理论上的问题，但我们表明，通过使用我们的开源代码将嵌入式图的数据集用于实践中，该定义仍然非常有用。
Graphs drawn in the plane are ubiquitous, arising from data sets through a variety of methods ranging from GIS analysis to image classification to shape analysis. A fundamental problem in this type of data is comparison: given a set of such graphs, can we rank how similar they are, in such a way that we capture their geometric "shape" in the plane? In this paper we explore a method to compare two such embedded graphs, via a simplified combinatorial representation called a tail-less merge tree which encodes the structure based on a fixed direction. First, we examine the properties of a distance designed to compare merge trees called the branching distance, and show that the distance as defined in previous work fails to satisfy some of the requirements of a metric. We incorporate this into a new distance function called average branching distance to compare graphs by looking at the branching distance for merge trees defined over many directions. Despite the theoretical issues, we show that the definition is still quite useful in practice by using our open-source code to cluster data sets of embedded graphs.
