Capturing graphs with hypo-elliptic diffusions

Conference item

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.

Authors: Toth, C; Lee, D; Hacker, C; Oberhauser, H

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Curran Associates
• Host title: Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
• Volume: 50
• Pages: 38803-38817
• Publication date: 2023-04-01
• Acceptance date: 2022-09-14
• Event title: 36th Conference on Neural Information Processing Systems (NeurIPS 2022)
• Event location: New Orleans, USA
• Event website: https://nips.cc/Conferences/2022
• Event start date: 2022-11-28
• Event end date: 2022-12-09
• ISSN: 1049-5258
• EISBN: 9781713873129
• ISBN: 9781713871088
• Language: English
• Keywords: FFR