4.Structure Preserving Embedding

算法思路

如果一种连通算法能够很容易地从嵌入后的节点坐标中恢复输入图的边，那么说明拓扑结构得到了保留（简单来说，映射后能逆向还原出原图的边点）

SPE是一个半定程序（semidefinite program），它学习由一组线性不等式约束的低秩核矩阵，这些不等式捕获了输入图的连通性结构。

传统的Graph embedding算法一般将节点映射到某种平面（如欧几里得空间）上的一点，如果节点与节点之间存在权重或连接，那么在平面上就用弧线将两个点进行连接。

再次回顾拉普拉斯

推导得拉普拉斯矩阵L(D对角度矩阵，W邻接矩阵)：
$$

利用拉普拉斯矩阵，和的约束条件，使用拉格朗日乘子法求导求解：
$$
于是形成了一个求解特征向量和特征值的问题

但是问题在于存在很多满足解的矩阵，并且得到的解并不能完全保留图的拓扑结构，它只是简单的反应了节点间的相对距离和聚合。

SPE

SPE提出使用一个半正定核矩阵，对它进行谱分解（spectral decomposition）分解产生一组能够保留输入图拓扑结构的特征向量

SPE

思路：给定一个连通算法（判断节点是否连通的算法）G,如果存在一个半正定核矩阵K，使得,则说明保留了嵌入结构

假设顶一个输入图，由表示连通情况的矩阵A和一个算法G，G接收一个核矩阵K,使得A≈G(K)，而计算与原图的差异为：
$$

K最邻节点算法（KNN）

定义:D矩阵由图节点之间的距离根据核矩阵进行计算后得到：
$$

由K的元素线性表示。因为与节点未连接的其他节点必须大于到该节点最远连接的邻居节点的距离
$$

最大权重子图

定义:

提问：

1. 什么是semidefinite program？
2. 什么是spectral decomposition？
3. 经常提到kernel ，kernel本质含义是什么，起什么作用？以便于下次遇见这个单词可以第一时间反应过来它要做什么？