Ferrer, Miquel

Profilbild
E-Mail-Adresse
Geburtsdatum
Projekt
Organisationseinheiten
Berufsbeschreibung
Nachname
Ferrer
Vorname
Miquel
Name
Ferrer, Miquel

Filter

20154

Einstellungen

Suchergebnisse

Gerade angezeigt 1 - 4 von 4
  • Kein Vorschaubild vorhanden
    Publikation
    Approximation of Graph Edit Distance in Quadratic Time
    (05/2015) 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.
    04B - Beitrag Konferenzschrift
  • Kein Vorschaubild vorhanden
    Publikation
    Suboptimal Graph Edit Distance Based on Sorted Local Assignments
    (Springer, 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.
    04B - Beitrag Konferenzschrift
  • Kein Vorschaubild vorhanden
    Publikation
    A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching
    (Springer, 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.
    04B - Beitrag Konferenzschrift
  • Kein Vorschaubild vorhanden
    Publikation
    Building Classifier Ensembles Using Greedy Graph Edit Distance
    (Springer, 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.
    04B - Beitrag Konferenzschrift