Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors

(1) , (1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
KnossowSharmaMateusHoraud-GbR.pdf (2.05 Mo) Télécharger le fichier
Vignette du fichier
mesh_matching.png (415.14 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image

Dates and versions

inria-00446989 , version 1 (13-01-2010)

Identifiers

Cite

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⟩
702 View
2015 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More