Robles-Kelly A, Hancock E R
IEEE Trans Pattern Anal Mach Intell. 2005 Mar;27(3):365-378. doi: 10.1109/TPAMI.2005.56.
This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.
本文关注于计算图编辑距离。对现有计算图编辑距离方法的一种批评是，它们缺乏字符串编辑距离计算中的一些形式化和严谨性。因此，我们的目标是将图转换为字符串序列，以便能够使用字符串匹配技术。为此，我们使用一种图谱序列化方法将邻接矩阵转换为字符串或序列顺序。我们展示了如何使用图邻接矩阵的主特征向量来建立序列排序。我们将图匹配问题作为图对的序列化序列的最大后验概率（MAP）对齐。这种处理导致了一种表达式，其中编辑成本是后验序列对齐概率的负对数。我们通过找到使遍历编辑格的路径成本最小化的字符串编辑操作序列来计算编辑距离。编辑成本由邻接矩阵的主特征向量的分量以及被匹配图的边密度决定。我们在一些图聚类问题上展示了编辑距离的效用。
