大规模复杂信息网络表示学习

1. 经典网络表示学习

将图嵌入学习算法应用在复杂信息网络上进行特征学习。首先将网络转换成矩阵表示，然后通过求解矩阵特征向量的形式，进行降维以获取网络的低维表达。

（1）基于谱方法的网络表示学习

直接从矩阵特征值等角度出发进行网络特征学习。

主成分分析PCA & 奇异值分解SVD

PCA/SVD可以降低高维空间中点的维度，并解决低维空间中的目标问题。此外，PCA/SVD算法通常还能够突出显示数据中的隐含结构。但是，通常这种把网络转换成邻接矩阵、通过PCA/SVD获得的顶点的低维表示质量较差。

主成分分析

奇异值分解

局部线性嵌入算法LLE

LLE（Locally Linear Embedding）是一种无监督局部线性嵌入算法。和PCA、LDA等关注样本方差的降维方法相比，LLE关注于降维时保持样本局部的线性特征，因此，它被广泛地用于图像识别、高维数据可视化等领域。

算法思想：LLE首先假设数据在较小的局部是线性的，即某一个数据可以由它邻域中的几个样本线性表示。比如我们有一个样本 $x_1$ ，我们在它的原始高维邻域里用K-近邻思想找到和它最近的三个样本 $x_2, x_3, x_4$ 。然后我们假设 $x_1$ 可以由 $x_2, x_3, x_4$ 线性表示，即：

$x_1=w_{12}x_2+w_{13}x3+w_{14}x_4$

在通过LLE降维后，我们希望 $x_1$ 在低维空间对应的投影 $x_1'$ 和 $x_2, x_3, x_4$ 对应的投影 $x_2', x_3', x_4'$ 也尽量保持同样的线性关系，即

$x_1'\approx w_{12}x_2'+w_{13}x_3'+w_{14}x4'$

也就是说，投影前后线性关系的权重系数 $w_{12}, w_{13}, w_{14}$ 是尽量不变或者最小改变的。

LLE算法以网络的邻接矩阵作为初始数据输入，计算得到各个顶点的局部重建权值矩阵后，将问题最后归结为矩阵特征值求解，从而获取顶点的低维表示。

Isomap

与LLE类似，Isomap通过分析高维流形，找到与之对应的低维嵌入。在计算高维流形上顶点之间距离时，使用测地线距离代替传统的欧氏距离，提出了一种用实际输入数据估计其测地线距离的算法。

拉普拉斯特征映射（Laplacian Eigenmaps）

**思想：**如果网络中两个顶点 $i$ 和 $j$ 很相似，那么 $i$ 和 $j$ 在降维后的空间中会非常靠近。

拉普拉斯特征映射能够反映出数据内在的流形结构，通过构建邻接矩阵作为输入，来重构数据流形的局部结构特征，最终选取拉普拉斯矩阵的最小的t个非零特征值对应的特征向量来表示学习到的网络。

局部线性协调LLC（Locally Linear Coordination）

通过几个局部降维专家学习使得不同的内部表示映射到用于原始数据空间的单一且一致的全局坐标系统中。该算法可以应用于任何专家组，同时，每个专家组会产生高维输入的低维局部表示。

与需要修改目标函数的模型不一样，LLC算法使用一种有效的特征分解器对训练后的模型进行后处理。这也使它比无模型算法（例如Isomap或LLE）更有效。

（查错了）稀疏保持嵌入SPE（Structure Preserving Embedding）

SPE算法的主要思想是以稀疏表示和图嵌入为基础，在低维嵌入空间中保持数据在高维空间中的稀疏特性不变，即先由稀疏表示揭示出各数据在高维全局空间中的内在相似性，再由图嵌入方法在低维嵌入空间中保持各数据的这种内在相似性不变。

结构保留嵌入方法SPE（Structure Preserving Embedding）

SPE被归结为一个半定规划问题，其学习由一组线性不等式约束的低秩核矩阵，用于捕获输入图的链接结构。SPE在图的可视化和无损压缩方面获得明显改善，优于拉普拉斯特征映射等方法。SPE可以仅使用几个维度对图或网络进行合理嵌入，并且将结构保留约束引入降维算法从而产生高维数据的更准确的学习表示。

（2）基于最优化的网络表示学习

这类表示学习算法事先设定一个优化目标函数，其参数设置为顶点在低维空间的向量形式，对目标函数进行最大化或最小化优化处理，最终得出网络中的顶点在低维空间的向量表示。

有向图嵌入DGE（Directed Graph Embedding）

DGE算法主要利用了转移概率与马尔可夫随机游走的思想。定义优化目标函数如下：

$\sum_i{T_V(i)}\sum_{j,i\rightarrow j}{T_E(i,j)(y_i-y_j)^2}$

其中， $y_i$ 是嵌入在一维空间中顶点 $i$ 的坐标， $T_E(i,j)$ 代表哦两个顶点 $i$ 和 $j$ 之间的有向边的重要性， $T_V(i)$ 则用于衡量顶点在图中的重要性。

对目标函数最小化以此获得图在一维空间上的优化嵌入。嵌入过程中考虑了顶点对的局部关系和顶点的全局相对重要性。如果DGE算法应用于无向网络，则该算法等价于Laplacian Eigenmaps算法。

多维量表MDS（Multi-dimensional Scaling）

MDS将网络的顶点映射到一个低维的欧式空间，使得在新空间中可以保持网络顶点的相似性。这个相似性可以基于网络连通性计算得到。