Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth
Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
J. Calder;Mahmood Ettehad
中科院分区：
文献类型：
--
作者：
J. Calder;Mahmood Ettehad
最短路径图距离广泛应用于数据科学和机器学习，因为它们可以近似数据流形上的底层测地线距离。然而，最短路径距离对图中损坏边的添加高度敏感，无论是通过噪声还是对抗性扰动。本文研究了图上的一类Hamilton-Jacobi方程，我们称之为$p$ -eikonal方程。我们证明了$p$ -eikonal方程与$p=1$在图上是一个可证明的鲁棒距离型函数，$p\to \infty$极限恢复了最短路径距离。虽然$p$ -eikonal方程不对应于最短路径图距离，但我们仍然表明，$p$ -eikonal方程在随机几何图上的连续体极限恢复连续体中的测地线密度加权距离。我们考虑了$p$ -eikonal方程在数据深度和半监督学习中的应用，并使用连续统极限证明了这两种应用的渐近一致性结果。最后，我们展示了在真实图像数据集（包括MNIST、FashionMNIST和CIFAR-10）上进行数据深度和半监督学习的实验结果，结果表明$p$ -eikonal方程比最短路径距离提供了明显更好的结果。
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\to \infty$ 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.