草稿

好呀 👍 我来举一个具体的小例子，帮你直观理解 WL 测试是怎么迭代更新节点特征（颜色）的。

🌳 示例图

假设有一个小图：

    A
   / \
  B   C

• 初始节点特征：
  • A: red
  • B: blue
  • C: blue

1️⃣ 初始状态 (Iteration 0)

• WL 测试开始时，每个节点用自己的初始特征（颜色）作为标签：
  • A: red
  • B: blue
  • C: blue

2️⃣ 第 1 轮更新 (Iteration 1)

规则：新标签 = 节点自己的颜色 + 邻居颜色的集合 （然后哈希成一个新的颜色/编码）

• A 的邻居是 {B, C} = {blue, blue} → 新标签 = (red, {blue, blue})
• B 的邻居是 {A} = {red} → 新标签 = (blue, {red})
• C 的邻居是 {A} = {red} → 新标签 = (blue, {red})

更新后：

• A: 新颜色 α
• B: 新颜色 β
• C: 新颜色 β

3️⃣ 第 2 轮更新 (Iteration 2)

继续相同规则：

• A 的邻居是 {B, C} = {β, β} → 新标签 = (α, {β, β})
• B 的邻居是 {A} = {α} → 新标签 = (β, {α})
• C 的邻居是 {A} = {α} → 新标签 = (β, {α})

更新后：

• A: 新颜色 γ
• B: 新颜色 δ
• C: 新颜色 δ

🔎 观察结果

• WL 的作用：它让节点的标签逐步编码了“以自己为根的邻居子树结构”。
  • A 的标签区分了“自己 + 两个相同邻居”。
  • B 和 C 的标签相同，因为它们对称，结构一样。
• 图区分性：如果换一个图（比如 B 和 C 不一样颜色），WL 会在某一轮产生不同的标签，从而区分两个图是否同构。

🤝 和 GIN 的联系

• 在 GIN 中，更新公式是： $h_v^{(k)} = \text{MLP}\Big((1+\epsilon)h_v^{(k-1)} + \sum_{u\in N(v)} h_u^{(k-1)}\Big)$
• 这正好对应 WL 的“自己标签 + 邻居标签集合”，只不过：
  • WL 用哈希函数更新 → 只能得到离散的“颜色”。
  • GIN 用 MLP → 得到连续向量，可以学习结构相似性。

要不要我再给你举一个 对比例子：用 WL 测试看看两个“非同构”的图（比如一条三节点链 vs 三角形）是如何在第二轮被区分开的？