About Graph Similarity and Applications

Speaker: Dr. Paul Van Dooren

We present the notion of similarity matrix between two graphs GA and GB as the matrix S whose element Sij measures the similarity of node i in graph GA and node j in graph GB. This matrix can be obtained as a solution of the matrix equation pS=ASB' + A'SB, where A and B are the adjacency matrices of the two graphs. We then show how to construct low rank approximations of this matrix for large scale graphs. This amounts to an optimization algorithm on isometries, and we describe a fixed point algorithm to solve this optimization problem. We give variants of this problem and describe a number of applications.


Paul M. Van Dooren received the engineering degree in computer science and the doctoral degree in applied sciences, both from the Katholieke Universiteit te Leuven, Belgium, in 1974 and 1979, respectively. He held research and teaching positions at the Katholieke Universiteit te Leuven (1974-1979), the University of Southern California (1978-1979), Stanford University (1979-1980), the Australian National University (1984), Philips Research Laboratory Belgium (1980-1991), the University of Illinois at Urbana-Champaign (1991-1994), Florida State University (1998) and the Universite Catholique de Louvain (1980-1991, 1994-now) where he is currently a professor of Mathematical Engineering
Dr. Van Dooren received the Householder Award in 1981 and the Wilkinson Prize of Numerical Analysis and Scientific Computing in 1989. He became an IEEE Fellow in 2006. He is an Associate Editor of several journals in numerical analysis and systems and control theory. His main interests lie in the areas of numerical linear algebra, systems and control theory, digital signal processing, and parallel algorithms.

Presented On: April 2nd, 2007
Video: Click here to see the video