Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors

In this paper we propose an inexact spectral matching algorithm that embeds large graphs on a low-dimensional isometric space spanned by a set of eigenvectors of the graph Laplacian. Given two sets of eigenvectors that correspond to the smallest non-null eigenvalues of the Laplacian matrices of two graphs, we project each graph onto its eigenenvectors. We estimate the histograms of these one-dimensional graph projections (eigenvector histograms) and we show that these histograms are well suited for selecting a subset of significant eigenvectors, for ordering them, for solving the sign-ambiguity of eigenvector computation, and for aligning two embeddings. This results in an inexact graph matching solution that can be improved using a rigid point registration algorithm. We apply the proposed methodology to match surfaces represented by meshes.

@InProceedings\{KSMH09,
  author       = "Knossow, David and Sharma, Avinash and Mateus, Diana and Horaud, Radu P.",
  title        = "Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors",
  booktitle    = "Proceedings 7th Workshop on Graph-based Representations in Pattern Recognition",
  series       = "LNCS 5534 ",
  month        = "May",
  year         = "2009",
  publisher    = "Springer",
  address      = "Venice, Italy",
  url          = "http://perception.inrialpes.fr/Publications/2009/KSMH09"
}