2021年的第一盆冷水：有人说别太把图神经网络当回事儿-技术圈

数学算法俱乐部

日期： 2021年01月10日

正文共：4610字

来源：机器之心

图神经网络（GNN）是目前热门的研究方向，但我们是否应把注意力过多地放在这上面？数据科学家 Matt Ranger 从模型的本质、性能基准测试、实践应用等方面陈述了自己的观点。

图神经网络（GNN）是机器学习中最热门的领域之一，在过去短短数月内就有多篇优秀的综述论文。但数据科学家 Matt Ranger 对 GNN 却并不感冒。他认为这方面的研究会取得进展，但其他研究方向或许更重要。

博客链接：https://www.singlelunch.com/2020/12/28/why-im-lukewarm-on-graph-neural-networks/

机器之心对这篇博客进行了编译整理，以下是博客内容。

模型的关键是压缩

图经常被认为是一种「非欧几里得」数据类型，但实际上并不是。正则图（regular graph）只是研究邻接矩阵的另一种方式：

如上图所示，充满实数的矩阵却被称为「非欧几里得」，这很奇怪。

其实这是出于实际原因。大多数图都相当稀疏，因此矩阵中会包含很多 0。从这个角度看，非零数值非常重要，这让问题接近于（计算上很难的）离散数学，而不是（容易的）连续、梯度友好的数学。

有了全矩阵，情况会变得容易

如果不考虑物理领域的内容，并假设存在全邻接矩阵，那么很多问题就会迎刃而解。

首先，网络节点嵌入不再是问题。一个节点就是矩阵中的一行，因此它本身已经是数字向量。

其次，所有网络预测问题也都被解决。一个足够强大且经过良好调整的模型将只提取网络与附加到节点上的目标变量之间的全部信息。

NLP 也只是一种花哨的矩阵压缩

让我们把目光从图转移到自然语言处理（NLP）领域。大多数 NLP 问题都可以看成图问题，所以这并不是题外话。

首先，像 Word2Vec、GloVe 这类经典词嵌入模型只进行了矩阵分解。

GloVe 算法基于词袋（bag of words）矩阵的一种变体运行。它会遍历句子，并创建一个（隐式）共现图，图的节点是词，边的权重取决于这些单词在句子中一同出现的频率。之后，Glove 对共现图的矩阵表示进行矩阵分解，Word2Vec 在数学方面是等效的。

语言模型也只是矩阵压缩

NLP 中许多 SOTA 方法都离不开语言模型。以 BERT 为例，BERT 基于语境来预测单词：

这就使我们正在分解的矩阵从词对共现发展为基于句子语境的共现：

我们正在培养待分解的「理想矩阵」。正如 Hanh & Futrell 所说：

人类语言和语言建模具有无限的统计复杂度，但可以在较低层次上得到很好地近似。这一观察结果有两层含义：

我们可以使用相对较小的模型获得不错的结果；
扩大模型具备很大潜力。

语言模型解决了很大的问题空间，以至于从柯氏复杂性（Kolmogorov Complexity）角度来看，它们可能近似压缩了整个语言。庞大的语言模型可能记住了很多信息，而不是压缩信息。

我们能像语言模型一样对任意图执行上采样吗？

实际上，我们已经在做了。

我们将图的「一阶」嵌入称为通过直接分解图的邻接矩阵或拉普拉斯矩阵（Laplacian matrix）来运行的方法。只要使用拉普拉斯特征映射（Laplacian Eigenmap）或采用拉普拉斯的主要组成部分进行图嵌入，那它就是一阶方法。类似地，GloVe 是词共现图上的一阶方法。我最喜欢的图一阶方法之一是 ProNE，它和大多数方法一样有效，但速度快了一个数量级。

高阶方法嵌入了原始矩阵和邻居的邻居连接（第二阶）以及更深的 k 步连接。GraRep 表明，通过扩展图矩阵可以基于一阶方法生成高阶表示。

高阶方法是在图上执行的上采样。基于大型邻域采样的 GNN 和 node2vec 等随机游走方法执行的是高阶嵌入。

性能增益在哪儿？

过去 5 年中，大多数 GNN 论文的实验数据对从业者选择要使用的模型都是无用的。

正如论文《Open Graph Benchmark: Datasets for Machine Learning on Graphs》中所写的那样，许多 GNN 论文基于一些节点数为 2000-20,000 的小型图数据集进行实验（如 Cora、CiteSeer、PubMed）。这些数据集无法真正地区分不同 GNN 方法之间的区别。

近期的一些研究开始直接解决这一问题，但是为什么研究者这么长时间一直在小型、无用的数据集上做实验呢？这个问题值得讨论。

性能和任务有关

一个令人震惊的事实是，尽管语言模型在大量 NLP 任务中达到最优性能，但如果你只是把句子嵌入用于下游模型，那么从语言模型嵌入中获得的性能增益并不比累加 Word2Vec 词嵌入这类简单方法要多。

类似地，我发现对于很多图而言，简单的一阶方法在图聚类和节点标签预测任务中的性能和高阶嵌入方法差不多。事实上，高阶方法还消耗了大量算力，造成了浪费。

此类一阶方法包括 ProNE 和 GGVec（一阶）。

高阶方法通常在链接预测任务上有更好的表现。

有趣的是，链接预测任务中的性能差距对于人工创建的图而言是不存在的。这表明，高阶方法的确能够学习到现实图的某种内在结构。

就可视化而言，一阶方法表现更好。高阶方法的可视化图可能会出现伪影，例如 Node2Vec 可视化会有长丝状的结构，它们来自较长单链随机游走的嵌入。高阶方法和一阶方法的可视化对比情况参见下图：

最后，有时候简单的方法能够打败高阶方法。问题在于我们不知道什么时候一类方法优于另一类方法，当然也不知道其原因。

不同类型的图在被不同方法表示时反应有好有坏，这背后当然是有原因的。但这目前仍是个开放性问题。

这其中的一大因素是研究空间充斥了无用的新算法。原因如下：

学术动机阻碍进步

愤世嫉俗者认为机器学习论文是通过以下方式炮制的：

使用已有的算法；
添加新的层 / 超参数，用数学形式描述其重要性；
对超参数执行网格搜索，直到该新方法打败被模仿的那个基线方法；
绝不对在「实验结果」部分中进行对比的方法执行网格搜索；
给新方法起个不错的缩写名称，不公布 Python 2 代码。

我不是唯一一个对当前可复现研究持此观点的人。至少近两年情况好了一点。

所有进展都关乎实际问题

早在四十多年前，我们就已经知道如何训练神经网络了，但直到 2012 年 AlexNet 出现，神经网络才出现爆炸式发展。原因在于实现和硬件都发展到了一个节点，足以使深度学习应用于实际问题。

类似地，至少 20 年前，我们就已经知道如何将词共现矩阵转换为词嵌入。但词嵌入技术直到 2013 年 Word2Vec 问世才出现爆发式发展。其突破点在于基于 minibatch 的方法允许在商用硬件上训练 Wikipedia 规模的嵌入模型。

如果只花费数天或数周时间在小规模数据上训练模型，那么这个领域的方法很难取得进步。研究者会失去探索新方法的动力。如果你想取得进展，你必须尝试在商用硬件上以合理时间运行模型。谷歌的初始搜索算法最开始也是在商用硬件上运行的。

效率更重要

深度学习研究的爆发式发展离不开效率的提升，以及更好的软件库和硬件支持。

模型架构没那么重要

今年更加重要的一篇论文是 OpenAI 的《Scaling Laws for Neural Language Models》。这篇文章指出，模型中的原始参数数量是对整体性能最具预测性的特征。最初的 BERT 论文也指出了这一点，并推动了 2020 年大规模语言模型的迅速增加。

这一现实呼应了 Rich Sutton 在《苦涩的教训 (https://mp.weixin.qq.com/s/B6rnFLxYe2xe5C5f2fDnmw)》一文中提出的观点：

利用算力的一般方法最终是最有效的方法。

Transformer 可能也在替代卷积，正如知名 YouTube 博主 Yannic Kilcher 所说，Transformer 正在毁掉一切。它们可以和图网络结合，这也是最近几年出现的方法之一，而且在基准测试中表现出色。

研究者似乎在架构方面投入了太多精力，但架构并没有那么重要，因为你可以通过堆叠更多层来近似任何东西。

效率的胜利是伟大的，而神经网络架构只是实现这一目标的方式之一。在架构方面投入过多的精力，只会使我们错过其他方面的巨大收益。

当前的图数据结构实现太差劲了

NetworkX 是一个糟糕的库。我是说，如果你正在处理一些微小的图，该库表现还 OK。但如果处理大规模的图任务，这个库会令你抓狂且迫使你重写所有的东西。

这时，多数处理大规模图任务的用户不得不手动滚动一些数据结构。这很难，因为你的计算机内存是由 1 和 0 组成的一维数组，并且图没有明显的一维映射。

这种情况在我们更新图（如添加 / 移除节点 / 边缘）时会变得更加困难。以下提供了几个替代选择：

分离的指针网络

NetworkX 就是最好的示例。每个节点对象都包含指向其他节点的指针列表（节点边缘），其布局就像链表一样。

链表完全违背了现代计算机的设计方式。它从内存中读取数据非常慢，但在内存中的运行速度却很快（快了两个数量级）。在这种布局中，无论何时做任何事情，你都需要往返 RAM。这在设计上就很慢，你可以使用 Ruby、C 或者汇编语言编写，但还是很慢，这是因为硬件上的内存读取速度就很慢。

这种布局的主要优势在于其添加了新节点 O(1)。所以如果你在维护一个庞大的图，并且添加和移除节点的频率与从图中读取数据的频率相同，则这种布局挺适合的。

另外一个优势是这种布局可以「扩展」。这是因为所有数据彼此之间可解耦，所以你可以将这种数据结构放置在集群上。但实际上，你正在为自身问题创造一个复杂的解决方案。

稀疏邻接矩阵

稀疏邻接矩阵非常适合只读（read-only）图。我在自己的 nodevectors 库中将它作为后端使用，很多其他的库编写者使用 Scipy CSR Matrix。

最流行的布局是 CSR 格式，你可以使用 3 个数组来保存图，分别用于边缘终点、边缘权重和「索引指针」，该指针说明边缘来自哪个节点。

此外，得益于 CSR 的 3 数组布局，它可以在单个计算机上进行扩展：CSR 矩阵可以放置在磁盘上，而不用放在内存中。你只需要对 3 个数组执行内存映射，并在磁盘上使用它们。

随着现代 NVMe 驱动器的出现，随机搜索速度不再那么慢了，要比扩展基于链表的图时进行分布式网络调用快得多。但这种表征存在的问题是：添加一个节点或边缘意味着重建整个数据结构。

Edgelist 表征

这种表征具有 3 个数组：分别用于边缘源、边缘终点和边缘权重。DGL 包在其内部使用的正是这种表征。其简单、紧凑的布局非常适合分析使用。

与 CSR 图相比，该表征的问题在于某些寻轨操作（seek operation）速度较慢。假设你要找出节点＃4243 的所有边缘，则如果不维护索引指针数组，就无法跳转到那里。

因此，你可以保持 sorted order 和二分搜索 (O(log2n)) 或 unsorted order 和线性搜索 (O(n))。

这种数据结构也可以在内存映射的磁盘阵列上使用，并且在 unsorted 版本上节点添加速度很快（在 sorted 版本上运行缓慢）。

全局方法是条死胡同

一次性处理整个图的方法无法利用算力，因为它们达到一定规模就会把 RAM 耗尽。

因此，任何想要成为新标准的方法都要能对图的各个部分进行逐个更新。

基于采样的方法

未来，采样效率将变得更加重要。

Edgewise 局部方法。我所知道的能做到这一点的算法只有 GloVe 和 GGVec，它们通过一个边列表，并在每一步上更新嵌入权重。这种方法的问题在于，它们很难应用于更加高阶的方法。但其优点也很明显：很容易进行扩展，即使是在一台计算机上也不例外。此外，逐渐增加新的节点也很简单，只需要获取现有的嵌入，添加一个新节点，然后在数据上执行一个新的 epoch。
随机游走采样。采用这一方法的包括 deepwalk 及相关的后续工作，通常用于嵌入而不是 GNN 方法。这在计算上可能非常昂贵，添加新节点也很困难。但它是可以扩展的，Instagram 就用它来为自己的推荐系统提供信息。
邻接采样。这是目前 GNN 中最普遍的一种采样方法，低阶、高阶都适用（取决于 neighborhood 的大小）。它的可扩展性也很好，尽管很难高效执行。Pinterest 的推荐算法用的就是这种方法。

结论

这里有几个有趣的问题：

图类型和图方法之间是什么关系？
统一的基准测试，如 OGB。
我们把随机的模型扔给随机的基准，却不知道为什么或者什么时候它们表现得更好。
更基础的研究。我很好奇：其他表示类型（如 Poincarre 嵌入）能否有效地编码定向关系？

另一方面，我们不应该再专注于添加新的层，并在相同的小型数据集上进行测试。没人在乎这个。

这篇博客在 Reddit 上引发了一些讨论，详情参阅：https://www.reddit.com/r/MachineLearning/comments/kqazpd/d_why_im_lukewarm_on_graph_neural_networks/

— THE END —