1 图神经网络

现在，图形的描述采用排列不变的矩阵格式，我们将描述使用图形神经网络（GNN）来解决图形预测任务。GNN 是对图的所有属性（节点、边、全局上下文）的可优化变换，它保留了图的对称性（排列不变性）。我们将使用 Gilmer 等人提出的“消息传递神经网络”框架来构建 GNN。

使用 Battaglia 等人介绍的 Graph Nets 架构原理图。GNN采用“图进图”的架构，这意味着这些模型类型接受图作为输入，将信息加载到其节点、边和全局上下文中，并逐步转换这些嵌入，而不改变输入图的连通性。

1.1 最简单的GNN

通过我们上面构建的图形的数值表示（使用向量而不是标量），我们现在已经准备好构建 GNN。我们将从最简单的 GNN架构开始，在这个架构中，我们学习所有图形属性（节点、边、全局）的新嵌入，但我们还没有使用图形的连通性。

这个GNN在图的每个分量上都使用一个单独的多层感知器（MLP）（或你最喜欢的可微模型），我们称之为GNN层。对于每个节点向量，我们应用 MLP并返回一个学习到的节点向量。我们对每条边都做同样的事情，学习每条边的嵌入，也对全局上下文向量做同样的事情，学习整个图的单个嵌入。

简单GNN的单层。图形是输入，每个分量$ (V,E,U)$都由MLP更新以生成新图形。每个函数下标表示GNN模型第$ n $层的不同图形属性的单独函数。

与神经网络模块或层一样，我们可以将这些GNN层堆叠在一起。

由于 GNN 不会更新输入图的连通性，因此我们可以使用与输入图相同的邻接列表和相同数量的特征向量来描述 GNN 的输出图。但是，输出图更新了嵌入，因为 GNN 更新了每个节点、边缘和全局上下文表示。

1.1.1 通过Pooling信息进行GNN预测

我们已经构建了一个简单的GNN，但是我们如何在上面描述的任何任务中做出预测呢？

我们将考虑二元分类的情况，但这个框架可以很容易地扩展到多类或回归情况。如果任务是对节点进行二元预测，并且图形已经包含节点信息，则方法很简单：对于每个节点嵌入，应用线性分类器。

我们可以想象一个社交网络，我们希望通过不使用用户数据（节点）来匿名化用户数据（节点），只使用关系数据（边缘）。此类方案的一个实例是我们在“节点级任务”小节中指定的节点任务。在空手道俱乐部的例子中，这只是使用人们之间的交往次数来确定与Hi先生或John H的联盟。

不管有多少个顶点，这里只有一个全连接层，所有顶点都会共享这一个全连接层的参数。

然而，事情并不总是那么简单。例如，可能将图形中的信息存储在边中，但节点中没有信息，但仍需要对节点进行预测。我们需要一种方法来从边缘收集信息，并将它们提供给节点进行预测。我们可以通过池化来做到这一点。池化分两个步骤进行：

对于要池化的每个项目，收集它们的每个嵌入并将它们连接到一个矩阵中。
然后，通常通过求和运算对收集的嵌入进行聚合。

用字母$\rho$表示池化操作，并表示我们正在从边收集到节点的信息，如$p_{E_{n} \rightarrow V_{n}}$。

从这个点相邻的边中收集信息。

因此，如果我们只有边级别的特征，并且试图预测二分类顶点信息，我们可以使用池化将信息路由（或传递）到它需要去的地方。该模型如下所示。

如果我们只有节点级的特征，并且试图预测二分类边级信息，则模型如下所示。

此类场景的一个示例是我们在“边级别任务”子部分中指定的边缘任务。节点可以被识别为图像实体，我们正在尝试对顶点进行二分类。

这是预测分子性质的常见情况。例如，我们有原子信息、连通性，我们想知道分子的毒性（有毒/无毒），或者它是否具有特定的气味（玫瑰/非玫瑰）。

在我们的示例中，分类模型$c$可以很容易地替换为任何可微模型，或者使用广义线性模型适应多类分类。

使用 GNN 模型的端到端预测任务。

现在我们已经证明了我们可以构建一个简单的GNN模型，并通过在图形的不同部分之间路由信息来进行二元预测。这种池化技术将作为构建更复杂的GNN模型的构建块。如果我们有新的图形属性，我们只需要定义如何将信息从一个属性传递到另一个属性。

请注意，在这个最简单的 GNN 公式中，我们根本没有在 GNN 层内部使用图形的连通性。每个节点都是独立处理的，每个边以及全局上下文都是独立处理的。我们仅在汇集信息进行预测时才使用连通性。

1.2 在图形的各个部分之间传递消息

我们可以通过在GNN层中使用池化来做出更复杂的预测，以便使我们学习的嵌入意识到图的连通性。我们可以使用消息传递来做到这一点，其中相邻节点或边交换信息并影响彼此的更新嵌入。

消息传递分三个步骤进行：

对于图中的每个节点，收集所有相邻节点嵌入（或消息），这就是上面描述的$g$函数
通过聚合函数（如 sum）聚合所有消息
所有池化消息都通过更新函数传递，该函数通常是学习的神经网络

正如池化可以应用于节点或边缘一样，消息传递也可以发生在节点或边缘之间。这些步骤是利用图形连通性的关键。我们将在 GNN 层中构建更详细的消息传递进行改变，从而产生具有增强表现和效果的 GNN 模型。

当应用一次时，此操作序列是最简单的消息传递 GNN 层类型。

这让人想起标准卷积：从本质上讲，消息传递和卷积是聚合和处理元素邻居信息以更新元素值的操作。在图结构中，元素是一个节点，而在图像中，元素是一个像素。但是，图结构中相邻节点的数量可以是可变的，这与图像中每个像素都有一定数量的相邻元素不同。

通过将传递GNN层的消息堆叠在一起，节点最终可以整合来自整个图的信息：在三层之后，一个节点拥有距离它三步远的节点的信息。

我们可以更新我们的架构图，以包含这个新的节点信息源：

GCN 架构示意图，该架构通过汇集距离为 1 度的相邻节点来更新图形的节点表示。

1.2.1 学习边表示

我们的数据集并不总是包含所有类型的信息（节点、边缘和全局上下文）。当我们想对节点进行预测，但我们的数据集只有边信息时，我们在上面展示了如何使用池化将信息从边缘路由到节点，但仅限于模型的最后预测步骤。我们可以使用消息传递在 GNN 层内的节点和边之间共享信息。

我们可以采用与之前使用相邻节点信息相同的方式合并来自相邻边缘的信息，即首先汇集边缘信息，使用更新函数对其进行转换，然后存储它。

然而，存储在图中的节点和边缘信息不一定具有相同的大小或形状，因此如何将它们组合起来并不清楚。一种方法是学习从边空间到节点空间的线性映射，反之亦然。或者，可以在更新功能之前将它们连接在一起。

消息传递层的架构示意图。第一步“准备”一条消息，该消息由来自边缘及其连接节点的信息组成，然后将消息“传递”到节点。

在构建 GNN 时，我们更新哪些图形属性以及以何种顺序更新它们是设计决策之一。我们可以选择是在边缘嵌入之前更新节点嵌入，还是相反。这是一个开放的研究领域，有各种各样的解决方案——例如，我们可以以“编织”的方式进行更新，其中，我们有四个更新的表示，它们被组合成新的节点和边表示：节点到节点（线性）、边到边（线性）、节点到边缘（边缘层）、边到节点（节点层）。

我们可以在GNN层中结合边缘和节点表示的一些不同方式。

1.2.2 添加全局表示

到目前为止，我们所描述的网络存在一个缺陷：即使我们多次应用消息传递，在图中彼此相距很远的节点可能永远无法有效地相互传输信息。对于一个节点，如果我们有 k 层，信息将在最多 k 步之外传播。如果预测任务依赖于相距很远的节点或节点组，这可能是一个问题。一种解决方案是让所有节点能够相互传递信息。不幸的是，对于大型图形来说，这很快就会变得计算成本高昂（尽管这种方法被称为“虚拟边缘”，已被用于分子等小型图形）。

此问题的一种解决方案是使用图形（U）的全局表示，该图形有时称为主节点或上下文向量。这个全局上下文向量连接到网络中的所有其他节点和边，并且可以充当它们之间的桥梁来传递信息，从而为整个图形构建表示。这创建了比以其他方式学习的更丰富、更复杂的图形表示。

利用全局表示的图形网络架构示意图。

在这个视图中，所有图形属性都学习了表示，因此我们可以在池化过程中通过调节我们感兴趣的属性相对于其余属性的信息来利用它们。例如，对于一个节点，我们可以考虑来自相邻节点、连接边和全局信息的信息。为了在所有这些可能的信息源上调节嵌入的新节点，我们可以简单地将它们连接起来。此外，我们还可以通过线性映射将它们映射到同一空间，然后添加它们或应用特征调制层，这可以被认为是一种特殊的注意力机制。

基于其他三个嵌入（相邻节点、相邻边、全局）调节一个节点信息的原理图。此步骤对应于 Graph Nets 层中的节点操作。

2 GNN实验

我们在这里描述了各种各样的 GNN 组件，但它们在实践中实际上有何不同？这个 GNN playground让你可以看到这些不同的组件和架构如何有助于 GNN 学习真实任务的能力。

我们的 Playground 展示了一个带有小分子图的图形级预测任务。我们使用 Leffingwell 气味数据集，它由具有相关气味感知（标签）的分子组成。预测分子结构（图形）与其气味的关系是一个跨越化学、物理学、神经科学和机器学习的 100 年历史的问题。

为了简化这个问题，我们只考虑每个分子一个二进制标签，根据专业调香师的标记，对分子图是否闻起来“刺鼻”进行分类。如果一个分子具有强烈、醒目的气味，我们就说它具有“刺鼻”的气味。例如，可能含有“烯丙醇”分子的大蒜和芥末就具有这种品质。分子 piperitone 通常用于薄荷味糖果，也被描述为具有刺激性气味。

我们将每个分子表示为一个图形，其中原子是包含其原子身份（碳、氮、氧、氟）的一热编码的节点，键是包含一热编码其键类型（单键、双键、三键或芳香族）的边缘。

我们将使用顺序GNN层构建针对此问题的通用建模模板，然后使用带有Sigmoid激活的线性模型进行分类。我们的 GNN 的设计空间有许多可以自定义模型的杠杆：

GNN 层数，也称为深度
更新时每个属性的维度。更新函数是一个 1 层 MLP，具有 relu 激活函数和用于激活归一化的层范数
池化中使用的聚合函数：最大值、平均值或总和
更新的图形属性，或消息传递的样式：节点、边缘和全局表示。我们通过布尔开关（打开或关闭）来控制它们。基线模型将是一个与图形无关的 GNN（所有消息传递），它将最后的所有数据聚合到一个单一的全局属性中。切换所有消息传递函数会产生 GraphNets 架构

为了更好地理解GNN如何学习图形的任务优化表示，我们还研究了GNN的倒数第二层激活。这些“图嵌入”是 GNN 模型在预测之前的输出。由于我们使用广义线性模型进行预测，因此线性映射足以让我们了解我们如何围绕决策边界学习表示。

由于这些是高维向量，我们通过主成分分析（PCA）将它们简化为二维。一个完美的模型可以查看单独的标记数据，但由于我们正在降低维度并且也有不完美的模型，所以这个边界可能更难看到。

尝试使用不同的模型架构来构建您的直觉。例如，查看是否可以编辑左侧的分子以增加模型预测。对于不同的模型架构，相同的编辑是否具有相同的效果？

编辑分子以查看预测如何变化，或更改模型参数以加载不同的模型。在散点图中选择不同的分子。

2.1 一些经验性的GNN设计经验

在探索上述架构选择时，您可能已经发现某些模型比其他模型具有更好的性能。是否有一些明确的GNN设计选择会给我们带来更好的性能？例如，较深的GNN模型是否比较浅的GNN模型表现更好？或者在聚合函数之间是否有明确的选择？答案将取决于数据，甚至特征化和构建图形的不同方式也会给出不同的答案。

通过下面的交互式图形，我们探索了 GNN 架构的空间以及在几个主要设计选择中执行此任务的性能：消息传递的样式、嵌入的维度、层数和聚合操作类型。

散点图中的每个点都代表一个模型：$x$轴是可训练变量的数量，$y $轴是性能。将鼠标悬停在某个点上可查看 GNN 架构参数。

每个模型的性能与其可训练变量数量的散点图。将鼠标悬停在某个点上可查看 GNN 架构参数。

首先要注意的是，令人惊讶的是，更多的参数确实与更高的性能相关。GNN是一种参数效率非常高的模型类型：即使是少量的参数（$3k$），我们已经可以找到高性能的模型。

2.1.1 不同属性嵌入

接下来，我们可以查看基于不同图形属性的学习表示的维度聚合的性能分布。

在不同的节点、边缘和全局维度上聚合模型的性能。

我们可以注意到，维数较高的模型往往具有更好的均值和下限性能，但在最大值下没有发现相同的趋势。可以找到一些性能最佳的模型用于较小的尺寸。由于维数越高，参数数量越多，因此这些观测值与上图相辅相成。

2.1.2 不同层数

接下来，我们可以看到基于 GNN 层数的性能细分。

层数与模型性能的关系图，以及模型性能与参数数量的散点图。每个点都由层数着色。

箱形图显示了类似的趋势，虽然平均性能往往随着层数的增加而增加，但性能最好的模型没有三层或四层，而是两层。此外，性能的下限随着四层的增加而降低。这种效应之前已经观察到，层数更多的GNN将在更远的距离上广播信息，并且可能会冒着其节点表示在许多连续迭代中被“稀释”的风险。

2.1.3 不同汇聚操作

我们的数据集是否有首选的聚合操作？下图根据聚合类型对性能进行了细分。

聚合类型与模型性能的图表，以及模型性能与参数数量的散点图。每个点都按聚合类型着色。

总体而言，sum 似乎对 mean 性能有非常轻微的改进，但 max 或 mean 可以给出同样好的模型。在查看 aggregation operations 的判别/表达能力时，这对于上下文很有用。

之前的探索给出了好坏参半的信息。我们可以找到平均趋势，其中复杂性越高，性能越好，但我们可以找到明显的反例，其中参数、层数或维度较少的模型表现更好。一个更明显的趋势是关于相互传递信息的属性数量。

2.1.4 不同消息传递类型

在这里，我们根据消息传递的样式对性能进行细分。在这两个极端，我们考虑了在图形实体（“none”）之间不通信的模型和在节点、边和全局变量之间传递消息的模型。

消息传递与模型性能的关系图，以及模型性能与参数数量的散点图。每个点都由消息传递着色。

总的来说，我们看到，图形属性进行通信的次数越多，平均模型的性能就越好。我们的任务以全局表示为中心，因此明确学习此属性也往往会提高性能。我们的节点表示似乎也比边表示更有用，这是有道理的，因为这些属性中加载了更多信息。

从这里开始，您可以采取许多方向来获得更好的性能。我们希望其中两个突出两个大方向，一个与更复杂的图形算法相关，另一个与图形本身有关。

到目前为止，我们的 GNN 是基于邻域的池化操作。有一些图形概念很难用这种方式表达，例如线性图形路径（连接的节点链）。设计新的机制，使图信息可以在GNN中被提取、执行和传播，这是当前的一个研究领域。

GNN研究的前沿之一不是制作新的模型和架构，而是“如何构建图形”，更准确地说，为图形注入可以利用的附加结构或关系。正如我们粗略地看到的，图形属性传达的次数越多，我们就越倾向于拥有更好的模型。在这种特殊情况下，我们可以考虑通过在节点之间添加额外的空间关系，添加不是键的边缘，或者在子图之间明确学习关系，使分子图的特征更加丰富。

3 相关技术

接下来，我们将介绍与GNN相关的无数与图结构相关的主题。

3.1 其他类型的图

虽然我们只描述了每个属性的矢量化信息的图形，但图形结构更灵活，可以容纳其他类型的信息。幸运的是，消息传递框架足够灵活，以至于将 GNN 适应更复杂的图形结构通常是为了定义新的图形属性如何传递和更新信息。

例如，我们可以考虑多边图或多重图，其中一对节点可以共享多种类型的边，当我们想要根据节点的类型以不同的方式对节点之间的交互进行建模时，就会发生这种情况。例如，对于社交网络，我们可以根据关系类型（熟人、朋友、家人）指定边缘类型。GNN 可以通过为每种边类型设置不同类型的消息传递步骤来进行调整。我们还可以考虑嵌套图，例如，节点代表一个图，也称为超节点图。嵌套图可用于表示层次结构信息。例如，我们可以考虑一个分子网络，其中节点代表一个分子，如果我们有一种将一个分子转化为另一个分子的方法（反应），那么两个分子之间共享一条边。在这种情况下，我们可以通过让一个 GNN 在分子水平上学习表示，另一个在反应网络水平上学习表示，并在训练期间在它们之间交替学习。

另一种类型的图是超图，其中边可以连接到多个节点，而不仅仅是两个节点。对于给定的图，我们可以通过识别节点社区并分配连接到社区中所有节点的超边来构建超图。

更复杂图形的示意图。在左边，我们有一个多图的例子，它有三种边类型，包括有向边。在右边，我们有一个三级层次结构图，中间级节点是超节点。

3.2 GNN 中的采样图和批处理

训练神经网络的一种常见做法是使用在训练数据的随机常数大小（批量大小）子集（小批量）上计算的梯度来更新网络参数。这种做法给图形带来了挑战，因为彼此相邻的节点和边的数量是可变的，这意味着我们不能有一个恒定的批量大小。使用图形进行批处理的主要思想是创建子图，以保留较大图形的基本属性。这种图形采样操作高度依赖于上下文，并涉及从图形中子选择节点和边。这些操作在某些情况下（引文网络）可能有意义，而在其他上下文中，这些操作可能太强了（分子，其中子图仅代表一个新的、更小的分子）。如何对图表进行采样是一个开放的研究问题。

如果我们关心在邻域级别保持结构，一种方法是随机采样统一数量的节点，即我们的节点集。然后添加与节点集相邻的距离为$ k $的相邻节点，包括它们的边。

每个邻域都可以被视为一个单独的图，GNN 可以在这些子图的批次上进行训练。可以忽略损失，只考虑节点集，因为所有相邻节点都有不完整的邻域。更有效的策略可能是首先随机抽取单个节点，将其邻域扩展到距离$ k $，然后在扩展集内选择另一个节点。一旦构造了一定数量的节点、边或子图，就可以终止这些操作。如果上下文允许，我们可以通过选择初始节点集，然后对恒定数量的节点进行子采样（例如随机，或通过随机游走或 Metropolis 算法）来构建恒定大小的邻域。

对同一图形进行采样的四种不同方法。抽样策略的选择在很大程度上取决于上下文，因为它们将生成不同的图形统计信息分布（# 节点、#edges 等）。对于高度连通的图形，还可以对边进行二次采样。

当图形足够大以至于无法放入内存中时，对图形进行采样尤为重要。激发新的架构和培训策略，例如 Cluster-GCN，我们预计图形数据集的规模将在未来继续增长。

3.3 归纳偏置

在构建模型以解决特定类型的数据上的问题时，我们希望将模型专业化以利用该数据的特征。当这成功完成时，我们通常会看到更好的预测性能、更短的训练时间、更少的参数和更好的泛化。

例如，在对图像进行标记时，我们希望利用这样一个事实，即无论它在图像的左上角还是右下角，狗仍然是狗。因此，大多数图像模型使用卷积，卷积是平移不变的。对于文本，标记的顺序非常重要，因此递归神经网络按顺序处理数据。此外，一个标记（例如“not”一词）的存在会影响句子其余部分的含义，因此我们需要能够“参与”文本其他部分的组件，而 BERT 和 GPT-3 等转换器模型可以做到这一点。这些是归纳偏差的一些例子，在这些例子中，我们正在识别数据中的对称性或规律性，并添加利用这些属性的建模组件。

在图的情况下，我们关心每个图分量（边、节点、全局）如何相互关联，因此我们寻找具有关系归纳偏差的模型。

模型应保留实体之间的显式关系（邻接矩阵）并保持图对称性（排列不变性）。我们预计实体之间交互很重要的问题将从图形结构中受益。具体来说，这意味着在集合上设计转换：节点或边上的操作顺序无关紧要，操作应该适用于可变数量的输入。

3.4 比较聚合操作

汇集来自相邻节点和边缘的信息是任何相当强大的 GNN 架构中的关键步骤。由于每个节点的邻居数目都是可变的，并且由于我们想要一种可微分的方法来聚合此信息，因此我们希望使用与节点排序和提供的节点数无关的平滑聚合操作。

选择和设计最佳聚合操作是一个开放的研究课题。聚合操作的一个理想属性是相似的输入提供相似的聚合输出，反之亦然。一些非常简单的候选排列不变运算是 sum、mean 和 max。方差等汇总统计量也有效。所有这些都采用可变数量的 inputs，并提供相同的 output，无论 input ordering如何。让我们来探讨一下这些操作之间的区别。

没有池化类型可以始终区分图形对，例如左侧的 max pooling 和右侧的 sum / mean pooling。

没有一个操作是绝对的最佳选择。当节点的相邻要素数量高度可变或您需要局部邻域特征的标准化视图时，均值运算可能很有用。当您想要高亮显示局部邻域中的单个突出要素时，max 操作可能非常有用。Sum 通过提供特征的局部分布的快照，在这两者之间提供平衡，但由于它未归一化，因此也可以突出显示异常值。在实践中，通常使用 sum。

设计聚合操作是一个开放的研究问题，它与集合上的机器学习相交。新方法，例如 Principal Neighborhood 聚合通过连接多个聚合操作并添加一个扩展函数来考虑这些操作，该函数取决于要聚合的实体的连接程度。同时，还可以设计特定于域的聚合操作。一个例子是 “Tetrahedral Chirality” 聚合运算符。

3.5 GCN 作为子图函数近似器

使用 1 度邻居查找查看 k 层的 GCN（和 MPNN）的另一种方法是作为神经网络，该网络对大小为 k 的子图的学习嵌入进行操作。

当关注一个节点时，在 k 层之后，更新的节点表示具有所有邻居的有限视点，直到 k 距离，本质上是子图表示。边表示也是如此。

因此，GCN 正在收集所有可能的大小为 k 的子图，并从一个节点或边的有利位置学习向量表示。可能的子图的数量可以组合增长，因此从头开始枚举这些子图与像在 GCN 中那样动态构建它们可能会令人望而却步。

3.6 边和图形对偶

需要注意的一点是，边预测和节点预测虽然看起来不同，但通常归结为同一个问题：图$G$上的边预测任务可以表述为对的对偶的$G$节点级预测。

为了获得$G$的对偶，我们可以奖节点转换为边（将边转换为节点）。图形及其对偶包含相同的信息，只是以不同的方式表示。有时，此属性使一种表示中的问题比另一种表示中的问题更容易，例如傅里叶空间中的频率。简而言之，要解决$G$上的边分类问题，可以考虑对$G$的dual 进行图卷积（这与$G$上的学习边表示相同），这个想法是用Dual-Primal Graph Convolutional Networks 开发的。

3.7 将图卷积作为矩阵乘法，将矩阵乘法作为在图上的游走

我们已经讨论了很多关于图卷积和消息传递的内容，当然，这就提出了一个问题，即我们如何在实践中实现这些操作？在本节中，我们将探讨矩阵乘法、消息传递及其与遍历图形的一些连接。

我们要说明的第一点是，具有大小$n_{\text {nodes }} \times node {\text {dim }}$为节点特征矩阵$X$的相邻矩阵$An{\text {nodes }} \times n_{\text {nodes }}$的矩阵乘法实现了使用求和聚合的简单消息传递。设矩阵为$B=AX$，我们可以观察到任何条目$B_{ij}$都可以表示为

$$
<A_{\text {row }{i}} \dot{X}{\text {column }{j}}>=A{i, 1} X_{1, j}+A_{i, 2} X_{2, j}+\ldots+A_{i, n} X_{n, j}=\sum_{A_{i, k}>0} X_{k, j}
$$

因为$A_{i,k}$只有当和$node_k$之间存在边时$node_i$，才为1，所以内积本质上是收集维度$j$的所有节点特征值，这些值与$node_i$共享一条边。应该注意的是，此消息传递不会更新节点特征的表示，而只是池化相邻节点特征。但是这可以通过在矩阵乘法之前或之后通过$X$你最喜欢的可微变换（例如MLP）来轻松适应。

从这个角度来看，我们可以体会到使用邻接列表的好处。由于对$A$预期的稀疏性，我们不必对$A_{i,j}$为0的所有值求和。只要我们有基于索引收集值的操作，我们应该能够只检索正条目。此外，这种无矩阵乘法使我们无需使用求和作为聚合运算。

我们可以想象，多次应用此操作可以让我们在更远的距离传播信息。从这个意义上说，矩阵乘法是遍历图的一种形式。当我们查看邻接矩阵的幂$A^K$时，这种关系也很明显。如果我们考虑矩阵$A^2$，项$A_{ij}^2$计算从$node_i$到$node_j$的所有长度为2的路径，并且可以表示为内积：

$$
<A_{\text {rou }{i}}, A_{\text {column }_{j}}>=A{i, 1} A_{1, j}+A_{i, 2} A_{2, j}+\ldots+A_{i, n} A_{n, j}
$$

直觉是，第一项$a_{i,1}a_{1,j}$仅在两个条件下为正，一条边连接$node_i$和$node_1$，另一条边连接$node_ 1$和$node_j$。换句话说，两条边形成一条长度为 2 的路径，该路径从$node_i$经过$node_1$连接到$node_j$。由于求和，我们正在计算所有可能的中间节点。当我们考虑$A^3=AA^2$时，这种直觉会延续下来以此类推至$A^k$。

关于我们如何将矩阵视为要探索的图形，存在更深层次的联系。

3.8 注意力网络

在 graph 属性之间传递信息的另一种方式是通过 attention。例如，当我们考虑一个节点及其 1 度相邻节点的和聚合时，我们也可以考虑使用加权和。然后，挑战在于以排列不变的方式关联权重。一种方法是考虑一个标量评分函数，该函数根据节点对$f(node_i,node_j)$分配权重。在这种情况下，评分函数可以解释为测量相邻节点与中心节点的相关性的函数。权重可以标准化，例如使用 softmax 函数将大部分权重集中在与任务相关的节点最相关的邻居上。这个概念是 Graph Attention Networks （GAT）的基础保留排列不变性，因为评分适用于成对的节点。一个常见的评分函数是内积，在评分之前，通常会通过线性映射将节点转换为查询和关键向量，以提高评分机制的表达能力。此外，为了可解释性，评分权重可以用作衡量边缘相对于任务的重要性的度量。

一个节点相对于其相邻节点的注意力示意图。对于每条边，都会计算、规范化交互分数，并用于对节点嵌入进行加权。

此外，Transformer可以被视为具有注意力机制的 GNN。在这个视图下，transformer 将几个元素（即字符标记）建模为全连接图中的节点，并且注意力机制为每个节点对分配边缘嵌入，用于计算注意力权重。区别在于实体之间连接的假设模式，GNN 假设稀疏模式，而 Transformer 对所有连接进行建模。

3.9 图表解释和归属

在直接部署 GNN 时，我们可能会关心模型的可解释性，以建立可信度、调试或科学发现。我们想要解释的图形概念因上下文而异。例如，对于分子，我们可能关心特定子图的存在与否，而在引文网络中，我们可能关心文章的关联程度。由于图形概念的多样性，构建解释的方法有很多种。GNNExplainer将此问题转换为提取对任务最重要的最相关的子图。归因技术将 Ranked importance 值分配给与任务相关的图表部分。由于可以综合生成现实且具有挑战性的图形问题，因此 GNN 可以作为评估归因技术的严格且可重复的测试平台。

图表上的一些可解释性技术的示意图。归因将排名值分配给图表属性。排名可以用作提取可能与任务相关的连接子图的基础。

3.10 生成模型

除了学习图上的预测模型外，我们可能还关心学习图的生成模型。使用生成模型，我们可以通过从学习的分布中采样或通过完成给定起点的图形来生成新图形。一个相关的应用是新药的设计，其中需要具有特定特性的新型分子图作为治疗疾病的候选者。

图形生成模型的一个关键挑战在于对图形的拓扑进行建模，图形的大小可能会有很大差异并且有$N_{nodes}^2$项。一种解决方案是使用自动编码器框架直接对临界矩阵进行建模，就像对图像进行建模一样。对边缘是否存在的预测被视为二分类任务。可以通过仅预测已知边和不存在的边的子集来避免该$N_{nodes}^2$。graphVAE 学习对邻接矩阵中的正连接模式和一些非连接模式进行建模。

另一种方法是按顺序构建图形，从图形开始，然后迭代地应用离散操作，例如增加或减少节点和边缘。为了避免估计离散行动的梯度，我们可以使用策略梯度。这是通过自回归模型完成的，例如 RNN，或者在强化学习场景中。此外，有时可以将图形建模为仅包含语法元素的序列。

4 结论

图形是一种强大而丰富的结构化数据类型，其优势和挑战与图像和文本截然不同。在本文中，我们概述了研究人员在构建基于神经网络的图形处理模型时提出的一些里程碑。我们已经介绍了使用这些架构时必须做出的一些重要设计选择，希望 GNN playground 可以直观地了解这些设计选择的经验结果是什么。近年来 GNN 的成功为各种新问题创造了巨大的机会，我们很高兴看到该领域将带来什么。