没想到时隔半年，我又把拉普拉斯算子这块难啃的骨头捡起来了，在之前我虽然搞清楚了在欧式空间上连续拉普拉斯算子和傅里叶变换间的关系，但是事情远没有那么简单。当我深入看这些论文之后，我放弃了完全弄动它们的想法，已经超出了我的数学能力范围，可能后面有大块空闲的时间，学习微分几何，黎曼流形之后，再来看这些内容。这章纯粹是个人理解，如果有不准确的地方请海涵。

Graph Laplacian的来历

首先，离散拉普拉斯算子不只有一种，根据问题的不同有很多种形式，最经典的是图拉普拉斯算子，因为我们大多数图都是非欧几里得空间中的数据，比如社交网络、商品和用户间的关系等等，图的存在是非常广泛的，但是在非欧空间中，形式简单的拉普拉斯算子不能用了，我们需要另寻他法。图拉普拉斯算子定义为 $L=D-A$，其中D为度矩阵，A为邻接矩阵，也有其他的定义比如$L=D-W$，W为权重矩阵，表示有权图。这些定义可以说是凭经验写的，也叫empirical approximation，就是根据之前的经验和线索猜的。

是怎么猜出来的呢？具体的过程见论文[3] (这篇论文是最早讲谱聚类的，Belkin这位大佬在开发谱聚类后，之后一直在研究图拉普拉斯矩阵的收敛性问题)，这里简单写下我的理解。

首先，需要了解Laplace-Beltrami算子，这个算子是欧式空间中的Laplacian在黎曼流形上的推广，既然推广了，他们的共同定义要一致，即梯度的散度：

$\begin{aligned} \Delta_M f &=\nabla_M\cdot\nabla_M f \\ &=\mathrm{div}(\nabla_M f) \end{aligned}$

按照论文[1]中的说法，当流形$M$不确定的时候，Laplace-Beltrami算子是没有一个通用的解析式的（原文：, the closed form of the Laplace operator is unavailable for general manifolds）。至于为什么没有，这个坑我没有找到。然后论文[1]说，因此，需要给出一个有具体形式的中间算子$\mathcal{L}$，来近似Laplace-Beltrami算子：

$\mathcal{L}_t^Mf(x)=\frac{1}{t(4\pi t)^{m/2}}\int_{y\in M} e^{-\frac{||x-y||^2}{t}}(f(x)-f(y))dy$

这个公式出现的很突然，论文[1]表示，这是论文[3] Belkin先提出来的，然后论文[3]的Belkin说，这是文献[4]在1997年提出来的，等我找到了文献[4]，我已经彻底看不懂了。

总之，论文[3]中说到，流形上的Laplace-Beltrami算子与热力学方程紧密相关（可能要去看数学物理方法的书），然后，利用热传导方程，可以构建出具有核函数的近似中间算子，这一步得去深入阅读文献[4]这本书。我想不通的地方在于，热传导方程和黎曼流形有啥关系，[4]这本书的Introduction我都看不懂，更别说深入去了解了。直观来说，这个近似是建立在一个假设之上：在流形上两个点之间的信息交流的速度和热传导相似。

我们接受这个事实，这个中间算子就是用来近似Laplace-Beltrami算子的。然后，再做进一步离散化，将积分改为级数，设$K$为流形$M$的网格近似（满足一定条件的近似），$V=\{v_1,…,v_n\}$是网格上的顶点
，并且$f$是网格上的函数，可以表示为向量$\mathbf{f}=[f(v_1),…,f(v_n)]^T$，那么离散化后的近似算子可以写成矩阵形式：

$L_{t,n}^K f(v_i)=\frac{1}{t(4\pi t)^{m/2}}\sum_{v_j\in V}\frac{1}{n}e^{-\frac{|v_i-v_j||^2}{4t}}(f(v_i)-f(v_j))$

可以令图的权矩阵为:

$W_{ij}= \begin{cases} e^{-\frac{|v_i-v_j||^2}{4t}}& \text{if } ||v_i-v_j||<\epsilon\\\\ 0& \text{otherwise} \end{cases}$

这样$L=D-W$就出来了

我们发现，这里的核心在于热传导方程和Laplace-Beltrami算子的关系，搞清楚文献[4]是怎么导出近似算子的，就搞清楚了$L=D-W$是怎么来的。

Graph Laplacian谱的收敛性

上面给出了图拉普拉斯算子的形式，一路近似过来的，显然我们需要大胆猜想，小心求证。你这样近似出来的拉普拉斯矩阵，靠不靠谱？如果我的点足够多，足够密，趋近于无穷大，这个拉普拉斯矩阵还能继续近似吗？

文献[1],[2]还有很多都在研究这个问题，我只看了大致的思路。首先，需要明确的是，如果算子收敛，是不能得出算子的特征值和特征向量也收敛的。我们用Graph Laplacian主要是用它的特征值和特征向量，那么研究自然也是特征值的收敛和特征向量的收敛，这两个要求会更强一些。

文献[2]应该是比较早研究收敛性的文章，后面很多文章都引用它，我们简单说下它的证明步骤。

$\mathbf{Eig \ L}_{t,n}^K \xrightarrow{n\rightarrow \infty} \mathbf{Eig \ }\mathcal{L}_{t}^\mathcal{M} \xrightarrow{t\rightarrow 0} \mathbf{Eig \ }\Delta_\mathcal{M}$

证明分为两个步骤：

part1

证明当n趋于无穷大的时候，也就是在流形$\mathcal{M}$上，以uniform的分布采样无穷多的点，那么图拉普拉斯算子$\mathbf{ L}_{t,n}^K$的特征值与特征向量会收敛至流形上连续的近似算子$\mathcal{L}_{t}^\mathcal{M}$。也就是得到以下结论:

$\lim_{n\rightarrow \infty} \lambda^t_{n,i}=\lambda^t_i \\ \\ \ \\ \lim_{n\rightarrow \infty}||e^t_{n,i}(x)-e^t_i(x)||=0$

其中$\lambda$表示特征值，$e(x)$表示特征函数。

part2

证明当t趋于无穷小的时候，近似拉普拉斯算子的特征值和特征向量收敛于流形$\mathcal{M}$上的Laplace-Beltrami算子。这里的t是热传导方程中的时间参数，是指在当前，经过t时间后，某个地方的温度大小。当t趋于无穷小，也就是下一刻无限趋近这一刻的时候，很抽象，论文[1][2][3]都没有给出直观解释。这样看似简单的两步，涉及到其他很多文献。

另外，我们注意到一些前置条件，比如从流形上采样的点，必须是均匀概率分布。

总结

至此，我们终于磕磕绊绊，了解了图拉普拉斯算子的来龙去脉，但是远没有到完全清楚的地步。这是个时间跨度很长的学习，关于Laplacian的零零散散至少还有两个点没有搞清楚，需要后面继续努力：

为什么黎曼流形上的Laplace-Beltrami算子没有通用的解析式。
热力学方程和Laplace-Beltrami算子的关系。
近似Laplace-Beltrami算子的导出理由是什么。

我觉得首先得了解微分几何和黎曼流形的基本概念，再去看Laplace-Beltrami算子。文献[4]的标题就是The Laplacian on a Riemannian Manifold，看起来很符合我的痛点，可惜前置知识太多，一时半会看不完。这里再挖一个坑，等到明年的今天，希望我可以弄清楚这三个问题。