mlsanityData to 7 Oct 2026

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

arXiv 2202.08789 ↗First posted 17 Feb 2022math.AP cs.LG cs.NAcited by 7

Not on the map. Why?

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.

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

Builds on

26 of 82 references.

References · 26

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2019AET vs. AED: Unsupervised Representation Learning by Auto-Encoding Transformations rather than Datacited by 77
  3. 2018Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operatorcited by 70
  4. 2020Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Ratescited by 49
  5. 2017Analysis of p-Laplacian Regularization in Semi-Supervised Learningcited by 39
  6. 2021SPAGAN: Shortest Path Graph Attention Networkcited by 28
  7. 2020Lipschitz regularity of graph Laplacians on random data cloudscited by 26
  8. 2017The game theoretic p-Laplacian and semi-supervised learning with few labelscited by 22
  9. 2018Properly-weighted graph Laplacian for semi-supervised learningcited by 19
  10. 2020Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Ratescited by 18
  11. 2017Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithmscited by 17
  12. 2015Algorithms for Lipschitz Learning on Graphscited by 16
14 more
  1. 2016Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learningcited by 16
  2. 2020Balancing Geometry and Density: Path Distances on High-Dimensional Datacited by 16
  3. 2017Consistency of Lipschitz learning with infinite unlabeled data and finite labeled datacited by 15
  4. 2019Analysis and algorithms for ℓp-based semi-supervised learning on graphscited by 14
  5. 2019Spectral Analysis Of Weighted Laplacians Arising In Data Clusteringcited by 11
  6. 2017A random matrix analysis and improvement of semi-supervised learning for large dimensional datacited by 10
  7. 2021Uniform Convergence Rates for Lipschitz Learning on Graphscited by 9
  8. 2019Depth for curve data and applicationscited by 8
  9. 2018The limit shape of convex hull peelingcited by 6
  10. 2021Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applicationscited by 4
  11. 2013A Hamilton-Jacobi equation for the continuum limit of non-dominated sortingcited by 3
  12. 2020A continuum limit for the PageRank algorithmcited by 3
  13. 2021Tukey Depths and Hamilton-Jacobi Differential Equationscited by 3
  14. 2022Eikonal depth: an optimal control approach to statistical depthscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 2; 2025: 0; 2026: 1.

7 papers.

  1. 2022Graph-based Active Learning for Semi-supervised Classification of SAR Datacited by 7
  2. 2023Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower boundscited by 6
  3. 2024Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplaciancited by 3
  4. 2023Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classificationcited by 2
  5. 2023Choosing the parameter of the Fermat distance: navigating geometry and noisecited by 2
  6. 2024A Learned Generalized Geodesic Distance Function-Based Approach for Node Feature Augmentation on Graphscited by 1
  7. 2026High-dimensional Semi-supervised Classification via the Fermat Distancecited by 1