Self-organizing maps for learning the edit costs in graph matching.
Although graph matching and graph edit distance computation have become areas of intensive research recently, the automatic inference of the cost of edit operations has remained an open problem. In the present paper, we address the issue of learning graph edit distance cost functions for numerically labeled graphs from a corpus of sample graphs. We propose a system of self-organizing maps (SOMs) that represent the distance measuring spaces of node and edge labels. Our learning process is based on the concept of self-organization. It adapts the edit costs in such a way that the similarity of graphs from the same class is increased, whereas the similarity of graphs from different classes decreases. The learning procedure is demonstrated on two different applications involving line drawing graphs and graphs representing diatoms, respectively.
Neuhaus
Michel
M
Department of Computer Science, University of Bern, CH-3012 Bern, Switzerland. mneuhaus@iam.unibe.ch
Bunke
Horst
H
D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003196:Computer Graphics; D003198:Computer Simulation; D017377:Diatoms / Q000166:cytology*; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D008954:Models, Biological; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique