Institut für Wirtschaftsinformatik
Dauerhafte URI für die Sammlunghttps://irf.fhnw.ch/handle/11654/66
Listen
44 Ergebnisse
Ergebnisse nach Hochschule und Institut
Publikation On the impact of using utilities rather than costs for graph matching(Springer, 09.11.2019) Riesen, Kaspar; Bunke, Horst; Fischer, AndreasThe concept of graph edit distance constitutes one of the most flexible graph matching paradigms available. The major drawback of graph edit distance, viz. the exponential time complexity, has been recently overcome by means of a reformulation of the edit distance problem to a linear sum assignment problem. However, the substantial speed up of the matching is also accompanied by an approximation error on the distances. Major contribution of this paper is the introduction of a transformation process in order to convert the underlying cost model into a utility model. The benefit of this transformation is that it enables the integration of additional information in the assignment process.We empirically confirm the positive effects of this transformation on five benchmark graph sets with respect to the accuracy and run time of a distance based classifier.01A - Beitrag in wissenschaftlicher ZeitschriftPublikation Approximate graph edit distance in quadratic time(IEEE, 2020) Riesen, Kaspar; Ferrer, Miquel; Bunke, HorstGraph 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 ZeitschriftPublikation Novel Kernels for Error-tolerant Graph Classification(Brill, 2009) Riesen, Kaspar; Bunke, Horst; Neuhaus, Michel01A - Beitrag in wissenschaftlicher ZeitschriftPublikation Non-linear Transformations of Vector Space embedded Graphs(2008) Riesen, Kaspar; Bunke, Horst; Juan-Ciscar, Alfons; Sanchez, Gemma04B - Beitrag KonferenzschriftPublikation Graph Classification by means of Lipschitz Embedding(IEEE, 2009) Riesen, Kaspar; Bunke, Horst01A - Beitrag in wissenschaftlicher ZeitschriftPublikation Feature Ranking Algorithms for Improving Classification of Vector Space Embedded Grahps(Springer, 2009) Bunke, Horst; Riesen, Kaspar; Jiang, Xiaoyi; Petkov, Nicolai04B - Beitrag KonferenzschriftPublikation Graph Edit Distance - Optimal and Suboptimal Algorithms with Applications(Wiley, 2009) Bunke, Horst; Riesen, Kaspar04B - Beitrag KonferenzschriftPublikation Reducing the Dimensionality of Vector Space Embedding of Graphs(2007) Riesen, Kaspar; Kilchherr, Vivian; Bunke, Horst04B - Beitrag KonferenzschriftPublikation On Lipschitz Embeddings of Graphs(Springer, 2008) Riesen, Kaspar; Bunke, Horst; Lovrek, Ignac; Howlett, Robert J.; Jain, Lakhmi C.04B - Beitrag KonferenzschriftPublikation Efficient Suboptimal Graph Isomorphism(Springer, 2009) Riesen, Kaspar; Fankhauser, Stefan; Bunke, Horst; Dickinson, Peter J; Torsello, Andrea; Escolano, Francisco; Brun, Luc04B - Beitrag Konferenzschrift