A generic framework for median graph computation based on a recursive embedding approach |
| |
| Authors: | M. Ferrer D. Karatzas E. Valveny I. Bardaji H. Bunke |
| |
| Affiliation: | 1. Institut de Robòtica i Informàtica Industrial, CSIC-UPC, C.Llorens Artigas 4-6, 2a planta, 08028 Barcelona, Spain;2. Centre de Visió per Computador, Departament de Ciències de la Computació, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain;3. Institute of Computer Science and Applied Mathematics, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland;1. University of York, UK;2. Universitá Ca’ Foscari Venezia, Italy;3. University of Alicante, Spain;4. GREYC, CNRS UMR 6072, ENSICAEN, France;1. University of South Australia, Advanced Computing Centre, Adelaide, SA, Australia;2. Defence Science and Technology Organisation, Adelaide, SA, Australia;1. Hanken School of Economics, P.O. Box 287, Handelsesplanaden 2, 65101 Vasa, Finland;2. Fairfield University, 1073 North Benson Road, 06824 Fairfield, CT, USA;1. College of Computer and Control Engineering, Nankai University, Tianjin 300071, PR China;2. Institute for Bioinformatics and Translational Research, UMIT, Hall in Tyrol, Austria;3. Department of Computer Science, Universität der Bundeswehr München, Werner-Heisenberg-Weg 39, 85577 Neubiberg, Germany;4. Computational Biology and Machine Learning Laboratory, Center for Cancer Research and Cell Biology, School of Medicine, Dentistry and Biomedical Sciences, Faculty of Medicine, Health and Life Sciences, Queen’s University Belfast, Belfast, UK;5. Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, PR China;1. Department of Mathematics-Computer Sciences, Faculty of Science, Necmettin Erbakan University, Meram Yeniyol, 42100 Konya, Turkey;2. Department of Mathematics, Sungkyunkwan University, Suwon 440-746, Republic of Korea;3. Department of Mathematics, Faculty of Science, Selçuk University, Campus, 42075 Konya, Turkey |
| |
| Abstract: | The median graph has been shown to be a good choice to obtain a representative of a set of graphs. However, its computation is a complex problem. Recently, graph embedding into vector spaces has been proposed to obtain approximations of the median graph. The problem with such an approach is how to go from a point in the vector space back to a graph in the graph space. The main contribution of this paper is the generalization of this previous method, proposing a generic recursive procedure that permits to recover the graph corresponding to a point in the vector space, introducing only the amount of approximation inherent to the use of graph matching algorithms. In order to evaluate the proposed method, we compare it with the set median and with the other state-of-the-art embedding-based methods for the median graph computation. The experiments are carried out using four different databases (one semi-artificial and three containing real-world data). Results show that with the proposed approach we can obtain better medians, in terms of the sum of distances to the training graphs, than with the previous existing methods. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
