紧致流形上随机几何与有向k最近邻图拉普拉斯算子的强一致收敛性分析

《Advances in Applied Probability》：Strong uniform convergence of Laplacians of random geometric and directed k NN graphs on compact manifolds

本文聚焦于解决在流形学习领域，如何利用随机采样点构造的图拉普拉斯算子一致逼近连续流形上的拉普拉斯-贝尔特拉米算子这一核心理论问题。研究团队针对光滑紧致流形上由独立同分布点集生成的随机游走生成元，在放宽对核函数连续性的严格限制下，首次系统地证明了其到扩散型拉普拉斯-贝尔特拉米算子的几乎必然一致收敛性，并给出了明确的收敛速率。该工作不仅覆盖了包括k近邻（kNN）图和几何图在内的非连续核情形，还进一步建立了相应随机过程到流形上扩散过程的弱收敛性，为基于图拉普拉斯的流形学习算法提供了坚实的理论保证，对非参数统计、机器学习与概率论等领域均有重要意义。

　　

在现代数据科学和机器学习中，我们常常面对高维空间中的数据点，这些点可能并非杂乱无章地分布，而是悄然聚集在一个低维的、弯曲的“曲面”附近——这个曲面在数学上被称为“流形”（manifold）。例如，一系列人脸图片的高维像素数据，其本质可能由一个低维的姿势、光照参数所控制，形成一个嵌入在高维空间中的低维流形。理解并利用这种流形结构，是“流形学习”（manifold learning）的核心目标。其中，图拉普拉斯算子（graph Laplacian）作为一种从离散数据点中构造的算子，被广泛用于逼近流形上内在的微分算子——拉普拉斯-贝尔特拉米算子（Laplace-Beltrami operator），后者是描述流形上扩散、热传导等物理过程的关键。通过这种逼近，我们可以对数据进行降维、聚类或恢复其几何结构。

然而，理想很丰满，现实却很骨感。大多数现有的理论结果都建立在图拉普拉斯算子所使用的“核函数”（kernel function）K足够光滑（比如连续可微的高斯核）的强假设之上。但在实际应用中，两类非常重要且自然的图——ε-几何图（ε-geometric graph）和k近邻（k-nearest neighbor, kNN）图——所对应的核函数恰恰是不连续的（例如指示函数）。这使得经典理论无法直接适用于这些实用场景。此外，已有的收敛性结果往往缺乏关于收敛速率的定量刻画，或者未能证明算子在整个流形上“一致地”（uniformly）收敛，而这对于后续研究算子的谱（特征值、特征函数）收敛性以及相关随机过程的极限行为至关重要。为了填补这些理论与应用之间的鸿沟，本文的研究人员开展了一项深入的理论探索。

为了回答上述问题，研究团队展开了一项严谨的概率与几何分析。他们研究的对象，是从一个光滑、紧致、无边的d维流形M上，按照一个C²类密度函数p独立同分布采样得到n个点{X_i}。基于这些点，他们定义了如下一族随机算子（即随机游走的生成元）：

A_hn,n(f)(x) = (1/(n h_n^d+2)) Σ_i=1ⁿK(‖x - X_i‖₂/h_n) (f(X_i) - f(x))

其中，K是一个从正实数到正实数的核函数，h_n是一个趋于0的正实数序列（带宽参数）。这个算子的物理意义很直观：它可以解释为一个连续时间随机游走的生成元，该游走在点集上跳转，从位置x跳到点X_i的速率与K(‖x - X_i‖₂/h_n)成正比。当K取高斯函数时，对应经典的图拉普拉斯；当K取指示函数1_[0,1]时，则对应几何图或kNN图的拉普拉斯算子。

本研究的核心目标是证明，当样本量n趋于无穷，带宽h_n以适当速率趋于0时，这个随机算子A_hn,n几乎必然地、一致收敛于（在流形M上每一点，对足够光滑的测试函数f）一个确定的二阶微分算子A：

A(f) = c₀[〈?_M(p), ?_M(f)〉 + (1/2) p Δ_M(f)]

这里，?_M和Δ_M分别是流形M上的梯度算子和拉普拉斯-贝尔特拉米算子，c₀是一个由核函数K决定的常数（c₀= (1/d) ∫_R^dK(‖v‖₂) ‖v‖₂²dv）。这个极限算子A描述了一个依赖于采样密度p的扩散过程。

为了达成这一目标，研究人员采用了多种关键技术方法：

1. 1.
   核心假设的突破：摒弃了核函数K必须连续的经典要求，代之以一个更弱且更具一般性的“有界变差”（bounded variation）假设（Assumption 1）。该假设仅要求K是有限变差的，并满足矩条件∫₀^∞a^d+3dH(a) < ∞（其中H是K的全变差函数）。这使得指示函数K(a)=1_[0,1](a)等非连续核被纳入理论框架，从而覆盖了几何图和kNN图。
2. 2.
   偏差-方差分解与概率工具：将随机算子与极限算子之间的误差系统地分解为两部分：一个“统计误差”（方差项），源自用有限样本的经验平均代替期望，运用了现代概率论中的集中不等式（concentration inequalities）进行控制；一个“逼近误差”（偏差项），源于用欧氏距离近似测地距离以及在局部用切空间近似流形，这部分通过微分几何的工具（如管状邻域理论、指数映射的性质）加以分析。
3. 3.
   一致收敛性的证明策略：为了实现整个流形M上的一致上界，研究采用了覆盖论证（covering argument）。将紧流形M用有限个半径与h_n成正比的小测地球覆盖，先在每个球心处建立收敛性，再利用核函数的有界变差性质和流形的几何正则性，将局部的控制推广到整个流形。
4. 4.
   kNN图情形的特殊处理：针对kNN图拉普拉斯算子A_n^kNN，其挑战在于带宽R_n,kn(x)（点到其第k近邻的距离）是随机且随位置x变化的。研究借用了Cheng和Wu（2019）关于kNN距离一致收敛性的结果，证明了该随机带宽以高概率被一个确定序列h_n的常数倍所控制，从而将kNN情形化归到固定带宽情形进行分析。
5. 5.
   随机过程弱收敛的证明：基于生成元的一致收敛性（定理1），利用Trotter-Kato型逼近定理，并结合在càdlàg函数空间D([0,T], M)上分布的紧性（tightness）论证，建立了由这些生成元驱动的随机游走过程（公式13, 14）弱收敛到极限扩散过程（定理3, 4）。

研究结果

定理1 (主定理)：在密度函数p属于C²类、核函数K满足有界变差假设（Assumption 1）、且带宽序列满足h_n→ 0以及(log h_n^-1)/(n h_n^d+2) → 0的条件下，以概率1，对于所有C³(M)类函数f，有如下一致收敛速率估计：

sup_x∈M|A_hn,n(f)(x) - A(f)(x)| = O( √( (log h_n^-1)/(n h_n^d+2) ) + h_n)。

通过优化带宽h_n~ n^-1/(d+4)，可获得最优收敛速率O(n^-1/(d+4))（忽略对数因子），这与Hein等人（2007）提出的最优速率一致。

推论1 (指数浓度不等式)：在上述假设下，可以推导出一个非渐近的、一致的概率上界。存在常数C'>0，使得对所有充分大的n和适当的δ，有：

P( sup_f∈Fsup_x∈M|A_hn,n(f)(x) - Af(x)| > C'δ ) ≤ exp( -n h_n^d+2δ²)。

其中F是一族有界的C³(M)函数及其导数。这为统计推断提供了有力的工具。

定理2 (kNN图拉普拉斯的收敛)：对于kNN图拉普拉斯算子A_n^kNN，在密度p有正的下界p_min> 0，且k_n满足k_n/n → 0以及(1/n)(n/k_n)^1+2/dlog(n/k_n) → 0的条件下，以概率1，有：

sup_x∈M|A_n^kNN(f)(x) - A(f)(x)| = O( √log(n/k_n) * (1/√k_n) * (n/k_n)^1/d+ (k_n/n)^1/d)。

当选择k_n~ n^4/(d+4)时，同样得到速率O(√log n * n^-1/(d+4))。

定理3与定理4 (随机过程的收敛)：在定理1和定理2的条件下，进一步假设随机游走过程的初始分布收敛于某概率测度ν，则这些随机游走过程（无论是基于固定带宽还是kNN图）在càdlàg函数空间D([0, T], M)上的分布，弱收敛到以算子A为生成元、以ν为初始分布的扩散过程X。这意味着，不仅无穷小生成元收敛，整个路径的随机行为也收敛。

结论与讨论

本研究取得了以下重要结论：

1. 1.
   理论框架的显著扩展：成功地将图拉普拉斯算子的收敛性理论推广到核函数仅为有界变差的情形，从而首次在严格的理论意义上，将k近邻图和几何图这两类在应用中极为重要的图模型纳入统一的分析框架。这解决了之前许多工作（如Giné和Koltchinskii, 2006; Hein等人, 2007）因要求核函数连续或光滑而无法处理非连续核的遗留问题。
2. 2.
   强一致收敛性与定量速率：不仅证明了几乎必然的点态收敛，更重要的是证明了在流形上关于位置x和关于一族光滑测试函数f的“双重”一致收敛性，并给出了明确的收敛速率。这种强一致性是研究谱收敛（如特征值、特征函数的收敛）的关键前提，也为基于Courant-Fisher极大极小原理的谱分析铺平了道路。
3. 3.
   从算子到随机过程的升华：通过结合生成元的一致收敛和概率测度的紧性论证，将结论从静态的算子收敛提升到了动态的随机过程收敛。这证明了在流形上由离散点集定义的随机游走，在适当缩放下，其宏观极限行为是由一个连续的扩散过程所描述。这为理解基于图的随机算法（如随机游走采样、标签传播）的极限行为提供了理论基础。
4. 4.
   方法论上的贡献：研究巧妙地融合了概率论（集中不等式、经验过程理论）、微分几何（管状邻域、指数映射、距离比较）和随机分析（泊松点过程、随机微分方程、弱收敛理论）的工具，为解决此类流形学习中的概率-几何交叉问题提供了一个有力的范式。特别是对kNN距离的随机性控制，以及对非连续核的处理技术，具有方法论上的创新性。

本研究的成果具有深远的意义。首先，它为流形学习中广泛使用的基于图的算法（特别是那些使用非连续相似性度量的算法）提供了坚实的数学基石，增强了其可信度。其次，一致收敛性和收敛速率的获得，使得在统计意义上对这些方法进行误差控制和模型选择成为可能。最后，随机过程收敛性的建立，开辟了连接离散图过程与连续扩散过程的新视角，有望在基于扩散的图神经网络、非参数贝叶斯推断以及数学物理中的格点模型逼近连续场论等领域产生后续影响。总之，这项发表在《应用概率进展》（Advances in Applied Probability）上的工作，是连接概率论、几何分析与机器学习理论的一座坚实桥梁，对推动数据科学的基础理论发展具有重要意义。