Skip to Main content Skip to Navigation
Conference papers

Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors

David Knossow 1 Avinash Sharma 1 Diana Mateus 1 Radu Horaud 1
1 PERCEPTION [2007-2015] - Interpretation and Modelling of Images and Videos [2007-2015]
Inria Grenoble - Rhône-Alpes, LJK [2007-2015] - Laboratoire Jean Kuntzmann [2007-2015], Grenoble INP [2007-2019] - Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019]
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Radu Horaud <>
Submitted on : Wednesday, January 13, 2010 - 10:17:04 PM
Last modification on : Thursday, July 23, 2020 - 10:02:02 AM
Long-term archiving on: : Thursday, October 18, 2012 - 12:25:44 PM


Files produced by the author(s)




David Knossow, Avinash Sharma, Diana Mateus, Radu Horaud. Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors. 7th International Workshop on Graph-Based Representations in Pattern Recognition, May 2009, Venice, Italy. pp.144-153, ⟨10.1007/978-3-642-02124-4_15⟩. ⟨inria-00446989⟩



Record views


Files downloads