← COMP5541 全部讲次
L08b · 第 10 周

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 的对称归一化就是同时考虑「我有几个好友」和「这个好友有几个好友」。

类比在哪里失效:

  1. 成绩是一个数,节点特征是一串数,每一列分别做同样的加和除。
  2. 真实小组里每个好友的影响可能不同。这一页的几种做法里,权重只由度决定,和特征内容无关;按内容定权重是 attention 的思路,见 L07d。

从零讲起

1. 消息传递:ÃX 把邻居特征加起来

它解决什么问题

节点分类时,一个节点自己的特征往往不够,它的邻居也提供线索:好友都支持某位候选人,这个人大概率也支持。要一种运算,让每个节点同时拿到自己和所有邻居的信息,而且所有节点一次算完。

直觉

à 的第 i 行在「自己和邻居」的位置上是 1,其余是 0。拿这一行去乘 X,相当于把 1 所在的那几行特征挑出来加在一起。

所有行同时这样做,就是矩阵乘法 ÃX。

一步一步看

目标:用五节点图算 ÃX 的每一行,看各节点加的项数从 3 到 5 不等,度大的节点数值也更大。

用课件的五节点图,算 ÃX 的 A 行。

  1. Ã 的 A 行是 1 1 1 0 0:A 自己、B、C 三个位置是 1。

  2. 从 X 里挑出 A、B、C 三行特征,按列相加,得到 [-0.3, -2.0, 1.6]。

    左边 Ã 的 A 行 1 1 1 0 0,前三格描成青绿;中间取出 A、B、C 三行特征,横线下是相加结果 -0.3、-2.0、1.6,描成青绿;右边列出三个分量的加法

  3. 其余四行同理。B 的邻居最多,B 行要加 5 项。

  4. 把五行和每行加的项数并排放,看出项数从 3 到 5 不等。

    左边 ÃX 五行:A -0.3 -2.0 1.6,B 3.6 -2.1 0.5,C 1.8 -2.2 2.6,D 4.0 0.1 0.1,E 2.8 -1.5 -0.6;右边一列每行加的项数 3、5、4、3、4,B 行描成青绿

  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,同一个邻居在不同行里分到的份额不同。

  1. D̃ = diag(3, 5, 4, 3, 4),取倒数得 D̃⁻¹ = diag(1/3, 1/5, 1/4, 1/3, 1/4)。

  2. ÃX 的 A 行 [-0.3, -2.0, 1.6] 除以 3,得到约 [-0.1, -0.667, 0.533]。

    ÃX 的 A 行 -0.3、-2.0、1.6 除以 3,得到 D̃⁻¹ÃX 的 A 行 -0.1、-0.667、0.533,结果描成青绿;下方写出三个除法

  3. B 行除以 5:[3.6, -2.1, 0.5] 变成 [0.72, -0.42, 0.1]。其余行依此类推。

  4. 换个角度看权重矩阵 D̃⁻¹Ã:A 行是 1/3、1/3、1/3、0、0,每行加起来都是 1。

    5×5 矩阵 D̃⁻¹Ã:A 行 1/3 1/3 1/3 0 0;B 行全是 1/5;C 行 1/4 1/4 1/4 0 1/4;D 行 0 1/3 0 1/3 1/3;E 行 0 1/4 1/4 1/4 1/4。A 行 B 列的 1/3 和 C 行 B 列的 1/4 描成青绿

  5. 同一个邻居 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 来归一化,摘要说方法来自谱图卷积的局部一阶近似。课件后面定义的 Â 就是这个矩阵。

出处:arXiv 1609.02907

直觉

左乘 D̃⁻¹ 是每行除以中心节点的度,右乘 D̃⁻¹ 是每列除以邻居的度。左右都乘 D̃⁻¹ 就除了两次,权重变得太小。

折中办法是左右各乘 D̃^-1/2:每行除以 √(中心度),每列除以 √(邻居度)。合起来,i 和 j 之间的权重是 1/√(d̃_i × d̃_j)。

一步一步看

目标:用 A 行比较四种写法给 A、B、C 的权重,看对称归一化怎样让度越大的邻居分到越少。

还看课件图的 A 行,比较四种写法给 A、B、C 的权重。

  1. ÃX 求和:权重 1、1、1,行和 3。

  2. D̃⁻¹ÃX 按行平均:权重都是 1/3,行和 1。

  3. 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。

  4. 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。

    表格四行:ÃX 求和,A 行权重 1、1、1,行和 3;D̃⁻¹ÃX,1/3 三个,行和 1;D̃⁻¹ÃD̃⁻¹X,1/9、1/15、1/12,行和 0.261;D̃^-1/2 à D̃^-1/2 X,0.333、0.258、0.289,行和 0.880,最后一行描成青绿

  5. 第 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。

必背

  1. ÃX 的第 i 行 = 节点 i 自己和所有邻居的特征之和(消息传递)。
  2. 直接求和的问题:度大的节点加的项多,数值偏大,需要归一化。
  3. D̃⁻¹ÃX 按行平均:每行除以该节点的 d̃,D̃⁻¹Ã 每行之和为 1,但矩阵不对称。
  4. D̃⁻¹ÃD̃⁻¹X 左右各除一次度,对称,课件称为 averaged twice。
  5. D̃^-1/2 Ã D̃^-1/2 X 是 modified average,第 i 行第 j 列的权重是 1/√(d̃_i d̃_j)。
  6. Â := D̃^-1/2 Ã D̃^-1/2,是 GCN 层实际使用的归一化邻接矩阵。

课件例题

例 1(课件 p.16):ÃX 的 A 行

题面:用 p.15 的 Ã 和 X,算 ÃX 的 A 行。

左边是 5 节点图,边为 A-B、A-C、B-C、B-D、B-E、C-E、D-E,节点特征 A [0.8, −0.6, 1.1]、B [0.1, 0.2, 1.2]、C [−1.2, −1.6, −0.7]、D [1.8, 0.1, −2.1]、E [2.1, −0.2, 1.0]。右边依次是邻接矩阵 A 与加自环后的 Ã(对角线改为 1),度矩阵 D = diag(2, 4, 3, 2, 3) 与 D̃ = diag(3, 5, 4, 3, 4),以及按 A 到 E 排行的特征矩阵 X。
图片来源:COMP5541 L08_Graph Neural Networks.pptx, p.15
提示

à 的 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 1 0 / 1 1 1 / 0 1 1,d̃ = (2, 3, 2)。
  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]。
  3. D̃⁻¹ÃX:第 1 行 [2, 4]/2 = [1, 2];第 2 行 [8, 6]/3 ≈ [2.667, 2];第 3 行 [6, 6]/2 = [3, 3]。
  4. Â:对角 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. (1) B + C + D + E = [2.8, -1.5, -0.6],除以 4 得 [0.7, -0.375, -0.15]。
  2. (2) B 行 = [1/√15, 1/5, 1/√20, 1/√15, 1/√20] ≈ [0.258, 0.2, 0.224, 0.258, 0.224]。
  3. (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 怎么做节点分类。

下一讲 →
L08c L08c 一层 GCN 逐步手算,再叠成两层做节点分类

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。