学习笔记 - Graph Embedding：DeepWalk 算法
2022-12-20 18:11:18
DeepWalk算法首次将无监督特征学习引入图网络分析，通过截断式随机游走和Skip-Gram模型学习节点的低维嵌入表示，使相似节点在低维空间距离相近。
一、Graph Embedding核心思想
Graph Embedding旨在找到一种映射函数，将图中的每个节点转换为低维稠密的嵌入表示，要求在图中相似的节点在低维空间距离相近。得到的表示向量可用于下游任务，如节点分类、链接预测、可视化等。
二、DeepWalk算法概述
DeepWalk算法通过截断式随机游走（truncated random walk）来学习图网络节点的社区表示（Social Representations），首次将无监督特征学习引入图网络分析中。
三、DeepWalk问题定义
以节点分类问题为例：
- 给定图$G=(V,E)$，其中$V$是节点数，$E$是边数，$E subseteq (V times V)$。
- 给定部分标记的图$G_L=(V,E,X,Y)$，其中$X$是节点的属性，$Y$是节点的标签。
- 目标是学习节点的表示$X_E in mathbb R^{|V| times d}$，其中$d$是较小的嵌入维数。
该方法可捕获与标签分布无关的图网络结构的特征，学得的表示具有通用性，可应用于多种下游任务。
四、可行性及性质分析
DeepWalk算法学得的社区表示具有以下特征：
- 适应性：随着图网络的不断发展，可只学习新的节点信息，不需重复学习过程。
- 社区性：同社区的节点具有相似的表示，即相似的节点在低维嵌入空间距离相近。
- 低维：低维模型可以更好地泛化，降低过拟合风险，并加快收敛和推理速度。
- 连续：连续的嵌入向量使节点表示在社区之间具有平滑的决策边界，从而可以进行更加可靠的分类。
DeepWalk算法的思路是使用Random Walk算法在图网络中进行节点采样，获得了足够的节点访问序列后，使用Word2Vec的Skip-Gram算法进行表示学习。
如上图所示，图(a)来自无标度图网络上的一系列截断性随机游走，图(b)来自英语维基百科的100万条语料。其分布规律满足类似的幂律分布，因此可以将NLP的词向量模型（如Skip-Gram算法）应用在图网络的截断性随机游走中。
五、DeepWalk算法步骤
该算法包含两个主要的步骤：
1. Random Walk算法采样节点序列- 算法思路：在图网络上，从某个特定的节点开始，从与该节点相连的边中随机选择一条移动到下一个节点，重复该过程直到达到窗口大小。是一种可重复访问已访问节点的深度优先遍历算法。
- 主要特征：
可扩展：在后续添加新的信息时，可只学习新的节点信息，无需从头学习。
可并行：可以同时从不同的节点处开始游走。
参考《学习笔记 - Word2Vec：Skip-Gram算法》。
六、效果展示
通过DeepWalk算法获取图网络表示后，使用K-Means算法进行聚类，得到如下实验结果：
实验数据选取了成熟的空手道图网络，设置低维嵌入维度$d=2$，不同颜色代表节点的聚类。可见，将嵌入表示维数压缩至$d=2$的情况下，也取得了较好的聚类效果。
热门标签
