Capturing Graphs with Hypo-Elliptic Diffusions

arXiv2205.14092MaRDI QIDQ6400380FDOQ6400380

Authors: Csaba D. Tóth, Darrick Lee, Celia Hacker, Harald Oberhauser 

Publication date: 27 May 2022

Abstract: Convolutional layers within graph neural networks operate by aggregating information about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these random walks evolves according to a diffusion equation defined using the graph Laplacian. We extend this approach by leveraging classic mathematical results about hypo-elliptic diffusions. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We provide theoretical guarantees and efficient low-rank approximation algorithms. In particular, this gives a structured approach to capture long-range dependencies on graphs that is robust to pooling. Besides the attractive theoretical properties, our experiments show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges as opposed to quadratically in nodes.

Has companion code repository: https://github.com/tgcsaba/graph2tens

This page was built for publication: Capturing Graphs with Hypo-Elliptic Diffusions

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