Heat Kernel Embeddings, Differential Geometry and Graph Structure

Axioms

Hewayda ElGhawalby²  Edwin R. Hancock¹ 

[1] Department of Computer Science, University of York, York YO10 5GH, UK; E-Mail:;Faculty of Engineering, Port-Said University, Port Said 42526, Egypt

关键词: graph spectra;    kernel-based methods;    graph embedding;    graph clustering;    differential geometry;   

DOI  :  10.3390/axioms4030275

来源: mdpi

【 摘 要 】

In this paper, we investigate the heat kernel embedding as a route to graph representation. The heat kernel of the graph encapsulates information concerning the distribution of path lengths and, hence, node affinities on the graph; and is found by exponentiating the Laplacian eigen-system over time. A Young–Householder decomposition is performed on the heat kernel to obtain the matrix of the embedded coordinates for the nodes of the graph. With the embeddings at hand, we establish a graph characterization based on differential geometry by computing sets of curvatures associated with the graph edges and triangular faces. A sectional curvature computed from the difference between geodesic and Euclidean distances between nodes is associated with the edges of the graph. Furthermore, we use the Gauss–Bonnet theorem to compute the Gaussian curvatures associated with triangular faces of the graph.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland.