L08b 邻居聚合:ÃX 求和、按度平均和对称归一化
GCN 的第一步是让每个节点把自己和邻居的特征收集起来。直接相加会让邻居多的节点数值偏大,所以要按度归一化。这一页用课件的五节点图逐步算 ÃX、D̃⁻¹ÃX,再比较四种归一化写法。
一句话版
每个节点的新特征,来自它自己和邻居的旧特征。用矩阵写,Ã 乘 X 就是把这些特征加起来。直接相加会让邻居多的节点数值偏大,所以要按度除一下,GCN 用的除法是左右各除以 √d̃。
上一页 L08a 把图写成了 Ã、D̃、X,这一页在它们上面做乘法。
先认识这几个词
读之前最好会矩阵乘法:结果第 i 行第 j 列 = 左矩阵第 i 行和右矩阵第 j 列对应相乘再相加,不熟看 P01a。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 聚合 | aggregate | 把邻居的信息收集到一起 |
| 消息传递 | message passing | 邻居把自己的特征「发」给中心节点 |
| 归一化 | normalize | 除以某个数,让大小可以比较 |
| D̃⁻¹ | D̃ 的逆 | 对角线取倒数的对角矩阵 |
| D̃^-1/2 | D̃ 的负二分之一次方 | 对角线取「1 除以平方根」 |
| Â | A-hat | GCN 用的归一化邻接矩阵 |
一个类比:小组打分
每个同学的成绩要参考自己和好友的成绩来调整。最直接的做法是把自己和所有好友的分数加起来。
问题马上就来了:好友多的同学加了一长串,总分自然高,和好友少的人没法比。改成取平均就公平了:好友多就除以大数,好友少就除以小数。
再细一点:某个好友本身人缘很广,跟谁都连着,他对每个人的影响应该打点折扣。GCN 的对称归一化就是同时考虑「我有几个好友」和「这个好友有几个好友」。
类比在哪里失效:
- 成绩是一个数,节点特征是一串数,每一列分别做同样的加和除。
- 真实小组里每个好友的影响可能不同。这一页的几种做法里,权重只由度决定,和特征内容无关;按内容定权重是 attention 的思路,见 L07d。
从零讲起
1. 消息传递:ÃX 把邻居特征加起来
它解决什么问题
节点分类时,一个节点自己的特征往往不够,它的邻居也提供线索:好友都支持某位候选人,这个人大概率也支持。要一种运算,让每个节点同时拿到自己和所有邻居的信息,而且所有节点一次算完。
直觉
à 的第 i 行在「自己和邻居」的位置上是 1,其余是 0。拿这一行去乘 X,相当于把 1 所在的那几行特征挑出来加在一起。
所有行同时这样做,就是矩阵乘法 ÃX。
一步一步看
目标:用五节点图算 ÃX 的每一行,看各节点加的项数从 3 到 5 不等,度大的节点数值也更大。
用课件的五节点图,算 ÃX 的 A 行。
-
à 的 A 行是 1 1 1 0 0:A 自己、B、C 三个位置是 1。
-
从 X 里挑出 A、B、C 三行特征,按列相加,得到 [-0.3, -2.0, 1.6]。
-
其余四行同理。B 的邻居最多,B 行要加 5 项。
-
把五行和每行加的项数并排放,看出项数从 3 到 5 不等。
-
加的项越多,结果的数值尺度越大。课件红字:度大的节点数值更大,需要归一化。
怎么算
(ÃX) 的第 i 行 = Σ_j Ã[i][j] × X 的第 j 行
意思是:Ã[i][j] 只有 0 和 1,等于 1 的那些 j 就是节点 i 自己和它的邻居。所以结果的第 i 行就是这些节点特征的和。课件把这一步叫 message pass:每个邻居把自己的特征「传」给中心节点。
为什么要加自环:如果用 A 而不是 Ã,A 的对角线是 0,结果里就只有邻居,没有节点自己的特征。
常见误解
以为 ÃX 只收集邻居,不包括自己
à 对角线是 1,所以自己的特征也加进去了。只收集邻居的是 AX,课件用的是 ÃX。
以为求和的结果可以直接拿来比较不同节点
B 加了 5 项,A 只加了 3 项,两者的数值尺度不一样,直接比较会偏向度大的节点。这正是下一步要归一化的原因。
试一下
用课件的特征,算 ÃX 的 D 行(D 的邻居是 B、E)。
D + B + E = [1.8+0.1+2.1, 0.1+0.2-0.2, -2.1+1.2+1.0] = [4.0, 0.1, 0.1]。
2. 按行平均:D̃⁻¹ÃX
它解决什么问题
直接求和让度大的节点数值偏大。最简单的修正是取平均:每个节点的和除以它加了几项,也就是除以 d̃。这样每个节点的新特征都是「自己和邻居的平均值」,大小可以比较。
直觉
D̃⁻¹ 是对角线取倒数的对角矩阵。对角矩阵左乘一个矩阵,效果是把每一行乘以对角线上对应的数。所以 D̃⁻¹ÃX 就是把 ÃX 的每一行除以该节点的 d̃。
一步一步看
目标:把 ÃX 每行除以自己的度,看权重矩阵每行加起来为 1,同一个邻居在不同行里分到的份额不同。
-
D̃ = diag(3, 5, 4, 3, 4),取倒数得 D̃⁻¹ = diag(1/3, 1/5, 1/4, 1/3, 1/4)。
-
ÃX 的 A 行 [-0.3, -2.0, 1.6] 除以 3,得到约 [-0.1, -0.667, 0.533]。
-
B 行除以 5:[3.6, -2.1, 0.5] 变成 [0.72, -0.42, 0.1]。其余行依此类推。
-
换个角度看权重矩阵 D̃⁻¹Ã:A 行是 1/3、1/3、1/3、0、0,每行加起来都是 1。
-
同一个邻居 B,在 A 行里占 1/3,在 C 行里占 1/4:它对不同中心节点的贡献不同,只取决于中心节点自己的度。
怎么算
D̃⁻¹ÃX 的第 i 行 = (1/d̃_i) × (节点 i 自己和邻居的特征之和)
意思是:先像上一节那样求和,再除以项数 d̃_i,得到平均值。权重矩阵 D̃⁻¹Ã 每行之和为 1,课件称为 Normalized but asymmetric(归一化了但不对称)、Averaged in rows(按行平均)。
不对称是因为只按「中心节点」的度来除。A 行 B 列是 1/3(按 A 的度),B 行 A 列是 1/5(按 B 的度),两个数不一样。
常见误解
以为 D̃⁻¹ 是把 D̃ 每一格都取倒数
只取对角线的倒数,对角线以外的 0 保持 0(0 没有倒数)。课件例子图的 D̃⁻¹ 就是 diag(1/3, 1/5, 1/4, 1/3, 1/4)。
以为按行平均以后,同一个邻居对每个中心节点的贡献一样
不一样。B 在 A 行占 1/3,在 C 行占 1/4。同一行里各邻居贡献相等,跨行就不等了。
试一下
算 D̃⁻¹ÃX 的 C 行。ÃX 的 C 行是 [1.8, -2.2, 2.6],d̃_C 是多少?
d̃_C = 4,C 行 = [1.8/4, -2.2/4, 2.6/4] = [0.45, -0.55, 0.65]。
3. 对称归一化:D̃^-1/2 Ã D̃^-1/2
它解决什么问题
按行平均只看中心节点的度,没看邻居的度。一个跟谁都连着的「大 V」邻居,对每个人的影响都一样大,这不太合理。而且 D̃⁻¹Ã 不对称,A 对 B 的权重和 B 对 A 的权重不等。要一种同时考虑两端度数、又保持对称的写法。
从哪来(补充)
Kipf 和 Welling 2016 年 9 月在 arXiv 发布 GCN 论文,2017 年发表于 ICLR。论文的传播规则就用 D̃^-1/2 Ã D̃^-1/2 来归一化,摘要说方法来自谱图卷积的局部一阶近似。课件后面定义的 Â 就是这个矩阵。
直觉
左乘 D̃⁻¹ 是每行除以中心节点的度,右乘 D̃⁻¹ 是每列除以邻居的度。左右都乘 D̃⁻¹ 就除了两次,权重变得太小。
折中办法是左右各乘 D̃^-1/2:每行除以 √(中心度),每列除以 √(邻居度)。合起来,i 和 j 之间的权重是 1/√(d̃_i × d̃_j)。
一步一步看
目标:用 A 行比较四种写法给 A、B、C 的权重,看对称归一化怎样让度越大的邻居分到越少。
还看课件图的 A 行,比较四种写法给 A、B、C 的权重。
-
ÃX 求和:权重 1、1、1,行和 3。
-
D̃⁻¹ÃX 按行平均:权重都是 1/3,行和 1。
-
D̃⁻¹ÃD̃⁻¹X 除两次:A-A 是 1/(3×3) = 1/9,A-B 是 1/(3×5) = 1/15,A-C 是 1/(3×4) = 1/12,行和约 0.261。
-
D̃^-1/2 Ã D̃^-1/2 X:A-A 是 1/3,A-B 是 1/√15 ≈ 0.258,A-C 是 1/√12 ≈ 0.289,行和约 0.880。
-
第 4 种里,度大的邻居 B(d̃ = 5)权重最小,度小的 C(d̃ = 4)次之:邻居越「热闹」,分到的权重越少。
怎么算
 := D̃^-1/2 à D̃^-1/2,Â[i][j] = Ã[i][j] / √(d̃_i × d̃_j)
意思是:Ã 里是 1 的格子(自己或邻居)才有权重,权重等于 1 除以两端度数乘积的平方根。矩阵对称,Â[i][j] = Â[j][i]。行和不一定正好是 1,课件图的五行约 0.880、1.164、1.012、0.880、1.012,都在 1 附近。
课件把四种写法总结为:sum(求和)、average by rows(按行平均)、averaged twice(平均两次)、modified average(修正平均),后两种打 ✓。下一页的 GCN 层用的是第 4 种。
常见误解
以为 D̃⁻¹ÃD̃⁻¹ 每行之和也是 1
不是。它左右各除一次度,A 行之和只有约 0.261。课件把它标成 Normalized,严格说它只是对称,没有归一到 1。
以为 Â 里的权重和特征内容有关
 只由图的连接和度决定,和 X 的数值无关。同一张图上,换一组特征  不变。
试一下
在课件图里,D 和 E 之间的 Â 权重是多少?(d̃_D = 3,d̃_E = 4)
1/√(3×4) = 1/√12 ≈ 0.289。
把它们串起来
GCN 的第一步是聚合:Ã 乘 X,每个节点把自己和邻居的特征加起来。直接相加让度大的节点数值偏大,所以要按度归一化。
最简单的归一化是 D̃⁻¹ÃX,每行除以中心节点的 d̃,得到平均值,但矩阵不对称。左右各乘 D̃⁻¹ 能对称,可是除了两次,权重太小。GCN 用的是折中:左右各乘 D̃^-1/2,i、j 之间的权重是 1/√(d̃_i d̃_j)。
这个矩阵记作 Â。下一页把 ÂX 再乘一个可学习的权重 W,过 ReLU,就是完整的一层 GCN。
课件里的坑
- [课件有误] p.18 的 D̃⁻¹ÃX A 行第三个数写 .52。1.6/3 = 0.533,四舍五入应为 .53,本页按 .53 算。
- [课件有误] p.18 说同一个邻居 B 对 A 的贡献是 1/2、对 C 是 1/3,这是用不含自环的度(A 是 2、C 是 3)算的。按同页的 D̃⁻¹ÃX,B 在 A 行占 1/3、在 C 行占 1/4。应改为 1/3 和 1/4,「贡献不同」的结论不变。
- [课件有误] p.19 把 D̃⁻¹ÃD̃⁻¹ 标为 Normalized and symmetric,应只标 symmetric。它对称,但每行之和约 0.26,没有归一到 1;GCN 原论文用的是 D̃^-1/2 à D̃^-1/2(p.20 第 4 种)。
- [术语] p.19 说 D̃⁻¹ÃD̃⁻¹ 是 Averaged in columns。更准确的理解是在按行平均的基础上,再按列(邻居的度)除一次,所以 p.20 称它 averaged twice。
课后 10 分钟:考点复习
这 10 分钟怎么用:先对着课件图算一遍 ÃX 和 D̃⁻¹ÃX 的 A 行;再写出四种归一化的 A 行权重和行和;最后说清楚为什么 GCN 选左右各乘 D̃^-1/2。
必背
- ÃX 的第 i 行 = 节点 i 自己和所有邻居的特征之和(消息传递)。
- 直接求和的问题:度大的节点加的项多,数值偏大,需要归一化。
- D̃⁻¹ÃX 按行平均:每行除以该节点的 d̃,D̃⁻¹Ã 每行之和为 1,但矩阵不对称。
- D̃⁻¹ÃD̃⁻¹X 左右各除一次度,对称,课件称为 averaged twice。
- D̃^-1/2 Ã D̃^-1/2 X 是 modified average,第 i 行第 j 列的权重是 1/√(d̃_i d̃_j)。
- Â := D̃^-1/2 Ã D̃^-1/2,是 GCN 层实际使用的归一化邻接矩阵。
课件例题
例 1(课件 p.16):ÃX 的 A 行
题面:用 p.15 的 Ã 和 X,算 ÃX 的 A 行。
提示
à 的 A 行在 A、B、C 三列是 1。
解答
A + B + C = [0.8+0.1-1.2, -0.6+0.2-1.6, 1.1+1.2-0.7] = [-0.3, -2.0, 1.6]。
例 2(课件 p.18):D̃⁻¹ÃX 的 A 行
题面:写出 D̃⁻¹,算 D̃⁻¹ÃX 的 A 行(Ã、D̃、X 见上图)。
提示
D̃⁻¹ 是对角线取倒数;A 行除以 d̃_A。
解答
D̃⁻¹ = diag(1/3, 1/5, 1/4, 1/3, 1/4)。A 行 = [-0.3, -2.0, 1.6] / 3 ≈ [-0.1, -0.667, 0.533](课件写 .52,应为 .53)。
例 3(课件 p.19):两种权重矩阵的 A 行
题面:写出 D̃⁻¹Ã 和 D̃⁻¹ÃD̃⁻¹ 的 A 行(矩阵见上图),判断哪个对称、哪个每行和为 1。
提示
D̃⁻¹ÃD̃⁻¹ 的第 i 行第 j 列是 Ã[i][j] / (d̃_i × d̃_j)。
解答
D̃⁻¹Ã 的 A 行:1/3, 1/3, 1/3, 0, 0,每行和为 1,但不对称。D̃⁻¹ÃD̃⁻¹ 的 A 行:1/9, 1/15, 1/12, 0, 0,对称,A 行之和约 0.261,不是 1。
例 4(课件 p.20):四种形式
题面:说出四种聚合写法的名字,哪几种打 ✓?
提示
sum、average by rows、averaged twice、modified average。
解答
ÃX 求和;D̃⁻¹ÃX 按行平均;D̃⁻¹ÃD̃⁻¹X 平均两次(✓);D̃^-1/2 à D̃^-1/2 X 修正平均(✓,GCN 用的就是这个)。
完整例题
自编情境。三个节点排成一条线 1-2-3,特征 x_1 = [2, 0],x_2 = [0, 4],x_3 = [6, 2]。(a) 求 ÃX。(b) 求 D̃⁻¹ÃX。(c) 写出 Â。
- Ã 是 1 1 0 / 1 1 1 / 0 1 1,d̃ = (2, 3, 2)。
- ÃX:第 1 行 = x_1 + x_2 = [2, 4];第 2 行 = x_1 + x_2 + x_3 = [8, 6];第 3 行 = x_2 + x_3 = [6, 6]。
- D̃⁻¹ÃX:第 1 行 [2, 4]/2 = [1, 2];第 2 行 [8, 6]/3 ≈ [2.667, 2];第 3 行 [6, 6]/2 = [3, 3]。
- Â:对角 1/2、1/3、1/2;1-2 和 2-3 是 1/√6 ≈ 0.408;1-3 是 0。
答案:ÃX = [2, 4] / [8, 6] / [6, 6];D̃⁻¹ÃX = [1, 2] / [2.667, 2] / [3, 3]; 如上。
要点:每一行先求和再除以 d̃;Â 的每格是 1/√(两端度数之积)。
答题格式:先写 Ã 和 d̃,再按行求和,最后写除法或 Â 的每一格。
变式题(先自己做)
(1) 改编自课件 p.18:算 D̃⁻¹ÃX 的 E 行(E 的邻居是 B、C、D)。 (2) 改编自课件 p.20:算  的 B 行(d̃_B = 5,B 和所有节点都相连)。 (3) 自编情境:为什么 GCN 不直接用 ÃX?
提示
(1) 先求 B + C + D + E,再除以 d̃_E。(2) 每格是 1/√(5 × d̃_j)。(3) 想想度大的节点。
判分点与答案(非官方评分标准)
判分点:① 求和包括节点自己;② 除数用含自环的 d̃;③ 说出「度大数值大」。
- (1) B + C + D + E = [2.8, -1.5, -0.6],除以 4 得 [0.7, -0.375, -0.15]。
- (2) B 行 = [1/√15, 1/5, 1/√20, 1/√15, 1/√20] ≈ [0.258, 0.2, 0.224, 0.258, 0.224]。
- (3) ÃX 是直接求和,度大的节点加的项多,数值偏大,不同节点没法比,训练也不稳定,所以要归一化。
闪卡自测
1. ÃX 的第 i 行是什么?
节点 i 自己和所有邻居的特征之和(p.16)。
2. 课件说直接求和有什么问题?
度大的节点数值更大,需要归一化(p.16)。
3. 例子图的 D̃⁻¹?
diag(1/3, 1/5, 1/4, 1/3, 1/4)(p.18)。
4. D̃⁻¹ÃX 的 A 行?
约 [-0.1, -0.667, 0.533](p.18)。
5. D̃⁻¹Ã 有什么性质?
每行和为 1,不对称,按行平均(p.19)。
6. D̃⁻¹ÃD̃⁻¹ 有什么性质?
对称,左右各除一次度,课件称 averaged twice(p.19–20)。
7. Â 的定义和每格的值?
 := D̃^-1/2 à D̃^-1/2,第 i 行第 j 列是 Ã[i][j] / √(d̃_i d̃_j)(p.20–21)。
8. 四种写法哪两种打 ✓?
D̃⁻¹ÃD̃⁻¹X 和 D̃^-1/2 à D̃^-1/2 X(p.20)。
下一讲
下一页 L08c 在 ÂX 后面乘上可学习的权重 W 再过 ReLU,用一张三节点小图把一层 GCN 从头到尾手算一遍,再讲两层 GCN 怎么做节点分类。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。