Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors

David Knossow 1 Avinash Sharma 1 Diana Mateus 1 Radu Horaud 1
1 PERCEPTION - Interpretation and Modelling of Images and Videos
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
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


https://hal.inria.fr/inria-00446989
Contributor : Radu Horaud <>
Submitted on : Wednesday, January 13, 2010 - 10:17:04 PM
Last modification on : Wednesday, April 11, 2018 - 1:59:47 AM
Long-term archiving on : Thursday, October 18, 2012 - 12:25:44 PM

Files

KnossowSharmaMateusHoraud-GbR....
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

1073

Files downloads

2483