Abstract
This paper describes a spectral method for graph-matching. We adopt a graphical models viewpoint in which the graph adjacency matrix is taken to represent the transition probability matrix of a Markov chain. The node-order of the steady state random walk associated with this Markov chain is determined by the co-efficent order of the leading eigenvector of the adjacency matrix. We match nodes in different graphs by aligning their sequence order in the steady-state walk. The method proceeds from the nodes with the largest leading eigenvector co-efficient. We develop a brushfir e search method to assign correspondences between nodes using the rank-order of the eigenvector coefficients in first-order neighbourhoods of the graphs. We demonstrate the utility of the new graph-matching method on both synthetic and real graphs.