UC Irvine

How is the shape of a graph captured by the way heat diffuses between its nodes? The Laplacian Exponential Kernel of a graph is a matrix whose eigenvalues and eigenvectors describe this heat (or more generally, probability) diffusion process as a function of time. Previous work has shown that the Laplacian can be gainfully used for comparing graphs, but these methods are limited to graphs of the same size. This work focuses on generalizing one such measure, Graph Diffusion Distance (GDD), making it capable of comparing graphs of varying size. Calculating these distances involves solving a complicated multivariate optimization problem, and we will detail a novel optimization algorithm for doing so. This procedure outperforms naive univariate optimization by a speedup of as much as 1000x. One key feature of this procedure is that it produces a coarsening operator which attempts to align the two heat kernels to agree with each other as much as possible. These operators can be used as the coarsening step in a convolutional neural network, resulting in a 10x increase in training efficiency. We will show how these “Graph Prolongation Convolutional Networks” can be used to accelerate molecular dynamics simulations of proteins. Finally, we will also discuss some applications of the GDD, including 2D and 3D shape analysis and characterization of plant cell growth.