中科院计算所沈华伟:GNN发展简史,诟病才是成长动力

news2024/3/3 18:12:28

文:周寅张皓

图神经网络(Graph Neural Network)的应用在近年来蓬勃发展,但同时对其质疑也从未消失。诸如对与大规模图数据的存储问题,表达能力问题,以及数据集的规范问题引发了许多讨论。

中科院计算所沈华伟研究员在图神经网络领域深耕多年。在青源talk第四期中,沈华伟梳理了图神经网络的发展历程,及对于一些问题、质疑的看法。

沈华伟表示,每一次对领域的质疑都是该领域成长的一次动力,只有解决了质疑的问题,领域才会得到发展。

报告回放链接:https://hub.baai.ac.cn/activity/details/126

题外:不忘初心,牢记使命,沈华伟自述,如何误打误撞走上科研这条道路

01

发展|从分离到融合

上世纪 90 年代末,作为神经网络在不同数据上的应用方案,图神经网络与循环神经网络、卷积神经网络一同被提出。因此最初 Graph Neural Network 应该被称为 Neural Network for Graph,但由于图数据的问题在当时并没有很广的应用场景,因此相较于迅速崛起的卷积网络, GNN 并未得到快速发展。

在沉寂了十多年后,人们由 CNN 的发展得到启发,开始思考如何将 CNN 的参数共享的性质泛化到非欧结构的数据中,而图作为非欧结构的两大类型之一(图与流形),被许多研究者关注。

但如何在图上定义卷积,成了一个困扰学科发展的问题。由于图数据的性质,每个节点的度大小不一,在社交网络中,甚至可能从1到10^8,这给卷积的定义带来了很大挑战。

图的表示:图可以被表示为一个四元组(V,E,W,X),分别代表节点、边、加权邻接矩阵和节点属性集。

在研究过程中,对图的卷积定义主要经历了两个发展方向:谱方法与空间方法。

最早将卷积概念应用于神经网络的 Yann Lecun 在面对这个问题时,提出了谱域 (spectral) 和空间 (spatial) 两种方法。

但由于谱方法没有在空间方法上的局部性质,即空间上的不变性,虽然数学形式优美,但强行定义卷积的效果并不好。

而空间方法较为直观,与 CNN 定义类似,空间方法则是通过对节点周边邻居的信息聚合来实现卷积。后续的发展表明,空间方法推动了 GNN 的发展,让人们对 GNN 的认识进入了信息传递的框架。

谱方法

在 「Spectral Networks and Deep Locally Connected Networks on Graphs」一文中,Yann Lecun 提出将图的拉普拉斯矩阵的特征向量作为基底,将样本投影到该空间后,进行卷积操作。

采用超参控制每次选择的相邻节点数量,对变化后的样本做 filter 和求加,再将输出结果进行拉普拉斯的逆变换,并输出非线性化后的结果。工作中的方法展示了在谱域进行卷积操作的可能性,并为后续的一系列图网络奠定了基础。

但这种方法,仍然存在一些问题。

沈华伟指出,该方法依赖于矩阵的特征分解,且投影计算和逆变换的开销为O(n^2),计算开销过大。另外,该方法并不是在局部空间上操作,这让这种方法失去了直观上的意义。

这些问题给未来的工作提供了一系列改进的空间。

2017年的「Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering」使用切比雪夫多项式近似。该方法一次性解决了谱域方法中存在的三个问题。

沈华伟指出,该方法避免了分解拉普拉斯矩阵,而是采用特征值对角矩阵作为基底。操作避免了使用过多自由参数导致的学习困难,同时代入计算公式后,减少了对特征向量矩阵 U 的依赖。

研究证明了该方法与谱方法有同样的误差上界,且计算复杂度降低到了 O(|E|) ,极大改善了谱方法图卷积的性能,同时启发了空间方法 GCN,作为该方法的一阶近似。

沈华伟认为,ChebNet在使用多项式近似时限制了卷积操作的自由度,使得该模型在实际使用中并不能有很好的效果。因此采用图的小波基作为基底U。由于小波变换的性质,U为一个稀疏矩阵,降低了计算开销,同时其局部性质也使得WaveletNet在实际应用中展现出不错的效果。

空间方法

2016年发表的文章「Learning Convolutional Neural Networks for Graph」发现,从CNN向GCN的卷积过程的迁移问题在于,需要确定一个固定的邻域,后续卷积的「定序」、「参数共享」步骤都可以在确定邻域后解决。因此该工作选择了每个节点固定个数的邻接节点作为邻域。但是,该工作确定邻域需要设计某种启发式的距离度量,后续工作对此作出了改进。

在GraphSAGE「Inductive Representation Learning on Large Graphs」中,作者采用了采样的方法确定邻域。在卷积操作的节点进行固定个数的随机行走,得到固定大小的邻居节点。由于随机行走能够更大概率获得与起点节点更近的节点,因此该方法采样能够得到相似的邻居集。得到了集合后,算法对邻居节点做信息聚合。

在先前工作的基础上,GCN对节点的一阶邻近节点进行访问,通过一阶层次化的堆叠,可以实现对二阶、三阶信息的获取。

但进一步的分析发现,该方法在计算中并未使卷积操作参数化而共享,其共享的参数是实现特征变换的 W ,使得该方法本质上是对邻接节点的加权聚合,使用邻居信息来平滑自身,其可以在很多任务中表现了不错的效果,但表达能力受限。

因此,后续工作诸如「Graph Attention Network」采用 self-attention 来控制自身信息与邻接节点信息的表达,实现了卷积操作的参数共享。

后续的研究发现,谱方法可以被定义为空间方法的一个子集。

「Geometric deep learning on graphs and manifolds using mixture model CNNs」给予图的卷积方法一种规范化的描述。文中指出,图卷积的实质是使用参数化的权重对定义的距离矩阵加权聚合。这个框架同时给予谱方法一种新的解释。

沈华伟指出,相较于空间方法在原始空间定义聚合函数,谱方法在规范后实质上是对变换到新的空间中的样本进行卷积。

因此谱方法可以被看作是变换空间后的空间方法,其从属于空间方法这一类别。而谱方法将显式地写出了空间变换,空间方法直接将 kernel matrix 定义出来,未写明变换的空间。

谱方法与空间方法的关系

02

反思|实践在先

Pooling

沈华伟指出,近年来关于GNN的理论进步十分有限,但是采用同样思想,从 CNN 结构迁移的技术比如 Graph Pooling 仍然不断发展,大致可分为两类:

  • 其一是通过对图进行层次聚类后,定义 pooling;

  • 另一种直接使用 attention 的方式,为每个节点计算attention weight,筛选节点。

但是,pooling 是针对图任务而言的,若需要节点级别的任务,则 Graph Pooling 就显得并不必要。

和 CNN 相比,由于图像任务处理的是图像本身,使用 pooling 能够从局部表示学习到全局的表示,而图的任务很多都是针对节点和边的,采用 pooling 反而会丢失信息,与任务本身并不匹配。因此,该领域需要尽快理清发展的目标。

表达能力

表达能力有两种形式:一是模型能够刻画的空间,另一种是拟合能力,是否可以逼近复杂函数。

由于神经网络在表达方面的强大能力,因此GNN提出以来,少有工作怀疑其表达能力。

但有研究发现,GNN并不能为图结构的数据提供万能近似的功能。WL test 为 GNN 的表达能力提供了理论的上界。

不过表达能力的限制同样带来了GNN的优势:易训练且开销小,相比于同等规模的全连接网络,GNN能够更快收敛。

与表达能力不足相反,GNN 通常在泛化能力上表现很好。这让其在特定任务上比神经网络具有更加优秀的表现,例如在样本稀少的任务上,GNN能够有很好的泛化性能。

然而,当加深 GNN 时,模型反而会出现过平滑问题,甚至在 training loss 上出现了不降反增的现象。分析表明,这源于 GCN 的跨层共享的硬编码矩阵 A,而 GAT 并不存在这个问题,因此某种意义上多头 GAT 才是真正意义上的 GCN。

03

应用|通用的跨学科图数据表示器

图神经网络的应用可以从三个领域来讨论,分别是 (1)节点层面、(2)图层面和 (3)信号层面。

在学科方面,推荐系统是一个参与众多的应用方向。

另一个极有前景的领域是知识图谱。由于知识图谱本身就是图结构,使用GNN或许会产生非常好的效果。

此外,诸如量子化学、物理等领域,GNN 都展现出了不错的能力。作为处理图的一个方便的工具,GNN 对其他学科的图类型的数据都可以做到很好的表达。

GNN在其他学科的应用

04

One More Thing

问:如何看待 GNN 的诟病?

沈华伟:针对 GNN 的诟病很多都来自最初几年发展的时候,学科发展的不规范,例如benchmark数据规模小,固定划分等不符合机器学习的常规规范。但简化了的研究验证过程也方便了研究者进行快速实验,在短短几年间就完成了理论的积累,走向蓬勃发展。在之后几年,研究者们便开始对GNN的研究作出规范,修正了当初的问题。因此对最初几年的诟病是正确的,但这是在特定阶段的便宜之计,因为这样有利于快速发展。

表达能力的问题正如报告中所说,存在一定局限。另一种批评是图在做 transductive learning时需要完整图的知识,对大规模的图做transductive learning开销很大。当前的发展方向倾向于inductive learning,即采用局部采样的方式获得样本,而不用储存整张图。

这些对领域的抨击都是这一领域成长的契机,只有解决了这些抨击的问题,才能获得发展。


扫描下方小助手二维码,备注 姓名+学校/单位+专业/方向,即可加入智源社区「图神经网络」主题讨论群

点击左下角“阅读原文”,查看回放!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://nwjs.net/news/141824.html

如若内容造成侵权/违法违规/事实不符,请联系七分地网进行投诉反馈,一经查实,立即删除!

相关文章

赠书活动 | 数据挖掘经典入门

赠书活动在 AINLP 公众号。这本书相当受欢迎(前两个版本累计销量超过 5 万册),尤其是受学校青睐——在此也说声抱歉,出于出版时间的原因,很多学校依然采用了旧版作为教材;同时也请知悉,新版已上…

《C语言编程初学者指南》一2.9 理解运算符优先级

本节书摘来自异步社区《C语言编程初学者指南》一书中的第2章,第2.9节,作者【美】Keith Davenport(达文波特) , M1ichael Vine(维恩),更多章节内容可以访问云栖社区“异步社区”公众号查看 2.9 …

产品开发的 11 宗罪

题图 | created by freepik最近图灵君在翻看一本比较小众的书:《硬件产品设计与开发:从原型到交付》,没成想翻开前言和第 1 章都很惊艳,尤其是第 1 章总结的《产品开发的 11 宗罪》,真的让我受益匪浅。因为这篇文章总结…

盘点:2020 年机器学习 10 大进展

转载自:机器之心2020 年因为新冠疫情,很多人不得不在家工作和学习,大量人工智能学术会议也转为线上。不过在去年我们仍然看到了很多 AI 技术领域的进展。DeepMind 研究科学家 Sebastian Ruder 近日帮我们对去年的机器学习社区进行了一番总结。…

《精通自动化测试框架设计》—第1章 1.3节五天太久,还能压缩吗

本节书摘来自异步社区《精通自动化测试框架设计》一书中的第1章,第1.3节五天太久,还能压缩吗,作者陈冬严 , 邵杰明 , 王东刚 , 蒋涛,更多章节内容可以访问云栖社区“异步社区”公众号查看。 1.3 五天太久,还能压缩吗两…

终于!有本书把我从“看完就忘、死记硬背”的学习困境中拯救出来了!

设想一下,你面前有一堵由5000个魔方组成的魔方墙,从中间分割成两块,左右各2500个,并且它们的图案完全一致!这时,有人从右边的墙上随机挑选一个魔方,让九个方格中的一个变换颜色,你能…

一秒看遍10万神经元的「绚丽烟花」,AI究竟向大脑学什么?|北大陈良怡专访...

作者:梦佳大脑是人类进化的高级产物,重量约1.5公斤,占体重2%,功耗约20瓦,占全身功耗20%,当前人类对大脑的认识还不足5%,尚无完整的脑谱图可供参考。毫无疑问&…

一本真正讲“大数据”处理思路的书

这是我读到的第一本真正讲“大数据”处理思路的书,我想分享一下我读了这本书的感悟。一般情况下,在面对海量数据的时候,我们的软件架构也会跟着发生变化。当你的数据量在内存里放不下的时候,你就得考虑硬盘;当你的硬盘…

这些代码改变了科学界:从Fortran、arXiv到AlexNet

转自:机器之心2019 年,「事件视界望远镜」团队拍下了第一张黑洞照片。这张照片并非传统意义上的照片,而是计算得来的——将美国、墨西哥、智利、西班牙和南极多台射电望远镜捕捉到的数据进行数学转换。该团队公开了所用代码,使科学…

不存在完美的入门书,但是有些书在某些方面很惊艳

题图 | Technology vector created by stories - www.freepik.com前段时间收到了明发哥翻译的《Android 编程权威指南(第4版)》,许久没有打开纸质书,但翻阅时的纸墨味儿依旧,仿佛回到了几年前初学 XML 布局的时候。我从…

两院院士评选2020年中国、世界十大科技进展揭晓,「机器学习模拟上亿原子」等入选 | AI日报...

两院院士评选2020年中国、世界十大科技进展揭晓,「机器学习模拟上亿原子」等入选由中国科学院、中国工程院主办,中国科学院学部工作局、中国工程院办公厅、中国科学报社承办,腾讯集团发展研究办公室协办的中国科学院院士和中国工程院院士投票…

一本书带你入门商业数据科学

老马(Matt Taddy)是 Central Economics Team 的 VP,亚马逊北美首席经济学家。相当于大型智囊团里的二当家的。在来亚马逊之前,老马是芝加哥大学布斯商学院的明星教授,他是学数理统计出身的,一开始教授的是统…

面对500篇GNN论文,心态差点儿崩了,幸好我有这本小书

题图 | Computer vector created by stories - www.freepik.com说起来,大学时代的图灵君也算得上是零挂科修完全部计算机课程的人才。怀着对前沿技术的满腔热忱,年(yī)纪(tu)轻(xi)…

《因果科学周刊》第7期:2021因果强化学习第一课

为了帮助大家更好地了解因果科学的最新科研进展和资讯,我们因果科学社区团队本周整理了第7期《因果科学周刊》,推送近期因果科学领域值得关注的论文和资讯信息。本期的主题是“因果强化学习”,它在众多通向通用人工智能的路径中备受关注&…

JDK安装与环境变量配置

安装JDK 选择安装目录 安装过程中会出现两次 安装提示 。第一次是安装 jdk ,第二次是安装 jre 。建议两个都安装在同一个java文件夹中的不同文件夹中。(不能都安装在java文件夹的根目录下,jdk和jre安装在同一文件夹会出错) 如下图…

搞定了数学,拿下了代码,没想到在这件事上栽了跟头……

“我好像要失业了。”如果有一天,你的学霸老同学给你发了这样一条信息,你会怎么想?我就碰到了这样的事。当年我们系所向披靡的刚哥,毕业季能拿着一叠offer打扑克的牛人,他竟然告诉我他要失业了。#1被800字追杀的学霸“…

哈佛大学研发水下机器人,Science Robotics发表 | AI日报

哈佛大学研发水下机器人,Science Robotics发表日前,来自哈佛大学的科学家们就从鱼群中汲取灵感,研发出了一批水下机器人,这种机器人可以像真正的鱼群一样同步运动,且不需要任何外部控制。同时,他们也首次利…

日程来了!2021年佛山敏捷之旅暨第1届佛山DevOps社区Meetup

2021年佛山敏捷之旅暨第1届佛山DevOps社区Meetup首次在佛山举行,大会以金融科技研发效能为主题,立足广东金融高新区,服务周边企业。大会地点在广东佛山市南海区新凯广场万枫酒店,时间为5月16日,拟定2个会场&#xff0c…

[解决方案记录]No module named fused(stylegan2的bug,已更新)

基本情况 https://github.com/rosinality/stylegan2-pytorch/issues/81 运行psp时出现的问题。其实就是stylegan2里面采用了c编译等功能带来的bug,非常烦人。 系统:windows 平台:pycharm jupyter notebook GPU:GTX1660Ti 解决…

5月书讯 | 哺育小平邦彦、伊藤清等一代数学家的“数学圣经”终于来啦!

“2020已经过去了三分之二,不知何年何月才能与此书见面。”“编辑老师,不知道还有多久面世?”“2021年了,终于预售了...”......经过编辑老师几百个日夜的努力,作为图灵经典数学系列的其中一员,这本书与其他…