介绍
[!info] 这个是结合李沐和相关博客介绍整理，刚接触GNN
A Gentle Introduction to Graph Neural Networks
什么是图
表示实体(节点)集合之间的关系(边)
图里面可以嵌入信息，比如标量或向量
数据怎么表示成图
图像
把每个像素当成一个点，这样一个$224 \times 224$的图像就会变成一个$224 \times 224$的图上的每个点，周围的邻域就是每个点的邻居，绘制成邻接矩阵如下，发现会非常稀疏。
文本
我们可以通过将索引与每个字符、单词或标记相关联，并将文本表示为这些索引的序列来对文本进行重新排序。这创建了一个简单的有向图，其中每个字符或索引都是一个节点，并通过边连接到它后面的节点。
这只是粗略地表示，因为这样的话邻接矩阵只有两条对角线有值
分子
社交网络
图上问题
图层面
eg. 识别两个环
图的分类
顶点
节点标签预测
边
边缘级推理的一个示例是图像场景理解。除了识别图像中的对象之外，深度学习模型还可以用于预测它们之间的关系。我们可以将其称为边级分类：给定代表图像中对象的节点，我们希望预测这些节点中的哪些节点共享边或边的值是什么。如果我们希望发现实体之间的连接，我们可以认为图是完全连接的，并根据它们的预测值修剪边以获得稀疏图。
机器学习应用到图上
机器学习模型通常采用矩形或网格状阵列作为输入。因此，如何以与深度学习兼容的格式表示它们并不直观。图有多达四种类型的信息，我们可能希望使用它们来进行预测：节点、边、全局上下文和连通性。前三个相对简单：例如，对于节点，我们可以通过为每个节点分配索引 $i$ 并将 $node_i$ 的特征存储在 $N$ 中来形成节点特征矩阵 $N$ 。虽然这些矩阵具有可变数量的示例，但它们可以在没有任何特殊技术的情况下进行处理。
然而，表示图的连通性更复杂。也许最明显的选择是使用邻接矩阵，因为它很容易张量化。然而，这种表示有一些缺点。从示例数据集表中，我们可以看到图中的节点数量可以达到数百万，并且每个节点的边数可以高度可变。通常，这会导致非常稀疏的邻接矩阵，这是空间效率低下的。
另一个问题是，有许多邻接矩阵可以编码相同的连接性，并且不能保证这些不同的矩阵在深度神经网络中会产生相同的结果（也就是说，它们不是置换不变的）。
eg. 四个顶点互相连接，但是可以有多种不一样的图进行表示：
表示稀疏矩阵的一种优雅且节省内存的方法是邻接列表。这些将节点 $n_i$ 和 $n_j$ 之间的边 $e_k$ 的连通性描述为邻接列表的第k个条目中的元组（i，j）。由于我们期望边的数量远低于邻接矩阵的条目数量（ $n_{nodes}^2$ ），因此我们避免了对图的不连通部分的计算和存储。
使用邻接表来存储信息，两个数字表示两个点的连接，这样就可以做到对各种结果的适配
应该注意的是，图中使用每个节点/边/全局的标量值，但大多数实际的张量表示都有每个图属性的向量。我们将处理大小为 $[n_{nodes},node_{dim}]$ 的节点张量，而不是大小为 $[n_{nodes}]$ 的节点张量。其他图形属性也是如此。
图神经网络
既然图的描述是以矩阵格式的，它是置换不变的，我们将描述使用图神经网络（GNN）来解决图预测任务。GNN是对图的所有属性（节点、边、全局上下文）的可优化变换，其保持图的对称性（置换不变性）。我们将使用Gilmer等人提出的“消息传递神经网络”框架来构建GNN。
GNN采用“graph-in，graph-out”架构，这意味着这些模型类型接受图作为输入，将信息加载到其节点，边缘和全局上下文中，并逐步转换这些嵌入，而不改变输入图的连接性。
最简单的GNN
该GNN在图的每个组件(顶点、边、全局)上使用单独的多层感知器(MLP);我们称之为GNN层。对于每个节点向量，我们应用MLP并返回学习的节点向量。我们对每条边做同样的事情，学习每边嵌入，也对全局上下文向量做同样的事情，学习整个图的单个嵌入
由于是分别进行MLP，因此得到的是没有改变结构的结构，且由于没有考虑连接信息，因此不会改变结果。
由于GNN不会更新输入图的连通性，因此我们可以使用与输入图相同的邻接列表和相同数量的特征向量来描述GNN的输出图。但是，输出图已经更新了嵌入，因为GNN已经更新了每个节点，边缘和全局上下文表示。
怎么做预测
我们将考虑二元分类的情况，但这个框架可以很容易地扩展到多类或回归的情况。如果任务是对节点进行二进制预测，并且图已经包含节点信息，则方法很简单-对于每个节点嵌入，应用线性分类器，即在最后添加一个输出维度为2的全连接层，再过softmax得到输出。
然而，它并不总是那么简单。例如，您可能在图中的边中存储了信息，但在节点中没有信息，但仍然需要对节点进行预测。我们需要一种方法来从边缘收集信息，并将其提供给节点进行预测。我们可以通过合并来实现这一点。池化($\rho$)分为两个步骤：
- 对于要合并的每个项，收集它们的每个嵌入并将它们连接到一个矩阵中。
- 然后聚合收集的嵌入，通常通过求和操作。
把连边的向量都加起来，得到对应顶点的信息向量
如果我们只有节点级特征，并且试图预测二进制边缘级信息，模型看起来像这样，同样可以通过点得到边
有顶点但没有全局，那么把所有点加起来，再过全连接层：
最终流程：
但在这里还没有用到图的连通性信息
传递信息
把该点向量和该点邻居的两个顶点的向量都加在一起得到汇聚的向量，然后再更新
对于每个节点，收集其所有邻居的向量，然后求和后过MLP进行更新
有点像做卷积，但是没有加权
学习边表示
我们的数据集并不总是包含所有类型的信息（节点、边和全局上下文）。当我们想要对节点进行预测，但我们的数据集只有边信息时，我们在上面展示了如何使用池将信息从边路由到节点，但仅在模型的最后预测步骤。我们可以使用消息传递在GNN层内的节点和边之间共享信息。
我们可以采用与之前使用相邻节点信息相同的方式合并来自相邻边缘的信息，方法是首先汇集边缘信息，使用更新函数对其进行转换并存储。
但是，存储在图中的节点和边信息不一定是相同的大小或形状，因此不能立即清楚如何将它们组合。一种方法是学习从边空间到节点空间的线性映射，反之亦然。或者，可以在更新函数之前将它们连接在一起。
反过来也可以，两种方法导致不一样的结果
也可以结合两边的信息
全局信息
到目前为止，我们所描述的网络有一个缺陷：即使我们多次应用消息传递，图中彼此远离的节点也可能永远无法有效地相互传输信息。对于一个节点，如果我们有k层，信息将传播最多k步。对于预测任务依赖于相距较远的节点或节点组的情况，这可能是一个问题。一个解决方案是让所有节点都能够相互传递信息。不幸的是，对于大型图，这很快就变得计算昂贵（尽管这种称为“虚拟边”的方法已用于分子等小型图）
解决方法是加入一个master node/全局上下文向量$U$。这个全局上下文向量连接到网络中的所有其他节点和边，并且可以充当它们之间传递信息的桥梁，从而构建整个图的表示。这就创建了一个比其他方式更丰富、更复杂的图形表示。
因此汇聚的时候会汇聚U，更新的时候也会把U更新
在这个视图中，所有的图属性都已经学习了表示，所以我们可以在池化过程中通过调整我们感兴趣的属性相对于其他属性的信息来利用它们。例如，对于一个节点，我们可以考虑来自相邻节点的信息，连接的边缘和全局信息。为了在所有这些可能的信息源上嵌入新的节点，我们可以简单地将它们连接起来。此外，我们还可以通过线性映射将它们映射到相同的空间，并添加它们或应用特征调制层
Into the Weeds
其他图
虽然我们只描述了具有每个属性的矢量化信息的图，但图结构更灵活，可以容纳其他类型的信息。幸运的是，消息传递框架足够灵活，通常使GNN适应更复杂的图结构是关于定义如何通过新的图属性传递和更新信息。
我们可以考虑多边图或多重图，其中一对节点可以共享多种类型的边，当我们希望根据节点的类型对节点之间的交互进行不同建模时，就会发生这种情况。例如，对于社交网络，我们可以根据关系类型（熟人，朋友，家人）指定边类型。GNN可以通过针对每个边类型具有不同类型的消息传递步骤来适配。我们还可以考虑嵌套图，其中例如节点表示图，也称为超节点图。
嵌套图对于表示层次信息很有用。例如，我们可以考虑一个分子网络，其中一个节点代表一个分子，如果我们有一种方法（反应）将一个分子转化为另一个分子，则两个分子之间共享一条边.在这种情况下，我们可以在嵌套图上学习，方法是让一个GNN在分子水平上学习表示，另一个在反应网络水平上学习表示，并在训练过程中交替进行。
另一种类型的图是超图，其中一条边可以连接到多个节点，而不仅仅是两个节点。对于一个给定的图，我们可以通过识别节点的社区并分配一个连接到社区中所有节点的超边来构建超图。
图采样与批处理
训练神经网络的一个常见做法是使用在训练数据（小批量）的随机化恒定大小（批量大小）子集上计算的梯度来更新网络参数。
这种做法对图提出了挑战，因为相邻节点和边的数量可变，这意味着我们不能有一个恒定的批量大小。并且计算量太大，存不下所有中间值。
因此需要通过对原图进行采样来创建子图，子图保留了较大图的基本属性。这种图形采样操作高度依赖于上下文，并且涉及从图形中选择节点和边。这些操作在某些情况下可能是有意义的（引用网络），而在其他情况下，这些操作可能太强（分子，其中子图只是代表一个新的，更小的分子）。如何对图进行采样是一个开放的研究问题。
- 随机采样点+它的邻居
- 随机游走+步数
- 随机游走+邻居
- 取一个点，然后做BFS
归纳偏差
在图的情况下，我们关心每个图组件（边，节点，全局）如何相互关联，因此我们寻求具有关系归纳偏差的模型。模型应该保持实体之间的显式关系（邻接矩阵），并保持图形对称性（置换不变性）。我们希望实体之间的交互很重要的问题将受益于图结构。具体地说，这意味着在集合上设计变换：节点或边上的操作顺序不应该有关系，操作应该在可变数量的输入上工作。
比较聚合操作
没有一种操作是一致的最佳选择。当节点具有高度可变的邻居数量时，或者您需要局部邻居的特征的归一化视图时，均值运算可能很有用。当您想要突出显示局部邻域中的单个显著特征时，max操作非常有用。Sum通过提供特征的局部分布的快照，在这两者之间提供了平衡，但由于它没有归一化，也可以突出离群值。在实践中，通常使用sum。
GCN可以认为是子图的近似
GCN收集所有可能的大小为k的子图，并从一个节点或边的Vantage位置学习向量表示。可能的子图的数量可以组合地增长，因此从一开始就枚举这些子图，而不是像在GCN中那样动态地构建它们，可能会受到限制。
