卷积吃网格,循环吃链条;可是一张社交网络里,谁的邻居有 3 个人、谁的邻居有 3000 个, 连「窗口」都定义不出来。这一章给图建立最薄的数学地基,然后把第 16 章那句话推广成 一切图神经网络的公共骨架:收消息、聚合、更新自己。
图数据与消息传递
1. 这一章讲什么
三件事: 图这种数据和它的三种计算机表示; 拉普拉斯矩阵——它为什么是全章(乃至下一章谱方法)的地基; 以及任务的三级分类和图神经网络的统一机制(消息传递)。
它在全书链条里的位置: 第 16 章末尾说过,把循环网络展开看成链上的 「收消息—更新—传出」,推广到任意结构就是图神经网络。 这一章完成这个推广,并给出下一章四个经典模型共同踩着的那块石头(L 矩阵)。
需要第 13 章、第 16 章;下一章从头用到本章每一节。
2. 顶层全景
数据形态: 网格(图像) ── 序列(文本) ──▶ 图(关系)
邻居数不固定 · 无平移结构
表示: 邻接矩阵(写公式方便) / 邻接表(稀疏友好) / 边列表(边操作多)
地基: L = D − A ; xᵀLx = ½Σ Aᵢⱼ(xᵢ−xⱼ)² ←「平滑度」的代数化身
任务三级: 节点级(直接用 h_v) · 边级(组合 h_u⊕h_v) · 图级(全局汇聚成 h_G)
统一机制: 消息构造 m_{u→v} → 邻域聚合 AGGREGATE → 状态更新 UPDATE
L 层网络 ⟺ 最多看 L 跳
一句话链条: 关系数据的先验是「连接结构本身携带信息」→ 表示要同时存属性和连接 → 拉普拉斯矩阵把「相邻节点差多少」变成一个代数量 → 任务按预测对象分三级、共享同一个节点表示学习 → 表示怎么学?消息传递:一层看一跳,层层往外看。
3. 排不成网格的数据
图由节点与边构成,记作 G=(V,E); 节点是人、论文、原子,边是它们之间的交互、依赖、连接。 与只强调局部排列的序列和图像不同,图数据的关键在于: 对象本身的属性与对象之间的连接结构同样重要1。 前面所有章的先验到这里全部失效:
- 图像的「相邻」有固定方向和数量(上下左右),图的邻居数任意;
- 卷积的「同一花纹出现在不同位置」依赖平移结构,图没有「位置」;
- 循环的「上一步下一步」只是一条链,图是链的网状推广。
两个正交的细分维度先钉死2:
| 维度 | 取值 | 例子 |
|---|---|---|
| 边有无方向 | 无向图(对称关系) / 有向图(单向关系) | 好友 / 引用 |
| 节点边类型 | 同质图(单一类型) / 异质图(多种类型) | 用户-好友 / 作者-论文-会议 |
异质图需要专门的建模方式(关系图卷积、异质图注意力等), 本章的机制都在同质图上展开3。
4. 怎么把图放进计算机
三种常见表示,各有各的便宜4:
| 表示 | 是什么 | 适合 |
|---|---|---|
| 邻接矩阵 A | n×n 方阵,Aᵢⱼ=1 表示有边 | 写公式最方便;无向图对称 |
| 邻接表 | 每个节点存一份邻居列表 | 稀疏图——只存实际存在的边 |
| 边列表 | 所有边 (u,v) 的集合 | 边操作多的场景,消息传递实现常见 |
关键矛盾在第一行:邻接矩阵写公式方便,但一张百万节点、平均 10 个邻居的图, 稠密存储意味着 99.999% 的格子是零——大规模稀疏图直接存稠密矩阵,内存开销会很大5。 这就是为什么论文里的公式全用矩阵、工程实现全用表。
5. 地基:拉普拉斯矩阵在说什么
先补两个量。度:与节点直接相连的边数(有向图分入度/出度); D 是度矩阵(对角线放各节点的度)。同质性:相似节点的边占比 H = 连接同类节点的边数 / 总边数——GCN 一类模型默认「邻居信息有用」, 同质性低时,简单的邻域平均反而会削弱效果6。(这一伏笔下一章兑现。)
拉普拉斯矩阵定义为 L = D − A7。它同时编码了局部连接与整体拓扑, 但它真正的身份要看它作用在图信号上——图信号就是「每个节点附着一个数值」的向量 x:
(Lx)ᵢ = Σⱼ Aᵢⱼ(xᵢ − xⱼ) —— 节点自己的值减去邻居值的加权和
xᵀLx = ½ Σᵢ,ⱼ Aᵢⱼ(xᵢ − xⱼ)² —— 全图相邻差值的平方和
两行读出的结论:Lx 衡量每个节点与邻居的局部差异; xᵀLx 是全图「平滑度」的代数化身——相邻节点取值越接近,它越小; 信号在图上振荡得越剧烈,它越大9。这就是后面图正则化、谱聚类(按振荡平滑性分群)、 以及图卷积定义全部踩在上面的那块石头。第 8 节主走查拿真实数字走一遍。 常用的还有归一化版本 L_norm = I − D^{−1/2}AD^{−1/2}, 消除了节点度差异带来的尺度影响,谱图分析中更常用10——下一章它就是主角。
6. 三级任务与划分纪律
围绕图的任务只有三级,分别以节点、边、整图为预测对象; 书用同一个引文网络贯穿:论文是节点、引用是边、标题摘要是节点特征—— 预测论文的领域是节点分类,预测两篇论文未来是否互引是链接预测, 判断一组论文及引用关系构成子图的学科是图级任务11。
| 级别 | 预测对象 | 读出方式 | 例 |
|---|---|---|---|
| 节点级 | 单个节点 | 直接用 h_v 过分类器 | 节点分类、回归、表示学习 |
| 边级 | 节点对 | 组合节点对表示(内积或 MLP(h_u⊕h_v)) | 链接预测、边分类 |
| 图级 | 整张图 | 读出函数:全局汇聚成 h_G | 分子分类、图生成 |
(「读出」= 把学到的节点表示进一步变换为任务输出的步骤12; 图级的汇聚有求和、平均、最大几种。)
比模型更容易出错的是数据划分,书在这节花了很多字,纪律值得整段搬走13:
- 节点任务:同一张图上划分训练/验证/测试节点; 传导式(全图可见,只在训练节点上算损失)与归纳式(隔离新节点)要分清;
- 链接预测必须把验证、测试的正例边从训练图里删掉—— 否则模型直接通过已存在的边得到答案;
- 图随时间演化时优先按时间划分,不许用未来预测过去;
- 图级任务以整张图为划分单位,并警惕近重复样本/同源结构泄漏;
- 指标与任务匹配:类别不平衡用宏平均或 PR 曲线(第 08 章的老朋友)。
7. 统一机制:消息传递
现在回答「表示怎么学」。所有图神经网络共享一个核心思想—— 消息传递机制:在图上反复进行局部信息传递、邻域聚合与表示更新, 让每个节点逐步融合周围的结构与属性信息14。
一层消息传递只直接聚合一阶邻居;L 层网络至多覆盖 L 跳邻域—— 层数决定了节点在图上的感受野15 (它能「看到」多大范围)。 第 16 章链上那句话的推广版。层数于是成为一把双刃刀: 加深扩大感受野,但会带来过度平滑、过压缩和训练开销—— 层数并非越深越好16 (三个词下一章逐一兑现)。
一层 GNN 的两步,公式形状如下17:
① 消息构造 + 邻域聚合
m_{u→v} = φ(h_v, h_u, h_{uv}) 每条边造一条消息
m_v = AGGREGATE({m_{u→v} : u ∈ N(v)}) 求和/平均/最大
② 状态更新
h_v ← UPDATE(h_v, m_v) 常见如 ReLU(W[h_v ⊕ m_v])
这个「消息构造—邻域聚合—状态更新」的统一框架叫 消息传递神经网络(MPNN)[Gilmer et al., 2017]18—— 下一章的 GCN、GraphSAGE、GAT、GIN 全部是它填空题的不同答案。
聚合函数有一条硬约束:必须对邻居的排列顺序不变。 因为邻居本质上是一个集合,没有先后编号; 聚合若依赖枚举(逐个排列)顺序,同一张图换个节点编号输出就变了19。 (下一章 GIN 一节会看到:不同的不变聚合函数,连「能分辨哪些图」都不一样。)
8. 主走查:一个五节点图,从邻接矩阵到平滑度
设定:原书图 9.1a 的五节点无向图,边为 1-2, 1-4, 1-5, 2-3, 3-4, 3-5, 4-5(原书式 9.4-9.5 就是按它写的)。 给每个节点配一个数(图信号):x = (1, 2, 3, 4, 5)。
第一步:邻接矩阵与度。
边集:1-2, 1-4, 1-5, 2-3, 3-4, 3-5, 4-5
度: d₁=3, d₂=2, d₃=3, d₄=3, d₅=3 (与原书式 9.4 的 D 矩阵一致)
第二步:算 (Lx)₁(公式:3x₁ − x₂ − x₄ − x₅,系数 3 是节点 1 的度):
(Lx)₁ = 3×1 − 2 − 4 − 5 = −8
读法:节点 1 的值(1)比它的三个邻居(2、4、5)低不少, 负号和大数就是「这一家子不协调」的定量版。
第三步:算平滑度 xᵀLx(= 相邻差值平方和):
边 差² 边 差²
1-2 1 3-4 1
1-4 9 3-5 4
1-5 16 4-5 1
2-3 1
合计 xᵀLx = 33
这张表就是「平滑度」的实物:16 那一格(1-5 边)一家就贡献了一半—— 信号在图上最不光滑的地方,被 L 精确指认了出来。 下一章的谱方法会反过来用这个量:把信号拆到 L 的特征向量上, 特征值大的分量正是「振荡剧烈」的那些。
9. 作者的判断与证据
书里给了定义与推导的: 拉普拉斯的元素式与二次型(½ΣAᵢⱼ(xᵢ−xⱼ)², 用到无向图的对称性)8;归一化拉普拉斯消尺度影响的理由10; MPNN 统一框架18。
书里给了实践纪律的: 链接预测删目标边、时间划分优先、图级整图划分13; 聚合的排列不变性约束及其理由(邻居是集合)19; 同质性低时邻域平均可能有害6。
书里划了边界的: L 层=L 跳,加深有过度平滑/过压缩/开销三重代价1516; 异质图需专门模型,本章机制不直接覆盖3。
10. 边界与局限
本章的机制是「同质图上的静态消息传递」:边类型单一、图不随时间变; 异质关系、动态图只在概念层点名3。
拉普拉斯只定义到了「地基」:特征分解、频率基、谱卷积一个都没讲—— 它们是下一章前半部的全部内容,本章读者只需带着 xᵀLx 的直觉过去。
图生成在任务表里只有一行:GraphVAE、GraphRNN 点名即止, 机制牵涉第 34 章的概率图语言,此章不展开11。
聚合函数的选择问题被悬置:约束只有「排列不变」一条, 求和/平均/最大在「能分辨什么」上的差别,是下一章 GIN 一节的主题。
11. 可带走的
- 图数据的核心先验:连接结构本身携带信息,与属性同等重要;
- 三 种表示的分工:公式用邻接矩阵、稀疏图用邻接表、边操作用边列表;
- L = D − A 的两副面孔:Lx 是局部差异,xᵀLx 是全图相邻差值平方和(平滑度);
- 同质性低的图上,朴素的邻域平均可能帮倒忙;
- 任务三级:节点(用 h_v)、边(组合节点对)、图(全局汇聚); 差别只在读出,底座都是节点表示学习;
- 划分纪律:链接预测删目标边;图级按整图划分;时间数据按时间切;
- 一切 GNN = 消息构造 → 邻域聚合 → 状态更新(MPNN 框架);
- 层数 = 跳数 = 感受野,但层数不是越深越好(下一章给出三条病名);
- 聚合函数必须对邻居排列不变——邻居是集合,不是序列;
- 拿到任何一张图,先算度分布和同质性,再决定模型——先验检查比调参便宜。
12. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 图与关键性质 | 第9章 图神经网络 | text/10-ch09.txt:30(搜「节点（Nodes）与边（Edges」) · text/10-ch09.txt:30(搜「用于同时刻画实体及其」) |
| 无向/有向与同质/异质 | 第9章 图神经网络 | text/10-ch09.txt:51(搜「无向图（Undirected Graph」) · text/10-ch09.txt:61(搜「同质图（Homogeneous Graph」) · text/10-ch09.txt:66(搜「异质图（Heterogeneous Graph」) |
| 三种表示 | 第9章 图神经网络 | text/10-ch09.txt:98(搜「邻接矩阵（Adjacency Matrix」) · text/10-ch09.txt:120(搜「开销会很大」) · text/10-ch09.txt:123(搜「邻接表（Adjacency List」) · text/10-ch09.txt:126(搜「边列表（Edge List」) |
| 度与同质性 | 第9章 图神经网络 | text/10-ch09.txt:138(搜「度（Degree）」) · text/10-ch09.txt:140(搜「同质性（Homophily」) · text/10-ch09.txt:149(搜「削弱模型效果」) |
| 拉普拉斯矩阵 | 第9章 图神经网络 | text/10-ch09.txt:156(搜「拉普拉斯矩阵（Laplacian」) · text/10-ch09.txt:226(搜「图信号（Graph Signal」) · text/10-ch09.txt:237(搜「局部差异」) |
| 平滑性二次型 | 第9章 图神经网络 | text/10-ch09.txt:250(搜「衡量图信号的平滑性」) |
| 归一化拉普拉斯 | 第9章 图神经网络 | text/10-ch09.txt:253(搜「归一化拉普拉斯矩阵（Normalized」) |
| 三级任务 | 第9章 图神经网络 | text/10-ch09.txt:265(搜「节点级、边级和图级三个层」) · text/10-ch09.txt:270(搜「引文网络（Citation」) · text/10-ch09.txt:282(搜「节点分类是指」) · text/10-ch09.txt:300(搜「链接预测（Link Prediction」) · text/10-ch09.txt:321(搜「图分类是指」 |
| 划分纪律 | 第9章 图神经网络 | text/10-ch09.txt:337(搜「划分训练集、验证集和测试集时」) · text/10-ch09.txt:344(搜「删除或遮蔽」) |
| 消息传递与感受野 | 第9章 图神经网络 | text/10-ch09.txt:377(搜「消息传递机制（Message Passing Mechanism」) · text/10-ch09.txt:387(搜「𝐿 跳邻域」) · text/10-ch09.txt:388(搜「感受野（Receptive Field」) · text/10-ch09.txt:390(搜「过度平滑、过」) |
| 聚合与更新 | 第9章 图神经网络 | text/10-ch09.txt:405(搜「邻居本质上构成一个集合」) · text/10-ch09.txt:406(搜「常见的聚合函数包括求和」) · text/10-ch09.txt:419(搜「节点更新步骤中」) |
| MPNN 框架 | 第9章 图神经网络 | text/10-ch09.txt:416(搜「消息传递神经网络（Message Passing Neural Network」) |
| 读出与全局汇聚 | 第9章 图神经网络 | text/10-ch09.txt:460(搜「全局汇聚（Global Pooling」 · text/10-ch09.txt:476(搜「图神经网络的计算流程」) |