想象一家高端拼图工厂的质检流水线。老师傅老李有个绝活：给他两堆散落的拼图碎片，他能判断这两堆碎片是不是来自同一幅画。无论碎片怎么重新编号、怎么换个位置摆放，只要拼起来完全一样，他就盖章「同构」。可工厂每天要验上万堆拼图，一块一块对着拼太慢了。老李的办法很朴素：给每块拼图盖一个特征章，然后反复观察邻居的章——把周围邻居的章颜色汇总起来，给自己更新一个新章。戳一轮不够，就多戳几轮。这，就是 Weisfeiler-Lehman（WL）测试的雏形。今天要讲的 GIN 图同构网络，本质上就是把「盖章—看邻居—再盖章」的过程，改造成一台可以学习、可以反向传播的神经网络。本文会带你一步步拆开 GIN：它为何能逼近老李的眼力，又和 GCN、GAT 两位「年轻同事」差在哪儿。

岗位关联

掌握 GIN 与 WL 测试的等价性，能让你在设计图神经网络时判断：这个模型到底能不能分清我关心的图结构差异。做分子性质预测、社交网络分析时，这份「眼力」就是少走弯路的关键。

目录
  1. 可视化演示
  2. 图同构问题：两堆拼图是否同源
  3. WL测试原理：反复盖章的鉴定术
  4. GIN消息聚合：可学习的盖章机
  5. 表达能力分析：为什么求和最接近万能
  6. GCN/GAT对比：其他质检员的章法
  7. 应用与选型：把对的人派到对的线
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示Cursor AI编辑器的Chat+Edit交互模式，包括自然语言指令解析、AI代码生成、差异预览与一键应用，直观理解AI辅助编程的实时编辑流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

Cursor Chat+Edit 模式 Chat指令：自然语言描述需求，AI解析意图并生成代码修改 差异预览：高亮显示新增/删除/修改的代码行，开发者审阅后确认 一键应用：接受AI建议，代码自动插入编辑器光标位置 Edit = Chat(prompt) → AI_Generate(code) → Diff(review) → Apply Chat+Edit模式实现自然语言驱动的代码编辑

图同构问题：两堆拼图是否同源

回到质检流水线。老李收下两堆拼图碎片后，第一步不是数碎片数量，而是先随手给它们标个号——比如按颜色分成红、蓝、绿。可编号方式千千万，你怎么知道这两堆碎片是按同一种方式编的号？在图论里，这种「换个编号就一模一样」的关系就叫图同构。如果两个图的节点之间能建立一一对应，且原本相连的节点在新的对应下依然相连、原本不相连的依然不相连，那它们就是同构的。

用邻接矩阵来表达这个条件最清晰：邻接矩阵记录着「每对节点之间有没有边」。如果存在一个置换矩阵 P，能把图 1 的边关系完全「搬运」成图 2 的边关系，就说明两张图本质相同：

判定图同构是计算理论里著名的难题：它既没被证明能在多项式时间内解决，也没被证明是 NP 完全问题，而是悬而未决的「中间地带」。对几千个节点的图，暴力尝试所有编号排列是阶乘级别的代价，GPU 也扛不住。所以现实中需要的是高效的「近似判定法」——不求 100% 准确，但求又快又稳定。老李当然也不会一张张试，他需要一套对编号不敏感的盖章流程。下一节，我们就来看这套流程如何运转。

G1≅G2  ⟺  ∃P:A2=PA1PTG_1 \cong G_2 \iff \exists P : A_2 = P A_1 P^{\mathsf{T}}
这个式子说的是：图 1 和图 2 同构，当且仅当能找到一种「重新排列节点编号」的方式，让两者的邻接矩阵完全重合。
  1. 同构符号$G_1 \cong G_2$ 表示两个图在结构上完全等价，像两堆拼图只是摆放顺序不同。
    ≅\cong
  2. 置换矩阵$P$ 是一个只交换行列顺序的矩阵，乘上它相当于把拼图块的编号重新打乱。
    A2=PA1PTA_2 = P A_1 P^{\mathsf{T}}
  3. 存在性量词$\exists P$ 强调「只要存在一种打乱方式」就能对齐，而不是要求所有方式都对齐。
    ∃P\exists P

WL测试原理：反复盖章的鉴定术

老李的盖章法并不直接关心编号。他先给每块拼图发一个初始章，比如按颜色标成 0 或 1；然后他做了一件关键的事：反复「读邻居的章」。每一轮，他都把某块碎片自己的章和它所有邻居的章抄成一张小纸条，再按这张纸条生成一个新章盖上去。等到所有章都不再变化，他就收集两堆碎片的盖章统计表，对比是否一致。这套流程就是 WL 测试。

WL 测试每一轮的更新规则写成公式就是：

WL 测试每轮对每个节点做同样的操作，总复杂度随边数线性增长，且对节点编号完全无感——无论你先把哪块碎片拿起来，只要邻居关系一样，结果就一样。但它不是完全可靠的判官：如果两堆碎片的盖章统计始终相同，只能说明「没找到区分它们的证据」，不能说它们一定同构；反过来，只要统计不同，就铁定非同构。老李的这套流程，后来成了所有图神经网络的理论标尺，而 GIN 的目标就是把这套本领完整装进神经网络。

hv(k)=hash⁡(hv(k−1), { ⁣{hu(k−1):u∈N(v)} ⁣})h_v^{(k)} = \operatorname{hash}\left(h_v^{(k-1)},\ \{\!\{ h_u^{(k-1)} : u \in \mathcal{N}(v) \}\!\}\right)
双重花括号表示「多重集」：它关心每个标签出现几次，而不只是有哪几种。这正是 WL 测试能捕捉「数量」信息的钥匙。
  1. 初始标签$h_v^{(0)}$ 是节点 $v$ 最初的章，通常取节点自带的属性或统一的占位值。
    hv(0)=atomic⁡(v)h_v^{(0)} = \operatorname{atomic}(v)
  2. 邻居多重集$\{\!\{ h_u^{(k-1)} : u \in \mathcal{N}(v) \}\!\}$ 把所有邻居上一轮的章收集起来，重复的章也要记录次数。
    Mv(k)={ ⁣{hu(k−1):u∈N(v)} ⁣}M_v^{(k)} = \{\!\{ h_u^{(k-1)} : u \in \mathcal{N}(v) \}\!\}
  3. 哈希更新$\operatorname{hash}(\cdot)$ 把「自己原来的章 + 邻居章的清单」压缩成一个新标签，充当盖章机。
    hv(k)=hash⁡(hv(k−1),Mv(k))h_v^{(k)} = \operatorname{hash}\big(h_v^{(k-1)}, M_v^{(k)}\big)
  4. 收敛判定两图各自的标签多重集完全相同时停止，再比较最终统计是否一致。
    Multiset(h(k)[V1])=?Multiset(h(k)[V2])\mathrm{Multiset}(h^{(k)}[V_1]) \stackrel{?}{=} \mathrm{Multiset}(h^{(k)}[V_2])

GIN消息聚合：可学习的盖章机

老李的章是手工搓出来的——理论上精妙，但没法自动化。GIN（Graph Isomorphism Network，图同构网络）的聪明之处，是把 WL 测试里「哈希函数」这个黑箱子，替换成神经网络中常见的 MLP（多层感知机）。章不再是人工设计，而是从数据里学出来的。

GIN 第 $k$ 层的更新规则如下：

为什么 (1+ε) 不用够大？理论证明：哪怕 $\varepsilon = 0$，GIN 依然与 WL 测试在区分能力上等价。$\varepsilon$ 只是一个「自身权重旋钮」，真正决定表达力上限的，是求和聚合与 MLP 的组合。对老李来说，GIN 相当于一个学徒：盖章配方交给万能函数去学习，但学完之后的逻辑和老李如出一辙——自己的章加邻居的章，一起搅匀。老李听了都点头：学得还挺像。

hv(k)=MLP⁡(k)((1+ε(k)) hv(k−1)+∑u∈N(v)hu(k−1))h_v^{(k)} = \operatorname{MLP}^{(k)}\left((1+\varepsilon^{(k)})\, h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}\right)
这个公式可以读作：新章 = MLP（自己放大一点点后的旧章 + 所有邻居的章的总和）。求和是灵魂，MLP 是学会怎么盖章的大脑。
  1. 自身加权项$(1+\varepsilon^{(k)})\, h_v^{(k-1)}$ 表示给自己原来的章加一个可调节的权重，$\varepsilon$ 可以是 0、固定常数或可学习参数。
    (1+ε(k)) hv(k−1)(1+\varepsilon^{(k)})\, h_v^{(k-1)}
  2. 邻居求和$\sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}$ 把邻居的章逐一相加，重复的邻居自然多算一次，数量信息全保留。
    ∑u∈N(v)hu(k−1)\sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}
  3. 组合输入两项相加后，构成了「自己 + 邻居」的完整证据，交给下一步的映射函数。
    (1+ε(k)) hv(k−1)+∑u∈N(v)hu(k−1)(1+\varepsilon^{(k)})\, h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}
  4. MLP 映射$\operatorname{MLP}^{(k)}(\cdot)$ 是带激活函数的多层感知机，扮演 WL 测试中哈希函数的角色，把证据压缩成新章。
    MLP(k)(⋅)\mathrm{MLP}^{(k)}(\cdot)
  5. 逐层迭代$h_v^{(k)}$ 是第 $k$ 轮后的新章，整个图的所有节点同步更新，进入下一轮。
    hv(k)=MLP⁡(k)(⋅)h_v^{(k)} = \operatorname{MLP}^{(k)}(\cdot)

表达能力分析：为什么求和最接近万能

既然 GIN 是在模仿老李，那它模仿得到底像不像？答案藏在「求和」这个朴素操作里。假设一个中心节点有两种情况：它有两个特征为 1 的邻居，或者它有三个特征为 1 的邻居。两种情况下，三种常见聚合方式的表现截然不同：

为什么求和是关键？因为平均会把「出现几次」抹平，最大只保留「最突出的那个」，而求和一字不差地保留了多重集的全部构成信息——出现几次就算几次。2019 年 Xu 等人证明了一个更强的结论：只要 MLP 足够强大，采用求和聚合的 GIN，区分图结构的能力与一维 WL 测试完全相当。换句话说，老李的眼力上限，GIN 都能学会；而 GCN、GAT 连老李的平替都算不上。回到车间教训：章可以印淡，但不能印丢。求和，是唯一不会把数量信息印丢的盖章方式。

sum⁡({1,1})=2≠3=sum⁡({1,1,1});mean⁡({1,1})=1=mean⁡({1,1,1});max⁡({1,1})=1=max⁡({1,1,1})\operatorname{sum}(\{1,1\}) = 2 \neq 3 = \operatorname{sum}(\{1,1,1\});\quad\operatorname{mean}(\{1,1\}) = 1 = \operatorname{mean}(\{1,1,1\});\quad\max(\{1,1\}) = 1 = \max(\{1,1,1\})
求和把「邻居到底有几个」记进结果里，平均和最大则把数量抹掉了。这就是 GIN 与 GCN 表达力差距的根源。
  1. 求和聚合$\operatorname{sum}$ 对邻居特征直接相加，$\{1,1\}$ 得 2，$\{1,1,1\}$ 得 3，结果不同，说明它能区分数量差别。
    2≠32 \neq 3
  2. 平均聚合$\operatorname{mean}$ 先加再除以个数，两组都得到 1，数量信息被归一化过程抵消。
    1=11 = 1
  3. 最大聚合$\max$ 只挑最大的特征，两组最大值都是 1，同样丢失了数量信息。
    max⁡=1=1\max = 1 = 1

GCN/GAT对比：其他质检员的章法

工厂里还有其他质检员。GCN 老张的习惯是平均：把所有邻居的章取平均值，再盖到自己身上，讲究「一碗水端平」。GAT 小王更机灵：先观察每个邻居跟自己关系有多铁，给关系铁的邻居更大权重——这就是注意力机制，适合抓重点。

GCN 的一层传播写成公式是：

问题在于：平均会让大章变小章。当中心节点有两个特征为 1 的邻居和三个特征为 1 的邻居时，平均结果都是 1——老张会看走眼。GAT 的注意力也只在「平均」的轴上做加权，依然丢失数量信息。简单说：GCN 是端水式、GAT 是挑重点式、GIN 是记账式。但这不代表 GCN、GAT 一无是处——GCN 参数少，在超大图上训练飞快；GAT 在「只有少数邻居重要」的场景，如社交关系链中，表现出色。选型就像挑质检员：想要满分眼力选 GIN，想要速度快选 GCN，想要会抓大放小选 GAT。

hv′=σ(∑u∈N(v)∪{v}1d^vd^u huW)h_v' = \sigma\left(\sum_{u \in \mathcal{N}(v) \cup \{v\}} \frac{1}{\sqrt{\hat{d}_v \hat{d}_u}}\, h_u W\right)
其中 $\hat{d}_v$ 是节点 $v$ 的度数加 1（含自环），分母是两端度数的几何平均。这个归一化让每个节点对邻居的贡献被「稀释」——这正是平均的本质。
  1. 加自环的邻居集$\mathcal{N}(v) \cup \{v\}$ 表示聚合时把自己也当成一个邻居，保证原自身特征不会被完全淹没。
    N~(v)=N(v)∪{v}\tilde{\mathcal{N}}(v) = \mathcal{N}(v) \cup \{v\}
  2. 对称归一化系数$1/\sqrt{\hat{d}_v \hat{d}_u}$ 让度数大的节点贡献被压缩，相当于盖章前先兑水。
    1d^vd^u\frac{1}{\sqrt{\hat{d}_v \hat{d}_u}}
  3. 加权求和与激活$\sigma(\cdot)$ 是激活函数，$W$ 是可学习矩阵；整体是「归一化平均 + 线性变换」。
    hv′=σ ⁣(∑u∈N~(v)1d^vd^uhuW)h_v' = \sigma\!\left(\sum_{u \in \tilde{\mathcal{N}}(v)} \frac{1}{\sqrt{\hat{d}_v \hat{d}_u}} h_u W\right)

应用与选型：把对的人派到对的线

回到工厂决策层：质检线老板该派谁去哪个项目？首先看任务核心——如果答案对细微结构差异敏感，比如分子性质预测：判断一个分子有没有毒性，苯环上多一个甲基官能团就是质的差别。这时 GIN 的全保留求和与图级读出机制非常关键。图级读出就是把整张图压缩成一个向量：

在实际选型中：图分类任务、分子性质预测、需要严格区分结构差异的场景，优先 GIN + 求和池化；网络规模极大、对推理速度敏感时，选 GCN + 邻居采样；节点级任务如推荐、链路预测，GAT 或 GCN 性价比更高。实践建议：先跑一轮 WL 测试当基线，再让 GIN 去追平它，最后才考虑为效率牺牲精度。把合适的质检员派到合适的拼图线上，工厂吞吐量才能最大化。GIN 看似朴素，却是你工具箱里那把衡量「眼力上限」的量尺。

hG=CONCAT⁡(∑v∈Vhv(1), ∑v∈Vhv(2), …, ∑v∈Vhv(K))h_G = \operatorname{CONCAT}\left(\sum_{v \in V} h_v^{(1)},\ \sum_{v \in V} h_v^{(2)},\ \ldots,\ \sum_{v \in V} h_v^{(K)}\right)
每层都做一次全图求和的「大点名」，再把各层的点名结果拼起来。这样既保留了局部细节，又汇总出全局概览。
  1. 逐层节点表征$h_v^{(k)}$ 是第 $k$ 层消息聚合后每个节点的新章，层数越多，每个章里包含的邻居范围越广。
    hv(k)=GINLayer⁡(k)(hv(k−1))h_v^{(k)} = \operatorname{GINLayer}^{(k)}\big(h_v^{(k-1)}\big)
  2. 层内求和池化$\sum_{v \in V} h_v^{(k)}$ 把第 $k$ 层所有节点的章加总，得到这一层的全局签名。
    ∑v∈Vhv(k)\sum_{v \in V} h_v^{(k)}
  3. 跨层拼接$\operatorname{CONCAT}(\cdot)$ 把各层全局签名拼接成最终图向量 $h_G$，兼顾不同粒度。
    hG=CONCAT⁡(∑vhv(1),…,∑vhv(K))h_G = \operatorname{CONCAT}\Big(\textstyle\sum_v h_v^{(1)}, \ldots, \textstyle\sum_v h_v^{(K)}\Big)

AI 应用场景

分子性质预测：数清官能团的个数

阶段：图表征学习 / 图分类

解决的问题：传统分子指纹是人工设计的，会把「两个羟基」和「一个羟基」这类数量差异编码得模棱两可。GIN 用求和聚合，分子里官能团的个数被忠实保留，模型能准确区分细微结构差异。

具体案例：药物研发中，给定一个候选分子，预测其水溶性或毒性。将分子建模为原子图为节点、化学键为边，用 3 层 GIN 提取每个原子周围邻域的多重集特征，最后一层做全图求和池化，输出溶解度数值。相比 GCN，GIN 在包含同分异构体差异的数据集上准确率显著更高。

社交网络异常检测：识破刷量团伙

阶段：图分类 / 图对比学习

解决的问题：刷赞团伙与普通用户群的局部结构差异，往往只体现在「某个小团体比正常情况多了一倍的关系量」。平均聚合会把这种倍数差异稀释成相同的均值，GIN 的求和聚合则让差异成倍放大，异常无处遁形。

具体案例：风控团队抽取一批可疑账号的社交子图，用 GIN 把它们嵌入成向量，再与正常子图的向量分布做对比。某刷量团伙在子图里有 100 条内部边，正常只有 50 条，GIN 的求和读出直接让异常分数翻倍，命中率提升约 30%。

代码剽窃检测：让抽象语法树「同构」说话

阶段：图匹配 / 图嵌入

解决的问题：判断两段代码是否同源，需要比较抽象语法树（AST）的近似同构关系。传统图同构算法在大型 AST 上慢得无法上线，而 GIN 可以把 AST 转成图并嵌入成低维向量，快速给出相似度分数。

具体案例：在线判题系统把每份提交的 AST 转图，用 GIN 得到 128 维向量；两段代码向量余弦相似度超过阈值就标记为「待人工复核」。相比逐树比对，速度提升数十倍，且对变量改名、语句顺序微调有天然鲁棒性。

Python 演示

python46 行
import numpy as np # 7 nodes: node0 = center A (neighbors 1,2); node3 = center B (neighbors 4,5,6)feats = np.ones((7, 1))adj = np.array([    [0, 1, 1, 0, 0, 0, 0],    [1, 0, 0, 0, 0, 0, 0],    [1, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, 1, 1, 1],    [0, 0, 0, 1, 0, 0, 0],    [0, 0, 0, 1, 0, 0, 0],    [0, 0, 0, 1, 0, 0, 0],], dtype=float)  def gin_agg(h, A, eps=0.0):    # GIN aggregation: weighted self + sum of neighbors    return (1 + eps) * h + A @ h  def mean_agg(h, A):    # Mean aggregation: average over self and neighbors (GCN-like)    deg = A.sum(axis=1, keepdims=True)    return (h + A @ h) / (deg + 1)  def max_agg(h, A):    # Max aggregation: elementwise max over self and neighbors    out = h.copy()    for i in range(len(h)):        nbrs = np.nonzero(A[i])[0]        if len(nbrs) > 0:            out[i] = np.maximum(h[i], h[nbrs].max(axis=0))    return out  def main():    centers = [0, 3]    print("GIN  sum :", gin_agg(feats, adj)[centers].ravel())    print("GCN mean :", mean_agg(feats, adj)[centers].ravel())    print("MAX      :", max_agg(feats, adj)[centers].ravel())    print("GIN distinguishes 3.0 vs 4.0; mean and max both give 1.0 vs 1.0")  if __name__ == "__main__":    main()
目的：用三个聚合函数对比「两个邻居」与「三个邻居」两种局部结构，直观展示 GIN 求和聚合能区分、平均与最大聚合不能区分的经典案例。
  1. feats = np.ones((7, 1))让所有节点特征相同，把差异完全留给「邻居数量」来体现，就像所有拼图碎片初始章都长一样。
  2. return (1 + eps) * h + A @ h一行实现 GIN 核心：自己乘 (1+ε)，邻居求和只需一次矩阵乘法。
  3. deg = A.sum(axis=1, keepdims=True)数出每个节点有几个邻居，为后面的平均做准备。
  4. return (h + A @ h) / (deg + 1)GCN 式平均：自己和邻居求均值，分母是度数加一，数量信息被归一化抹掉。
  5. out[i] = np.maximum(h[i], h[nbrs].max(axis=0))最大聚合只取局部最大值，彻底丢弃「有几个邻居」的信息。
  6. print("GIN sum :", gin_agg(feats, adj)[centers].ravel())同时打印两个中心的聚合结果，3.0 vs 4.0 的差异一目了然。

常见误区

误区很多人觉得 `(1+ε)` 是 GIN 的精髓，必须花大心思调 ε，甚至以为 ε 越大表达力越强，模型效果越好。

正解论文理论证明：ε 固定为 0 时，GIN 的区分能力已经与一维 WL 测试完全等价。ε 只是一个「自身权重」的调节旋钮，可以设为 0、固定常数或可学习参数；真正决定表达力上限的是求和聚合 + MLP 的单射性。就像老李盖章，关键在「集齐邻居信息」，而不是「把自己放大几倍」。

为何常见：公式里 ε 的位置非常醒目，又符合「加权求和」的直觉，初学者很容易把它当成魔法参数来研究。

误区以为像 CNN 一样堆层数就能提升性能，层数越多越能区分复杂图结构，于是无脑加深到十几层。

正解层数增加会带来过平滑问题——节点经过多轮聚合后特征趋于一致，反而更难区分。而且无论堆多少层，GIN 的理论表达力仍被一维 WL 测试限制。层数是灵活性，不是上限；真实任务里 2~4 层往往就够。

为何常见：深度学习里「更深更强」的惯性思维太强，忽略了图的「小世界」特性：几轮消息传递就覆盖了大范围邻居。

误区注意力在 NLP 中战功赫赫，于是认为 GAT 的加权求和比 GIN 的朴素求和更强大，表达力更高。

正解GAT 的注意力本质是「加权平均」，仍属于平均族聚合，会把邻居数量信息归一化掉。在「两个特征为 1 的邻居 vs 三个特征为 1 的邻居」面前，GAT 同样输出相同的表征。理论上，GAT 的区分能力不高于 GIN。

为何常见：注意力机制的光环效应——把「机制更复杂」误当成「能力更强」，忽略了表达力由聚合的信息保留量决定。

误区看到两堆拼图的盖章统计完全一致，就断定它们一定同构，甚至拿这个结论去做算法下线判断。

正解一维 WL 测试是必要条件，不是充分条件。统计不同，肯定不同构；统计相同，只能说「没找到证据」，两图可能同构也可能非同构。存在一类强正则图，它们并不同构，但一维 WL 测试永远无法区分。需要更高阶的 WL(k) 或更强方法。

为何常见：名字里带「测试」，容易被理解成「判决」；实际上它输出的是「未发现区别」，而不是「完全一致」。

误区把 GIN 当成完全创新的神经网络架构，认为它跟几十年前图论的 WL 测试没有任何渊源。

正解GIN 恰恰是把 WL 测试里的哈希函数替换成可学习 MLP、把聚合方式显式设计为求和，才构造出来的——它是 WL 测试的「可学习版本」。理解 WL 测试，就是理解 GIN 的设计蓝图。

为何常见：教材常把「经典图核算法」和「现代 GNN」分在不同章节，学生容易把它们当作两代割裂的技术。

面试题

Q1. GIN 中负责更新节点标签的核心组件是？

单选题 · easy

  • A.求和聚合与 MLP← 正确答案
  • B.平均聚合与 ReLU
  • C.注意力加权与 Softmax
  • D.随机采样与 Dropout

答案：A。GIN 的更新公式是 h′ = MLP((1+ε)h + Σh_u)，求和聚合负责收集邻居消息，MLP 负责把消息映射成新标签。平均聚合是 GCN 的思路，注意力加权是 GAT 的思路，Dropout 是正则化手段，都不是 GIN 的核心。

Q2. GIN 在理论上与哪种经典算法表达力相当？

单选题 · easy

  • A.一维 WL 测试← 正确答案
  • B.随机游走采样
  • C.PageRank 排序
  • D.图嵌入 DeepWalk

答案：A。2019 年 Xu 等人的论文证明，求和聚合 + MLP 的 GIN 与一维 Weisfeiler-Lehman 测试在区分图结构上能力等价。随机游走、PageRank、DeepWalk 都是基于采样的方法，理论保证远弱于 WL 测试。

Q3. 中心节点的邻居特征为 {1,1} 与 {1,1,1} 时，哪种聚合能区分两种结构？

单选题 · easy

  • A.平均聚合
  • B.最大聚合
  • C.求和聚合← 正确答案
  • D.中位数聚合

答案：C。求和聚合分别得到 2 和 3，能区分；平均聚合都得到 1，最大聚合都得到 1，中位数聚合也都得到 1。只有求和把「邻居个数」计入了结果，这正是 GIN 表达力的来源。

Q4. GIN 公式中参数 ε 的主要功能是？

单选题 · mid

  • A.控制自身特征权重← 正确答案
  • B.添加随机噪声
  • C.抵消梯度爆炸
  • D.加速矩阵乘法

答案：A。(1+ε) 乘在自己的特征上，控制「自己原来的章」在聚合时的权重。ε 不是噪声也不是正则，更不影响计算速度。理论表明 ε 取 0 时 GIN 已与 WL 测试等价，它只是一个可调节的自身权重旋钮。

Q5. 以下哪种图结构最考验 GNN 的表达力？

单选题 · mid

  • A.度数分布相同的非同构图← 正确答案
  • B.两个完全随机的大图
  • C.节点特征完全不同的大图
  • D.只有一个节点的极小图

答案：A。度数分布相同意味着平均、最大等「统计型」聚合难以从度数上找到破绽，比如两个不同构的 3-正则图，每个节点度数都是 3，GCN 几乎无法区分。随机大图、特征完全不同、单节点图都容易被简单方法区分，缺乏挑战性。

Q6. 关于 GCN 聚合的说法正确的是？

多选题 · mid

  • A.本质是归一化平均← 正确答案
  • B.会丢失邻居数量信息← 正确答案
  • C.表达力强于 GIN
  • D.适合大规模图训练← 正确答案

答案：ABD。GCN 用对称归一化系数对邻居求和，本质是加权平均，确实会把「邻居有几个」的信息归一化掉，所以表达力不高于 GIN。C 说反了。GCN 参数少、计算高效，适合大规模图训练。

Q7. 两图经过多轮一维 WL 测试后标签统计仍相同，能得出什么结论？

单选题 · extreme

  • A.两图必然同构
  • B.两图可能同构← 正确答案
  • C.两图必然不同构
  • D.两图节点数必然不等

答案：B。一维 WL 测试是图同构的必要条件而非充分条件。标签统计不同，可断定非同构；标签统计相同，只能说「没发现区分证据」，两图可能同构也可能同构但 WL 分不出。存在强正则图并不同构却让 WL 测试失效，因此选「可能同构」。

Q8. GIN 的表达力上限由什么决定？

单选题 · hard

  • A.一维 WL 测试上限← 正确答案
  • B.MLP 隐藏层宽度
  • C.训练数据规模
  • D.图节点最大度数

答案：A。GIN 被证明与一维 WL 测试等价，因此它的区分能力上限就是一维 WL 测试能区分的图对集合。MLP 宽度影响逼近能力但不提升理论上限；数据规模影响泛化而非表达力；节点度数只影响局部聚合范围。

Q9. 以下哪些手段能提升 GIN 的表达力？

多选题 · mid

  • A.使用求和聚合← 正确答案
  • B.多层消息传递← 正确答案
  • C.可学习自身权重← 正确答案
  • D.使用最大池化

答案：ABC。求和聚合是 GIN 表达力的根基；多层消息传递扩大感受野；可学习的 ε 让模型自动调节自身权重，都不改变理论上限但提升实际效果。最大池化会丢失数量信息，反而降低表达力。

Q10. 关于 GCN、GAT、GIN 三者对比，说法正确的是？

多选题 · hard

  • A.GCN 是归一化平均聚合← 正确答案
  • B.GIN 表达力不弱于 GCN← 正确答案
  • C.GAT 注意力适合重要邻居← 正确答案
  • D.GCN 理论强于 GIN

答案：ABC。GCN 的归一化是平均思想，GAT 的注意力是加权平均思想，两者都属于平均族，理论上不高于使用求和聚合的 GIN。GAT 在「少数邻居至关重要」的场景表现好。D 说反了，GIN 的理论表达力强于 GCN。