从Weisfeiler-Lehman算法到图卷积网络(GCN)的演进与实践

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算法的图结构感知能力。

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_