原文：TowardsDataScience

协议：CC BY-NC-SA 4.0

解释了图形嵌入

原文：https://towardsdatascience.com/graph-embeddings-explained-f0d8d1c49ec

节点、边和图嵌入方法的概述和 Python 实现

图片由 Ester Marie Doysabas 从 Unsplash 拍摄

近年来，基于图形的机器学习有所增加。基于图的方法可应用于数据科学中的各种常见问题，如链接预测、社区检测、节点分类等。根据你如何组织你的问题和你所拥有的数据，有许多潜在的方法来解决它。这篇文章将提供一个高层次的概述和基于图形的嵌入算法背后的直觉。我还将介绍如何引用像node2vec这样的预建 Python 库来生成图中的节点嵌入。下面概述了本文涵盖的内容。

目录

• 图上的机器学习
  -图上机器学习的好处
• 什么是图嵌入？
• 图嵌入的类型
  -节点嵌入
  -边嵌入
  -图嵌入
• Python 实现
  -需求
  -节点嵌入
  -边嵌入
  -图嵌入
• 结束语
• 资源

图上的机器学习

人工智能有各种分支，从推荐系统、时间序列、自然语言处理、基于图形等。通过基于图形的机器学习，有各种方法来解决常见的过程。图由节点之间的一系列成对关系组成。使用图可以解决各种各样的问题，这些问题可以包括社区检测、链路预测、节点分类等。这些问题和解决方案因问题和数据集而异。

与图的机器学习相关的主要问题是找到一种表示(或编码)图结构的方法，以便它可以很容易地被机器学习模型利用[1]。通常，机器学习中的问题需要与模型的图形相关联的结构化表格数据来学习某种表示。在过去，统计测量或核函数是实现这一点的主要方法。然而，近年来，趋势已经转向对图进行编码以生成嵌入向量来训练机器学习模型。

机器学习对图形的好处

机器学习模型的目标是接受训练，以大规模学习和识别数据集中的模式。在处理图形时，这一点可能会被放大。它们提供了文本、音频或图像等其他形式的数据所没有的不同且复杂的结构。基于图的机器学习可以检测和解释重复出现的潜在模式[2]。

例如，我们可能对确定与社交网络上的用户相关联的人口统计信息感兴趣。人口统计数据是指年龄、性别、种族等。像脸书或 Twitter 这样的公司的社交媒体网络从数百万到数十亿用户和数万亿边缘。一定有几种模式与来自该网络的用户的人口统计信息相关，这些模式不容易通过人类或算法检测到，但模型应该能够学习它们。类似地，当一对用户目前不是朋友时，我们可能想要推荐他们成为朋友。这进入了链接预测方面(基于图形的机器学习的另一个应用)。

什么是图嵌入？

特征工程是指处理输入数据以形成一组特征的常用方法，这些特征提供了原始数据集的紧凑且有意义的表示。特征工程阶段的结果将被用作机器学习模型的输入。虽然这是常见表格结构数据集的处理过程，但在处理图形时，这是一种难以执行的方法。我们需要找到一种方法来生成与所有图形数据相关联的适当表示。

从图中生成表示结构信息的特征有多种方法。最常见和直接的方法是从图表中提取统计数据。这可以包括诸如识别程度分布、页面等级分数、中心性度量、jaccard 分数等。离此更远的一步将是应用能够将期望的属性结合到模型中的核函数。核函数的问题是生成结果的相关时间复杂度。

最近的研究趋势已经转向寻找有意义的图形表示。这项研究的结果产生了图的嵌入。这些嵌入学习保持网络原始结构的图形表示。我们可以认为这是一个映射函数，它的目的是将一个离散的图转换成一个连续的域。一旦学习了该函数，就可以将其应用于该图，并且所得到的映射可以用作机器学习算法的特征集[2]。

图嵌入的类型

通常，对图形的分析可以分为 3 个粒度级别。节点级、边级和图级(整个图)。每一层都包含不同的生成嵌入向量的过程，所选择的过程应该取决于你正在处理的问题和数据。请参考下图，该图直观地概括了每个粒度级别的嵌入是如何彼此不同的。

节点嵌入

在节点级别，您生成一个与图中每个节点相关联的嵌入向量。这个嵌入向量可以保存图形表示和结构。本质上，彼此非常接近的节点也应该具有彼此非常接近的向量。这是 Node2Vec 等流行的节点嵌入模型的基本原则之一。

二维空间中节点嵌入的可视化表示。图片由作者提供。

边缘嵌入

边级别，您生成一个与图中每条边相关联的嵌入向量。链路预测问题是使用边缘嵌入的常见应用。链接预测是指预测一对节点应该具有连接它们的边的可能性。这些嵌入可以学习由图提供的边属性。例如，在一个社交网络图中，你可以有一个多边图，其中节点可以根据年龄范围、性别、友谊等通过边连接。表示该边的相关向量可以学习这些边属性。

二维空间中边缘嵌入的可视化表示。图片由作者提供。

图形嵌入

图级别的嵌入并不常见，它们包括生成一个表示每个图的嵌入向量。考虑一个有多个子图的大图，每个对应的子图都有一个表示图结构的嵌入向量。分类问题是一个常见的应用，其中图嵌入可能是有用的。这些类型的问题包括将一个图形分类到一个特定的类别。

二维空间中图形嵌入的可视化表示。图片由作者提供。

Python 实现

要求

Python=3.9
networkx>=2.5
pandas>=1.2.4
numpy>=1.20.1
node2vec>=0.4.4
karateclub>=1.3.3
matplotlib>=3.3.4

如果没有安装 node2vec 包，这里的是通过命令行安装的库文档。同样，你可以用 Python 安装 karateclub 包，指令如下这里。

节点嵌入

从可视化的杠铃图生成的节点嵌入。图片由作者提供。

有许多方法可以计算节点嵌入，如 node2vec、深度行走、随机行走等。出于本教程的目的，我将使用 node2vec。

边缘嵌入

可视化杠铃图生成的边缘嵌入。图片由作者提供。

Hammard 嵌入器的源代码可以在这里找到。

图形嵌入

从许多随机生成的图中生成的图嵌入。图片由作者提供。

graph2vec 算法的源代码可以在这里找到。

结束语

简单地说，嵌入是一个将离散图映射到向量表示的函数。从图中可以生成各种形式的嵌入，即节点嵌入、边嵌入和图嵌入。所有这三种类型的嵌入都提供了一种矢量表示，将图的初始结构和特征映射到 x 维的数值量。

你可以在我的 GitHub 页面这里查看与本教程相关的资源库。

如果你想转型进入数据行业，并希望得到经验丰富的导师的指导和指引，那么你可能想看看最敏锐的头脑。Sharpest Minds 是一个导师平台，导师(他们是经验丰富的实践数据科学家、机器学习工程师、研究科学家、首席技术官等。)将有助于你的发展和学习在数据领域找到一份工作。点击这里查看。

资源

• [1]https://www-cs . Stanford . edu/people/jure/pubs/graph representation-IEEE 17 . pdf
• [2]Aldo Marzullo、Claudio Stamile 和 Enrico Deusebio 的《图形机器学习》
• [3]https://karateclub . readthedocs . io/en/latest/_ modules/karateclub/graph _ embedding/graph 2 vec . html

如果你觉得这篇文章有用，这里有一些我写的其他文章，你可能也会觉得有用。

图形嵌入:节点如何映射到向量

原文：https://towardsdatascience.com/graph-embeddings-how-nodes-get-mapped-to-vectors-2e12549457ed

• 大多数传统的机器学习算法对数字向量数据进行处理
• 图嵌入通过学习从图结构数据到向量表示的映射，打开了强大的工具箱
• 它们的基本优化是:在嵌入空间中映射具有相似上下文的节点
• 图中节点的上下文可以使用两种正交方法之一来定义——同伦和结构等价——或者它们的组合
• 一旦定义了度量标准，数学就被简明地公式化了——让我们来探索一下。

图形数据库和机器学习

图形数据库对各种来源的相关数据的大数据应用程序有着广泛的热情和采用。它们基于强大的存储概念，使简洁的查询语言能够分析数据中复杂的关系模式。因此，像 PageRank、中心性检测、链接预测和模式识别这样的算法可以用简单和直观的方式来陈述。

然而，大多数发展良好的传统机器学习算法，如线性和逻辑回归、神经网络等，都是基于数字向量表示的。要打开这个强大的工具箱来处理图结构，我们需要一种方法来以向量形式表示我们的数据网络。图嵌入是从图中的数据学习这种映射的一种形式。

图嵌入的目的

作者图片

我们的目标是为图中的每个节点找到一个向量表示。映射应该代表节点的网络结构，而不是考虑节点的相关特征。换句话说，节点的嵌入向量应该基于它的关系和相邻节点。图中相似的节点应该在向量空间中紧密映射。我们将节点映射到的向量空间称为嵌入空间。

现在，如果我们看一下上面的陈述，我会想到两个问题，需要进一步思考:

• 是什么使得图中的两个节点相似？
• 嵌入空间中的关闭是什么意思？

网络中的相似节点

为了详细说明图中的相似性，让我们考虑一个句子:

作者图片

一个句子是一系列单词，每个单词都有一个确定的位置。因此，一个句子中的一个词恰好有一个祖先和一个后继者。为了定义一个单词在句子中的上下文，我们可以使用它周围的单词。例如，单词“capital”的距离一上下文是单词“the”和“of”。距离-两个上下文将是单词“是”，“的”，“的”，“德国”。这被称为 n-gram 模型，并被称为 word2vec 的用于查找单词嵌入的流行方法所使用。

类似于 n-gram，我们可以定义图中节点的上下文。尽管如此，我们在图形结构中比在单词序列中有更多的选择。在一般的图中，每个节点可能连接到两个以上的其他节点，而在一个句子中，一个单词只有一个直接的祖先和后继。

因此，一个句子是一个向量，沿着索引轴移动可以探索单词的上下文。然而，图被描述为二维邻接矩阵，并且节点的直接祖先是向量。为了探索节点的上下文，我们在每个距离级别上都有多个选择，并且我们必须决定如何遍历它们。

通常，有两种正交的方法来探索网络环境:

作者图片

1. 广度优先:在我们(可能)转移到距离为 2 的节点之前，我们首先详细说明源节点的直接邻居。这也被称为同性恋，来源于一个社会学概念，即人们通常倾向于与相似的人密切互动。因此，它基于图中相似节点具有紧密关系的假设。
2. 深度优先:我们首先沿着从源节点开始到其深度的路径探索一个连接链，然后再继续下一个。与同向性相反，这种度量从更广的角度捕捉了网络中节点的角色。我们不是着眼于密切的关系，而是寻求发现一个节点的结构角色:例如，它是如何嵌入到一个更大的社区环境中的。这种度量被称为结构等价。

我们可以使用这两种方法来查找节点的上下文——可能的话，可以将它们结合起来。有了一组描述每个节点上下文的节点，我们可以使用这些集合来比较每对节点的上下文相似性。例如，我们可以应用 Jaccard 相似度来度量两个上下文有多少重叠。这将为我们提供一种在图中找到具有相似网络结构的节点的方法。

作者图片

背景取样

然而，我们不能对任何给定节点的整个上下文进行采样，因为这最终会导致捕获任何节点的整个图。因此，我们采用一种叫做抽样策略的近似方法。想法是在源顶点开始固定数量的随机行走，以探索其上下文来生成随机样本。node2vec 定义的采样策略结合了同质性和结构等价性。它实现了一个参数来决定在行走的每一步中是应该靠近源节点(同向性)还是应该探索另一个距离级别(结构等价)。

作者图片

在 node2vec 中，我们试图为每个节点找到一个数字向量，而不是使用前面描述的 Jaccard 相似性。我们使用图中节点的采样上下文来优化映射函数，以将具有相似上下文的节点映射到一起。

node2vec 的数学

让我们通过考虑下面的例子来详细探讨 node2vec 是如何工作的:

V: all nodes in graph
N_S(u): neighborhood of u determined by sample strategy S
f(u): mapping function of node u onto a vector

我们的目标是找到 V 中所有节点 u 的嵌入，使得具有相似上下文的节点的向量表示在嵌入空间中是接近的。我们已经知道图中相似的上下文意味着什么，但是我们仍然需要定义，嵌入空间中的接近意味着什么。

作者图片

现在让我们只考虑图中的两个节点:

u: source node
v: node in context of u

为了开始我们的数学，我们简单地为两个节点选择两个随机向量f(u), f(v)。为了度量嵌入空间中的相似性，我们使用两个向量的点积，即它们之间的角度。

作者图片

由于节点v在u的附近，现在的想法是递增地优化映射函数f，使得它们的相似性得到最大化。

为了将我们的相似性转化为概率，我们应用了一个 softmax。softmax 使用u与所有其他向量v in V的所有相似性的总和来标准化相似性得分dot(f(u), f(v))。因此，点积被转换成一个介于[0,1]之间的数字，所有的相似性加起来等于 1。结果是在节点u的上下文中从它们的向量表示中看到节点v的概率。现在，我们可以通过使用随机梯度下降更新我们的向量f(u)来递增地优化这个概率。

作者图片

下一步是推广这一概念，不仅对 N_S(u)中的一个节点 v 进行优化，而且对 u 上下文中的所有节点进行优化。如果给定节点 u，我们希望优化看到整个采样上下文的概率。如果我们假设样本独立，我们可以将此公式简化为简单概率的乘积。

作者图片

最后，我们想学习图中每个源节点 u 的映射。因此，我们将该公式同时应用于图的所有节点。我们使用 SGD 通过调整我们的映射f来优化总和，以便概率增加。我们逐步改进，直到达到最大迭代次数，或者在优化问题中找到一个固定点。

作者图片

进一步说明

当实现这个解决方案并在大型数据集上运行它时，有一个主要的挑战:当我们计算 softmax 来确定概率P(f(v) | f(u))时，分母中有一个归一化项，计算起来很难看。这个归一化项是图中u和所有其他节点的所有相似性的总和。它在优化的整个迭代中保持固定，因此对于源节点u的求和的所有迭代也是固定的。第一个优化是将该因子移出总和。

第二个挑战是，计算所有向量的这种因子非常昂贵。在每次迭代中，我们必须确定每个源节点u与图中所有其他向量的点积，以找到归一化因子。为了克服这一点，一种称为负采样的技术被用来近似这一因素。

边缘嵌入

上述方法也可以应用于不同的基本假设:代替寻找具有相似上下文的节点的映射，我们也可以设置将边映射到嵌入空间的不同目标，使得这些边靠近，共享相同的节点。结合 node2vec 中的节点和边嵌入，我们在更一般的术语下导出图嵌入，它能够将相关数据映射到向量表示。

结论

我们已经探索了如何找到一个映射f(u)来将一个图的节点映射到一个向量空间中，这样相似的节点是闭合的。有多种方法来定义图上下文中节点的相似性:同构和结构等价。两者都有正交的方法，node2vec 定义了一个策略，将两者结合成一个参数化的采样策略。采样策略是一种找到节点上下文的方法，这反过来又被用来导出我们的嵌入。嵌入空间中的相似性又被定义为两个映射向量之间的点积。嵌入本身是使用随机梯度下降的迭代优化。它在每次迭代中调整所有节点的向量，以最大化同时看到来自相同上下文的节点的概率。对非常大的数据集的实现和应用需要一些统计近似来加速计算。

node2vec 是打开传统机器学习算法的强大工具箱以处理图结构数据的重要钥匙。

就我个人而言，我再次被解决手头问题的算法定义的简单和简洁所吸引。我发现令人惊讶的是，如果将这些方法应用于正确的问题，使用正确的数据量，它们的效果会有多好。

参考

• node2vec:网络的可扩展特征学习。a .格罗弗 j .莱斯科维奇。 ACM SIGKDD 知识发现与数据挖掘国际会议(KDD) ，2016。

图形机器学习@ ICML 2022

原文：https://towardsdatascience.com/graph-machine-learning-icml-2022-252f39865c70

GraphML 有什么新特性？

最新进展和热点趋势，2022 年 7 月版

国际机器学习大会(ICML) 是研究人员发表最佳作品的主要场所之一。ICML 2022 挤满了数百份论文和众多致力于图表的工作室。我们分享最热门的研究领域的概况🔥在图表 m1 中。

本帖由 迈克尔·高尔金 (米拉)和 朱兆承 (米拉)撰写。

我们尽最大努力强调了 ICML 会议上图形 ML 的主要进展，每个主题包含 2-4 篇论文。尽管如此，由于被接受的论文数量庞大，我们可能会错过一些作品——请在评论或社交媒体上让我们知道。

目录(可点击):

1. 生成:去噪扩散就是你所需要的
2. 图形变形金刚
3. 理论和表达性 GNNs
4. 光谱 GNNs
5. 可解释的 GNNs
6. 图形增强:超出边缘丢失
7. 算法推理和图形算法
8. 知识图推理
9. 计算生物学:分子连接、蛋白质结合、性质预测
10. 酷图应用

代:去噪扩散是你所需要的

去噪扩散概率模型 ( DDPMs )将在 2022 年接管深度学习领域，几乎所有领域都具有令人惊叹的生成质量和比 GANs 和 VAEs 更好的理论属性，例如，图像生成( GLIDE 、 DALL-E 2 、 Imagen )、视频生成、文本生成( Diffusion-LM )，甚至从概念上讲，扩散模型逐渐向输入对象添加噪声(直到它是高斯噪声)，并学习预测添加的噪声水平，以便我们可以从对象中减去它(去噪)。

扩散可能是 GraphML 在 2022 年的最大趋势——特别是当应用于药物发现、分子和构象异构体生成以及一般的量子化学时。通常，它们与等变 GNNs 的最新进展配对。ICML 为图形生成提供了几个很酷的去噪扩散实现。

在由 Hoogeboom、Satorras、Vignac 和 Welling 撰写的《3d中用于分子生成的等变扩散中，作者定义了用于分子生成的等变扩散模型( EDM ，其必须在原子坐标 x 上保持 E(3)等变(关于旋转*、平移、重要的是，分子具有不同的特征形态:原子电荷是一个有序整数，原子类型是一个热点分类特征，原子坐标是连续特征，因此，例如，你不能只添加高斯噪声到一个热点特征，并期望模型工作。相反，作者设计了特定特征的噪声处理和损失函数，并缩放输入特征以训练稳定性。*

EDM 采用最先进的 E(n) GNN 作为神经网络，根据输入特征和时间步长预测噪声。在推理时，我们首先对期望数量的原子 M 进行采样，然后我们可以根据期望的属性 c 对 EDM 进行调节，并要求 EDM 生成分子(由特征 x 和 h 定义)作为 x，h ~ p(x，h | c，M) 。

在实验上，EDM 在实现负对数似然性、分子稳定性和独特性方面远远优于基于归一化流量和 VAE 的方法。烧蚀表明，等变 GNN 编码器至关重要，因为用标准 MPNN 代替它会导致性能显著下降。GitHub 上已经有的代码了，试试吧！

向前和向后扩散。来源: Hoogeboom、Satorras、Vignac 和 Welling 。

基于扩散的生成可视化。来源:推特

对于 2D 图形， Jo、Lee 和 Hwang 提出了通过随机微分方程系统 ( GDSS )的图形扩散。之前的 EDM 是去噪扩散概率模型(DDPM)的一个实例， GDSS 属于 DDPMs 的姐妹分支，即基于分数的模型*。事实上，最近的(ICLR ’ 21)表明，如果我们用随机微分方程(SDEs)描述前向扩散过程，DDPMs 和基于分数的模型可以统一到同一个框架中。***

SDE 允许将连续时间内的扩散建模为维纳过程(为简单起见，假设它是添加噪声过程的一个奇特术语)，而 DDPMs 通常以 1000 步将其离散化(具有可学习的时间嵌入)，尽管 SDE 需要使用特定的解算器。与之前基于分数的图生成器相比， GDSS 将相邻关系 A 和节点特征 X 作为输入(并预测)。表示为 SDE 的向前和向后扩散需要计算分数*——这里是联合对数密度(X，A)的梯度。为了获得这些密度，我们需要一个基于分数的模型，这里作者使用了一个具有注意力集中的 GNN(图形多头注意力)。*

在训练时，我们求解一个正向 SDE 并训练一个得分模型，而在推理时，我们使用训练好的得分模型并求解反向时间 SDE 。通常，你会在这里使用类似于朗之万动力学的东西，例如，朗之万 MCMC，但是高阶龙格-库塔解算器原则上也应该在这里工作。实验表明，在 2D 图生成任务中，GDSS 远远优于自回归生成模型和一次性 VAEs，尽管由于集成了逆时 SDE，采样速度可能仍然是一个瓶颈。 GDSS 码已经有了！

GDSS 直觉。资料来源:乔、李和黄

👀现在看看 arxiv，我们期待今年会有更多的扩散模型发布——图中的 DDPMs 应该有他们自己的大博客，敬请关注！

➡️最后，非扩散生成的一个例子是 Martinkus 等人的工作，他们设计了用于一次性图形生成的 GAN。除了经常立即生成邻接矩阵的其他 GANs 之外， SPECTRE 的思想是根据拉普拉斯算子的前 k 个(最低)特征值和特征向量来生成图形，这些特征值和特征向量已经给出了集群和连通性的一些概念。1️⃣ 幽灵生成 k 个特征值。2️⃣作者使用了一个聪明的技巧，从 top-k 特征向量诱导的斯蒂费尔流形中抽取特征向量。Stiefel 流形提供了一组标准正交矩阵，从中我们可以采样一个 n x k 矩阵。3️⃣Finally，获得一个拉普拉斯算子，作者使用一个可证明强大的图网来生成最终邻接。

实验表明， SPECTRE 比其他 GANs 好几个数量级，比自回归图形生成器快 30 倍🚀。

SPECTRE 生成特征值->特征向量->邻接的 3 步过程。来源:马丁库斯等人

图形转换器

在今年的 ICML 上，我们有两篇关于改进图形转换器的论文。

首先，陈，奥布雷，博格瓦德提出结构感知变压器。他们注意到自我关注可以被重写为核平滑，其中查询键乘积是一个指数核。然后归结为找到一个更一般化的内核——作者建议使用节点和图的功能来添加结构意识，即k-子树和k-子图特征。K-子树本质上是 k-hop 邻域，可以相对快速地挖掘，但最终受限于 1-WL 的表达能力。另一方面，k-子图的计算成本更高(并且很难扩展)，但是提供了可证明的更好的区分能力。

无论您选择什么特征，这些子树或子图(为每个节点提取的)都将通过任何 GNN 编码器(例如，PNA)进行编码，汇集(总和/平均值/虚拟节点)，并在自我关注计算中用作查询和关键字(参见图示👇).

从实验上来说，k 为 3 或 4 就足够了，k-子图特性在我们能够负担计算费用的图上工作得更好。有趣的是，像拉普拉斯特征向量和随机游走特征这样的位置特征只对k-子树 SAT* 有帮助，而对k-子图 SAT 则毫无用处。*

资料来源:【陈、奥布雷、博格瓦德

第二， Choromanski，林，陈等人(该团队与著名表演者的作者有很多重叠)研究的是实现亚二次注意的原理性机制。特别是，他们考虑了相对位置编码(RPE)及其对不同数据形式(如图像、声音、视频和图形)的变化。考虑到图形，我们从graph former得知，将最短路径距离注入注意力效果很好，但是需要完整注意力矩阵的具体化(因此，不可扩展)。我们能否在没有完全具体化的情况下近似 softmax 注意力，但仍然包含有用的图形归纳偏差？🤔

是啊！作者提出了两种这样的机制。(1)事实证明，我们可以使用图形扩散核(GDK)——也称为热核——模拟热传播的扩散过程，并作为最短路径的软版本。然而，扩散需要调用求解器来计算矩阵指数，因此作者设计了另一种方法。(2)随机行走图-节点核(RWGNK ),其值(对于两个节点)编码从这两个节点开始的随机行走获得的(这两个节点的)频率向量的点积。

随机漫步很棒，我们喜欢随机漫步😍查看下图，了解漫射和 RW 内核结果的可视化描述。具有 RWGNK 内核的最终转换器被称为**图内核注意力转换器***【GKAT】**，并且针对从 er 图中拓扑结构的综合识别到小型 compbio 和社交网络数据集的几个任务进行探索。GKAT 在合成任务上显示出更好的结果，并且在其他图形上的表现与 GNNs 相当。如果能看到真正的可伸缩性研究将转换器推向输入集大小的极限，那就太好了！*

资料来源:乔罗曼斯基、林、陈等

理论与表达性 GNNs

GNN 社区继续研究突破 1-WL 表达能力的上限并保持至少多项式时间复杂性的方法。

➡️ 帕普和瓦腾霍夫从当前理论研究的准确描述开始:

每当引入新的 GNN 变体时，相应的理论分析通常会显示它比 1-WL 更强大，有时还会将其与经典的 k-WL 层次结构进行比较……我们能否找到一种更有意义的方法来衡量 GNN 扩展的表现力？

作者将表达性 GNNs 的文献分为 4 类:1️⃣ k-WL 和近似；2️⃣底座计数*(s)**；3️⃣子图和邻域感知 GNNs (N) (在 Michael Bronstein 最近的文章中广泛讨论了)；带有标记的 4️⃣gnns——这些是节点/边扰动方法和节点/边标记方法 (M) 。然后，作者提出了所有这些 k-WL、S、N 和 M 家族如何相关以及哪一个在何种程度上更强大的理论框架。该层次比 k-WL 更细粒度，有助于设计具有足够表现力的 gnn，以覆盖特定的下游任务并节省计算。*

不同的富有表现力的 GNN 家族的等级制度。n =子图 GNNs，S =子结构计数，M =带标记的 GNNs。资料来源: Papp 和 Wattenhofer

➡️也许是最美味的 ICML’22 作品是由厨师们用🥓 SpeqNets 🥓(斯帕克在德语中是培根*)。已知的高阶 k-WL gnn 要么在 k 阶张量上操作，要么考虑所有的 k 节点子图，这意味着在存储器需求上对 k 的指数依赖，并且不适应图的稀疏性。 SpeqNets 为图同构问题引入了一种新的启发式算法，即 (k，s)-WL ，它在表达性和可伸缩性之间提供了更细粒度的控制。*

本质上，该算法是局部 k-WL 的变体，但仅考虑特定元组以避免 k-WL 的指数存储复杂性。具体来说，该算法只考虑最多具有 s 个连通分量的 k 节点上的 k 元组或子图，有效地利用了底层图的潜在稀疏性——变化的 k 和 s 导致理论上的可扩展性和表达性之间的折衷。

基于上述组合见解，作者导出了一种新的置换等变图神经网络，记为 SpeqNets ，在极限情况下达到普适性。与受监督的节点和图形级分类和回归机制中的标准高阶图形网络相比，这些架构大大减少了计算时间，从而显著提高了标准图形神经网络和图形核架构的预测性能。

的等级制度🥓SpeqNets🥓。来源:莫里斯等人

接下来，黄等人以一种非正统的眼光看待排列不变的 gnn，认为精心设计的排列敏感的gnn 实际上更有表现力。Janossy pooling 的理论说，如果我们展示一组变换的所有可能的例子，那么一个模型对于这样一组变换是不变的，对于 n 个 T21 元素的排列，我们有一个难以处理的 n！排列组合。相反，作者表明，只考虑节点的邻域的成对 2 元排列就足够了，并且可以证明比 2-WL 更强大，并且不比 3-WL 更弱。

实际上，提出的 PG-GNN 扩展了 GraphSAGE 的思想，通过两层 LSTM 对节点邻域的每个随机排列进行编码，而不是传统的 sum/mean/min/max 。此外，作者设计了一种基于哈密顿圈的线性置换采样方法。

PG-GNN 排列敏感聚集思想。来源:黄等

你可能想看看其他一些有趣的作品:

• 蔡和王研究不变图网络的收敛性质，与传统 MPNNs 的不同之处在于，它们对节点和边特征的操作如同对整体张量的等变操作。基于 graphon 理论，作者找到了一类可证明收敛的 ign。更多技术细节在牛逼的 Twitter 帖子！
• 高与里贝罗研究⏳时间 GNNs⏳设计两个系列:(1)——我们首先通过一些 GNN 嵌入图形快照，然后应用一些 RNN；(2) 先时间后图形其中，我们首先通过 RNN 对所有节点和边特征(在所有快照的统一图形上)进行编码，然后仅应用单个 GNN 过程，例如， TGN 和 TGAT 可以被认为是该家族的实例。理论上，作者发现当使用像 GCN 或 GIN 这样的标准 1-WL GNN 编码器时，时间-图形比时间-图形更有表现力，并提出了一个带有 GRU 时间编码器和 GCN 图形编码器的简单模型。该模型在时态节点分类和回归任务上表现出极具竞争力的性能，速度快 3-10 倍，GPU 内存效率高。有趣的是，作者发现无论是 时间和图形还是时间和图形 都不足以表达时间链接预测的🤔。**
• 最后，“魏斯费勒-雷曼遇上-瓦瑟斯坦”作者【陈、林、梅莫利、万、王(5-第一作者联合论文👀)从 WL 核中导出一个多项式时间的 WL 距离，这样我们可以测量两个图的相异度——WL 距离为 0 当且仅当它们不能被 WL 测试区分，并且正的当且仅当它们可以被区分。作者进一步认识到，提出的 WL 距离与格罗莫夫-瓦瑟斯坦距离有着深刻的联系！

魏斯费勒-莱曼如何在实践中遇到格罗莫夫-沃瑟斯坦？本应在论文中由陈、老林、莫文蔚、万、王。来源:期限

光谱 GNNs

➡️光谱 GNNs 往往被忽视的空间 GNNs 的主流，但现在有一个理由让你看看光谱 GNNs 🧐.在王和张的《 谱图神经网络 有多强大》一文中，作者证明了在一些较弱的假设下，线性谱是图上任何函数的通用逼近子。更令人兴奋的是，根据经验，这些假设对于真实世界的图来说是正确的，这表明线性谱 GNN 对于节点分类任务来说足够强大。

但是我们如何解释光谱 GNNs 实验结果的差异呢？作者证明了谱 GNNs 的不同参数化(特别是多项式滤波器)影响收敛速度。我们知道 Hessian 矩阵的条件数(等损线有多圆)与收敛速度高度相关。基于这种直觉，作者提出了一些有利于优化的正交多项式。被命名为雅可比基的多项式是切比雪夫基中使用的切比雪夫基的推广。雅可比基由两个超参数定义， a 和 b 。通过调整这些超参数，可以找到一组有利于输入图形信号的基。

实验上， JacobiConv 在嗜同性和嗜异性数据集上都表现良好，即使作为线性模型也是如此。或许是时候抛弃那些华而不实的 gnn 了，至少对于节点分类任务来说是这样😏。

➡️:还有两篇关于光谱 gnn 的论文。一个是基于光谱浓度分析的图高斯卷积网络 (G2CN)，在嗜异性数据集上显示出良好的结果。另一篇来自 Yang 等人的文章分析了基于光谱平滑度的图形卷积中的相关性问题，显示了锌上的 0.0698 MAE 的非常好的结果。

可解释的 GNNs

由于大多数 GNN 模型都是黑箱，所以解释 GNNs 在关键领域的应用预测是很重要的。今年我们在这个方向有两篇很棒的论文，一篇是熊等人的高效而强大的事后模型，另一篇是苗等人的内在可解释模型。

熊等人扩展了他们之前的 GNN 解释方法 GNN-LRP ，使之更具可扩展性。与其他方法( GNNExplainer 、 PGExplainer 、 PGM-Explainer )不同的是， GNN-LRP 是一种考虑子图中节点联合贡献的高阶子图归属方法。对于子图不仅仅是一组节点的任务来说，这种性质是必要的。例如，在分子中，六个碳的子图(忽略氢)可以是苯(一个环)或己烷(一个链)。如下图所示，高阶方法可以计算出这样的子图(右图)，而低阶方法(左图)则不能。

来源:熊等人。

然而，GNN-LRP 算法的缺点是，它需要计算子图中每一次随机行走的梯度 w.r.t .对于一个子图 S 和 L 跳随机行走需要 O(|S|L) 。这里动态编程来拯救😎。请注意，梯度 w.r.t. a 随机游走是乘法的(链式法则)，不同的随机游走通过求和来聚合。这可以通过和积算法有效地计算出来。这个想法是利用乘法上的求和的分配性质(更普遍的是，半环)，在每一步聚合部分随机游走。这就构成了模型， 子图 GNN-LRP (sGNN-LRP) 。

sGNN-LRP 还通过广义子图属性对 GNN-LRP 进行了改进，该属性考虑了子图 S 及其补图 G\S 中的随机游动。虽然看起来很复杂，但广义子图属性可以通过两次和积算法来计算。实验上， sGNN-LRP 不仅比所有现有的解释方法更好地发现属性，而且运行速度与常规消息传递 GNN 一样快。可能是解释和可视化的有用工具！🔨

💡顺便说一句，基于随机游走的模型比简单的节点或边模型更有表现力，这并不新鲜。NeurIPS 的 21 篇论文 NBFNet 用随机游走和动态规划解决知识图推理，在直推式和归纳式设置中都取得了惊人的结果。

➡️ 苗等从另一个角度研究内在可解释的 GNN 模型。他们表明，事后解释方法，如 GNNExplainer ，对于解释来说是不合格的，因为它们仅仅使用了一个固定的预训练 GNN 模型。相比之下，联合优化预测器和解释模块的内在可解释 GNN 是更好的解决方案。沿着这个思路，作者从图信息瓶颈( GIB )原理中推导出 图随机注意(GSAT) 。 GSAT 对输入图进行编码，从后验分布中随机抽取一个子图(解释)。它基于采样的子图进行预测。作为一个优势， GSAT 不需要限制采样子图的大小。

来源:苗等人

实验上， GSAT 在解释和预测性能方面都比事后方法好得多。它也可以与预训练的 GNN 模型相结合。如果您正在为您的应用程序构建可解释的 gnn，GSAT 应该是一个不错的选择。

图形扩充:超越边缘丢失

今年带来了一些关于改进 gnn 的自我监督能力的工作，这些工作超越了像节点/边丢失这样的随机边索引扰动。

韩等人将 2017 年以来用于图像增强的混合的思想带到了带有g-mix的图中(ICML 2022 优秀论文奖🏅).混合的想法是拍摄两幅图像，将它们的特征混合在一起，并将它们的标签混合在一起(根据预定义的加权因子)，并要求模型预测这个标签。这种混合提高了分类器的鲁棒性和泛化质量。

但是我们如何混合两个通常可能有不同数量的节点和边的图呢？

作者找到了优雅的答案——让我们不要混合图表，而是混合他们的图表——简而言之，就是图表生成器。来自同一个生成器的图具有相同的底层 graphon。因此算法变得相当简单(见下图)——对于一对图，我们 1️⃣估计它们的图；2️⃣通过加权求和将两个文法混合成一个新文法；3️⃣从新 graphon 和它的新标号中抽取一个图样本；4️⃣把这个送到分类器。在说明性示例中，我们有两个分别具有 2 个和 8 个连通分量的图，并且在混合它们的图之后，我们得到两个主要社区的新图，每个主要社区具有 4 个次要社区。估计图可以用一个阶跃函数和几种计算复杂度不同的方法来完成(作者大多求助于【最大间隙】)。

实验上， G-Mixup 稳定了模型训练，表现得比传统的节点/边扰动方法更好或相当，但是在具有标签噪声或许多添加/移除的边的鲁棒性场景中远远超过它们。一种众所周知的扩充方法对图形的冷静适应👏！如果你感兴趣，ICML 22 提供了一些关于混合的更一般的作品:一项关于混合如何改进校准的研究和如何在生成模型中使用它们的研究。

G-Mixup。来源:韩等

刘等人从另一个角度来看增强技术，特别是在节点的邻域很小的情况下。 局部增强 GNNs (LA-GNN) 的思想是训练一个生成模型，为每个节点产生一个附加的特征向量。生成模型是(在整个图形上)训练的条件 VAE，以预测以中心节点为条件的相连邻居的特征。也就是说，一旦 CVAE 被训练，我们只需传递每个节点的一个特征向量，并获得另一个特征向量，该特征向量应该比普通邻居捕获更多的信息。

然后，我们将每个节点的两个特征向量连接起来，并将其发送给任何下游的 GNN 和任务。注意，CVAE 是预先训练过的，不需要用 GNN 训练。有趣的是，CVAE 可以为看不见的图形生成特征，即，局部增强也可以用于归纳任务！最初的假设通过实验得到了证实——增强方法对于小角度的节点特别有效。

局部增强的想法。来源:刘等

下一步，于，王，王等人，处理 GNN 可扩展性任务，其中使用标准邻居采样器 a-la GraphSAGE 可能导致指数邻域大小扩展和陈旧的历史嵌入。作者提出了 GraphFM ，一种特征动量方法，其中历史节点嵌入通过动量步骤从它们的 1 跳邻居获得更新。通常，动量更新经常出现在 SSL 方法中，如用于更新目标网络的模型参数的 BYOL 和 BGRL 。这里，GraphFM 使用动量来减轻不同小批量中历史再现的方差，并为不同大小的邻域提供特征更新的无偏估计。

一般来说，GraphFM 有两种选择graph FM-in batch和graph FM-out of batchT21。(1) GraphFM-InBatch 通过大幅减少必要邻居的数量来实现 GraphSAGE 风格的邻居采样，而 GraphSAGE 需要 10–20 个邻居，具体取决于级别，GraphFM 只需要每层每个节点 1 个随机邻居。唯一👌！(2) GraphFM Out-of-batch 构建在 GNNAutoScale 之上，我们首先应用图分割将图分割成 k 个小批。****

从实验上看，特征动量看起来对 SAGE 风格的采样(批量版本)特别有用——对于所有基于邻居采样的方法来说，这似乎是一个很好的默认选择！

与 GNNAutoScale (GAS) 相比，历史节点状态也根据新的嵌入和特征动量(移动平均)进行更新。来源:【于，王，王，等

最后，赵等人提出了一个巧妙的基于反事实链接的链接预测增强技巧。本质上，作者问:

“如果图形结构变得与观察不同，这种联系还会存在吗？”

这意味着我们想找到链接，在结构上类似于根据一些给定的链接💊处理(这里，那些是经典的度量标准，如 SBM 聚类、k-core 分解、Louvain 等等)但是给出了相反的结果。通过 CFLP ，作者假设训练 GNN 正确预测真实和反事实的联系有助于模型摆脱虚假的相关性，并只捕捉对推断两个节点之间的联系有意义的特征。

在获得一组反事实链路之后(基于所选的处理函数的预处理步骤) CFLP 首先在事实链路和反事实链路上被训练，然后链路预测解码器利用一些平衡和正则化项被微调。从某种意义上来说，这种方法类似于挖掘硬性否定来增加真实肯定联系的集合🤔实验上， CFLP 与 GNN 编码器配对大大优于单个 GNN 编码器在 Cora/Citeseer/Pubmed 上的结果，并且仍然在 OGB-DDI 链接预测任务的 top-3 中！

反事实链接(右)。来源:赵等人

算法推理和图形算法

🎆算法推理社区的一个巨大里程碑——CLRS 基准测试 的出现 (以一本经典教科书命名，由 Cormen、Leiserson、Rivest 和 Stein 编写，Velič ković等人编写！现在，没有必要发明玩具评估任务——CLRS 包含 30 种经典算法(排序、搜索、MST、最短路径、图形、动态规划等等),将一个 ICPC 数据生成器转换成一个 ML 数据集😎。

在 CLRS 中，每个数据集元素是一个轨迹，即输入、输出和中间步骤的集合。底层的表示格式是一组节点(通常不是一个图，因为边可能不是必需的)，例如，对 5 个元素的列表进行排序被构造为对一组 5 个节点的操作。轨迹由探测器组成——格式元组(阶段、位置、类型、值)，用其状态编码算法的当前执行步骤。输出解码器取决于预期的类型—在示例图中👇排序是用指针建模的。

分开来看，训练和验证轨迹具有 16 个节点(例如，长度为 16 的排序列表)，但是测试集在具有 64 个节点的任务上探测模型的分布外(OOD)能力。有趣的是，普通 GNNs 和 MPNNs 非常适合训练数据，但在 OOD 设置中表现不佳，其中指针图网络显示更好的数字。这是 GNNs 无法推广到更大的推理图的观察集合的又一个数据点——如何解决这个问题仍然是一个开放的问题🤔。代码已经可用并且可以用更多的定制算法任务来扩展。

clr 中提示的表示。来源:veli kovi 等人

➡️从更理论的角度来看， Sanmartín 等人通过代数路径问题 (APP)概括了图度量的概念。APP 是一个更高级的框架(在范畴理论中有的一些根源)，它通过半环的概念统一了许多现有的图形度量，如最短路径、通勤成本距离和极大极小距离，半环是具有特定运算符和属性的集合上的代数结构。例如，最短路径可以描述为一个半环，带有" min “和” + “带有中性元素的运算符” +inf “和” 0 "。

在这里，作者创建了一个单一的应用程序框架对数范数距离**，允许仅使用两个参数在最短路径、通勤成本和 minimax 之间进行插值。本质上，您可以改变和混合边权重和周围图结构(其他路径)对最终距离的影响。虽然没有实验，但这是一个坚实的理论贡献——如果你在“吃你的蔬菜”时学习范畴理论🥦，这篇论文非常值得一读——并且肯定会在 GNNs 中找到应用。👏**

对数范数距离。来源:桑马丁等人

➡️:最后，我们将在这一类别中添加一部作品https://arxiv.org/pdf/2206.08119.pdf*，作者是罗西等人**，他们将图论与博弈论结合在一起。博弈论在经济学和其他多学科研究中被大量使用，你可能听说过定义非合作博弈解决方案的纳什均衡。在这项工作中，作者考虑了 3 种游戏类型:线性二次型、线性影响和巴里克-奥诺里奥图形游戏。游戏通常是通过他们的效用函数来定义的，但是在这篇文章中，我们假设我们对游戏的效用函数一无所知。***

游戏被定义为采取特定行动的 n 个玩家(图中的节点)(为了简单起见，假设我们可以用某个数字特征来描述它，查看🖼️).下面的插图行动可以影响邻近的玩家——这个任务的框架是根据玩家的行动推断他们的图形。本质上，这是一个图生成任务——给定节点特征 X，预测 a(归一化)邻接矩阵 a，通常一个游戏玩 K 次，那些是独立游戏，所以编码器模型应该对游戏的排列不变(对每个游戏中节点的排列等变)。作者提出了金块🍗编码器-解码器模型，其中变换器编码器通过 N 个玩家处理 K 个游戏，产生潜在的表示，并且解码器是潜在的成对玩家特征的哈达玛乘积之和上的 MLP，使得解码器对于 K 个游戏的顺序是置换不变的。

实验表明，该模型在合成数据集和真实数据集上都运行良好。这篇论文绝对是“开阔你的眼界”🔭你可能没想到会在 ICML 看到这些作品，但后来会发现这是一种引人入胜的阅读，并学到了许多新概念👏。

来源:罗西等人

知识图推理

知识图推理一直是 GraphML 方法的乐园。在今年的《ICML》上，有不少关于这个话题的有趣论文。作为今年的一个趋势，我们看到从嵌入方法( TransE 、 ComplEx 、 RotatE 、 HAKE )到 GNNs 和逻辑规则(其实 GNNs 也是和逻辑规则相关)的一个显著漂移。有四篇论文基于 GNNs 或逻辑规则，两篇论文扩展了传统的嵌入方法。

先从颜等人提出的 循环基 GNN (CBGNN) 说起。作者在逻辑规则和循环之间画了一个有趣的联系。对于任何一个链式逻辑规则，逻辑规则的头和体在知识图中总是形成一个循环。例如，下图的右图显示了(X, part of Y) ∧ (X, lives in, Z) → (Y, located in Z)的周期。换句话说，逻辑规则的推理可以被视为预测循环的合理性，这归结为学习循环的表示。

蓝色和红色三角形是更大的绿色循环中的循环。来源:颜等人

一个有趣的观察是，循环在模 2 加法和乘法下形成一个线性空间。在上面的例子中，红色❤️和蓝色的总和💙自行车，抵消了他们的共同优势，导致绿色💚循环。因此，我们不需要学习所有圈的表示，而是只需要学习线性空间的几个圈基**。作者通过挑选与最短路径树有很大重叠的环来生成环基。为了学习循环的表示，他们创建了一个循环图，其中每个节点都是原始图中的一个循环，每个边都表示两个循环之间的重叠。应用 GNN 来学习循环图中的节点(原始图的循环)表示。**

CBGNN 编码。来源:严等

为了将 CBGNN 应用于归纳关系预测，作者通过用 LSTM 对循环中的关系进行编码来为每个循环构建归纳输入表示。实验上，CBGNN 在 FB15k-237/WN18RR/NELL-995 的感应版本上实现了 SotA 结果。

接下来， Das 和 godbole 等人提出了用于 KBQA 的基于案例推理(CBR)方法 CBR-SUBG 。核心思想是在解决查询时从训练集中检索相似的查询-答案对。我们知道检索的想法在 OpenQA 任务中很流行( EMDR 、 RAG 、 KELM 、提内存 LMs )，但这是第一次看到这样的想法在图上被采用。

给定一个自然语言查询，CBR 首先基于由预先训练的语言模型编码的查询表示检索相似的 k-最近邻(kNN)查询。所有检索到的查询都来自训练集，因此它们的答案是可访问的。然后，我们为每个查询-答案对生成一个局部子图，它被认为是答案的推理模式(尽管不一定是精确的)。当前查询的局部子图(我们无法访问其答案)是通过遵循其 kNN 查询的子图中的关系路径来生成的。 CBR-SUBG 然后对每个子图应用 GNN，并通过将节点表示与 KNN 查询中的答案进行比较来预测答案。

基于案例的推理直觉。来源: Das 和 Godbole 等人

➡️今年有两种神经符号推理方法。第一个是 层次规则归纳(HRI) 出自 Glanois 等人。HRI 扩展了以前的一个工作，逻辑规则归纳(LRI) 关于归纳逻辑编程。规则归纳的想法是学习一堆规则，并应用它们来推断事实，如正向链接。

在 LRI 和 HRI 中，每个事实P(s,o)都由一个嵌入 𝜃p 的谓词和一个赋值vp(即事实为真的概率)来表示。每个规则P(X,Y) ← P1(X,Z) ∧ P2(Z,Y)都由其谓词的嵌入来表示。目标是迭代地应用规则来推导新的事实。在每次迭代过程中，通过软统一来匹配规则和事实，软统一衡量两个事实是否满足嵌入空间中的某些规则。一旦选择了一个规则，就会生成一个新的事实并将其添加到事实集中。所有嵌入和软统一操作被端到端地训练，以最大化观察到的事实的可能性。

HRI 模型在三个方面比 LRI 模型有所改进:1)使用分层的先验知识，将每个迭代步骤中使用的规则分开。2)使用 gumbel-softmax 来归纳用于软统一的稀疏且可解释的解决方案。3)证明 HRI 能够表达的逻辑规则集。

分层规则归纳。来源: Glanois 等人

第二篇是朱等人的 GNN-QE 论文(免责声明:本文作者的论文)。GNN-QE 用广义神经网络和模糊集解决知识图上复杂的逻辑查询。它兼具神经方法(例如强大的性能)和符号方法(例如可解释性)的优点。因为在 GNN-QE 有很多有趣的东西，我们很快会有一个单独的博客帖子。敬请期待！🤗

最后， Kamigaito 和 Hayashi 研究了负抽样在知识图嵌入中的理论和实证效果。从旋转开始，知识图嵌入方法使用一个归一化的负采样损失，加上一个边际二进制交叉熵损失。这不同于原来 word2vec 中使用的负采样。在本文中，作者证明了基于距离的模型(trans， RotatE )要达到最优解，归一化负采样损失是必要的。边距在基于距离的模型中也起着重要的作用。只有当 𝛾 ≥ log|V| 时，才能达到最优解**，这与经验结果一致。基于这个结论，现在我们可以确定最佳的保证金没有超参数调整！😄**

计算生物学:分子连接，蛋白质结合，性质预测

总的来说，comp bio 在 ICML 表现很好。在这里，我们将看看分子连接**、蛋白质结合、构象异构体生成和分子性质预测的新方法。**

分子连接**是设计蛋白水解靶向嵌合体(PROTAC) 药物的关键部分。对我们来说，仅仅是 GNN 的研究者🤓在没有生物学背景的情况下，这意味着给定两个分子，我们想要生成一个有效的接头分子，它将两个片段分子连接在一个分子中，同时保留原始片段分子的所有属性(查看下面的插图以获得一个很好的示例)**

为了生成分子链，黄等人创造了 3DLinker ，这是一个 e(3)-等变生成模型(VAE)，它以绝对坐标顺序生成原子(和连接键)。通常，等变模型会生成相对坐标或相对距离矩阵，但在这里，作者旨在生成绝对 (x，y，z) 坐标。为了允许模型从等变(到坐标)和不变(到节点特征)变换中生成精确的坐标，作者应用了一个巧妙的向量神经元的想法，它本质上是一个类似 ReLU 的非线性，通过巧妙的正交投影技巧来保持特征等变。

富含向量神经元的 e(3)-等变编码器对特征和坐标进行编码，而解码器以 3 个步骤顺序地生成链接(也在下面示出):1️⃣预测链接将被附加到的锚节点；2️⃣预测链接器节点节点类型；3️⃣预测边缘及其绝对坐标；4️⃣重复，直到我们在第二个片段中到达停止节点。 3DLinker 是(到目前为止)第一个生成具有精确 3D 坐标的连接分子并预测片段分子中锚点的等变模型——以前的模型在生成之前需要已知锚点——并显示最佳实验结果。

3d 链接器直觉。来源:黄等

➡️ 蛋白质-配体结合是另一项至关重要的药物发现任务——预测一个小分子可能在哪里附着到一个更大蛋白质的某个区域。先是，史塔克，加内亚等人创作 对等 (ICML 聚焦💡)以蛋白质和配体图的随机 RDKit 构象作为输入，并输出结合相互作用的精确 3D 位置。EquiBind 已经在麻省理工学院新闻和阅读小组中获得了非常热烈的欢迎和宣传，因此我们鼓励您详细了解技术细节！ EquiBind 比商业软件快几个数量级，同时保持较高的预测精度。

EquiBind。资料来源:斯特尔克、加内亚等人

如果结合分子是未知的，并且我们想要生成这样的分子，刘等人创建了 GraphBP ，这是一种自回归分子生成方法，其将目标蛋白质位点(表示为初始上下文)作为输入。使用任何 3D GNN 对上下文进行编码(此处为 SchNet ，GraphBP 生成原子类型和球坐标，直到不再有接触原子可用或达到所需的原子数量。一旦原子生成，作者就求助于开放巴别塔来创造化学键。

用 GraphBP 生成结合分子。来源:刘等

在分子性质预测中，** 于和高提出了一个简单而惊人强大的想法，用一包基序来丰富分子表征。也就是说，他们首先在训练数据集中挖掘出一个模体词汇表，并根据 TF-IDF 分数对它们进行排序(你好，来自 NLP😉).然后，每个分子可以被表示为一个模体包(多热编码),并且整个分子数据集被转换为一个具有关系“模体-分子”(如果任何分子包含该模体)和“模体-模体”(如果任何两个模体在任何分子中共享一条边)的异质图。边缘特征是之前挖掘的那些 TF-IDF 得分。**

分子的最终嵌入是通过分子上的任何香草 GNN 和来自基序图的采样子图上的另一个异质 GNN 的串联获得的。这样一个 异构基元 GNN (HM-GNN) 始终优于图子结构网络(GSN) ，这是最早提出在社交网络中计算三角形和在分子中计算 k-循环的 GNN 架构之一，甚至优于细胞同构网络(CIN) ，这是一个顶级的高阶消息传递模型。HM-GNNs 可以作为高阶 GNNs 领域的后续研究的简单有力的基线💪。

在 HM-GNN 建立主题词汇。来源:于、高

➡️最后，strk 等人的一项工作展示了使用 3D Infomax 方法对 2D 分子图及其 3D 构象图进行预训练的好处。 3D Infomax 的想法是最大化 2D 和 3D 表示之间的互信息，使得在 2D 图上的推断时间，当没有给出 3D 结构时，模型仍然可以受益于 3D 结构的隐含知识。

为此，2D 分子用主邻域聚集(PNA) 网编码，3D 构象异构体用球形信息传递(SMP) 网编码，我们取它们表示的余弦相似性，并通过对比损失使一个分子与其真实 3D 构象异构体的相似性最大化，并将其他样品视为阴性。有了预训练的 2D 和 3D 网络，我们可以在下游任务中微调 2D 网络的权重——在这种情况下是 QM9 属性预测——结果明确显示预训练有效。顺便说一句，如果你对预训练进一步感兴趣，可以看看 ICLR 2022 上发布的 GraphMVP 作为另一种 2D/3D 预训练方法。

在 3D Informax 中，我们首先预训练 2D 和 3D 网络，并在推理时使用经过训练的 2D 网络。资料来源:strk 等人

酷图应用

GNNs 极大地推动了物理模拟和分子动力学的发展。物理模拟的标准设置是一个粒子系统，其中节点特征是几个最近的速度，边缘特征是相对位移，任务是预测粒子在下一个时间步移动到哪里。

**⚛️今年， Rubanova，Sanchez-Gonzalez 等人通过在 C-GNS **(基于约束的图网络模拟器)中加入明确的标量约束，进一步改进了物理模拟。从概念上讲，MPNN 编码器的输出通过解算器进一步细化，该解算器最小化一些学习到的(或在推理时指定的)约束。求解器本身是一个可微分函数(在这种情况下是 5 次迭代梯度下降),因此我们也可以通过求解器进行反向投影。C-GNS 与深层隐含层有着内在的联系，这些深层隐含层的可见性越来越强，包括GNN 应用。

物理模拟作品通常是花哨的模拟可视化的来源——查看带有视频演示的网站！

基于约束的图形网络模拟器。来源:鲁巴诺瓦、桑切斯-冈萨雷斯等人

您可能想看看其他一些很酷的应用程序:

• 交通预测 : 兰、马等创建了【DSTA-GNN】(动态时空感知图神经网络)用于交通预测🚥在繁忙的加州道路的真实世界数据集上进行评估——去年，在谷歌和 DeepMind 对改进谷歌地图 ETA 进行大量工作后，用图表预测交通得到了推动，我们在 2021 年的结果中报道了这些工作。
• 神经网络剪枝 : 于等设计【GNN-RL】在给定期望的 FLOPs 缩减率的情况下，迭代地剪枝深度神经网络的权重。为此，作者将神经网络的计算图视为块的分层图，并将其发送到分层 GNN(通过中间可学习池来粗粒度化 NN 架构)。编码的表示被发送到 RL 代理，该代理决定删除哪个块。
• 排名 : 何等人处理一个有趣的任务——给定一个两两互动的矩阵，例如，在足球联赛中的球队之间，其中 Aij > 0 表示球队 i 比球队 j 得分更高，找出得分最高的节点(球队)的最终排名。换句话说，我们希望在看到所有比赛的配对结果后，预测谁是联赛的冠军。作者提出 GNNRank 将成对结果表示为有向图，并应用有向 GNN 来获得潜在节点状态，并计算图拉普拉斯的费德勒向量。然后，他们将该任务设计为一个约束优化问题，具有近似梯度步骤，因为我们无法通过费德勒向量的计算轻松地反向推进。**

这就是 ICML 2022 的最终目标！😅

期待看到 NeurIPS 2022 论文以及全新 图学(LoG) 会议的投稿！

使用 Python 的图机器学习第 3 部分:无监督学习

原文：https://towardsdatascience.com/graph-machine-learning-with-python-part-3-unsupervised-learning-aa2854fe0ff2

大都会艺术博物馆中绘画的聚类和嵌入

大都会艺术博物馆的绘画网络。作者图片

在第 1 部分中，我介绍了我们如何从图中推理，为什么它们如此有用，用于分析和浓缩大量信息的度量标准，等等。

在第 2 部分中，我查看了 CryptoPunks 交易网络，介绍了更高级别的图形推理——随机世界和扩散模型。

然后我稍微离题讨论了我们如何使用网络和图表分析来看待 NBA 比赛。这一部分将使用那个故事中介绍的概念来进一步分析图形机器学习。

https://animadurkar.medium.com/network-analysis-of-nba-playoffs-via-flow-dynamics-e5d5de70d4af

我强烈建议在深入研究这一部分之前先回顾一下前面的部分，因为它们为这一部分做了很好的准备，我在这里不深入研究的许多概念已经在每一部分中讨论和展示了。

在这个故事中，我将分析一个不同于我以前故事中看到的数据集。我会看一看被归类为绘画的大都会艺术博物馆的艺术品。这个数据集可以在 Github 上找到:https://github.com/metmuseum/openaccess

来自他们的 GitHub 数据集:

大都会艺术博物馆展示了来自世界各地超过 5000 年的艺术，供每个人体验和欣赏。该博物馆位于纽约市的两个标志性建筑——大都会第五大道和大都会修道院。数百万人也在线参加了大都会博物馆的体验活动。

自 1870 年成立以来，大都会博物馆一直渴望不仅仅是一个珍奇美丽物品的宝库。每一天，艺术都在博物馆的画廊里，通过展览和活动变得生动起来，揭示了新的思想和跨时间、跨文化的意想不到的联系。

大都会艺术博物馆为其收藏的超过 470，000 件艺术品提供精选的数据集，用于无限制的商业和非商业用途。在法律允许的范围内，大都会艺术博物馆已经放弃使用 Creative Commons Zero 对该数据集的所有版权和相关或邻接权。该作品发表于:美利坚合众国。你也可以在这个资源库的许可文件中找到 CC Zero 契约的文本。这些精选的数据集现在可以在任何媒体上免费使用；它们还包括受版权保护的艺术品的识别数据。数据集支持对博物馆藏品的搜索、使用和交互。

目录

1. 简介和网络拓扑
2. 图的无监督嵌入
3. 节点表示学习(Node2Vec)
4. 边的表示学习(Edge2Vec)
5. 图的表示学习(Graph2Vec)
6. 摘要

简介和网络拓扑

在任何类型的数据项目之前，从一些探索性的数据分析开始总是好的。除此之外，通过可视化网络拓扑，我们可以很好地了解我们正在处理的数据类型。

作者图片

数据似乎有相当多的空值，而且 450，000 行数据在图形中编码和操作(在我的本地机器上)需要很长时间。为了简单一点，我只筛选出“画”这一类的作品。

Prints                                  69260
Prints|Ephemera                         30033
Photographs                             26821
Drawings                                25230
Books                                   14685
Ceramics                                13332
Paintings                               11038
Textiles-Woven                          10995
Photographs|Ephemera                    10940
Glass                                    8838
Negatives                                6460
Vases                                    5050
Textiles-Laces                           4966
Prints|Ornament & Architecture           4554
Sculpture                                4487
Ceramics-Porcelain                       4104
Textiles-Embroidered                     4093
Metalwork-Silver                         3969
Drawings|Ornament & Architecture         3910
Books|Prints|Ornament & Architecture     3583
Name: Classification, dtype: int64

为了处理未知数，如果一个字段丢失了，那么我们将使用“unknown_{column_name}”来估算 NaNs，这可能是非常有趣的。再做一点清理，我们就可以选择一些字段，这些字段为我们的图表填充了大量的值。

作者图片

Top 10 for Culture
Culture
unknown_Culture                 6591
China                           2059
Japan                           1173
India (Gujarat)                  200
American                         107
Tibet                             81
Nepal (Kathmandu Valley)          65
India (Bengal) or Bangladesh      63
Korea                             52
India                             32
dtype: int64

Top 10 for Period
Period
unknown_Period                                  8599
Edo period (1615–1868)                           701
Qing dynasty (1644–1911)                         466
Ming dynasty (1368–1644)                         212
Meiji period (1868–1912)                         151
Muromachi period (1392–1573)                      90
Pala period                                       89
Ming (1368–1644) or Qing dynasty (1644–1911)      86
Ming (1368–1644) or Qing (1644–1911) dynasty      78
Yuan dynasty (1271–1368)                          54
dtype: int64

Top 10 for Artist Display Name
Artist Display Name
unknown_Artist Display Name       1104
Unidentified Artist                373
Xie Zhiliu                         344
John Singer Sargent                115
Fu Baoshi                          101
Marsden Hartley                     87
Shibata Zeshin                      74
Kerry James Marshall                72
Bhadrabahu                          71
Élisabeth Louise Vigée Le Brun      69
dtype: int64

Top 10 for Medium
Medium
Oil on canvas                                3592
Watercolor on ivory                           632
Oil on wood                                   576
Hanging scroll; ink and color on paper        434
Hanging scroll; ink and color on silk         374
Hanging scroll; ink on paper                  249
Ink, opaque watercolor, and gold on paper     226
Tempera on wood, gold ground                  155
Album leaf; ink and color on silk             136
Ink and opaque watercolor on paper            129
dtype: int64

Top 10 for Object Name
Object Name
Painting                                5808
Hanging scroll                          1362
Painting, miniature                      693
unknown_Object Name                      641
Folio                                    462
Handscroll                               297
Drawing                                  283
Album leaf                               278
Folding fan mounted as an album leaf     172
Album                                    104
dtype: int64

正如所料，我们可以看到有很多值是未知的或者很难准确计算出来的。此外，我们还看到了奇怪的分类碎片(例如“明朝(1368–1644)”、“清朝(1644–1911)”、“明朝(1368–1644)或清朝(1644–1911)”、明朝(1368–1644)或清朝(1644–1911)朝代”)。没有领域专家，可能很难知道为什么或如何发生这种情况，以及值是否应该被组合、删除、重新标记或保持不变，所以现在我将把它们留在这里。这些也只是在这几个类别的前 10 个值中看到的，所以人们只能想象这些类别在更低的级别上变得多么支离破碎，更难辨别。

在我们的图表中，我们需要转换这些列来创建 From 和 to 格式。有几种不同的方法可以做到这一点，数据的上下文可以决定处理这一点的最佳途径。我们将创建一个类似如下的无向图:

作者图片

作者图片

虽然这仍然是一个很大的图，但是让我们来看看拓扑是什么。

Graph Summary:
Number of nodes : 12688
Number of edges : 66693
Maximum degree : 9092
Minimum degree : 2
Average degree : 10.512767969735183
Median degree : 6.0

Graph Connectivity
Connected Components : 1

Graph Distance
Average Distance : 2.500517379796479
Diameter : 6

Graph Clustering
Transitivity : 0.0015246604242919772
Average Clustering Coefficient : 0.5194453022433385

相当低的传递性是有意义的，因为这不是一个社会图，没有理由相信三元闭包会在这里成立。除此之外，只有 1 个连通分量是一个有趣的度量，因为我们不应该有很多只连通而没有其他的子图。节点和边的数量表明有大量的小众类别、艺术家、风格等。在图表中创造了进一步的分割。

如果我能接触到领域专家，我可能会通过一个广泛的练习来清理类别，因为它们中的一些可能会有潜在的重叠，但现在，我们将继续。

作者图片

该图的节点颜色由度中心性编码，边颜色由 Jaccard 相似性编码(我将在本系列的监督学习部分讨论链接预测时讨论链接度量)。有趣的是，在这个图中有一些节点完全支配着其他节点。当我们按流中心性排序时(中间中心性的一种变体，用于度量进入过程之间的实体)，我们发现许多“未知”或 NaN 字段占主导地位。

作者图片

对中心性度量的进一步分析也证实了有少数节点强烈地扭曲了分布。一种解决方案是简单地删除具有任何这些 nan 的行，但是某些数据点丢失的事实对于在低维空间中嵌入该节点可能是非常重要的信息。

作者图片

图的无监督嵌入

图的无监督机器学习主要可以分为以下几类:矩阵分解、跳跃图、自动编码器和图神经网络。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)有一个奇妙的图像，概述了这些和每个下面的算法:

本书中描述的不同无监督嵌入算法的层次结构。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)，O’Reilly

尽管我将简要介绍嵌入及其工作原理，但我不会在本文中介绍自动编码器和图形神经网络。自动编码器和 gnn 应该有自己的故事(提示提示)，所以我将只关注我发现性能最好的主要无监督算法——跳格算法。

与大多数结构化数据不同，图是在非欧几里得空间中定义的。具有讽刺意味的是，它们没有空间成分；一个节点的相关性仅在于它是否与其他节点相连，而与该节点在图中的位置或方向无关。由于这个原因，我们经常把一个图简化成一个结构化的数据问题来简化它。我们通过创建图的邻接矩阵并学习矩阵中成对关系的嵌入来做到这一点。这些学习到的表示允许我们在节点、边和图形之间的潜在关系中发现隐藏的和复杂的新模式。

邻接矩阵看起来像这样:

无向标号图及其邻接矩阵。维基百科

每行和每列代表每个节点，数字代表节点之间的链接数量。该邻接矩阵可以被学习为用于降维、聚类和进一步的下游预测任务的嵌入。这里的目标是对节点进行编码，使得嵌入空间中的相似性近似于图中的相似性。

每种矩阵分解方法都使用这种分解技术来创建节点和边缘级数据的嵌入。根据谷歌的说法，“嵌入是一个相对低维的空间，你可以将高维向量转换到其中。嵌入使得在大量输入上进行机器学习变得更加容易，比如表示单词的稀疏向量。理想情况下，嵌入通过在嵌入空间中将语义相似的输入放在一起来捕获输入的一些语义。嵌入可以被学习并跨模型重用。”

在浅层方法中，通过具有以下步骤的表示学习来学习节点嵌入:

1. 编码器将节点映射到嵌入
2. 定义节点相似度函数
3. 解码器将嵌入映射到相似性得分
4. 优化编码器的参数，使得解码的相似性尽可能接近地匹配基础网络相似性

Skip-gram 模型使用各种随机行走来优化相似性度量的嵌入。这些模型不使用标签或显式特征来估计节点的一组坐标，以便捕捉网络结构的某些方面。对于节点通过边连接的图，随机漫步有两个明显的好处:

1. 表现性:一种灵活的获取局部和全局节点邻域信息的方法。这源于这样的想法:如果从节点 u 开始的随机行走以高概率行进到节点 v，那么它们是相似的。
2. 效率:我们不想考虑网络中的每一条路径，因为这将很快变得难以计算。这种方法只考虑随机漫步中同时出现的配对。

生成随机行走路径后，我们现在有了序列数据，可以像处理文本一样生成嵌入。这就是跳格模型，特别是 Word2Vec，出现的原因。Skip-gram 模型通常被称为 Word2Vector，因为它是一个简单的神经网络，具有一个隐藏层叛逆者来预测当输入单词存在时给定单词存在的概率。它基于输入语料库建立训练数据，然后被训练来预测单词成为给定目标的上下文单词的概率。下图显示了第一步训练是如何进行的。

从给定语料库生成训练数据的示例。在填充的框中，目标单词。在虚线框中，由长度为 2 的窗口大小标识的上下文单词。图形机器学习(克劳迪奥·斯塔米尔，奥尔多·马尔祖洛，恩里科·德乌塞比奥)，奥莱利

然后，简单的神经网络根据该数据进行训练，以基于每个单词在训练语料库中的位置来生成每个单词的概率。这将输出一个嵌入，在一个低得多的维度空间中表示该单词。

跳跃图模型的神经网络结构。隐藏层中 d 个神经元的数目代表了嵌入空间的最终大小。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)，O’Reilly

对于图中的 skip-gram 模型，此图展示了随机游走如何连接到 skip-gram，然后生成嵌入的示例:

DeepWalk 算法用来生成给定图的节点嵌入的所有步骤。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)，O’Reilly

深度遍历跳过程序算法是这样的:

1. 从图上的每个节点开始，进行短距离固定长度(不一定都是相同长度)的随机行走。
2. 对于每个节点 u，收集在从 u 开始的随机行走中访问的节点的多重集，并在其上训练 skip-gram 模型。当给定图作为跳格模型的输入时，图可以被视为输入文本语料库，而图的单个节点可以被视为语料库的单词。随机漫步可以被看作是一个单词序列(一个句子)。在这一步中使用了跳格模型的参数(窗口大小， w ，以及嵌入大小， d )。
3. 使用随机梯度下降优化嵌入。给定节点 u ，我们想要预测它的邻居 N(u)。【Jure Lescovec 博士的图形机器学习课程中生动地描述了这里正在优化的损失函数:

Jure Lescovec，斯坦福， CS224W:带图的机器学习

该模型的常见参数有:

• walk_number:为每个节点生成的随机行走的次数
• walk_length:生成的随机漫步的长度
• window_size:跳格模型的窗口大小参数

虽然我相信这足够让这个故事继续下去了，但这里还有很多内容要讲。矩阵分解方法、负采样(以有效地近似损失函数最优化)等。仅举几个例子。如果您想深入了解，我强烈推荐这些资源:

图机器学习第三章:无监督学习

斯坦福 CS224W:带图的机器学习

节点表示学习(Node2Vec)

Node2Vec 是深度遍历模型的一种变体，在随机遍历的生成方式上有显著的不同。深度遍历在保存节点的局部邻域信息方面存在局限性，因此 Node2Vec 采用了宽度优先搜索(BFS)和深度优先搜索(DFS)的灵活而强大的组合来进行图探索。这两种算法的组合通过以下方式进行调整:

1. p :随机游走回到前一个节点的概率
2. q :随机漫步可以通过图中以前看不见的部分的概率。BFS 与 DFS 的比率。

该模型引入了有偏行走，可以在网络的局部微观(BFS)和全局宏观(DFS)视图之间进行权衡。

Node2Vec 算法是这样的:

1. 计算随机行走概率
2. 模拟从每个节点 u 开始的 r 长度 l 的随机行走
3. 使用随机梯度下降优化模型的目标

该模型的常见参数有:

• num_walks:为每个节点生成的随机行走的次数
• walk_length:生成的随机漫步的长度
• p，q:随机游走生成算法的参数 p 和 q

让我们用 2 维来绘制节点嵌入，并找到与文森特·梵高相似的艺术家，他是个人的最爱。

作者图片

#Artists similar to Vincent van Gogh
Adrien Dauzats
Anne Louis Girodet-Trioson
Eugène Isabey

上面的代码仅假设二维空间足以捕捉低维空间中的每个节点。通常，这在大型复杂的图表中是不够的，但是随着维度的增加，它可能很难可视化。另一点要注意的是，当模型评估相似性时，它仅基于节点中的信息(时期、文化、介质等)。)，所以艺术家相似性将仅与图中的节点邻近度/相似性相关。这与使用计算机视觉来分析艺术品的像素值以找到相似的图像截然不同。

尽管梵高是一位荷兰艺术家，但众所周知，他在法国找到了自己的标志性风格，并最终在法国去世。这三位艺术家都是法国人，但他们的主要风格是浪漫主义，与梵高的后印象派风格形成鲜明对比。

让我们添加更多的维度来让模型学习我们的图表的更好的表示。

#Artists similar to Vincent van Gogh
Paul Cézanne
Goya (Francisco de Goya y Lucientes)
Georges Rouault
Alfred Sisley
Georges Seurat
Claude Monet
Gustave Courbet
Edward McKnight Kauffer

这样其实好多了！这些艺术家在时代、文化和风格上更相似。请注意，我们还在图表中添加了媒介、部门和对象类型，因此可能这些艺术家中的一些人可能在该时期有所不同，但使用了与梵高相同的材料，或者出现在博物馆的同一部门。

以下是文森特·梵高和保罗·塞尚的作品供参考:

L’Arlésienne:约瑟夫-米歇尔·吉诺夫人(玛丽·朱利安，1848–1911)，文森特·梵高。大都会艺术博物馆(公共领域)

打牌的人，1890-1900，保罗·塞尚。大都会艺术博物馆(公共领域)

边的表示学习(Edge2Vec)

Edge2Vec 是 Node2Vec 相对简单的扩展，它使用两个相邻节点的节点嵌入来执行一些基本的数学运算，以便提取连接它们的边的嵌入。以下是图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)中阐述的主要问题:

Node2Vec 库中的边嵌入操作符及其方程和类名。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)，O’Reilly

根据数据的性质以及数据之间的关系，不同的嵌入会有不同的价值。一种有效的评估方法是尝试每一种方法，看看哪一种方法具有最合理的边缘分离。

虽然我们不能一下子看到所有的维度，但你可以通过下面的方法看到梵高和他的相似作品与艺术家之间边缘嵌入的前两个维度。

作者图片

图的表示学习(Graph2Vec)

这是节点和边表示学习的最高概括。在自然语言处理中，这种模型被称为 Doc2Vec，因为它是多个文档的嵌入，而不是单词或句子。当涉及到图时，我们可以将其划分为子图，然后训练模型来学习这些子图中每一个的表示作为嵌入。

Doc2Vec 模型的功能与 Node2Vec 相关，如下图所示:

Doc2Vec 跳跃图模型的简化图形表示。隐藏层中 d 个神经元的数目代表了嵌入空间的最终大小。图形机器学习(Claudio Stamile，Aldo Marzullo，Enrico Deusebio)，O’Reilly

这个算法是这样的:

1. 围绕每个节点生成一组有根子图。
2. 使用生成的子图训练 Doc2Vec 跳转图。
3. 使用包含在经训练的 Doc2Vec 模型的隐藏层中的信息，以便提取每个节点的嵌入。通过随机梯度下降进行优化。

生成子图的方式可以变化，并显著改变模型学习精确表示的能力。基本上，有三种不同的方法可以创建子图:

方法 1:嵌入节点并聚合它们(最常见的是求和或平均)

方法 2:创建一个节点(超级节点),它代表并跨越每个子图，然后嵌入该节点

方法 3:匿名行走嵌入。捕获与随机漫步中第一次访问节点的索引相对应的状态。被认为是匿名的，因为这种方法不知道被访问节点的身份。

Jure Lescovec，斯坦福， CS224W:带图的机器学习

使用方法 3，随着匿名遍历的数量呈指数级增长，您很容易遇到所需计算资源的问题。由于这种计算复杂性，我们可以:

• 对匿名遍历进行采样，然后将图形表示为每次匿名遍历发生次数的一部分
• 嵌入匿名遍历，连接它们的嵌入得到一个图嵌入。本质上，嵌入行走，以便可以预测下一次行走。

整个目标是将图形表示为这些行走的概率分布。

对于我们的例子，我们可以创建仅包含 Vincent van Gogh 和与他相似的艺术家的行的子图。我们可以使用嵌入以一种更加简洁和有效的方式来表示他们所有的信息。请注意，我们需要将节点标签转换为整数，以使模型更加合适，出于示例的原因，我们将只做二维处理。

作者图片

摘要

这个故事旨在说明即使在相对不干净、不完整和最少的数据上，表征学习的力量。在没有目标标签或基础真值的情况下，我们可以使用图表来真正有效地找到潜在的结构相似性。显然，像任何机器学习项目一样，在这个过程中，我们做了很多假设和警告，但图表给了我们一个额外的维度来分析我们的数据。

我们的模型可以[潜在地]变得更好的一些重要方式:

• 将数据帧中的行表示为不同的节点和边
• 在领域专家的监督下清理无关和不完整的值
• 添加更多维度，将艺术家与其作品和其他艺术家联系起来

这是一篇很长的文章，但是谢谢你坚持下来！在本系列的下一部分，我们将讨论监督学习。跟着一起玩吧！

参考

[1] Claudio Stamile，Aldo Marzullo，Enrico Deusebio，图机器学习

[2] Jure Leskovec，斯坦福， CS224W:带图的机器学习

[3]伊斯利，大卫和克莱因伯格，乔恩。2010.网络、人群和市场:关于高度互联世界的推理

[4] 大都会艺术博物馆开放存取

您可以在这里找到本系列的第 4 部分:

基于 Python 的图机器学习第 4 部分:监督和半监督学习

原文：https://towardsdatascience.com/graph-machine-learning-with-python-part-4-supervised-semi-supervised-learning-d66878161b79

大都会艺术博物馆绘画的分类和预测

大都会艺术博物馆的绘画网络。作者图片

介绍

这个故事将探索我们如何通过监督和半监督学习，使用标签从图形中推理和建模。我将使用 MET Art Collections 数据集，它将建立在我以前关于度量、无监督学习等部分的基础上。在这篇文章之前，请务必查看之前的文章，以便跟上一些片段，因为我不会在这篇文章中再次涵盖所有概念:

目录

1. 基于特征的方法
2. 嵌入方法
3. 集体分类
4. 摘要

基于特征的方法

进行监督学习的最简单方法是使用图测量作为新数据集中的要素，或者作为现有数据集中的附加要素。我已经看到这种方法对建模任务产生了积极的结果，但是它可能真的依赖于 1。你如何以图表的形式建模(输入、输出、边等是什么？)和 2。要使用哪些指标。

根据预测任务，我们可以计算节点级、边级和图级指标。这些度量可以作为关于实体本身及其与其他实体的关系的丰富信息。这可以看作是一个经典的监督 ML 任务，但这里的重点是特征选择。根据您的预测任务，您可以选择不同的图表度量来预测标签。

在我们的数据集中，我们将选择的标签是“突出显示”字段。标签的选择可以根据个人的目标而改变，但对于这个项目，我的假设是，有许多艺术作品值得突出显示(在公共领域展示)，但大部分都被隐藏了。让我们看看是否可以使用图表来创建模型，以帮助预测哪些其他艺术品应该突出显示。

0 10733 
1 305
Name: Highlight, dtype: int64

我们在这里看到了很大的阶级不平衡，这是有道理的，因为只有一些艺术品能够得到强调，通常博物馆在他们的档案中包含大量的收藏。

dataframe 仅包含各种图表指标，我们将使用这些指标作为预测“突出显示”的特征。

让我们对数据集进行随机过采样，然后预测我们的目标变量。

Accuracy 0.7889492753623188 
Precision 0.08961303462321792 
Recall 0.6984126984126984 
F1-score 0.15884476534296027

不是最好的结果，但我们只是使用了基本模型，所以我们可能会通过广泛的调整或功能工程使其性能更好，但这超出了本故事的范围。需要注意的一点是，我们希望针对我们的问题进行召回优化。在这种情况下，获得“相关的”结果比“精确的”结果更好，因此看到相对较高的召回分数是件好事(记住，我们只是使用了一些图表指标来做到这一点！).

最后，这是一个节点级别的预测任务，其中有问题的节点是一个艺术品。同样的概念也可以很容易地用于边缘或图形级(具有传统功能)任务，使其高度通用。

嵌入方法

基于浅层嵌入的监督学习方法与非监督学习的不同之处在于，它们试图找到节点、边或图形级预测任务的最佳解决方案。这方面的两个主要算法是:标签传播和标签扩散。

这两种方法属于半监督学习领域，因为图中只有几个标记节点。这里的主要假设是网络中存在同向性，这意味着相似的节点比不相似的节点更有可能相互连接。

图表至少增加了一个维度的建模和选择，使得您的假设对于验证非常重要。例如，在第 3 部分中，我特别选择了用一种特殊的方式来设计这个网络，但是它也可以很容易地用不同的方式来制作。我选择的方法是为艺术品的每个属性创建节点，而不是将其嵌入到艺术品节点中。

作者图片

这可能仍然适用于我们的用例(即相似时期或文化中的艺术作品自然会比其他作品更紧密地联系在一起)，但是这些是你应该和建模假设一起重新评估的选择类型。

标签传播

该算法将节点的标签传播到它的邻居(节点),这些邻居具有从该节点到达的最高概率。

sklearn 已经为我们实现了这个算法，使用两个主要的内核:kNN 和 rbf。我们可以控制 gamma 和 n_neighbors 等参数，以控制模型在标记节点周围扫描的“距离”。

对于我们的用例，从技术上来说，我们只有一个标签(1 代表“突出显示”)，我们还有大量连接到节点的艺术品，如第 3 部分中看到的“未知时期”或“未知文化”(这些节点具有高中心性度量)。这基本上意味着我们的大多数模型配置将只输出“Highlight ”,以传播给几乎所有的节点，表明所有的艺术品都应该被突出显示。虽然这没有什么错，但是从模型的角度来看，它并没有给我们提供太多的价值——我们可以直接说出来，然后就完成了。

Highlight     Is Public Domain 
No Highlight  True                6567               
              False               4166 
Highlight     True                 235               
              False                 70
dtype: int64

我们首先需要做的是创建一个启发，允许我们控制什么是真正被突出显示的“合格的”。在我们的数据集中，只有大约 300 件艺术品被突出显示，其中超过 75%的作品属于公共领域。我们可以给没有突出显示和不在公共域中的节点加 0，表示它们“没有资格”被突出显示。在给定数据和领域的情况下，这可以很容易地更改为任何有意义的启发式规则。

-1    6567  
0     4166  
1     305 
Name: Highlight, dtype: int64

请注意，该模型需要未标记的节点具有-1 值。

您可以使用 predict_proba()方法提取每个类的模型概率，然后在模型拟合后使用 transduction_ after 将标签归属于行。

array([[4.46560147e-17, 1.00000000e+00],        
      [4.46560147e-17, 1.00000000e+00],        
      [4.89043690e-17, 1.00000000e+00],        
      ...,        
      [1.00000000e+00, 4.60058884e-51],        
      [1.00000000e+00, 1.50981524e-52],        
      [1.00000000e+00, 1.07327710e-50]])

0    6300 
1    4738 
dtype: int64

我们现在有超过 4000 件艺术品可以考虑在博物馆中重点展示！还应该进行模型评估，可以调整一些参数(gamma 或 n_neighbors)以确保“良好”的分割，但这是一项相当主观的任务，因此由领域专家进行基于任务的评估可能是最佳的评估策略。

从数学上讲，该算法使用一个转移矩阵乘以某个时间步长上每个节点的类值矩阵。如此迭代多次，直至收敛。

让我们来看看一些符号以及矩阵是如何组合在一起的。Stamile 等人的图形机器学习。艾尔。如果你想了解更多细节，我会解释得很清楚。

图的邻接矩阵

图的对角度矩阵

表示每个节点遍历到另一个节点的概率的转移矩阵

时间 t 时班级分配的概率矩阵

标签扩散

标签传播算法解决了标签传播算法的一个关键功能/限制:节点到类的初始标签。标签传播假设最初在数据集中提供的标签是真实的，并且它们不能在训练期间改变。标签扩散放松了这种约束，并允许在训练期间重新标记最初被标记的节点。

为什么？如果在最初标记的节点中存在一些误差或偏差，这可能是非常有益的；初始标记时出现的任何错误都会传播开来，仅通过指标很难发现这一点。

array([[1.00000000e+00, 2.14018170e-10],        
      [1.00000000e+00, 2.05692171e-10],        
      [1.00000000e+00, 2.13458111e-10],        
      ...,        
      [1.00000000e+00, 4.27035952e-18],        
      [1.00000000e+00, 3.85172946e-28],        
      [1.00000000e+00, 1.33374342e-32]])

0    6127 
1    4911 
dtype: int64

尽管表面上看起来非常相似，但由于概率的不同，这可能会产生非常不同的结果。标签扩散算法不是计算转移矩阵，而是计算归一化的图拉普拉斯矩阵，该矩阵类似于转移矩阵，可以被视为图的节点和边的低维表示。

归一化图拉普拉斯矩阵

使用 alpha 的概率矩阵，alpha 是一个正则化参数，用于调整原始解对每次迭代的影响程度

集体分类

图的强大之处在于使用了同向性、影响力等关键概念，通过连接提取模式。同质性指的是节点与它们相似的其他节点相关联的趋势，而影响力指的是社会联系影响个人/节点的个体特征的能力。这两种影响都可以在图表中捕捉到，我们可以利用这些作为假设来执行真正强大的监督和半监督 ML 任务。

我在上面讨论了一些更常见的技术，但是我们可以更深入地研究这个广阔的世界，并揭示网络中未知标签分类背后的一些理论。这一部分将紧密跟随 Jure Leskovec 博士在斯坦福在线上关于机器学习的课程。让我们澄清我们的方法将依赖的前提:

1. 相似的节点通常靠得很近或者直接相连
2. 节点的标签可能取决于:它的特征、它附近的邻近节点的标签以及它附近的邻近节点的特征。

集体分类是建立在马尔可夫假设上的概率框架:一个节点的标签依赖于其邻居的标签(一阶马尔可夫链)。它包括 3 个步骤:

局部分类器:分配初始标签。

• 基于节点属性/特征预测标签的标准分类任务。不使用网络信息。

关系分类器:捕获节点之间的相关性。

• 使用网络信息根据其邻居的标签和/或属性对节点的标签进行分类。

集体推理:通过网络传播相关性。

• 迭代地将关系分类器应用于每个节点，并迭代直到相邻标签之间的不一致性最小化。

集体分类有三种常用模型:

概率关系分类器

• 节点的类概率是其邻居的类概率的加权平均值。
• 带标签的节点用真实标签初始化。未标记的节点用 0.5 初始化。
• 通过将邻近的一阶节点标签(地面真实标签和 0.5 用于未标记的节点)相加并除以总的一阶节点来标记节点。
• 所有节点以随机顺序更新，直到收敛或达到最大迭代次数。

局限性:

• 不能保证收敛
• 模型不使用节点特征信息

迭代分类

• 主要思想是根据节点的属性以及邻居集的标签对节点进行分类。
• 基本上训练了两个分类器。一种是基于节点特征向量预测节点标签。第二种方法基于节点特征向量和节点邻居标签的汇总来预测节点标签。
• 相邻标签的汇总是一个向量，可以表示为:每个标签的数量直方图、最常见的标签或相邻集中不同标签的数量。
• 在阶段 1 中，在训练集上建立两个分类器，在阶段 2 中，基于分类器 1 在测试集上设置标签，计算摘要向量，并且用分类器 2 预测标签。对每个节点重复这一过程。

局限性:

• 这种方法也不能保证收敛。

循环信念传播

• 动态编程方法，其中节点相互“传递消息”,反复回答概率查询。达成共识才算信念。
• 每个节点只能与其邻居交互(传递消息),该消息被每个节点从其邻居处听到，被更新，然后被转发。把这个想象成游戏电话。

Jure Lescovec，斯坦福， CS224W:带图的机器学习

• 该算法需要对节点进行排序，并且边缘方向根据节点集合的顺序。这定义了消息是如何传递的。
• 利用标签-标签势矩阵，该矩阵是节点与其邻居之间的依赖关系。它与一个节点属于一个类的概率成正比，假设它在同一个类中有一个邻居。
• 利用与节点成为一个类的概率成比例的先验信念。
• 利用“消息”,它是一个节点对下一个节点是一个类的估计。
• 所有的消息都被初始化为 1，然后对于每个节点，我们想要计算什么消息将被一起发送(给定节点对下一个节点的类的信任)。这是通过对邻居的所有状态加总标签-标签电势、先验以及邻居从前一轮发送的消息来计算的。

Jure Lescovec，斯坦福， CS224W:带图的机器学习

局限性:

• 当你的图中有圈时，会出现一些问题，因为如果节点的初始信念是不正确的，它可以通过圈和/或不收敛来加强。这可能是因为每个消息都被认为是独立的，这在 cycles 中并不真实。

其中一些是需要通过遵循算法来构建的模型，但我建议快速阅读文档中引用的一些 sklearn 或 networkx 论文背后的研究论文——很可能提到了其中的一些技术！

摘要

在这一部分中，我介绍了如何利用图形信息进行监督和半监督学习。使用图表的价值在于至少可以提供丰富的空间连通性和中心性特征，并提供大量新技术来扩展您的问题解决策略库。

如果您将这里讨论的想法与前面关于度量、随机世界和扩散模型以及无监督学习技术的部分结合起来，您会发现自己正在以一个全新的维度分析您的数据。

即使有了所有这些新的想法和方法，我仍然没有讨论最近几年对图形——图形神经网络的大肆宣传。在接下来的部分中，我将把这个系列带到图形神经网络中，但请记住，深度学习仍然只与特定的数据问题相关。大多数数据问题都是表格形式的，不应该真的需要深度神经网络来解决，但是扩展自己的知识库也无妨！

为了避免写一本书和内容超载，我在这个故事中也没有涉及到很多内容，但这里有一些我使用的主要资源和特定主题，我认为从业者会从回顾中获得很多价值:

• 图正则化方法
• 集体分类模式示例

参考

[1] Claudio Stamile，Aldo Marzullo，Enrico Deusebio，图机器学习

[2] Jure Leskovec，斯坦福， CS224W:带图的机器学习

[3]伊斯利，大卫和克莱因伯格，乔恩。2010.网络、人群和市场:关于高度互联世界的推理

[4] 大都会艺术博物馆开放存取

图形神经网络:2008 年以来的学习之旅——扩散卷积神经网络

原文：https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-diffusion-convolutional-neural-networks-329d45471fd9

图中邻接矩阵的真正威力是什么？什么是扩散卷积？请跟随我探索图形和机器学习的新冒险，探索 DCNN 理论

图片由杰里米·贝赞格在 Unsplash 上拍摄

我以前关于图形和 ML 的帖子:

• 图形神经网络:2008 年以来的学习之旅——第一部分
• 图形神经网络:2008 年以来的学习之旅——第二部分
• 图形神经网络:2008 年以来的学习之旅——深度行走
• 图形神经网络:2008 年以来的学习之旅——Python&深度行走
• 图神经网络:2008 年以来的学习之旅——图卷积网络
• 图神经网络:2008 年以来的学习之旅——Python&图卷积网络

通过我的推荐链接支持我的写作加盟媒介:

https://medium.com/@stefanobosisio1/membership

在这个系列中，我们正在跟踪和研究机器学习算法处理图的演变[1，2]。图表可以以非常简洁的方式存储大量信息[3–6]，它们可以用于根据人们的社会关系评估人群[7–9]或利用简单线性分析无法检测的潜在特征[10]。另一方面，图形是复杂的数学结构[11，12]，它们的输入信号不能在网格上描述，并且很难定义主要的局部统计，除非我们对节点的邻居进行平均。由于这些原因，卷积神经网络[13–15]等强大的最大似然算法的应用有时很复杂，需要了解图形的数学基础。

在上一篇帖子中，我们学习了 Kipf 和布鲁纳的卷积神经网络【11，12】，突出了一个图的谱分析和卷积运算之间的关系。今天我们将继续这项研究，分析 Atwood 和 Towsley 关于扩散卷积神经网络的论文[16，17]。在这种方法中，作者利用邻接矩阵和频谱分析之间的关系，利用邻接矩阵的内在属性，得出马尔可夫链公式[18–20]。

扩散卷积神经网络

扩散卷积神经网络(DCNN)通过学习“过滤器”来解决图形分类问题，这些过滤器通过扩散过程总结局部信息。这些信息是通过利用邻接矩阵属性获得的图的潜在表示来检索的。最后的算法大量使用张量运算，它需要一种稀疏表示，以允许 DCNN 处理数百万或数十亿节点的图形。

图 DCNN 的总结。根据图的邻接矩阵，我们可以计算从一个起始节点到给定 H 跳的最终节点的概率转移张量。这个张量反映了邻接矩阵的相同特征以及节点之间的“扩散”行为。张量 P、输入特征 X 和神经网络权重之间的乘积给出了扩散卷积层 z。该层可被完全连接的层接收，以返回输入图上的预测。

从 GCN 及其理论[21–25]中，我们了解到图的拉普拉斯描述与傅立叶变换密切相关。从这里，我们可以通过将自连接邻接矩阵 A 与节点的特征相乘来直接获得卷积运算，为图定义一个卷积神经网络层:

等式 1: l+1 卷积层的 l+1 激活矩阵，其被用作图形卷积神经网络(GCN)算法的传播规则

其中 H 是第l或l+1层的激活矩阵，σ是类似于 ReLu 的激活函数， D 是图度矩阵， A 是自连接邻接矩阵， W 是层特定的可训练权重矩阵。

从这个基本计算出发，阿特伍德和陶斯利在卷积运算中加入了扩散。这种扩散允许节点“浏览”它们的邻居，并考虑来自它们的社会影响——这是 GCN 和 DeepWalk 的一种混合。然而，我们如何在一个图上添加扩散呢[26]？让我们考虑一个简单的 3 个顶点的图和它们的邻接矩阵(图 2)

图 2:一个简单的 3 顶点图及其邻接矩阵 A

每个顶点都可以与这些坐标相关联: (1，0，0) 表示 v1 ， v2 ， (0，0，1) 表示 v3 。如果我们把顶点乘以邻接矩阵，我们就能得到它的邻居的视图:

图 3:顶点邻接矩阵乘法返回给定顶点的邻居

图 3 显示，如果我们从顶点 1 开始，我们可以跳到顶点 2，对于顶点 2 我们可以跳到 v1 或 v3 ，从顶点 3 我们可以跳到顶点 2 。现在，如果我们多次应用邻接矩阵会怎么样？我们以 v2 为例。 v2 和 A 之间的乘积返回两次 v2 ，即如果我们沿着图中从 v2 开始的路径走两次，我们将返回到 v2 。因此，我们可以陈述这个定理:*给定邻接矩阵 a 的幂 h，Aʰ(i，j)等于长度正好为 h 的图 g 中从 I 到 j 的路径数。*这意味着邻接矩阵 A 的幂 h 给了我们一个图，该图给出了每个起始顶点在 h 跳中的去向——因此我们在图上是“扩散”的。

我们能给这个公式增加一点概率吗？我们当然可以！如果我们对邻接矩阵进行归一化，我们将获得一个转移矩阵，即给定一些跳数，从节点 i 到节点 j 的概率 h. 这里应该有一个铃声在你脑海中响起，让你思考马尔可夫链。这里的归一化邻接矩阵可以充当转移概率矩阵，就像在马尔可夫链过程中一样。这个矩阵的力量可以给我们一个关于如何在图上扩散每个顶点的想法。

现在可以将卷积运算与扩散概念结合起来。如图 1 所示，扩散卷积算子可以认为是转移概率张量 P，与输入节点特征矩阵 X 和层随机初始化权重矩阵 W 的乘积，P 是一个N×H×N张量， X 是一个 N x F 矩阵，而 W 是一个 F x N 矩阵，其中 N 是节点数， H 是跳数(或邻接矩阵的幂)，而 F 是输入特征数。 最终的扩散卷积算子 Z 是一个 N x H x H 张量。这个张量可以被一个完全连接的神经网络层摄取，其输入节点与存储在张量中的矩阵一样多。然后可以通过 softmax 激活处理完全连接层的结果，以返回概率标签 Y.

总之，等式 2 报告了在 DCNNs 中执行的操作。首先，根据转移概率矩阵 P 和输入特征计算扩散卷积层 Z。然后，通过对来自完全连接的神经网络的输出的 softmax 激活来产生概率，该神经网络已经摄取了 z。

等式 DCNNs 操作总结。最初，根据输入概率转移张量 P 和节点特征 x 计算扩散卷积算子 Z。最后，在全连接层输出上，通过 softmax 激活返回概率预测。

今天就到这里吧！请继续关注我们的下一篇文章，在那里我们将编写 Python 代码来实现 DCNNs！

如果有任何问题或意见，请随时给我发电子邮件，地址是:stefanobosisio1@gmail.com，或者直接在 Medium 这里。

文献学

1. 克劳德·贝尔热。图论。快递公司，2001 年。
2. 弗朗西斯·安斯科姆，《统计分析中的图表》美国统计学家 27.1(1973):17–21。
3. 沃索伊，索罗什，德布罗伊和西南阿拉尔。"真假新闻在网上的传播."理科359.6380(2018):1146–1151。
4. 维拉、何塞和约兰达·戈麦斯。"从图表中提取商业信息:眼球追踪实验."商业研究杂志69.5(2016):1741–1746。
5. 特鲁科，欧内斯特。"关于图的信息量的一个注记."数学生物物理学通报 18.2(1956):129–135。
6. González-Díaz，Humberto，et al .〈基于分子图和社会网络信息指数的美国县级抗 HIV 药物活性与艾滋病流行率的人工神经网络多尺度模型〉。化学信息与建模杂志54.3(2014):744–755。
7. 尹，郝，等，“局部高阶图聚类”第 23 届 ACM SIGKDD 知识发现和数据挖掘国际会议论文集。2017.
8. 拉蒂根，马修 j，马克梅尔和大卫·延森。"用网络结构指数进行图聚类."第 24 届机器学习国际会议论文集。2007.
9. 张，邓杰，陈金印，陆。"区块链钓鱼诈骗检测通过多通道图分类."区块链和可信系统国际会议。新加坡斯普林格，2021。
10. 佩罗齐、布莱恩、拉米·艾尔弗和史蒂文·斯基纳。"深度行走:社交表征的在线学习."第 20 届 ACM SIGKDD 知识发现和数据挖掘国际会议论文集。2014.
11. 基普夫，托马斯 n，和马克斯韦林。“图卷积网络的半监督分类.” arXiv 预印本 arXiv:1609.02907 (2016)。
12. 琼·布鲁纳等着《图上的谱网络和深局部连通网络》第二届国际学习代表大会，ICLR 。第 2014 卷。2014.
13. 阿尔巴维、萨阿德、塔里克·阿贝德·穆罕默德和萨阿德·扎维。“了解卷积神经网络.” 2017 国际工程与技术大会(ICET) 。Ieee，2017。
14. 卡尔·布伦纳、纳尔、爱德华·格雷芬斯特特和菲尔·布伦松。“一个用于建模句子的卷积神经网络.” arXiv 预印本 arXiv:1404.2188 (2014)。
15. 克里日夫斯基、亚历克斯、伊利亚·苏茨基弗和杰弗里·e·辛顿。"使用深度卷积神经网络的图像网络分类."神经信息处理系统进展25(2012):1097–1105。
16. 阿特伍德，詹姆斯和唐·陶斯利。"扩散卷积神经网络."神经信息处理系统的进展。2016.
17. 稀疏扩散-卷积神经网络。 arXiv 预印本 arXiv:1710.09813 (2017)。
18. 叶，侬。"用于异常检测的时间行为的马尔可夫链模型."2000 年 IEEE 系统、人和控制论信息保证和安全研讨会会议录。第 166 卷。纽约西点军校，2000 年。
19. 海因斯布莱恩。"马尔可夫链中的第一个环节."美国科学家 101.2 (2013): 252。
20. 奥雷，史蒂文。马尔可夫链转移概率的极限定理。伦敦:范·诺斯特朗，1971 年。
21. 学习分子指纹的图形卷积网络。 arXiv 预印本 arXiv:1509.09292 (2015)。
22. 哈蒙德、大卫·k、皮埃尔·范德盖恩斯特和雷米·格里邦瓦尔。"通过谱图论研究图上的小波."应用和计算谐波分析30.2(2011):129–150。
23. 学习仿射变换。模式识别32.10(1999):1783–1799。
24. 李，文静，和唐利。“仿射不变匹配的 Hopfield 神经网络.”《IEEE 神经网络汇刊》12.6(2001):1400–1410。
25. 离散傅立叶变换和卷积的算法。斯普林格，1989 年。
26. 邻接矩阵的好资源在这里:https://www . bowaggoner . com/courses/2019/csci 5454/docs/spectral . pdf

图形神经网络:2008 年以来的学习之旅——从 Python 到 JAX:图形注意力网络

原文：https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-from-python-to-jax-graph-attention-networks-692e4d6d7637

实践中的 GAT！探索 PyTorch、Torch Geometric 和 JAX #GPU 实现来加速 GAT 性能

图片由本杰明·沃罗斯在 Unsplash 上拍摄

通过我的推荐链接加入 Medium 来支持我的写作和项目:

https://stefanobosisio1.medium.com/membership

我之前关于图形神经网络的文章:

• 图形神经网络:2008 年以来的学习之旅——第一部分
• 图形神经网络:2008 年以来的学习之旅——第二部分
• 图形神经网络:2008 年以来的学习之旅——深度行走
• 图形神经网络:2008 年以来的学习之旅——Python&深度行走
• 图形神经网络:2008 年以来的学习历程——图形卷积网络
• 图神经网络:2008 年以来的学习之旅——Python&图卷积网络
• 图形神经网络:2008 年以来的学习之旅——扩散卷积神经网络
• 图形神经网络:2008 年以来的学习之旅——图形注意力网络

上次我们学习了图形注意网络(GAT)的理论原理。GAT 试图克服以前的图形神经网络方法中的一些已知问题，强调注意力的力量。我们看到，自 2014 年 Cho 和 Bahdanau 开始解决序列对序列(Seq2Seq)问题(例如，从法语到英语的翻译)以来，注意力一直是一个热门话题。GAT 的核心部分是 Bahdanau 的注意力，它计算输入序列和预期输出序列之间的比对分数。也可以为图节点的特征计算这样的分数，将输入图转换成潜在表示。此外，这种新的特征表示可以通过多头注意力得到进一步增强，其中多个注意力层被并行使用，以检测和使用彼此远离的节点之间的长期依赖性和关系。

今天，所有这些理论都可以付诸实践。所有的实现都将在 Cora 数据集上进行测试(许可证:https://paperswithcode.com/dataset/cora；
CC0:公共领域)[1，4]。Cora 数据集由机器学习论文组成，分为 7 类:case_based、genetic_algorithms、neural_networks、probabilistic_methods、reinforcement_learning、rule_learning、theory。论文总数为 2708，这将是节点数。去除词干和停用词后，最终数据集只有 1433 个唯一词，这将是要素的数量。因此，该图可以用一个 2708 x 1433 的矩阵来表示，其中 1 s 和0取决于特定单词的存在。从论文引文文件中可以获得边列表并创建一个 2708×2708 的邻接矩阵。最初将颁发一个 PyTorch。随后，JAX 又进一步改进了深记的包。最后，用 Torch 几何包进行测试。

！！！所有这些测试都能在这个 Jupyter Colab 笔记本里找到！！！

前奏:加载数据例程

对于所有的测试，数据都是用模板化的 Python 代码加载的，这里是好心提供的

图 1:加载 CORA 数据集程序。该函数返回邻接矩阵、节点特征、标签、用于训练、验证和测试的索引以及长传感器格式的边列表

CORA 数据集从https://linqs-data.soe.ucsc.edu/public/lbc/cora.tgz下载，然后节点的特征被编码成一个稀疏矩阵features = sp.csr_matrix(idx_features_labels[:, 1:-1],dtype=np.float32并被归一化，使得它们的值范围在[0，1]之间。从Cora.cites创建边缘列表，并从那里获得稀疏的adjacency矩阵。最终元素被转换为 PyTorch 张量:

features = torch.FloatTensor(np.array(features.todense()))    
labels = torch.LongTensor(np.where(labels)[1])    
adj = torch.LongTensor(adj.todense())   

idx_train = torch.LongTensor(idx_train)    
idx_val = torch.LongTensor(idx_val)    
idx_test = torch.LongTensor(idx_test) edge_tensor = torch.LongTensor(edges)

第一首赋格:PyTorch 实现 GAT

让我们从 PyTorch 开始我们的实现之旅。图 2 显示layers.py开始覆盖 GAT 的第一个关键点:注意力算法。

图 2: Bahdanau 在 PyTorch 对 GAT 的关注

代码是我们在理论中看到的一个总结。首先，我们需要指定一个大小为in_features, out_features的权重矩阵W，它是输入节点特征矩阵h的倍数。这个产品然后被传递到 attention，它是由两层和一维输出的神经网络a组成的。比对分数如下获得:

WH1 = torch.matmul(WH, self.a[:self.out_features, :]) 
WH2 = torch.matmul(WH, self.a[self.out_features:, :])
e = nn.LeakyReLU(WH1 + WH2.T)
attnt = torch.where(adjacency > 0, e, -1e9*torch.ones_likes(e) )         attnt = funct.softmax(attnt, dim=1)

最后，结果可以连接或平均，从这里返回新节点的表示hfirst. 非常容易实现具有多头关注的 GAT:

图 3: GAT 模型，多头注意力，向前迈步，准备接受训练

导入基本注意层from layers import GraphAttentionLayer后，构造器建立注意头和最终输出:

self.attheads = [GraphAttentionLayer(in_features, out_features, concat=True) for _ in range(nheads)]     

self.output = GraphAttentionLayer(out_features*nheads, nclass, concat=False)

forward步骤计算每个注意力头attn(X, adjacency) for attn in self.attheads的输出，并返回给定输入图X的最终输出节点预测

我们现在已经准备好根据给定的 CORA 输入开始训练 GAT，图 5:

图 5:基于 PyTorch 的 GAT 的训练路由

训练使用亚当优化器，100 个周期的学习率为lr=0.005和weight_decay=5e-4。该测试在单 CPU 处理器英特尔至强 2.20GHz 的 google Colab 上运行。100 个时代可以在 2 分 55 秒内运行，训练和验证负似然损失nll，从 1.945 提高到 1.931。好但不是最好的方法！我们可以用 PyTorch Geometric 放大我们的模型

更好的是:PyTorch 几何中的一首赋格曲

PyTorch Geometric 是一个建立在 PyTorch 之上的库，并针对图形神经网络的实现和计算进行了优化。PyTorch Geometric 的关键结构点是易于使用的小型批量加载器，它允许模型处理非常大的数据集，以及优化的图形管道支持，并在箭筒中进行分布式图形学习。简而言之，用 PyTorch Geometric 编写代码非常简单，只需几行代码就可以实现图形神经网络，还可以在 CPU 和 GPU 之间切换。

图 6 显示 PyTorch 几何安装和 CORA 数据集的加载。数据集可以很容易地通过torch_geometric.datasets导入。数据集对象可以很容易地与torch_geometric.transforms交互，因此特性可以在一行代码中规范化为dataset.transform = T.NormalizeFeatures()

图 6: PyTorch 几何安装和 Cora 数据集的加载

为了与之前的测试保持一致，CORA 数据集将通过load_data()函数加载。从这里我们可以创建我们的 GAT 网络对象:

图 GAT 对象的实现和训练。培训可以是

GAT 类遵循通常的 PyTorch 方案。在结构__init__中，我们定义了模型参数和模型层。这些层由两个GATConv单元组成。前者是多头注意层，输出级联，后者是多头注意层，平均输出。在forward功能中，定义了模型序列。初始丢弃后，输入节点的特征在conv1层进行处理，最后在conv2层进行平均。与之前一样，我们将在英特尔至强 2.20GHz 处理器上使用 8 个隐藏单元和 8 个注意力头执行计算，并通过 Adam optimiser 进行参数优化。正如之前一样，我们可以调用上面的train函数来执行训练，而神奇的命令%%time测量执行时间。

PyTorch Geometric 中引入的伟大优化仅在 9.58 秒内处理 100 个时代，训练损失从 1.946 到 1.107 不等，有效损失从 1.945 到 1.352 不等。这是一个了不起的结果，这应该会让我们想起在处理 GNN 问题时应该用什么方法。它还没有完成。我将向您展示一种处理 GAT 的更深入的方法。

JAX +图形处理器

作为最后的测试，我检查了吉列姆·库库鲁https://github.com/gcucurull/jax-gat的实现，他出色地实现了 JAX 的 GAT，我对原始代码做了一些修改。什么是 JAX？JAX 是 DeepMind 中使用的主要编码框架，用于放大大模型，使它们运行得更快。JAX 的基础核心单元是autograd一个在 Python 中高效计算导数的 Python 包和XLA一个加速线性代数编译器，可以用几行代码加速 Tensorflow 模型，在 8 Volta V100 GPUs 上实现 BERT 7 倍的性能提升。正如你所看到的，如果我们要在 GPU 或 TPU 上加速我们的模型，JAX 工作得非常好。此外，DeepMind 最近发布了 https://github.com/deepmind/jraph/tree/master/jraph 的jraph一个新的 JAX 包，完全专注于图形神经网络的实现。遗憾的是，我还没有时间处理它——正如你看到的，我还在调试我的注意力实现——但是更多的更新即将到来:)

图 9 示出了在 JAX 中实现注意力算法的核心。首先，GraphAttentionLayer从构造器init_fun开始初始化神经网络和矩阵W权重。这是通过jax作为jax.random.split(random.PRNGKey(NUMBER),4)产生一些特定的随机数来实现的。jax需要随机数，例如，初始化数组或计算概率分布。特别是，输入参数需要是一个伪随机数生成器密钥或PRNGKey。NUMBER是一个随机数，可以通过NumPy轻松生成。随机生成器函数是create_random，它与jit装饰器一起存在。jit标记一个要优化的函数，它的意思是just in time，即该函数的编译将推迟到第一次函数执行时进行。由于我们只需要生成 4 个随机数，jax并不是非常高效，因此我们可以用jit来加速这个过程——记住jax在我们扩大规模时非常有用，因此在生成数百万个随机数时，它会比简单的NumPy 更高效。

一旦输入权重被初始化，apply_fun计算输入特征矩阵x上的关注度。Guillem 已经实现了Dropout函数，允许将is_training作为一个参数。然后，代码与 PyTorch 和NumPy非常相似，例如jax.numpy.dot(x,W)用于点积乘法，jax.nn.softmax(jax.nn.leaky_relu(...))用于最终注意力的 softmax 计算

图 9:JAX GAT 关注层的实现

接下来，创建多头注意力层，如图 10 所示。首先，我们创建一个空列表layer_funs来存储注意力头，并创建一个空列表来初始化权重layer_inits。然后，init_fun在这种情况下初始化layer_inits列表中每个元素的权重。apply_fun为layer_funs中的每个元素设置关注的应用。如果我们在 GAT 的最后一层，我们对所有的注意力进行平均，否则我们连接结果x = jax.numpy.concatenate()

图 10:多头关注层的实现

图 11 将最后的GAT函数合并在一起。在这种情况下，nhid头被创建为MultiHeadLayer(nheads[layer_i], nhid[layer_i]...)，每个头的初始化函数被附加到init_funs列表，应用函数被附加到attn_funs列表。

图 11:最终的 GAT 实现，合并多标题层和关注层

在GAT中，init_fun通过att_init_func初始化每个头，同时apply_fun运行完整的 GAT 网络算法。

为了创建输入 CORA 数据，我对上面的 load data 函数做了一点修改，返回了NumPy数组而不是张量(图 12)

图 load _ data 函数的轻微修改。返回 NumPy 数组，而不是 PyTorch 张量

一旦一切就绪，我们就可以开始训练了。训练在特斯拉 K8 和特斯拉 T4 GPU 上运行——由谷歌❤实验室免费提供

图 13 显示了训练程序。在每一步中，jax.experimental.optimizer.Adam通过autograd功能更新所有参数。update函数需要在每个时期结束时运行，所以我们可以用jit装饰器来加速。然后，每个数据批次可以作为jax.device_put(train_batch)直接加载到计算设备上，在这种情况下是 GPU。这是 jax 的一个显著特性，因为整个数据都可以很容易地读取，从而提高了整个模型的性能。如果没有这个步骤，该算法在 Tesla K80 上运行大约需要 1/2 分钟，而在 GPU 上推送数据平均将计算时间减少到 30/40 秒。显然，特斯拉 T4 的表现更好，平均成绩为 15/18 秒。对于训练和验证批次，最终训练负对数似然损失的范围为 1.908 至 1.840。

图 13: JAX 加特训练部分。Update 函数和 device_put 是这个在 GPU 上实现的核心特性。

今天是一切:)

您可以在这里找到包含上述测试的整个笔记本

请继续关注下一个图表冒险！

如有任何问题或意见，请随时给我发电子邮件:stefanobosisio1@gmail.com 或直接在 Medium 这里。

文献学

1. 网络数据中的集体分类。艾杂志 29.3(2008):93–93。
2. 《推特上仇恨用户的描述和检测》第十二届 AAAI 国际网络和社交媒体会议。2018.
3. 彭宁顿、杰弗里、理查德·索彻和克里斯托弗·d·曼宁。"手套:单词表示的全局向量."2014 年自然语言处理经验方法会议论文集。2014.
4. 《用机器学习自动化互联网门户的构建》信息检索3.2(2000):127–163。

图形神经网络:2008 年以来的学习之旅——图形注意网络

原文：https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-graph-attention-networks-f8c39189e7fc

今天我们将深入研究图形注意力网络(GAT)的理论和实现。一言以蔽之:关注摇滚，图表摇滚，GAT 的作者摇滚！

图片由 Unsplash 上的 Pascale Amez 拍摄

通过我的推荐链接加入 Medium 来支持我的写作和项目:

https://stefanobosisio1.medium.com/membership

我以前关于图和 M 的帖子

• 图形神经网络:2008 年以来的学习之旅——第一部分
• 图形神经网络:2008 年以来的学习之旅——第二部分
• 图形神经网络:2008 年以来的学习之旅——深度行走
• 图形神经网络:2008 年以来的学习之旅——Python&深度行走
• 图形神经网络:2008 年以来的学习历程——图形卷积网络
• 图神经网络:2008 年以来的学习之旅——Python&图卷积网络
• 图形神经网络:2008 年以来的学习之旅——扩散卷积神经网络

欢迎回到我的图形神经网络系列。今天我要向大家介绍一个最伟大的图形神经网络框架下的基础理论:图注意力网络(GAT)[1]由 Velickovic，Cucurull，Casanova，Romero，莉雅和 Bengio 于 2018 年发表(你应该只听到这些名字就起鸡皮疙瘩！)这种 ML-graph 方法有什么新的地方？我们来分析一下前几集看到的内容。

最初，Gori 和 Scarselli[5–9]提出了图形神经网络(GNNs ),其中递归神经网络被推广为直接与图形对象交互。gnn 基于 Banach 不动点定理。一旦达到平衡，运行神经网络以返回输出。相比之下，GNN 不能利用表征学习，其可扩展性非常有限，由于收敛问题。

我们看到的另一种方法是 Perozzi 在 2014 年提出的 Deep Walk [6]及其在 2017 年的演变[7]。深度行走标志着节点嵌入的概念，即通过 skip gram[8–12]获得的节点的潜在表示(或社会表示)。这个模型在半无人监督的模式下工作，尽管可扩展性和表示学习可能仍有问题。

因此，已经提出了进一步的图形神经网络框架。谱方法[13–17]，其中图形拉普拉斯表示、特征值分解和卷积是关键要素。卷积可以通过扩散概念来进一步利用。在这种方法[18–22]中，算法学习每个节点的特定权重矩阵，计算转换矩阵的幂来描述节点的邻域。虽然这些技术非常成功，但它们直接依赖于拉普拉斯的特征基，限制了我们可以研究的图形种类。因此，一旦我们将我们的模型训练到一个特定的图，我们就不能使用这个模型在不同的结构图上运行预测。

在 GAT 中，作者强调了注意力的力量。注意力算法直接来源于神经机器翻译问题或序列对序列(Seq2Seq)。如果我从法语翻译成英语，我将不得不考虑输入和输出序列之间的长度差异，以及在给定词汇和目标序列的情况下我可以使用的最佳术语。注意力不仅可以解决不同长度的问题，还可以检测输入的最相关部分，以优化和最大化给定输入序列的输出概率。

现在让我们跳到注意力是如何工作的，以及一切是如何开始的。

注意:什么？谁啊。在哪里？什么时候？为什么？

注意力算法起源于 Cho 的 RNN 编码器-解码器模型[14]。作者正在寻找一种有效的方法来改进 seq2seq 翻译的 ML 模型。编码器-解码器模型是递归神经网络(RNN)的堆叠组合。编码器将符号序列编码成固定长度的向量表示，而解码器以另一种符号范例对给定的表示进行解码。

图 1 显示了 Cho 算法的工作原理。给定输入序列 x (例如Je m'appelle S)，该模型试图最大化目标序列 y: 的条件对数似然

等式 1:给定输入序列 x 和目标序列 y，RNN 编码器-解码器试图最大化条件对数似然

输入序列用大小为hidden_size的嵌入层解码，然后在 GRU 单元中处理。GRU 的隐藏状态，称为context_vector，与目标序列一起被提供给解码器。解码器将输入序列和上下文向量一起投影到嵌入空间。最后，一个 GRU 和一个线性层在 x 和 y 之间创建一个映射

图 Cho 的 RNN 编码器-解码器模型的逻辑示意图。编码器对输入序列进行消化。编码器的隐藏状态与目标序列一起被用作解码器的输入，以便找到序列到序列的正确映射。

图 2 显示了如何在 Pytorch 中对 Cho 的编码器和解码器进行编码的示例代码。一个关键的区别是解码器类将在嵌入的目标空间中映射输入。

图 Cho 的 RNN 模型的编码器和解码器的示例代码。这两个模型都依赖于嵌入层和 GRU。

Keras 提供了进一步的可视化帮助，我们可以用一种简单的方式对这个模型进行编码，以显示输入信息是如何处理的:

图 Cho 的 RNN 编码器-解码器的 Keras 实现。在这里，您可以进一步看到当将编码器 GRU 的隐藏状态传递给解码器时，注意力是如何被触发的。

2016 年晚些时候，Bahdanau 扩展了 Cho 的模型[26，28]，用*比对分数构建了注意力算法。校准分数进一步增强了编码器的输出，定义了它与给定输出的匹配程度:

• 每个编码器的 GRU 输入 x₁、x₂、x₃ …都有各自的隐藏状态 h₁、h₂、h₃
• 解码器开始计算比对分数，例如 e ₁₁ ，e ₁₂ ，e ₁₃ (等式 2)。校准分数是通过函数 a — 通常是前馈线性神经网络来定义的，该函数作用于解码器的输出状态 s 和编码器的输出 h.

等式 2:对准分数被定义为作用于解码器的输出状态 s 和编码器的输出 h 的函数 a

• 在第一步，解码器输出为 0，因此校准分数定义为:

等式 3:第一次迭代中的对齐分数，其中解码器的输出为 0。

• 是简单的pytorch.nn.Linear前馈神经网络，其输出α 然后用 softmax 函数(等式 4)归一化:

等式 4:来自神经网络的一般 softmax-ed 输出以及等式 3 的 3 个输入的示例

• 然后，归一化对齐分数被用于更新输出编码器的上下文向量 c，并被注入到解码器 GRU 中:

等式 5:输出对齐权重用于将每个上下文向量与给定目标对齐

• 循环重复，新解码器的输出 s 用于计算比对分数

通过添加由前馈神经网络、softmax 和注意权重/对齐分数与编码器输出之间的矩阵乘法组成的注意层，可以在 PyTorch 中将该方案容易地应用于 Cho 的模型(图 2 ):

图 4:在 Cho 的 RNN 编码器-解码器中添加注意层。

总之，Bahdanau 的方法旨在将编码器的所有隐藏状态传递给 RNN 解码器，并进一步将注意力/对准分数层应用于解码器架构。从这里我们可以开始研究图形注意力网络算法

图形注意网络

从 Bahdanau 的注意力方法开始，Velickovic 等人开始使用图形注意力网络框架——然而，我必须强调，GAT 对注意力机制的特定选择是不可知的。现在，让我们考虑一个有 N 个节点的图，每个节点有 F 个特征。这里注意机制的整体过程是摄取一组节点特征*(维度为 F )并返回这些特征的一个输出表示**'(维度为 F’ )。要素的输出表示将调用一些潜在要素，这允许网络在节点级别运行预测。***

图 GAT 工作流程和注意力的示意图。

图 5 报告了 GAT 的作用方案。节点共享一个权重矩阵W** ，其维数为FxF’。权重矩阵 W 与每个节点的特征矩阵相乘以执行第一线性变换。它遵循第二线性变换，通过自关注机制，通过应用前馈神经网络 a，返回关注系数 e:**

等式 6:表示节点 j 的特征对节点 I 的重要性的关注系数

从 a 输出的注意系数在到达 softmax 层之前通过 LeakyReLu。softmax 在节点 j 的特征上被归一化，以使所有系数在不同节点之间容易比较:

等式 7:相对于节点 j 特征的归一化(softmax)关注系数

最后，应用非线性 σ 得到最终的特征描述h’。为了进一步稳定自我注意机制中的学习过程，作者扩展了该算法以使用多头注意。这种方法包括在图表的不同部分运行多个注意力层，以便掌握一些长期的依赖关系。长程相关性是指相距很远的节点之间的关系。最终的特征集合可以连接在一起，并且如 GAT 的论文中所提议的，进行平均以返回最终节点的预测。这种平均过程突出了 GAT 的输出是来自目标节点邻域的聚集信息。

现在让我们看看如何在 PyTorch 中实现 GAT 方法，而在下一个故事中，我们将处理数据集和预测以及优化 GAT 的技巧！

加特&皮托奇

图 6 显示了 GAT 核心部分的简单 PyTorch 实现。在call函数中，GAT 接收节点的特征和边(input)作为输入，报告图形结构信息。输入节点状态/特征最初乘以权重矩阵 W 以执行第一线性变换:node_states_transformed = tf.matmul(node_states, self.kernel)。将转换后的状态与结构信息node_states_expanded收集在一起，并从那里运行进一步的线性转换以获得关注系数:attention_scores = tf.nn.leaky_relu(tf.matmul(node_states_expanded, self.kernel_attention))。

图 PyTorch 中注意机制的实现

最后，softmax 被应用到attention_scores(第 70–79 行)，来自关注层的邻域特征信息被返回到主函数。

*第二个最重要的一点是实现了*多头关注。该类定义了并行运行的关注层的数量，以及关注层单元。最终输出是所有串联注意力输出的平均值:tf.reduce_mean(tf.stack(outputs, axis=-1), axis=-1)。

图 7:多头注意力的实现

让我们以 GAT 的最终实现来结束这个故事，对算法有一个全面清晰的了解:

图 GAT 模型的最终代码。

今天到此为止，请在下一个故事中欣赏我，我们将把 GAT 应用于数据集，看看 GAT 的真正威力是什么:)

如果有任何问题或意见，请随时给我发电子邮件，地址是:stefanobosisio1@gmail.com，或者直接在 Medium 这里。

文献学

1. 《图形注意网络》 arXiv 预印本 arXiv:1710.10903 (2017)。
2. 《图形神经网络模型》 IEEE 神经网络汇刊20.1(2008):61–80。
3. 《图形神经网络的计算能力》IEEE 神经网络汇刊 20.1(2008):81–102。
4. 《网页排序的图形神经网络》。2005 年 IEEE/WIC/ACM 网络智能国际会议(WI’05) 。IEEE，2005 年。
5. 哥里、马尔科、加布里埃尔·蒙法迪尼和佛朗哥·斯卡塞利。"一个在图形领域学习的新模型."议事录。2005 年 IEEE 神经网络国际联合会议。第二卷。№2005.2005.
6. 佩罗齐、布莱恩、拉米·艾尔弗和史蒂文·斯基纳。"深度行走:社交表征的在线学习."第 20 届 ACM SIGKDD 知识发现和数据挖掘国际会议论文集。2014.
7. 佩罗齐、布莱恩等人“不要走，跳过！多尺度网络嵌入的在线学习。”2017 年 IEEE/ACM 社交网络分析与挖掘进展国际会议论文集 2017 。2017.
8. 《向量空间中单词表征的有效估计》 arXiv 预印本 arXiv:1301.3781 (2013)。
9. 单词和短语的分布式表征及其组合性。神经信息处理系统的进展。2013.
10. 大卫·格思里等着，〈跳过语法建模的更近距离观察〉。 LREC 。第六卷。2006.
11. Gittens，Alex，Dimitris Achlioptas 和 Michael W. Mahoney。" Skip-Gram Zipf+Uniform =矢量可加性."计算语言学协会第 55 届年会论文集(第 1 卷:长篇论文)。2017.
12. 明诺、大卫和劳雷·汤普森。"负抽样跳跃图的奇异几何."自然语言处理中的经验方法。2017.
13. 基普夫，托马斯 n，和马克斯韦林。“图卷积网络的半监督分类.” arXiv 预印本 arXiv:1609.02907 (2016)。
14. 琼·布鲁纳等着《图上的谱网络和深局部连通网络》第二届学习代表国际会议，ICLR。第 2014 卷。2014.
15. 迪费拉德、米歇尔、泽维尔·布列松和皮埃尔·范德盖恩斯特。"具有快速局部谱滤波的图上的卷积神经网络."神经信息处理系统进展29(2016):3844–3852。
16. 学习分子指纹的图形卷积网络。 arXiv 预印本 arXiv:1509.09292 (2015)。
17. 哈蒙德、大卫·k、皮埃尔·范德盖恩斯特和雷米·格里邦瓦尔。"通过谱图论研究图上的小波."应用和计算谐波分析30.2(2011):129–150。
18. 阿特伍德，詹姆斯和唐·陶斯利。"扩散卷积神经网络."神经信息处理系统的进展。2016.
19. 稀疏扩散-卷积神经网络。 arXiv 预印本 arXiv:1710.09813 (2017)。
20. 叶，侬。"用于异常检测的时间行为的马尔可夫链模型."2000 年 IEEE 系统、人和控制论信息保证和安全研讨会会议录。第 166 卷。纽约西点军校，2000 年。
21. 海因斯布莱恩。"马尔可夫链中的第一个环节."美国科学家 101.2 (2013): 252。
22. 奥雷，史蒂文。马尔可夫链转移概率的极限定理。伦敦:范·诺斯特朗，1971 年。
23. 使用统计机器翻译的 RNN 编码解码器学习短语表达 arXiv 预印本 arXiv:1406.1078 (2014)。
24. 基于注意力的语音识别模型。神经信息处理系统进展 28 (2015)。
25. 基于端到端注意力的大词汇量语音识别。 2016 年 IEEE 声学、语音和信号处理国际会议(ICASSP) 。IEEE，2016。
26. Bahdanau、Dzmitry、Kyunghyun Cho 和 Yoshua Bengio。“通过联合学习对齐和翻译的神经机器翻译.” arXiv 预印本 arXiv:1409.0473 (2014)。
27. 你所需要的只是关注。神经信息处理系统进展 30 (2017)。
28. Luong，Minh-Thang，Hieu Pham 和 Christopher D. Manning。“基于注意力的神经机器翻译的有效方法.” arXiv 预印本 arXiv:1508.04025 (2015)。

*:https://jalammar . github . io/visualizing-neural-machine-translation-mechanics-of-seq 2 seq-models-with-attention/这里是 seq2seq with attention 的优秀可视化流程

图形神经网络:2008 年以来的学习之旅——Python 和图形卷积网络

原文：https://towardsdatascience.com/graph-neural-networks-a-learning-journey-since-2008-python-graph-convolutional-network-5edfd99f8190

今天，我们对 GCN 理论有了清晰而实用的认识。我们会穿过基普夫的火炬🔦GCN 的实施👩‍🎓。然后，我们将把我们所学到的应用到可恶的 Twitter 数据集上🔥

图片由龙之介菊野在 Unsplash

我以前关于图形和 ML 的帖子:

• 图形神经网络:2008 年以来的学习之旅——第一部分
• 图形神经网络:2008 年以来的学习之旅——第二部分
• 图形神经网络:2008 年以来的学习之旅——深度行走
• 图形神经网络:2008 年以来的学习之旅——Python&深度行走
• 图神经网络:2008 年以来的学习之旅——图卷积网络

通过我的推荐链接支持我的写作加盟媒介:

https://medium.com/@stefanobosisio1/membership

欢迎回到我的图形神经网络系列！在之前的文章中，我们研究了图论、卷积神经网络的理论和数学基础。今天我们将讨论 Kipf 对 GCN 的 PyTorch 实现，试图简化实现，并将 GCN 应用于 Twitter 仇恨/正常用户数据集。享受:)

将 GCN 理论翻译成 PyTorch

传承 PyTorch nn。组件

在 PyTorch 中常见的做法是制作一个定制模块来创建一个模型，使用torch.nn.Module这就创建了一个 Python 对象，从而允许创建复杂的模块。定制模块是类，它是包torch.nn.Module的子包，继承了所有的方法和属性:

图 1:使用 torch.nn 定义一个定制模块，新定义的模块继承了所有的 nn。模块属性和方法，并可以很容易地适应实现自定义模型。

class MyNetwork(nn.Module)定义了子类，然后，类似于nn.Module，它希望用输入和输出网络大小(分别是in_size和output_size)来定义构造函数。在构造函数中，调用超级构造函数super()。这允许从对象MyNetwork内的包torch.nn.Module创建对象，而不需要显式初始化它。然后，可以设置网络层和forward步骤，这也是从nn.Module继承而来的。

应用神经网络。基本 GCN 操作模块:layers.py

同样的方案之后是 Kipf 在layers.py:https://github.com/tkipf/pygcn/blob/master/pygcn/layers.py中实现 GCN 逻辑。图 2 显示实现了 GCN 的基本层功能，它是邻接图矩阵与输入图特征数组和第 I 层权重的乘积:

图 2:作为 torch.nn.Module 实现的 GCN 的基本操作。这里，Kipf 定义了 GCN 步骤，这是一个简单的基于拉普拉斯的矩阵乘法。权重和偏差被均匀采样，前一步执行所需的乘法。

权重和偏差参数被定义为torch.nn.parameter对象，通过从均匀分布中随机取样产生。forward步骤更新了前一篇文章的等式 10 中的层权重计算。

堆叠图层:models.py 中的 GCN 模型

既然我们已经实现了基本的构建模块，我们就可以继续实现 GCN 模型了。根据 Kipf 的论文，GCN 由两层组成，一个输入层，一个隐藏层，它们通过 ReLu 激活来组合。此外，我们可以有一个丢弃层，其中输入训练数据的一部分被丢弃，以进一步加强层预测。最终输出为 softmax 的对数，等式。一

等式 1:对数 softmax 函数。首先，对第 I 个输入执行 softmax，然后计算 log。

图 3:GCN 模型的实现。该模型由两层组成，一个输入层，一个隐藏层和一个可能的下降步骤。

准备输入数据

一旦基本模型已经建立，我们可以看看输入数据。Kipf 提供了来自 Cora 数据集(https://paperswithcode.com/dataset/cora)的数据；
CC0:公共领域)[1，4]。Cora 数据集由机器学习论文组成，分为 7 类:case_based、genetic_algorithms、neural_networks、probabilistic_methods、reinforcement_learning、rule_learning、theory。论文总数为 2708，这将是节点数。去除词干和停用词后，最终数据集只有 1433 个唯一词，这将是要素的数量。因此，该图可以用一个 2708 x 1433 的矩阵来表示，1 和 0 取决于特定单词的存在。从论文引用文件可以获得边列表，并从那里创建一个 2708 x 2708 邻接矩阵。数据通过实用程序脚本 [utils.py](https://github.com/tkipf/pygcn/blob/master/pygcn/utils.py)创建。一旦创建了这些元素，就可以继续进行培训步骤。

用 Cora 数据集训练 GCN 模型

图 4 总结了所有的 GCN 步骤。加载数据，以创建特征矩阵X和邻接矩阵adj。这些元素可以被 GCN 模型摄取，该模型通过拉普拉斯乘法来转换数据，返回每个节点的 7 个类的概率。

图 Kipf 代码概述。对初始 Cora 数据集进行处理，以获得特征矩阵 X 和邻接矩阵 adj。这些元素可在 GCN 模型中直接用于计算每个结点的输出类。

图 5 显示了用于训练 GCN 模型的 Kipf 代码的摘录。核心位是火车功能。这里，最初通过optimiser.zero_grad()将梯度设置为零。然后，模型的输出被计算为output = model(features, adj)。最后，运行模型性能检查和损失，计算负对数似然性和准确性，负对数似然性更新网络权重，准确性评估模型相对于评估数据集的良好性。

图 5:GCN 模型的训练程序。函数串是调用模型的核心位，权重通过负对数似然更新，并通过计算准确度分数来执行评估。

玩 GCN，预测推特上可恶的用户

现在是时候玩一个奇特的数据集和 GCN 了。数据集是 Twitter 可恶的用户【2】(CC0:公共领域许可证)在其论文中有描述【2】。该数据集拥有 100，000 名用户。5，000 名用户被贴上了仇恨的标签，也就是说，他们在 Twitter 上发布仇恨帖子。每个用户都有一组定义好的和人工设计的特征users_neightborhood_anon.csv，其中推文已经通过手套嵌入进行编码【3】。其目的是利用网络信息来预测哪些用户也可能是可恨的。这个例子是自由地受这个教程的启发:https://stellar graph . readthedocs . io/en/v 1 . 0 . 0 rc1/demos/interpretatibility/gcn/evidence-twitters-interpretatibility . html

下载数据和预处理

首先，我们需要下载数据并解压文件。在本例中，我们将通过 Google Colab 笔记本使用 Kaggle APIs:

!pip install kaggle --upgrade
# download from your kaggle account the token file kaggle.json
!mkdir /root/.kaggle 
!cp kaggle.json /root/.kaggle/. 
!mkdir dataset 
!kaggle datasets download -d manoelribeiro/hateful-users-on-twitter -p dataset/
# unzip the files 
!unzip dataset/*.zip

这个例子需要的文件是users_neighborhood_anon.csv和来自users.edges的边缘列表

节点的特征是人工设计的，然而，图形神经网络的优点在于它们可以去除这些特征，因为它们能够检索网络信息，这对于正确的分类是至关重要的。为此，我们将清理输入数据集，并将要素的大小从 1039 缩小到 206:

图 6:读取输入节点的特征并清理它们，以便将维数减少到 206。

从这里，我们可以开始准备一个数据集，用于 GCN 预测。首先，我们选择所有被标记为normal和hate的用户(总共 4971 个)。然后，可以读取边并选择带有已过滤节点索引的子图，最后，我们可以创建邻接表。

图 7:只选择标签不是 2 的用户，正常用户和讨厌用户，从他们的索引中提取相关的边子图。然后，使用 networkx 创建邻接矩阵，并使用 scipy 将其转换为稀疏矩阵

邻接矩阵是一种稀疏类型，通过scipy.sparse.coo_martrix创建，正如我们在 Kipf 代码中看到的。

最后一步是为 GCN 摄取准备邻接和特征矩阵。在这种情况下，我们将对要素的值进行归一化，因为相邻要素已经进行了归一化，我们将为训练(0–1000)、评估(1000–1200)和测试(1200–1400)定义一些样本索引。

图 8:归一化节点特征矩阵，定义训练、评估和测试的指标。

在推特上训练 GCN 可恶的数据集

最后一步完全遵循 Kipf 的代码。我们称之为 GCN 模型和亚当优化器。从那里开始，我们运行一系列的训练程序，然后我们将测量精确度。

图 9:根据节点的特征形状准备输入尺寸的 GCN 模型，设置隐藏层尺寸和优化器参数。然后，运行一组定义的时期

在这种情况下，我们定义的隐藏层大小为 16，但可以随意修改，输出类的数量为 2 ( normal或hate)。我们可以收集各个时期的损失和准确度，并看到在 50 个时期后有一个收敛，而评估集的准确度达到 0.89。

图 10:训练和评估 Twitter 数据集的负对数似然损失。两个数据集通过大约 0.34(训练)和 0.65(评估)的损失收敛。进一步的时代将会加强趋同

这只是 GCN 美丽的一个小小的例子。你可以带着这些作业进一步练习和探索 GCN 的力量:

• 修改输入数据集大小
• 从输入数据集中提取更多要素
• 从第二层提取信息，用分解算法作图，看网络在训练时如何分裂网络。

今天它是一切:)请继续关注下一个图表冒险！

如果有任何问题或意见，请随时给我发电子邮件，地址是:stefanobosisio1@gmail.com，或者直接在 Medium 这里。

文献学

1. 网络数据中的集体分类。艾杂志29.3(2008):93–93。
2. 《推特上仇恨用户的描述和检测》第十二届 AAAI 国际网络和社交媒体会议。2018.
3. 彭宁顿、杰弗里、理查德·索彻和克里斯托弗·d·曼宁。"手套:单词表示的全局向量."2014 年自然语言处理经验方法会议论文集。2014.
4. 《用机器学习自动化互联网门户的构建》信息检索3.2(2000):127–163。

作为梯度流的图形神经网络

原文：https://towardsdatascience.com/graph-neural-networks-as-gradient-flows-4dae41fb2e8a

基普夫&韦林反击战

在一些简单的约束下，图形神经网络可以被导出为梯度流，该梯度流最小化描述特征空间中吸引力和排斥力的可学习能量。这种形式主义允许将 gnn 解释为物理系统，并揭示了图形频率和通道混合频谱之间的相互作用如何决定节点特征的演变，并控制动力学是“平滑”还是“锐化”它还导致了一个令人惊讶的结论:即使是非常简单的具有共享权重的图卷积模型也不一定会遭受过度平滑，并且在嗜异性设置中可能是有效的。

图片:Shutterstock。

本文与 Francesco Di Giovanni、James Rowbottom、Ben Chamberlain 和 Thomas Markovich 合著，基于 F. Di Giovanni、J. Rowbottom 等人的论文 【图神经网络作为梯度流【2022】，arXiv:2206.10991。请看一段Francesco 在 首届意大利暑期学校关于几何深度学习 的演讲录音以及我们之前关于 神经扩散细胞束 和 物理启发图 ML

raph 神经网络经常被批评为过度平滑*(多个消息传递层逐渐产生接近常数的节点特征的趋势【1-2】)以及在异嗜性设置中的糟糕性能(当相邻节点具有不同标签时【3】)。应对这些现象的尝试最近导致了更复杂的信息传递方案的“寒武纪大爆发”，其中一些求助于非常奇特的结构，如蜂窝滑轮【4】。*

最重要的是，图形神经网络面临深度学习的普遍问题:可解释性差。总的来说，机器学习社区对 GNNs 有一种爱恨交加的关系:有时最新和最伟大的架构提供了最先进的结果，而在其他情况下，简单的旧方法(如图形卷积模型[5]或甚至节点式多层感知器)几乎一样好。对于某些模型在什么时候以及为什么表现良好，并没有清晰的认识，一种多少有些不健康的“民间传说”从一张纸重复到另一张纸上。

在最近的出版物中【6】，我们认为 GNNs 是离散的粒子动力系统，它在微分方程(称为梯度流)下演化，使一些能量最小化。这种受物理学启发的方法，我们称之为梯度流框架(GRAFF)* ，提供了对现有 GNN 建筑的更好理解(导致一些令人惊讶的结论！)以及派生新的更有效的方法的原则性方法。*

梯度流

考虑一个由演化方程支配的动力系统

ẋ(t)=f(x(t))

从某个初始状态 X (0)开始，运行时间 t > 0。这个微分方程的结构(在我们的符号中是 F )取决于底层的物理系统。例如，矩阵 X 的行可以表示以矢量场F给出的速度移动的粒子系统的空间坐标。如果粒子带电，它们相互施加静电力，导致耦合的常微分方程系统，其中不同行的 X 之间存在相关性。

模拟流体的复杂粒子动力系统。图片:李大卫。

在深度学习中，人们可以将微分方程系统的输入演变视为深度神经网络的连续版本，这是一种称为“神经微分方程”的方法[7–8]。然后，就有可能在用于求解方程的数值方案的时间步骤和神经网络的层之间画出一条平行线。

梯度流【9】是特殊类型的演化方程的形式

f(x(t)= –∇ℰ(x(t)，

ℰ是某种能量函数。梯度流使得ℰ在演化过程中单调下降[10]。许多物理系统都可以用一些能量来表征，这些能量被它们的动力学最小化了。ℰ的知识提供了对系统的更好的理解，并且经常允许一个人对动力学的主要影响和它的渐近行为作出陈述。

一个原型梯度流是扩散方程*，它控制着物理介质中的热传播。扩散方程的正式推导可以追溯到 19 世纪约瑟夫·傅立叶关于热分析理论【11】的论文。这种方程在物理学中有很多应用，也已经用于图像处理、计算机视觉[12]和graph ML【13】。*

在其最简单的形式中，𝒢图上的扩散方程由下式给出

ẋ(t)=–δx(t)，

其中 X 为 n × d 节点特征矩阵δ为 n × n 图拉普拉斯[14]。这是一个耦合的 ode 系统:图中的每个节点( X 的行)都与其邻居相互作用。

扩散方程原来是狄利克雷能量的梯度流

ℰᴰᴵᴿ(x)= trace(xᵀδx)=∑ᵤᵥ||(∇x)ᵤᵥ| |，

其中∇ X 表示在图的每条边上定义的特征的梯度。狄利克雷能量测量图[15]上特征的平滑度*。在极限 t →∞时，扩散会丢失输入特征中包含的信息，因为所有节点都变得“相同”[16]——这种现象在 GNN 文献中通常被称为“过度平滑”*

流形上的热扩散方程。

卷积图神经网络

T 平滑节点特征的简单扩散方程在图形 ML 问题中可能不太有用【17】，其中图形神经网络提供了更多的灵活性和能力。人们可以把 GNN 想象成一个由参量演化方程支配的更一般的动力系统

ẋ(t)=gnn(𝒢，x(t)； θ ( t )，

使用欧拉方法[18]离散，固定时间步长 0<τ<1为**

x(t+τ)=x(t)+τgnn(𝒢，x(t)； θ ( t ))。

每次迭代对应于一个 GNN 层，该层通常可以有一组不同的参数 θ ( t )。

如何实现上述等式中的函数“GNN”是不同图形神经网络架构之间的关键区别。卷积类型的 gnn[19]将共享线性变换应用于特征(可学习的d×d‘信道混合’矩阵 W 和ω**)，随后沿边缘传播(通过归一化邻接矩阵**‘扩散’)，并可能进行元素式非线性激活 σ 😗***

X(t+τ)=X(t)+▽(—X(t)ω(t)+āX(t)【T24

选择ω=W=I和 σ= id 恢复了我们之前看到的离散化图形扩散方程。由 Thomas Kipf 和 Max Welling [5]介绍的最简单的图卷积模型之一 GCN 的残差版本是上述模型的特例，其中ω= 0。

我们的例子展示了 GNN 建筑的通常设计过程，从参数化一个演化方程开始。我们认为，另一种方法，即参数化能量并导出 GNN 作为其离散梯度流，提供了更好的可解释性，并导致更有效的架构。这是我们 GRAFF 方法的精髓:我们对一类可以写成梯度流的 gnn 感兴趣**

ẋ(t)=−∇ℰ(𝒢，x(t)； θ ( t )，

一些参量能量ℰ(.； θ ，参数 θ 通过任务损失函数的反向传播学习。

能量和演化方程之间的联系提出了理解和设计 GNNs 的双重水平:从能量到演化方程，我们导出了更有原则和更有效的图形卷积模型版本，作为 Dirichlet 型参数能量族的梯度流。我们表明，这种模型具有避免过度平滑的理论保证和处理嗜异性数据的能力。

相反，从演化方程到能量，我们证明了许多现有的非线性图卷积模型，尽管不是梯度流，仍然可以在我们的框架内进行分析。特别地，我们证明了它们的演化方程降低了前面提到的狄利克雷型能量。

从能量到演化方程

让我们考虑一族二次能量

ℰᶿ(x)=∑ᵤ⟨xᵤ，ωxᵤ⟩∑ᵤᵥāᵤᵥ⟨x*， Wx*****

由矩阵ω和 W 参数化。我们称ℰᶿ为“广义参数狄利克雷能量”，因为经典ℰᴰᴵᴿ是它的特例[20]。****

物理解释。 ℰᶿ是与粒子系统(图中的节点，其在特征空间中的位置由矩阵 X 表示)相关联的能量，可以解释如下:第一项表示作用于所有粒子的‘外部’能量。第二项考虑了沿着图的边缘的成对相互作用，因此代表了粒子系统的“内部”能量。成对交互由通道混合矩阵 W 控制。第二能量项的最小化使得相邻节点的特征xᵤ*、xt20】ᵥ沿着对应于正特征值的特征向量 W 吸引。同样的， W 的负本征值诱发斥力【21】。*****

****梯度流动。ℰᶿ的梯度流量由下式给出

ẋ(t)= −∇ℰ(x(t)=-x(t)(ω+ωᵀ)/2++x(t)(w+wᵀ)/2.****

由于ω和 W 以对称形式出现在梯度流中，在不失一般性的情况下，我们可以假设它们是对称的:**

ẋ(t)=-x(t)ω+āx(t)w。

当以固定时间步长 τ、离散化时，该演化方程成为具有共享对称权重的图卷积模型

X(t+τ)=X(t)+τ(-X(t)ω++X(t****

由于ω和 W 独立于层 t 。逐层共享权重将一个 L 层卷积 GNN 中的参数总数从 2dL 减少到 d 。重要的是，对称约束不会削弱 GNN 的表现力[22]。**

格拉夫诱导的排斥和吸引动力学的例子:节点位置代表它们的特征坐标，颜色是标签。斥力沿着特征空间的 x 轴(W的负特征向量的方向)发生，引力沿着 y 轴(W的正特征向量发生。

****动力学中的显性效应。我们对 GNN 粒子系统的物理解释允许分析其梯度流诱发的动力学。吸引力使边缘梯度最小化，产生平滑效应(“模糊”)，放大了图中节点特征的低频[23]。另一方面，排斥力增加了边缘梯度，产生了增强高频的“锐化”效应。

这可以通过监测沿归一化解的狄利克雷能量来定量表示:如果在极限ℰᴰᴵᴿ(x(t)/| |x(t)| |)趋向于零，我们就有了低频主导的 (LFD)动力学。在收敛到图的拉普拉斯最大特征值的情况下，我们称动力学高频 支配(HFD)【24】。****

嗜同性(左)和嗜异性(右)图表示例。不同类型的节点用颜色编码。

多项研究表明，LFD 过程对于同形图中的节点分类是成功的。直观地，在这样的图中，邻居包含相似的信息，并且平滑过程聚集邻居，同时平均掉噪声。在异嗜性情况下，平滑通常是有害的，因为高频成分可能包含更多相关信息【27】。因此，一个理想的 GNN 模型必须通过能够诱导 LFD 或 HFD 动力学来适应这两种相反的情况。**

我们表明，基于扩散的模型，如连续 GNN [28]，PDE-GCN-D [29]，和图神经扩散 (GRAND) [13]无法诱导 HFD 动力学，因此可能会在嗜异性设置中遭受可预见的痛苦[30]。其中一个原因是，GRAND 等方案不允许通道混合:GRAND 在节点特征的每个通道上独立地执行非线性扩散，这可以被解释为一种图形注意力[31]的形式。

另一方面，根据w【32】的光谱，通过离散化我们的参数能量ℰᶿ的梯度流获得的格拉夫模型可以学习成为 LFD(主要是边缘方向吸引)或 HFD(主要是边缘方向排斥)。这使得格拉夫既适用于嗜同性也适用于嗜异性。

具有受控同质性的合成 Cora 数据集上的节点分类实验。GCN [5]通过利用节点特征的局部相似性，在高同质性的情况下表现良好；当同质性低时，这变成导致性能恶化的缺点。多层感知器(MLP)通过独立考虑每个节点的特征而忽略了图的结构。这使得 MLP 对低同性免疫，但也无法利用高同性。我们受物理学启发的格拉夫模型在两种情况下都工作得很好，因为它能够诱导低频和高频主导的动力学。图改编自[6]。

*格拉夫系统动态的驱动因素是拉普拉斯图{ λₗ }的频谱和通道混合矩阵{ₖ}【33】的频谱的相互作用。 W 的正特征值(ₖ>t13】0)放大低频(λₗt29】1)，负特征值(ₖ>t17】0)放大高频(λₗt31】1)[33 ]。

如果 W 的负特征值比正特征值【35】大得多，那么排斥力和高频占主导地位。在相反的情况下，低频占主导地位，导致极限t→∞1，36】中的过度平滑。

此外，负特征值{ ₖ < 0}的影响等同于翻转边的符号；这是为嗜异性数据集[37]提出的一种启发式方法，最近在我们关于神经层扩散 T26 的 NeurIPS 论文[4]中也被赋予了代数拓扑动机。

基普夫&韦林公司

我们应该强调的是，虽然 GRAFF 是一个允许将 gnn 导出为任何能量泛函的离散梯度流的通用框架，但是从我们的二次能量ℰᶿ中产生的模型是标准的卷积型 gnn。梯度流形式主义为他们的行为以及如何做出正确的架构选择提供了重要的见解。

我们的分析的一个结果是，如果信道混合矩阵具有足够负的特征值，卷积 GNNs 可以处理图异构。这与图形 ML 文献中经常重复的相反的“民间传说”陈述相矛盾。

然而，有一个重要的细微差别:由于我们使用欧拉离散化，我们总是有一个残差 GCN 模型。这个架构特征被证明是至关重要的:我们证明了一个没有剩余连接的模型(即迭代公式为X**(t+τ)=τāX(t)W最初由 Kipf 和 Welling [5]提出)只能诱导独立于W的谱的 LFD 动力学******

其次，我们的模型是残差 GCNs 的特定版本，其中信道混合矩阵是对称的，并且跨层共享。这也与 graph ML 社区中的常见做法相矛盾:通常，多层 GCN 模型每层都有不同的通道混合矩阵，并且还包括非线性激活[39]。我们通过实现 GRAFF 模型来证明这是不必要的，其中演化方程是线性的，唯一的非线性是在特征编码器和解码器中。

不同同质性水平数据集上的节点分类精度。GRAFF 及其非线性版本(GRAFF-NL)实现了与最近一些专门为嗜异性设置设计的方法(如 GGCN 和 GPRGNN)相当或更好的结果，同时在计算复杂性和参数数量方面明显更轻便。表来自[6]。

考虑到我们的理论和实验结果，简单的图卷积证明了简单的图卷积是正确的:我们得出结论，简单的图卷积在许多实际情况下足够强大，其性能与复杂得多的 GNN 模型相当，甚至更好。

简单图卷积模型反击。原始迷因:米哈伊尔高尔金。

从演化方程到能量

梯度流形式主义为 GNNs 的设计带来了一种新的思维模式:我们不是将演化方程参数化，而是将梯度流最小化的能量参数化[41]。我们已经证明，通过这种方式，人们可以做出更明智的设计选择，并为 GCNs 等“旧”模型带来新的生命。

人们可能想知道如何处理现有的进化方程不是梯度流的 gnn？GRAFF 在这种情况下仍然提供了重要的见解:例如，我们表明，如果权重是对称的，使用非线性激活的更一般的卷积模型仍然会降低能量ℰᶿ[42]——再次注意，从通用近似的角度来看，这不是限制性的[22],事实上为在图形神经网络中使用对称权重提供了更具理论原则性的理由。

我们的分析概括了现有的结果[2，4],这些结果监测了用 ReLU 激活的 Kipf-Welling GCNs 中的狄利克雷能量ℰᴰᴵᴿ:我们考虑了更广泛的一类能量以及无限类非线性激活函数。我们相信，这种方法可以提供一种新的视角，通过考虑哪种能量泛函沿着学习的节点特征减少来分析新旧 GNNs 的学习动力学。

更广泛地说，GRAFF 是一种受 T2 物理学启发的图形学习方法，我们最近已经看到了几个这样的例子，包括我们自己的作品。这种方法的主要思想是使用物理系统作为学习的隐喻，并通过系统的状态来参数化解的空间。在某种意义上，这是对物理信息神经网络 (PINN)的补充，后者将物理定律作为其归纳偏差，以便更好地逼近现实生活中的物理系统。

受物理学启发的方法的一个重要方面是，它们带来了不同于 graph ML 中传统使用的工具。例如，GNNs 的表达能力通常通过诉诸消息传递和 Weisfeiler-Lehman 图同构测试【45】之间的等价性来分析。后者通常限制太多，因为它假设信息传播在输入图上完成，而在实施某种形式的图重布线的实际 gnn 中，情况往往不是这样[46]。

通过研究动力系统的渐近行为(例如，扩散方程[4]的极限)，人们可以表达 GNNs 的分离能力，而无需求助于 WL 形式。这种技术自然允许图形重新布线，这假定了对基础微分方程的不同离散化的解释。

我们的工作表明，物理启发的方法甚至可以在以前研究得很好的图形学习模型中提供新的见解，并将鼓励在这个方向上的更多研究。

[1] K. Oono 和 t .铃木，图神经网络对节点分类的表达能力呈指数级丧失 (2020) ICLR。

[2]蔡春华，王永元，.关于图神经网络过光滑问题的一个注记.(2020)arXiv:2006.13318 .

[3] J. Zhu 等，超越图神经网络中的同向性:当前的局限与有效设计 (2020) NeurIPS 。

[4] C .博德纳尔，f .迪·乔瓦尼等，神经束扩散:GNNs 中异嗜性和过度光滑的拓扑透视(2022) NeurIPS 。参见附带的博文。

[5] T. Kipf 和 M. Welling，带图卷积网络的半监督分类 (2017)， ICLR 。

[6] F. Di Giovanni，J. Rowbottom 等人，将神经网络图化为梯度流 (2022)，arXiv:2206.10991。

[7] E. Haber 和 L. Ruthotto，深度神经网络的稳定架构(2017) 逆问题 34 (1)。

[8] R. Chen 等，神经常微分方程 (2019) NeurIPS。

[9]梯度流可被视为最陡下降法的连续版本，该方法最初由 A.-L .柯西、méthode générale pour la résolution des systèmes d 'éequations simultanées(1847)Comptes Rendus de l ’ académie des Sciences提出，用于解方程组(该方法出现在术语梯度之前，后者由 Horace Lamb 于 2004 年提出术语“流”来自流体力学，粒子系统的一个重要设置。

[10]梯度流单调减少底层能量的事实源于∂/∂tℰ(x(t)= –||∇ℰ(x(t))| |。

[11] J .傅立叶，https://archive.org/details/bub_gb_TDQJAAAAIAAJ(1822)。傅立叶在 1807-1811 年间发展了后来成为同名的分析。这项工作在接下来的十年里没有被公开，因为他的职责是伊泽尔省的省长，这是一个由拿破仑亲自任命的高级职位(他在埃及的战役中就认识傅立叶)。****

[12] P .佩罗娜和 j .马利克，使用各向异性扩散的尺度空间和边缘检测 (1990)，PAMI12(7):629–639。

[13]例如，参见我们的论文 B. Chamberlain，J. Rowbottom 等人，GRAND:Graph Neural Diffusion(2021)ICML，附带的博文，以及其中的许多参考文献。

[14]我们使用对称归一化图拉普拉斯算子δ= I–ā，其中ā= dᐨᐟadᐨᐟ是归一化邻接矩阵。我们的分析可以针对拉普拉斯算子的其他变体进行重复，参见[6]中的附录 A.2。

[15]ℰᴰᴵᴿ的二次型表达式允许导出图傅立叶基(图拉普拉斯的正交特征向量)为φ= arg minₓtrace(xᵀδxs . t .xᵀx=I，这可以解释为狄利克雷能量意义上的“最光滑正交基”。

[16]更正确的说法是 X (0)在 ker(δ)上的投影。对于归一化的拉普拉斯算子，扩散方程的极限是节点度数的向量。对于非规格化的拉普拉斯δ= I-A，结果是一个常数向量。

[17]固定扩散在某些情况下是有用的。比如 D. Zhou 和 b . schlkopf 提出的标签传播(label propagation)，离散空间上的正则化(2005)，联合模式识别研讨会，是一个带边界条件(已知节点标签)的扩散方程，是很多直推式图 ML 问题的很好的基线。在最近的一篇论文中，E. Rossi 等人，关于在具有缺失节点特征的图上学习的特征传播的不合理有效性 (2021)，arXiv:2111.12128 表明特征传播在具有缺失特征的同形图上有效地工作。**

[18]欧拉离散化(也称为显式或前向方案)用前向时差、ẋ(t)≈(x(t+τ)–x(t)/代替时间导数这总是导致剩余*架构。*****

[19]我们在这里采用了我们书中的“GNN 风味”术语，M. M. Bronstein 等人，几何深度学习:网格、组、图、测地线和规范 (2021) arXiv:2104.13478。在这种情况下，卷积类型的 gnn 可以写成以下形式:X(t+τ)=AX(t))(更新由与特征无关的矩阵完成)， 注意力为x*(t+τ)=a(x(t)x(t)(特征相关矩阵值函数)消息传递*****

[20] ℰᶿ = ℰᴰᴵᴿ当ω=w=I。在[6]的附录 B.5 中，我们还表明ℰᶿ可以认为是一个离散版的谐波能量ℰ(x)=∫⟨∇x(u),∇x(u)⟩ₕdu一个流形嵌入x*:ℳ→ℝ*******

[21]参见[6]中的公式 10。直观上注意如果 x ᵤ 和 x ᵥ 是相邻节点特征并且都是满足wxᵤ*=xᵤ和 Wx 的特征向量 wxᵥ⟩=⟨xᵤ*， x ᵥ ⟩和我们看到，如果> 0 那么 x ᵤ 和 < 0 反之亦然。********

[22] S. X. Hu，S. Zagoruyko 和 N. Komodakis，探索深度神经网络中的权重对称性(2019) 计算机视觉和图像理解，187 表明具有对称权重的神经网络是通用近似器。

[23]本文中的“频率”是指归一化图拉普拉斯的频谱分解，提供了傅立叶基础的类比。节点特征可以写成拉普拉斯正交本征向量的线性组合，对应的特征值在 0 ≤ λₗ ≤ 2 的范围内。第零特征值对应于恒定的特征向量(使用谐波分析术语的‘DC’)；对应于较大特征值的特征向量不太光滑，并且具有较高的狄利克雷能量。

[24]见[6]中的定义 3.1。注意，LFD/HFD 动力学的定义是通用的，不要求演化方程是梯度流。

[25] J .克利茨佩拉等，扩散改善图形学习 (2019) NeurIPS 。

[26]吴等，简化图神经网络 (2019) 。

[27]经典例子是分离二部图的∈的最大特征向量。参见 D. Bo 等人，超越图卷积网络中的低频信息(2021) AAAI 。****

[28] L.-P. Xhonneux 等人，连续图神经网络 (2020) ICML 。

[29] M. Eliasof、E. Haber 和 E. Treister。PDE-GCN:由偏微分方程驱动的图形神经网络的新架构(2021) NeurIPS 。

[30]文献[6]中的定理 3.3。

[31]p . veli kovi 等人，图形注意网络 (2018) ICLR 。

[32]文献[6]中的定理 3.2。

[33]文献[6]中的定理 4.1。

[34]我们表明，可以根据图形和通道混合频率明确地写出每一层的学习节点表示，从而得出每一个主导效应。这种对动力系统的“剖析”也强调了 W 的光谱和特征向量比条目本身更重要。

[35]在[6]中的方程 13 的意义上。

[36] H. Nt 和 T. Maehara，重新审视图形神经网络:我们所拥有的只是低通滤波器(2019) arXiv:1812.08434v4。

[37]d . Bo 等人在《超越图形卷积网络中的低频信息》(2021)和 Y. Yan 等人在《同一枚硬币的两面:图形卷积神经网络中的异嗜性和过度平滑》(2021) arXiv:2102.06462 中使用了异嗜性数据集的负边缘加权。

[38]文献[6]中的定理 4.3。

[39]没有非线性激活(σ= id)anm-层 gcnx(t+τ)=σ(σ(āσ(ax(t)w 可以写成单层x**(t+)=τāᵐx*(t)w带 m -hop 扩散āᵐ通过吸收 这个特性在[26]中被用于一个被称为简化 GCN (SGCN)的建筑。这种方法的优点是扩散特征āᵐx可以预先计算，允许将 gcn 缩放到非常大的图，如我们的论文 Frasca 等人的sign:scalable inception graph neural networks(2020)icml workshop on graph re presentation learning and beyond以及附带的博客帖子所示。注意，这种简化不会发生在 GCN 的残差版本中，如[6]中的方程(34)所示。*********

[40]在[6]中的方程 17。

[41]我们注意到,“最小化”在这里指的是能量沿着演化方程的行为(即，在通过网络的正向传递期间),并且不同于用于学习的行为(即，通过反向传播最小化关于模型参数的一些特定任务损失函数)。

[42]文献[6]中的定理 5.1。在我们最近的工作中，Dirichlet 能量的指数衰减被用于形式化超光滑现象[43]。

[43] B. P. Chamberlain 等人， Beltrami 流和图形上的神经扩散 (2021) NeurIPS。

[44] T. K. Rusch 等人，图耦合振荡器网络 (2022) ICML 。

[45] B. Weisfeiler 和 A. Lehman，将图简化为标准形式和其中出现的代数(1968)Nauchno-techniceskaya informatisia2(9):12–16。WL 与用内射聚合器传递消息的等价性在例如 K. Xu 等人的文章中示出。图神经网络有多强大？ (2019) ICLR 。参见我们的博客文章。

[46]传统的 gnn 使用输入图来传播信息，通过这种方式获得反映图的结构和其上的特征的表示。然而，由于“瓶颈”导致来自太多节点的信息被“挤压”到单个节点表示中，一些图对信息传播不太友好，这种现象被称为“过度压制”。现代 GNN 实现通过将输入图与计算图解耦(或为计算目的对其进行优化)来处理这种现象，这是一套被称为“图重布线”的技术。在我们最近的论文 J. Topping，F. Di Giovanni 等人的通过曲率理解图的过度挤压和瓶颈(2022)ICLR中，我们将重布线与图曲率和 Ricci 流联系起来。参见我们的博客文章。

我们非常感谢大卫·艾纳德、尼尔斯·哈默拉、托马斯·基普夫、伊曼纽·罗西和康斯坦丁·鲁施对这篇文章的校对。关于图形深度学习的其他文章，请参见 Michael 在《走向数据科学》中的 其他帖子 ， 订阅他的帖子和 YouTube 频道 ，获取 中等会员 ，或关注他的https://twitter.com/mmbronstein

超越 Weisfeiler-Lehman 和普通消息传递的图神经网络

原文：https://towardsdatascience.com/graph-neural-networks-beyond-weisfeiler-lehman-and-vanilla-message-passing-bc8605fa59a

图形学习的新蓝图

基于图的物理学启发的连续学习模型允许克服传统 GNNs 的限制

消息传递范式多年来一直是图形深度学习的“战马”，使图形神经网络在从粒子物理到蛋白质设计的广泛应用中取得了巨大成功。从理论角度来看，它建立了与 Weisfeiler-Lehman 等级的联系，允许分析 GNNs 的表达能力。我认为，当前图形深度学习方案的“以节点和边为中心”的思维模式施加了不可逾越的限制，阻碍了该领域的未来进展。作为替代方案，我提出了受物理学启发的“连续”学习模型，该模型从微分几何、代数拓扑和微分方程领域开辟了一个新的工具宝库，迄今为止，这些领域在 graph ML 中基本上没有被探索过。

图片:Shutterstock。迷宫隐喻:多米尼克·比艾尼。

本文基于克里斯蒂安·博德纳尔、董晓文、本·张伯伦、大卫·艾纳德、法布里齐奥·弗拉斯卡、弗朗切斯科·迪·乔瓦尼、玛利亚·戈里诺瓦、皮埃特罗·里ò、朱利亚·路易斯、锡德·米什拉、吉多·蒙图法尔、伊曼纽·罗西、康斯坦丁·鲁施、尼娜·奥特、詹姆斯·罗博顿、杰克·托平、于·王光和斯特凡·韦布的近期作品。另见我之前关于 图神经网络通过微分几何和代数拓扑 的帖子。

图是抽象复杂的关系和交互系统的一种便捷方式。从社交网络到高能物理再到化学，图结构数据的日益突出(所有这些都处理相互交互的对象，无论是人、粒子还是原子)，这些应用中的一系列初步成功，以及工业采用，使图的深度学习成为机器学习研究的最热门话题之一[1]。到目前为止，图形神经网络(GNNs)是图形 ML 方法中最常见的，并且在撰写本文时，是最流行的神经网络架构之一[2]。

图形抽象了复杂的关系和交互系统。从左到右显示:分子图(代表构成分子的原子之间的化学键)、社交网络(代表用户之间的关系和交互)、推荐系统(代表用户和产品之间的关联)。

GNNs 是如何工作的？图形神经网络将具有节点和边特征的图形作为输入，并计算取决于特征和图形结构的函数。消息传递型 gnn(也称为 MPNN [3])通过在相邻节点之间交换信息来传播图上的特征。典型的 MPNN 架构包括几个传播层，其中每个节点基于其邻居特征的集合进行更新。不同形式的聚合函数(是参数化的，其参数在训练期间学习)产生了三种不同的图形神经网络“味道”:【卷积】(相邻特征的线性组合，权重仅取决于图形的结构)(线性组合，权重也取决于特征)(一般非线性函数)【4】。在这三种味道中，后者是最普遍的，而前者可以被看作是信息传递的特例。**

GNNs 的三种“味道”，从左到右:卷积、注意力和一般非线性消息传递味道。所有这些都是信息传递的形式。图改编自 P. Velič ković。

传播层由基于下游任务学习的参数构成。典型的用例包括节点 嵌入(将每个节点表示为向量空间中的一个点，以这种方式，这些点的接近程度恢复了原始图的连通性，这种任务称为“链接预测”)，节点方式的分类或回归(例如，推断社交网络用户的属性)，或图方式的预测，通过进一步聚合节点方式的特征(例如，预测分子图的化学属性)。

消息传递 GNNs 怎么了？

D 尽管 GNNs 在所有方面都取得了令人印象深刻的成功，并且最近的研究具有显著的广度和深度，但公平地说，当前图形深度学习方案的主要模型是采用图形并通过消息传递的方式沿其边缘传播节点信息。我相信正是这种“以节点和边缘为中心”的思维模式设置了阻碍该领域未来发展的主要障碍。我在下面概述了当今一般 gnn 的一些突出的局限性:

魏斯费勒-雷曼类比是有局限性的。适当选择求和等局部聚合函数[5]使得消息传递等同于 Weisfeiler-Lehman 图同构测试[6]，允许图神经网络从信息在其上传播的方式中发现图的某些结构。这种与图论的重要联系[7]已经产生了关于 GNNs 表达能力的多种理论结果，确定了图上的某些函数是否可以通过消息传递的方式来计算[8]。然而，这种类型的结果通常不能说明这种表示的效率(即计算一个函数需要多少层)【9】，也不能说明 GNNs 的泛化能力。

Dominique Beaini 为 Weisfeiler-Lehman 测试提出了一个比喻:试图通过在没有地图的情况下行走来理解迷宫的结构。位置编码提供了迷宫的“地图”，而重新布线则提供了爬过“墙”的梯子。

Weisfeiler-Lehman 算法甚至无法检测简单的图形结构，如三角形，这让试图将信息传递神经网络用于分子图形的从业者非常失望:例如，在有机化学中，环等结构非常丰富，并在分子行为方式中起着重要作用(例如，芳香环因其在萘等具有强烈气味的化合物中的突出地位而得名)。

十氢萘(左)和双环戊基(右)的两个分子图的例子，它们在结构上不同(一个有 6 个环，另一个有 5 个环)，但是不能通过 Wesifeiler-Lehman 测试来区分。

在过去的几年中，已经提出了几种更具表现力的 GNN 模型的方法。这些包括 Weisfeiler-Lehman 层次结构中的高维同构测试10，将 wes feiler-Lehman 测试应用于子图集合[11]，或者对图的节点进行“着色”的位置或结构编码[12]，从而帮助打破“混淆”Weisfeiler-Lehman 算法的规律性。位置编码是迄今为止在变形金刚[13]中流行的最常见的技术，现在在 GNNs 中无处不在。虽然存在多种位置编码，但公平地说，特定的选择是依赖于应用程序的，而是凭经验的。

位置编码示例。从左到右显示:随机特征、拉普拉斯特征向量(类似于变形金刚中使用的正弦曲线)、结构特征(三角形和矩形的数量)。

图重布线打破了 GNNs 的理论基础。【GNNs 和 CNN 之间的一个重要而微妙的区别是，图形既是输入的部分，也是的计算结构。传统的 gnn 使用输入图来传播信息，通过这种方式获得反映图的结构和其上的特征的表示。然而，由于某些结构特征(“瓶颈”)，一些图对信息传播不太友好，导致来自太多节点的信息被“挤压”到单个节点表示中，这种现象被称为“过度挤压”[14]。****

现代的 GNN 实现通过将输入图与计算图解耦(或者为了计算的目的对其进行细化)来处理这种现象，这种技术被称为“图重布线”。重新布线可以采取邻域采样的形式(如 GraphSAGE [15]中所做的，最初是为了处理可扩展性)、虚拟节点[16]、连通性扩散[17]或进化[18]或者节点和边缘丢失机制[19]。变形金刚和 GAT [20]等注意力型 gnn 通过给每条边分配不同的权重，有效地“学习”了一个新图，这也可以理解为一种“软”重新布线的形式。最后，“潜在图形学习”方法建立一个特定任务的图形，并在每一层更新它21也可以归入这一类。总的来说，如果说几乎没有现代 GNN 模型在原始输入图上传播信息，这可能只是稍微夸大了情况。

GNNs 中使用的不同图形重布线技术。从左到右:原图、邻域采样(如 GraphSAGE [15])、注意(如 GAT [20])、连通性进化(如 DIGL [17])。

然而，这对于依赖于消息传递的等价性和 Weisfeiler-Lehman 测试的理论分析来说是个坏消息，weis feiler-Lehman 测试从信息在图上传播的方式获得对图的描述。重新布线打破了这种理论联系，将我们置于机器学习中并不罕见的情况:理论上可以分析的模型与实践中使用的模型并不相同。

图的“几何”太差。**图形神经网络可以作为“几何深度学习蓝图”[22]的一个实例获得，这是一个群论框架，允许从数据下的域的对称性中导出深度学习架构。在图的情况下，这种对称性是节点置换，因为图没有规范的节点排序。由于这种结构特征，在图上局部操作的 MPNNs 必须依赖于置换不变特征聚合函数，这意味着图上没有“方向”的概念，并且信息的传播是各向同性的【23】。这种情况与在连续域、网格甚至网格上学习明显不同[24]，并且是对 GNNs 的早期批评之一，认为各向同性滤波器不是很有用[25]。**

左图:网格是具有局部欧几里得结构的离散流形。相邻节点被定义为旋转，允许“方向”的概念。右图:图的结构较少，相邻节点被定义为排列。

****图的“几何”太丰富了。“距离而非方向”的问题也与构建节点嵌入时遇到的问题有些关系，在构建节点嵌入时，某个空间中的节点表示之间的距离用于捕捉图的连通性(粗略地说，嵌入空间中靠近的节点预期由图中的边连接)。典型的用例是推荐系统，其中图嵌入用于在由节点表示的实体(例如，在 Twitter 上关注谁)之间创建关联(边)。

图形嵌入的质量和它们表达图形结构的能力主要取决于嵌入空间的几何形状及其与图形“几何形状”的兼容性。欧几里得空间是表示学习的真正“战马”，也是迄今为止最简单、最方便的工作对象，但对于许多自然图来说，它却是一个相当糟糕的选择:原因之一是欧几里得度量球的体积增长在半径上是多项式的，但在维度上是指数的[26]，而许多真实世界的图表现出指数的体积增长[27]。结果，嵌入变得“太拥挤”，迫使使用高维空间，这导致更高的计算和空间复杂度。

最近流行的一种替代方法是使用负曲线(双曲线)空间[28]，这种空间的指数体积增长与图[29]的指数体积增长更兼容。双曲几何的使用通常导致更低的嵌入维数，从而导致更紧凑的节点表示。然而，图通常倾向于异质(即，一些部分可能看起来像树，而其他部分像集团，具有非常不同的体积增长属性)，而双曲嵌入空间是同质的(每个点都具有相同的几何形状)。

此外，通常不可能在嵌入空间[30]中精确地表示一般图形的度量结构，即使该空间具有非欧几里德几何。因此，图嵌入不可避免地近似。然而，更糟糕的是，因为嵌入是用“链接预测”标准构建的，所以高阶结构(三角形、矩形等)的失真。)可能会大得无法控制[31]。在一些应用中，包括社会和生物网络，这种结构发挥着重要作用，因为它们捕捉更复杂的非配对相互作用和基序[32]。

图形主题是高阶结构的例子。这种结构已经在许多生物现象的模型图中观察到。图:米洛等人。

当数据的结构与底层图形的结构不兼容时，gnn 就会陷入困境。许多图学习数据集和基准对数据同向性做出默认假设(即相邻节点的特征或标签相似，或者，使用信号处理术语，“平滑”)。在这种设置下，即使简单的低通滤波(例如，取邻居平均值)也能很好地工作。早期的基准，包括仍然无处不在的 Cora 数据集，是在具有高度同向性的图上进行的，这使得 GNNs 的评估“太容易了”。

嗜同性(左)和嗜异性(右)数据集。在前一种情况下，节点特征或标签的结构与图的结构兼容(即，节点与其邻居“相似”)。相似节点用匹配颜色表示。

然而，当处理嗜异性数据时，许多模型显示出令人失望的结果，在这种情况下，必须使用更细微的聚合[33]。在这种情况下观察到的两个典型现象是完全避免使用邻居信息(因此 GNNs 本质上归结为节点式多层感知器)或“过度平滑”，即节点表示的现象随着 GNN 的每一层变得更加平滑，最终崩溃为单个点[34]。后一种现象也发生在嗜同性数据集，似乎是一些类型的 MPNNs 的更基本的困境，使得难以实现深度图学习模型 [35]。

****通常很难理解 GNNs 学什么。对深度学习系统的一个批评特别适用于 gnn:这些是难以解释的“黑箱”。虽然可解释性是一个有点模糊的范畴，很大程度上取决于旁观者的观点，但我们可以诚实地承认，在大多数情况下，我们并不真正理解 gnn 所学的东西。最近的几项工作试图通过以紧凑的子图结构和在 GNN 的预测中起关键作用的节点特征的小子集的形式为基于 GNN 的模型提供“解释”来减轻这一缺点[36]。潜在图形学习架构[21]学习的图形也可以看作是“解释”的一种形式。

限制通用的消息传递函数有助于排除不可信的输出，并确保 GNN 学习的内容有意义，并在特定领域的应用中得到更好的理解。特别是，有可能赋予消息传递额外的“内部”数据对称性，以便更好地“理解”潜在的问题[37]。一个完美的例子是 E(3)-等变消息传递，它正确地处理了分子图中的原子坐标，最近为蛋白质结构预测架构的胜利做出了贡献，如 AlphaFold [38]和 RosettaFold [39]。

另一个例子是 Miles 和 Kyle Cranmer 合著的工作(没有家庭关系)[40]，其中在多体动力系统上学习的消息传递功能被符号公式取代，允许“学习物理方程”。最后，有人试图将 GNNs 与因果推理[41]联系起来，在这种情况下，人们试图构建一个解释不同变量之间因果关系的图。总体来说，这还是一个处于起步阶段的研究方向。

不同的“可解释的”GNN 模型(从左到右):图形解释器36，潜在图形学习[21]和等变信息传递。

大多数 GNNs 的实现都是硬件无关的。当今的大多数 gnn 依赖于 GPU 实现，并默认数据适合内存。在处理生物和社交网络等大型图表时，这往往是一厢情愿的想法。在这种情况下，了解底层硬件的限制，如不同的带宽和内存层次的延迟，并有利地使用它是至关重要的。大致来说，同一物理内存中的两个节点和不同芯片上的两个节点之间的消息传递成本(例如，在延迟和功耗方面)可能存在数量级的差异。让 GNNs 对现有的硬件友好是一个重要而又经常被忽视的问题。考虑到设计新芯片所需的时间和精力，以及机器学习技术的发展速度，开发新型以图形为中心的硬件是一个更大的挑战。

“连续”模型作为图形学习的新蓝图

当前“离散”gnn 的一个新兴和有前途的替代方案是“连续”学习模型，其受物理系统的启发，并从微分几何、代数拓扑和微分方程领域开辟了一个新的工具宝库，迄今为止在 graph ML 中基本上没有探索过。

****把基因想象成连续的物理过程。我们可以考虑在连续时间内在某个域(也可以是连续的，例如流形，并离散为图)上发生的物理过程(代替离散层)，而不是在图上传递多层消息。时空中某一点的过程状态，取代了 GNN 层所产生的图形中某个节点的潜在特征。该过程由一组参数(代表底层物理系统的属性)控制，这些参数取代了消息传递层的可学习权重。

从经典和量子系统中可以构建出大量不同的受物理启发的过程。在一系列论文[42–44]中，我们已经表明，许多现有的 gnn 可能与扩散过程有关，这可能是传播信息的最“自然”的方式，但其他更奇特的方式，如耦合振荡器系统[45]也是可能的，并可能提供某些优势。

图形耦合振荡器系统的动力学[45]。

连续系统在时间和空间上都可以离散化。空间离散化，以连接连续区域上邻近点的图形的形式，并且可以在整个时间和空间中改变。这种学习范式彻底背离了传统的 Weisfeiler-Lehman 方案，该方案受到基础输入图假设的严格限制。更重要的是，它带来了一套新的工具，至少在原则上允许解决现有图论技术目前无法解决的重要问题。

2D 拉普拉斯算子的不同离散化。

作为最优控制问题的学习。过程在给定时刻的所有可能状态的空间，可以看作是可以表示的函数的一个“假设类”。以这种方式学习被提出为最优控制问题[46]，即，是否可以控制过程(通过选择参数空间中的轨迹)以使其达到某个期望的状态。表达能力可以表述为是否可以通过在控制过程的参数空间中适当选择轨迹来达到给定的功能(使用最优控制理论的术语“可达性”)；效率与达到某个状态需要多长时间有关；而泛化关系到这个过程的稳定性。

作为控制问题的学习:飞机是一个物理系统的隐喻，其 xyz 坐标(“系统状态”)通过操纵推力、副翼和方向舵(“参数空间”)来控制。

****GNNs 可以从离散化的微分方程中导出。物理系统的行为通常由微分方程控制，其解产生系统的状态。在某些情况下，这种解决方案可以推导出一个封闭的形式[47]，但更普遍的是，一个人不得不求助于数值解决方案的基础上适当的离散。经过一个多世纪的研究，数值分析文献中积累的不同迭代求解器的财富为图形深度学习提供了潜在的全新架构。

例如，我们在[42]中表明，GNNs 的注意力味道可以解释为离散化的扩散 PDEs，具有使用显式数值方案求解的可学习的扩散率。在这种情况下，求解程序的每次迭代(时间上的离散步长)都对应于 GNN 的一个图层。更复杂的求解器，例如使用自适应步长或多步方案，目前在 GNN 建筑的“动物园”中没有直接的类比，但可能会导致未来的建筑洞察力。隐式方案需要在每次迭代中求解线性系统，可以解释为“多跳”滤波器[48]。此外，数值方案具有稳定性和收敛性保证，当它们工作时提供条件，当它们失败时提供理解[49]。

数值解算器可以是硬件友好的。迭代求解器比数字计算机更古老，从数字计算机诞生的那一刻起，它就必须意识到底层硬件并有效地利用它。科学计算中的大规模问题通常必须在计算机集群上解决，这些问题在集群中至关重要。

图形深度学习的“连续”方法允许以与模拟它们的硬件兼容的方式离散化基础微分方程，潜在地利用来自超级计算社区的大量文献，例如区域分解技术【50】。具体而言，可以使图形重新布线和自适应迭代求解器知道存储器层级，例如，在不同物理位置的节点之间执行少量不频繁的信息传输步骤，而在相同物理存储器中的节点之间执行更频繁的步骤。

****将进化方程解释为与物理系统相关的能量泛函的梯度流提供了对学习模型的洞察。许多物理系统都有相关的能量泛函(有时也包含某些对称性或守恒定律)，其中控制系统动力学的微分方程是最小化梯度流[51]。例如，扩散方程最小化了狄利克雷能量[42],其非欧几里得版本(贝尔特拉米流)最小化了波利亚科夫泛函[43],给出了学习模型正在做什么的直观理解。利用最小作用量原理，某些能量泛函产生双曲方程，如波动方程。这类方程的解是“波动的”(振荡的)，与典型的 GNNs 动力学有很大的不同。

分析此类流量的极限情况是一项标准工作，可提供对模型行为的深刻见解，否则很难获得这种见解。例如，在我们最近的论文【44】中，我们证明了传统的 GNNs(类似于各向同性扩散方程)必然导致过度光滑，并且只有在同质性假设下才具有分离能力；通过在图上使用额外的结构(细胞束)，可以获得更好的分离能力[52]。在另一篇最近的论文[45]中，我们证明了一个振荡系统避免了极限中的过度振荡。这些结果可以解释为什么在一些 GNN 建筑中会出现某些不良现象，以及如何设计建筑来避免这些现象。此外，将流动的极限情况与分离联系起来揭示了模型表达能力的界限。

图形可以被赋予更丰富的结构。我们已经提到，图形可能同时“太差”(即无法捕捉非成对关系等更复杂的现象)和“太丰富”(即难以在同质空间中表示)。处理前一个问题的方法是用额外的结构来“丰富”图。一个很好的例子是前面提到的分子图，其中包含环(图形术语中的环)，化学家将其视为单个实体，而不仅仅是原子和键(节点和边)的集合。

在一系列工作[53–54]中，我们展示了图可以被“提升”到更高维度的拓扑结构，称为单纯型- 和细胞复合体，在此基础上可以设计一个更复杂的消息传递方案，不仅允许在传统 GNNs 中的节点之间传播信息，还允许在环(“细胞”)等结构之间传播信息。“提升”操作的适当构造使得这种模型比传统的 Weisfeiler-Lehman 测试更具表现力[55]。

左图:将图形提升为细胞复合体。右图:手机信息传递。图改编自[54]。

在最近的另一篇论文【44】中，我们展示了通过给节点和边分配向量空间和线性映射，图可以配备一个额外的“几何”结构，称为细胞层。传统的 GNNs 隐含地假设一个图具有平凡的底层，这反映在相关的扩散方程的性质和图的拉普拉斯算子的结构中。与传统的 gnn 相比，使层非平凡(并可从数据中学习)产生更丰富的扩散过程，并对其渐近行为给予更大的控制。例如，适当选择的层结构上的扩散方程可以在有限的多个类别中分离，即使在嗜异性设置中[52]。

从几何角度来看，层结构类似于连接，这是微分几何中描述向量在流形上平行传输的概念【56】。从这个意义上来说，我们可以把层学习看作是一种依赖于下游任务来进化图的“几何”结构的方式。我们表明，通过将层的结构组(使用代数拓扑术语的“限制图”)限制到特殊的正交组，允许节点特征向量仅旋转，可以获得有趣的见解。

建立在图上的细胞层由连接到每个节点的向量空间和连接它们的线性“限制图”组成。在几何术语中，这可以被认为是赋予图形“几何”，而限制映射类似于连接。

图中“几何”结构的另一个例子是曲率的离散模拟，这是微分几何领域中描述流形局部行为的标准工具。在[18]中，我们表明负图 Ricci 曲率产生篡改图上信息流的“瓶颈”,并导致 GNNs [14]中的过压制现象。离散 Ricci 曲率说明了在许多应用中很重要的高阶结构(三角形和矩形)。这种结构对于传统的图嵌入来说“太丰富了”，因为图是异质的(具有非恒定曲率)，而通常用于嵌入的空间，甚至是非欧几里得空间，是同质的(恒定曲率)。

在另一篇最近的论文[57]中，我们展示了一种具有可控 Ricci 曲率的异构嵌入空间的构造，可以选择这些嵌入空间来匹配图的曲率，从而不仅可以更好地表示邻域(距离)结构，还可以更好地表示更高阶的结构，如三角形和矩形。此类空间被构造为齐次和旋转对称流形的乘积，并允许使用标准黎曼梯度下降法进行有效优化[58]。

左图:具有恒定的正、零和负 Ricci 曲率的空间形式(球面、平面和双曲面)及其具有相应离散 Forman 曲率的图形类比(团、网格和树)。中间:一个乘积流形(圆柱体可以认为是一个圆和一条线的乘积)。右图:变曲率异质流形及其图形类比。详见[57]。图:弗朗西斯科·迪·乔瓦尼。

****位置编码可以被视为域的一部分。将图形视为连续流形的离散化，可以将节点位置和特征坐标视为同一空间的不同维度。在这种情况下，该图可用于表示由这种嵌入诱导的黎曼度量的离散模拟，与嵌入相关的调和能量是狄利克雷能量的非欧几里得扩展，在弦理论中称为波利亚科夫泛函[59]。这种能量的梯度流是一个扩散型方程，它发展了位置和特征坐标[43]。在节点的位置上构建图形是特定任务图形重新布线的一种形式，它也随着扩散的迭代(层)而改变。

通过重新布线的 Beltrami 流，Cora 图的位置和特征分量的演变(颜色表示特征向量)。动画:詹姆斯·罗博特姆。

****域的进化取代了图的重布线。扩散方程也可以应用于图的连通性，作为预处理步骤，旨在改善信息流和避免过度抑制。克利茨佩拉等人[17]提出了一种基于个性化页面排名的算法，这是一种图形扩散嵌入的形式。在[18]中，我们分析了这个过程，指出了它在异构环境中的问题行为，并提出了一个替代的图形重布线方案，该方案是由 Ricci 流启发的。这种重新布线减少了导致图形瓶颈的负向弯曲边的影响。 Ricci 流是流形的几何演化方程，非常类似于应用于黎曼度量的扩散方程，并且是微分几何中流行且强大的技术，包括著名的庞加莱猜想的证明。更一般地说，我们可以考虑一个演化过程的耦合系统，而不是作为预处理步骤来执行图的重新布线:一个演化特性，另一个演化域(图)。

上图:一个哑铃形的黎曼流形，具有负弯曲的瓶颈(负曲率由冷色编码)，经历了基于曲率的度量演化，变得“更圆”，更少“瓶颈”。下图:基于曲率的图形重布线的类似过程，减少了瓶颈，使图形对消息传递更友好。参见我们的博客文章了解更多详情。图:杰克托普。

结束语

这真的是新的吗？我们必须避免陷入的一个陷阱是，新模型基于“名义上”的花哨的数学形式主义，而底层模型仍然大致做着上一代 gnn 所做的事情。例如，人们可以认为[44]中研究的层扩散是消息传递的一个特例。微分几何[18，43]和代数拓扑学[44，53–54]的工具使深刻的理论结果成为可能，这使我相信这已经不太可能了。然而，新的理论框架能带我们走多远，以及它是否能够解决该领域目前尚未回答的问题，仍然是一个开放的问题。

这些方法会在实践中实际使用吗？对于实践者来说，一个至关重要的问题是这些方法是否会产生新的更好的架构，或者仍然是一个脱离现实世界应用的理论装置，仅仅用于证明定理。我相信该领域将是务实的，通过拓扑和几何工具获得的理论见解将允许为现有的 GNN 架构做出更好的选择，例如，如何限制消息传递功能以及何时使用这种特定选择。

我们已经超越了信息传递吗？**最后，一个有点语义性质的问题是，所描述的方法是否仍然可以被称为“消息传递”。虽然观点可能各不相同，从将 GNN 的每一种形式都视为信息传递[60]到宣称需要超越这种范式[61]，但我有点不愿意使用这个术语。在数字计算机上的任何计算都是一种信息传递的形式。然而，在 GNNs 的严格意义上的中，消息传递是一个计算概念，通过将信息从一个节点发送到另一个节点来实现，这是一个固有的离散过程。另一方面，所描述的物理模型以连续的方式在节点之间共享信息(例如，在图耦合振荡器的系统中，一个节点的动态取决于其邻居在每个时间点的动态)。当描述这种系统的微分方程被离散化和数值求解时，相应的迭代方案确实通过消息传递来实现。

然而，人们可以假设使用这种物理系统的实际实现[62]或其他计算范例，如模拟电子学或光子学[63]。在数学上，基本微分方程的解有时可以以封闭形式给出:例如，各向同性扩散方程的解是具有高斯核的卷积。在这种情况下,“邻居”的影响被吸收到内核的结构中，没有实际的“消息传递”发生。因此，这种模式的连续性需要一个更合适的术语——例如，在此时没有更好的想法的情况下，“空间耦合”或“信息传播”。作为一种计算原语，当与其他角度(如本文介绍的角度)协同应用时，消息传递现在和将来都可能是有用的。

通过真实物理系统反向传播的深度学习。图片:Wright 等人[61]。

[1]参见 ICLR 2021 年统计数据。

[2]我把变形金刚算作 GNNs 的实例。

[3]我使用术语“GNN”来指代任意图形神经网络架构，使用“MPNN”来指代基于本地消息传递的架构。

[4]卷积风格的典型代表是从图形信号处理领域出现的“光谱”图形神经网络，如 M. Defferrard 等人具有快速局部光谱过滤的图形卷积神经网络 (2016) NIPS 和 T. Kipf 和 M. Welling，具有图形卷积网络的半监督分类 (2017) ICLR。Petar Velič ković在[16]中介绍了注意力的味道，尽管人们可以考虑由 F. Monti 等人开发的 Monet 架构，使用混合模型 CNN(2017)CVPR 在图形和流形上的几何深度学习，作为对位置坐标的注意力形式。J. Gilmer 等人在《量子化学的神经信息传递》( 2017 年)ICML 使用了一种通用的信息传递形式和名称 MPNN。

我们在 M. M. Bronstein 等人的“原型书”几何深度学习:网格、组、图形、测地线和量规 (2021) arXiv:2104.13478 中采用的风味命名是由 Petar Velič ković提出的。在我这种二分法的早期版本中(如 MLSS Moscow 2019 的教程)，我使用了术语*“线性”(其中特征计算的形式为 Y = AX ，其中 A 通常是图邻接矩阵的某种形式)、“线性特征相关”*(y=a(【t22 这比书中采用的符号更不通用，因为它假设基于总和的聚合。

[5]局部聚集函数必须是内射的。参见 K. Xu 等人图神经网络有多强大？ (2019) ICLR。

[6] B. Weisfeiler 和 A. Lehman，将图简化为标准形式以及其中出现的代数(1968)。信息技术 2(9):12–16。

[7]参见 C. Morris 等人，Weisfeiler 和 Leman go 机器学习:迄今为止的故事(2021) arXiv:2112.09992，了解历史笔记和深入综述。

[8] Z. Chen 等人用 GNNs (2019) NeurIPS 关于图同构测试与函数逼近的等价性，给出了图同构测试与置换不变图函数逼近的等价性。

[9]例如，N. Dehmamy，A.-L. Barabási，于荣，理解图神经网络在学习图拓扑中的表示能力 (2019) NeurIPS 表明，学习图上的某些函数(某些阶的图矩)需要某些最小深度的 gnn。另见 F. Geerts 和 J. L. Reutter,《图形神经网络的表达能力和近似性质》( 2022 年), ICLR。

[10]所谓的严格递增权力的“k-WL 检验”的等级制度。拉斯洛·巴拜将 k 的发明归功于 WL 与鲁道夫·马顿和尼尔·伊莫曼和埃里克·兰德的独立测试。参见 L. Babai，拟多项式时间内的图同构 (2015)，arXiv:1512.03547 第 27 页。

[11]已经有几篇论文提出在子图集合上应用 GNNs，包括我们自己的 B. Bevilacqua 等人，等变子图聚合网络 (2021) arXiv:2110.02910。见我们关于这个话题的帖子。

[12]通过计数局部子结构的结构编码由 G. Bouritsas，f .弗拉斯卡等人在 GNNs 的背景下提出通过子图同构计数提高图神经网络表达能力 (2020)。arXiv:2006.09252。另见 P. Barceló等人的《具有局部图形参数的图形神经网络》( 2021) arXiv:2106.06707。

[13] A. Vaswani 等人，注意力是你所需要的全部 (2017) NIPS。

[14]过度抑制现象不是 GNNs 独有的，以前在 seq2seq 模型中也观察到过。但是，在体积呈指数增长的图表中，这种情况会变得特别严重。参见 U. Alon 和 E. Yahav，关于图神经网络的瓶颈及其实际含义 (2020)。arXiv:2006.05205 和我们的论文[14]对这一现象进行了描述和分析。

[15] W. Hamilton 等人，大型图上的归纳表示学习 (2017) NIPS 使用邻域采样来应对可扩展性。

[16] P. W .巴塔格利亚等人，关系归纳偏差、深度学习和图网络(2018)，arXiv:1806.01261。

[17] J .克利茨佩拉等人，扩散改善图形学习 (2019) NeurIPS 通过个性化页面排名嵌入(一种“连通性扩散”的形式)使用重新布线。

[18] J. Topping，F. Di Giovanni 等人，通过曲率了解图的过度挤压和瓶颈 (2022) ICLR。

[19]丢弃可以在边或节点上完成，并且也导致更好的表达能力(原因类似于子图 GNNs)，参见例如 Y. Rong 等人， DropEdge:走向节点分类上的深度图卷积网络 (2020)和 P. A. Papp 等人， DropGNN:随机丢弃增加了图神经网络的表达能力 (2021) arXiv:2111.06283。

[20]p . veli kovi 等人，图形注意网络 (2018) ICLR 。

[21]最早的“潜图学习”架构之一是我们的工作 Y. Wang et al. 用于在点云上学习的动态图 CNN(2019)ACM Trans .点云上的图形 38(5):146，其中初始的“位置编码”(点的 xyz 坐标)表示数据的几何形状，图形用于在相关部分之间传播信息。A. Kazi 等人考虑了更一般的情况，用于图卷积网络的可微分图模块(DGM)(2020)arXiv:2002.04999，其中没有明显的数据几何，并且为手头的任务学习适当的“位置编码”。另见我的关于主题的博文。

[22]在我的 ICLR 主题演讲中有更多关于这方面的内容。

[23]在图中进行“各向异性”传播的尝试有几种，最近的一种是 D. Beaini 等人的《定向图网络》(2020)，arXiv:2010.02863，旧的一种是我们的论文 F. Monti，K. Otness，M. M. Bronstein，motif net:a motif-based Graph Convolutional Network for directed graphs(2018)，arXiv:1802.01572。必须提供某种形式的外部信息，例如，在 DGNNs 的情况下，图的拉普拉斯特征向量的梯度，以及在 MotifGNNs 的情况下，一些选择的子结构。

[24] D. Boscaini 等人，利用各向异性卷积神经网络学习形状对应(2016) NIPS。

[25]例如，见 Ferenc Huszar 的博客文章。

[26]回忆一下二维和三维体积的经典公式， πr 和 4π r /3:这些是 r 中的多项式。一个 2 n 维球的通式是 v =πⁿt20】rt22】ⁿ/n！，显示出对 n 的指数依赖性。

[27]社会和生物网络等现实世界的图表显示出等级结构和与负曲率相关的幂律度分布。

[28] Q. Liu，M. Nickel，D. Kiela，双曲图神经网络(2019)。

[29]参见，例如，m .博古等人，网络几何学 (2021)《自然评论物理学》3:114–135。

[30]更正式地说，不存在等距嵌入，即没有办法在欧几里得空间中表示图的距离度量。一个简单的例子是建立在球赤道上的三个点和极点上的一个点上的图，所有这些点都有单位测地线距离。这样的图不能嵌入任何有限维的欧几里得空间。

[31] C. Seshadhri 等人，富三角形复杂网络的低秩表示的不可能性(2020)，PNAS 117(11):5631–5637。

[32]r . Milo 等人在《网络主题:复杂网络的简单构建模块》( 2002)Science 298(5594):824–827 中提供了现实世界网络中高阶结构的经典证据。更多最近的结果，见 f .巴蒂斯顿等人,《超越成对相互作用的网络:结构和动力学》( 2020)物理学报告 874:1–92。

[33] J. Zhu 等，超越图神经网络中的同质性:当前的限制和有效设计(2020)，NeurIPS。

[34]在 H. Nt 和 T. Maehara 的《再访图形神经网络:我们拥有的只是低通滤波器》( 2019) arXiv:1812.08434v4 和 K. Oono 和 t .铃木,《图形神经网络指数地失去对节点分类的表达能力》( 2020) ICLR。

[35]见我有点争议的上一篇。从那时起，已经出现了几个非常深的 gnn，但总的来说，这似乎比其他深度学习架构更难。

[36] R. Ying 等人，GNNExplainer:为图形神经网络生成解释(2019)，NeurIPS

[37]在物理学中，通常区分空间的外部对称和场的内部对称。这在 Taco Cohen 的博士论文中解释得很透彻。

[38] J. Jumper 等人，用 AlphaFold 进行高度精确的蛋白质结构预测，Nature 596:583–589，2021。

[39] M. Baek 等人，使用三轨道神经网络准确预测蛋白质结构和相互作用，科学 373:871–876，2021。

[40] M. Cranmer 等人，从具有归纳偏差的深度学习中发现符号模型 (2020) arXiv:2006.11287

[41]m . ze EVI 等人将图形神经网络与结构因果模型联系起来(2021 年)arXiv:2109.04173。

[42] B. Chamberlain，J. Rowbottom 等人，GRAND:Graph Neural Diffusion(2021)ICML。

[43] B. P. Chamberlain 等人， Beltrami 流和图形上的神经扩散 (2021) NeurIPS。

[44] C .博德纳尔，f .迪·乔瓦尼等人，神经束扩散:对 GNNs 中异嗜性和过度光滑的拓扑透视(2022) arXiv:2202.04579。参见附带的博文。

[45] T. K. Rusch 等人,《图形耦合振荡器网络》( 2022 年)ICML。

[46]深度学习问题作为最优控制的观点已经在例如 M. Benning 等人的《深度学习作为最优控制问题:模型和数值方法》( 2019) arXiv:1904.05657 中讨论过。

[47]欧几里得域ℝ ⁿ 上的各向同性扩散方程的解析解作为与热核(δ初始条件下热方程的“基本解”)的卷积给出，这是形式为 h ( x ， y ，t)=(4πt)ⁿᐟexp()在非欧情况下，热核可以在拉普拉斯特征基中展开，并且是位置相关的(即 h ( x ， y ， t )不能像以前那样写成h(x-y， t )。热核已广泛用于计算机图形和几何处理文献，包括 J. Sun、M. Ovsjanikov 和 L. Guibas 的著名热核签名，这是一种基于热扩散的简明且可证明信息丰富的多尺度签名(2009 年)《计算机图形论坛》28(5):1383–1392。马克斯·奥夫斯贾尼科夫小组最近在网格深度学习的背景下使用了类似的想法，参见 n .夏普等人，扩散网:表面上的离散化不可知论学习(2020) arXiv:2012.00888。

[48]弗拉斯卡等人， SIGN:可扩展的初始图神经网络 (2020)关于图表示学习的 ICML 研讨会。

[49]在我们的框架和研究数值格式特性的典型环境之间有一个微妙但重要的区别。在后一种情况下，人们感兴趣的是获得给定偏微分方程的精确数值解。在我们的例子中，我们使用一个偏微分方程的解来参数化一个函数空间，而不是求解一个特定的方程。

[50]区域分解方法将一个大规模问题分解成较小的子问题，这些子问题可以在多处理器机器上并行独立解决。通信仅沿着相邻子域的界面发生。

【51】一个梯度流可以看作是变分问题中梯度下降的连续类比。它源于泛函的最优性条件(变分法中称为欧拉-拉格朗日方程)。

[52]关于分离能力的结果，参见我们论文[44]中的定理 13、14、16、18、19、21 和 23，关于过度光滑的结果，参见定理 25-28。

[53] C .博德纳尔，f .弗拉斯卡等人，魏斯费勒和雷曼 go 拓扑:消息传递单纯网络 (2021) ICML。

[54] C .博德纳尔、f .弗拉斯卡等人，魏斯费勒和雷曼 go cellular:CW Networks(2021)neur IPS。参见附带的博文。

[55]在某种程度上，更高维的 gnn 如 C. Morris 等人 Weisfeiler 和 Leman go neural:高阶图神经网络 (2019) AAAI，H. Maron 等人不变和等变图网络 (2019) ICLR，也可以归入这一类。

[56]联系是微分几何中描述流形上两个不同点处的切空间之间的关系的对象。它用于流形上向量的并行传输。关于图，A. Singer 和 H.-T. Wu 研究了离散版本，向量扩散图和连接拉普拉斯算子(2012)纯数学和应用数学通讯 65(8)，他们也使用了术语“连接拉普拉斯算子”(它是我们具有正交限制图的细胞层的特定设置)。具有正交消息传递的图形神经网络已经由例如 K. Guo，Orthogonal Graph Neural Networks(2021)arXiv:2109.11338 进行了探索。

[57] F. Di Giovanni，G. Luise 和 M. M. Bronstein，曲率感知图嵌入的异构流形(2022) arXiv:2202.01185。

[58]黎曼优化是一类约束优化方法，其中假设数据点位于一个流形上。黎曼优化通过在局部切空间中操作在流形上执行梯度下降，参见 N. Boumal 的优秀参考文献，光滑流形上的优化介绍 (2022)。在我们构造的非均匀流形中，旋转对称因子只有一个坐标，参见我们论文[56]的 4.1 节。

[59] A .波利亚科夫,《玻色子弦的量子几何》( 1981 年)《物理学通讯》B 103:207。

[60]p . veli kovi，信息一路向上传递(2022) arXiv:2202.11097。

[61]参见我们对 2021 年的预测。

[62] L. G. Wright 等人，用反向传播训练的深度物理神经网络(2022 年),《自然》601:549–555。

[63] R. Hamerly，深度学习的未来是光子 (2021) IEEE 频谱。

我感谢多米尼克·比艾尼、克里斯蒂安·博德纳尔、乔治·布里特萨斯、本·张伯伦、董小文、弗朗切斯科·迪·乔瓦尼、尼尔斯·哈默拉、哈盖·马龙、锡德·米什拉、克里斯多夫·莫利斯、詹姆斯·罗博顿和佩塔尔·韦利奇科维奇进行了富有成效的讨论和评论，其中一些内容非常充实，相当于“集体编辑”。不用说，任何遗留的遗漏或错误都是我的责任。

关于图形深度学习的其他文章，请参见《走向数据科学》中我的 其他帖子 ， 订阅我的帖子 和 YouTube 频道 ，获取 中等会员 ，或者关注我的

Python 中的图形神经网络

原文：https://towardsdatascience.com/graph-neural-networks-in-python-c310c7c18c83

简介和逐步实施

最近，图机器学习领域发展迅速，该领域的大多数模型都是用 Python 实现的。本文将介绍图形的概念以及使用 Python 处理图形的一些基本方法。之后，我们将创建一个图卷积网络，并让它在 PyTorch 的帮助下在现实世界的关系网络上执行节点分类。这里描述的整个工作流程可以从的 Colab 笔记本中获得。

什么是图？

一个图，在其最一般的形式下，仅仅是节点以及节点之间的一组边的集合。形式上，一个图 G 可以写成 G = (V，E) ，其中 V 表示节点， E 表示相应的边集。有两种主要类型的图，有向图和无向图。有向图的边从它们的原点 u 节点指向目标节点 v ，而无向图中的边是没有方向的，因此( u，v)∑e⇔(v，u)∑e .图可以用一个可以通过让每个节点索引特定的行和列来创建该矩阵。然后，边的存在可以被表示为邻接矩阵中的条目，意味着如果( u，v)∈E和 A [ u ， v ] = 0，则 A [ u ， v ] = 1，否则。如果图仅由无向边组成，邻接矩阵将是对称的，但是如果图是有向的，就不一定是对称的。**

为了在 Python 中操作图形，我们将使用非常流行的 networkx 库[1]。我们首先创建一个空的有向图 H :

**import networkx as nxH = nx.DiGraph()**

然后，我们将向图中添加 4 个节点。每个节点有两个特征，颜色和大小。机器学习问题中的图通常具有带有特征的节点，例如社交网络中某个人的姓名或年龄，然后模型可以使用这些特征来推断复杂的关系并进行预测。Networkx 附带了一个内置的实用函数，用于以列表形式填充带有节点的图形，此外还有以下特性:

**H.add_nodes_from([
  (0, {"color": "gray", "size": 450}),
  (1, {"color": "yellow", "size": 700}),
  (2, {"color": "red", "size": 250}),
  (3, {"color": "pink", "size": 500})
])for node in H.nodes(data=True):
  print(node)> (0, {'color': 'gray', 'size': 450})
> (1, {'color': 'yellow', 'size': 700})
> (2, {'color': 'red', 'size': 250})
> (3, {'color': 'pink', 'size': 500})**

图中的边被定义为包含源节点和目标节点的元组，因此例如边(2, 3)将节点 2 连接到节点 3。因为我们有一个有向图，所以也可以有一条指向相反方向的边(3, 2)。多条边可以作为列表的一部分添加到图表中，方式与节点相似:

**H.add_edges_from([
  (0, 1),
  (1, 2),
  (2, 0),
  (2, 3),
  (3, 2)
])print(H.edges())> [(0, 1), (1, 2), (2, 0), (2, 3), (3, 2)]**

现在我们已经创建了一个图表，让我们定义一个函数来显示关于它的一些信息。我们验证了该图确实是有向的，并且它具有正确的节点数和边数。

**def print_graph_info(graph):
  print("Directed graph:", graph.is_directed())
  print("Number of nodes:", graph.number_of_nodes())
  print("Number of edges:", graph.number_of_edges())print_graph_info(H)> Directed graph: True
> Number of nodes: 4
> Number of edges: 5**

绘制您正在使用的图表也非常有帮助。这可以通过使用nx.draw来实现。我们使用节点的特征来给每个节点着色，并在绘图中给每个节点指定它们自己的大小。因为节点属性是以字典的形式出现的，而且 draw 函数只接受列表，所以我们必须首先转换它们。生成的图看起来像是应该有 4 个节点、5 条边和正确的节点特征。

**node_colors = nx.get_node_attributes(H, "color").values()
colors = list(node_colors)node_sizes = nx.get_node_attributes(H, "size").values()
sizes = list(node_sizes)nx.draw(H, with_labels=True, node_color=colors, node_size=sizes)**

有向图，作者的图像。

让我们把有向图 H 转换成无向图 G 。之后，我们再次打印关于该图的信息，我们可以看到转换成功了，因为输出表明它不再是一个有向图。

**G = H.to_undirected()
print_graph_info(G)> Directed graph: False
> Number of nodes: 4
> Number of edges: 4**

奇怪的是，边的数量减少了一个。如果我们仔细观察，我们可以看到边(3, 2)已经消失了，这是合理的，因为一个无向边只能由一个元组来表示，在这种情况下是(2, 3)。

**print(G.edges())> [(0, 1), (0, 2), (1, 2), (2, 3)]**

当我们想象无向图时，我们可以看到边的方向消失了，而其他一切都保持不变。

**nx.draw(G, with_labels=True, node_color=colors, node_size=sizes)**

一个无向图，作者的图像。

空手道俱乐部网络

现在我们已经对如何在 Python 中处理图形有了一个高层次的理解，我们将看看一个真实世界的网络，我们可以使用它来定义一个机器学习任务。扎卡里的空手道俱乐部网络[2]就是为此而选择的。它代表了 w .扎卡里在七十年代研究的空手道俱乐部成员之间的友谊关系。如果两个人在俱乐部之外进行社交，则图中的一条边将他们连接起来。

空手道俱乐部数据集可通过 PyTorch Geometric (PyG ) [3]获得。PyG 库包含了对图形和其他不规则结构进行深度学习的各种方法。我们首先检查数据集的一些属性。它似乎只包含一个图形，这是意料之中的，因为它描述了一个俱乐部。此外，数据集中的每个节点被分配一个唯一代表每个节点的 34 维特征向量。俱乐部的每个成员都是机器学习术语中 4 个派别或类别之一的一部分。

**from torch_geometric.datasets import KarateClubdataset = KarateClub()
print("Dataset:", dataset)
print("# Graphs:", len(dataset))
print("# Features:", dataset.num_features)
print("# Classes:", dataset.num_classes)> Dataset: KarateClub()
> # Graphs: 1
> # Features: 34
> # Classes: 4**

我们可以进一步探索数据集中唯一的图形。我们看到该图是无向的，它有 34 个节点，每个节点有 34 个特征，如前所述。边用元组表示，一共有 156 个。然而，在 PyG 中，无向边被表示为两个元组，每个方向一个，也称为双向，这意味着在空手道俱乐部图中有 78 个唯一的边。PyG 只包括 A 中非零的条目，这就是为什么边是这样表示的。这种类型的表示被称为坐标格式，通常用于稀疏矩阵。每个节点都有一个标签， y ，它保存了相应节点属于哪个类的信息。该数据还包含一个train_mask,它具有我们在训练期间已知的基础事实标签的节点的索引。有 4 个真实节点，每个派系一个，现在的任务是推断其余节点的派系。

**data = dataset[0]print(data)
print("Training nodes:", data.train_mask.sum().item())
print("Is directed:", data.is_directed())> Data(x=[34, 34], edge_index=[2, 156], y=[34], train_mask=[34])
> Training nodes: 4
> Is directed: False**

我们将空手道俱乐部网络转换为 Networkx 图，这允许我们使用nx.draw函数来可视化它。节点根据它们所属的职业(或派别)进行着色。

**from torch_geometric.utils import to_networkxG = to_networkx(data, to_undirected=True)
nx.draw(G, node_color=data.y, node_size=150)**

扎卡里的空手道俱乐部网络，由作者图像。

半监督节点分类

当训练模型来执行节点分类时，它可以被称为半监督机器学习，这是用于在训练期间组合有标签和无标签数据的模型的通用术语。在节点分类的情况下，我们可以访问图中的所有节点，甚至是那些属于测试集的节点。唯一缺少的信息是测试节点的标签。

图卷积网络(GCNs)将用于对测试集中的节点进行分类。为了给出简单的理论介绍，图形神经网络中的层可以写成非线性函数 f :

以图的邻接矩阵 A 和某层的(潜在)节点特征l作为输入。图形神经网络的简单分层传播规则如下所示:**

其中 W 为第 l 个神经网络层的权重矩阵， σ 为非线性激活函数。将权重与邻接矩阵相乘意味着对每个节点的所有(1 跳)相邻节点的所有特征向量进行求和和聚合。但是，不包括节点本身的特征向量。

为了解决这个问题，Kipf 和 Welling [4]将单位矩阵添加到邻接矩阵中，并将这个新矩阵表示为*—=A+I。邻接矩阵的乘法也将改变特征向量的比例。为了抵消这个—*被对称地乘以其对角度矩阵，产生最终的 GCN 传播规则:

GCN 层已经是 what PyG 的一部分，它可以很容易地作为GCNConv类导入。与在普通神经网络中层叠层的方式相同，也可以层叠多个 GCN 层。具有 3 层 GCN 将导致三个连续的传播步骤，导致每个节点用来自 3 跳之外的信息进行更新。模型的第一层必须具有与每个节点的要素数量一样多的输入单元。与最初的 GCN 论文一致，除了最后一个维度被设置为 2 之外，潜在维度被设置为 4。这允许我们稍后将所学习的潜在嵌入绘制为二维散点图，以查看该模型是否设法学习对于属于同一类的节点来说相似的嵌入。双曲正切激活函数在 GCN 层之间用作非线性函数。输出层将二维节点嵌入映射到 4 个类中的 1 个。

**from torch.nn import Linear
from torch_geometric.nn import GCNConvclass GCN(torch.nn.Module):
  def __init__(self):
    super(GCN, self).__init__()
    torch.manual_seed(42)
    self.conv1 = GCNConv(dataset.num_features, 4)
    self.conv2 = GCNConv(4, 4)
    self.conv3 = GCNConv(4, 2)
    self.classifier = Linear(2, dataset.num_classes) def forward(self, x, edge_index):
    h = self.conv1(x, edge_index)
    h = h.tanh()
    h = self.conv2(h, edge_index)
    h = h.tanh()
    h = self.conv3(h, edge_index)
    h = h.tanh()
    out = self.classifier(h)
    return out, hmodel = GCN()
print(model)> GCN(
>   (conv1): GCNConv(34, 4)
>   (conv2): GCNConv(4, 4)
>   (conv3): GCNConv(4, 2)
>   (classifier): Linear(in_features=2, out_features=4, bias=True)
> )**

我们使用交叉熵作为损失函数，因为它非常适合于多类分类问题，并初始化 Adam 作为随机梯度优化器。我们创建一个标准的 PyTorch 训练循环，并让它运行 300 个周期。注意，虽然所有节点确实获得了对它们的节点嵌入的更新，但是仅针对训练集中的节点计算损失。在训练期间，损失急剧减少，这意味着分类效果良好。来自最后一个 GCN 层的二维嵌入被存储为一个列表，以便我们可以在训练期间动画化嵌入的演变，给出对模型的潜在空间的一些洞察。

**criterion = torch.nn.CrossEntropyLoss()
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)def train(data):
  optimizer.zero_grad()
  out, h = model(data.x, data.edge_index)
  loss = criterion(out[data.train_mask], data.y[data.train_mask])
  loss.backward()
  optimizer.step()
  return loss, hepochs = range(1, 301)
losses = []
embeddings = []for epoch in epochs:
  loss, h = train(data)
  losses.append(loss)
  embeddings.append(h)
  print(f"Epoch: {epoch}\tLoss: {loss:.4f}")> Epoch: 1    Loss: 1.399590
> Epoch: 2    Loss: 1.374863
> Epoch: 3    Loss: 1.354475
> ...
> Epoch: 299  Loss: 0.038314
> Epoch: 300  Loss: 0.038117**

Matplotlib 可以用来制作节点嵌入的散点图，其中每个点都根据它们所属的派系进行着色。对于每一帧，除了该时期的训练损失值之外，我们还显示该时期。最后，动画被转换成 GIF 格式，如下图所示。

**import matplotlib.animation as animationdef animate(i):
  ax.clear()
  h = embeddings[i]
  h = h.detach().numpy()
  ax.scatter(h[:, 0], h[:, 1], c=data.y, s=100)
  ax.set_title(f'Epoch: {epochs[i]}, Loss: {losses[i].item():.4f}')
  ax.set_xlim([-1.1, 1.1])
  ax.set_ylim([-1.1, 1.1])fig = plt.figure(figsize=(6, 6))
ax = plt.axes()
anim = animation.FuncAnimation(fig, animate, frames=epochs)
plt.show()gif_writer = animation.PillowWriter(fps=20)
anim.save('embeddings.gif', writer=gif_writer)**

节点嵌入的演变，作者图片。

GCN 模型设法线性分离不同类的几乎所有节点。这是令人印象深刻的考虑到它只给了每个派系一个标记的例子作为输入。

希望你对图形神经网络的介绍感兴趣。gnn 是非常通用的算法，因为它们可以应用于复杂的数据和解决不同类型的问题。例如，通过在我们的神经网络末端使用一些置换不变池(如 mean)来简单地聚集节点特征，它可以对整个图进行分类，而不是对单个节点进行分类！

[1] A. Hagberg，D. Schult 和 P. Swart，“使用 NetworkX 探索网络结构、动力学和功能”， SciPy2008 ，2008，【networkx.org】T2

[2] W .扎卡里，“小群体中冲突和裂变的信息流模型”， J. Anthropol .Res 。doi:10.1086/jar . 33 . 4 . 3629752

[3] M. Fey 和 J. Lenssen，“用 PyTorch 几何快速图形表示学习”， ICLR， 2019，pyg.org，麻省理工学院许可

[4] T. Kipf 和 M. Welling，“基于图卷积网络的半监督分类”， ICLR ，2016， arXiv: 1609.02907