【斯坦福cs224w-图机器学习】8-Graph Neural Networks

GNN

发布日期: 2020-11-26

复习Node Embeddings

目的

将图中的节点映射到d-维度嵌入空间，使得图中的相似的节点在d-维度嵌入空间中紧密地相邻。即要使得$similarity(u,v) \approx z_u^{T}z_v$。

这里的“相似的节点”并不是指在原空间相邻，相似（similarity）的定义有很多种，除了相邻，如果两个节点在图中承担了相同的structure role，它们也可以称作是相似的。

完成Node Embedding需要定义两个东西：

实现

从Node Embedding的目的的定义中，我们可以抽取出实现Node Embedding的两个重要组件：

Encoder函数
input network上节点similarity的度量方式

这里的dot product$z_v^Tz_u$其实最后计算的是余弦距离，余弦距离是一种常见的相似度度量方式。

实现方式一：Shallow Node Embedding

我们之前所提到的DeepWalk也好，node2vec也好，都属于浅层的encoders。它们的作用类似是建立了一张Hash Table，如下图：

这些内容第七课实际上都已经介绍过了，所以就不赘述了。

局限性——即为什么要引入Graph Neural Network？👏

那么浅层的encoders有哪些缺陷呢？

太多参数：v个节点就有v个embedding，并且nodes之间不共享参数，每一个node都有其独立的embedding，那么如果embedding的维度是100，有100万个节点，我们就要训练1亿个参数。
固有的局限性：无法为训练期间未见的节点生成embedding，这就好比word2vec对于未见过的词无法进行embedding一样；woe对于没见过的类别无法编码一样；除此之外，当我们在一个网络上训练得到了各个节点的embedding，然后比如时间长了，网络里又增加了很多新的节点和边，那么我们又得重新训练一次，
压根没用上node的feature啊：我们在cs224w第七课中，DeepWalk和node2vec压根没有用到每一个节点的属性特征，它们只是使用了图结构信息，比如某个user的节点，会有age、gender之类的特征，我们在embedding的时候也应该将这些考虑尽量，因为如果两个节点的属性完全相同很可能也代表了这两个节点非常接近，所以他们在embedding的空间里按理说也应该接近。

除了要解决上面的这些问题之外，还有一个问题：

Spectral Clustering可以看作是一种Embedding，它是人工数学推导计算出来的用于聚类的Embedding。（其数学推导是为了近似最大化conductance！）

那如果我们想，如果我要进行一个链路预测问题的话，难道我又要另外自己去公式推导找Embedding？如果我要进行一个分类问题的话，我又要找另外一个Embedding？难道我们就不能训练一个模型，这个模型能够根据任务的特征，自动得到Embedding？

那么这里就是GNN大展身手的时候了！

实现方式二：Deep Node Embedding

Shallow Node Embedding vs. Deep Node Embedding

所有的deep encoders都可以和上一节课我们介绍的node similarity functions结合起来，即：

Adjacency-based（即如果两个节点连通，那么它们相似）
Multi-hop similarity definitions
Random walk approaches

上一节课我们这里的$ENC(V)$如下：

这个地方其实我一直在概念上比较困惑，因为总是不自觉地联想到DNN和CNN，在普通的深度学习的领域里，DNN是普通的全连接层，CNN则是带有卷积层和池化层的特殊结构，二者应该是两种不同的结构所以总是误以为有一种GNN的图网络结构和一种GCN的图网络结构。。。实际上这里的GNN指代的是nn的概念，即CNN属于nn的一种，GCN属于GNN的一种。另一方面，GCN有广义和狭义之分：

这节课谈到的GCN属于狭义的GCN，也就是上图最右边的那个。这也是2017年的论文《semi-supervised classification with GCN》里所谈到的结构，是目前我们经常谈论到的那种GCN。

已有机器学习的局限性——研究GNN的原因

这些实际上都是综述里的内容，这里引出了为什么我们使用常规的NN结构无法处理图数据：

图中的节点没有固定的顺序或参考系，而我们使用CNN或RNN所面对的数据都是fixed size，固定大小的，每一张图片的大小都处理成完全一样的，每一个序列都会通过补零然后mask从而达到同样size的效果；
网络常常是动态的并且具有多模态特征；

从计算机视觉到图神经网络

我们希望能够将CNN中卷积的思想推广到网格结构之外，同时充分利用节点原有的属性（例如文本或图像）。

你甚至可以认为结点不同的feature作为convolution操作里面不同的channel。

（这里建议看下gnn的综述，里面详细介绍了图像和文本都属于图数据结构的一种）

将图像转变为图结构进行思考：

上图左边为一个简单的3X3的卷积核，其计算的本质就是对$W_i*h_i$进行求和。比如原图中的9个像素点$h_i$代表了9个输入，每个输入对应一个$W_i$，即连接权，然后进行加权求和再进入activation function。

我们前面提到过图像属于图数据的一种，因此这里也可以从图数据的角度来描述，如右图，因为$CNN$传播的时候所有节点都参与了加权求和，对应到图上就是中心节点再加一个自循环进来，这样实际上右图也一样可以表示为加权求和的形式。这样我们就把$CNN$的输入转化为用图来描述。

但是，需要辨别的是：在CNN中，聚合的单位是特征；而在GNN中，聚合的单位是节点。特征和节点的粒度大小是不一样的！所以我认为只能说GNN是利用了CNN这种聚合的思想，而不是完全照搬CNN的模型~🤔

这样我们就可以用常规$CNN$处理这种规整的图数据了，然而：

现实中的网络复杂的多，比如上面这样形式的图，就没办法用CNN来处理的。。。

这种结构别说CNN，目前我们常见的模型都无法接受这种形式的数据作为输入，

所以我们该怎么做才能像在图像上使用卷积层来slide（卷积层按照步长滑动）那样在graph的数据上slide呢?

一种简单的方法——没看懂

一个简单的思路，我们把图转化为其领接矩阵的形式，然后这个邻接矩阵和node的属性组成的特征矩阵合并（concat）在一起，如上图，这样就转化为一个规整的二维矩阵了，这样我们就可以用一个普通的nn结构或lr、gbdt之类的算法来处理了；

然而这种做法的坏处也很明显：

如果node的数量非常多，那么最终的合并矩阵的维度会非常大，高维稀疏的情况下非常容易过拟合；
这种情况下训练出来的模型对于不同size的网络用不了。比如我们原来是100个node，扩展成100维加上原来计入50维的node feature一共150维，然后我们训练一个nn，这个nn只能接受150维的输入，然后新的网络有500个node，concat之后是550维，这样我们就面临了输入数据的异构问题了；
显然破坏了图的结构信息，比如A和E是二度关联的，但是转换成领结矩阵之后我们无法直接观察到这种关联；
这里提到了第四点，就是比如我们保持原始的图结构不变，然后变换了node的位置，但是领域信息是完全不变的（建议自己把node换一下然后看看每个节点的领域关系是否改变就知道了）但是其领接矩阵确发生了变化，显然我们希望这种变化对于模型来说没有影响。

GCN

GNN的兴起，是以GCN模型的提出为标志的，所以我们学习GCN能够让我们了解一些GNN的入门知识。

Preliminaries

我们给定一个图结构：

$V$是节点的集合；
$A$是图的邻接矩阵；
$X$是节点的属性矩阵组成的特征矩阵（维度有点意思~）

不同网络有不同的node features，比如：

社交网络：用户信息与用户画像等；
生物网络：基因表达谱、基因功能信息
数字特征：指示向量（节点的独热编码）

GCN的idea⭐⭐⭐⭐⭐

GNN的思想：Generate Embedding by Aggregating Neighbors‘ Embedding Through Computation Graph

顾名思义，我们需要解决两个问题：

how to capture computation graph？
how to aggregate information？

很多基于GCN的优化也是从这两个方面出发的。

Computation Graph

上图中的橙色部分就是经过对节点$i$的邻域采样后的得到的Computation Graph。

这里我们希望学习如何通过图的结构来传播信息（Message Passing）从而更好地计算节点的embedding，说白了就是不仅像node2vec那些算法那样考虑节点和节点之间的关联关系还要考虑节点的属性（特征）。

上图的k=1表示一度关联，k=2表示二度关联。比如node $i$，我们后面介绍的方法不仅能够捕获到node $i$ 所在图的结构信息，还能够捕获node $i$ 的邻节点的属性信息从而增强embedding的表达能力。

通常来说这个聚合邻居的操作（也就是这个彩色的层数，如上图中有两层）是不需要叠很多层的，因为著名的6度理论告诉我们，走了6层邻居差不多就可以遍历到图中的每一个节点了。但是黑色盒子里面的DNN是可以叠很多层的！

这里就看的非常明白了，例如我们要计算$A$的embedding，我们希望能够collect来自$B$、$C$、$D$的信息，而$B$、$C$、$D$又分别collect来自其各自的领域的信息，这里可能有点懵逼，那么所有Nodes最原始的属性（即之前提到的user profiles，images之类的属性）到底是在哪里参与了这个网络结构，答案就是

here，这里是layer-0，第0层，这里的输入都是节点的属性。这样我们就巧妙的把node A的邻节点的属性考虑进来了，同时node A所在的网络的结构也一并考虑进来了，因为不同的结构会使得最终embedding的结果不同，通过这种方式捕获的结构的信息。

（这里学生问了一个我也想问的问题，如果说整个网络非常复杂，A的邻居节点B存在邻节点C，而邻节点C存在一个更远的邻节点D，邻节点D存在一个更更远的邻节点E，那么我们是不是也要统一考虑进来，这里教授的答案是“no need”。。。。额。。。）

到这里还有一个问题，这些黑色的box到底是什么东西？

关于box，我们目前只知道有一点性质，它需要满足，就是这个box中的函数对于输入节点的顺序是完全不敏感的，比如第一个灰色box的输入是$A$和$C$节点，我们替换$A$和$C$的顺序之后，经过这个box function之后的结果应该是不变的。这个function应该是order invariant function（目的是为了解决上面讲的对顺序敏感的问题），具体后面会描述清楚的。

那么通过刚才的思路，我们为每一个节点都进行了上面所说的展开的方法进行展开得到了上图。可以发现，每个结点拥有不同的Computation Graph。

怎样初始化，以及怎样计算：

这里整个Deep Graph Encoder的结构就出来了，我们的输入是target node的二阶邻居节点，输出是target node的embedding。

需要注意，以节点$C$为例，layer-0节点$C$是$C$的原有的features，比如$C$是一个用户，那么就可能是用户的age、gender、nationality等，但是除了layer-0之外，其它的layer里，$C$都是该层对应的embedding。这是一个很奇怪很有意思的地方。

其实这里涉及到了两种思维方式——Top to Down 和 Down to Top（有点类似于递归的思想）：

Top to Down：是我们得到计算图的过程，类似于递归函数不断递归深入的过程。给定节点$u$，如果我们要聚合它的二阶以内邻居的信息，我们首先得到它的一阶邻居，然后通过一阶邻居的一阶邻居得到它的二阶邻居。过程类似于从左到右看上面的网络图。
Down to Top：是我们聚合邻居信息的过程，类似于递归函数不断返回的过程。同样是上面那个例子，首先是二阶邻居将自己的信息聚合到对应的一阶邻居，然后一阶邻居再聚合到节点$u$。过程类似于从右到左看上面的网络图。这是我们的网络计算的顺序。

可以思考，以上两个过程的确能够确保节点$u$能够聚合到二阶邻居以内的所有信息。

上图是一个二层的结构（这里的层数是box代表了层，并不是指Deep Neural Network里面的层数），这意味着我们取的是node $A$的2 hops away的邻节点，这里又提到了为什么我们不继续”go deep“的问题，如果我们考虑太远的节点，会把太多的结构信息考虑进来，举一个极端的例子，比如我们go 20 steps deeper，可能会把整个网络结构的信息考虑进来。

（这里是我自己的思考，我们以word2vec为例，假设一个句子有10个单词，而我们的windows是10，这就意味着在这个句子中，每个单词的embedding表示最终都是由这个句子中所有的单词一同参与训练的，这会导致最终这个句子中所有的单词训练出来的embedding接近一致，这显然不是我们想要的结果。）

但是这并不意味着你不能做很深的Deep Neural Network！我们完全可以让$box$里面的DNN非常深~

另外，假设我们图中的F直接又接入了一个G，这个G仅仅和F连接而不和其它所有的已知节点有连接，那么我们就要在F的屁股后面接入一个box，这个box的输入是F的邻节点E、C、G。

btw，问了一下，之所以我们不go太过deeper，一方面引入太多的领域信息：

90%的nodes会在8hops之内访问到，因此这意味着hops取得太大，会导致最终每个节点的embedding的计算过程中，输入的features几乎差不多，从而最终导致over-smooth的问题，即每个节点最终计算出来的embedding接近一致。

这类似于我们使用word2vec对一篇文章中的每个词进行向量化，windows取得太大使得整篇文章的词语都参与了每一个词的embedding训练——换句还说，每个词都在每个词的附近。。。最终结算的结果当然是所有的embedding都差不多了。。。

Aggregation Function

现在一个重要的地方在于我们如何汇总各层的信息？做基本的思路如下：

最简单的思路，我们把所有来自于邻域的信息进行平均然后输入一个$NN$结构即可；注意，所有的box都是这样的，箭头的地方先进行average，然后送到一个$NN$的结构里。也就是box前面的箭头是average，box里面是一个$NN$。

把整个过程用公式来表示就是：

这个过程用公式来表示如上图，这就是狭义的GCN的整个前向传播的过程了。这里，如果$W_k$全是0，则意味着我们根本不考虑邻节点的信息，这个时候这个GCN的结构就退化成了普通的MLP（DNN）。如果$W_k$非常非常大，$B_k$相对非常非常小，则相当于我们只考虑了邻节点信息而忽略了自身的信息。具体应该怎么去分$W_k$和$B_k$的大小，是由整个模型训练的过程中自己决定的。

Training the Model

这里我们定义完了前向传播的过程，还缺一个损失函数。

这里，我们把上面的公式表达成矩阵的形式，如上图，其中$H(l+1)$表示所有node的在$l+1$层的embedding表示，$H(l)$同理，$A$表示graph的领接矩阵，$D$表示graph的度矩阵，关于graph常用的矩阵的含义可见：GNN之常用矩阵汇总
这里的$W_k$和$B_k$可以用于衡量邻居和自己的作用的大小。

无监督方式

损失函数可以使用random walks定义的损失函数也可以用graph factorization或者node proximity的损失函数。比如第七课用过的：

这样损失函数也确定下来惹~，我们就在自动微分的框架下快乐的等待整个网络训练到收敛为止。

有监督方式

除此之外，我们可以直接在最终的输出上接一个分类层，然后使用分类的损失函数比如交叉熵作为最终的损失函数。

这里公式写的非常明了了。

总结

下面进行了一个完整的总结：

我们定义一个neighborhood aggregation function，狭义的GCN使用的就是简单平均的策略；
我们定义一个funtion用于指导GCN进行反向传播更新权重参数W和B；

一个节点对应一个模型输入的样本，我们在这些样本上进行训练；

假设我们的训练集是node $A$、node $B$和node $C$，那么我们直接可以把训练完的model用于预测未见过的node $B$、$E$、$F$，这里就比较重要了，首先我们训练完毕的模型是什么样子的？

实际上我们训练完毕的model就是**两个box**：

一个是浅灰色的box，一个是深灰色的box，这两个box都是$NN$的结构，具体是什么结构可以自己用普通的神经网络的方法来定义。另一个重要的地方在于，可以看到深灰色的box有3个，实际上只有一个，这3个浅灰色box进行了权值共享，是不是和CNN里的卷积核非常相似？实际上CNN里的卷积核的传播形式展开之后也可以表示成上面的形式的。

所以，对于new node，我们可以很轻易的使用已经训练完的两个box来进行预测得到最终的结果。

见下：

inductive capability

归纳能力

我们最终share的权重如上图，这里就是体现$GNN$权值共享的地方。可以看到，相对于node2vec和deepwalk这种算法，deep graph encoders可以对unseen的node进行embedding，而node2vec和deepwalk无法实现这样的功能，并且deep graph encoders还考虑了node的features，使得最终的embedding结果更加expressive。

不仅如此，即使是新的graph结果，我们也可以直接apply原来的model了！简直太牛逼了！！

上面的例子很赞👍

还有一个非常有用的地方就是，你可以只训练一个子图，就可以获取这个全局的信息。但是这个采样子图一定要保证良好的随机性！！！

需要区别聚合信息的depth和深度学习的depth。你完全可以让你的黑盒子非常的deep，因为一个黑盒子就是一个deep neural network，这个可以联想的~

这样我们就从graph embedding过渡到了GCN，这也是我认为最好理解的方式了，后面补充一下graphsage的内容，关于gat，我得去复习下attention的内容，后面佛系更新了。

这里实际上我们就实现了在graph上slide，这两个box就是我们的“卷积核”，我们取2 hops away的节点进行展开，就类比于固定了“卷积核”的size，比如我们从D开始slide，“卷积核”的size（这里的卷积核取双引号因为是类比的关系，不是真正指cnn里的卷积核的概念），取其2hops away的节点展开成一个computation graph，得到了上面第四个图，然后我们slide到节点A，取其2hops away的邻节点，展开成一个computation graph图，得到上面第一个图。。。。。依次类推，可以看到，实际上类似于我们把每一个node当作cnn中卷积核的中心的像素点~。

GraphSAGE

GraphSAGE的提出原因

从GCN过渡到GraphSAGE的过程是非常自然，二者的不同之处仅仅是box处做了一些修改：

这里提到了weighted average，实际上指的就是当图为带权图的时候，我们进行average之前，每个节对应的要乘上edge的权重再平均，这实际上也是很好理解的，比如我认识很多大佬，但是大佬们都不认识我，所以他们收入高跟我可能没什么关系，我们之间的edge的权重可能是0.001。。。

比较一下：

主要有两个不同：

邻域信息和自身信息的结合从代数运算变成了concatenate（这样能够让节点自身的信息与邻域的信息区分开来）；
不使用简单的mean函数作为聚合函数，而是使用Generalized的聚合函数。这里，我们从广义的角度上来定义聚合函数，即我们在GCN中使用的是简单的邻居的聚合，而在GraphSAGE中，这个聚合函数的形式更加多样：