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, 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.