机器之心编辑部编译

2021年的第一盆冷水:有人说别太把图神经网络当回事儿

图神经网络(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/

Powered by Froala Editor

入门图神经网络
1
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

词嵌入技术

词嵌入是自然语言处理(NLP)中语言模型与表征学习技术的统称。概念上而言,它是指把一个维数为所有词的数量的高维空间嵌入到一个维数低得多的连续向量空间中,每个单词或词组被映射为实数域上的向量。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

数据科学技术

数据科学,又称资料科学,是一门利用数据学习知识的学科,其目标是通过从数据中提取出有价值的部分来生产数据产品。它结合了诸多领域中的理论和技术,包括应用数学、统计、模式识别、机器学习、数据可视化、数据仓库以及高性能计算。数据科学通过运用各种相关的数据来帮助非专业人士理解问题。

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

上采样技术

在数字信号处理中,上采样、扩展和内插是与多速率数字信号处理系统中的重采样过程相关的术语。 上采样可以与扩展同义,也可以描述整个扩展和过滤(插值)过程。

随机搜索技术

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

矩阵分解技术

矩阵分解是一种将矩阵简化为其组成部分的方法。这种方法可以简化更复杂的矩阵运算,这些运算可以在分解的矩阵上执行,而不是在原始矩阵本身上执行。它的衍生Non-negative matrix factorization也被用于降维等操作上。

图网络技术

2018年6月,由 DeepMind、谷歌大脑、MIT 和爱丁堡大学等公司和机构的 27 位科学家共同提交了论文《Relational inductive biases, deep learning, and graph networks》,该研究提出了一个基于关系归纳偏置的 AI 概念:图网络(Graph Networks)。研究人员称,该方法推广并扩展了各种神经网络方法,并为操作结构化知识和生成结构化行为提供了新的思路。

推荐文章
暂无评论
暂无评论~