Deakin University
Browse

File(s) under permanent embargo

Graph edit distance from spectral seriation

Version 2 2024-06-05, 00:33
Version 1 2019-07-18, 12:06
journal contribution
posted on 2024-06-05, 00:33 authored by Antonio Robles-KellyAntonio Robles-Kelly, ER Hancock
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.

History

Journal

IEEE transactions on pattern analysis and machine intelligence

Volume

27

Pagination

365-378

Location

Piscataway, N.J.

ISSN

0162-8828

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2005, IEEE

Issue

3

Publisher

Institute of Electrical and Electronics Engineers