We are concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that it lacks the formality and rigour of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that standard string edit distance techniques can be used. To do this we use graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We pose the problem of graph-matching as maximum a posteriori probability alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression for the edit costs. We compute the edit distance by finding the sequence of string edit operations, which minimise the cost of the path traversing the edit lattice. The edit costs are defined in terms of the a posteriori probability of visiting a site on the lattice. We demonstrate the method with results on a data-set of Delaunay graphs.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Edit distance from graph spectra


    Contributors:
    Robles-Kelly, (author) / Hancock, (author)


    Publication date :

    2003-01-01


    Size :

    677988 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Edit Distance from Graph Spectra

    Robles-Kelly, A. / Hancock, E. / IEEE | British Library Conference Proceedings | 2003


    Bayesian Graph Edit Distance

    Myers, R. / Wilson, R. / Hancock, E. et al. | British Library Conference Proceedings | 1999


    Travel-Activity Patterns Identification Using Graph Edit Distance

    Tran, Yen / Hashimoto, Naohisa / Ando, Takafumi et al. | IEEE | 2023


    Approximate graph edit distance computation by means of bipartite graph matching

    Riesen, K. / Bunke, H. | British Library Online Contents | 2009


    Computation of graph edit distance: Reasoning about optimality and speed-up

    Serratosa, F. | British Library Online Contents | 2015