Graph Matching using Adjacency Matrix Markov Chains

A Robles-Kelly and E Hancock

This paper describes a graph-spectral method for structural matching. We make use of the leading eigenvector of the node adjacency matrix. The magnitude order of the co-efficients in this vector defines an edge-connected walk across the graph. We match nodes in different graphs by using their sequence order in the walk. The method proceeds from the nodes with the largest leading eigenvector co-efficient. We develop a brushfire search method to assign correspondences between nodes using the rank-order of the eigenvector co-efficients in first-order neighbourhoods of the graphs. We demonstrate the utility of the new graph-matching method on both synthetic and real graphs.

PDF version

Home Contents Author index Keyword index

Valid CSS! Valid HTML 4.01!

This document produced for BMVC 2001