不上前十不改名1. 从Weisfeiler-Lehman算法到图卷积网络
我第一次接触Weisfeiler-Lehman(WL)算法是在研究图同构问题的时候。这个1968年提出的经典算法，本质上是通过迭代地聚合节点及其邻居的信息来生成图的"指纹"。有趣的是，当我们把其中的哈希函数替换成可微的神经网络层时，竟然直接得到了图卷积网络(GCN)的雏形。
具体来看，WL算法的核心操作可以表示为：
$$ h^{(t+1)}(v_i) = hash({h^{(t)}(v_i)} \cup {h^{(t)}(v_j)|v_j \in N_i}) $$
这里的hash函数如果换成：
$$ h^{(l+1)} = \sigma(\sum_{j \in N_i} c_{ij}h^{(l)}W^{(l)}) $$
就得到了GCN的传播规则。当选择特定的归一化系数$c_{ij} = 1/\sqrt{d_id_j}$时，这正是Kipf & Welling在2017年提出的经典GCN模型。
关键理解：GCN可以视为WL算法的可微参数化版本。这个视角解释了为什么即使未经训练的GCN也能产生有意义的节点嵌入——因为它继承了WL算法的图结构感知能力。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 节点嵌入的魔法：从随机权重开始
在Zachary空手道俱乐部网络上的实验让我印象深刻。这个经典的社交网络包含34个成员及其互动关系，通常被分成4个社区。实验设置非常简洁：
- 输入特征：仅使用单位矩阵$X=I_N$（即没有人工设计的特征）
- 模型结构：3层GCN，隐藏层维度4，输出维度2
- 权重初始化：Glorot正态分布初始化
令人惊讶的是，即使未经任何训练，这个随机初始化的GCN模型产生的二维嵌入（见图3b）已经展现出明显的社区结构。这与DeepWalk等需要复杂无监督训练的算法效果相当，但计算成本低得多。
python复制# 随机GCN的PyTorch实现示例
import torch
import torch.nn as nn
class UntrainedGCN(nn.Module):
def __init__(self, num_nodes, hidden_dim=4, out_dim=2):
super().__init__()
self.W1 = nn.Parameter(torch.randn(num_nodes, hidden_dim))
self.W2 = nn.Parameter(torch.randn(hidden_dim, hidden_dim))
self.W3 = nn.Parameter(torch.randn(hidden_dim, out_dim))
def forward(self, A_hat, X):
H1 = torch.relu(A_hat @ X @ self.W1)
H2 = torch.relu(A_hat @ H1 @ self.W2)
return A_hat @ H2 @ self.W3
这个现象背后的原理在于：GCN的传播过程本质上是在执行多次的邻域信息聚合，这与WL算法的着色过程异曲同工。即使权重是随机的，图结构信息已经通过邻接矩阵的多次乘法被编码到节点表示中。
3. 半监督学习的动态过程
更精彩的是观察模型在半监督训练过程中嵌入的变化（图4）。我们只用每个类别的一个标签（总共4个标记节点）进行训练：
- 初始化：节点嵌入随机分布
- 早期迭代：社区结构开始显现
- 后期迭代：不同类别节点逐渐线性可分
python复制# 半监督训练的关键代码片段
model = GCN(nfeat=features.shape[1], nhid=16, nclass=num_classes)
optimizer = optim.Adam(model.parameters(), lr=0.01)
def train(epoch):
model.train()
optimizer.zero_grad()
output = model(features, adj)
loss = F.cross_entropy(output[labeled_nodes], labels[labeled_nodes])
loss.backward()
optimizer.step()
这个实验揭示了GCN的两个关键能力：
- 通过图结构传播标签信息（类似标签传播算法）
- 同时学习适合分类任务的节点表示
4. 模型深度与残差连接的实践智慧
在Cora、Citeseer和Pubmed三个标准引文网络上的实验（图5）得出了一些重要结论：
| 层数 | 准确率(%) | 训练难度 |
|---|---|---|
| 1 | 72.3 | 容易 |
| 2 | 81.5 | 中等 |
| 3 | 79.8 | 中等 |
| 5 | 75.2 | 困难 |
| 7+ | 68.4 | 非常困难 |
当模型超过3层时，会出现两个问题：
- 过度平滑（Over-smoothing）：随着层数增加，所有节点的表示会趋向相似
- 梯度消失：信息难以反向传播到早期层
解决方案是引入残差连接：
$$ H^{(l+1)} = \sigma(\hat{A}H^{(l)}W^{(l)}) + H^{(l)} $$
这让我想起在CV领域的ResNet。实际上，我们在实现时可以采用更灵活的Dense连接：
python复制class GCNWithResidual(nn.Module):
def __init__(self, nfeat, nhid, nclass, dropout):
super().__init__()
self.gc1 = GraphConvolution(nfeat, nhid)
self.gc2 = GraphConvolution(nhid, nhid)
self.gc3 = GraphConvolution(nhid, nclass)
self.dropout = dropout
def forward(self, x, adj):
x1 = F.relu(self.gc1(x, adj))
x1 = F.dropout(x1, self.dropout, training=self.training)
x2 = F.relu(self.gc2(x1, adj) + x1) # 残差连接
x2 = F.dropout(x2, self.dropout, training=self.training)
return self.gc3(x2, adj)
5. 实践中的经验与陷阱
经过多次实验，我总结了以下实用建议：
-
归一化是关键
- 对称归一化$\hat{A} = D^{-1/2}AD^{-1/2}$比简单平均更稳定
- 加入自循环$\tilde{A} = A + I$避免信息丢失
-
初始化很重要
- 使用Glorot/Xavier初始化保持方差
- 偏置项初始化为0是安全的选择
-
正则化策略
- 第一层的dropout效果最明显（0.5左右）
- 对第一层权重使用L2正则（5e-4）
- 早停法(early stopping)很有效
-
超参数选择
- 学习率0.01是好的起点
- 隐藏层16-64维通常足够
- 2-3层模型在大多数任务上表现最佳
一个常见的陷阱是特征缩放。与常规神经网络不同，GCN对输入特征的尺度更敏感。我通常会先对特征进行标准化：
python复制from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
features = scaler.fit_transform(features) # 均值0，方差1
另一个容易忽视的细节是稀疏矩阵的实现。对于大规模图，使用稀疏矩阵运算可以显著减少内存消耗：
python复制import scipy.sparse as sp
# 将邻接矩阵转换为COO格式
adj = sp.coo_matrix(adj)
indices = torch.LongTensor(np.vstack((adj.row, adj.col)))
values = torch.FloatTensor(adj.data)
shape = torch.Size(adj.shape)
adj = torch.sparse.FloatTensor(indices, values, shape)
6. 深入理解WL测试与GCN的关系
WL算法之所以与GCN有深刻联系，是因为它们都基于以下两个核心操作：
- 聚合(Aggregate)：收集邻居节点的信息
- 组合(Combine)：将自身信息与邻居信息融合
WL算法使用哈希函数作为组合操作，而GCN使用可学习的线性变换+非线性激活。这种联系帮助我们理解GCN的表达能力上限——它最多与1-WL测试一样强大。
在实际应用中，这意味着：
- GCN可以区分大多数现实世界的图结构
- 但对于某些特殊构造的图，GCN可能失效
- 增加深度不一定提高判别能力（与WL测试的层级有关）
一个改进方向是借鉴更高阶的WL测试，例如：
python复制# 模拟2-WL的聚合策略
def higher_order_aggregate(h, adj, k=2):
# h: node features
# adj: adjacency matrix
# k: order of neighborhood
power_adj = torch.matrix_power(adj, k)
return torch.matmul(power_adj, h)
7. 扩展到其他图学习任务
虽然本文聚焦半监督节点分类，但GCN的思想可以推广到：
- 图分类
- 添加全局池化层(global pooling)
- 使用readout函数生成图级表示
python复制class GraphClassificationGCN(nn.Module):
def __init__(self, nfeat, nhid, nclass):
super().__init__()
self.gc1 = GraphConvolution(nfeat, nhid)
self.gc2 = GraphConvolution(nhid, nhid)
self.pool = nn.AdaptiveAvgPool1d(1) # 全局平均池化
self.fc = nn.Linear(nhid, nclass)
def forward(self, x, adj):
x = F.relu(self.gc1(x, adj))
x = F.relu(self.gc2(x, adj))
x = self.pool(x.transpose(1,2)).squeeze(2)
return self.fc(x)
-
链接预测
- 使用节点表示的内积预测边存在概率
- 负采样训练策略
-
图生成
- 逐步预测节点和边
- 结合变分自编码器(VAE)框架
在实际项目中，我发现GCN特别适合以下场景：
- 数据具有明确的关系结构
- 特征信息有限但关系信息丰富
- 标注成本高（需要半监督学习）
例如在推荐系统中，我们可以将用户和商品视为二部图的节点，用GCN学习它们的联合表示：
python复制# 用户-商品二部图的邻接矩阵
# 行是用户，列是商品
user_item_adj = torch.FloatTensor(num_users, num_items)
# 联合特征矩阵
features = torch.cat([user_features, item_features], dim=0)
# 构建完整的邻接矩阵
adj = torch.zeros(num_users+num_items, num_users+num_items)
adj[:num_users, num_users:] = user_item_adj
adj[num_users:, :num_users] = user_item_adj.t()
8. 前沿发展与未来方向
虽然GCN已经非常强大，但仍有改进空间：
-
注意力机制
- GAT(Graph Attention Network)学习动态邻域权重
- 比固定的归一化系数更灵活
-
异构图神经网络
- 处理多种节点和边类型
- 使用特定类型的参数矩阵
-
动态图神经网络
- 处理随时间演变的图结构
- 结合RNN或时序卷积
-
解释性
- 理解模型学到了什么图模式
- 可视化重要的子结构
最近我在实验的一个有趣方向是"解耦式"GCN，将信息传播和特征变换分开：
python复制class DecoupledGCN(nn.Module):
def __init__(self, nfeat, nhid, nclass, K=2): # K传播步数
super().__init__()
self.propagate = nn.Parameter(torch.ones(K)/K) # 可学习的传播权重
self.mlp = nn.Sequential(
nn.Linear(nfeat, nhid),
nn.ReLU(),
nn.Linear(nhid, nclass)
)
def forward(self, x, adj):
x_prop = x
all_x = [x]
for _ in range(len(self.propagate)):
x_prop = torch.matmul(adj, x_prop)
all_x.append(x_prop)
mixed_x = sum([alpha * x for alpha, x in
zip(F.softmax(self.propagate, dim=0), all_x)])
return self.mlp(mixed_x)
这种设计允许模型自动学习不同传播步数的重要性，在实践中往往能获得更好的鲁棒性。