图神经网络 (Graph Neural Networks)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 的关系，以及层数太多时的“过平滑”。

Each network in the previous lessons assumed a "shape" for its input. An MLP wants a vector of fixed length in a fixed order; a CNN wants a regular grid of pixels; a transformer wants a sequence of tokens and lets every token see every other token. Much of what a robot deals with has a different shape:

• Deformable objects: a rope, a cloth or a lump of dough can be seen as many point masses (or mesh vertices) with forces between neighbouring ones.
• Robot bodies: links and joints form a tree (Lesson 7.1), and the trees of a quadruped, a hexapod and a snake robot all differ.
• Scenes: objects and the relations between them ("the cup is on the table"), the 3D scene graphs of Lesson 15.3.
• Multi-robot teams: each robot can only exchange information with the neighbours within radio range.
• Point clouds: lidar points and the points near them (Lesson 12.1).

Three things are common to all of them: the number of things varies (a rope of 6 segments or 12, four legs or six); the numbering is arbitrary (which mass is called number 1 changes nothing physical); and interactions are mostly local (a mass is pulled only by the springs attached to it). Concatenating everything into one long vector for an MLP breaks all three: a different size means retraining, a different numbering changes the output, and the network has to guess from data who is connected to whom.

A graph neural network (GNN) takes the graph itself as input. It runs one shared "message function" on every edge and one shared "update function" on every node, for a few rounds. The result works on graphs of any size, is insensitive to the numbering by construction, and lets only connected things talk directly. This lesson first shows what message passing does (FIG 1), then trains a learned rope simulator live (FIG 2), and then looks at permutation equivariance, graph attention (GAT), how transformers relate to GNNs, and the "oversmoothing" that appears with too many layers.

每个节点 \(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，看这个信号怎样一层一层扩散。

Every node \(i\) carries a feature vector \(\mathbf h_i\) (for a rope, a mass's velocity; for a robot, a joint angle; for an object, its class and position). One GNN layer does three things:

1. Send messages: on every edge \(j\to i\) one shared small network \(\phi\) computes a message \(\mathbf m_{ij}=\phi(\mathbf h_i,\mathbf h_j)\).
2. Aggregate: node \(i\) adds up the messages from all its neighbours \(\mathcal N(i)\) (or averages them, or takes the maximum). Addition does not care about order, which will matter a lot.
3. Update: another shared small network \(\psi\) combines the aggregate with the node's old state into a new \(\mathbf h_i\).

After one layer a node has "heard" only from its direct neighbours; after two, the neighbours already carry news from their own neighbours, so information has travelled two hops. In an \(L\)-layer GNN the output at node \(i\) depends only on nodes within \(L\) hops: that is its receptive field, the same thing as a CNN's receptive field growing with each layer (Lesson 17.1). The figure shows this with the simplest message passing there is, with no learnable parameters: each node's new value is the average of itself and all its neighbours. We put a 1 at one "source" node s and 0 everywhere else, and watch the signal spread layer by layer.

给真实的绳子、布料或面团写一个准确的物理模型很难，参数也难测。另一条路是让网络从数据里学会“下一步会怎样”，再像模拟器一样一步步滚动预测，这类模型叫学出来的模拟器（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\|\)。两者都只用相对位置，所以整根绳子平移时预测不变；等变版还保证：整根绳子旋转，消息跟着一起旋转。

Writing an accurate physical model of a real rope, cloth or lump of dough is hard, and its parameters are hard to measure. The alternative is to let a network learn "what happens next" from data and then roll it forward step by step like a simulator: a learned simulator (the general method of learning dynamics models is in Lesson 24.1). GNNs suit this especially well because physics is local: a mass's acceleration depends only on the springs attached to it.

The "real world" below is a mass-spring rope: every mass is 1, the spring stiffness is \(K=400\) (N/m per unit mass), the rest length is \(L_0=0.4\) m, and there is gravity plus a velocity damping of \(1.5\,\mathrm{s^{-1}}\); the first mass is pinned (and you can drag it). The graph's nodes are the masses and its edges the springs. The GNN does just one round of message passing:

• Each edge turns the relative displacement \(\mathbf d_{ij}=\mathbf x_j-\mathbf x_i\) of its two masses into a message \(\mathbf m_{ij}\) (think "the pull of the spring on \(i\)", although the network does not know there is a spring).
• Each node adds up its messages and a term \(\psi(\mathbf v_i)\) that sees only its own velocity (so it can learn gravity and damping), giving the acceleration \(\hat{\mathbf a}_i\).
• A semi-implicit Euler step (\(\Delta t=1/240\) s, Lesson 2.5) gives the next state, which is fed back into the GNN: the "rollout".

The training data are 600 snapshots of 6-mass ropes with random shapes and velocities, and the loss is the mean squared error between predicted and true accelerations (the supervised regression of Lesson 16.1). We train two edge networks at once, which differ in one thing only: the generic one is \(\mathbf m_{ij}=\mathrm{MLP}(d_x,d_y,\|\mathbf d\|)\in\R^2\); the equivariant one computes a single number from the length and sends it out along the spring, \(\mathbf m_{ij}=\mathrm{MLP}(\|\mathbf d\|)\,\mathbf d/\|\mathbf d\|\). Both see only relative positions, so shifting the whole rope leaves the prediction unchanged; the equivariant one also guarantees that rotating the whole rope rotates the messages with it.

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

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

Renumbering the nodes of a graph does not change the graph. Every step of a GNN uses only "who my neighbours are" and "add them up", never "what number I am", so after renumbering each node's output stays exactly the same and simply travels with the node: this is permutation equivariance. If we also add up the outputs of all nodes to get one vector for the whole graph (a readout), that vector does not even move: it is permutation invariant.

For robots this means one GNN policy can read the "joint graph" of any body and output a torque for every joint. The policy below is a randomly initialized two-layer message-passing network (untrained: we only care about its structural properties). Node features are the joint type (torso, hip, knee, ankle or snake segment, one-hot) plus the joint angle and angular velocity, and the angles change over time with a gait. For comparison, next to it is an MLP policy that concatenates all joint features in index order.

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

Equivariance has another side: a GNN cannot tell apart two nodes that "look the same". If all four legs had identical features they would necessarily get identical torques; the network could not make the left front leg do something different from the right hind leg. Real morphology policies therefore give nodes features that distinguish them, such as the joint type, the joint's position on the body or its depth in the tree (here: the type, plus the different phase each joint has in the gait).

汇总邻居时，每个邻居该占多大比重？图卷积网络（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 之间。

When aggregating neighbours, how much should each one count? The graph convolutional network (GCN, Kipf & Welling, 2017) lets the graph's structure decide: each neighbour (and the node itself) gets a fixed weight from degree normalization, roughly \(1/(d_i+1)\) on average, where \(d_i\) is the node's degree. The graph attention network (GAT, Veličković et al., 2018) lets the network decide: it scores every edge, takes a softmax over the neighbours, and uses the result \(\alpha_{ij}\) as weights. This is the attention mechanism of Lesson 17.3, except that each node may attend only to its neighbours.

When does the difference matter? Take a formation task: in a group of robots every follower must output the speed command \(s\) broadcast by its leader. Exactly one of its neighbours is a leader; the others are followers, each reporting its own \(s\) (distractors). Node features are \([b_j,\ s_j]\), with \(b_j=1\) for the leader and 0 otherwise. Below, a single-layer GCN and a single-layer GAT train side by side. Their message transform and output layer are identical; the only difference is where the weights come from: uniform for the GCN, learned attention for the GAT. Every step uses 16 fresh random samples with 2 to 6 neighbours.

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

Why can the GCN not learn this? Its output is a fixed weighted average of the neighbours' features followed by a transform, in which the leader's \(s\) is only a \(1/(k+1)\) share, mixed with the followers' values: the network cannot use the "is leader" feature to change the weights, because the weights do not depend on features at all. The GAT's score function does see that feature: by giving "is leader" a large score, the softmax hands nearly all the weight to it. This does not make GCNs useless: when all neighbours matter equally (smoothing a sensor field, diffusion on a mesh), fixed weights are exactly right, and cheaper and more stable.

把 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\)，所有人都去看最东边的那个物体（像所有机器人都盯着同一个目标）。

Drop GAT's "attend only to neighbours", let every node attend to every node, and you have the self-attention layer of Lesson 17.3: a transformer is a GNN doing message passing on the complete graph, with the attention weights as edge weights. Conversely, a GNN can be seen as a transformer with a "mask": the scores of unconnected pairs are set to \(-\infty\), so after the softmax their weight is 0. The whole difference is where the graph comes from: a GNN hard-codes "who is related to whom" as a prior in the graph, a transformer lets the network learn it.

The figure has 10 tokens (think of 10 objects in a scene; drag them), and the graph is set by a radius \(r\): two tokens at most \(r\) apart are joined by an edge. On the right is the \(10\times10\) attention matrix; each row holds one token's weights over the others. There are two kinds of scores: local scores \(e_{ij}=-\|\mathbf p_i-\mathbf p_j\|^2/2\), where nearby objects attend to each other, much like physical interactions; and non-local scores \(e_{ij}=1.2\,x_j\), where everyone looks at the easternmost object (as when every robot watches the same target).

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

This is the core trade-off between a GNN and a transformer. If the interactions really are local (springs, contacts, neighbouring points), the graph is a good prior: the cost grows with the number of edges instead of \(n^2\), and less data is needed. If an important relation can appear between any two things (two words far apart in a sentence; in a robot policy, a seen object and the joint that must move), the complete graph is safer, at a cost of \(O(n^2)\). The complete graph carries no structure, so a transformer needs positional encodings to know how tokens relate; graph transformers often use eigenvectors of the graph Laplacian or random-walk statistics as node positional encodings, giving the structure back in a "soft" form.

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

If \(L\) layers see only \(L\) hops, why not just use many layers? The problem: every layer averages over neighbours, and repeated averaging pulls the features of all nodes towards one value, like heat spreading through a piece of metal until it is the same temperature everywhere. This is oversmoothing. The graph below has two communities (10 nodes each, circles and squares), tightly connected inside and joined by only 7 bridges (dashed purple). The initial features are "+1 for community A, −1 for B" plus noise, and then the mean aggregation of FIG 1 is applied over and over.

图 \(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\) 层是

A graph \(G=(\mathcal V,\mathcal E)\) has \(n\) nodes and an adjacency matrix \(A\in\{0,1\}^{n\times n}\) (\(A_{ij}=1\) when \(i\) and \(j\) are connected); node features are stacked as rows of \(X\in\R^{n\times d}\), and edges may carry features \(\mathbf e_{ij}\) (a relative displacement, say). Let \(\mathbf h_i^{(0)}=\mathbf x_i\). Layer \(l\) of a general message-passing neural network (MPNN, Gilmer et al., 2017) is

\(\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 正是这种“边算作用、节点汇总”的结构）：

\(\phi\) and \(\psi\) are small MLPs shared by every edge and every node; \(\bigoplus\) is a sum, mean or maximum over neighbours, any operation that ignores order. Substituting repeatedly shows that \(\mathbf h_i^{(L)}\) depends only on inputs in \(\hl{rf}{\mathcal N_L(i)}=\{j:\operatorname{dist}(i,j)\le L\}\): the receptive field of FIG 1. FIG 1's parameter-free version is \(\phi(\mathbf h_i,\mathbf h_j)=\mathbf h_j\) with a sum for \(\bigoplus\) and \(\psi\) dividing by \(\deg(i)+1\); as a matrix the whole layer is \(H^{(l+1)}=\tilde D^{-1}\tilde AH^{(l)}\), where \(\tilde A=A+I\) adds self-loops and \(\tilde D\) is the diagonal degree matrix of \(\tilde A\).

The learned simulator of FIG 2 is the special case \(L=1\) (the interaction network of Battaglia et al. has exactly this "edges compute effects, nodes aggregate" structure):

真实加速度是 \(\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 里画出等变模型在每个质点上的消息之和（绿色箭头）。

The true acceleration is \(\mathbf a_i=\sum_j K(\|\mathbf d_{ij}\|-L_0)\,\mathbf d_{ij}/\|\mathbf d_{ij}\|+\mathbf g-c\,\mathbf v_i\), where \(\mathcal D\) is the set of training snapshots and \(\mathcal F\) the masses that are not pinned; \(\phi_1\) is the generic model and \(\phi_2\) the equivariant one. The equivariant model only has to learn the one-dimensional function \(K(\|\mathbf d\|-L_0)\). The rollout is \(\mathbf v\leftarrow\mathbf v+\Delta t\,\hat{\mathbf a}\), \(\mathbf x\leftarrow\mathbf x+\Delta t\,\mathbf v\). Hovering \(\sum_j\phi\) draws the equivariant model's summed messages at every mass in FIG 2 (green arrows).

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

A renumbering is a permutation matrix \(P\): the features become \(PX\) and the adjacency becomes \(PAP^\top\). Let \(F\) be one (or several) GNN layers, with one output row per node. Then

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

The left identity is equivariance: the outputs are reordered along with the nodes; the right one is invariance: the readout does not move at all. The proof is one line: node \(i\)'s new state is decided by its own feature and the multiset \(\{\mathbf h_j:j\in\mathcal N(i)\}\); renumbering does not change that multiset, and \(\bigoplus\) ignores the order of its elements. An MLP policy \(f(\operatorname{vec}(X))\) lacks this property: its first layer multiplies joint 1's features by weight block 1, so a renumbering swaps in different weights, which is how the red bars in FIG 3 jump away.

三行依次是 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)\)。

The three lines are the GCN, the GAT and masked attention. The GCN weights \(1/\sqrt{\tilde d_i\tilde d_j}\) depend only on degrees; the GAT weights \(\alpha_{ij}\) are computed from features, where \([\cdot\|\cdot]\) is concatenation and \(\mathbf a\) a learnable scoring vector; in practice several "heads" run in parallel and are concatenated, as in a transformer. The last line writes the attention of Lesson 17.3 as a GNN: with \(M\equiv0\) it is the complete graph, i.e. an ordinary transformer layer; with \(M\) set to 0 or \(-\infty\) by a graph it is attention on that graph. Hovering \(\alpha_{ij}\) highlights the GAT weight labels in FIG 4; hovering \(M_{ij}\) marks the masked cells of FIG 5 in red. FIG 4's GAT scores are exactly the formula above (plus a bias), except that the LeakyReLU's negative slope is 0.01 instead of the original paper's 0.2; FIG 4's GCN uses the uniform mean weights \(1/(k+1)\) rather than the symmetric normalization. The cost per layer is \(O(|\mathcal E|)\) for both GCN and GAT, and \(O(n^2)\) for attention on the complete graph.

聚合函数决定 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 正是这样：弹簧力是加起来的，平均就错了。

The aggregator decides which neighbourhoods a GNN can tell apart. Let one node's multiset of neighbour features be \(\{a\}\) and another's \(\{a,a\}\): mean and max give the same result, the sum does not (\(a\) versus \(2a\)); the multisets \(\{a,b\}\) and \(\{a,a,b,b\}\) have the same mean, and \(\{a,b\}\) and \(\{a,b,b\}\) the same max. Xu et al. (2019) proved that message passing alone can distinguish graphs at most as well as the Weisfeiler-Lehman (1-WL) graph isomorphism test, and that GIN, built on "sum + MLP", reaches that bound. So when "how many" matters (how many contacts, how many neighbours), use the sum; FIG 2 does exactly this: spring forces add up, so a mean would be wrong.

没有可学权重时，\(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 向量。把初始特征按特征向量展开：

Without learnable weights, \(L\) layers of mean aggregation are \(H^{(L)}=P^LX\) with \(P=\tilde D^{-1}\tilde A\). \(P\) is similar to the symmetric matrix \(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}\), so its eigenvalues are real and lie in \((-1,1]\) (with self-loops even the smallest is above \(-1\)); for a connected graph the largest is \(\lambda_1=1\), with the all-ones vector as eigenvector. Expanding the initial features in eigenvectors:

所有节点收敛到同一个值 \(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 每层还有权重和非线性，分析更复杂，但同样的现象在实践中很常见；常用的对策是残差连接、归一化，以及干脆不用太多层，让远处的信息通过别的途径（比如一个连到所有节点的“虚拟节点”或全局注意力）传过来。

All nodes converge to the same value \(c_1\), and the differences die out at the rate \(|\lambda_2|^L\). For the graph of FIG 6, \(\lambda_2=0.919\) and \(\lambda_3=0.643\): the community gap lies almost entirely along the eigenvector of \(\lambda_2\) (whose signs roughly split the two communities, which is the idea behind spectral clustering), so it decays by only 8% per layer, while the noise inside communities lies mostly along \(\lambda_3\) and beyond and decays much faster. That explains "first denoising, then washing out": the first few layers help, later ones hurt. The more tightly the communities are connected, the smaller \(\lambda_2\) and the sooner oversmoothing sets in. The second line is the version with an initial residual (APPNP, i.e. personalized PageRank): its fixed point is no longer a constant vector, so the gap survives. Hovering \(\lambda_2\) thickens the dashed line in FIG 6. Real GNNs also have weights and nonlinearities in every layer, which complicates the analysis, but the same phenomenon is common in practice; the usual remedies are residual connections, normalization, and simply not using many layers, letting distant information arrive another way (a "virtual node" connected to every node, or global attention).

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

In robotics, GNNs show up mainly in four kinds of problems, which line up with the figures of this lesson: dynamics of deformable objects and particles (FIG 2), bodies whose shape varies (FIG 3), relations between robots and between objects in a scene (FIG 4, FIG 5), and data with no natural order, such as point clouds.

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

The link to Part IV is worth noting too: the pose graph of Lesson 15.2 is also a graph, with poses as nodes and relative measurements as edges, but there the "messages" (Jacobians, information matrices) are derived from the measurement model and solving it is a least-squares problem. A GNN uses the same kind of graph structure but learns the message rules from data. The two can be combined: a GNN predicts measurements or weights in a factor graph, and a classical optimizer solves it.