A Riemannian approach to graph embedding

Antonio Robles-Kelly*, Edwin R. Hancock

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    84 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)1042-1056
    Number of pages15
    JournalPattern Recognition
    Volume40
    Issue number3
    DOIs
    Publication statusPublished - Mar 2007

    Fingerprint

    Dive into the research topics of 'A Riemannian approach to graph embedding'. Together they form a unique fingerprint.

    Cite this