节点数可变、邻居数不定 — 34 个点只给 2 个标签,四种做法并排
这一章讲三件事: 一张「谁连着谁」的网在程序里怎么存; 在这张网上做训练的统一套路(消息传递)长什么样; 以及同一张 34 人的小网上,四种代表性做法跑出来的四组数该怎么读。
它在全书链条里的位置: 前面十八章的输入全是规整的方阵或序列。 这一章是全书唯一的支线:换一种数据形状,但骨架还是第 03 章那五步,只是中间那台机器换了构造方式。
需要的基础: 「层」「参数」「损失」这套通用词汇;第 15 章的注意力(读 GAT 那节要用)。
1. 先看现象:这三样东西没法摆进一个矩形
一张图片是 32×32 的格子,一句话是 23 个编号的位置——它们都能摊平成规则矩形。 下面三种东西不行:
社交网络 人与人之间的朋友关系
分子 原子与原子之间的化学键
引用网络 论文与论文之间的引用
它们的共同点:点的个数不固定、每个点连几条线不固定、连谁也任意1。 书里把它们统称为图——不是图画,是把一堆东西(叫节点)和它们之间的连线(叫边) 当成一个整体来看的数据形状。
书里点破了这个麻烦:前面学过的前馈网络、卷积网络、循环网络, 都假定输入是规则的向量、网格或序列,对这种不规则的网直接用不上1。
书里的解法一句话:在这张网上做消息传递,学习三种粒度的表示——每个节点一份、每条边一份、或者整张网一份2。 本章落到四种代表性模型:GCN(图卷积)、GraphSAGE(采样加聚合)、GAT(图注意力)、GIN(同构网络)2, 全部用纯 PyTorch 手写,不用现成的图计算库——书里明说是为了看清消息传递范式本身3。
全章主走查:一张 34 个人的朋友圈子
═══════════════════════════════════════════ ════════════════════════
输入 某大学空手道俱乐部 34 名成员的友谊网络 + 只有 2 个已知阵营
───────────────────────────────────────────────────────────────────
§3 ① 存下来:邻接矩阵 [34,34]、边列表 [2,156]
§4 ② 更新一个人:先收邻居的消息,再合并,再更新自己
§5 ③ 训练:只看 0 号和 33 号两个人的阵营,训 200 轮 → 34 个里对 33 个
§7 ④ 换另外三种做法再跑一遍,四组成绩并排
§8 ⑤ 把层数从 2 层加到 8 层,看会坏成什么样
═══════════════════════════════════════════════════════════════════
2. 三种存法:同一张网,三种记法
记住一张网,本质上就是回答「谁连了谁」。书里给了三种记法,各有各的划算场景4:
| 记法 | 怎么记 | 开销 | 划算的场景 |
|---|---|---|---|
| 邻接矩阵 | N×N 的 0/1 方表,第 i 行第 j 列是 1 就是相连 | O(N²) | 小图、矩阵运算 |
| 边列表 | 一个 2×E 的整数张量,把每条边两端的编号各写一遍 | O(E) | 大而稀疏的网 |
| 邻接表 | 每个节点自己维护一份邻居名单 | O(N+E) | 逐个扫邻居的老算法 |
邻接矩阵直观、方便做矩阵乘法,但一张 N 个节点的网就要 N² 格—— 百万节点的引用网要存一万亿格,哪怕绝大多数格都是 0(这种大片是 0 的性质,正式名字叫稀疏)4。
除了连线关系,每个节点还可以随身带一份特征向量(整个网摞起来是一个特征矩阵 X), 每条边也可以带属性——比如分子里那根键是单键还是双键;另外还有一张度矩阵, 记录每个节点连了几条线,后面的归一化要用4。
3. 主走查前半:把空手道俱乐部存进内存
这一章的实验对象是一张只有 34 个节点的社交网,书里管它叫图上的 MNIST5: 某大学空手道俱乐部的 34 名成员,谁是朋友就连一条边(共 78 条); 后来俱乐部因为教练和管理员闹矛盾分裂成两派,每个人各自选了边站。 任务:只告诉模型教练派一人、管理员派一人(共 2 个标签), 让它借朋友关系把其余 32 人的阵营全猜出来。
按上一节的三种记法把这拿网存进去,书里的打印输出6:
主走查第 ① 步
────────────────────────────────────────────────────────────────
节点数 N = 34, 边数 E = 78, 平均度数 = 4.59
(平均度数 = 平均每人认识 4.59 个人)
邻接矩阵:[34, 34],占 4624 字节
(78 条无向边在对角称两侧各写一次 → 表里有 156 个 1)
边列表:[2, 156] (每条边写两次,两个方向都记)
────────────────────────────────────────────────────────────────
对照:真实引用网 Cora 有 2 708 个节点、10 556 条边,
它的邻接矩阵就要近 30 MB——比这张小网大五千多倍[^7]
这张小网的连法自带规律:把它画出来,同一个阵营的人内部连得密、跨阵营连得疏; 邻接矩阵画成热力图,接近「左上一块、右下一块」的块状—— 书里给这个「物以类聚」的现象起了名字,叫同质性(homophily):连在一起的人,大概率是同一派7。 正是这条规律,后面才可能只凭 2 个标签推出 32 个人。
节点带什么特征?这张网本身没有任何属性,书的兜底办法是 one-hot: 每个人领一个 34 维向量,自己编号那一维是 1、其余全是 0——等于只告诉模型「我是几号」, 其余信息全靠连关系推出来8。 真实的图不会这么寒酸:Cora 上每个节点是论文摘要的 1 433 维词袋向量; 分子图上每个节点是原子的化学元素等理化属性;实在没属性时也可以干脆随机初始化、让训练把它学出来9。
4. 消息传递:所有图网络的公共三步
五花八门的图模型其实共享同一个框架:一层网络更新一个节点的表示,分三步10:
节点 i 的一次更新
════════════════════════════════════════════════
① 造消息 对每条指向 i 的边,由源节点 j 算出带给 i 的消息
② 合邻居 把所有邻居发来的消息合并成一个「聚合消息」
——常用 sum / mean / max,都与邻居的排列顺序无关
(名单打乱、结果不变;这个性质行话叫置换不变)
③ 更新自己 把聚合消息和自己的旧表示组合,产出新表示
════════════════════════════════════════════════
不同模型之间的真正差异,就落在这三步的具体形式上:消息怎么造、邻居怎么合、节点怎么更新11。 书里为此写了一个抽象基类,三个钩子函数各管一步,后面四种模型各自填空—— 和 PyTorch Geometric 库的同名设计思路一致,只是去掉了工程优化、便于阅读12。
有一处实现取舍必须交代,它同时是这一章的天花板:基类为了清楚, 把「每条边的消息」存成一个 N×N×D 的整块稠密张量——34 个节点的小网毫无问题, 放到百万节点的大图上会直接撑爆显存13。 这道墙到第 19 章第 9 节正面处理,这里先知道有这回事。
5. 图卷积 GCN:按度数归一后求和
第一个填空的叫 GCN(图卷积网络)。它的一条公式解决了两个工程问题14:
H(l+1) = σ( D̃^(−1/2) · Ã · D̃^(−1/2) · H(l) · W )
────────────────────────────────────────────────
à = A + I 加自环:让每个节点也算自己一个邻居
(不给的话,更新三次之后自己原有的信息就被冲没了)
D̃ Ã 对应的度矩阵
D̃^(-1/2)ÃD̃^(-1/2) 对称归一化:热闹的人的一票不能顶冷清的人的好几票
W 这层的可调参数
σ 折线激活(ReLU)
直觉版:先把邻居(连同自己)按双方度数折算权重求和,再做一次线性变换、过一道非线性14。 在消息传递的三步框架里,它就是:每条边带固定的按度数归一的权重(①)、聚合用 sum(②)、更新为 σ(mW)(③)。
主走查第 ③ 步:极省的训练设定。 书里自己用了「节俭」这个词: 全图 34 个人,只给教练派、管理员派各 1 个贴标签的人(共 2 个), 两层 GCN(隐藏 16 维)、暂退率 0.3、Adam 学习率 0.05、权重衰减 5e-4、训 200 轮15:
主走查数字
────────────────────────────────────────────────────────────────
只有 0 号(教练派)和 33 号(管理员派)参与算损 失
其余 32 个人的表示,纯靠图结构在三层之间被"传话"带动
结果:final acc = 0.9706 ≈ 34 个里猜对 33 个[^17]
过程:损失在前 20 轮内快速降到接近 0,
准确率几轮内升过 0.95,之后在 0.94~0.97 之间小幅波动[^18]
为什么 2 个标签够用?答案在第 3 节埋的那条同质性: 教练的密友大概率也是教练派,他们的密友也是……标签信息沿着边一层层扩散, 几步之内就把整张网的立场染色了。 把第一层的输出降到二维画出来,两派几乎完全分离——这就是 2 个标签撬动 34 个人的证据16。
这种「一小撮样本有标签、大多数没标签」的设定有个正式名字:半监督—— 区别于监督(全体都有标签):模型要学的主要不是样本本身,是样本之间的结构。
6. 另外三种填空:SAGE、GAT、GIN
GCN 不是唯一填法。书里另外三种,差异全在第 4 节那三步里:
GraphSAGE(采样加聚合)。动机很实际:GCN 每次更新要把整张归一化邻接矩阵搬进显存, 大图吃紧;GraphSAGE 把更新公式落到单个节点上,每次只从邻居里抽 K 个参与聚合, 从而能扩展到任意大的图17。单头(mean 版)更新式: 新表示 = σ(W · [自己的旧表示 ‖ 邻居均值]),两项首尾相接(concatenate)后过一层线性17。 真实大图上那个「取均值」会被换成真正的邻居采样,PyTorch Geometric 有专门的装载器负责18;
GAT(图注意力)。GCN 给每个邻居的权重是死的(由度数决定);但现实里并非所有邻居同等重要—— 书里的比方:知心好友显然比泛泛之交更值得听19。GAT 让权重变成学出来的: 对每对邻居打一个注意力分数(打分方式与第 15 章自注意力同族:线性变换后做拼接投影、过 LeakyReLU、 只在邻居范围内 softmax(把一组分数压成总和为 1 的权重)归一),再按分数加权求和;实用中同样切成多头各看各的20;
GIN(图同构网络)。这一种是理论逼出来的:什么样的图模型能区分两张不同的图? 答案是聚合函数得是单射(不同的输入集合必须给出不同的聚合结果—— max 就不行:邻居 {3,7} 和 {3,5,7} 取最大都是 7,区分不开;sum 可以;mean 也区分不了集合大小)。 GIN 用 sum 聚合加上一个小多层感知机凑齐理论条件,再把自己的旧表示乘 (1+ε) 加以突出21。
四种模型在同一套三步框架下的分工,一句话各自认领22:
| 模型 | ① 造消息 | ② 合邻居 | ③ 更新 |
|---|---|---|---|
| GCN | h_j × 按度数的固定权重 | sum | σ(·W) |
| GraphSAGE | 原样 h_j | mean | W[自己‖聚合] |
| GAT | 学出来的 α_ij × Wh_j | sum | 直通 |
| GIN | 原样 h_j | sum | MLP((1+ε)h_i + 聚合) |
7. 四种并排:同种子、同超参的四组数
书里用完全相同的设定(同种子、200 轮、Adam、学习率 0.05、暂退率 0.3)把四个模型跑了一遍—— 并且特意在每个模型构造前重置随机种子,注释写明理由:权重初始化也要消耗随机数, 不重置的话构造顺序都会影响结果、对比不可复现23。单次结果24:
GCN final_acc = 0.9706 ← 依然是 33/34
SAGE final_acc = 0.9706 ← 同样 33/34
GAT final_acc = 0.8824 ← 30/34
GIN final_acc = 0.9118 ← 31/34
单次成绩会说谎:书里补了一张换 5 个随机种子求均值和标准差的对照表25:
| 模型 | 平均准确率 | 标准差 | 特点(书里原注) |
|---|---|---|---|
| GCN | 0.96 | 0.01 | 简单稳定,参数最少 |
| GraphSAGE | 0.81 | 0.25 | 支持邻居采样、可扩展大图;小图上方差大 |
| GAT | 0.89 | 0.01 | 注意力解释性好;34 节点上优势不明显 |
| GIN | 0.66 | 0.16 | 理论表达力最强;2 标签小图上对种子极敏感 |
怎么读这张表:单次排名和多次排名不一样。 单次并列第一的两个,5 种子之下 GCN 仍稳在 0.96, GraphSAGE 掉到 0.81 且波动最大( 标准差 0.25——大概是 2 个标签喂不出稳定的统计); 理论上最强的 GIN 反而最惨(均值 0.66)。书里的解释是这张小图太极端:只有 2 个标签, 凡是对初始化敏感的设计都会被放大;GAT 的优势(挑重要邻居)要到真实规模才能显出来——第 19 章的 Cora 基线表会再看它一次;SAGE 原书只在笔记里许了同一句话、Cora 基线表(表 9.2)却没排它,这桩悬案照实记在这里26。
还有一处口径书里自己加了脚注:这一节用的是单头 GAT(隐藏 16 维), 配套 notebook 为了演示多头改成了 4 头(隐藏 8 维),两边数值略有出入、各自自洽(各自与自己的设定对得上)27。 引这组数时要带上这个前提。
判断(我们的,不是书里的):这张 0.97 的小网验证的是「结构里有信息」,不是「哪种模型更好」。 同一张 34 节点的网、同样的 2 个标签,四种设计的名次可以随种子互换, 但都远高于瞎猜的二分类 0.5——说明拉开成绩的是图本身那条同质性,而不是模型的高下。 如果错,会错在: 如果某一种结构的优势恰好在小图上就该显现,那这个结论就把结构性差距误判成了数据规模问题。 判据是:第 19 章 Cora(2 708 节点、140 标签)上若出现稳定的单方面领先,则此判断作废。
8. 堆深了会怎样:八层之后所有人长成一个样
CNN 常见上百层,图的这边却普遍只敢堆两三层——背后的病叫过度平滑: 层数太深时,所有节点的表示迅速趋同、可分性消失28。
机制不难想:每一层 GCN 都把节点朝邻居均值的方向拉一步; 拉足够多次,所有人都收敛到同一个点(数学上是归一化邻接矩阵的主特征向量方向)—— 整张网被「熨平」,分类边界自然没了29。
主走查第 ⑤ 步。 书里写了个支持任意层数的 GCN,层数 2 / 4 / 6 / 8 各跑一遍, 并顺手量了一个指标:节点表示两两余弦相似度(两个向量方向有多接近:1 = 完全同向)的均值(越接近 1 = 越长一个样)30:
L=2 acc = 0.9706 余弦相似度 0.7177
L=4 acc = 0.9412 余弦相似度 0.5280
L=6 acc = 0.9118 余弦相似度 0.7596
L=8 acc = 0.5294 余弦相似度 1.0000 ← 完全重合,分类器瞎了
────────────────────────────────────────────────
参照:这个二分类任务瞎猜是 0.5,L=8 的 0.5294 已经贴地[^34]
注:中间层(4、6)的相似度受随机性影响会上下跳动,
书里自己说明这不改变「深到 8 层必趋同」的大势[^35]
9. 三条缓解思路,以及另一道墙
治过度平滑有三类办法31,你会认出其中一个是老朋友:
- 残差连接(第 09 章那招搬过来):每层改为 H ← ReLU(GCN(H)) + H,JK-Net、ResGCN 属于这类;
- 表示归一化:PairNorm、NodeNorm 在每层之后重新把节点表示拉开距离;
- 图稀疏化:DropEdge 随机丢一部分边,放慢「扩散」的速度。
书里跑了带残差的六层版本(ResGCN-6L),成绩回到约 0.88——接近浅层水平(没到 0.97,但不再是 0.53 的瞎猜)32。
深度之外还有一个量级问题,书里专门用提醒框钉死:图上的「深」和图像里的「深」不是一个单位。 CNN 常见 100 层以上,GNN 加了残差多数论文也就堆 4~6 层——因为每多一层,感受野往外扩一跳, 在小直径的图上覆盖的节点数近乎指数膨胀:像 Karate 这种小网,4 层基本就能覆盖整张图,再深全是冗余33。
深度的墙讲完了,还有一道宽度的墙:到此为止的所有实现,都在把整张邻接矩阵 (以及 N×N×D 的边消息)当成一块完整张量搬进显存——这种逐格写法, 百万节点的图第一步就爆。怎么翻这道墙(稀疏存法 + 真实规模的实战),第 19 章第 9 节正式交代。
10. 边界与局限
这一章没覆盖的:
| 没讲什么 | 依据 / 为什么值得知道 |
|---|---|
| 表达力理论的推导 | GIN 只给了「单射 → 1-WL」的结论与设计要点,没有证明34 |
| 异质图、动态图 | 全章的图只有一种节点、一种边,时间维度也没碰 |
| 标签多给一点会怎 样 | 书留成练习:标签从 2 个加到 10 个,观察 GCN 成绩曲线35 |
| GAT 换个层深会不会更抗平滑 | 书留成练习(提示:注意力可以学到忽略某些邻居)36 |
| 现成的图计算库 | 只在一节末尾点名 PyTorch Geometric 及安装注意,实战细节留给第 19 章 |
出门会撞见的名字:
- GCN / 图卷积(Graph Convolutional Network) —— 第 5 节;
- GraphSAGE(Sample and AggreGatE) —— 第 6 节,配套的装载器叫 NeighborLoader18;
- GAT(Graph Attention Network) —— 第 6 节;
- GIN(Graph Isomorphism Network,图同构网络) —— 第 6 节;
- 消息传递(Message Passing)、置换不变 —— 第 4 节的公共框架;
- 过度平滑(oversmoothing)、DropEdge、PairNorm —— 第 8、9 节;
- one-hot 特征(一位有效编码) —— 第 3 节那个兜底办法的通行叫法。
11. 可带走的
- 图是「点 + 连线」的数据形状:节点数可变、邻居数不定,规整方阵那 套先用不上;
- 存图三选一:小图用邻接矩阵、大图用边列表(真正生产行业的默认),逐个扫邻居才用邻接表;
- 所有图模型共用三步:造消息、合邻居、更新自己——差别只是这三步各自的形式;
- GCN 一条公式两个机关:加自环保住自己的信息,按度数归一不让热闹节点霸麦;
- 2 个标签能推全图,靠的是同质性——书里那张 34 人小网上 GCN/SAGE 都到 0.9706;
- 单次成绩会说谎:5 种子之下 SAGE 掉到 0.81±0.25、理论更强的 GIN 只有 0.66±0.16;
- 图上不敢堆深:8 层之后全体表示余弦相似度冲到 1.0000、成绩退回瞎猜附近(0.5294 vs 0.5);
- 深度的解药是残差(六层带回约 0.88),宽度的墙靠稀疏表示——那是第 19 章的事;
- 图上的「深」和 CNN 的「深」不是一个单位:Karate 这种小网 4 层就盖住全图。
12. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 图的不规则性 | 第9章 图神经网络 | text/10-ch09.txt:165(搜「不规则」) |
| 消息传递范式与四种模型 | 第9章 图神经网络 | text/10-ch09.txt:168(搜「在图上做消息传递」) |
| 纯 PyTorch 手写的约定 | 第9章 图神经网络 | text/10-ch09.txt:176( 搜「torch_geometric」) |
| 三种存储方式 | 第9章 图神经网络 | text/10-ch09.txt:200(搜「常见的存储方式有三种」) |
| Karate Club 与任务设定 | 第9章 图神经网络 | text/10-ch09.txt:218(搜「Zachary's Karate Club堪称」) |
| 规模与开销输出 | 第9章 图神经网络 | text/10-ch09.txt:252(搜「节点数 N=34」) |
| Cora 近 30 MB 的对照 | 第9章 图神经网络 | text/10-ch09.txt:258(搜「近 30 MB」) |
| 同质性与块状矩阵 | 第9章 图神经网络 | text/10-ch09.txt:788(搜「同质性」) |
| one-hot 特征 | 第9章 图神经网络 | text/10-ch09.txt:314(搜「one-hot」) |
| 三步消息传递 | 第9章 图神经网络 | text/10-ch09.txt:337(搜「共享一个统一框架」) |
| 差异落在三处函数 | 第9章 图神经网络 | text/10-ch09.txt:349(搜「真正差异」) |
| 稠密写法的显存警告 | 第9章 图神经网络 | text/10-ch09.txt:402(搜「爆显存」) |
| GCN 公式与组件 | 第9章 图神经网络 | text/10-ch09.txt:461(搜「对称归一化」) |
| 半监督训练设定 | 第9章 图神经网络 | text/10-ch09.txt:501(搜「极为“节俭”」) |
| GCN 成绩与曲线 | 第9章 图神经网络 | text/10-ch09.txt:526(搜「0.95 以」) |
| 表示分离可视化 | 第9章 图神经网络 | text/10-ch09.txt:557(搜「几乎完全分离」) |
| GraphSAGE 动机与公式 | 第9章 图神经网络 | text/10-ch09.txt:596(搜「搬上显存」) |
| GAT 动机 | 第9章 图神经网络 | text/10-ch09.txt:625(搜「知心好友」) |
| GIN 单射要点 | 第9章 图神经网络 | text/10-ch09.txt:658(搜「单射」) |
| 相同超参对比约定 | 第9章 图神经网络 | text/10-ch09.txt:688(搜「相同的训练超参」) |
| 四种成绩输出 | 第9章 图神经网络 | text/10-ch09.txt:741(搜「final_acc=0.9706」) |
| 5 种子对照表 | 第9章 图神经网络 | text/10-ch09.txt:775(搜「次不同随机种子」) |
| 小图方差大的解释 | 第9章 图神经网络 | text/10-ch09.txt:790(搜「0.16 0.25」) |
| 过度平滑定义 | 第9章 图神经网络 | text/10-ch09.txt:802(搜「趋同」) |
| 层数实验输出 | 第9章 图神经网络 | text/10-ch09.txt:851(搜「L=2 acc=0.9706」) |
| 缓解三类 | 第9章 图神经网络 | text/10-ch09.txt:881(搜「缓解方法有 3 类」) |
| ResGCN 回到约 0.88 | 第9章 图神经网络 | text/10-ch09.txt:908(搜「恢复到接近浅层水平」) |
| 深度的量级提醒 | 第9章 图神经网络 | text/10-ch09.txt:911(搜「100 层以上」) |