File(s) under permanent embargo
A Riemannian approach to graph embedding
journal contribution
posted on 2007-03-01, 00:00 authored by Antonio Robles-KellyAntonio Robles-Kelly, Edwin R HancockIn this paper, we make use of the relationship between the Laplace–Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. To embark on this study, we review some of the basics of Riemannian geometry and explain the relationship between the Laplace–Beltrami operator and the graph Laplacian. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths on the manifold between nodes. For the particular case of a constant sectional curvature surface, we use the Kruskal coordinates to compute edge weights that are proportional to the geodesic distance between points. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold. To do this, we develop a method that can be used to perform double centring on the Laplacian matrix computed from the edge-weights. The embedding coordinates are given by the eigenvectors of the centred Laplacian. With the set of embedding coordinates at hand, a number of graph manipulation tasks can be performed. In this paper, we are primarily interested in graph-matching. We recast the graph-matching problem as that of aligning pairs of manifolds subject to a geometric transformation. We show that this transformation is Pro-crustean in nature. We illustrate the utility of the method on image matching using the COIL database.
History
Journal
Pattern recognitionVolume
40Issue
3Pagination
1042 - 1056Publisher
ElsevierLocation
Amsterdam, The NetherlandsPublisher DOI
ISSN
2160-7508Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
2006, Pattern Recognition SocietyUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC