# Capturing Graphs with Hypo-Elliptic Diffusions

arXiv: https://arxiv.org/abs/2205.14092 · HTML: https://mlsanity.com/paper/2205.14092/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 75 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 30 of 46)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Group Normalization](https://mlsanity.com/paper/1803.08494/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)

## Built on by (most cited first, 12 of 12)

- [On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems](https://mlsanity.com/paper/2405.01009/) (2024)
- [From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyond](https://mlsanity.com/paper/2310.10121/) (2023)
- [Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching](https://mlsanity.com/paper/2312.16560/) (2023)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs](https://mlsanity.com/paper/2302.00713/) (2023)
- [Improving the Effective Receptive Field of Message-Passing Neural Networks](https://mlsanity.com/paper/2505.23185/) (2025)
- [G-Signatures: Global Graph Propagation With Randomized Signatures](https://mlsanity.com/paper/2302.08811/) (2023)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows](https://mlsanity.com/paper/2508.05070/) (2025)
- [S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning](https://mlsanity.com/paper/2605.23467/) (2026)
- [Widest-Path Reachability Fields for Connectivity-Preserving Slender Structure Segmentation](https://mlsanity.com/paper/2607.07123/) (2026)

## Abstract (arXiv)

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.