Recent Advances in Graph Based Pattern Recognition
Horst Bunke
Professor
University of Bern, Switzerland
Abstract :
The discipline of pattern recognition is traditionally divided into the statistical and the structural approach. Statistical pattern recognition is characterized by representing objects by means of feature vectors, while the structural approach uses symbolic data structures, such as strings, trees, and graphs. In the current talk we mainly focus on graphs for object representation. When comparing graph representations with feature vectors, one notices an increased flexibility provided by graphs in the sense that not only unary properties of objects can be represented, but also higher-dimensional relationships. On the other hand, the domain of graphs exhibits only little mathematical structure and consequently, there is a lack of suitable methods for graph classification, clustering, and related tasks.
In this talk, we review some advances in the field of graph-based pattern recognition. The main focus will be on work conducted at the University of Bern in recent years. A general approach to transforming graphs into n-dimensional real vectors by means of graph dissimilarity will be described. This approach makes all algorithmic tools originally developed for feature vectors instantly available to graphs. In particular, it leads to a novel family of graph kernels. Moreover, the embedding procedure allows one to generate, in a straightforward way, systems for classification and clustering that involve multiple experts. With various experimental results we prove the robustness and flexibility of this new approach and show that it outperforms standard graph classification and clustering methods on several graph data sets of diverse nature. In order to address computational complexity problems, we also describe novel algorithms for the efficient computation of graph dissimilarity in an approximate way. It will be shown that these algorithms can substantially reduce computation time while maintaining a high accuracy of the underlying classification algorithms.
Bio:
Horst Bunke is a professor of Computer Science at the University of Bern, Switzerland. From 1998 to 2000 he served as the 1st Vice-President of the International Association for Pattern Recognition (IAPR) and in 2000 he was Acting President of IAPR. Horst Bunke is a Fellow of the IAPR, former Editor-in-Charge of the International Journal of Pattern Recognition and Artificial Intelligence, Editor-in-Chief of the journal Electronic Letters of Computer Vision and Image Analysis, Editor-in-Chief of the book series on Machine Perception and Artificial Intelligence by World Scientific Publ. Co., Advisory Editor of Pattern Recognition, Associate Editor of Acta Cybernetica and Frontiers of Computer Science in China, and former Associate Editor of the International Journal of Document Analysis and Recognition, and Pattern Analysis and Applications.
Horst Bunke is the recipient of the 2010 KS Fu Prize, awarded by the IAPR. Moreover, he received the IAPR/ICDAR Outstanding Achievements Award in 2009 and an honorary doctor degree from the University of Szeged, Hungary, in 2007. He held visiting positions at the Chinese Academy of Science, Beijing(1987), the IBM Los Angeles Scientific Center (1989), the University of Szeged, Hungary (1991), the University of South Florida at Tampa (1991, 1996, 1998-2007), the University of Nevada at Las Vegas (1994), Kagawa University, Takamatsu, Japan (1995), Curtin University, Perth, Australia (1999), Australian National University, Canberra (2005), Autonomous University, Barcelona (2005), and NICTA, Brisbane (2009). Horst Bunke has more than 650 publications, including over 40 authored, co-authored, edited or co-edited books and special editions of journals. His h-index is 44, as determined by Google Scholar and harzing.com software. In the DBLP Computer Science Bibliography, which captures more than 1.4 million papers from the whole discipline of Computer Science, Horst Bunke ranks among the 60 most prolific authors in the Computer Science community.