By the same authors

From the same journal

From the same journal

Geometric characterization and clustering of graphs using heat kernel embeddings

Research output: Contribution to journalArticlepeer-review

Published copy (DOI)

Author(s)

Department/unit(s)

Publication details

JournalImage and Vision Computing
DatePublished - Jun 2010
Issue number6
Volume28
Number of pages19
Pages (from-to)1003-1021
Original languageEnglish

Abstract

In this paper, we investigate the use of heat kernels as a means of embedding the individual nodes of a graph in a vector space. The reason for turning to the heat kernel is that it encapsulates information concerning the distribution of path lengths and hence node affinities on the graph. The heat kernel of the graph is found by exponentiating the Laplacian eigensystem over time. In this paper, we explore how graphs can be characterized in a geometric manner using embeddings into a vector space obtained from the heat kernel. We explore two different embedding strategies. The first of these is a direct method in which the matrix of embedding co-ordinates is obtained by performing a Young-Householder decomposition on the heat kernel. The second method is indirect and involves performing a low-distortion embedding by applying multidimensional scaling to the geodesic distances between nodes. We show how the required geodesic distances can be computed using parametrix expansion of the heat kernel. Once the nodes of the graph are embedded using one of the two alternative methods, we can characterize them in a geometric manner using the distribution of the node co-ordinates. We investigate several alternative methods of characterization, including spatial moments for the embedded points, the Laplacian spectrum for the Euclidean distance matrix and scalar curvatures computed from the difference in geodesic and Euclidean distances. We experiment with the resulting algorithms on the COIL database. (C) 2009 Elsevier B.V. All rights reserved.

    Research areas

  • Graph spectra, Kernel methods, Graph embedding, Differential geometry, Graph clustering, DIMENSIONALITY REDUCTION, ALGORITHM

Discover related content

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

View graph of relations