李沐老师讲解GCN视频：https://www.bilibili.com/video/BV1iT4y1d7zP?from=search&seid=17425771631747736862&spm_id_from=333.337.0.0

该博客原地址（有些可以点击演示的交互图）：https://distill.pub/2021/gnn-intro/

一、简介

这个图中一共有四层，每个节点是由下一层中该节点本身和该节点的邻居计算而来的

图越深，在顶部的层的节点，包含的邻居的信息越广（包含邻居的邻居...）

博客提供了一个GNN playground【应该就是这些交互的可操作性的图】

该博客中，V表示节点属性，E表示边（或链接）属性，U代表全局（或主节点）属性【U代表整个图】

比如节点的属性表示为长为6的向量，柱形的高矮表示每一维数值大小

二、怎么表示成图

1、把一个图片表示成图

假设有一张图（244*244*3），高宽都是244，有RGB三个通道，通常会将其表示成有一个有3个维度的tensor（张量）。

换个角度，可以将其看做图，每个像素是一个点，如果一个像素跟我是邻接关系就把我们连一条边。

2、把文本表示成图

文本是一个序列，可以把其中的每个词表示成一个顶点，上一个词和下一个词之间连一个有向边。

3、举例

分子图、社交网络图、引文网络图

三、有哪些类型的任务

1、图级别任务

eg：给张图，对图进行分类

2、顶点级任务

预测图中节点的属性。

3、边级任务

边缘预测

四、将机器学习（神经网络）应用在图上的挑战

考虑我们将如何表示图形以与神经网络兼容。

节点、边、全局上下文可以用向量表示。

如何表示连接性：

（1）可以用邻接矩阵

问题：①可能会很大，涉及稀疏矩阵问题，而稀疏矩阵的处理是较大的技术难题）

② 有许多邻接矩阵可以编码相同的连通性，并且不能保证这些不同的矩阵在深度神经网络中会产生相同的结果（也就是说，它们不是置换不变的）。【就是邻接矩阵的某些行、列交换下位置是不影响的，但是会形成不同的图】

（2）邻接表

例子如下图，图中节点和边的属性均用标量表示的，也可以用向量表示。

邻接表的长度与边集的长度一样，第i项就表示第i条边连接的是哪两个顶点。

存储高效；对顺序无关（只需要把邻接列表中对应的调整就行）

五、图神经网络

GNN 是对图的所有属性（节点、边、全局上下文）的可优化转换，它保留了图的对称性（置换不变性）。

【对称性、置换不变性，就是指把节点、边等的顺序调了没影响】

GNN 采用“图入图出”架构，这意味着这些模型类型接受图作为输入，将信息加载到其节点、边和全局上下文中，并逐步转换这些嵌入，而不改变输入的连接性图形。【GNN输入是一个图，输出也是一个图。会变换其属性，但是不会变连接性。】

（1）构建一个最简单的GNN

在图的每个组件（节点、边、全局）上使用单独的多层感知器 (MLP)，称之为 GNN 层。对于每个节点向量，我们应用 MLP 并返回一个学习的节点向量。对每条边做同样的事情，学习每个边的嵌入，对于全局上下文向量，学习整个图的单个嵌入。

MLP输入的向量大小和输出的向量大小是一样的。

出来时属性是被更新过的，但是图的结构不变。这里MLP是对每个组件独自作用的所以满足置换不变性。所以满足了之前的两个要求。

（2）如何用这个GNN做预测

eg：n分类问题：每个节点已经有了对应的向量表示，那么就在后面加一个输出度为n的全连接，再加一个softmax。记作C_V。

对最后一层的输出（一个图），对每个顶点，进行全连接，然后做节点预测。所有节点共享一个全连接层里面的参数。

之前的GNN中，所有的节点也是共享一个MLP。

（3）如果：可能将图中的信息存储在边中，但节点中没有信息，但仍需要对节点进行预测。

需要一种从边缘收集信息并将它们提供给节点进行预测的方法。可以通过pooling（池化）来做到这一点。池化分两步进行：

①对于要合并的每个项目，收集它们的每个嵌入并将它们连接成一个矩阵。

②然后聚合收集的嵌入，通常通过求和操作。

也就是，把跟点连接的那些边的向量拿出来（2个向量），同样把全局的向量拿出来（2+1一共三个向量），把这3个向量全部加起来，就会得到代表这个节点的向量。如果节点、边、全局向量的维度不一样，还需要做一些投影。

然后再全连接层预测。

不论缺乏哪一类属性，都可以汇聚层进行。

（4）之前没有使用图的连接信息，没有把图的信息更新进属性信息中。

使用信息传递技术Passing message

把节点向量和其邻居的向量加在一起，得到一个汇聚的向量，然后再进入MLP，得到这个节点的向量更新。

这个操作，跟图片上的卷积有点像但有差异。卷积会根据核窗口求加权和，这里就是求和，但是通道还是保留了。

（5）学习边缘表示、顶点和边的信息交换

把顶点信息传递给边，然后再把边的信息传递给顶点。然后顶点和边再各自传递到MLP中做更新

更新哪些图属性以及更新它们的顺序是构建 GNN 时的一项设计决策：

（6）全局信息

到目前为止，描述的网络存在一个缺陷：即使多次应用消息传递，图中彼此相距很远的节点也可能永远无法有效地相互传递信息。对于一个节点，如果有 k 层，则信息将最多传播 k 步。对于预测任务依赖于相距很远的节点或节点组的情况，这可能是一个问题。

所以加入一个叫做master node或context vector的东西，一个虚拟的点，认为它跟所有节点相连、跟所有边相连，也就是全局信息U。

顶点汇聚到边时，会把U也汇聚过来，因为U跟节点是相连的；边汇聚到顶点时，也会把相连的U汇聚过来。最后U自己更新时会把所有顶点和边信息都拿过来。然后再各自做MLP更新。

六、实验heplayfround

作者在博客嵌入了一个可以调超参数来看训练结果的。

汇聚的操作：求和（用的其实不多）、求平均、求max。分别对应神经网络中池化层的average-pooling和max-pooling。

训练结束会告诉模型的AUC是多少。（AUC越大越好）

后面作者展示了一些超参数对最后精度影响的解释。【不展开了，图很好看，放下图】

随着超参数数量的增多，可以看到AUC的上限是提高了的。但是如果调不好，AUC也会很低。 组件向量的长度。中间的横线是中值，箱是25%-75%。希望中值横线越高越好，箱长度越短越好（表示没那么敏感）。 不同层数的影响。虽然图上看起来不同层数的结果很耦合，但是从箱图看中值是提高了的，但箱长是差不多的 汇聚的方法，没啥区别 消息传递中传递哪些消息。灰色表示都传递，效果 最后，但是如果参数没调好，也可以看到下面有三个outliers。

整体来说，GNN对超参数还是比较敏感的，能调的东西也是很多的。

七、GNN相关技术

（1）其他类型的图（多重图、超图、超节点、分层图）

（2）GNN 中的图采样sampling和批处理batching

假设有很多层时，最后一层中的节点，其实能看到一个很大的图。如果连通性够强，最后一层节点甚至可以看到整个图，然而计算梯度时，要把forward的中间变量存下来，那么对最后的节点算梯度时，要把整个图的中间结果都存下来，可能无法计算。

所以要采样，每次采一个小图，在小图上进行汇聚。下面是几种采样的方法：

第一个是随机采样一些点，然后把这些点的邻居找出来。

第二个是随机游走，从某个点开始，随机沿某条边往下走，规定最多走多少步。

第三个结合上面两种，比如随机走三步，然后把这三步的邻居们找出来。

第四个，取一个节点，然后找一阶邻居、二阶邻居...往前找k步，即宽度遍历。

batching，问题是每个节点的邻居数量是不一样的，怎么样把这些顶点和他们的邻居合并成一个规则的张量，是一个有挑战性的问题。

（3）感应偏差Inductive biases

任何机器学习、神经网络都有一些假设。

卷积神经网络假设空间变换的不变性。循环神经网络假设的是时序的连续性。

图神经网络的假设是：保持图的对称性。

（4）比较不同的聚合操作

求和、求平均、求max。没有一种池化类型可以始终区分图对【其实没有哪一种是更理想的】。

（5）GCN 作为子图函数近似subgraph function approximators

GCN（或MPNN）如果有k个层，每一层都是看一阶邻居，就等价于在卷积神经网络中有k层3*3的卷积。最后的顶点，看到的是一个子图，子图的大小是k，看到的最远的顶点距离当前顶点距离是k。然后所有子图上求一个embedding。

（5）边和图对偶

（6）在图上做卷积，或者在图上做randomwalk，等价于把邻接矩阵拿出来做矩阵乘法

（7）图注意网络Graph Attention Networks

前面图中信息传递时，求和。卷积是根据卷积核求加权和。

图上也可以求加权和，但是差别是，卷积的权重是跟位置相关的，3*3窗口，每个固定的点上有固定的权重，而图中不需要这个位置信息，因为图中邻居个数不一定，且邻居顺序可以打乱，所以图中的权重对位置是不敏感的。

所以可以用注意力机制来做，就是权重取决于两个顶点向量的关系，比如做点乘然后做一个softmax。

（8）图的可解释性

（9）Generative modeling