2020, Riesen, Kaspar, Ferrer, Miquel, Bunke, Horst

Graph edit distance is one of the most flexible and general graph matching models available. The major drawback of graph edit distance, however, is its computational complexity that restricts its applicability to graphs of rather small size. Recently, the authors of the present paper introduced a general approximation framework for the graph edit distance problem. The basic idea of this specific algorithm is to first compute an optimal assignment of independent local graph structures (including substitutions, deletions, and insertions of nodes and edges). This optimal assignment is complete and consistent with respect to the involved nodes of both graphs and can thus be used to instantly derive an admissible (yet suboptimal) solution for the original graph edit distance problem in Ο(n³) time. For large scale graphs or graph sets, however, the cubic time complexity may still be too high. Therefore, we propose to use suboptimal algorithms with quadratic rather than cubic time for solving the basic assignment problem. In particular, the present paper introduces five different greedy assignment algorithms in the context of graph edit distance approximation. In an experimental evaluation, we show that these methods have great potential for further speeding up the computation of graph edit distance while the approximated distances remain sufficiently accurate for graph based pattern classification.

2015, Riesen, Kaspar, Ferrer, Miquel, Fischer, Andreas

Classifier ensembles aim at more accurate classifications than single classifiers. In the present paper we introduce a general approach to building structural classifier ensembles, i.e. classifiers that make use of graphs as representation formalism. The proposed methodology is based on a recent graph edit distance approximation. The major observation that motivates the use of this particular approximation is that the resulting distances crucially depend on the order of the nodes of the underlying graphs. Our novel methodology randomly permutes the node order N times such that the procedure leads to N different distance approximations. Next, a distance based classifier is trained for each approximation and the results of the individual classifiers are combined in an appropriate way. In several experimental evaluations we make investigations on the classification accuracy of the resulting classifier ensemble and compare it with two single classifier systems.

2015-05, Riesen, Kaspar, Ferrer, Miquel, Fischer, Andreas, Bunke, Horst

The basic idea of a recent graph matching framework is to reduce the problem of graph edit distance (GED) to an instance of a linear sum assignment problem (LSAP). The optimal solution for this simplified GED problem can be computed in cubic time and is eventually used to derive a suboptimal solution for the original GED problem. Yet, for large scale graphs and/or large scale graph sets the cubic time complexity remains a severe handicap of this procedure. Therefore, we propose to use suboptimal algorithms – with quadratic rather than cubic time complexity – for solving the underlying LSAP. In particular, we introduce several greedy assignment algorithms for approximating GED. In an experimental evaluation we show that there is great potential for further speeding up the GED computation. Moreover, we empirically confirm that the distances obtained by this procedure remain sufficiently accurate for graph based pattern classification.

2015, Ferrer, Miquel, Serratosa, Francesco, Riesen, Kaspar, Liu, Cheng-Lin, Luo, Bin, Kropatsch, Walter G., Cheng, Yian

In recent years, a powerful approximation framework for graph edit distance computation has been introduced. This particular approximation is based on an optimal assignment of local graph structures which can be established in polynomial time. However, as this approach considers the local structural properties of the graphs only, it yields sub-optimal solutions that overestimate the true edit distance in general. Recently, several attempts for reducing this overestimation have been made. The present paper is a starting point towards the study of sophisticated heuristics that can be integrated in these reduction strategies. These heuristics aim at further improving the overall distance quality while keeping the low computation time of the approximation framework. We propose an iterative version of one of the existing improvement strategies. An experimental evaluation clearly shows that there is large space for further substantial reductions of the overestimation in the existing approximation Framework.

2015, Riesen, Kaspar, Ferrer, Miquel, Bunke, Horst, Schwenker, Friedhelm, Roli, Fabio, Kittler, Joseph

Graph based pattern representation offers a number of useful properties. In particular, graphs can adapt their size and complexity to the actual pattern, and moreover, graphs are able to describe structural relations that might exist within a pattern. Yet, the high representational power and flexibility of graphs is accompanied by a significant increase of the complexity of many algorithms. For instance, exact computation of pairwise graph distance can be accomplished in exponential time complexity only. A previously introduced approximation framework reduces the problem of graph distance computation to an instance of a linear sum assignment problem. This allows suboptimal graph distance computation in cubic time. The present paper introduces a novel procedure, which is conceptually related to this previous approach, but offers O(n2log(n2)) (rather than cubic) run time. We empirically verify the speed up of our novel approximation and show that the faster approximation is able to keep up with the existing framework with respect to distance accuracy.

2011, Fankhauser, Stefan, Riesen, Kaspar, Bunke, Horst, Jiang, Xiaoyi, Ferrer, Miquel, Torsello, Andrea