Auflistung nach Autor:in "Bunke, Horst"

Gerade angezeigt 1 - 20 von 52

A Family of Novel Graph Kernels for Structural Pattern Recognition
(Springer, 2007) Bunke, Horst; Riesen, Kaspar; Rueda, Luis; Mery, Domingo; Kittler, Josef
04B - Beitrag Konferenzschrift
A Fast Matching Algorithm for Graph-Based Handwriting Recognition
(2013) Fischer, Andreas; Frinken, Volkmar; Riesen, Kaspar; Bunke, Horst; Suen, Ching Y.; Haxhimusa, Yll; Jiang, Xiaoyi; Artner, Nicole M.; Kropatsch, Walter G.
04B - Beitrag Konferenzschrift
A Novel Software Toolkit for Graph Edit Distance Computation
(17.05.2013) Riesen, Kaspar; Emmenegger, Sandro; Bunke, Horst
04B - Beitrag Konferenzschrift
An Approximate Algorithm for Median Graph Computation using Graph Embedding
(2008) Ferrer, Miguel; Valveny, Ernest; Serratosa, Francesco; Riesen, Kaspar; Bunke, Horst
04B - Beitrag Konferenzschrift
An Experimental Study of Graph Classification using Prototype Selection
(2008) Fischer, Andreas; Riesen, Kaspar; Bunke, Horst
04B - Beitrag Konferenzschrift
Approximate Graph Edit Distance Computation by means of Bipartite Graph Matching
(Elsevier, 2009) Riesen, Kaspar; Bunke, Horst
01A - Beitrag in wissenschaftlicher Zeitschrift
Approximate graph edit distance in quadratic time
(IEEE, 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.
01A - Beitrag in wissenschaftlicher Zeitschrift
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
Bipartite Graph Matching for Computing the Edit Distance of Graphs
(2007) Riesen, Kaspar; Neuhaus, Michel; Bunke, Horst; Escolano, Francisco; Vento, Mario
04B - Beitrag Konferenzschrift
Classification and Clustering of Vector Space Embedded Graphs
(2011) Riesen, Kaspar; Bunke, Horst
04A - Beitrag Sammelband
Classification and Clustering of Vector Space Embedded Graphs. Series in Machine Perception and Artificial Intelligence
(World Scientific, 2010) Riesen, Kaspar; Bunke, Horst
02 - Monographie
Classifier Ensembles for Vector Space Embedding of Graphs
(2007) Riesen, Kaspar; Bunke, Horst
04B - Beitrag Konferenzschrift
Combining Bipartite Graph Matching and Beam Search for Graph Edit Distance Approximation
(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, Cheng
Graph edit distance (GED) is a powerful and flexible graph dissimilarity model. Yet, exact computation of GED is an instance of a quadratic assignment problem and can thus be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, the primary optimization process of this approximation framework is able to consider local edge structures only, and thus, the observed speed up is at the expense of approximative, rather than exact, distance values. In order to improve the overall approximation quality, the present paper combines the original approximation framework with a fast tree search procedure. More precisely, we regard the assignment from the original approximation as a starting point for a subsequent beam search. In an experimental evaluation on three real world data sets a substantial gain of assignment accuracy can be observed while the run time remains remarkable low.
04B - Beitrag Konferenzschrift
Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time
(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, Cheng
Exact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.
04B - Beitrag Konferenzschrift
Discriminative Prototype Selection Methods for Graph Embedding
(2013) Riesen, Kaspar; Bunke, Horst; Borzeshi, Ehsan Zare; Piccardi, Massimo
01A - Beitrag in wissenschaftlicher Zeitschrift
Dissimilarity based Vector Space Embedding of Graphs using Prototype Reduction Schemes
(Springer, 2009) Riesen, Kaspar; Bunke, Horst; Perner, Petra
04B - Beitrag Konferenzschrift
Efficient Suboptimal Graph Isomorphism
(Springer, 2009) Riesen, Kaspar; Fankhauser, Stefan; Bunke, Horst; Dickinson, Peter J; Torsello, Andrea; Escolano, Francisco; Brun, Luc
04B - Beitrag Konferenzschrift
Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations
(World Scientific, 02.03.2015) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst
The concept of graph edit distance (GED) is still one of the most flexible and powerful graph matching approaches available. Yet, exact computation of GED can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, this approach considers local — rather than the global — structural properties of the graphs only, and thus GED derived from the optimal node assignment generally overestimates the true edit distance. Recently, it has been shown how the existing approximation framework can be exploited to additionally derive a lower bound of the exact edit distance without any additional computations. In this paper we make use of regression analysis in order to predict the exact GED using these two bounds. In an experimental evaluation on diverse graph data sets we empirically verify the gain of distance accuracy of the estimated GEDs compared to both bounds.
01A - Beitrag in wissenschaftlicher Zeitschrift
Exact and Inexact Graph Matching: Methodology and Applications
(Springer, 2010) Riesen, Kaspar; Jiang, Xiaoyi; Bunke, Horst; Aggarwal, Charu C.; Wang, Haixun
04A - Beitrag Sammelband
Fast Suboptimal Algorithms for the Computation of Graph Edit Distance
(2006) Neuhaus, Michel; Riesen, Kaspar; Bunke, Horst; Yeung, Dit-Yan; Kwok, James T.; Fred, Ana; Roli, Fabio; de Ridder, Dick
04B - Beitrag Konferenzschrift