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


https://hal.inria.fr/inria-00446989
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

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

1329

Files downloads

3354