# Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 82 references that are in the map.
- First posted on arXiv 17 Feb 2022.

## Builds on (most cited first, 26 of 26)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [AET vs. AED: Unsupervised Representation Learning by Auto-Encoding Transformations rather than Data](https://mlsanity.com/paper/1901.04596/) (2019)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [SPAGAN: Shortest Path Graph Attention Network](https://mlsanity.com/paper/2101.03464/) (2021)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms](https://mlsanity.com/paper/1712.06206/) (2017)
- [Algorithms for Lipschitz Learning on Graphs](https://mlsanity.com/paper/1505.00290/) (2015)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Balancing Geometry and Density: Path Distances on High-Dimensional Data](https://mlsanity.com/paper/2012.09385/) (2020)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [Analysis and algorithms for ℓp-based semi-supervised learning on graphs](https://mlsanity.com/paper/1901.05031/) (2019)
- [Spectral Analysis Of Weighted Laplacians Arising In Data Clustering](https://mlsanity.com/paper/1909.06389/) (2019)
- [A random matrix analysis and improvement of semi-supervised learning for large dimensional data](https://mlsanity.com/paper/1711.03404/) (2017)
- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Depth for curve data and applications](https://mlsanity.com/paper/1901.00180/) (2019)
- [The limit shape of convex hull peeling](https://mlsanity.com/paper/1805.08278/) (2018)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [A Hamilton-Jacobi equation for the continuum limit of non-dominated sorting](https://mlsanity.com/paper/1302.5828/) (2013)
- [A continuum limit for the PageRank algorithm](https://mlsanity.com/paper/2001.08973/) (2020)
- [Tukey Depths and Hamilton-Jacobi Differential Equations](https://mlsanity.com/paper/2104.01648/) (2021)
- [Eikonal depth: an optimal control approach to statistical depths](https://mlsanity.com/paper/2201.05274/) (2022)

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

- [Graph-based Active Learning for Semi-supervised Classification of SAR Data](https://mlsanity.com/paper/2204.00005/) (2022)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classification](https://mlsanity.com/paper/2305.16239/) (2023)
- [Choosing the parameter of the Fermat distance: navigating geometry and noise](https://mlsanity.com/paper/2311.18663/) (2023)
- [A Learned Generalized Geodesic Distance Function-Based Approach for Node Feature Augmentation on Graphs](https://mlsanity.com/paper/2407.01194/) (2024)
- [High-dimensional Semi-supervised Classification via the Fermat Distance](https://mlsanity.com/paper/2604.23573/) (2026)

## Abstract (arXiv)

Shortest path graph distances are widely used in data science and machine learning, since they can approximate the underlying geodesic distance on the data manifold. However, the shortest path distance is highly sensitive to the addition of corrupted edges in the graph, either through noise or an adversarial perturbation. In this paper we study a family of Hamilton-Jacobi equations on graphs that we call the p-eikonal equation. We show that the p-eikonal equation with p=1 is a provably robust distance-type function on a graph, and the p→ ∞ limit recovers shortest path distances. While the p-eikonal equation does not correspond to a shortest-path graph distance, we nonetheless show that the continuum limit of the p-eikonal equation on a random geometric graph recovers a geodesic density weighted distance in the continuum. We consider applications of the p-eikonal equation to data depth and semi-supervised learning, and use the continuum limit to prove asymptotic consistency results for both applications. Finally, we show the results of experiments with data depth and semi-supervised learning on real image datasets, including MNIST, FashionMNIST and CIFAR-10, which show that the p-eikonal equation offers significantly better results compared to shortest path distances.