社交网站猜你可能认识谁,购物网站猜你可能喜欢什么,背后常有同一个直觉。物以类聚,朋友喜欢的东西,你多半也喜欢。
图卷积网络(Graph Convolutional Network,GCN)就是把这个直觉写成数学。
这篇从零开始,不需要图论背景,会加减乘除就够了,矩阵乘法用到时再解释。读完之后,你会亲手算完一层 GCN,也会看着一个小模型只靠两个已知答案,猜出其他人的答案。文中有三个可以动手玩的交互图,点一点、拉一拉,会比只读公式快很多。
先看一个问题
有六个人。Alice、Bob、Carol 彼此是朋友,Dave、Eve、Frank 也是;Carol 和 Dave 也认识,是两群人之间唯一的连接。
我们只知道两件事。Alice 喜欢打球,Frank 不喜欢。
其他四个人呢?
你大概会这样猜。Bob 的朋友是 Alice 和 Carol,Alice 喜欢打球,所以 Bob 可能也喜欢;Eve 的朋友是 Dave 和 Frank,Frank 不喜欢,Eve 大概也不太喜欢。
「看朋友来猜」,就是图卷积的出发点。接下来一步一步,把这个猜法变成电脑算得出来的东西。
图:点和线
先厘清一个名词。这里的「图」是英文的 graph,不是图片。它只有两种东西:
- 节点(node):要描述的对象,这里是六个人。
- 边(edge):对象之间的关系,这里是朋友关系。
每个节点还可以带一些数字来描述自己,叫做特征(feature)。这里每个人只有一个特征,就是「喜欢打球的程度」。Alice 是 1,Frank 是 0;其他四个人不知道,先都填 0.5,表示一半一半。
电脑看不到线,要把朋友关系写成一张表,叫做邻接矩阵(adjacency matrix)。
六个人就是 6×6 的表,写成 。第 行、第 列的 ,表示第 个人和第 个人是朋友;不是朋友就填 0。
看 Carol 那一行,Alice、Bob、Dave 三格是 1,她有三个朋友。一行里有几个 1,就是这个人的朋友数,叫做度数(degree)。
朋友是互相的,所以 ,整张表沿着对角线左右对称。
最直觉的做法:问问朋友
最简单的猜法,是把每个人的数字换成朋友们的平均。
Bob 的朋友是 Alice(1)和 Carol(0.5),平均是 0.75,他大概喜欢打球。Eve 的朋友是 Dave(0.5)和 Frank(0),平均是 0.25,她大概不喜欢。
用矩阵可以一次替所有人算。先把邻接矩阵的每一行除以那个人的朋友数,每个朋友就各占一份;再乘上每个人喜欢打球的程度(Alice 是 1、Frank 是 0,其他人不知道,先填 0.5)。结果的第 个数字,是把第 行的每一份和对应的数字相乘再加起来,也就是第 个人所有朋友的平均,六个人依次是 0.5、0.75、0.67、0.33、0.25、0.5。
Bob 是 0.75,Eve 是 0.25,和我们的直觉一样。可是看看 Alice 和 Frank。
他们两个原本是唯一知道答案的人,算完却都变成 0.5。只问朋友,就把自己知道的事丢掉了。
两个修补
自己也算一票
修法很直接,算平均的时候把自己也算进去。在邻接矩阵的对角线上补 1,等于让每个人多一个「自己」当朋友,这叫自环(self-loop),写成 。 是对角线为 1、其他为 0 的单位矩阵。
这样 Alice 的新数字是 ,她自己的答案保住了大半。
朋友多的人,每一票轻一点
直接取平均时,每个朋友的份量都一样。GCN 多做了一步,依两个人各自的朋友数调整份量。第 个人从第 个人拿到的份量是:
是加上自环后的度数,也就是朋友数再加 1。
拿 Bob 来看。Bob 的 是 3。他从 Alice()拿 ,从 Carol()拿 。Carol 认识的人比较多,她的声音分给更多人,传到 Bob 这里就轻一点。
这个份量也是对称的,Bob 从 Carol 拿多少,Carol 就从 Bob 拿多少。写成矩阵,就是 GCN 论文里的 ,左右各除一次度数的平方根。加上自环之后,六个人的度数依次是 3、3、4、4、3、3;用 重新算一次,新的数字是 0.64、0.64、0.68、0.39、0.31、0.31。
左边三个人都超过 0.5,右边三个人都低于 0.5,Alice 也还是倾向喜欢打球。份量加起来不一定刚好是 1,Carol 那一行就是 1.08,但很接近。
为什么不直接取平均就好?两种做法都有人用。GCN 选这个对称的版本,一个原因是它从频域的推导一路简化而来,另一个是叠很多层时数值比较稳,不会越乘越大。
下面这个交互图可以点任何一个人,看他从谁那里拿了多少。三种算法切换看看,特别注意 Alice 在「只问朋友」时发生了什么事。
Bob 的新数字GCN 的权重
- Alice1.00 × 0.330.33
- 自己0.50 × 0.330.17
- Carol0.50 × 0.290.14
加起来0.64
这就是一层 GCN
把刚才做的事写成一行,就是 GCN 论文里的公式:
三个部分各做一件事:
- :每个人和朋友、自己,照刚才的份量取加权平均。 是所有人的特征,一个人一行;第一层的 就是原始特征,写成 。
- 乘上 :每个人的特征常常不只一个。 把这些特征重新组合,换一组说法,每个新特征都是旧特征的加权和。 是模型要学的参数,所有人共用同一个 。
- :一个非线性函数,GCN 用的是 ReLU,负的变成 0,正的保持原样。
让每个人多一个特征「喜欢看书的程度」,Alice 是 0、Frank 是 1,其他人还是 0.5。 先由我们指定,让第一个新特征是「打球减看书」,第二个是「看书减打球」。经过一层 GCN,Alice、Bob、Carol 的新特征是 [0.33, 0]、[0.33, 0]、[0.29, 0],Dave、Eve、Frank 是 [0, 0.29]、[0, 0.33]、[0, 0.33]。
左边三个人的第一个新特征是正的,右边三个人的第二个新特征是正的。一层 GCN 之后,两群人已经用不同的特征分开了。
实际训练时, 不是我们指定的,而是从数据学出来的。这一点等一下再看。
为什么叫「卷积」
如果你学过处理图像的卷积神经网络(CNN),应该会觉得刚才的做法有点眼熟。
图像的卷积,是让每个像素的新值等于自己和周围 8 个像素的加权和,再让同一组权重滑过整张图像。图卷积也是让每个节点的新值等于自己和邻居的加权和,所有节点共用同一个 。两者做的是同一类事,所以叫图「卷积」。
差别在邻居。像素的邻居固定是 8 个,左上、正上、右上各有固定的位置,每个位置有自己的权重;图上的邻居数量不固定,也没有上下左右,GCN 只好让份量只由度数决定。这个差别埋下了不少后来的研究,〈图卷积大观园〉的第一站就从这里开始。
叠两层,看得更远
一层 GCN 只让每个人听到朋友的声音。把第一层的结果再送进第二层,朋友的朋友也听得到了。
以 Alice 为例,她的信息一层之后传到 Bob 和 Carol,两层之后越过桥传到 Dave,三层之后才到 Eve 和 Frank。叠 层,就看得到 步以内的人。
拖动下面的滑杆试试看。
一开始,只有 Alice 和 Frank 有答案。
Alice 的信息传到的人数0 / 5
虚线圈起来的,就是已经传到的人。
一开始最高和最低差了 1.00;叠一层,两群人已经分开,差距是 0.37;叠到 8 层只剩 0.18。叠越多层,大家的数字越来越接近,最后两群人会分不出来,这叫 over-smoothing。GCN 论文的主要实验只用两层;附录试过更深的版本,最好的结果都落在两到三层。
让模型自己学
到目前为止,数字和 都是我们给的。真正的 GCN 要自己学。
我们把题目弄得更纯粹一点。模型完全不知道谁喜不喜欢打球,每个人的特征只有「我是谁」;唯一的线索是朋友关系,以及两个答案,Alice 喜欢打球、Frank 不喜欢。
模型先用 在图上平滑两次,再接一个线性分类器,用 softmax 把两个类别的分数换成加起来是 1 的概率,输出每个人喜欢打球的概率。训练时只拿 Alice 和 Frank 的答案来算误差,用梯度下降一步一步调整分类器的权重。用图的时候,Bob、Carol 被猜成喜欢打球(0.98、0.92),Dave、Eve 被猜成不喜欢(0.08、0.02),四个人都对。不用图的时候,模型对这四个人一无所知,只能停在 0.5。
答案只有两个,其他的都是从朋友关系推出来的。这就是 GCN 最常见的用法,半监督节点分类。GCN 论文在 Cora 论文引用网络上做的就是这件事,2,708 篇论文里只给 140 篇的类别,两层 GCN 猜对其他论文类别的准确率是 81.5%。
下面可以一步一步看训练的过程,也可以切换「不用图」比较。
没给答案的 4 个人,猜对 0 个。
和 Transformer 差在哪
如果你熟悉 Transformer,可能觉得「每个人取别人的加权平均」很像注意力机制。确实很像,差别在两件事。
第一,谁拿得到份量。GCN 只在朋友之间分配,图上没有连接的两个人,份量是 0;Transformer 的注意力让每个人都看每个人。
第二,份量怎么来。GCN 的份量只由度数决定,事先就算好了;注意力的份量是看两个人的特征有多相近,每次输入都重新算。
这两条路后来慢慢汇在一起。有人让 GCN 也依特征分配份量,有人让 Transformer 也看得到图的结构。
最后整理一下
- 图由节点和边组成,邻接矩阵记下谁和谁相连。
- 一层 GCN 让每个人和朋友、自己取加权平均,份量由两边的度数决定,再乘上 、过 ReLU。
- 叠 层看得到 步以内的人;叠太多层,大家会变得一样。
- 只要少数答案,靠着朋友关系,GCN 就能猜出其他人。
如果你想知道后来的人怎么改进这一行公式,可以接着读〈图卷积大观园〉。那篇从头到尾用的,正是这六个人的朋友关系,只是名字缩成了 A 到 F。
之后在论文里看到 ,记得它就是 Bob 从 Carol 那里拿走 0.29 的那条算式。
