By the same authors

From the same journal

From the same journal

A Riemannian approach to graph embedding

Research output: Contribution to journalArticle

Published copy (DOI)



Publication details

JournalPattern recognition
DatePublished - Mar 2007
Issue number3
Number of pages15
Pages (from-to)1042-1056
Original languageEnglish


In 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. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

    Research areas

  • graph embedding, Riemannian geometry, combinatorial Laplacian, NONLINEAR DIMENSIONALITY REDUCTION, EM ALGORITHM, RELAXATION

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations