图神经网络 (Graph Neural Networks)

前面几节的网络各自假设了输入的“形状”。MLP 要一个长度固定、顺序固定的向量；CNN 要规则的像素网格；Transformer 要一串 token，并让每个 token 都能看到所有其他 token。可机器人遇到的很多数据是另一种形状：

• 可变形物体：绳子、布料、面团可以看成许多质点（或网格顶点），相邻的质点之间有力。
• 机器人本体：连杆和关节组成一棵树（7.1 节）；四足、六足和蛇形机器人的树长得不一样。
• 场景：物体和它们之间的关系（“杯子在桌上”），也就是 15.3 节讲的三维场景图。
• 多机器人：每台机器人只能和通信范围内的邻居交换信息。
• 点云：激光雷达的点和它附近的点（12.1 节）。

这些数据有三个共同点：东西的数量会变（6 段绳子还是 12 段，4 条腿还是 6 条）；东西的编号是随意的（谁是 1 号质点不影响物理）；相互作用主要是局部的（一个质点只被和它相连的弹簧拉）。把它们拼成一个长向量喂给 MLP，这三点全都违反了：换个大小网络就要重训，换个编号输出就变，而且网络得从数据里自己猜出谁和谁相连。

图神经网络（GNN）把图本身当作输入。它在每条边上运行同一个“消息函数”，在每个节点上运行同一个“更新函数”，重复几轮。这样得到的网络对任意大小的图都能用，对节点编号天然不敏感，而且只让相连的东西直接对话。本节先看消息传递在做什么（FIG 1），再现场训练一个学出来的绳子模拟器（FIG 2），然后看置换等变性、图注意力 GAT、Transformer 与 GNN 的关系，以及层数太多时的“过平滑”。

每个节点 \(i\) 带一个特征向量 \(\mathbf h_i\)（对绳子是质点的速度，对机器人是关节角，对物体是它的类别和位置）。GNN 的一层做三件事：

1. 发消息：每条边 \(j\to i\) 用同一个小网络 \(\phi\) 算出一条消息 \(\mathbf m_{ij}=\phi(\mathbf h_i,\mathbf h_j)\)。
2. 汇总：节点 \(i\) 把来自所有邻居 \(\mathcal N(i)\) 的消息加起来（或取平均、取最大）。加法不在乎顺序，这一点后面很关键。
3. 更新：用另一个共享的小网络 \(\psi\) 把汇总结果和自己原来的状态合成新的 \(\mathbf h_i\)。

一层之后，节点只“听说”了它的直接邻居；两层之后，邻居已经带着邻居的邻居的消息，于是信息传了两跳。\(L\) 层 GNN 里，节点 \(i\) 的输出只依赖于 \(L\) 跳以内的节点：这就是它的感受野，和 CNN 每加一层感受野就变大（17.1 节）是同一回事。下图用最简单的、没有任何可学参数的消息传递来看这个过程：每个节点的新值是它自己和所有邻居的平均。我们只在一个“源”节点 s 放入 1，其余为 0，看这个信号怎样一层一层扩散。

给真实的绳子、布料或面团写一个准确的物理模型很难，参数也难测。另一条路是让网络从数据里学会“下一步会怎样”，再像模拟器一样一步步滚动预测，这类模型叫学出来的模拟器（learned simulator），学动力学模型的一般方法见 24.1 节。GNN 特别适合做这件事，因为物理本来就是局部的：一个质点的加速度只取决于和它相连的弹簧。

下面的“真实世界”是一根质点-弹簧绳：每个质点质量为 1，弹簧刚度 \(K=400\)（单位质量下为 N/m），静止长度 \(L_0=0.4\) m，有重力和速度阻尼 \(1.5\,\mathrm{s^{-1}}\)，第一个质点被钉住（可以拖动）。图的节点是质点，边是弹簧。GNN 只做一轮消息传递：

• 每条边用两质点的相对位移 \(\mathbf d_{ij}=\mathbf x_j-\mathbf x_i\) 算出一条消息 \(\mathbf m_{ij}\)（可以理解为“弹簧对 \(i\) 的拉力”，但网络并不知道有弹簧这回事）。
• 节点把所有消息加起来，再加上一个只看自己速度的项 \(\psi(\mathbf v_i)\)（让它学会重力和阻尼），得到加速度 \(\hat{\mathbf a}_i\)。
• 用半隐式欧拉法积分（\(\Delta t=1/240\) s，2.5 节）得到下一时刻的状态，再把它喂回 GNN：这就是“滚动”（rollout）。

训练数据是 600 个随机形状、随机速度的6 质点绳子快照，损失是预测加速度和真实加速度之间的均方误差（16.1 节的监督回归）。我们同时训练两种边网络，它们只在一点上不同：通用版 \(\mathbf m_{ij}=\mathrm{MLP}(d_x,d_y,\|\mathbf d\|)\in\R^2\)；等变版先只用长度算一个标量，再沿弹簧方向放出去，\(\mathbf m_{ij}=\mathrm{MLP}(\|\mathbf d\|)\,\mathbf d/\|\mathbf d\|\)。两者都只用相对位置，所以整根绳子平移时预测不变；等变版还保证：整根绳子旋转，消息跟着一起旋转。

给图的节点重新编号，图本身并没有变。GNN 的每一步都只用“我的邻居是谁”和“加起来”，不用“我是第几号”，所以重新编号之后，每个节点的输出原封不动地跟着它走：这叫置换等变（permutation equivariance）。如果再把所有节点的输出加起来得到整张图的一个向量（readout），这个向量连跟着走都不用，完全不变：置换不变。

这对机器人的意义是：同一个 GNN 策略可以读入任意一种身体的“关节图”，为每个关节输出一个力矩。下图里的策略是一个随机初始化的两层消息传递网络（没有训练，我们只关心它的结构性质）：节点特征是关节类型（躯干、髋、膝、踝或蛇的体节，独热编码）加上关节角和角速度，关节角随时间按步态变化。作为对比，旁边是一个把所有关节特征按编号顺序拼起来的 MLP 策略。

等变性也有另一面：GNN 分不清两个“看起来一样”的节点。如果四条腿的特征完全相同，它们必然得到完全相同的力矩，网络不可能让左前腿和右后腿做不同的事。所以真实的形态学策略会给节点加上能区分它们的特征，比如关节类型、关节在身体上的位置、或者它在树里的深度（这里用的是类型，加上各关节在步态里不同的相位）。

汇总邻居时，每个邻居该占多大比重？图卷积网络（GCN，Kipf 与 Welling，2017）的答案由图的结构决定：每个邻居（连同自己）按度数归一化后的固定权重，平均下来大致是 \(1/(d_i+1)\)，\(d_i\) 是节点的度数。图注意力网络（GAT，Veličković 等，2018）则让网络自己决定：对每条边算一个分数，在邻居之间做 softmax，得到权重 \(\alpha_{ij}\)，这和 17.3 节的注意力是同一个机制，只是每个节点只能注意它的邻居。

什么时候这个区别要紧？看一个编队任务：一群机器人里，每台跟随者都要输出领队广播的速度指令 \(s\)。它的邻居里恰好有一台领队，其余是其他跟随者，各自也报着自己的 \(s\)（干扰项）。节点特征是 \([b_j,\ s_j]\)，领队的 \(b_j=1\)，其余为 0。下面同时训练一个单层 GCN 和一个单层 GAT，两者的消息变换和输出层完全一样，唯一的区别是权重来源：GCN 用均匀权重，GAT 用学出来的注意力。每一步用 16 个新的随机样本，邻居数在 2 到 6 之间。

为什么 GCN 学不会？它的输出是邻居特征的固定加权平均再做变换，领队的 \(s\) 只占其中 \(1/(k+1)\)，而且混着其他跟随者的 \(s\)：网络无法根据“是否领队”这个特征去调整权重，因为权重根本不由特征决定。GAT 的分数函数看得到这个特征，只要给“是领队”很大的分数，softmax 就把几乎全部权重给它。这不是说 GCN 没用：当邻居都同样重要（比如平滑一个传感器场，或者网格上的扩散）时，固定权重正合适，而且更便宜、更稳定。

把 GAT 的“只注意邻居”去掉，让每个节点注意所有节点，就得到了 17.3 节的自注意力层：Transformer 就是在完全图上做消息传递的 GNN，注意力权重就是边上的权重。反过来，一个 GNN 也可以看成一个带“掩码”的 Transformer：不相连的节点对的注意力分数被设成 \(-\infty\)，softmax 之后权重为 0。区别就在于这张图从哪里来：GNN 把“谁和谁有关”作为先验写死在图里，Transformer 让网络自己去学。

下图有 10 个 token（可以想成场景里的 10 个物体，位置可拖动），图由半径 \(r\) 决定：距离不超过 \(r\) 的两个 token 之间有边。右边是 \(10\times10\) 的注意力矩阵，每一行是一个 token 对其他 token 的权重。两种分数：局部分数 \(e_{ij}=-\|\mathbf p_i-\mathbf p_j\|^2/2\)，近的物体互相关注，类似物理相互作用；非局部分数 \(e_{ij}=1.2\,x_j\)，所有人都去看最东边的那个物体（像所有机器人都盯着同一个目标）。

这就是选 GNN 还是 Transformer 的核心权衡。如果相互作用真的是局部的（弹簧、接触、相邻的点），图是一个好先验：计算量随边数线性增长而不是 \(n^2\)，数据也省。如果重要的关系可能出现在任意两个东西之间（一句话里相距很远的两个词，一个机器人策略里“看到的物体”和“要动的关节”），完全图更安全，代价是 \(O(n^2)\) 的计算。完全图里没有结构信息，所以 Transformer 必须靠位置编码知道 token 之间的关系；图 Transformer 常用图拉普拉斯矩阵的特征向量或随机游走统计量作为节点的位置编码，把图的结构以“软”的方式交还给它。

既然 \(L\) 层只能看到 \(L\) 跳，那把层数加到很多不就行了？问题是：每一层都在对邻居做平均，而反复平均会把所有节点的特征拉到同一个值，就像热量在一块金属里扩散到处处同温。这叫过平滑（oversmoothing）。下图是两个社区（各 10 个节点，圆形和方形）组成的图，社区内部连得紧，之间只有 7 条桥（紫色虚线）。初始特征是“社区 A 为 +1，B 为 −1”再加噪声，然后反复做 FIG 1 那样的均值聚合。

图 \(G=(\mathcal V,\mathcal E)\) 有 \(n\) 个节点，邻接矩阵 \(A\in\{0,1\}^{n\times n}\)（\(A_{ij}=1\) 表示 \(i,j\) 相连），节点特征按行堆成 \(X\in\R^{n\times d}\)，边可以有特征 \(\mathbf e_{ij}\)（比如相对位移）。记 \(\mathbf h_i^{(0)}=\mathbf x_i\)。一般的消息传递神经网络（MPNN，Gilmer 等，2017）的第 \(l\) 层是

\(\phi\) 和 \(\psi\) 是小 MLP，在所有边、所有节点上共享；\(\bigoplus\) 是对邻居的求和、平均或最大值，任何“与顺序无关”的运算都行。反复代入可知 \(\mathbf h_i^{(L)}\) 只依赖于 \(\hl{rf}{\mathcal N_L(i)}=\{j:\operatorname{dist}(i,j)\le L\}\) 里的输入：这就是 FIG 1 的感受野。FIG 1 的无参数版本是 \(\phi(\mathbf h_i,\mathbf h_j)=\mathbf h_j\)、\(\bigoplus\) 取和、\(\psi\) 除以 \(\deg(i)+1\)，整层写成矩阵就是 \(H^{(l+1)}=\tilde D^{-1}\tilde AH^{(l)}\)，其中 \(\tilde A=A+I\) 加了自环，\(\tilde D\) 是 \(\tilde A\) 的度数对角阵。

FIG 2 的学出来的模拟器是 \(L=1\) 的特例（Battaglia 等的 interaction network 正是这种“边算作用、节点汇总”的结构）：

真实加速度是 \(\mathbf a_i=\sum_j K(\|\mathbf d_{ij}\|-L_0)\,\mathbf d_{ij}/\|\mathbf d_{ij}\|+\mathbf g-c\,\mathbf v_i\)，其中 \(\mathcal D\) 是训练快照的集合，\(\mathcal F\) 是没被钉住的质点；\(\phi_1\) 是通用版，\(\phi_2\) 是等变版。等变版只需要学会一维函数 \(K(\|\mathbf d\|-L_0)\)。滚动时 \(\mathbf v\leftarrow\mathbf v+\Delta t\,\hat{\mathbf a}\)，\(\mathbf x\leftarrow\mathbf x+\Delta t\,\mathbf v\)。悬停 \(\sum_j\phi\) 会在 FIG 2 里画出等变模型在每个质点上的消息之和（绿色箭头）。

重新编号用置换矩阵 \(P\) 表示：特征变成 \(PX\)，邻接矩阵变成 \(PAP^\top\)。设 \(F\) 是一层（或多层）GNN，输出每个节点一行。则

左式是等变：输出跟着节点一起重排；右式是不变：读出完全不动。证明只要一行：节点 \(i\) 的新状态由它自己的特征和多重集 \(\{\mathbf h_j:j\in\mathcal N(i)\}\) 决定，重新编号不改变这个多重集，而 \(\bigoplus\) 不在乎元素的顺序。MLP 策略 \(f(\operatorname{vec}(X))\) 没有这个性质：它的第一层把第 1 个关节的特征乘上第 1 组权重，重新编号就换了一组权重，FIG 3 里的红条就是这样跳走的。

三行依次是 GCN、GAT 和带掩码的注意力。GCN 的权重 \(1/\sqrt{\tilde d_i\tilde d_j}\) 只由度数决定；GAT 的权重 \(\alpha_{ij}\) 由特征算出，\([\cdot\|\cdot]\) 是拼接，\(\mathbf a\) 是可学的打分向量，实际中还会像 Transformer 一样用多个“头”并行再拼接。最后一行把 17.3 节的注意力写成了 GNN：\(M\equiv0\) 时就是完全图，也就是普通的 Transformer 层；\(M\) 按图取 0 或 \(-\infty\) 时就是在图上做注意力。悬停 \(\alpha_{ij}\) 会在 FIG 4 里高亮 GAT 的权重标签，悬停 \(M_{ij}\) 会在 FIG 5 里把被掩码的格子标红。FIG 4 的 GAT 打分正是上式（多一个偏置项），只是 LeakyReLU 负半轴的斜率取 0.01，而不是原论文的 0.2；FIG 4 的 GCN 用的是均值形式的均匀权重 \(1/(k+1)\)，而不是对称归一化。每层的计算量：GCN 和 GAT 都是 \(O(|\mathcal E|)\)，完全图上的注意力是 \(O(n^2)\)。

聚合函数决定 GNN 能区分哪些邻域。设一个节点的邻居特征多重集是 \(\{a\}\)，另一个是 \(\{a,a\}\)：平均和最大值给出一样的结果，求和却不同（\(a\) 对 \(2a\)）；多重集 \(\{a,b\}\) 与 \(\{a,a,b,b\}\) 平均值相同，\(\{a,b\}\) 与 \(\{a,b,b\}\) 最大值相同。Xu 等（2019）证明，只靠消息传递的 GNN 区分不同图的能力最多和 Weisfeiler-Lehman（1-WL）图同构测试一样强，而用“求和 + MLP”的 GIN 能达到这个上限。所以当“有几个”很重要时（几个接触点、几个邻居），用求和；FIG 2 正是这样：弹簧力是加起来的，平均就错了。

没有可学权重时，\(L\) 层均值聚合就是 \(H^{(L)}=P^LX\)，\(P=\tilde D^{-1}\tilde A\)。\(P\) 与对称矩阵 \(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}\) 相似，特征值都是实数，落在 \((-1,1]\) 里（加了自环之后最小的也大于 \(-1\)）；连通图的最大特征值 \(\lambda_1=1\)，对应的特征向量是全 1 向量。把初始特征按特征向量展开：

所有节点收敛到同一个值 \(c_1\)，差别以 \(|\lambda_2|^L\) 的速度消失。FIG 6 的图里 \(\lambda_2=0.919\)，\(\lambda_3=0.643\)：社区差几乎全部落在 \(\lambda_2\) 对应的特征向量上（它的正负号大致把两个社区分开，这就是谱聚类的道理），所以每层只衰减 8%；社区内的噪声多半落在 \(\lambda_3\) 及以后的特征向量上，衰减快得多。这解释了“先去噪、再抹平”：前几层有益，之后有害。社区之间连得越紧，\(\lambda_2\) 越小，过平滑来得越早。第二行是带初始残差的版本（APPNP，即个性化 PageRank），它的不动点不再是常数向量，所以社区差留了下来。悬停 \(\lambda_2\) 会加粗 FIG 6 里的虚线。真实的 GNN 每层还有权重和非线性，分析更复杂，但同样的现象在实践中很常见；常用的对策是残差连接、归一化，以及干脆不用太多层，让远处的信息通过别的途径（比如一个连到所有节点的“虚拟节点”或全局注意力）传过来。

在机器人里，GNN 主要出现在四类问题上，它们恰好对应本节的几个图：可变形物体与粒子的动力学（FIG 2），可变形态的身体（FIG 3），多机器人和场景里的关系（FIG 4、FIG 5），以及点云这类没有天然顺序的数据。

和 Part IV 的联系也值得一提：15.2 节的位姿图也是一张图，节点是位姿，边是相对测量，但那里的“消息”（雅可比、信息矩阵）是从测量模型推导出来的，求解是一个最小二乘问题。GNN 用同样的图结构，只是让消息规则从数据里学出来。两者可以结合：用 GNN 预测因子图里的测量或权重，再交给经典优化器求解。