常见的Graph Embedding方法

Embedding在数学上是一个函数，将一个空间的点映射到另一个空间，通常是从高维抽象的空间映射到低维的具象空间。
Embedding的作用：

• 将高维数据转换到低维利于算法的处理；
• 同时解决one-hot向量长度随样本的变化而变化，以及无法表示两个实体之间的相关性这一问题。

Graph Embedding的分类：

1.DeepWalk
借鉴了word2vec的思想，词嵌入是对一个句子的单词序列进行分析，而Deepwalk的序列是通过随机游走(random walk)得到的。
算法的核心步骤分为两步：

• 使用RandomWalk对图中节点采样，得到节点序列的表示
• 使用SkipGram学习出节点的Embedding表示

RandomWalk:
是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。
SkipGram：
是一个语言模型，用于最大化句子中出现在窗口w内的单词之间的共现概率。它使用独立性假设，最后条件概率近似为：

\[\text{Pr} \left(\left\{v_{i-w}, \dotsc, v_{i+w}\right\} \setminus v_i \mid \Phi \left(v_i\right)\right) = \prod_{j=i-w, j \neq i}^{i+w} \text{Pr} \left(v_j \mid \Phi \left(v_i\right)\right) \]

\(\Phi \left(v_i\right)\) 是节点 \(v_i\) 的向量表示，对序列中的每个顶点，计算条件概率，即该结点出现的情况下序列中其他结点出现的概率的log值，并借助随机梯度下降算法更新该结点的向量表示。

Hierarchical Softmax:
是word2vec中的技术，为了解决标签过多在使用softmax时带来的计算量大的问题。因此生成一个二叉树，叶子节点就是每个类别。假设一共有V个类别，原始softmax的计算量就是 \(O(V)\)，使用二叉树后，从根节点到叶子节点的距离就变成了 \(O(log V)\)。

(无语??研一刚入学老师让看的论文，现在重新整理一遍又看了半天)
2.LINE
优点：

• 同时保留节点之间的一阶相似性（first-order proximity）和二阶相似性（second-order proximity）。
• 可以处理大规模网络，例如：百万级别的顶点和十亿级别的边。
• 可以处理有向，无向和带权的多种类型的图结构。

一阶:局部的结构信息，节点对之间的相似性
二阶:节点的邻居。共享邻居的节点可能是相似的，两个节点的局部网络结构的相似性

对于节点5和6，虽然没有直接的边相连，但是她们的邻居都包含节点1、2、3、4，因此也可能具有相似的表示。

其中，\(u_6\) 是随机初始化的embedding，\(w_{6,7}\)是节点6和7之间边的权重，
通过最小化联合概率分布和经验分布的 KL 散度来优化模型，则目标函数定义如下：

\[O_{1}=-\sum_{(i, j) \in E} w_{i j} \log p_{1}\left(v_{i}, v_{j}\right) \]

注意：一阶相似度仅可用于无向图，通过最小化上述目标函数，我们可以将任意顶点映射到一个d维空间向量。

二阶相似度既可以用于无向图，也可以用于有向图。二阶相似度假设共享大量同其他节点连接的节点之间是相似的，每个节点被视为一个特定的上下文，则在上下文上具有类似分布的节点是相似的。在此，引入两个向量 \(\vec{u}_{i}\) 和 \({\vec{u}_{i}}'\)，其中是 \(\vec{u}_{i}\) 做为节点的表示， \({\vec{u}_{i}}'\) 是做为上下文的表示（其本质是同一个向量，只是论文中用两个不同的符号作为区分）。对于一个有向边 \(\left(i, j\right)\) ，由 \(v_i\) 生成上下文 \(v_j\) 的条件概率为：

\[p_{2}\left(v_{j} | v_{i}\right)=\frac{\exp \left(\vec{u}_{j}^{\prime T} \cdot \vec{u}_{i}\right)}{\sum_{k=1}^{|V|} \exp \left(\vec{u}_{k}^{\prime T} \cdot \vec{u}_{i}\right)} \]

其中，\(|V|\) 为节点或上下文的数量。在此我们引入一个参数 \(\lambda_i\) 用于表示节点 \(v_i\) 的重要性程度，重要性程度可以利用度或者 PageRank 算法进行估计。经验分布 \(\hat{p}_{2}\left(\cdot \mid v_{i}\right)\) 定义为 \(\hat{p}_{2}\left(v_{j} \mid v_{i}\right)=\dfrac{w_{i j}}{d_{i}}\) ，其中 \(w_{ij}\) 为边 \(\left(i, j\right)\) 的权重， \(d_{i}\) 为节点 \(v_i\) 的出度。LINE 中采用 \(d_{i}\) 作为节点的重要性 \(\lambda_i\) ，利用 KL 散度同时忽略一些常量，目标函数定义如下：

\[O_{2}=-\sum_{(i, j) \in E} w_{i j} \log p_{2}\left(v_{j} \mid v_{i}\right) \]

LINE 采用负采样的方式对模型进行优化，同时利用 Alias 方法加速采样过程。
注意：在度较小的情况效果可能不好

3.SDNE

4.Node2vec

5.Struc2vec

参考资料：
b站视频【图神经网络】GNN从入门到精通
几种常见的Graph Embedding方法
图嵌入 (Graph Embedding) 和图神经网络 (Graph Neural Network)
【论文笔记】DeepWalk
【Graph Embedding】DeepWalk：算法原理，实现和应用
论文：
DeepWalk
代码：
GraphEmbedding