【GNN原理解析】表示学习

表示学习（Representation Learning）是机器学习的核心范式：与其手工设计特征，不如让模型自动学习数据的低维向量表示。在图神经网络中，表示学习的历史可追溯到 Word2Vec 和早期的图嵌入方法（DeepWalk、Node2Vec）。这些方法是 GNN 的思想先驱，理解它们有助于理解 GNN 为何有效。

一、表示学习的动机

1.1 传统方法的局限

在深度学习兴起之前，图上的机器学习任务严重依赖手工设计的特征：

• 节点的度：该节点连接了多少条边
• 聚类系数：节点的邻居间互相连接的程度
• PageRank 值：节点在图中的全局重要性
• 路径统计：节点到其他关键节点的最短路径长度
• 子图计数：节点参与的特定子图（如三角形）的数量

这些手工特征存在严重问题：

1. 设计成本高：每个新任务都需要领域专家设计新特征
2. 不可迁移：为社交网络设计的特征对分子图可能毫无意义
3. 信息瓶颈：手工设计的特征只能捕捉有限维度的信息
4. 无法利用大量未标注数据：传统方法只能利用标注数据进行有监督学习

1.2 表示学习的核心思想

表示学习的目标是学习一个映射函数 f: V → R^d，将图中的每个节点映射到一个低维稠密向量空间（通常 d << |V|），使得在这个向量空间中，结构相似的节点距离近。即：

f: v ↦ z_v ∈ R^d

这个向量 z_v 就是节点 v 的嵌入（embedding）。一个好的嵌入应满足：

• 低维性：d 通常在 64-256 之间，远小于图的节点数 |V|
• 稠密性：向量的每个维度都有信息（不像 one-hot 编码那么稀疏）
• 语义性：语义相似的节点在嵌入空间中距离近，语义相异的节点距离远
• 可迁移性：相同的嵌入可用于多种下游任务（分类、聚类、链接预测、可视化）

二、Word2Vec 回顾

DeepWalk 和 Node2Vec 的核心思想来自 Word2Vec。理解 Word2Vec 是理解图嵌入方法的前提。

2.1 语言模型与分布式表示

传统 NLP 使用 one-hot 编码表示词汇：每个词是一个 |V|-维的 0/1 向量。问题：one-hot 向量无法表示词汇间的语义相似性（”猫”和”狗”的 one-hot 向量与”猫”和”电脑”的 one-hot 向量完全一样”远”）。

Word2Vec 通过预测任务学习词的分布式表示（distributed representation）：每个词被表示为 d 维稠密向量（通常 d = 100-300）。

2.2 Skip-gram 模型

Skip-gram 的核心思想：用一个词 w_t 预测其上下文词 w_{t-c}, …, w_{t+c}。

目标函数：

最大化平均对数概率：
(1/T) * Σ_{t=1}^T Σ_{-c≤j≤c, j≠0} log P(w_{t+j} | w_t)

其中 P(w_O | w_I) 使用 softmax 定义：

P(w_O | w_I) = exp(v'_wO · v_wI) / Σ_{w=1}^W exp(v'_w · v_wI)

• v_wI：词 w_I 作为”输入词”时的嵌入向量（输入向量）
• v’_wO：词 w_O 作为”输出词”时的嵌入向量（输出向量）

问题：分母需要对整个词汇表 W 求和（通常 |W| > 10^5），计算量太大。

2.3 负采样（Negative Sampling）

为了缓解 softmax 的计算瓶颈，Mikolov 等人提出了负采样：

log σ(v'_wO · v_wI) + Σ_{i=1}^k E_{w_i~P_n(w)} [log σ(-v'_wi · v_wI)]

其中：

• σ(x) = 1 / (1 + exp(-x))：sigmoid 函数
• k：负样本数量（通常 k = 5-20）
• P_n(w)：负样本分布（通常使用词频的 3/4 次幂：P_n(w) ∝ U(w)^{3/4}）

直觉：正样本（真实上下文词）应该与输入词的内积大（sigmoid 输出接近 1），负样本（随机采样词）的内积应该小（sigmoid 输出接近 0）。这本质上是一个二分类问题，计算量从 O(|W|) 降到了 O(k)。

2.4 层级 Softmax（Hierarchical Softmax）

另一种加速方案：将所有词汇构造成一棵霍夫曼树（Huffman Tree），叶子节点是词汇，每个非叶子节点是一个二分类器。计算 P(w_O | w_I) 只需沿树路径计算 log_2(|W|) 次二分类。DeepWalk 正是使用层级 Softmax 作为优化目标。

# Word2Vec Skip-gram 的核心实现（简化版）
import torch
import torch.nn as nn

class SkipGram(nn.Module):
    def __init__(self, vocab_size, embed_dim):
        super().__init__()
        self.in_embed = nn.Embedding(vocab_size, embed_dim)   # 输入嵌入
        self.out_embed = nn.Embedding(vocab_size, embed_dim)  # 输出嵌入

    def forward(self, center_word, context_word, negative_samples):
        # center_word: 目标词索引
        # context_word: 正样本上下文词索引
        # negative_samples: 负样本词索引

        center_embed = self.in_embed(center_word)       # (batch, embed_dim)
        pos_embed = self.out_embed(context_word)         # (batch, embed_dim)
        neg_embed = self.out_embed(negative_samples)     # (batch, num_neg, embed_dim)

        # 正样本得分
        pos_score = torch.sum(center_embed * pos_embed, dim=1)  # (batch,)
        pos_loss = -torch.log(torch.sigmoid(pos_score) + 1e-10).mean()

        # 负样本得分
        neg_score = torch.bmm(neg_embed, center_embed.unsqueeze(2)).squeeze(2)  # (batch, num_neg)
        neg_loss = -torch.log(torch.sigmoid(-neg_score) + 1e-10).sum(dim=1).mean()

        return pos_loss + neg_loss

三、DeepWalk：图上的 Skip-gram

3.1 核心思想

DeepWalk（Perozzi et al., KDD 2014）是第一个将 Word2Vec 思想应用于图嵌入的方法。它的核心洞察是：

图中节点的出现模式与自然语言中的词的出现模式高度相似。

具体来说：

• 自然语言中，词按序列排列，Skip-gram 用中心词预测上下文词
• 图中没有天然的顺序，但如果我们通过随机游走生成节点序列，这些序列中节点的出现模式确实遵循幂律分布 —— 这与自然语言中词频的幂律分布（齐夫定律，Zipf’s Law）类似

3.2 算法流程

DeepWalk 算法：
1. 输入：图 G = (V, E)，嵌入维度 d，每节点游走次数 γ，游走长度 t，窗口大小 w
2. 从每个节点 v ∈ V 开始，执行 γ 次随机游走，每次长度为 t
3. 将所有游走序列作为"语料"，每一行为一个随机游走序列
4. 使用 Skip-gram + 层级 Softmax 训练节点嵌入
5. 输出：每个节点 v 的 d 维嵌入向量 z_v

import random
import numpy as np

def random_walk(graph, start_node, walk_length):
    """
    从 start_node 出发，随机游走 walk_length 步
    graph: dict，邻接表 {node: [neighbors]}
    """
    walk = [start_node]
    current = start_node
    for _ in range(walk_length - 1):
        neighbors = graph.get(current, [])
        if not neighbors:
            break
        current = random.choice(neighbors)
        walk.append(current)
    return walk

def generate_walks(graph, num_walks_per_node, walk_length):
    """从图中每个节点生成指定数量的随机游走序列"""
    nodes = list(graph.keys())
    walks = []
    for _ in range(num_walks_per_node):
        random.shuffle(nodes)
        for node in nodes:
            walks.append(random_walk(graph, node, walk_length))
    return walks

# 示例
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2],
    4: [2],
}
walks = generate_walks(graph, num_walks_per_node=5, walk_length=10)
print(f"生成 {len(walks)} 个随机游走序列")
print(f"示例序列: {walks[0]}")

3.3 DeepWalk 的优化目标

给定随机游走序列 (v_1, v_2, …, v_T)，DeepWalk 最大化：

max Σ_{t=1}^T Σ_{-w≤j≤w, j≠0} log P(v_{t+j} | v_t)

其中 P(v_j | v_i) 使用层级 Softmax 建模：

P(v_j | v_i) = Π_{l=1}^{L(v_j)-1} σ( [n(v_j, l+1) = ch(n(v_j, l))] · u^T_{n(v_j,l)} v_i )

这里每个节点 v_j 在霍夫曼树中对应一条路径，路径上的每个非叶子节点 n(v_j, l) 有一个可学习的向量 u。[condition] 在 condition 为真时取 +1，为假时取 -1。

3.4 使用 PyG 中的 Node2Vec

PyG 提供了 Node2Vec 的统一实现（Node2Vec 包含 DeepWalk 作为 p=1, q=1 的特例）：

from torch_geometric.nn import Node2Vec

# 加载数据
from torch_geometric.datasets import Planetoid
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

# Node2Vec 模型
model = Node2Vec(
    edge_index=data.edge_index,
    embedding_dim=128,
    walk_length=20,
    context_size=10,         # 窗口大小
    walks_per_node=10,
    num_negative_samples=5,  # 负采样数
    p=1.0, q=1.0,            # p=q=1 就是 DeepWalk
    sparse=True
)

# 训练
optimizer = torch.optim.SparseAdam(model.parameters(), lr=0.01)
loader = model.loader(batch_size=128, shuffle=True, num_workers=4)

model.train()
for epoch in range(100):
    total_loss = 0
    for pos_rw, neg_rw in loader:
        optimizer.zero_grad()
        loss = model.loss(pos_rw, neg_rw)
        loss.backward()
        optimizer.step()
        total_loss += loss.item()
    if epoch % 20 == 0:
        print(f"Epoch {epoch}, Loss: {total_loss:.4f}")

# 获取嵌入
embeddings = model().detach()   # shape: (num_nodes, embedding_dim=128)

四、Node2Vec：有偏随机游走

4.1 从 DeepWalk 到 Node2Vec

DeepWalk 使用无偏随机游走（每一步等概率选择邻居）。Node2Vec（Grover & Leskovec, KDD 2016）引入了有偏随机游走，通过两个超参数 p 和 q 控制游走策略：

• p（Return parameter）：控制回退的概率。较小的 p 鼓励游走在局部区域来回探索。
• q（In-out parameter）：控制向外的概率。较小的 q 鼓励游走远离起始节点（DFS-like），较大的 q 鼓励游走留在局部邻域（BFS-like）。

4.2 二阶随机游走

设游走刚从节点 t 到达节点 v，现在要从 v 选择下一步走向节点 x。转移概率为：

π_vx = α_pq(t, x) · w_vx

其中非归一化转移权重：
α_pq(t, x) = {
    1/p   if d_tx = 0    (x = t，即回退)
    1     if d_tx = 1    (x 是 t 的邻居)
    1/q   if d_tx = 2    (x 不是 t 的邻居)
}

其中 d_tx 是节点 t 到 x 的最短路径距离。

直观理解：

• p < 1：游走倾向于回退，产生”来回探索”的微观模式 → BFS-like，捕捉局部结构（同质性）
• q < 1：游走倾向于远离起点 → DFS-like，捕捉全局结构（结构等效性）
• q > 1：游走倾向于留在局部 → BFS-like

def node2vec_walk(graph, start_node, walk_length, p, q):
    """
    基于 Node2Vec 的二阶随机游走
    """
    walk = [start_node]
    if len(walk) == 1:
        # 第一步：无偏随机游走（没有 t 参考）
        current = start_node
        next_node = random.choice(graph[current])
        walk.append(next_node)
        current = next_node

    for _ in range(2, walk_length):
        prev = walk[-2]   # t
        curr = walk[-1]   # v

        neighbors = graph[curr]
        if not neighbors:
            break

        # 计算每个邻居的非归一化转移概率
        probs = []
        for neighbor in neighbors:
            if neighbor == prev:           # d_tx = 0：回退
                probs.append(1.0 / p)
            elif prev in graph.get(neighbor, []):  # d_tx = 1：邻居的邻居
                probs.append(1.0)
            else:                          # d_tx = 2：远离
                probs.append(1.0 / q)

        # 归一化
        probs = np.array(probs)
        probs /= probs.sum()

        current = np.random.choice(neighbors, p=probs)
        walk.append(current)
        current = walk[-1] if len(walk) > 1 else current

    return walk

4.3 BFS vs DFS 的特征捕捉

游走模式	超参数	捕捉的特征	适用场景
BFS-like	p < 1, q > 1	同质性（Homophily）：结构相邻的节点嵌入相似	社交网络中朋友推荐
DFS-like	q < 1	结构等效性（Structural Equivalence）：有相似图角色的节点嵌入相似，即使它们距离很远	网络中”桥节点”的检测

示例：在社交网络中，两个不同城市的”意见领袖”可能结构等效（都有很多追随者、都是社区桥梁），但它们的图距离很远。Node2Vec 的 DFS 模式能捕捉这种结构等效性。

五、LINE：大规模网络嵌入

5.1 一阶邻近度（First-order Proximity）

LINE（Tang et al., WWW 2015）定义了一阶邻近度和二阶邻近度。一阶邻近度即两个节点之间的边权重：

P_1(v_i, v_j) = 1 / (1 + exp(-u_i^T u_j))    # sigmoid 概率
P̂_1(v_i, v_j) = w_ij / Σ_{(a,b)∈E} w_ab        # 经验概率（归一化边权重）

一阶邻近度的优化目标（最小化 KL 散度）：

O_1 = - Σ_{(i,j)∈E} w_ij log P_1(v_i, v_j)

一阶邻近度的局限性：它只能捕捉直接相连的节点间的相似性，无法捕捉”有共同邻居但不相连”的节点间的相似性。

5.2 二阶邻近度（Second-order Proximity）

二阶邻近度通过节点的共享邻居来衡量相似性：如果两个节点有相似的邻居分布，那么它们应该是相似的。

P_2(v_j | v_i) = exp(u'_j^T u_i) / Σ_{k=1}^{|V|} exp(u'_k^T u_i)
P̂_2(v_j | v_i) = w_ij / d_i        # 经验概率

二阶邻近度的优化目标（最小化 KL 散度）：

O_2 = - Σ_{(i,j)∈E} w_ij log P_2(v_j | v_i)

二阶邻近度使用负采样加速：与 Word2Vec 的负采样类似，每条边采样 k 个负样本。

5.3 LINE 与 DeepWalk/Node2Vec 的关系

• LINE 明确地定义和优化了一阶和二阶邻近度，数学上更清晰
• DeepWalk/Node2Vec 通过随机游走隐式地优化了高阶邻近度（游走长度 T 内的对称）
• 实验表明 DeepWalk 等价于对矩阵 M = log(A^2 + A^3 + … + A^T) 的矩阵分解
• LINE 的训练速度更快（不需要生成游走序列），但 DeepWalk/Node2Vec 通常质量更好

六、其他经典图嵌入方法

6.1 SDNE（Structural Deep Network Embedding）

SDNE（Wang et al., KDD 2016）使用深度自编码器进行图嵌入。它结合了一阶邻近度（Laplacian Eigenmaps 监督项）和二阶邻近度（自编码器重建损失）：

L = L_2nd + α L_1st + ν L_reg

L_2nd = Σ_i ||(x̂_i - x_i) ⊙ b_i||^2    # 二阶：邻接向量重建
L_1st = Σ_{(i,j)∈E} s_ij ||y_i - y_j||^2  # 一阶：相似节点嵌入相近

其中 x_i 是节点 i 的邻接向量，y_i 是自编码器的隐层表示。

6.2 TransE：知识图谱嵌入

TransE（Bordes et al., NeurIPS 2013）是知识图谱嵌入的代表方法，核心假设：

h + r ≈ t

即头实体向量 h 加上关系向量 r 应接近尾实体向量 t。

评分函数：

f(h, r, t) = -||h + r - t||_{L1/L2}

损失函数（margin-based ranking loss）：

L = Σ_{(h,r,t)∈S} Σ_{(h',r,t')∈S'} [γ + f(h,r,t) - f(h',r,t')]_+

其中 S’ 是负样本（替换头实体或尾实体），γ 是 margin。TransE 简单但有效，是 KG 嵌入的奠基性工作。后续的 TransH、TransR、RotatE 等模型都是对 TransE 的扩展。

6.3 Metapath2Vec：异构图嵌入

Metapath2Vec（Dong et al., KDD 2017）处理异构图（有多种类型节点和边的图）。核心创新是在随机游走中使用元路径（metapath）约束游走方向。

例如，学术网络中的元路径”作者-论文-会议”（APA）规定了游走必须按”作者→论文→会议→论文→…”的模式进行，确保生成的序列包含有意义的语义结构。

七、从表示学习到 GNN 的演进

7.1 传统图嵌入的局限

局限	说明
直推式（Transductive）	必须看到所有节点才能训练，无法泛化到新节点
无节点特征	仅利用图结构，不能利用节点本身的属性信息
无端到端训练	嵌入与下游任务分离（先训嵌入，再接分类器），无法端到端优化
参数量大	每个节点有独立的嵌入向量，参数量 O(
无归纳能力	新节点加入时需重新训练

7.2 GNN 如何解决这些问题

GNN 通过消息传递机制实现归纳式（Inductive）节点表示：

• GNN 学习的是聚合函数而非节点特定的嵌入
• 聚合函数的参数在整个图中共享，参数量 O(d^2) 而非 O(|V|·d)
• 节点特征（如文本、属性）作为初始输入，与图结构共同驱动表示学习
• 新节点加入时，只需将其特征和图结构输入训练好的 GNN 即可获得嵌入（无需重新训练）

这也就是为什么 GCN、GAT、GraphSAGE 等模型在现代图机器学习中远超 DeepWalk/Node2Vec 等传统嵌入方法的原因。

---

八、PyG 完整实现：Cora 上的 Node2Vec + 分类

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import Node2Vec
from torch_geometric.datasets import Planetoid
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score

# 1. 加载数据
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

# 2. 训练 Node2Vec
device = 'cuda' if torch.cuda.is_available() else 'cpu'
model = Node2Vec(
    edge_index=data.edge_index,
    embedding_dim=128,
    walk_length=20,
    context_size=10,
    walks_per_node=10,
    num_negative_samples=5,
    p=1.0, q=1.0,   # DeepWalk 参数
    sparse=True
).to(device)

optimizer = torch.optim.SparseAdam(model.parameters(), lr=0.01)
loader = model.loader(batch_size=128, shuffle=True, num_workers=4)

for epoch in range(1, 101):
    model.train()
    total_loss = 0
    for pos_rw, neg_rw in loader:
        optimizer.zero_grad()
        loss = model.loss(pos_rw.to(device), neg_rw.to(device))
        loss.backward()
        optimizer.step()
        total_loss += loss.item()
    if epoch % 20 == 0:
        print(f'Epoch: {epoch:03d}, Loss: {total_loss:.4f}')

# 3. 获取嵌入并下游分类
model.eval()
with torch.no_grad():
    embeddings = model().cpu().numpy()

# 用 Logistic Regression 评估嵌入质量
X_train = embeddings[data.train_mask]
y_train = data.y[data.train_mask].numpy()
X_test = embeddings[data.test_mask]
y_test = data.y[data.test_mask].numpy()

clf = LogisticRegression(max_iter=1000, multi_class='auto')
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print(f'Node2Vec + LogisticRegression Test Accuracy: {accuracy_score(y_test, y_pred):.4f}')

---

面试/自查问题

Q1：DeepWalk 的图嵌入方法本质是什么？

DeepWalk 等价于对某个矩阵 M 的隐式矩阵分解。具体来说，DeepWalk 近似的矩阵是：

M = log( vol(G) · (1/T) Σ_{t=1}^T (D^{-1} A)^t · D^{-1} )

其中 (D^{-1} A)^t 是 t 步随机游走的转移矩阵。这表明 DeepWalk 本质上是在分解一个包含了图的 T 步内所有随机游走概率的矩阵。

Q2：Node2Vec 的 p 和 q 参数如何影响嵌入？

• p < 1：偏好”回退”到来源节点，导致游走在局部来回 → 嵌入更注重局部社区结构
• p > 1：避免回退，鼓励探索新区域 → 更少回头
• q < 1：偏好深入探索（DFS-like），远离起始点 → 捕捉结构等效性
• q > 1：偏好局部探索（BFS-like）→ 捕捉同质性

当 p = q = 1 时，Node2Vec 退化为 DeepWalk。

九、图嵌入方法的理论联系

9.1 矩阵分解视角

许多图嵌入方法可以统一为矩阵分解框架。设我们要分解的矩阵为 M，嵌入 U 满足 M ≈ U·U^T 或 M ≈ U·V^T：

方法	分解的矩阵 M	说明
Laplacian Eigenmaps	L (拉普拉斯矩阵)	使用最小特征向量
GF (Graph Factorization)	A (邻接矩阵)	最早的方法
GraRep	log(A^k / α) - log β	捕获 k 阶邻近度
HOPE	各种相似性矩阵 (Katz, RPR, …)	通用高阶邻近度
DeepWalk	log( (1/T) Σ_{t=1}^T (D^{-1}A)^t D^{-1} )	截断随机游走的对数
Node2Vec	log( (1/T) Σ_{t=1}^T P_{p,q}^t D^{-1} )	有偏随机游走的对数

9.2 NetMF 对 DeepWalk 的统一

Qiu et al. (WSDM 2018) 在 NetMF 中严格证明了 DeepWalk 隐式分解的矩阵是：

M = log( max( (vol(G) / bT) · (Σ_{r=1}^T P^r) D^{-1}, 1 ) )

其中 P = D^{-1}A 是随机游走转移矩阵，b 是负采样数，T 是游走窗口大小。这一发现使得我们可以通过 SVD 直接计算 DeepWalk 的嵌入，而不需要消耗时间的随机游走 + Skip-gram 训练。

9.3 嵌入评估协议

图嵌入的质量通常通过下游任务评估：

节点分类（Node Classification）：

• 使用嵌入作为 logistic regression / SVM 的输入特征
• 在 Cora/CiteSeer/PubMed 上报告 Micro-F1 或 Accuracy
• 使用标准的 train/val/test 划分（每类 20 个标记样本）

链接预测（Link Prediction）：

• 随机遮蔽一定比例的边作为测试集
• 使用嵌入计算节点对的相似性（内积、余弦相似度）
• 报告 AUC-ROC 或 Hits@K

聚类（Clustering）：

• 对嵌入执行 K-means
• 报告 NMI（Normalized Mutual Information）

十、从传统图嵌入到 GCN：平滑过渡

10.1 消息传递统一的视角

传统图嵌入和 GNN 都可以用”消息传递”的框架来理解：

• DeepWalk：消息 = 随机游走路径中出现的 co-occurrence 统计；聚合 = Skip-gram 的梯度更新
• GCN：消息 = 邻居的特征向量 × 可学习权重；聚合 = 归一化求和

关键区别：GCN 的消息和聚合是端到端可微的，而传统嵌入方法不是。

10.2 为什么 GNN 几乎总是优于传统嵌入

在 Cora 数据集上的典型表现对比：

方法	测试准确率	参数量
DeepWalk (128d)	~67%	O(
Node2Vec (128d)	~71%	O(
GCN (2 layers, 16d)	~81%	O(d·H) + O(H·C) = 1.4k·16 = 22k
GAT (2 layers, 8 heads)	~83%	~100k

GCN 在参数量减少 100 倍的情况下仍然大幅优于 DeepWalk/Node2Vec。差距来自：GCN 利用了节点内容特征（Cora 中每个节点有 1,433 维 TF-IDF 文本特征），而传统嵌入方法忽略了这些信息。

优势：训练简单，不需要节点特征，小图上非常高效，可解释性强（嵌入=矩阵分解）。

劣势：

• 直推式（无法泛化到新节点）
• 无法利用节点特征（属性信息被忽略）
• 不能端到端训练（嵌入和下游任务分离）
• 参数量大（O(|V|d)），大规模图不可行
• 新节点加入需重训练或近似（如通过邻居嵌入的聚合）

在现代实践中，对于有节点特征的图（如引文网络的文本特征、分子图的原子特征），GNN 几乎总是优于传统嵌入方法。