Heat kernel embeddings, differential geometry and graph structure

DOI10.3390/AXIOMS4030275MaRDI QIDQ2422513zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hewayda ElGhawalby, Edwin R. Hancock

Publication date 19 June 2019

Published in Axioms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/axioms4030275

zbMATH Keywords

differential geometrygraph clusteringgraph embeddinggraph spectrakernel-based methods

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for image processing (68U10)

Review text

Summary: 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.

Recommendations

• Geometric Characterizations of Graphs Using Heat Kernel Embeddings
• Graph-Based Representations in Pattern Recognition
• Mathematics of Surfaces XI
• Structural, Syntactic, and Statistical Pattern Recognition
• Graph Regularisation Using Gaussian Curvature

Cites work

• A comprehensive introduction to differential geometry. Vol. 1-5
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• An eigendecomposition approach to weighted graph matching problems
• Consistency of spectral clustering
• Diffusion kernels on statistical manifolds
• scientific article; zbMATH DE number 1219775 (Why is no real title available?)
• scientific article; zbMATH DE number 1385733 (Why is no real title available?)
• scientific article; zbMATH DE number 770462 (Why is no real title available?)
• scientific article; zbMATH DE number 847265 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Kernels and regularization on graphs.
• Spectral embedding of graphs.
• Structural, Syntactic, and Statistical Pattern Recognition
• The geometry of graphs and some of its algorithmic applications
• WFEM heat kernel: Discretization and applications to shape analysis and retrieval

Cited in

(10)

• Graph Regularisation Using Gaussian Curvature
• Geometric Characterizations of Graphs Using Heat Kernel Embeddings
• scientific article; zbMATH DE number 1944725 (Why is no real title available?)
• scientific article; zbMATH DE number 219049 (Why is no real title available?)
• Global graph curvature
• GLEE: geometric Laplacian eigenmap embedding
• Graph-Based Representations in Pattern Recognition
• Mathematics of Surfaces XI
• Structural, Syntactic, and Statistical Pattern Recognition
• Coarse geometric kernels for networks embedding

This page was built for publication: Heat kernel embeddings, differential geometry and graph structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2422513)