A probabilistic approach to learning costs for graph edit distance

Graph edit distance provides an error-tolerant way to measure distances between attributed graphs. The effectiveness of edit distance based graph classification algorithms relies on the adequate definition of edit operation costs. We propose a cost inference method that is based on a distribution estimation of edit operations. For this purpose, we employ an expectation maximization algorithm to learn mixture densities from a labeled sample of graphs and derive edit costs that are subsequently applied in the context of a graph edit distance computation framework. We evaluate the performance of the proposed distance model in comparison to another recently introduced learning model for edit costs.