On the convergence of graph Laplacians with a symmetric divergence

2026-07-08 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

A key finding demonstrates the pointwise convergence of graph Laplacians constructed using a smooth symmetric divergence D on a smooth, compact, connected Riemannian submanifold ℬ. The analysis shows that when ℬ is equipped with such a divergence D and a Riemannian metric g_p = ½Hess_p(D(p,·)), there exists a constant K>0 such that |D(p,q)-d_g(p,q)^2| ≤ Kd_g(p,q)^4 for all p,q ∈ ℬ. This crucial fourth-order error estimate enables the convergence proof. The work applies these findings to the Sinkhorn divergence, a debiased entropy-regularized optimal transport measure, particularly for families of probability measures parametrized by a manifold, such as particle systems or smooth deformations of a measure. This extends manifold learning algorithms like Laplacian eigenmaps beyond Euclidean distance.

Key takeaway

For research scientists developing manifold learning algorithms, this work provides a robust theoretical foundation for using symmetric divergences, specifically the Sinkhorn divergence, as dissimilarity measures. You can now confidently apply graph Laplacian-based methods to data represented as probability measures, such as molecular conformations, without being restricted to Euclidean distances. Consider integrating Sinkhorn divergence into your manifold learning pipelines to analyze complex, high-dimensional data where traditional metrics fall short.

Key insights

Graph Laplacian convergence extends to symmetric divergences by establishing a fourth-order error estimate against geodesic distance.

Principles

• Symmetric divergences can approximate squared geodesic distance with a Kd_g(p,q)^4 error.
• Non-degeneracy of g_p = ½Hess_p(D(p,·)) is critical for Riemannian manifold structure.
• Smoothness of divergence around the diagonal Ξℬ enables convergence proofs.

Method

The method involves using the symmetry of the divergence D to improve Taylor expansion error estimates to fourth order, then applying the implicit function theorem to prove smoothness of Sinkhorn divergence and its potentials.

In practice

• Apply Laplacian eigenmaps using Sinkhorn divergence for probability measure data.
• Model molecular conformation spaces with manifold learning on Sinkhorn divergence.

Topics

• Manifold Learning
• Graph Laplacian
• Sinkhorn Divergence
• Riemannian Geometry
• Optimal Transport
• Schrödinger Potentials

Best for: AI Scientist, Research Scientist

Related on AIssential

• Optimal Transport for Machine Learners — Optimal Transport offers a robust mathematical framework for comparing probability distributions, crucial for generative AI model design.
• Geodesic Flow Matching on a Riemannian Degradation Manifold for Blind Image Restoration — Modeling image degradations on a Riemannian manifold enables more principled blind image restoration via geodesic flow matching.
• Geometric structures and deviations on James' symmetric positive-definite matrix bicone domain — New Finsler and dual information-geometric structures on SPD bicone domain offer alternative dissimilarity measures.
• Barycentric Projections of Optimal Transport Plans on Riemannian Manifolds — A framework enables deterministic map extraction from optimal transport couplings on Riemannian manifolds using intrinsic and tangential projections.
• Which Way Does It Go? — Symmetric geometric models are insufficient for systems where direction, order, or causality are fundamental.
• Improved Convergence Analysis of Topology Dependence in Decentralized SGD — Decentralized SGD convergence is influenced by all mixing matrix eigenvalues, not just the spectral gap, aligning theory with experimental observations.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.