深入理解拉普拉斯特征映射

前言

拉普拉斯特征映射(Laplacian Eigenmaps，LE)是一种降维方法，之前有讲过一种比较常见的降维算法：主成分分析。

LE在图嵌入中有一些应用，所以在这里总结一下。

1. 问题定义

，

，

为邻接矩阵，

为图的度矩阵（对角阵），有

。

图的拉普拉斯矩阵定义：

需要注意的是，对于有向图来说，

可以为出度矩阵，也可以为入度矩阵，视具体情况而定。我们下面讨论的都是无向图的拉普拉斯矩阵。

对于实对称矩阵

，有以下性质：对任意非零列向量

，我们有：

即

是半正定的。证明如下：

2. 矩阵的迹求导

对LE的推导需要补充一些矩阵论的知识：

3. LE

3.1 目标函数

在图嵌入中，我们的目的是得到每个顶点的低维向量表示，假设嵌入向量维度为 。

LE的思想：如果两个数据实例很相似，那么它们在降维后的目标子空间中应该尽量接近。

而在图嵌入中，衡量两个节点是否相似的最直接度量为一阶邻近度，两个节点 和 间的一阶邻近度即两个节点间相连边的权重。

一阶邻近度通常意味着真实世界网络中两个节点的相似性。正所谓近朱者赤近墨者黑，比如在社交网络中成为朋友的人往往有相似的兴趣爱好，又比如万维网上相互链接的网页往往谈论类似的话题。由于这种重要性，现有的许多图嵌入算法在设计目标函数时都会保持一阶邻近度。

因此，LE的思想可以重新表述为：如果两个节点在原始图中彼此相邻，那么它们的低维嵌入向量应该彼此接近。

我们设节点

和

的向量表示分别为

和

，鉴于此，我们就可以得出LE的目标函数：

从目标函数可以看出，如果两个节点

和

的一阶邻近度

较大（很相似），那么我们在最小化目标函数时，就会更多地考虑减小二者间的差异。

假设

是一个列向量，那么

。

下面开始对目标函数进行化简：

其中，

，

表示对矩阵

求秩（对角线之和）。

3.2 约束条件

考虑到目标函数：

我们不妨设想一种极端情况：假设所有节点都映射到了同一个位置，也就是所有节点的嵌入向量

相同，那么此时目标函数肯定有最小值0。又比如我们就假设所有节点的嵌入向量全部为0向量，此时目标函数也有最小值0。

以上两种情况是毫无意义的。此外，在上述情况下，

的维度也是任意的。因此，为了得到唯一解，我们需要对节点嵌入向量

做一些限制。

一个最简单的限制就是：我们希望最终得到的所有节点的嵌入向量 能够尽可能地去填充 空间，而不是挤在一起。举个例子，假设 ，那么我们不希望所有节点的嵌入向量 (一个点)挤在一起，或者就只是聚集在某一条直线附近，而是尽可能的去散开，因为如果聚在一起就表示图中所有节点具有类似的性质，这显然是不科学的，我们只是需要邻接的节点的嵌入向量相似即可。

为了理解限制条件，我查阅了拉普拉斯特征映射的论文，论文中给出的限制条件为：

原文中关于约束条件的描述为：

这一限制条件删除了嵌入中的任意比例因子。也就是说，每一个

的尺度被固定了。

至于为什么选则

而不是其他矩阵，原文中给出的解释为：度矩阵

可以很好地提供节点自身的一个度量。我们可以这样理解：

可以描述每一个节点在graph中的重要性，如果我们使用

对

的尺度进行限制，那么我们可以使得

在

上分布更加均匀，也就是前面我们提到的：我们希望最终得到的所有节点的嵌入向量

能够尽可能地去填充

空间，而不是挤在一起。

3.3 优化

有了

这一限制条件后，我们可以构造拉格朗日函数如下：

我们令

为一个对角阵，对角阵上的元素

，因此，上述拉格朗日函数可以变为矩阵形式：

对于第一项，由第二节中求导公式(1)可知：

对于第二项，由第二节中求导公式(2)可知：

因此我们有：

解得：

写成一般形式为：

。

3.4 广义特征值问题

上述问题转为广义特征值问题：

所谓广义特征值问题：对于实对称矩阵

和实对称正定矩阵

，如果有非零解

满足：

则称

是

相对于

的特征值。

在本文中， 是实对称矩阵， 首先是实对称矩阵，其次 也是正定的，这点很好证明，便不再叙述。

那么到底如何求解广义特征值问题呢？我们知道，一般特征值的表达形式为：

对于一般特征值求解，我们可以转为：

那么我们可以尝试将广义特征值问题转为此类问题。

首先，我们将矩阵 进行Cholesky分解：

其中 为下三角矩阵。

然后有：

两边乘上 ：

然后：

这时两边都出现了 ，我们将其合并：

我们令：

于是原问题变为一般特征值的求解问题：

然后，我们就能求出矩阵 的特征值 ，进而解出 。

3.5 结果

经过3.4之后，得到了

中的

，然后选取最小的 个非零特征值对应的特征向量作为节点的嵌入向量。

为什么要选取非零特征值的特征向量？根据

的性质， 容易知道

的行和为0。因此，从

可以看出，

具有广义特征值0和对应的特征向量

，如果

被选中，那么所有节点的嵌入向量中的某一维度将全是1，嵌入向量将坍缩到更低一维的空间中。

为什么要选取最小的特征值对应的特征向量？我们将

代回到原目标函数

中，可以得到：

又由于有限制条件：

所以最终目标函数为：

这里

，目标函数即为特征值之和，为了使得目标函数最小化，当然应该选择最小的 个特征值。