Pattern Recognition with Graphs and Trees

Richard Wilson

(University of York)

Relational representations arise naturally from some types of data. They can also be used as an alternative representation of more traditional problems. These representations can be captured by graphs. Graph data provides some interesting and difficult challenges to the traditional pattern recognition model. In this talk I will survey more than a decade of research at York aimed at addressing some of this problems.
Starting from a standard model of recognition, I will highlight some of the particular challenges and some of the various approaches. I will begin by discussing the problem of comparing graphs via alignment and explain some optimisation-based approaches using graph deconstruction. I will then talk about the feasibility of extracting useful features directly from graphs without the need for alignment. Here spectral methods are an invaluable tool for finding descriptors which are invariant to graph order and be used as graph features. Finally, generative models are an important tool in machine learning. Recent work at York has investigated the use of generative models of graph structure. I will present a number of possible generative models for graphs and explain their use of different graph data.
Tuesday 10th March 2009, 14:00
Robert Recorde Room
Department of Computer Science