图嵌入（Graph Embedding）算法原理与应用

图嵌入是一种将图中的节点（或边、子图）映射到低维向量空间的技术，同时保留图的拓扑结构、节点属性和其他信息。生成的向量表示可用于机器学习任务，如节点分类、链接预测和社区发现。本专题将重点介绍经典算法DeepWalk的原理与实现。

一、问题背景与核心思想

1. 图数据的挑战

• 图结构数据（如社交网络、知识图谱）是非欧几里得空间数据，传统机器学习模型（如CNN、RNN）无法直接处理。
• 图嵌入的目标是将节点编码为稠密低维向量（例如100维），使得向量之间的几何关系（如距离、角度）反映原图中的关系。

2. DeepWalk的核心直觉

• 灵感来自词嵌入（Word2Vec）：将图中的节点类比为单词，通过生成随机游走序列，将节点序列视为“句子”，然后使用Word2Vec学习节点向量。
• 关键假设：图中相邻的节点在向量空间中应彼此接近。

二、DeepWalk算法步骤详解

步骤1：生成随机游走序列

1. 输入：无向图 \(G = (V, E)\)，游走长度 \(t\)，每个节点的游走次数 \(\gamma\)。
2. 过程：
   • 对每个节点 \(v_i \in V\)，重复 \(\gamma\) 次：
     • 从 \(v_i\) 出发，进行长度为 \(t\) 的随机游走。每次均匀随机选择当前节点的邻居作为下一步。
   • 示例：对于节点 \(A\)，可能生成游走序列 \([A, B, C, D]\)、\([A, C, E, F]\) 等。
3. 输出：一组随机游走序列集合，每个序列视为一个“句子”。

步骤2：使用Skip-gram模型学习嵌入

1. 目标函数：最大化序列中每个节点与其上下文节点共现的概率。
   • 对于序列中的每个节点 \(v_i\)，定义其上下文窗口大小为 \(w\)（即左右各 \(w\) 个节点）。
   • 目标：给定中心节点 \(v_i\)，预测其上下文节点 \(v_{i-w}, ..., v_{i+w}\)。
2. 模型简化：
   • 使用层次Softmax或负采样（参考Word2Vec）优化计算效率。
   • 最终每个节点学习两个向量：
     • \(\mathbf{v}\)：作为中心节点时的向量。
     • \(\mathbf{u}\)：作为上下文节点时的向量（通常最终使用 \(\mathbf{v}\) 作为节点嵌入）。

步骤3：参数训练

• 通过随机梯度下降（SGD）优化目标函数，更新节点向量。

三、关键参数与优化

1. 游走长度 \(t\)：较长游走捕获全局结构，较短游走偏向局部邻域。
2. 窗口大小 \(w\)：较大窗口使嵌入反映全局相似性，较小窗口聚焦直接邻居。
3. 嵌入维度 \(d\)：通常取64-256维，需平衡表达能力和计算成本。
4. 负采样数量：影响训练效率和嵌入质量，一般取5-20。

四、应用场景与局限性

1. 典型应用

• 节点分类：如预测社交网络中用户的兴趣标签。
• 链接预测：判断图中未连接的节点是否可能存在边。
• 可视化：将节点投影到2D空间观察社区结构。

2. 局限性

• 仅利用拓扑结构，忽略节点属性。
• 均匀随机游走可能无法捕获复杂结构（后续改进如Node2Vec引入偏置游走）。

五、代码实现简例（Python伪代码）

import networkx as nx
from gensim.models import Word2Vec

def deepwalk(G, walks_per_node=10, walk_length=80, embedding_dim=128):
    # 步骤1：生成随机游走序列
    walks = []
    for _ in range(walks_per_node):
        for node in G.nodes():
            walk = [node]
            while len(walk) < walk_length:
                curr = walk[-1]
                neighbors = list(G.neighbors(curr))
                if not neighbors:
                    break
                next_node = random.choice(neighbors)
                walk.append(next_node)
            walks.append(list(map(str, walk)))  # 转换为字符串序列
    
    # 步骤2：训练Word2Vec模型
    model = Word2Vec(sentences=walks, vector_size=embedding_dim, window=5, 
                     sg=1, negative=5, workers=4)
    return model.wv  # 返回节点向量集合

六、总结

DeepWalk通过结合随机游走和语言模型，开创了图嵌入的新思路。其核心是将图序列化，利用成熟的NLP技术学习节点表示。后续算法如Node2Vec、LINE等在此基础上引入了更复杂的游走策略或目标函数，以优化嵌入质量。