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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Edit distance from graph spectra


    Beteiligte:
    Robles-Kelly, (Autor:in) / Hancock, (Autor:in)


    Erscheinungsdatum :

    01.01.2003


    Format / Umfang :

    677988 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    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


    Bayesian graph edit distance

    Myers, R. / Wilson, R.C. / Hancock, E.R. | IEEE | 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