精华内容
下载资源
问答
  • 安波副教授:分布式人工智能进展与趋势
    2021-01-08 10:08:49

    2020-12-31 09:43:19


    2020年11月20日,由中国科学技术协会主办,中国国际科技交流中心、中国人工智能学会、新加坡通商中国承办的“中新数字经济与人工智能高峰论坛”云端召开。主题报告环节,新加坡南洋理工大学人工智能研究院联席院长校长委员会讲席副教授安波为我们带来了《分布式人工智能进展与趋势》的精彩演讲。

    演讲实录丨安波副教授:分布式人工智能进展与趋势

     

    安波

    新加坡南洋理工大学人工智能研究院

    联席院长校长委员会讲席副教授

     

    以下是安波副教授的演讲实录:

     

    很荣幸得到这个机会和大家分享关于分布式人工智能进展和趋势的一些看法。期望听完我的分享之后,大家能理解分布式人工智能是什么,为什么要care 这个领域,它最近有什么样的一些进展,以及未来可能会有什么样的一些挑战。

     

    过去这些年AI 的进展主要体现在一些比较简单的场景。比如,自然语言处理是相对比较静态的数据;或者围棋的博弈,只有两个player,并且所有对决策重要的信息都可以直接观测到。未来要考虑更加复杂环境下的AI 系统或者一些应用,这个环境是不确定的,甚至是完全open 的(open 意味着我们没有办法感知建模)。另外这个环境里面有多个player,这些参与方之间是竞争的,我们采取的策略是需要序贯的,同时需要进行分布式的优化。这样复杂的问题是分布式人工智能所研究的目标。

     

    星际争霸是目前AI 领域最火的问题之一,比如DeepMind 一直投入很大的精力在做,中国有很多初创公司也在做这方面的事情,我们很高兴看到,启元世界在一两个月之前北京的智源大会上,展示了他们最新的研究成果并击败了几位华人顶尖高手。星际争霸是一个特别复杂的问题,包括环境的不确定性和动态变化、多方的竞争、序惯的决策,完全体现了上面所讲的分布式人工智能所研究问题的特点。分布式人工智能覆盖很多其他场景,如军事方面的、金融方面的,也包括中科大陈小平老师团队参与的机器人足球比赛。这些问题相对比较复杂,有很多研究挑战,尤其是我们的解决方案特别需要考虑多个player 之间的竞争。

     

    分布式AI 最近几年涌现出来的算法框架大致可以分为两类,一类是把传统的规划算法、算法博弈论,以及运筹学优化算法结合,解决大规模的优化或规划的问题,或者是博弈竞争的问题;另外一类算法基于强化学习,特别是多智能体深度强化学习。

     

    接下来我针对这两方面,讲一些成功的例子,以及我们在这上面做的一部分工作。首先我讲一点关于很强竞争的AI 问题,这里需要用博弈论来分析竞争交互。把博弈论的思路应用到有竞争的AI 上,过去这几年有很多成功的例子。比如德州扑克(简称“德扑”),这是阿尔法狗之后最成功的AI 系统,有很大反响。德扑完全没用任何深度学习,是基于算法求解大规模博弈算法的进展。比如,安全博弈论成功应用于很多领域的安全资源调度;还有现在谷歌、百度、Bing 他们的主要收入来自于这些关联词拍卖,而关键词拍卖的成功依赖背后的拍卖机制设计。

     

    下面简单介绍一下德扑。CMU 的Libratus 系统是基于他们十几年来在求解特别大规模的博弈算法方面的积累,然后击败了最顶尖的人类德扑选手。其实也有很多团队长期在做这些事情,比如Alberta 大学和DeepMind 都在尝试深度学习来解决德扑问题,基于博弈的思路目前是最好的。像阿尔法狗一样,如果能找到那个最优解肯定是最好的,就不用深度学习。如果一些博弈,能够找到一个近似的均衡,肯定是最好的一个思路。

     

    早期的德扑是针对两个人博弈的,尽管能战胜世界上最顶尖的选手,但是在商业上没有太大价值。求解多人德扑是当前学术界的一个open 问题。最近两年的初步进展把多人分成两个队,一个队只有一个人,另外一个队是N-1 个人。我们在这方面也做了一些工作,提出的算法效率远远好过之前提出的所有算法。

     

    以前我们做了很多安全博弈论方面的事情,在本质上希望帮助安全部门做安全资源的高效分配。由于用户的特殊性,所以算法必须要完全给出最优的解,或者有近似界的近似解。传统的诸如遗传算法的启发式方法都不能用。这一系列漂亮的研究,不仅有很多理论成果,更重要的是在全世界很多地方得到了真实应用,并且有很大影响。

     

    对于涉及到多个竞争参与方的AI 问题,用算法博弈论是一个思路,刚才也展示了,希望这个思路能有很多很好的结果。有另外一些问题,用算法博弈的思路没有办法找到一个好的解。这几年有一个通常的做法,用强化学习来做,我在这里尝试去解释,在什么样的场景下,强化学习会是一个更好的选择?

     

    当这个问题不能很好的建模,比如这个环境完全是open 的,不知道怎么model 它,就不能对它很好地进行求解。应用算法博弈论的思路时,首先要对博弈问题进行建模,我们model 那些player的策略空间和效用函数等,当不能很好的model问题时,博弈求解的方法就不能工作;其次,当问题规模特别大时,传统的算法也不能把最优的求出来。如果问题很难近似或者没有一些特殊的结构可以利用时,算法博弈论的思路也很难成功。

     

    强化学习及多智能体强化学习是一个特别热的话题,国内有很多团队做了很多很好的工作。当然,现在还有很多挑战,特别是多智能体强化学习还处在起步阶段。

     

    接下来展示几个最近做的一些工作。

     

    我们做了电子商务平台的反作弊,并应用到电商平台上;还有电商平台组合推荐问题。比如,我们做了一个涉及电商平台多模块推荐的问题,这些模块是完全不同的团队运营,不同的团队在决定应该推荐什么样的东西没办法进行实时通信,所以我们研究了怎样来实现这些模块之间的协调,实现推荐效果的最优化。

     

    我们做了一些非常大规模的policy planning问题,比如政府要决定一个policy,这个policy会影响下面很多player 的行为选择,由于player数量很大并且交互复杂,因此需要用到腹部是强化学习来解决这种特别大规模的优化问题。同时大规模分布式系统优化面临通信方面的约束,需要决定什么时候通信?和谁通信?以及通信什么样的内容?我们在这些方面也做了一些初步尝试。

     

    总之,现在有很多挑战的问题需要分布式AI技术来解决,比如未来军事方面的应用,可能需要设计无人机及地面机器人的编队能够在陌生的环境执行特别复杂的任务。异构的无人机编队要对环境进行感知、要进行协作,然后要和敌方进行对抗。很显然,这样的环境下,优化必须是分布式的,如果由某个机器人来控制整个编队,整个系统是不鲁棒的,同时通信的代价也特别高。

     

    现在分布式AI 已经有了很多有影响力的应用,但是我们看到更多迫切需要解决的应用问题,以及研究方面的挑战,希望能有更多的人参与分布式人工智能方面的研究。

     

    (本报告根据速记整理)

    更多相关内容
  • 该算法采用分布式并行计算机制, 易其他方法结合, 具有较强的鲁棒性; 但搜索时间长、易限入局部最优解是其突出的缺点. 针对蚁群算法, 首先介绍其基本原理; 然后讨 论了近年来对蚁群算法的若干改进以及在...
  • No.16智源社区强化学习组强化学习研究观点资源活动关于周刊强化学习作为人工智能领域研究热点之一,多智能强化学习的研究进展与成果也引发了众多关注。为帮助研究工程人员了解该领域的相关进展...

    No.16

    智源社区

    强化学习组

     习

    研究

    观点

    资源

    活动

    关于周刊

    强化学习作为人工智能领域研究热点之一,多智能强化学习的研究进展与成果也引发了众多关注。为帮助研究与工程人员了解该领域的相关进展和资讯,智源社区结合领域内容,撰写为第16期《强化学习周刊》。本期周刊整理了近期多智能体强化学习领域相关的最新论文推荐、综述、新工具、课程等,以飨诸位。

     

    周刊采用社区协作的模式产生,欢迎感兴趣的朋友们参与我们的工作,一起来推动强化学习社群的分享、学习和交流活动。可以扫描文末的二维码加入强化学习社区群。

     

    本期贡献者:(李明,刘青、陈斌)

    论文推荐

    多智能体强化学习近年来取得了令人瞩目的成就,其应用于各个领域的研究也取得较大的进步。多智能体强化学习通过对不同智能体学习策略奖励不同的情况下,不断改进学习算法。近年来,该方向已经取得了一系列瞩目的进展,比如交通信号控制、机器人控制、未知探索、公交车时刻表优化等。故多智能体强化学习领域具有较大的潜在研究优势。

    多智能体强化学习的研究与应用越来越多,其在通信网络、合作探索、任务卸载等方面都有了深入的研究。本次推荐了8篇多智能体强化学习的相关论文,主要涉及应用于基于图注意的多智能体强化学习、基于多智能体强化学习的合作探索、基于知识迁移的多智能体改进、分布式多智能体强化学习、竞争性策略探索、结构关系推理、人机协作调度等。

    标题:Packet Routing with Graph Attention Multi-agent Reinforcement Learning(基于图注意多智能体强化学习的封包路由)了解详情

    简介:封包路由是通信网络中的一个基本问题,它决定了 封包如何通过一些中间节点从其源节点定向到其目的节点。随着网络拓扑结构的日益复杂和高度动态的流量需求,传统的基于模型和基于规则的路由方案由于简化和不切实际的模型假设以及缺乏灵活性和适应性而表现出明显的局限性。网络控制智能化正在成为一种趋势,也是实现网络高效运行的关键。本文通过利用强化学习 (RL) 开发了一种无模型和数据驱动的路由策略,其中路由器与网络交互并从经验中学习,为未来做出一些好的路由配置。考虑到网络拓扑的图性质,其结合图神经网络 (GNN) 设计了一个多代理 RL 框架,针对路由问题量身定制。分别探索了三种部署范式,集中式、联合式和协作式学习。仿真结果表明,本文的算法在数据包传输延迟和可承受负载方面优于一些现有的基准算法。

    https://arxiv.org/pdf/2107.13181.pdf

    https://hub.baai.ac.cn/view/9054

     

    标题:Cooperative Exploration for Multi-Agent Deep Reinforcement Learning(基于多智能体深度强化学习的合作探索)了解详情

    简介:探索对于深度强化学习的良好效果至关重要,并已引起了广泛关注。然而,现有的多智能体深度强化学习算法仍然主要使用基于噪声的技术。最近,开发方法,考虑多个代理之间的合作已经开发出来。然而,现有的方法面临着一个共同的挑战:代理努力识别值得探索的状态,并且几乎无法协调针对这些状态的探索工作。为了解决这一缺点,本文提出了合作多智能体探索(CMAE):智能体在探索过程中共享一个共同的目标。目标通过基于归一化熵的技术从多个投影状态空间中选择。然后,训练智能体以协调的方式实现这一目标。本文证明了CMAE在各种任务上始终优于基线,包括稀疏奖励版本的多粒子环境(MPE)和星际争霸多智能体挑战(SMAC)。

    论文地址:https://arxiv.org/pdf/2107.11444.pdf

     

    标题:Multi-agent Reinforcement Learning Improvement in a Dynamic Environment Using Knowledge Transfer(动态环境下基于知识转移的多智能体强化学习改进)了解详情

    简介:多智能体协作系统在许多领域得到了广泛的应用。代理之间的交互将带来积极的方面,包括降低操作成本、高可扩展性和促进并行处理。这些系统为处理大规模、未知和动态环境铺平了道路。然而,在这些环境中学习已成为不同应用中的一个突出挑战。这些挑战包括搜索空间大小对学习时间的影响、代理之间不适当的合作以及代理决策之间缺乏适当的协调。此外,在这些问题中,强化学习算法可能会受到长时间收敛的影响。本文介绍了一个使用知识转移概念的通信框架,以解决具有大状态空间的羊群问题中的此类挑战。为了解决收敛问题,知识转移被用来显著提高强化学习算法的效率。代理之间的协调分别通过每组代理中的主代理和协调代理来执行。研究结果表明,该框架确实可以提高学习速度并缩短收敛时间。

    论文地址:https://arxiv.org/pdf/2107.09807.pdf

     

    标题:Decentralized Multi-Agent Reinforcement Learning for Task Offloading Under Uncertainty(不确定环境下任务卸载的分散式多智能体强化学习)了解详情

    简介:由于环境的非平稳性和组合动作空间的高维性,多智能体强化学习(MARL)是强化学习的一个具有挑战性的子领域。deepmarl算法已被应用于解决不同的任务卸载问题。然而,在实际应用中,代理所需的信息(即奖励和状态)会受到干扰和更改。深度 MARL 对实际挑战的稳定性和鲁棒性仍然是一个开放的研究问题。本文应用最先进的MARL算法来解决具有奖励不确定性的任务卸载问题。研究发现,与具有完美奖励的学习相比,奖励信号中的扰动会导致性能下降。作者希望本论文能够激发更多的研究,以研究和解决在无线通信系统中部署deep MARL解决方案的实际挑战。

    论文地址:https://arxiv.org/pdf/2107.08114.pdf

     

    标题:Strategically Efficient Exploration in Competitive Multi-agent Reinforcement Learning(基于竞争多智能体强化学习的策略性探索)了解详情

    简介:高样本复杂度仍然是强化学习(RL)应用的障碍,特别是在多智能体系统中。大量研究表明,基于不确定性下乐观原则的探索机制可以显著提高单智能体任务中RL的样本效率。本文旨在了解乐观探索在非合作多智能体环境中的作用。其将证明,在零和博弈中,乐观探索会导致学习者浪费时间对与战略游戏无关的状态空间部分进行采样,因为它们只能通过两个参与者之间的合作实现。为了解决这个问题,本文在马尔可夫博弈中引入了一个策略有效探索的形式化概念,并使用这个概念开发了两个针对有限马尔可夫博弈的策略有效学习算法。研究结果证明了这些方法比乐观的方法更有效。

    论文地址:https://arxiv.org/pdf/2107.14698.pdf

     

    标题:智能工厂在线调度的多智能体强化学习Multi-agent reinforcement learning for online scheduling in smart factories了解详情

    简介:传感和通信技术的快速发展将产生大量数据的孤立制造单元连接起来。大规模定制的新趋势给生产计划带来了更高水平的干扰和不确定性。传统的制造系统在集中式架构中分析数据和调度订单,由于过度依赖中央控制器和有限的通信渠道,这种架构效率低下且不可靠。本文提出了智能工厂中新的网络物理集成,用于在线调度小批量高混合订单。首先,制造单位通过物联网技术通过信息物理系统(CPS)相互连接。加工操作的属性由射频识别 (RFID) 标签存储和传输。其次,为每个单元(例如,仓库、机器)提出了一种具有新颖神经网络的 AI 调度程序,以使用实时传感器数据调度动态操作。每个 AI 调度器都可以通过学习其他调度器的调度经验来与其他调度器协作。第三,设计了新的奖励函数,以提高基于强化学习 (RL) 的多个 AI 调度程序的决策能力。通过实际案例研究,在智能工厂中对所提出的方法进行了评估和验证。实验结果表明,智能工厂的新架构不仅提高了多个AI调度器的学习和调度效率,还有效处理了紧急订单和机器故障等突发事件。

    论文地址:https://www.sciencedirect.com/science/article/pii/S0736584521000855

     

    标题:用于多智能体强化学习的结构关系推理的 Actor-Critic/Structural Relational Inference Actor-Critic for Multi-Agent Reinforcement Learning了解详情

    简介:多智能体强化学习 (MARL) 对于多种高维场景和具有多个智能体的复杂任务至关重要。已经对具有先验领域知识和预定义结构的代理进行了许多尝试。然而,多智能体系统(MAS)中智能体之间的交互关系通常是未知的,以前的方法无法处理不断变化的环境中的动态活动。在这里,本文提出了一种称为结构关系推理 Actor-Critic (SRI-AC) 的多智能体 Actor-Critic 算法,该算法基于集中训练和分散执行的框架。SRI-AC 利用变分自编码器 (VAE) 中的潜在代码来表示成对代理之间的交互,重建误差基于图神经网络 (GNN)。有了这个框架,测试强化学习学习者是否可以形成可解释的结构,同时在合作和竞争场景中取得更好的表现。结果表明,与基线算法相比,SRI-AC 可以应用于复杂的动态环境以找到可解释的结构,同时获得更好的性能。

    论文地址:https://www.sciencedirect.com/science/article/pii/S0736584521000855

     

    标题:使用深度多智能体强化学习优化人机协作中的任务调度Optimizing task scheduling in human-robot collaboration with deep multi-agent reinforcement learning了解详情

    简介:人机协作 (HRC) 为提高制造流程的效率提供了机会。然而,现有的 HRC 任务规划方法在很多方面仍然受到限制,在本文中,HRC 装配工作过程被格式化为一种新颖的棋盘设置,其中棋子移动的选择被用来类比 HRC 装配工作过程中人类和机器人的决策。为了优化完成时间,考虑了马尔可夫博弈模型,该模型以任务结构和代理状态作为状态输入,以总完成时间作为奖励。没有专家的知识,该博弈模型能够在具有收敛性的代理之间寻求相关的均衡策略,从而做出面对动态环境的实时决策。为了提高寻找任务调度最优策略的效率,应用了一种基于深度 Q 网络(DQN)的多智能体强化学习(MARL)方法,并与 Nash-Q 学习、动态规划和 DQN-基于单智能体的强化学习方法。高度可调的办公桌组件用作案例研究,以证明所提出的算法在不同数量的任务和代理下的有效性。应用基于深度 Q 网络 (DQN) 的多智能体强化学习 (MARL) 方法并与 Nash-Q 学习、动态规划和基于 DQN 的单智能体强化学习方法进行比较。高度可调的办公桌组件用作案例研究,以证明所提出的算法在不同数量的任务和代理下的有效性。

    论文地址:https://www.sciencedirect.com/science/article/pii/S0278612521001527

    综述

    标题:多智能体深度强化学习:综述Multi-agent deep reinforcement learning: a survey了解详情

    简介:强化学习的进步已记录了各个领域的卓越成就。尽管在此过程中,多智能体领域已被其单智能体领域所遮盖,但多智能体强化学习获得了快速发展的动力,最新成果解决了现实世界中的复杂性问题。本文概述了多智能体深度强化学习领域的最新发展。主要关注近年来的文献,这些文献结合了深度强化学习方法和多智能体方案。主要内容分为三个部分。首先,分析了用于训练多个特工的训练方案的结构。第二,考虑了合作,竞争和混合场景中代理行为的新兴模式。第三,系统地枚举了多代理领域中唯一出现的挑战,并回顾了用于应对这些挑战的方法。本文讨论了研究进展,确定趋势并概述了该研究领域未来工作的可能方向。

    论文地址:

    https://link.springer.com/content/pdf/10.1007/s10462-021-09996-w.pdf

    新工具

    MALib:基于群体的多智能体强化学习并行框架了解详情

    简介:MALib 是一个基于种群的学习的并行框架,嵌套有(多代理)强化学习 (RL) 方法,例如 Policy Space Response Oracle、Self-Play 和 Neural Fictitive Self-Play。MALib 提供了更高级别的 MARL 训练范式抽象,可以在不同的分布式计算范式上实现高效的代码重用和灵活部署。MALib 的设计也力求推动其他多智能体学习的研究,包括多智能体模仿学习和基于模型的 MARL。基于种群的多智能体强化学习(PB-MARL)是指嵌套强化学习(RL)算法的一系列方法,这些方法通过耦合的种群动态产生自生成的任务序列。通过利用自动课程来诱导一群不同的紧急策略,PB-MARL在处理多智能体任务方面取得了令人印象深刻的成功。尽管分布式RL框架的现有技术非常出色,但由于异构策略交互所涉及的采样、训练和评估之间的多个嵌套工作负载的额外复杂性,PB-MARL对并行化训练框架提出了新的挑战。为了解决这些问题,提出了一个可扩展的高效计算框架。框架由三个关键部分组成:(1)集中式任务调度模型,支持自生成任务和异构策略组合的可扩展训练;(2)一个名为“教师-评估者-学习者”的编程架构,实现了训练和采样的高度并行,满足了自动课程学习的评估需求;(MARL训练范例的更高级抽象,它在不同的分布式计算范例上实现了高效的codereuseandflexibledeployments。实验表明,在一台拥有32个中央处理器内核的机器上,马利巴赫的吞吐量高于40K FPS;在多智能体训练任务中,比RLlib加速5倍,比OpenSpiel至少加速3倍。

    课程

    伦敦大学学院课程《多智能体机器学习(2021)》了解详情

    简介:主讲人为伦敦大学学院(UCL)计算机系教授汪军,适合广大多智能体研究的爱好者。现在已经更新48期。本课程基于伦敦大学学院计算机系2020-2021学年度课程Multi-agent Artificial Intelligence (20/21),主要介绍多智能体机器学习。课程将机器学习的研究与博弈论和经济学研究相结合,包括博弈论、拍卖理论、算法机制设计、多智能体(深度)强化学习等主题,同时还将讨论相关的实际应用,包括在线广告、在线拍卖、生成模型的对抗训练、机器人规划,以及玩在线游戏的智能体。课程为英文授课,与UCL授课进度同步。

    课程地址:

    https://app6ca5octe2206.pc.xiaoe-tech.com/detail/p_603db816e4b0a77c389892d3/6

    RLChina 2021 强化学习暑期课(8月16日-22日)了解详情

    简介:RLChina 暑期课程是由英国UCL大学汪军老师发起,强化学习业内顶尖学者共同分享给广大强化学习爱好者的免费网络直播课程。在2020 年的课程就吸引了超过 3 千名学员,课程也获得了大家的一致好评。今年,RLChina 暑期课全新升级,20 位来自全球顶级高校和企业的强化学习专家共同学员讲授从入门到前沿的强化学习知识,此外还准备了习题课、智能体竞赛日、决策智能创业日帮助大家全方位地接触强化学习从理论到落地实践。

    如果你正在从事或关注 强化学习研究、实现与应用,欢迎加入“智源社区-强化学习-交流群”。在这里,你可以:

     

    • 学习前沿知识、求解疑难困惑

    • 分享经验心得、展示风貌才华

    • 参与专属活动、结识研究伙伴

    扫描下方二维码,加入强化学习兴趣群。

    展开全文
  • 本文经机器之心授权转载。【导读】本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程 Theme II: Advances and Applica...

    本文经机器之心授权转载。

    【导读】本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程 Theme II: Advances and Applications 部分的核心内容。作者包括腾讯荣钰、徐挺洋、黄俊洲,清华大学黄文炳,香港中文大学程鸿。

    人工智能领域近几年历经了突飞猛进的发展。图像、视频、游戏博弈、自然语言处理、金融等大数据分析领域都实现了跨越式的进步并催生了很多改变了我们日常生活的应用。近段时间,图神经网络成为了人工智能领域的一大研究热点,尤其是在社交网络、知识图谱、化学研究、文本分析、组合优化等领域,图神经网络在发掘数据中隐含关系方面的强大能力能帮助我们获得更好的数据表达,进而能让我们做出更好的决策。比如通过图神经网络梳理人类社会关系网络的演变,可有望帮助我们理解人类社会的底层运作模式,进而让我们离理想社会更近一步。

    在今年的计算机协会国际数据挖掘与知识发现大会(ACM SIGKDD,简称 KDD)上,图神经网络备受研究关注的现状得到了充分体现:粗略统计,今年 KDD 接收的 216 篇论文(research track)中有近 40 篇与图神经网络相关。也因此,一场为期一天的图神经网络相关课程得到了参会人员的重点关注。该联合课程的主题为「图深度学习:基础、进展和应用(Deep Graph Learning: Foundations, Advances and Applications)」,由腾讯 AI Lab、清华大学、香港中文大学等机构联合组织,从基础的图概念一直谈到了当今最前沿的图神经网络研究进展。

    本次课程分为两个主题。本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程 Theme II: Advances and Applications 部分的核心内容,Theme I 以及更多详细的内容可参看课程幻灯片及相关论文:https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

    为了解决图学习中的一系列具有挑战性的问题, 探索图学习应用的边界并在于助力公司各类与图数据相关的业务。腾讯 AI Lab 于 2017 年下半年开始布局图深度学习的研究,积极探索图深度学习的应用边界。并且在各大机器学习数据挖掘顶级会议上发表多篇文章,涉及大图计算,超深图神经网络,无监督图学习,图的对抗攻击,图的样本学习等。在未来我们将探索图深度学习在广泛场景的应用,如社交推荐,药物研发等。使其能够真正造福人类。 

    一 图与图神经网络

    1 什么是图?

    汉语中的「图」可以对应成英语中多个不同的词:image、picture、map 以及本文关注的 graph。图(graph)也可称为「关系图」或「图谱」,是一种可用于描述事物之间的关系的结构。图的基本构成元素为顶点和连接顶点的边。根据边是否存在方向的性质,还可分为有向图和无向图。一般而言,我们通常可将图表示成点和连接点的线的形式,这有助于我们更直观地理解,如下图所示:

    但为便于计算机处理,我们也可用矩阵来表示图。比如如果定义当 v_i 与 v_j 相连时,A[i,j]=1,否则 A[i,j]=0,则可将以上矩阵表示为邻接矩阵 A:

    图具有很强的表征能力。物理学系统建模、蛋白质预测、疾病分类以及许多文本和图像处理任务都可以表示成图结构的数据,比如图可用于表示文本中句子的依赖关系和图像中事物的相对位置,也可以用于分析社交网络中的信息传播和用户关系,还能通过分析分子之间的关联来发现新药。

    2 图神经网络

    近些年在大数据和硬件发展双重助力下迎来跨越式发展的深度神经网络技术让我们具备了分析和理解大规模图数据的能力。总体而言,图分析任务可分为节点分类、连接预测、聚类三类。

    图神经网络(GNN)就是处理图数据的神经网络,其中有两种值得一提的运算操作:图过滤 (Graph Filter, 分为基于空间的过滤和基于谱的过滤)和图池化。其中图过滤可细化节点特征,而图池化可以从节点表示生成图本身的表示。

    一般来说,GNN 的框架在节点层面上由过滤层和激活构成,而对于图层面的任务,则由过滤层、激活和池化层组成不同的模块后再连接而成。

    在 GNN 的实现方面,目前最常用的方法是消息传递框架(Message Passing Framework)。简单总结起来,该框架分为两个步骤。

    第一步是消息生成步骤。首先,从近邻节点收集状态数据,然后使用对应函数生成当前节点的消息。在第二步中,我们更新目标节点的状态。

    目前大多数空间式 GNN 都可以构建为某种消息传递过程,而且事实上目前大多数用于图的深度学习工具包大都采用了这一框架,比如 Deep Graph Library 和 PyTorch Geometric。

    3 图神经网络的发展历史

    图神经网络(GNN)并不是一个新事物,最早的 GNN 的历史可以追溯到 1997 年,粗略总结起来,GNN 的发展过程大致可分为三个阶段。

    在第一个阶段,GNN 所使用的主要方法是基于循环神经网络(RNN)的扩展。众所周知,RNN 擅长处理序列数据,而反过来,序列数据则可被视为一种特殊模式的图。因此,早期的一些工作(TNN97 / TNN08)将处理序列数据的 RNN 泛化用于树和有向无环图(DAG)等特殊的图结构。但那之后这一领域的发展几乎陷入了停滞状态。然而,在当前这轮深度学习热潮的带动下,对非结构化数据的建模和处理的研究开始广泛涌现,GNN 也迎来了自己的发展契机,顶级会议上的相关论文数量也迅猛增长。

    在第二个阶段,卷积被引入到了 GNN 的工作流程中。当用矩阵进行表示时,图与卷积擅长处理的图像具有很多相似性,也因此开启了在 GNN 中使用卷积的时代。一系列的工作将在谱空间上的图卷积转换为了拓扑空间上的近似,并在此基础上于 2017 年诞生了图卷积网络(GCN),其首次使用了逐层卷积来扩展感受野,图神经网络也由此开始了实际应用。

    我们现在正处于 GNN 发展的第三个阶段。图卷积已经出现了多种变体,注意力机制已被引入 GNN 中,此外还出现了图池化(Graph Pooling)技术和高阶 GNN。这一阶段出现的重要技术包括:

    • 变体卷积:Lanczos 网络(使用 Lanczos 算法来获取图拉普拉斯的低秩近似)、图小波神经网络(使用小波变换替代傅里叶变换)、双曲 GCN(将 GCN 构建到双曲空间中)。

    • 注意力机制:图注意力网络(使用可学习的自注意力替换固定的聚合权重)、门控注意力网络(加入了可学习的门来建模每个头的重要度)、谱式图注意力网络(将注意力应用于谱域中的高 / 低频组件)。

    • 图池化:SAGE(自注意图嵌入,在池化时使用自注意力来建模节点重要度)、通过图剪切实现图池化(通过图剪切算法得到的预训练子图实现图池化)、可微分图池化(DIFFPOOL,通过学习聚类分配矩阵以分层方式来聚合节点表征)、特征池化(EigenPooling,通过整合节点特征和局部结构来获得更好的分配矩阵)。

    • 高阶 GNN:高阶 GNN 是指通过扩展感受野来将高阶相近度(high-order proximities)编码到图中。高阶相近度描述的是距离更多样的节点之间的关系,而不仅是近邻节点之间的关系。这方面的研究工作包括 DCNN(通过把转移矩阵的幂级数堆叠起来而将邻接矩阵扩展为张量,然后相互独立地输出节点嵌入和图嵌入)、MixHop(使用了归一化的多阶邻接矩阵,然后汇集各阶的输出,从而同时得到高阶和低阶的相近度)、APPNP(使用了个性化 PageRank 来为目标节点构建更好的近邻关系)。

    下图简单总结了各种 GNN 变体之间的关系:

    二 图神经网络的研究进展

    了解了 GNN 的基本知识和发展脉络,接下来我们将踏入当前的前沿研究领域,解读近期的一些理论研究成果和设计创新。

    1 图神经网络的表达能力

    我们知道图在表达事物的关系方面能力非凡,但图神经网络表达能力的极限在哪里?清华大学计算机系助理研究员、清华大学「水木学者」、腾讯「犀牛鸟访问学者」黄文炳在课程中介绍了相关的研究进展。

    为了有效地评估 GNN 的表达能力,首先需要定义评估标准。目前来说,可通过三种典型任务来进行评估:图同构、函数近似和图检测 / 优化 / 评估。

    对于图同构任务,GNN 的目标是确定任意给定的两个图是否同构。这是一个很重要的任务。对于图分类任务而言,如果两个图是同构的,则 GNN 需要为这两个图输出同样的标签。

    但是,判定图是否同构的问题是一个 NP-hard 问题,传统的 Weisfeiler-Lehman(WL)测试方法除了少数图结构外,基本能否识别大多数图结构是否同构。而 GNN 能更好地解决这一问题吗?

    并不一定。2019 年,Xu et al. 和 Morris et al. 已经证明 GNN 至多做到与 WL 测试一样强大。之后,Xu et al. 还进一步证明,如果 GNN 中的聚合和读出函数(readout function)是单射函数,则 GNN 就与 WL 测试等效。

    对于函数近似任务,该任务的目标是判断 GNN 能否以任意准确度近似任何基于图的函数。因为 GNN 本身也是基于图的某种函数,因此 GNN 在这一任务上的表现将能体现其能力。实际上,DNN 也有类似的评估任务。我们知道,只要隐藏单元足够多,DNN 可以收敛到任何向量函数,这就是所谓的「通用近似定理」。所以我们很自然也会为 GNN 提出类似的问题。

    Maron et al. 提出了一种架构,对于拥有图不变映射层(graph invariant layer)和图等变映射层(graph equivariant layer)的 GNN,如果在一个非线性层(比如 ReLU)之后堆叠等变映射层,层层叠加,然后在最后添加图不变映射层。可以看出这样的模型能在输入的排列方式变化时保持映射不变性。这样的模型被称为图不变网络(INN)。

    INN 有多强大?Maron et al. 证明对于任意连续的不变式图函数,如果某些条件成立,我们可以找到特定的 INN 参数,使其能以任意精度估计该函数。这是图学习领域一大强有力的理论结果。对 GNN 而言,这就相当于对 DNN 而言的通用近似定理。

    看过了图同构和函数近似的近期进展,更进一步,这两者之间又有何关系呢?Chen et al. 2019 证明在满足一些条件的情况下,这两者其实是等效的。

    接下来,我们看看 GNN 是否有足够的表达能力来解决更困难的任务,比如寻找图中的最短路径或确定图中是否存在环。这些任务的难度很高,因为它们需要在节点层面执行很细粒度的推理。

    Loukas 证明 GNN 能解决这些任务,他得出结论:只要 GNN 的深度和宽度足够,而且节点之间具有可互相判别的属性,则 GNN 就能完成这些任务。这里深度是指 GNN 的层数,宽度则是指隐藏单元的维度。

    因此,总结起来,只要架构合适,GNN 其实具有非常强大的表达能力;也因此,要充分发掘 GNN 的真正实力,我们还需要更多架构方面的研究探索。

    2 训练深度图神经网络

    前面已经简单提到,深度对 GNN 的能力而言是非常重要的。这一点在深度神经网络(DNN)上也有体现——更深的网络往往具有强大的表达能力,可以说深度网络就是当前的人工智能发展热潮的最主要驱动力之一。

    那么,具体来说,更深度的 GNN 是否也有如此的优势呢?更深度的 GNN 能否像 CNN 一样获得更大的感受野?

    答案当然是肯定的。举个例子,寻找最短路径问题需要非常深的感受野来寻找所有可能的路径,环检测和子图查找问题也都需要较大的感受野。

    那么,我们可以怎样增大 GNN 的感受野,使其具备更强大的能力呢?为此,我们需要更深或更宽的 GNN。

    首先来看通过简单增加深度来扩展 GNN 的方法。可以看到,对于下图中的六种 GNN:GCN、GraphSAGE(进一步改进了池化方法)、ResGCN(使用了残差网络的思路)、JKNet(使用了 DenseNet 的思路)、IncepGCN(使用了 Inception-v3 的思路)、APPNP(借用了 PageRank 的思路),简单增加深度并不一定能提升准确度,甚至还可能出现相反的状况,比如 GCN、GraphSAGE 和 ResGCN 在深度增大时准确度反而显著下降。

    这不禁让人疑问:增加深度能提升表达能力的根本原因是什么?又是什么原因阻碍了 GNN 的深度扩展?

    近期的研究找到了有碍 GNN 变得更深的三大根本原因:过平滑(over-smoothing)、过拟合(overfitting)和训练动态变化(training dynamics)。其中后两者也是常见的深度学习问题,而过平滑则是图深度学习方面特有的问题。

    过平滑

    首先来看过平滑。GNN 本质上是逐层推送彼此相邻节点混合的表征,因此极端地看,如果层数无限多,那么所有节点的表征都将收敛到一个驻点,这也就与输入特征完全无关了,并会导致梯度消失问题。因此,过平滑的一个现象是模型的训练损失和验证损失都难以下降。那么,为什么会出现过平滑呢?

    我们以线性 GCN 来进行说明。首先,GCN 与平滑有何关联?一般来说,GCN 可被视为拉普拉斯平滑(Laplacian smoothing)的一种特殊形式,如下所示:

    这个过程意味着一个节点的新特征是根据其本身和相邻节点的加权平均而构建的。

    要知道这个过平滑过程发生的位置,我们先讨论一下 GCN 何时会因过平滑而失效?我们将讨论三种过平滑的情况。第一种是使用线性激活时,隐变量 H_L 会收敛到一个特定的点。第二种是使用 ReLU 激活时,H_L 会收敛到一个特定的平面 M。第三种是使用 ReLU 加偏差时,H_L 会收敛到一个特定的子立方体 O(M, r) 的表面。

    在使用线性激活的情况下,H_L 为什么会收敛到一个特定的点呢?实际上,这与 L 步随机游走有关。一个游走器从一个节点游走到其一个相邻节点的概率为「1 / 该节点的度」。经过 L 步游走后,游走的路径会形成一个已访问节点的序列。用数学公式表示,随机游走的过程实际上就是一个归一化的矩阵的 L 次幂乘以初始概率。

    然后,如果我们用一组在节点特征上的可学习参数替换这个初始概率,它就能转换成一个线性的 L 层 GCN。

    可以看出,基于随机游走的一些结论也适用于线性 GCN,其中一项便是随机游走在经过无限多步之后会收敛到一个驻点。

    详细地说,我们首先需要进行特征值分解,即将归一化的邻接矩阵分解为 n 个特征值 λ 及其对应的特征向量 u。

    将这个求和展开,可得到下式:

    这个图谱中的特征值有一个性质。即,假设一个图 g 包含 m 个互相连接的分量,则归一化邻接矩阵的特征值便由 m 个为 1 的最大特征值构成,其余的 λ 则在 (-1,1) 的开区间中。

    因此,当 lL 趋近无穷大时,最大的 m 项依然存在,因为其 λ 等于 1。但是,其余的项都将被忽略,因为这些 λ 的 l 次幂将趋近于零。这会使得隐变量 H_L 随网络深度增长而趋近于一个特定的点。

    另一方面,对于非线性的情况,H_L 将收敛到一个具有非线性激活 ReLU 的特定子空间 M。首先我们给出 M 子空间的定义:

    则随着层的深度增加,隐变量将越来越接近子空间 M。H_L+1 离该子空间的距离至少为:

    要注意,λ_m+1 是邻接矩阵中最大的非 1 特征值,s_l 则是模型参数 W_l 中最大的奇异值。

    接下来我们开始解析这个收敛公式。这个归一化邻接矩阵的收敛满足这一不等式。

    如果我们假设这个子空间的维度为 m,则 m 个最大的 λ 将位于该子空间,其余的则在 λ_m+1 的范围内。

    然后,模型参数 W_l 和 ReLU 的收敛分别满足下列两个不等式:

    有关这些不等式的更详细证明,请参阅 ICLR 2020 论文《Graph Neural Networks Exponentially Loss Expressive Power for Node Classification》。

    综合这些不等式,可得到隐变量的子空间距离沿层数变化的收敛性。可以看到,随着层数趋近于无穷大,子空间距离将趋近于 0,因此隐变量将会收敛到子空间 M。

    接下来是更一般的情况,使用 ReLU 加偏差的 GCN 又如何呢?H_L 将收敛到一个特定子立方体 O(M,r) 的表面上。首先,我们写出带偏差的 GCN 的公式:

    很显然,由于 b_l 到子空间的距离是一个常量,因此其收敛性就满足:

    可以看到,当 l 趋近无穷大时,不等式右侧部分就是一个无穷等比序列的和:

    因此,可以看到 H_L 将趋近于一个子立方体的表面,其与子空间 M 的距离为 r,而 r 就等于上式。

    总结一下,通过分析上面三种来自不同场景的情况,可以发现这三种情况之下存在一种普适的公式。我们可用以下不等式统一过平滑的情况:

    然后通过不同的 v 和 r 取值,我们可以得到不同的具体情况:

    过拟合和训练动态变化

    接下来我们看看过拟合问题。过拟合是深度学习的一个常见问题,当数据点数量少而参数数量很多时,就会出现这种情况。此时模型会与训练数据完全拟合(本质上就是记住了数据),而在验证数据上表现很差。

    训练动态变化也是深度学习领域的一大常见问题。根据链式法则,当模型变深时,s_l-1 乘以 λ_m+1 的结果小于 1,会出现梯度消失问题。如果我们将 RGB 色彩作为以下的图的节点特征,可以看到当层数达到 500 时,这些特征的梯度降为了 0,节点都变成了黑色,即 RGB=[0, 0, 0]。

    过拟合和训练动态变化是深度学习的常见问题,这里便不过多赘述了。下面我们看看在解决过平滑问题方面有什么研究进展。

    如何解决过平滑问题?

    首先,如何量化平滑?以 GCN 为例,我们先定义一个 ε- 平滑,使得对于任意大于特定层 L 的 l,隐变量 H_l 的子空间距离将小于 ε:

    然后,将 ε- 平滑层定义为能让 H_l 的子空间距离小于 ε 的最小层。但是,ε- 平滑层是很难推导的。因此,我们取一个松弛化的 ε- 平滑层作为上界。这个松弛化的 ε- 平滑层的公式如下:

    用层量化了平滑之后,我们就可以想办法来缓解过平滑问题了。

    注意这里的 λ_m+1 与邻接矩阵相关,s_max 与模型权重相关,这也暗示了存在两个缓解过平滑问题的方向。

    第一,我们可以通过处理邻接矩阵来缓解过平滑,即增大 λ_m+1,进而使得松弛化的 ε- 平滑层增大:

    那么我们如何做到这一点呢?很简单,在每 epoch 都丢弃一些边即可。研究证明,当丢弃一些边时,图上信息的传播速度会下降,子空间的维度会随连接的分量的增多而增加。丢弃边后的这两个现象都有助于缓解过平滑问题。

    更多详情和实验论证可见腾讯 AI Lab 的 ICLR 2020 论文《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》。

    第二,我们可以通过调整模型权重来缓解过平滑。为了增大 s_max,我们可以增大初始 W_ls 的值。下图展示了这种方法的效果。详见 ICLR 2020 论文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》。

    其它问题的解决方案

    ICLR 2020 上还有一篇论文《PairNorm: Tackling Oversmoothing in GNNs》提出了一种用于解决训练动态变化问题的方法。

    PairNorm 的思路对 GCN 输出进行居中和重新缩放或归一化,使得总的两两平方距离保持不变。如图所示,GCN 的输出点在图卷积之后通常会更接近彼此。但通过使用 PairNorm,新输出的两两距离能与输入的距离保持相似。

    另一种克服训练动态变化的方法是在结构中添加捷径。JKNet、IncepGCN 和 APPNP 等 GNN 能在深度结构中保持性能的方法就是如此。

    因为这三个模型全都包含通过聚合层到终点的捷径,因此浅的信息可以传播到最后的层,也因此这些模型实际上仍旧是「浅模型」。

    顺便一提,这些不同的 GNN 结构仍然满足过平滑的一般情况:

    详细的分析请参考论文:《Tackling Over-Smoothing for General Graph Convolutional Networks》(https://arxiv.org/pdf/2008.09864.pdf)。总结一下,在这些新的理论进展的帮助下,训练更深度 GNN 的问题已经得到了初步解答。

    3 大规模图神经网络

    真实世界的图可能具有非常大的规模,因此让 GNN 有能力处理大规模图是非常重要的研究课题。

    基本的 GNN 通常无法处理大规模图,因为其通常无法满足巨大的内存需求,而且梯度更新的效率也很低。

    为了让 GNN 有能力处理大规模图,研究者已经提出了三种不同的采样范式:基于节点的采样、基于层的采样和基于子图的采样。

    其中,逐节点采样是根据目标节点执行采样,而逐层采样是基于卷积层来执行采样,逐图采样则是从原图采样子图,然后使用子图进行模型推理。

    根据这三种范式,可以知道为了实现大规模 GNN,我们需要解决两个问题:如何设计高效的采样算法?如何保证采样质量?

    近些年在构建大规模 GNN 方面已经出现了一些成果,下图给出了这些成果的时间线:

    接下来我们将按这一时间线简要介绍这些研究成果。

    首先来看 GraphSAGE,其可被视为原始 GCN 的一种扩展:在 GCN 的平均聚合器的基础上增加了许多广义上的聚合器,包括池化聚合器和 LSTM 聚合器。不同的聚合器也会对模型产生不同的影响。此外,在聚合之后,不同于 GCN 使用的求和函数,GraphSAGE 使用了连接函数来结合目标节点机器邻近节点的信息。这两大改进是基于对 GCN 的空间理解得到的。

    为了实现大规模 GNN,GraphSAGE 首先采用了 mini-batch 的训练方法,这样可以降低训练期间的通信成本。在每次迭代中,仅会考虑用于计算表征的节点。但是,mini-batch 训练可能出现邻近节点扩张的问题,使得 mini-batch 在层数较多时需要采用图的大部分乃至全部节点!

    为了解决这一问题并进一步提升性能,GraphSAGE 采用了固定采样个数的的邻近采样方法,即每层都采样固定大小的邻近节点集合。

    从上右图可以看到,采用固定采样个数的采样方法后,采样节点的数量降低了。当图的规模很大时,这一差距会更加显著。不过,GraphSAGE 在网络层数较大时依然无法避免邻近节点扩张问题,采样质量上也无法得到保证。

    为了进一步降低采样规模和得到一些理论上的质量保证,VR-GCN 整合了基于控制变量的估计器(CV 采样器)。其可以维持历史隐藏嵌入(historical hidden embedding)来获得更好的估计,这个历史隐藏嵌入可用于降低方差,进而消除方差,实现更小的采样规模。VR-GCN 的数学形式如下:

    不过,VR-GCN 也有一个缺点:需要额外的内存来存储所有的历史隐藏嵌入,这使得我们难以实现大规模扩展。

    上面我们可以看到,基于节点的采样方法并不能彻底解决邻近节点扩张问题。接下来看基于层的采样方法。

    FastGCN 提出从 Functional generalization 的角度来理解 GCN,并为 GCN 给出了基于层的估计形式:

    基于此,我们可以在每层都采样固定数量的节点。更进一步,FastGCN 还提出了基于重要度的采样模式,从而降低方差。在采样过程中,每一层的采样都是相互独立的,而且每一层的节点采样概率也保持一致。下图是 GCN 与 FastGCN 的对比:

    可以看出,FastGCN 的计算成本显著更低,而且研究表明,这种采样模式从期望上并不会丢失太多信息,因为其在执行重要度采样时会进行随机化处理,通过足够多 epoch 的训练,每个节点和链接都有期望被采样。

    可以看出,基于层采样的 FastGCN 彻底解决了邻近节点扩张问题,而且采样方法有质量保证。但是该方法的缺点是无法获得层之间的相关性,模型的表现也可能受到负面影响。

    为了更好地获得层之间的相关性,ASGCN 提出了自适应层式采样方法,即根据高层采样结果动态调整更低层的采样概率。如下左图所示,在对底层采样的时候 ASGCN 会考虑采样高层采样的邻居节点,使得层之间的相关性得到很好的保留。如下右图所示,整个采样过程是自上而下的。我们首先采样输出层的目标节点,然后根据其采样结果采样中间层的节点,然后重复这个过程直到输入层。在采样过程中,每层采样节点的数目也会保持一个固定值。

    另外,为了降低采样方差,ASGCN 还引入了显式方差下降法(explicit variance reduction),以优化损失函数中的采样方差。

    总体来说,ASGCN 能获得更好的性能,方差控制也更好,但由于采样过程有额外的层间依赖关系需要考虑,采样效率会受到一些影响。

    接下来出现了基于子图的采样方法。ClusterGCN 首先使用图分割算法将图分解为更小的聚子图,然后在子图层面上组成随机的分批,再将其输入 GNN 模型,从而降单次计算需求。

    通过限制子图的大小,这种方法也可以有效避免邻近节点扩张问题,因为在每一层中,采样的范围都不会超过聚类子图。

    不过,ClusterGCN 的论文并没有对这种方法的采样质量进行实证研究。

    GraphSAINT 则并未在采样过程中使用聚类算法(这会引入额外的偏差和噪声),而是直接通过子图采样器来采样用于 mini-batch 训练的子图。其给出了三种采样器的构建方式,分别为基于节点的采样、基于边的采样和随机游走采样,如下所示:

    GraphSAINT 还从理论上分析了控制采样器的偏差和方差的方法,其中包括用于消除采样偏差的损失归一化和聚合归一化方法:

    另外,该论文还提出通过调整边采样概率来降低采样方差。作为当前最佳的方法,GraphSAINT 的表现也在实验中得到了证明。具体详情请浏览 ICLR 2020 论文《GraphSAINT: Graph Sampling Based Inductive Learning Method》。

    很显然,大规模图神经网络方面还有很大的进一步研究空间,比如更高效的采样技术、适用于异构图或动态图的架构等等。

    4 图神经网络的自监督 / 无监督学习

    前面讨论的 GNN 的表达能力、深度和规模都是基于监督式方法,也就是说我们有输入图的标签。但在现实生活中,获取这些标签却并非易事。比如在分子属性预测任务中,为了获取基本真值标签,我们必需专业人士的协助。此外,训练任务与测试任务并不总是一致的,比如对于社交网络推荐任务,我们可能在训练中使用的是节点用户购买商品的数据,但我们却想知道节点用户是否想看某部电影,此时训练标签可能对测试就毫无作用了。因此,我们需要研究如何在没有标签的情况下训练 GNN。

    目前在自监督图学习方面已经有一些研究成果了。我们可以根据它们的机制将其分为两大类别:预测方法和基于信息论的方法。而根据所要解决的任务的差异,又可以分为两种情况:节点分类和图分类。

    预测方法

    首先来看预测方法。Yann LeCun 说过:「自监督学习的系统是根据其输入的某些部分来预测输入的其它部分。」这就意味着在自监督学习中,输入的结构是很重要的。而图就是高度结构化的,因此天生就很适合自监督学习。

    对于节点分类任务,实现自监督学习的方法通常有两种。一是强制使用相邻节点之间的相似性,二是基于邻近节点执行每个节点的重建。

    首先,我们来看第一种方法,这种方法由 GraphSAGE 引入,其基本思想是强制每个节点与其邻近节点有相似的表征。在这种情况下,设 h_u 为 h_v 的邻近节点,则我们的目标是最大化它们的内积。我们称这些邻近节点为正例样本。然后,我们最小化 h_v 与通过负采样得到的其它节点之间的相似性,这些节点通常是从整个图均匀采样的。这样,我们就可以使用反向传播来训练 GNN 的参数了。

    至于第二种方法,来自 Durán & Niepert 提出的 EP-B,其首先会计算邻近节点的表征的聚合。目标是最小化重建的结果与真实表征之间的距离。与此同时,又最大化这个聚合表征与其它节点的表征之间的距离。

    EP-B 和 GraphSAGE 的主要区别是 EP-B 强制使用了邻近节点和每个其它节点的聚合之间的相似性,而 GraphSAGE 则直接强制使用了邻近节点与每个节点的相似性。

    在图分类方面又有哪些方法呢?

    我们要介绍的第一种方法是 N-Gram Graph。该方法分为两个阶段:节点表征阶段和图表征阶段。节点表征阶段使用了一种传统的自监督式节点嵌入方法 CBoW 来学习节点表征。在第二个阶段,由于已有节点表征,则首先会为每条长度为 n 的路径计算表征,称为 n-gram 路径。这个路径表征是以该路径中每个节点的表征的积形式得到的。因此,它们将历经图中所有的 n-gram 路径并归总所有路径的表征。最终的图表征是通过将 1-gram 到 T-gram 的路径连接起来而得到的。

    事实上,这样的计算就等于没有训练的 GNN。N-Gram Graph 的训练无需任何监督。

    另一种用于图分类的方法是 PreGNN,它同样分为两个阶段:第一个阶段是执行节点表征(但使用了两种全新方法),第二阶段是使用简单的读出基于所有节点获取图层面的表征。但它是通过一种监督式策略交叉熵来训练图层面的表征。该研究指出,节点层面和图层面的训练对最终性能而言都很重要。

    因为其第二个阶段很普通,所以我们只解读一下第一个阶段。

    在这一阶段,PreGNN 提出了两种损失函数。周围结构预测(context prediction)是强制节点表征与其周围结构相似。另外我们还执行负采样来最小化 h_v 与其它节点的周围结构之间的相似性。这个方法的思路很简单:每个节点周围的结构定义了该节点的局部拓扑结构。

    另一个损失则是属性掩码(attribute masking)。这个损失的设计灵感来自强大的 NLP 模型 BERT。简单来说,就是随机地使用掩码替换节点,然后构建训练损失函数来预测输入。方法很简单,但效果很好。

    另一种值得一提的方法是 GCC。该方法使用了对比学习(contrastive learning)来执行图层面的无监督学习。不过 GCC 的一大主要问题是没有节点层面的训练。

    总结一下,在图分类任务上,N-Gram Graph 和 PreGNN 都使用了节点层面的自监督,而 GCC 使用了图层面的自监督。那么,我们自然会问:能不能同时使用节点层面和图层面的自监督?

    答案当然是肯定的。这就要谈到腾讯 AI Lab 研究团队提出的 GROVER 了。

    GROVER 同样分为两个阶段。在节点阶段,我们还同时考虑了边,但为了说明简单,这里仅讨论节点表征过程。在这一阶段,首先为每个节点提取一个词典池。我们称之为 key。然后我们像 BERT 一样为每个节点加掩码,然后预测每个节点周围的局部结构。如果局部结构与词典中的一个 key 匹配,则在该维度上输出 1,否则便输出 0。注意这是一个多标签分类问题,因为每个节点的局部结构通常有多个。这样,我们仅需要一类掩码就能做到 PreGNN 的两件事。

    然后在图阶段,预测是相似的。我们也首先提取 graph motif,其由典型的官能团(比如苯环)构成。然后我们使用 GNN 获取每个图的输出。使用该输出,我们将预测这个图是否包含这些 graph motif。注意这也是一个多标签分类问题。

    除此之外,腾讯 AI Lab 还在该研究中提出了一种类似 Transformer 的强大 GNN 模型:GTransformer。其首先会使用一种新提出的名为 dyMPN 的 动态扩展范围 MPNN 来获取每个输入图的 key、查询和值,然后会像 Transformer 一样获取最终输出结果。实验结果证明了这一模式的强大能力。

    以上这些就是 GROVER 的关键组件。更进一步的,我们还实现了一个分布式的图训练框架,最终成功在 1000 万个无标注分子数据上预训练带有 1 亿个参数的大模型。

    使用这个预训练的模型,我们可以针对下游任务进行微调。在此基础上,GROVER 可以取得显著优于 MPNN 和 DMPNN 等传统方法的表现,同时也优于 N-Gram 和 PreGNN 等自监督方法。

    基于信息的方法

    介绍了预测方法,我们再来看基于信息的方法。

    优良的表征应该能将输入中的大量信息保存下来。受此启发,Vincent et al. 在 2010 年提出使用自动编码器来进行表征学习,这意味着隐藏表征应该可以解码到与其输入一样。

    但自动编码器资源消耗高,既需要编码,也需要解码,而在图领域,如何解码图仍还是一个有待解决的问题。那么还有其它可以直接衡量表征与输入之间的信息的方法吗?有的,那就是互信息(mutual information)。

    给定两个随机变量,互信息的定义是它们的边界属性和关节属性的积之间的 KL 散度,这又可以进一步推导为熵减去条件熵。

    互信息为什么可以计算信息关系?我们可以这样看,如果 X 和 Y 互相独立,且 p(X)p(Y)=p(X,Y),则互信息等于 0,这表明 X 和 Y 不相关。这是合理的,因为 X 和 Y 互相独立。如果条件熵为 0,则 X 和 Y 确定是相关的,则互信息输出为最大值。

    Hjelm et al. 2019 证明执行自动编码是计算互信息的重建误差的一个下限。

    计算互信息是很困难的,近些年方才出现一些可行的方法。这里有三种典型的方法(MINE、JSD MI 和 infoNCE MI),其基本思想是学习一个神经网络来最大化互信息的一个替代函数。详情请参阅各论文。

    回到图,我们能否使用互信息来实现图的自监督学习?DGI 是这方面首个研究成果,其目标设定为最大化输入的节点特征 X 和邻接矩阵 A 与输出表征 h_i 之间的互信息。DGI 使用了 JSD 估计器,其中包含正例项和负例项。

    但直接计算互信息的难度不小,我们可能需要另一个 GNN 作为互信息的替代。DGI 使用了表征的读出 s 来替代输入。如下图所示,原图有两个输入,其中错误的图是负例,然后我们用同样的 GNN 得到它们的输出,之后再执行读出函数得到 s。s 可以替代原目标中的 X,A,得到替代目标函数。

    DGI 证明这种操作不会导致信息损失,其还证明这种替换方式实际上就等同于真正的互信息。

    不过 DGI 仍还有一些问题。第一是它需要读出函数来计算互信息,而且这个读出函数需要是单射式的,这并不容易保证。另外它还需要构建错误的图来得到负例,因此效率不高。而在实验中,DGI 需要为不同的任务使用不同的编码器,这并不实用。

    针对这些问题,清华大学、西安交通大学与腾讯 AI Lab 合作提出了 GMI,其基本思想是不使用读出函数和错误样本,而是直接计算互信息。

    在 GMI 中,首先分两部分定义互信息。一是特征互信息,仅度量节点特征和表征之间的信息关系。二是拓扑互信息,这是预测的边和原始邻接矩阵之间的互信息。

    很显然,这一方法能同时考虑到边和特征,而无需读出函数或错误样本。更重要的是,特征互信息还能进一步分解。

    我们证明:特征互信息可以分解为局部互信息的加权和。而每个局部互信息计算的是每个节点及其表征之间的互信息。权重取决于不同的情况,将它们设置为与预测的边一样也不错。然后我们可以使用 JSD 互信息估计器来计算特征互信息和边互信息。

    在节点分类任务上的实验结果证明 GMI 有更优的表现,相关的代码也已经发布:https://github.com/zpeng27/GMI

    至于用于图分类的基于信息的方法,可参看 ICLR 2020 论文《InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization》,这里不再过多赘述。

    三 图神经网络的应用进展

    图神经网络作为一种有效的深度学习工具,已经在分子属性预测、生物学分析、金融等许多领域得到了应用。这里以腾讯 AI Lab 实现的在社交网络和医疗影像领域的应用为例,介绍图神经网络的应用进展。

    1 用于社交网络的 GNN

    首先来看一篇 WWW 2019 论文《Semi-supervised graph classification: A hierarchical graph perspective》,其中腾讯 AI Lab 提出了使用分层图实现半监督图分类的方法。

    分层图是指一组通过边互相连接在一起的图实例,如图所示:

    在许多现实应用中,很多数据都可以建模成分层图的形式,比如具有分组结构的社交网络和文档集合(比如具有引用关系的 graph-of-words)。如上所示,假设我们有一个「用户 - 分组」分层图,我们知道其中部分标签,我们可以怎样预测其它组的标签?

    如果仅考虑组之间的联系,那么这个问题就又回到了节点分类。但是,可以看到每一组都有自己的用户图,忽略这样的信息并不合适。为了在用户和分组层面上利用图信息,我们面临着这样的难题:如何将任意大小的图表征为固定长度的向量?如何整合实例层面和分层层面的信息?

    首先来看第一个问题。图表征与节点表征在不同的层面上;在节点层面上图 G 会被投射到大小为 n×v 的隐藏空间中;而在图层面上图 G 会被投射成大小为 v 的隐藏向量。因此,为了将节点层面的空间转换成图层面的向量,这里引入了自注意力图嵌入(SGAE)。

    首先,将单个图通过一个两层 GCN,得到节点层面的表征 H,其大小为 n×v,然后根据上图中的 S 计算自注意力。在经过一个 softmax 函数之后,会得到一个具有 r 个头的多头自注意分数,其大小为 r×n。然后,如果我们将这些分数应用到节点层面的表征,我们就会得到大小固定为 r×v 的矩阵。SAGE 有三大优势:1)其大小因自注意力而保持不变,2)因为 GCN 平滑而具有排列不变性,3)因为自注意力而能使用节点重要度。

    对于第二个问题:如何整合实例层面和分层层面的信息?这里实例层面是基于 SAGE 的图层面学习,分层层面模型是节点层面的学习。我们使用了特征共享来连接 SAGE 的输出和 GCN 的输入。然后又引入一种新的分歧损失(disagreement loss)来最小化实例分类器和分层分类器之间的不一致情况。

    另外,我们还使用了主动学习来解决样本数量少的问题。我们使用了分歧损失来为外部标注选择实例。有关这两种算法 SEAL-AI 和 SEAL-CI 的详情以及相关实验结果请查阅论文。

    接下来看腾讯 AI Lab 另一项被 AAAI 2020 接收的研究《Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks》,提出了一种通过双向图卷积网络实现社交网络谣言检测的新思路。

    谣言可算是当今社会面临的一大顽疾。这篇论文提出通过关注和转发关系来检测社交媒体上的谣言。不管是谣言还是新闻,它们的传播模式都是树结构的。但通常来说,谣言的传播有两个属性。第一如下图 b 所示,其会沿一条关系链进行很深的传播。第二如图 c,谣言在社交媒体上传播时散布很宽。举个例子,一个 Twitter 用户可能有大量关注者。

    为了同时获取谣言传播的这两种属性,我们设计了一种基于 GCN 的新模型。这个用于谣言检测的双向 GCN 包含 4 个组件:1)两个不同的有向图,用于描述谣言的传播和扩散度;2)使用二层 GCN 来计算高层面的节点表征;GCN 不仅能学习特征信息,还能学习谣言的传播拓扑结构;3)经过观察,根节点通常就已经包含了谣言或新闻的主要内容,而关注者通常只是不带任何内容进行转发,因此通过将根特征连接到树中的每个节点,可以增强每层的隐藏特征;4)分别根据节点表征对传播和扩散度的两个表征进行池化处理。这两个表征再被聚合到一起得到最终结果。

    我们在 Twitter15、Twitter16、Weibo 三个常用基准上的实验研究对这一方法的效果进行验证,结果表明新方法具有显著更优的表现。

    此外,我们还评估了谣言的早期侦测,此时仅给出谣言树上非常有限的节点并且还设置了一个侦测截止时间,结果表明基于图的方法非常适用于早期发现谣言。

    2 用于医疗影像的 GNN

    医疗影像也是 GNN 的一个重要应用场景,腾讯 AI Lab 近两年在这一领域取得了一些重要的研究成果。首先来看腾讯 AI Lab 的 MICCAI 2018 论文《Graph CNN for Survival Analysis on Whole Slide Pathological Images》,其中提出使用图卷积网络基于全切片病理图像进行生存分析。

    生存分析的目标是预测特定事件发生的风险,这类事件包括器官衰竭、药物不良反应和死亡。有效的分析结果具有重要的临床应用价值。但实际操作时却面临着许多困难。

    首先,全切片病理图像(WSI)分析是一个需要大量计算的过程,因为单张 WSI 的数据量就超过 0.5 GB,而且其中包含数百万个细胞,还涉及局部特征和全局特征,因此非常复杂。另外,如何将 WSI 的拓扑特征用于生存分析也还是一个有待解决的问题。

    为此,我们提出将 WSI 建模成图,然后开发了一种图卷积神经网络(Graph CNN),其使用了注意力机制,可通过提供 WSI 的最优图表征来实现更好的生存分析。

    实验结果表明,这种新方法优于之前的其它方法。

    这一部分同时也介绍了近年来 GNN 在医疗图像上的其他工作:在 IPMI2019 发表的《Graph Convolutional Nets for Tool Presence Detection in Surgical Videos》中,作者提出使用 GCN 来检测手术视频中的工具,这是自动手术视频内容分析的核心问题之一,可用于手术器材使用评估和手术报告自动生成等应用。这个模型使用了 GCN 沿时间维度通过考虑连续视频帧之间的关系来学习更好的特征。

    而在 MICCAI 2020 发表的论文《Graph Attention Multi-instance Learning for Accurate Colorectal Cancer Staging》中,作者提出使用图注意力多实例学习来准确判断结直肠癌是处于早期、中期还是晚期。

    总结和展望

    在这次课程中,我们介绍了图神经网络的发展历史、包括图神经网络的表达能力、深度、大规模扩展、自监督 / 无监督学习等方面的研究进展,也简要介绍了腾讯 AI Lab 在图神经网络的社交网络和医疗影像应用方面的一些初步成果。

    图深度学习领域仍处于发展之中,有很多有趣的问题等待解决,例如逆向图识别(IGI),即我们在图分类问题中,是否可以根据图的标签来推断每个节点的标签?子图识别,即如何在图中找到关键的子图同时还有图与多示例学习问题的结合形成多图示例学习问题,以及在图上进行攻击与防御相关的图深度学习鲁棒性的研究。最后,层次图也是一个热门的研究方向。图神经网络必将在人工智能领域未来的研究和应用中扮演更重要的角色。

    推荐阅读

    浅析图卷积神经网络

    一文带你入门目前大热的图神经网络

    END

    备注:GNN

    GNN交流群

    图神经网络、GNN、GCN等技术,

    若已为CV君其他账号好友请直接私信。

    我爱计算机视觉

    微信号:aicvml

    QQ群:805388940

    微博知乎:@我爱计算机视觉

    投稿:amos@52cv.net

    网站:www.52cv.net

    在看,让更多人看到  

    展开全文
  • 感谢阅读腾讯AI Lab微信号第104篇文章。本文将详解图深度学习的历史、最新进展应用。前言人工智能领域近几年历经了突飞猛进的发展。图像、视频、游戏博弈、自然语言处理、金融等大数据分析...

    感谢阅读腾讯AI Lab微信号第104篇文章。本文将详解图深度学习的历史、最新进展及应用。

    前言

    人工智能领域近几年历经了突飞猛进的发展。图像、视频、游戏博弈、自然语言处理、金融等大数据分析领域都实现了跨越式的进步并催生了很多改变了我们日常生活的应用。近段时间,图神经网络成为了人工智能领域的一大研究热点,尤其是在社交网络、知识图谱、化学研究、文本分析、组合优化等领域,图神经网络在发掘数据中隐含关系方面的强大能力能帮助我们获得更好的数据表达,进而能让我们做出更好的决策。比如通过图神经网络梳理人类社会关系网络的演变,可有望帮助我们理解人类社会的底层运作模式,进而让我们离理想社会更近一步。

    在今年的计算机协会国际数据挖掘与知识发现大会(ACM SIGKDD,简称 KDD)上,图神经网络备受研究关注的现状得到了充分体现:粗略统计,今年 KDD 接收的 216 篇论文(research track)中有近 40 篇与图神经网络相关。也因此,一场为期一天的图神经网络相关课程得到了参会人员的重点关注。该联合课程的主题为「图深度学习:基础、进展和应用(Deep Graph Learning: Foundations, Advances and Applications)」,由腾讯AI Lab、清华大学、香港中文大学等机构联合组织,从基础的图概念一直谈到了当今最前沿的图神经网络研究进展。

    本次课程分为两个主题。本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程Theme II: Advances and Applications部分的核心内容,Theme I以及更多详细的内容可参看课程幻灯片及相关论文:https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

    为了解决图学习中的一系列具有挑战性的问题, 探索图学习应用的边界并在于助力公司各类与图数据相关的业务。腾讯AI Lab于2017年下半年开始布局图深度学习的研究,积极探索图深度学习的应用边界。并且在各大机器学习数据挖掘顶级会议上发表多篇文章,涉及大图计算,超深图神经网络,无监督图学习,图的对抗攻击,图的样本学习等。在未来我们将探索图深度学习在广泛场景的应用,如社交推荐,药物研发等。使其能够真正造福人类。

    一、图与图神经网络

    1.什么是图?

    汉语中的「图」可以对应成英语中多个不同的词:image、picture、map 以及本文关注的 graph。图(graph)也可称为「关系图」或「图谱」,是一种可用于描述事物之间的关系的结构。图的基本构成元素为顶点和连接顶点的边。根据边是否存在方向的性质,还可分为有向图和无向图。一般而言,我们通常可将图表示成点和连接点的线的形式,这有助于我们更直观地理解,如下图所示:

    但为便于计算机处理,我们也可用矩阵来表示图。比如如果定义当 v_i 与 v_j 相连时,A[i,j]=1,否则 A[i,j]=0,则可将以上矩阵表示为邻接矩阵 A:

    图具有很强的表征能力。物理学系统建模、蛋白质预测、疾病分类以及许多文本和图像处理任务都可以表示成图结构的数据,比如图可用于表示文本中句子的依赖关系和图像中事物的相对位置,也可以用于分析社交网络中的信息传播和用户关系,还能通过分析分子之间的关联来发现新药。

    2.图神经网络

    近些年在大数据和硬件发展双重助力下迎来跨越式发展的深度神经网络技术让我们具备了分析和理解大规模图数据的能力。总体而言,图分析任务可分为节点分类、连接预测、聚类三类。

    图神经网络(GNN)就是处理图数据的神经网络,其中有两种值得一提的运算操作:图过滤(Graph Filter, 分为基于空间的过滤和基于谱的过滤)和图池化。其中图过滤可细化节点特征,而图池化可以从节点表示生成图本身的表示。

    一般来说,GNN 的框架在节点层面上由过滤层和激活构成,而对于图层面的任务,则由过滤层、激活和池化层组成不同的模块后再连接而成。

    在 GNN 的实现方面,目前最常用的方法是消息传递框架(Message Passing Framework)。简单总结起来,该框架分为两个步骤。

    第一步是消息生成步骤。首先,从近邻节点收集状态数据,然后使用对应函数生成当前节点的消息。在第二步中,我们更新目标节点的状态。

    目前大多数空间式 GNN 都可以构建为某种消息传递过程,而且事实上目前大多数用于图的深度学习工具包大都采用了这一框架,比如 Deep Graph Library 和 PyTorch Geometric。

    3.图神经网络的发展历史

    图神经网络(GNN)并不是一个新事物,最早的GNN 的历史可以追溯到 1997 年,粗略总结起来,GNN 的发展过程大致可分为三个阶段。

    在第一个阶段,GNN 所使用的主要方法是基于循环神经网络(RNN)的扩展。众所周知,RNN 擅长处理序列数据,而反过来,序列数据则可被视为一种特殊模式的图。因此,早期的一些工作(TNN97 / TNN08)将处理序列数据的 RNN 泛化用于树和有向无环图(DAG)等特殊的图结构。但那之后这一领域的发展几乎陷入了停滞状态。然而,在当前这轮深度学习热潮的带动下,对非结构化数据的建模和处理的研究开始广泛涌现,GNN 也迎来了自己的发展契机,顶级会议上的相关论文数量也迅猛增长。

    在第二个阶段,卷积被引入到了 GNN 的工作流程中。当用矩阵进行表示时,图与卷积擅长处理的图像具有很多相似性,也因此开启了在 GNN 中使用卷积的时代。一系列的工作将在谱空间上的图卷积转换为了拓扑空间上的近似,并在此基础上于 2017 年诞生了图卷积网络(GCN),其首次使用了逐层卷积来扩展感受野,图神经网络也由此开始了实际应用。

    我们现在正处于 GNN 发展的第三个阶段。图卷积已经出现了多种变体,注意力机制已被引入 GNN 中,此外还出现了图池化(Graph Pooling)技术和高阶 GNN。这一阶段出现的重要技术包括:

    ●  变体卷积:Lanczos 网络(使用 Lanczos 算法来获取图拉普拉斯的低秩近似)、图小波神经网络(使用小波变换替代傅里叶变换)、双曲 GCN(将 GCN 构建到双曲空间中)。

    ●  注意力机制:图注意力网络(使用可学习的自注意力替换固定的聚合权重)、门控注意力网络(加入了可学习的门来建模每个头的重要度)、谱式图注意力网络(将注意力应用于谱域中的高/低频组件)。

    ●  图池化:SAGE(自注意图嵌入,在池化时使用自注意力来建模节点重要度)、通过图剪切实现图池化(通过图剪切算法得到的预训练子图实现图池化)、可微分图池化(DIFFPOOL,通过学习聚类分配矩阵以分层方式来聚合节点表征)、特征池化(EigenPooling,通过整合节点特征和局部结构来获得更好的分配矩阵)。

    ●  高阶 GNN:高阶 GNN 是指通过扩展感受野来将高阶相近度(high-order proximities)编码到图中。高阶相近度描述的是距离更多样的节点之间的关系,而不仅是近邻节点之间的关系。这方面的研究工作包括 DCNN(通过把转移矩阵的幂级数堆叠起来而将邻接矩阵扩展为张量,然后相互独立地输出节点嵌入和图嵌入)、MixHop(使用了归一化的多阶邻接矩阵,然后汇集各阶的输出,从而同时得到高阶和低阶的相近度)、APPNP(使用了个性化 PageRank 来为目标节点构建更好的近邻关系)。

    下图简单总结了各种 GNN 变体之间的关系:

    二、图神经网络的研究进展

    了解了 GNN 的基本知识和发展脉络,接下来我们将踏入当前的前沿研究领域,解读近期的一些理论研究成果和设计创新。

    1.图神经网络的表达能力

    我们知道图在表达事物的关系方面能力非凡,但图神经网络表达能力的极限在哪里?清华大学计算机系助理研究员、清华大学「水木学者」、腾讯「犀牛鸟访问学者」黄文炳在课程中介绍了相关的研究进展。

    为了有效地评估 GNN 的表达能力,首先需要定义评估标准。目前来说,可通过三种典型任务来进行评估:图同构、函数近似和图检测/优化/评估。

    对于图同构任务,GNN 的目标是确定任意给定的两个图是否同构。这是一个很重要的任务。对于图分类任务而言,如果两个图是同构的,则 GNN 需要为这两个图输出同样的标签。

    但是,判定图是否同构的问题是一个 NP-hard 问题,传统的 Weisfeiler-Lehman(WL)测试方法除了少数图结构外,基本能否识别大多数图结构是否同构。而 GNN 能更好地解决这一问题吗?

    并不一定。2019 年,Xu et al. 和 Morris et al. 已经证明 GNN 至多做到与 WL 测试一样强大。之后,Xu et al. 还进一步证明,如果 GNN 中的聚合和读出函数(readout function)是单射函数,则 GNN 就与 WL 测试等效。

    对于函数近似任务,该任务的目标是判断 GNN 能否以任意准确度近似任何基于图的函数。因为 GNN 本身也是基于图的某种函数,因此 GNN 在这一任务上的表现将能体现其能力。实际上,DNN 也有类似的评估任务。我们知道,只要隐藏单元足够多,DNN 可以收敛到任何向量函数,这就是所谓的「通用近似定理」。所以我们很自然也会为 GNN 提出类似的问题。

    Maron et al. 提出了一种架构,对于拥有图不变映射层(graph invariant layer)和图等变映射层(graph equivariant layer)的 GNN,如果在一个非线性层(比如 ReLU)之后堆叠等变映射层,层层叠加,然后在最后添加图不变映射层。可以看出这样的模型能在输入的排列方式变化时保持映射不变性。这样的模型被称为图不变网络(INN)。

    INN 有多强大?Maron et al. 证明对于任意连续的不变式图函数,如果某些条件成立,我们可以找到特定的 INN 参数,使其能以任意精度估计该函数。这是图学习领域一大强有力的理论结果。对 GNN 而言,这就相当于对 DNN 而言的通用近似定理。

    看过了图同构和函数近似的近期进展,更进一步,这两者之间又有何关系呢?Chen et al. 2019 证明在满足一些条件的情况下,这两者其实是等效的。

    接下来,我们看看 GNN 是否有足够的表达能力来解决更困难的任务,比如寻找图中的最短路径或确定图中是否存在环。这些任务的难度很高,因为它们需要在节点层面执行很细粒度的推理。

    Loukas 证明 GNN 能解决这些任务,他得出结论:只要 GNN 的深度和宽度足够,而且节点之间具有可互相判别的属性,则 GNN 就能完成这些任务。这里深度是指 GNN 的层数,宽度则是指隐藏单元的维度。

    因此,总结起来,只要架构合适,GNN 其实具有非常强大的表达能力;也因此,要充分发掘 GNN 的真正实力,我们还需要更多架构方面的研究探索。

    2.训练深度图神经网络

    前面已经简单提到,深度对 GNN 的能力而言是非常重要的。这一点在深度神经网络(DNN)上也有体现——更深的网络往往具有强大的表达能力,可以说深度网络就是当前的人工智能发展热潮的最主要驱动力之一。

    那么,具体来说,更深度的 GNN 是否也有如此的优势呢?更深度的 GNN 能否像 CNN 一样获得更大的感受野?

    答案当然是肯定的。举个例子,寻找最短路径问题需要非常深的感受野来寻找所有可能的路径,环检测和子图查找问题也都需要较大的感受野。

    那么,我们可以怎样增大 GNN 的感受野,使其具备更强大的能力呢?为此,我们需要更深或更宽的 GNN。

    首先来看通过简单增加深度来扩展 GNN 的方法。可以看到,对于下图中的六种 GNN:GCN、GraphSAGE(进一步改进了池化方法)、ResGCN(使用了残差网络的思路)、JKNet(使用了 DenseNet 的思路)、IncepGCN(使用了 Inception-v3 的思路)、APPNP(借用了 PageRank 的思路),简单增加深度并不一定能提升准确度,甚至还可能出现相反的状况,比如 GCN、GraphSAGE 和 ResGCN 在深度增大时准确度反而显著下降。

    这不禁让人疑问:增加深度能提升表达能力的根本原因是什么?又是什么原因阻碍了 GNN 的深度扩展?

    近期的研究找到了有碍 GNN 变得更深的三大根本原因:过平滑(over-smoothing)、过拟合(overfitting)和训练动态变化(training dynamics)。其中后两者也是常见的深度学习问题,而过平滑则是图深度学习方面特有的问题。

    过平滑

    首先来看过平滑。GNN 本质上是逐层推送彼此相邻节点混合的表征,因此极端地看,如果层数无限多,那么所有节点的表征都将收敛到一个驻点,这也就与输入特征完全无关了,并会导致梯度消失问题。因此,过平滑的一个现象是模型的训练损失和验证损失都难以下降。那么,为什么会出现过平滑呢?

    我们以线性 GCN 来进行说明。首先,GCN 与平滑有何关联?一般来说,GCN 可被视为拉普拉斯平滑(Laplacian smoothing)的一种特殊形式,如下所示:

    这个过程意味着一个节点的新特征是根据其本身和相邻节点的加权平均而构建的。

    要知道这个过平滑过程发生的位置,我们先讨论一下 GCN 何时会因过平滑而失效?我们将讨论三种过平滑的情况。第一种是使用线性激活时,隐变量 H_L 会收敛到一个特定的点。第二种是使用 ReLU 激活时,H_L 会收敛到一个特定的平面 M。第三种是使用 ReLU 加偏差时,H_L 会收敛到一个特定的子立方体 O(M, r) 的表面。

    在使用线性激活的情况下,H_L 为什么会收敛到一个特定的点呢?实际上,这与 L步随机游走有关。一个游走器从一个节点游走到其一个相邻节点的概率为「1/该节点的度」。经过 L步游走后,游走的路径会形成一个已访问节点的序列。用数学公式表示,随机游走的过程实际上就是一个归一化的矩阵的 L次幂乘以初始概率。

    然后,如果我们用一组在节点特征上的可学习参数替换这个初始概率,它就能转换成一个线性的 L层 GCN。

    可以看出,基于随机游走的一些结论也适用于线性 GCN,其中一项便是随机游走在经过无限多步之后会收敛到一个驻点。

    详细地说,我们首先需要进行特征值分解,即将归一化的邻接矩阵分解为 n 个特征值 λ 及其对应的特征向量 u。

    将这个求和展开,可得到下式:

    这个图谱中的特征值有一个性质。即,假设一个图 g 包含 m 个互相连接的分量,则归一化邻接矩阵的特征值便由 m 个为 1 的最大特征值构成,其余的 λ 则在 (-1,1) 的开区间中。

    因此,当 lL趋近无穷大时,最大的 m 项依然存在,因为其 λ 等于 1。但是,其余的项都将被忽略,因为这些 λ 的 l 次幂将趋近于零。这会使得隐变量 H_L 随网络深度增长而趋近于一个特定的点。

    另一方面,对于非线性的情况,H_L 将收敛到一个具有非线性激活 ReLU 的特定子空间 M。首先我们给出 M 子空间的定义:

    则随着层的深度增加,隐变量将越来越接近子空间 M。H_L+1 离该子空间的距离至少为:

    要注意,λ_m+1 是邻接矩阵中最大的非 1 特征值,s_l 则是模型参数 W_l 中最大的奇异值。

    接下来我们开始解析这个收敛公式。这个归一化邻接矩阵的收敛满足这一不等式。

    如果我们假设这个子空间的维度为 m,则 m 个最大的 λ 将位于该子空间,其余的则在 λ_m+1 的范围内。

    然后,模型参数 W_l 和 ReLU 的收敛分别满足下列两个不等式:

    有关这些不等式的更详细证明,请参阅 ICLR 2020 论文《Graph Neural Networks Exponentially Loss Expressive Power for Node Classification》。

    综合这些不等式,可得到隐变量的子空间距离沿层数变化的收敛性。可以看到,随着层数趋近于无穷大,子空间距离将趋近于 0,因此隐变量将会收敛到子空间 M。

    接下来是更一般的情况,使用 ReLU 加偏差的 GCN 又如何呢?H_L 将收敛到一个特定子立方体 O(M,r) 的表面上。首先,我们写出带偏差的 GCN 的公式:

    很显然,由于 b_l 到子空间的距离是一个常量,因此其收敛性就满足:

    可以看到,当 l 趋近无穷大时,不等式右侧部分就是一个无穷等比序列的和:

    因此,可以看到 H_L 将趋近于一个子立方体的表面,其与子空间 M 的距离为 r,而 r 就等于上式。

    总结一下,通过分析上面三种来自不同场景的情况,可以发现这三种情况之下存在一种普适的公式。我们可用以下不等式统一过平滑的情况:

    然后通过不同的 v 和 r 取值,我们可以得到不同的具体情况:

    详见论文:

    《Tackling Over-Smoothing for General Graph Convolutional Networks》(https://arxiv.org/pdf/2008.09864.pdf)。

    过拟合和训练动态变化

    接下来我们看看过拟合问题。过拟合是深度学习的一个常见问题,当数据点数量少而参数数量很多时,就会出现这种情况。此时模型会与训练数据完全拟合(本质上就是记住了数据),而在验证数据上表现很差。

    训练动态变化也是深度学习领域的一大常见问题。根据链式法则,当模型变深时,s_l-1 乘以 λ_m+1 的结果小于 1,会出现梯度消失问题。如果我们将 RGB 色彩作为以下的图的节点特征,可以看到当层数达到 500 时,这些特征的梯度降为了 0,节点都变成了黑色,即RGB=[0, 0, 0]。

    过拟合和训练动态变化是深度学习的常见问题,这里便不过多赘述了。下面我们看看在解决过平滑问题方面有什么研究进展。

    如何解决过平滑问题?

    首先,如何量化平滑?以 GCN 为例,我们先定义一个 ε-平滑,使得对于任意大于特定层 L 的 l,隐变量 H_l 的子空间距离将小于 ε:

    然后,将 ε-平滑层定义为能让 H_l 的子空间距离小于 ε 的最小层。但是,ε-平滑层是很难推导的。因此,我们取一个松弛化的 ε-平滑层作为上界。这个松弛化的 ε-平滑层的公式如下:

    用层量化了平滑之后,我们就可以想办法来缓解过平滑问题了。

    注意这里的 λ_m+1 与邻接矩阵相关,s_max 与模型权重相关,这也暗示了存在两个缓解过平滑问题的方向。

    第一,我们可以通过处理邻接矩阵来缓解过平滑,即增大 λ_m+1,进而使得松弛化的 ε-平滑层增大:

    那么我们如何做到这一点呢?很简单,在每 epoch 都丢弃一些边即可。研究证明,当丢弃一些边时,图上信息的传播速度会下降,子空间的维度会随连接的分量的增多而增加。丢弃边后的这两个现象都有助于缓解过平滑问题。

    更多详情和实验论证可见腾讯 AI Lab 的 ICLR 2020 论文《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》。

    第二,我们可以通过调整模型权重来缓解过平滑。为了增大 s_max,我们可以增大初始 W_ls 的值。下图展示了这种方法的效果。详见 ICLR 2020 论文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》。

    其它问题的解决方案

    ICLR 2020 上还有一篇论文《PairNorm: Tackling Oversmoothing in GNNs》提出了一种用于解决训练动态变化问题的方法。

    PairNorm 的思路对 GCN 输出进行居中和重新缩放或归一化,使得总的两两平方距离保持不变。如图所示,GCN 的输出点在图卷积之后通常会更接近彼此。但通过使用 PairNorm,新输出的两两距离能与输入的距离保持相似。

    另一种克服训练动态变化的方法是在结构中添加捷径。JKNet、IncepGCN 和 APPNP 等 GNN 能在深度结构中保持性能的方法就是如此。

    因为这三个模型全都包含通过聚合层到终点的捷径,因此浅的信息可以传播到最后的层,也因此这些模型实际上仍旧是「浅模型」。

    顺便一提,这些不同的 GNN 结构仍然满足过平滑的一般情况:

    详细的分析请参考论文:

    《Tackling Over-Smoothing for General Graph Convolutional Networks》(https://arxiv.org/pdf/2008.09864.pdf)。总结一下,在这些新的理论进展的帮助下,训练更深度 GNN 的问题已经得到了初步解答。

    3.大规模图神经网络

    真实世界的图可能具有非常大的规模,因此让 GNN 有能力处理大规模图是非常重要的研究课题。

    基本的 GNN 通常无法处理大规模图,因为其通常无法满足巨大的内存需求,而且梯度更新的效率也很低。

    为了让 GNN 有能力处理大规模图,研究者已经提出了三种不同的采样范式:基于节点的采样、基于层的采样和基于子图的采样。

    其中,逐节点采样是根据目标节点执行采样,而逐层采样是基于卷积层来执行采样,逐图采样则是从原图采样子图,然后使用子图进行模型推理。

    根据这三种范式,可以知道为了实现大规模 GNN,我们需要解决两个问题:如何设计高效的采样算法?如何保证采样质量?

    近些年在构建大规模 GNN 方面已经出现了一些成果,下图给出了这些成果的时间线:

    接下来我们将按这一时间线简要介绍这些研究成果。

    首先来看 GraphSAGE,其可被视为原始 GCN 的一种扩展:在 GCN 的平均聚合器的基础上增加了许多广义上的聚合器,包括池化聚合器和 LSTM 聚合器。不同的聚合器也会对模型产生不同的影响。此外,在聚合之后,不同于 GCN 使用的求和函数,GraphSAGE 使用了连接函数来结合目标节点机器邻近节点的信息。这两大改进是基于对 GCN 的空间理解得到的。

    为了实现大规模 GNN,GraphSAGE 首先采用了 mini-batch 的训练方法,这样可以降低训练期间的通信成本。在每次迭代中,仅会考虑用于计算表征的节点。但是,mini-batch 训练可能出现邻近节点扩张的问题,使得 mini-batch 在层数较多时需要采用图的大部分乃至全部节点!

    为了解决这一问题并进一步提升性能,GraphSAGE 采用了固定采样个数的的邻近采样方法,即每层都采样固定大小的邻近节点集合。

    从上右图可以看到,采用固定采样个数的采样方法后,采样节点的数量降低了。当图的规模很大时,这一差距会更加显著。不过,GraphSAGE 在网络层数较大时依然无法避免邻近节点扩张问题,采样质量上也无法得到保证。

    为了进一步降低采样规模和得到一些理论上的质量保证,VR-GCN 整合了基于控制变量的估计器(CV 采样器)。其可以维持历史隐藏嵌入(historical hidden embedding)来获得更好的估计,这个历史隐藏嵌入可用于降低方差,进而消除方差,实现更小的采样规模。VR-GCN 的数学形式如下:

    不过,VR-GCN 也有一个缺点:需要额外的内存来存储所有的历史隐藏嵌入,这使得我们难以实现大规模扩展。

    上面我们可以看到,基于节点的采样方法并不能彻底解决邻近节点扩张问题。接下来看基于层的采样方法。

    FastGCN 提出从Functional generalization的角度来理解 GCN,并为 GCN 给出了基于层的估计形式:

    基于此,我们可以在每层都采样固定数量的节点。更进一步,FastGCN 还提出了基于重要度的采样模式,从而降低方差。在采样过程中,每一层的采样都是相互独立的,而且每一层的节点采样概率也保持一致。下图是 GCN 与 FastGCN 的对比:

    可以看出,FastGCN 的计算成本显著更低,而且研究表明,这种采样模式从期望上并不会丢失太多信息,因为其在执行重要度采样时会进行随机化处理,通过足够多epoch的训练,每个节点和链接都有期望被采样。

    可以看出,基于层采样的FastGCN 彻底解决了邻近节点扩张问题,而且采样方法有质量保证。但是该方法的缺点是无法获得层之间的相关性,模型的表现也可能受到负面影响。

    为了更好地获得层之间的相关性,ASGCN 提出了自适应层式采样方法,即根据高层采样结果动态调整更低层的采样概率。如下左图所示,在对底层采样的时候ASGCN会考虑采样高层采样的邻居节点,使得层之间的相关性得到很好的保留。如下右图所示,整个采样过程是自上而下的。我们首先采样输出层的目标节点,然后根据其采样结果采样中间层的节点,然后重复这个过程直到输入层。在采样过程中,每层采样节点的数目也会保持一个固定值。

    另外,为了降低采样方差,ASGCN 还引入了显式方差下降法(explicit variance reduction),以优化损失函数中的采样方差。

    总体来说,ASGCN 能获得更好的性能,方差控制也更好,但由于采样过程有额外的层间依赖关系需要考虑,采样效率会受到一些影响。

    接下来出现了基于子图的采样方法。ClusterGCN 首先使用图分割算法将图分解为更小的聚子图,然后在子图层面上组成随机的分批,再将其输入 GNN 模型,从而降单次计算需求。

    通过限制子图的大小,这种方法也可以有效避免邻近节点扩张问题,因为在每一层中,采样的范围都不会超过聚类子图。

    不过,ClusterGCN 的论文并没有对这种方法的采样质量进行实证研究。

    GraphSAINT 则并未在采样过程中使用聚类算法(这会引入额外的偏差和噪声),而是直接通过子图采样器来采样用于mini-batch 训练的子图。其给出了三种采样器的构建方式,分别为基于节点的采样、基于边的采样和随机游走采样,如下所示:

    GraphSAINT 还从理论上分析了控制采样器的偏差和方差的方法,其中包括用于消除采样偏差的损失归一化和聚合归一化方法:

    另外,该论文还提出通过调整边采样概率来降低采样方差。作为当前最佳的方法,GraphSAINT 的表现也在实验中得到了证明。具体详情请浏览 ICLR 2020 论文《GraphSAINT: Graph Sampling Based Inductive Learning Method》。

    很显然,大规模图神经网络方面还有很大的进一步研究空间,比如更高效的采样技术、适用于异构图或动态图的架构等等。

    4.图神经网络的自监督/无监督学习

    前面讨论的 GNN 的表达能力、深度和规模都是基于监督式方法,也就是说我们有输入图的标签。但在现实生活中,获取这些标签却并非易事。比如在分子属性预测任务中,为了获取基本真值标签,我们必需专业人士的协助。此外,训练任务与测试任务并不总是一致的,比如对于社交网络推荐任务,我们可能在训练中使用的是节点用户购买商品的数据,但我们却想知道节点用户是否想看某部电影,此时训练标签可能对测试就毫无作用了。因此,我们需要研究如何在没有标签的情况下训练 GNN。

    目前在自监督图学习方面已经有一些研究成果了。我们可以根据它们的机制将其分为两大类别:预测方法和基于信息论的方法。而根据所要解决的任务的差异,又可以分为两种情况:节点分类和图分类。

    预测方法

    首先来看预测方法。Yann LeCun 说过:「自监督学习的系统是根据其输入的某些部分来预测输入的其它部分。」这就意味着在自监督学习中,输入的结构是很重要的。而图就是高度结构化的,因此天生就很适合自监督学习。

    对于节点分类任务,实现自监督学习的方法通常有两种。一是强制使用相邻节点之间的相似性,二是基于邻近节点执行每个节点的重建。

    首先,我们来看第一种方法,这种方法由 GraphSAGE 引入,其基本思想是强制每个节点与其邻近节点有相似的表征。在这种情况下,设 h_u 为 h_v 的邻近节点,则我们的目标是最大化它们的内积。我们称这些邻近节点为正例样本。然后,我们最小化 h_v 与通过负采样得到的其它节点之间的相似性,这些节点通常是从整个图均匀采样的。这样,我们就可以使用反向传播来训练 GNN 的参数了。

    至于第二种方法,来自 Durán & Niepert 提出的 EP-B,其首先会计算邻近节点的表征的聚合。目标是最小化重建的结果与真实表征之间的距离。与此同时,又最大化这个聚合表征与其它节点的表征之间的距离。

    EP-B 和 GraphSAGE 的主要区别是 EP-B 强制使用了邻近节点和每个其它节点的聚合之间的相似性,而 GraphSAGE 则直接强制使用了邻近节点与每个节点的相似性。

    在图分类方面又有哪些方法呢?

    我们要介绍的第一种方法是 N-Gram Graph。该方法分为两个阶段:节点表征阶段和图表征阶段。节点表征阶段使用了一种传统的自监督式节点嵌入方法 CBoW 来学习节点表征。在第二个阶段,由于已有节点表征,则首先会为每条长度为 n 的路径计算表征,称为 n-gram 路径。这个路径表征是以该路径中每个节点的表征的积形式得到的。因此,它们将历经图中所有的 n-gram 路径并归总所有路径的表征。最终的图表征是通过将 1-gram 到 T-gram 的路径连接起来而得到的。

    事实上,这样的计算就等于没有训练的 GNN。N-Gram Graph 的训练无需任何监督。

    另一种用于图分类的方法是 PreGNN,它同样分为两个阶段:第一个阶段是执行节点表征(但使用了两种全新方法),第二阶段是使用简单的读出基于所有节点获取图层面的表征。但它是通过一种监督式策略交叉熵来训练图层面的表征。该研究指出,节点层面和图层面的训练对最终性能而言都很重要。

    因为其第二个阶段很普通,所以我们只解读一下第一个阶段。

    在这一阶段,PreGNN 提出了两种损失函数。周围结构预测(context prediction)是强制节点表征与其周围结构相似。另外我们还执行负采样来最小化 h_v 与其它节点的周围结构之间的相似性。这个方法的思路很简单:每个节点周围的结构定义了该节点的局部拓扑结构。

    另一个损失则是属性掩码(attribute masking)。这个损失的设计灵感来自强大的 NLP 模型 BERT。简单来说,就是随机地使用掩码替换节点,然后构建训练损失函数来预测输入。方法很简单,但效果很好。

    另一种值得一提的方法是 GCC。该方法使用了对比学习(contrastive learning)来执行图层面的无监督学习。不过 GCC 的一大主要问题是没有节点层面的训练。

    总结一下,在图分类任务上,N-Gram Graph 和 PreGNN 都使用了节点层面的自监督,而 GCC 使用了图层面的自监督。那么,我们自然会问:能不能同时使用节点层面和图层面的自监督?

    答案当然是肯定的。这就要谈到腾讯 AI Lab 研究团队提出的 GROVER 了。

    GROVER 同样分为两个阶段。在节点阶段,我们还同时考虑了边,但为了说明简单,这里仅讨论节点表征过程。在这一阶段,首先为每个节点提取一个词典池。我们称之为 key。然后我们像 BERT 一样为每个节点加掩码,然后预测每个节点周围的局部结构。如果局部结构与词典中的一个 key 匹配,则在该维度上输出 1,否则便输出 0。注意这是一个多标签分类问题,因为每个节点的局部结构通常有多个。这样,我们仅需要一类掩码就能做到 PreGNN 的两件事。

    然后在图阶段,预测是相似的。我们也首先提取 graph motif,其由典型的官能团(比如苯环)构成。然后我们使用 GNN 获取每个图的输出。使用该输出,我们将预测这个图是否包含这些 graph motif。注意这也是一个多标签分类问题。

    除此之外,腾讯 AI Lab 还在该研究中提出了一种类似 Transformer 的强大 GNN 模型:GTransformer。其首先会使用一种新提出的名为 dyMPN 的 动态扩展范围MPNN 来获取每个输入图的 key、查询和值,然后会像 Transformer 一样获取最终输出结果。实验结果证明了这一模式的强大能力。

    以上这些就是 GROVER 的关键组件。更进一步的,我们还实现了一个分布式的图训练框架,最终成功在1000 万个无标注分子数据上预训练带有 1 亿个参数的大模型。

    使用这个预训练的模型,我们可以针对下游任务进行微调。在此基础上,GROVER 可以取得显著优于 MPNN 和 DMPNN 等传统方法的表现,同时也优于 N-Gram 和 PreGNN 等自监督方法。

    基于信息的方法

    介绍了预测方法,我们再来看基于信息的方法。

    优良的表征应该能将输入中的大量信息保存下来。受此启发,Vincent et al. 在 2010 年提出使用自动编码器来进行表征学习,这意味着隐藏表征应该可以解码到与其输入一样。

    但自动编码器资源消耗高,既需要编码,也需要解码,而在图领域,如何解码图仍还是一个有待解决的问题。那么还有其它可以直接衡量表征与输入之间的信息的方法吗?有的,那就是互信息(mutual information)。

    给定两个随机变量,互信息的定义是它们的边界属性和关节属性的积之间的 KL 散度,这又可以进一步推导为熵减去条件熵。

    互信息为什么可以计算信息关系?我们可以这样看,如果 X 和 Y 互相独立,且 p(X)p(Y)=p(X,Y),则互信息等于 0,这表明 X 和 Y 不相关。这是合理的,因为 X 和 Y 互相独立。如果条件熵为 0,则 X 和 Y 确定是相关的,则互信息输出为最大值。

    Hjelm et al. 2019 证明执行自动编码是计算互信息的重建误差的一个下限。

    计算互信息是很困难的,近些年方才出现一些可行的方法。这里有三种典型的方法(MINE、JSD MI 和 infoNCE MI),其基本思想是学习一个神经网络来最大化互信息的一个替代函数。详情请参阅各论文。

    回到图,我们能否使用互信息来实现图的自监督学习?DGI 是这方面首个研究成果,其目标设定为最大化输入的节点特征 X 和邻接矩阵 A 与输出表征 h_i 之间的互信息。DGI 使用了 JSD 估计器,其中包含正例项和负例项。

    但直接计算互信息的难度不小,我们可能需要另一个 GNN 作为互信息的替代。DGI 使用了表征的读出 s 来替代输入。如下图所示,原图有两个输入,其中错误的图是负例,然后我们用同样的 GNN 得到它们的输出,之后再执行读出函数得到 s。s 可以替代原目标中的 X,A,得到替代目标函数。

    DGI 证明这种操作不会导致信息损失,其还证明这种替换方式实际上就等同于真正的互信息。

    不过 DGI 仍还有一些问题。第一是它需要读出函数来计算互信息,而且这个读出函数需要是单射式的,这并不容易保证。另外它还需要构建错误的图来得到负例,因此效率不高。而在实验中,DGI 需要为不同的任务使用不同的编码器,这并不实用。

    针对这些问题,清华大学、西安交通大学与腾讯 AI Lab合作提出了 GMI,其基本思想是不使用读出函数和错误样本,而是直接计算互信息。

    在 GMI 中,首先分两部分定义互信息。一是特征互信息,仅度量节点特征和表征之间的信息关系。二是拓扑互信息,这是预测的边和原始邻接矩阵之间的互信息。

    很显然,这一方法能同时考虑到边和特征,而无需读出函数或错误样本。更重要的是,特征互信息还能进一步分解。

    我们证明:特征互信息可以分解为局部互信息的加权和。而每个局部互信息计算的是每个节点及其表征之间的互信息。权重取决于不同的情况,将它们设置为与预测的边一样也不错。然后我们可以使用 JSD 互信息估计器来计算特征互信息和边互信息。

    在节点分类任务上的实验结果证明 GMI 有更优的表现,相关的代码也已经发布:https://github.com/zpeng27/GMI

    至于用于图分类的基于信息的方法,可参看 ICLR 2020 论文《InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization》,这里不再过多赘述。

    三、图神经网络的应用进展

    图神经网络作为一种有效的深度学习工具,已经在分子属性预测、生物学分析、金融等许多领域得到了应用。这里以腾讯 AI Lab 实现的在社交网络和医疗影像领域的应用为例,介绍图神经网络的应用进展。

    1.用于社交网络的 GNN

    首先来看一篇 WWW 2019 论文《Semi-supervised graph classification: A hierarchical graph perspective》,其中腾讯 AI Lab 提出了使用分层图实现半监督图分类的方法。

    分层图是指一组通过边互相连接在一起的图实例,如图所示:

    在许多现实应用中,很多数据都可以建模成分层图的形式,比如具有分组结构的社交网络和文档集合(比如具有引用关系的graph-of-words)。如上所示,假设我们有一个「用户-分组」分层图,我们知道其中部分标签,我们可以怎样预测其它组的标签?

    如果仅考虑组之间的联系,那么这个问题就又回到了节点分类。但是,可以看到每一组都有自己的用户图,忽略这样的信息并不合适。为了在用户和分组层面上利用图信息,我们面临着这样的难题:如何将任意大小的图表征为固定长度的向量?如何整合实例层面和分层层面的信息?

    首先来看第一个问题。图表征与节点表征在不同的层面上;在节点层面上图 G 会被投射到大小为 n×v 的隐藏空间中;而在图层面上图 G 会被投射成大小为 v 的隐藏向量。因此,为了将节点层面的空间转换成图层面的向量,这里引入了自注意力图嵌入(SGAE)

    首先,将单个图通过一个两层 GCN,得到节点层面的表征 H,其大小为 n×v,然后根据上图中的 S 计算自注意力。在经过一个 softmax 函数之后,会得到一个具有 r 个头的多头自注意分数,其大小为 r×n。然后,如果我们将这些分数应用到节点层面的表征,我们就会得到大小固定为 r×v 的矩阵。SAGE 有三大优势:1)其大小因自注意力而保持不变,2)因为 GCN 平滑而具有排列不变性,3)因为自注意力而能使用节点重要度。

    对于第二个问题:如何整合实例层面和分层层面的信息?这里实例层面是基于 SAGE 的图层面学习,分层层面模型是节点层面的学习。我们使用了特征共享来连接 SAGE 的输出和 GCN 的输入。然后又引入一种新的分歧损失(disagreement loss)来最小化实例分类器和分层分类器之间的不一致情况。

    另外,我们还使用了主动学习来解决样本数量少的问题。我们使用了分歧损失来为外部标注选择实例。有关这两种算法 SEAL-AI 和 SEAL-CI 的详情以及相关实验结果请查阅论文。

    接下来看腾讯 AI Lab 另一项被 AAAI 2020 接收的研究《Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks》,提出了一种通过双向图卷积网络实现社交网络谣言检测的新思路。

    谣言可算是当今社会面临的一大顽疾。这篇论文提出通过关注和转发关系来检测社交媒体上的谣言。不管是谣言还是新闻,它们的传播模式都是树结构的。但通常来说,谣言的传播有两个属性。第一如下图 b 所示,其会沿一条关系链进行很深的传播。第二如图 c,谣言在社交媒体上传播时散布很宽。举个例子,一个 Twitter 用户可能有大量关注者。

    为了同时获取谣言传播的这两种属性,我们设计了一种基于 GCN 的新模型。这个用于谣言检测的双向 GCN 包含 4 个组件:1)两个不同的有向图,用于描述谣言的传播和扩散度;2)使用二层 GCN 来计算高层面的节点表征;GCN 不仅能学习特征信息,还能学习谣言的传播拓扑结构;3)经过观察,根节点通常就已经包含了谣言或新闻的主要内容,而关注者通常只是不带任何内容进行转发,因此通过将根特征连接到树中的每个节点,可以增强每层的隐藏特征;4)分别根据节点表征对传播和扩散度的两个表征进行池化处理。这两个表征再被聚合到一起得到最终结果。

    我们在 Twitter15、Twitter16、Weibo 三个常用基准上的实验研究对这一方法的效果进行验证,结果表明新方法具有显著更优的表现。

    此外,我们还评估了谣言的早期侦测,此时仅给出谣言树上非常有限的节点并且还设置了一个侦测截止时间,结果表明基于图的方法非常适用于早期发现谣言。

    2.用于医疗影像的 GNN

    医疗影像也是 GNN 的一个重要应用场景,腾讯 AI Lab 近两年在这一领域取得了一些重要的研究成果。首先来看腾讯 AI Lab 的 MICCAI 2018 论文《Graph CNN for Survival Analysis on Whole Slide Pathological Images》,其中提出使用图卷积网络基于全切片病理图像进行生存分析。

    生存分析的目标是预测特定事件发生的风险,这类事件包括器官衰竭、药物不良反应和死亡。有效的分析结果具有重要的临床应用价值。但实际操作时却面临着许多困难。

    首先,全切片病理图像(WSI)分析是一个需要大量计算的过程,因为单张 WSI 的数据量就超过 0.5 GB,而且其中包含数百万个细胞,还涉及局部特征和全局特征,因此非常复杂。另外,如何将 WSI 的拓扑特征用于生存分析也还是一个有待解决的问题。

    为此,我们提出将 WSI 建模成图,然后开发了一种图卷积神经网络(Graph CNN),其使用了注意力机制,可通过提供 WSI 的最优图表征来实现更好的生存分析。

    实验结果表明,这种新方法优于之前的其它方法。

    这一部分同时也介绍了近年来GNN在医疗图像上的其他工作:在IPMI2019发表的《Graph Convolutional Nets for Tool Presence Detection in Surgical Videos》中,作者提出使用 GCN 来检测手术视频中的工具,这是自动手术视频内容分析的核心问题之一,可用于手术器材使用评估和手术报告自动生成等应用。这个模型使用了 GCN 沿时间维度通过考虑连续视频帧之间的关系来学习更好的特征。

    而在MICCAI 2020发表的论文《Graph Attention Multi-instance Learning for Accurate Colorectal Cancer Staging》中,作者提出使用图注意力多实例学习来准确判断结直肠癌是处于早期、中期还是晚期。

    总结和展望

    在这次课程中,我们介绍了图神经网络的发展历史、包括图神经网络的表达能力、深度、大规模扩展、自监督/无监督学习等方面的研究进展,也简要介绍了腾讯 AI Lab 在图神经网络的社交网络和医疗影像应用方面的一些初步成果。

    图深度学习领域仍处于发展之中,有很多有趣的问题等待解决,例如逆向图识别(IGI),即我们在图分类问题中,是否可以根据图的标签来推断每个节点的标签?子图识别,即如何在图中找到关键的子图同时还有图与多示例学习问题的结合形成多图示例学习问题,以及在图上进行攻击与防御相关的图深度学习鲁棒性的研究。最后,层次图也是一个热门的研究方向。图神经网络必将在人工智能领域未来的研究和应用中扮演更重要的角色。

    展开全文
  • No.20智源社区强化学习组强化学习研究观点资源活动关于周刊强化学习作为人工智能领域研究热点之一,其研究进展与成果也引发了众多关注。并且诸多研究成果发表于CVPR-2021&20...
  • No.23智源社区强化学习组强化学习研究观点资源活动关于周刊强化学习作为人工智能领域研究热点之一,其研究进展与成果也引发了众多关注。并且诸多研究成果发表于NeurIPS 2021学术会议...
  • No.03智源社区强化学习组RL学习研究观点资源活动关于周刊深度强化学习是当前人工智能领域研究的热点之一,为帮助研究工程人员了解该领域的进展和资讯,智源社区整理了第3期《强化学习周刊》...
  • 首先许多地方写的过于晦涩,不适合初学者,第二也尚未与时俱进地容纳许多近年鲁棒优化领域的重要工作,尤其在分布式鲁棒优化(distributionally robust optimization)和动态优化方面(adaptive optimization/robust...
  • No.18智源社区强化学习组强化学习研究观点资源活动关于周刊强化学习作为人工智能领域研究热点之一,其研究进展与成果也引发了众多关注。并且诸多研究成果发表于ICML-2021学术会议中,为...
  • 群体智能动态优化算法及其应用综述[A survey of swarm ...动态优化2.1动态优化问题2.2离散空间连续空间2.3应用2.4测试2.5基准生成器三.群体智能算法3.1简要说明3.1.1 蚁群优化(ACO)3.1.2粒子群优化(PSO...
  • 最近,一些读者向我们询问在数据科学方面最好的编程...我们最近观看了一个出色的视频,围绕着这两种语言的近期进展,正好可以解决这个问题。该视频来自Domino数据实验室的首席数据科学家——Eduardo Ariño de la Ru...
  • 本文将分图图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程Theme II: Advances and Applications部分的核心内容,Theme I以及更多详细的内容可参看课程幻灯片及相关论文:...
  • No.42智源社区强化学习组强化学习研究观点资源活动周刊订阅告诉大家一个好消息,《强化学习周刊》已经开启“订阅功能”,以后我们会向您自动推送最新版的《强化学习周刊》。订阅方法:方式1:扫描下面二维码,进入...
  • 本文中,我们研究了SLAM最新进展,从SLAM形成的事实标准开始讲解,回顾了相关工作,这涵盖了一系列广泛的主题,包含长时间建图过程中的鲁棒性和尺度问题,建图过程中的特征和语义表示,理论上的性能保证,主动SLAM和...
  • No.09智源社区强化学习组强化学习研究观点资源活动关于周刊强化学习作为人工智能领域研究热点之一,它在决策智能领域中的应用研究进展与成果也引发了众多关注。为帮助研究工程人员了解该领域的...
  • 本文转载自公众号:智源社区助手。作为大数据时代重要的知识表示方式,知识图谱是人工智能领域构建和应用知识的新阶段,它能够更好地实现大规模数据的认知推理。同时,知识图谱和深度学习相互协作,是...
  • 综述:物联网的联邦学习

    千次阅读 2022-04-12 12:10:00
    联邦学习(FL)已经成为一种分布式协同人工智能方法,通过允许在分布式物联网设备上进行人工智能训练而不需要数据共享,它可以使许多智能物联网应用成为可能。 传统上,人工智能功能被放置在云服务器或数据中心,用于...
  • SLAM:现在,未来和鲁棒感知时代

    千次阅读 2019-05-16 21:20:15
    首先,我们发现过去十年中,视觉-惯性里程计代表了SLAM研究的最新进展。从某种意义上说,视觉-惯性导航(VIN, visual-inertial navigation)就是SLAM:VIN可以看作回环闭合(或场景识别)模块被关闭的SLAM系统。如果...
  • 第四章 防御理念技术新进展 4.1 网络防御技术新进展 传统防御技术只能防范已知的攻击 新型防御是:基于动态性、冗余性、异构性等基础防御手段构造具有“测不准”效应的运行环境,改变系统的静态性、确定...
  • 【Active Learning - 09】主动学习策略研究及其在图像分类中的应用:研究背景研究意义: https://blog.csdn.net/Houchaoqun_XMU/article/details/100177750 【Active Learning - 10】图像分类技术和主动学习...
  •  港中文李弘扬 :物体检测最新进展 第四期 语音技术专场 1. 中科院陶建华:语音技术现状未来 2. 清华大学吴及:音频信号的深度学习处理方法 3. 小米王育军:小爱背后的小米语音技术 4. 百度康永国:AI 时代的...
  • 2020年 第43篇 【Top Talk/大咖说】由美团技术学院和科研合作部主办,面向全体技术同学,定期邀请美团资深技术专家、业界大咖、高校学者及畅销书作者,为大家分享最佳实践、互联网热门话题、学术界前沿技术进展等...
  • 整整一个十年过去了,带大家解读《神经信息处理系统进展大会》历年最佳论文,了解并探究神经信息处理系统的重要进展。 了解过去,读懂现在,把握未来! 目录 NIPS(神经信息处理系统进展大...
  • 随着无人系统技术的不断发展,多无人系统之间的跨域协同凭借其诸多优势成为当前无人系统领域研究和应用的热点。首先,阐述了无人系统跨域协同的概念形成发展历程,并对未来发展趋势进行了展望;其次,...
  • 第9章知识融合更新方法 9.1 概述 随着互联网、物联网、云计算等技术的迅猛发展,网络在改变人们生活方式的同时,也产生了巨大的网络数据资源。这些网络数据资源具有以下特点。 网络数据来源多样:如在线百科、...
  • 对这3个基本特性的研究决定着网络大数据的发展趋势、研究进展应用前景。 1.3.1 网络大数据的复杂性 复杂性造成网络大数据存储、分析、挖掘等多个环节的困难。网络大数据的复杂性主要包括数据类型的复杂性、数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,403
精华内容 561
关键字:

分布式鲁棒优化:最新进展与应用