13.3.8.5 Graph Edit Distance, Tree-Edit Distance

Levenstein, A.,
Binary Codes Capable of Correcting Deletions, Insertions and Reversals,
Soviet Physics-Doklandy(10), 1966. The initial description of edit distance. BibRef 6600

Oommen, B.J.,
Recognition of Noisy Subsequences Using Constrained Edit Distances,
PAMI(9), No. 5, September 1987, pp. 676-685. BibRef 8709
And: Correction: PAMI(10), No. 6, November 1988, pp. 983. String Matching. BibRef

Marzal, A., Vidal, E.,
Computation of normalized edit distance and applications,
PAMI(15), No. 9, September 1993, pp. 926-932.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Vidal, E., Marzal, A., Aibar, P.,
Fast Computation of Normalized Edit Distances,
PAMI(17), No. 9, September 1995, pp. 899-902.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 9509

Marzal, A., Barrachina, S.,
Speeding up the Computation of the Edit Distance for Cyclic Strings,
ICPR00(Vol II: 891-894).
IEEE DOI Link
HTML Version. 0009
BibRef

Peris, G., Marzal, A.,
Fast cyclic edit distance computation with weighted edit costs in classification,
ICPR02(IV: 184-187).
IEEE DOI Link 0211
BibRef

Zhang, K.Z.[Kai-Zhong],
Algorithms for the constrained editing distance between ordered labeled trees and related problems,
PR(28), No. 3, March 1995, pp. 463-474.
WWW Version. 0401
BibRef

Zhang, K.,
A Constrained Edit Distance between Unordered Labeled Trees,
Algorithmica(15), No. 6, 1996, pp. 205-222. BibRef 9600

Bunke, H.,
On A Relation Between Graph Edit Distance and Maximum Common Subgraph,
PRL(18), No. 8, August 1997, pp. 689-694. 9801
BibRef

Lladós, J.[Josep], Martí, E.[Enric], Villanueva, J.J.[Juan José],
Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs,
PAMI(23), No. 10, October 2001, pp. 1137-1143.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0110
Match two RAGs using edit operators. To match with errors in the data. BibRef

Cross, A.D.J.[Andrew D.J.], Myers, R.[Richard], Hancock, E.R.[Edwin R.],
Convergence of a hill-climbing genetic algorithm for graph matching,
PR(33), No. 11, November 2000, pp. 1863-1880.
WWW Version. 0011
BibRef

Myers, R.[Richard], Hancock, E.R.[Edwin R.],
Least-commitment graph matching with genetic algorithms,
PR(34), No. 2, February 2001, pp. 375-394.
WWW Version. 0011
BibRef
Earlier:
Least Commitment Graph Matching by Evolutionary Optimisation,
ECCV00(I: 203-219).
WWW Version. 0003
BibRef

Myers, R.[Richard], Wilson, R.C., Hancock, E.R.,
Bayesian Graph Edit Distance,
PAMI(22), No. 6, June 2000, pp. 628-635.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0008
BibRef
Earlier: CIAP99(1166-1171).
IEEE DOI Link 9909
BibRef
Earlier: A2, A3, A1:
Efficient Relational Matching with Local Edit Distance,
ICPR98(Vol II: 1711-1714).
IEEE DOI Link 9808
BibRef

Robles-Kelly, A.[Antonio], Hancock, E.R.[Edwin R.],
Graph Edit Distance from Spectral Seriation,
PAMI(27), No. 3, March 2005, pp. 365-378.
IEEE Abstract. IEEE Top Reference. 0501
Convert graphs to strings so that string matching may be used. BibRef

Yu, H.[Hang], Hancock, E.R.[Edwin R.],
String Kernels for Matching Seriated Graphs,
ICPR06(IV: 224-228).
WWW Version. 0609
BibRef
Earlier:
Machine Learning with Seriated Graphs,
IbPRIA05(II:155).
Springer DOI Link 0509
BibRef
And:
Eigenspaces from Seriated Graphs,
CAIP05(179).
Springer DOI Link 0509
Graph to string (seriation), then learn structure. BibRef

Torsello, A.[Andrea], Hancock, E.R.[Edwin R.],
Computing approximate tree edit distance using relaxation labeling,
PRL(24), No. 8, May 2003, pp. 1089-1097.
WWW Version. 0304
BibRef
Earlier:
Efficiently Computing Weighted Tree Edit Distance Using Relaxation Labeling,
EMMCVPR01(438-453).
Springer DOI Link 0205
BibRef

Torsello, A.[Andrea], Hancock, E.R.[Edwin R.],
Matching and Embedding through Edit-Union of Trees,
ECCV02(III: 822 ff.).
HTML Version. 0205
tree edit distance for matching tree structures BibRef

Xia, S.P.[Sheng-Ping], Ren, P.[Peng], Hancock, E.R.[Edwin R.],
Ranking the local invariant features for the robust visual saliencies,
ICPR08(1-4).
IEEE DOI Link 0812
BibRef

Xia, S.P.[Sheng-Ping], Hancock, E.R.[Edwin R.],
Graph-Based Object Class Discovery,
CAIP09(385-393).
Springer DOI Link 0909
BibRef
And:
Learning Class Specific Graph Prototypes,
CIAP09(269-277).
Springer DOI Link 0909
BibRef
Earlier:
Clustering Using Class Specific Hyper Graphs,
SSPR08(318-328).
Springer DOI Link 0812
BibRef

Xia, S.P.[Sheng-Ping], Hancock, E.R.[Edwin R.],
Pairwise Similarity Propagation Based Graph Clustering for Scalable Object Indexing and Retrieval,
GbRPR09(184-194).
Springer DOI Link 0905
BibRef
Earlier:
3D Object Recognition Using Hyper-Graphs and Ranked Local Invariant Features,
SSPR08(117-126).
Springer DOI Link 0812
BibRef

Ren, P.[Peng], Aleksic, T.[Tatjana], Wilson, R.C.[Richard C.], Hancock, E.R.[Edwin R.],
Hypergraphs, Characteristic Polynomials and the Ihara Zeta Function,
CAIP09(369-376).
Springer DOI Link 0909
BibRef

Ren, P.[Peng], Wilson, R.C.[Richard C.], Hancock, E.R.[Edwin R.],
Characteristic Polynomial Analysis on Matrix Representations of Graphs,
GbRPR09(243-252).
Springer DOI Link 0905
BibRef

Ren, P.[Peng], Wilson, R.C.[Richard C.], Hancock, E.R.[Edwin R.],
Spectral Embedding of Feature Hypergraphs,
SSPR08(308-317).
Springer DOI Link 0812
BibRef

Ren, P.[Peng], Wilson, R.C.[Richard C.], Hancock, E.R.[Edwin R.],
Pattern vectors from the Ihara zeta function,
ICPR08(1-4).
IEEE DOI Link 0812
BibRef
And:
Graph Characteristics from the Ihara Zeta Function,
SSPR08(257-266).
Springer DOI Link 0812
BibRef

Escolano, F.[Francisco], Giorgi, D.[Daniela], Hancock, E.R.[Edwin R.], Lozano, M.A.[Miguel A.], Falcidieno, B.[Bianca],
Flow Complexity: Fast Polytopal Graph Complexity and 3D Object Clustering,
GbRPR09(253-262).
Springer DOI Link 0905
BibRef

Escolano, F.[Francisco], Hancock, E.R.[Edwin R.], Lozano, M.A.[Miguel A.],
Polytopal Graph Complexity, Matrix Permanents, and Embedding,
SSPR08(237-246).
Springer DOI Link 0812
BibRef

Wei, J.[Jie],
Markov edit distance,
PAMI(26), No. 3, March 2004, pp. 311-321.
IEEE Abstract. IEEE Top Reference. 0402
BibRef

Neuhaus, M.[Michel], Bunke, H.[Horst],
Self-Organizing Maps for Learning the Edit Costs in Graph Matching,
SMC-B(35), No. 3, June 2005, pp. 503-514.
IEEE DOI Link 0508
BibRef
Earlier:
A probabilistic approach to learning costs for graph edit distance,
ICPR04(III: 389-393).
IEEE DOI Link 0409
BibRef

Neuhaus, M.[Michel], Bunke, H.[Horst],
Bridging the Gap Between Graph Edit Distance and Kernel Machines,
World ScientificSeptember 2007. ISBN: 978-981-270-817-5 Survey, Graph Matching. To purchase this book look here BibRef 0709

Neuhaus, M.[Michel], Bunke, H.[Horst],
Edit distance-based kernel functions for structural pattern classification,
PR(39), No. 10, October 2006, pp. 1852-1863.
WWW Version. BibRef 0610
And:
A Convolution Edit Kernel for Error-tolerant Graph Matching,
ICPR06(IV: 220-223).
WWW Version. 0609
BibRef
And:
A Random Walk Kernel Derived from Graph Edit Distance,
SSPR06(191-199).
Springer DOI Link 0608
String matching; Graph matching; Kernel methods; Support vector machine 0606
BibRef

Neuhaus, M.[Michel], Bunke, H.[Horst],
Graph-Based Multiple Classifier Systems A Data Level Fusion Approach,
CIAP05(479-486).
Springer DOI Link 0509
BibRef

Neuhaus, M.[Michel], Bunke, H.[Horst],
A Quadratic Programming Approach to the Graph Edit Distance Problem,
GbRPR07(92-102).
Springer DOI Link 0706
BibRef

Riesen, K.[Kaspar], Bunke, H.[Horst],
Approximate graph edit distance computation by means of bipartite graph matching,
IVC(27), No. 7, 4 June 2009, pp. 950-959.
Elsevier DOI Link
WWW Version. 0904
Graph based representation; Graph edit distance; Bipartite graph matching BibRef

Riesen, K.[Kaspar], Bunke, H.[Horst],
Feature Ranking Algorithms for Improving Classification of Vector Space Embedded Graphs,
CAIP09(377-384).
Springer DOI Link 0909
BibRef

Riesen, K.[Kaspar], Neuhaus, M.[Michel], Bunke, H.[Horst],
Bipartite Graph Matching for Computing the Edit Distance of Graphs,
GbRPR07(1-12).
Springer DOI Link 0706
BibRef
Earlier: A2, A1, A3:
Fast Suboptimal Algorithms for the Computation of Graph Edit Distance,
SSPR06(163-172).
Springer DOI Link 0608
BibRef

Justice, D.[Derek], Hero, A.[Alfred],
A Binary Linear Programming Formulation of the Graph Edit Distance,
PAMI(28), No. 8, August 2006, pp. 1200-1214.
IEEE DOI Link 0606
Use for comparing graphs. BibRef

Li, Y.J.[Yu-Jian], Bo, L.[Liu],
A Normalized Levenshtein Distance Metric,
PAMI(29), No. 6, June 2007, pp. 1091-1095.
IEEE DOI Link 0704
Normalized edit distance, especially for strings. BibRef

Bille, P.,
A survey on tree edit distance and related problems,
TCS(337), No. 1-3, 2005, pp. 217-239.
Elsevier DOI Link Survey, Tree Edit. BibRef 0500

Bernard, M.[Marc], Boyer, L.[Laurent], Habrard, A.[Amaury], Sebban, M.[Marc],
Learning probabilistic models of tree edit distance,
PR(41), No. 8, August 2008, pp. 2611-2629.
WWW Version. 0805
Tree edit distance; EM algorithm; Generative model; Discriminative model BibRef

Gao, X.B.[Xin-Bo], Xiao, B.[Bing], Tao, D.C.[Da-Cheng], Li, X.L.[Xue-Long],
Image categorization: Graph edit distance+edge direction histogram,
PR(41), No. 10, October 2008, pp. 3179-3191.
WWW Version. 0808
Inexact graph matching; Graph edit distance (GED); Edge direction histogram (EDH); Earth mover's distance (EMD); Image categorization BibRef

Chairunnanda, P.[Prima], Gopalkrishnan, V.[Vivekanand], Chen, L.[Lei],
Enhancing Edit Distance on Real Sequences Filters using Histogram Distance on Fixed Reference Ordering,
ICPR06(III: 582-585).
WWW Version. 0609
BibRef

Olsen, O.F.[Ole Fogh],
Tree Edit Distances from Singularity Theory,
ScaleSpace05(316-326).
WWW Version. 0505
BibRef

Weigel, A., Jäger, T., Pies, A.,
Estimation of Probabilities for Edit Operations,
ICPR00(Vol II: 777-780).
IEEE DOI Link
HTML Version. 0009
BibRef

Weigel, A.[Achim], and Agne, S.[Stefan],
Learning the Cost of Edit Operations for Edit Distances,
SCIA97(xx-yy) 9705

HTML Version. BibRef

Bunke, H.[Horst],
Edit Distance of Regular Languages,
SDAIR96(XX) University of Bern. BibRef 9600

Weigel, A., Fein, F.,
Normalizing the weighted edit distance,
ICPR94(B:399-402).
IEEE DOI Link 9410
BibRef

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Linear Prediction Techniques .