图神经网络(Graph Neural Networks,GNN)综述

2019 年 11 月 27 日 极市平台
图神经网络(Graph Neural Networks,GNN)综述

加入极市专业CV交流群,与6000+来自腾讯,华为,百度,北大,清华,中科院等名企名校视觉开发者互动交流!更有机会与李开复老师等大牛群内互动!

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流。关注 极市平台 公众号 ,回复 加群,立刻申请入群~


作者:苏一

来源:https://zhuanlan.zhihu.com/p/75307407

本文已经作者授权,转载请联系原作者


本篇文章是对论文“Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph Neural Networks[J]. 2019.”的翻译与笔记

  • 论文 链接:https://arxiv.org/abs/1901.00596


目录

一、什么是图神经网络

二、有哪些图神经网络

三、图神经网络的应用



一、什么是图神经网络?


在过去的几年中,神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务,如目标检测、机器翻译和语音识别,曾经严重依赖手工的特征工程来提取信息特征集,最近被各种端到端的深度学习范式(例如卷积神经网络(CNN)、长短期记忆(LSTM)和自动编码器)彻底改变了。在许多领域中,深度学习的成功部分归因于快速发展的计算资源(如GPU)和大量训练数据的可用性,部分归因于深度学习从欧氏空间数据中提取潜在表示的有效性。


尽管深度学习在欧氏空间中的数据方面取得了巨大的成功,但在许多实际的应用场景中的数据是从非欧式空间生成的,同样需要进行有效的分析。例如,在电子商务中,一个基于图的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐。图数据的复杂性对现有的机器学习算法提出了重大挑战,这是因为图数据是不规则的。每个图都有一个大小可变的无序节点,图中的每个节点都有不同数量的相邻节点,导致一些重要的操作(例如卷积)在图像上很容易计算,但不再适合直接用于图域。此外,现有机器学习算法的一个核心假设是实例彼此独立。然而,对于图数据来说,情况并非如此,图中的每个实例(节点)通过一些复杂的链接信息与其他实例(邻居)相关,这些信息可用于捕获实例之间的相互依赖关系。


近年来,人们对深度学习方法在图数据上的扩展越来越感兴趣。在深度学习的成功推动下,研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想,定义和设计了用于处理图数据的神经网络结构,由此一个新的研究热点——“图神经网络(Graph Neural Networks,GNN)”应运而生,本篇文章主要对图神经网络的研究现状进行简单的概述。


需要注意的是,图神经网络的研究与图嵌入(对图嵌入不了解的读者可以参考我的这篇文章《图嵌入综述》)或网络嵌入密切相关,图嵌入或网络嵌入是数据挖掘和机器学习界日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息,将图中顶点表示为低维向量空间,以便使用简单的机器学习算法(例如,支持向量机分类)进行处理。许多图嵌入算法通常是无监督的算法,它们可以大致可以划分为三个类别,即矩阵分解、随机游走和深度学习方法。同时图嵌入的深度学习方法也属于图神经网络,包括基于图自动编码器的算法(如DNGR和SDNE)和无监督训练的图卷积神经网络(如GraphSage)。下图描述了图嵌入和图神经网络在本文中的区别。

  • 《图嵌入综述》链接:

    https://zhuanlan.zhihu.com/p/62629465




二、有哪些图神经网络?


在本文中,我们将图神经网络划分为五大类别,分别是:图卷积网络(Graph Convolution Networks,GCN)、 图注意力网络(Graph Attention Networks)、图自编码器( Graph Autoencoders)、图生成网络( Graph Generative Networks) 和图时空网络(Graph Spatial-temporal Networks)。


符号定义



1、图卷积网络(Graph Convolution Networks,GCN)


图卷积网络将卷积运算从传统数据(例如图像)推广到图数据。其核心思想是学习一个函数映射 ,通过该映射图中的节点 可以聚合它自己的特征 与它的邻居特征 )来生成节点  的新表示。图卷积网络是许多复杂图神经网络模型的基础,包括基于自动编码器的模型、生成模型和时空网络等。下图直观地展示了图神经网络学习节点表示的步骤。



GCN方法又可以分为两大类,基于频谱(spectral-based)和基于空间(spatial-based)。基于频谱的方法从图信号处理的角度引入滤波器来定义图卷积,其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法将图卷积表示为从邻域聚合特征信息,当图卷积网络的算法在节点层次运行时,图池化模块可以与图卷积层交错,将图粗化为高级子结构。如下图所示,这种架构设计可用于提取图的各级表示和执行图分类任务。



在下面,我们分别简单介绍了基于频谱的GCN和基于空间的GCN。


1.1 Spectral-based Graph Convolutional Networks


在大学里学过《数字信号处理》这门课程的朋友应该会记得,在这门课上我们通过引入傅里叶变换将时域信号转换到频域进行分析,进而我们完成一些我们在时域上无法完成的操作,基于频谱的图卷积网络的核心思想正是来源于此。


在基于频谱的图神经网络中,图被假定为无向图,无向图的一种鲁棒数学表示是正则化图拉普拉斯矩阵,即



其中,A为图的邻接矩阵,D为对角矩阵且



正则化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质,正则化拉普拉斯矩阵可以分解为



,其中



U是由L的特征向量构成的矩阵,是对角矩阵,对角线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基。


在图信号处理过程中,一个图的信号



是一个由图的各个节点组成的特征向量, 代表第i个节点。


对图X的傅里叶变换由此被定义为



傅里叶反变换则为



其中为傅里叶变换后的结果。


为了更好地理解图的傅里叶变换,从它的定义我们可以看出,它确实将输入图信号投影到正交空间,在正交空间中,基由正则化图拉普拉斯的特征向量构成。


转换后得到的信号 的元素是新空间中图信号的坐标,因此原来的输入信号可以表示为



正是傅里叶反变换的结果。


现在我们可以来定义对输入信号X的图卷积操作了



其中, 是我们定义的滤波器; 表示Hadamard product。


假如我们定义这样一个滤波器



那么我们的图卷积操作可以简化表示为



基于频谱的图卷积网络都遵循这样的模式,它们之间关键的不同点在于选择的滤波器不同。


现有的基于频谱的图卷积网络模型有以下这些:Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)


基于频谱的图卷积神经网络方法的一个常见缺点是,它们需要将整个图加载到内存中以执行图卷积,这在处理大型图时是不高效的。


1.2 Spatial-based Graph Convolutional Networks


模拟传统卷积神经网络对图像的卷积运算,基于空间的方法基于节点的空间关系定义图卷积。为了将图像与图关联起来,可以将图像视为图的特殊形式,每个像素代表一个节点,如下图a所示,每个像素直接连接到其附近的像素。通过一个3×3的窗口,每个节点的邻域是其周围的8个像素。这八个像素的位置表示一个节点的邻居的顺序。然后,通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均,对该3×3窗口应用一个滤波器。由于相邻节点的特定顺序,可以在不同的位置共享可训练权重。同样,对于一般的图,基于空间的图卷积将中心节点表示和相邻节点表示进行聚合,以获得该节点的新表示,如图b所示。



一种共同的实践是将多个图卷积层叠加在一起。根据卷积层叠的不同方法,基于空间的GCN可以进一步分为两类:recurrent-based和composition-based的空间GCN。recurrent-based的方法使用相同的图卷积层来更新隐藏表示,composition-based的方法使用不同的图卷积层来更新隐藏表示。下图说明了这种差异。



1.3 Comparison Between Spectral and Spatial Models


作为最早的图卷积网络,基于频谱的模型在许多与图相关的分析任务中取得了令人印象深刻的结果。这些模型在图信号处理方面有一定的理论基础。通过设计新的图信号滤波器,我们可以从理论上设计新的图卷积网络。然而,基于频谱的模型有几个缺点。我们从效率、通用性和灵活性三个方面来说明这一点。


在效率方面,基于频谱的模型的计算成本随着图的大小而急剧增加,因为它们要么需要执行特征向量计算,要么同时处理整个图,这使得它们很难适用于大型图。基于空间的模型有潜力处理大型图,因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行,而不是在整个图中执行。当相邻节点数量增加时,可以引入采样技术来提高效率。


在一般性方面,基于频谱的模型假定一个固定的图,使得它们很难在图中添加新的节点。另一方面,基于空间的模型在每个节点本地执行图卷积,可以轻松地在不同的位置和结构之间共享权重。


在灵活性方面,基于频谱的模型仅限于在无向图上工作,有向图上的拉普拉斯矩阵没有明确的定义,因此将基于频谱的模型应用于有向图的唯一方法是将有向图转换为无向图。基于空间的模型更灵活地处理多源输入,这些输入可以合并到聚合函数中。因此,近年来空间模型越来越受到关注。


2、图注意力网络(Graph Attention Networks)


注意力机制如今已经被广泛地应用到了基于序列的任务中,它的优点是能够放大数据中最重要的部分的影响。这个特性已经被证明对许多任务有用,例如机器翻译和自然语言理解。如今融入注意力机制的模型数量正在持续增加,图神经网络也受益于此,它在聚合过程中使用注意力,整合多个模型的输出,并生成面向重要目标的随机行走。在本节中,我们将讨论注意力机制如何在图结构数据中使用。


2.1 Graph Attention Network (GAT)


图注意力网络(GAT)是一种基于空间的图卷积网络,它的注意机制是在聚合特征信息时,将注意机制用于确定节点邻域的权重。GAT的图卷积运算定义为:



其中α(·)是一个注意力函数,它自适应地控制相邻节点j对节点i的贡献。为了学习不同子空间中的注意力权重,GAT还可以使用多注意力:



2.2 Gated Attention Network (GAAN)


门控注意力网络(GAAN)还采用了多头注意力机制来更新节点的隐藏状态。然而,GAAN并没有给每个head部分配相等的权重,而是引入了一种自注意机制,该机制为每个head计算不同的权重。更新规则定义为,



其中  和  是反馈神经网络,而 是第k个注意力head的注意力权重


2.3 Graph Attention Model (GAM)


图形注意力模型(GAM)提供了一个循环神经网络模型,以解决图形分类问题,通过自适应地访问一个重要节点的序列来处理图的信息。GAM模型被定义为




其中 是一个LSTM网络,fs是一个step network,它会优先访问当前节点 优先级高的邻居并将它们的信息进行聚合。



除了在聚集特征信息时将注意力权重分配给不同的邻居节点,还可以根据注意力权重将多个模型集合起来,以及使用注意力权重引导随机行走。尽管GAT和GAAN在图注意网络的框架下进行了分类,但它们也可以同时被视为基于空间的图形卷积网络。GAT和GAAN的优势在于,它们能够自适应地学习邻居的重要性权重。然而,计算成本和内存消耗随着每对邻居之间的注意权重的计算而迅速增加。


3、Graph Autoencoders


图自动编码器是一类图嵌入方法,其目的是利用神经网络结构将图的顶点表示为低维向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入,其中解码器重建节点的邻域统计信息,如positive pointwise mutual information (PPMI)或一阶和二阶近似值。最近,研究人员已经探索了将GCN作为编码器的用途,将GCN与GAN结合起来,或将LSTM与GAN结合起来设计图自动编码器。我们将首先回顾基于GCN的AutoEncoder,然后总结这一类别中的其他变体。


目前基于GCN的自编码器的方法主要有:Graph Autoencoder (GAE)和Adversarially Regularized Graph Autoencoder (ARGA)


图自编码器的其它变体有:


Network Representations with Adversarially Regularized Autoencoders (NetRA)


Deep Neural Networks for Graph Representations (DNGR)


Structural Deep Network Embedding (SDNE)


Deep Recursive Network Embedding (DRNE)


DNGR和SDNE学习仅给出拓扑结构的节点嵌入,而GAE、ARGA、NetRA、DRNE用于学习当拓扑信息和节点内容特征都存在时的节点嵌入。图自动编码器的一个挑战是邻接矩阵A的稀疏性,这使得解码器的正条目数远远小于负条目数。为了解决这个问题,DNGR重构了一个更密集的矩阵,即PPMI矩阵,SDNE对邻接矩阵的零项进行惩罚,GAE对邻接矩阵中的项进行重加权,NetRA将图线性化为序列。


4、Graph Generative Networks


图生成网络的目标是在给定一组观察到的图的情况下生成新的图。图生成网络的许多方法都是特定于领域的。例如,在分子图生成中,一些工作模拟了称为SMILES的分子图的字符串表示。在自然语言处理中,生成语义图或知识图通常以给定的句子为条件。最近,人们提出了几种通用的方法。一些工作将生成过程作为节点和边的交替形成因素,而另一些则采用生成对抗训练。这类方法要么使用GCN作为构建基块,要么使用不同的架构。


基于GCN的图生成网络主要有


Molecular Generative Adversarial Networks (MolGAN):将relational GCN、改进的GAN和强化学习(RL)目标集成在一起,以生成具有所需属性的图。GAN由一个生成器和一个鉴别器组成,它们相互竞争以提高生成器的真实性。在MolGAN中,生成器试图提出一个伪图及其特征矩阵,而鉴别器的目标是区分伪样本和经验数据。此外,还引入了一个与鉴别器并行的奖励网络,以鼓励生成的图根据外部评价器具有某些属性。


Deep Generative Models of Graphs (DGMG):利用基于空间的图卷积网络来获得现有图的隐藏表示。生成节点和边的决策过程是以整个图的表示为基础的。简而言之,DGMG递归地在一个图中产生一个节点,直到达到某个停止条件。在添加新节点后的每一步,DGMG都会反复决定是否向添加的节点添加边,直到决策的判定结果变为假。如果决策为真,则评估将新添加节点连接到所有现有节点的概率分布,并从概率分布中抽取一个节点。将新节点及其边添加到现有图形后,DGMG将更新图的表示。


其它架构的图生成网络主要有


GraphRNN:通过两个层次的循环神经网络的深度图生成模型。图层次的RNN每次向节点序列添加一个新节点,而边层次RNN生成一个二进制序列,指示新添加的节点与序列中以前生成的节点之间的连接。为了将一个图线性化为一系列节点来训练图层次的RNN,GraphRNN采用了广度优先搜索(BFS)策略。为了建立训练边层次的RNN的二元序列模型,GraphRNN假定序列服从多元伯努利分布或条件伯努利分布。


NetGAN:Netgan将LSTM与Wasserstein-GAN结合在一起,使用基于随机行走的方法生成图形。GAN框架由两个模块组成,一个生成器和一个鉴别器。生成器尽最大努力在LSTM网络中生成合理的随机行走序列,而鉴别器则试图区分伪造的随机行走序列和真实的随机行走序列。训练完成后,对一组随机行走中节点的共现矩阵进行正则化,我们可以得到一个新的图。


5、Graph Spatial-Temporal Networks


图时空网络同时捕捉时空图的时空相关性。时空图具有全局图结构,每个节点的输入随时间变化。例如,在交通网络中,每个传感器作为一个节点连续记录某条道路的交通速度,其中交通网络的边由传感器对之间的距离决定。图形时空网络的目标可以是预测未来的节点值或标签,或者预测时空图标签。最近的研究仅仅探讨了GCNs的使用,GCNs与RNN或CNN的结合,以及根据图结构定制的循环体系结构。


目前图时空网络的模型主要有


Diffusion Convolutional Recurrent Neural Network (DCRNN)


CNN-GCN


Spatial Temporal GCN (ST-GCN)


Structural-RNN



三、图神经网络的应用


1、Computer Vision


图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。


在场景图生成中,对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像,场景图生成模型检测和识别对象,并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图,其中每个词代表一个对象,这是一个有希望的解决方案,以合成给定的文本描述图像。


在点云分类和分割中,点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境,这通常有利于无人驾驶车辆。为了识别点云所描绘的物体,将点云转换为k-最近邻图或叠加图,并利用图论进化网络来探索拓扑结构。


在动作识别中,识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一组解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图表。给定人类关节位置的时间序列,应用时空神经网络来学习人类行为模式。


此外,图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。


2、Recommender Systems


基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息,基于图的推荐系统能够生成高质量的推荐。推荐系统的关键是评价一个项目对用户的重要性。因此,可以将其转换为一个链路预测问题。目标是预测用户和项目之间丢失的链接。为了解决这个问题,有学者提出了一种基于GCN的图形自动编码器。还有学者结合GCN和RNN,来学习用户对项目评分的隐藏步骤。


3、Traffic


交通拥堵已成为现代城市的一个热点社会问题。准确预测交通网络中的交通速度、交通量或道路密度,在路线规划和流量控制中至关重要。有学者采用基于图的时空神经网络方法来解决这些问题。他们模型的输入是一个时空图。在这个时空图中,节点由放置在道路上的传感器表示,边由阈值以上成对节点的距离表示,每个节点都包含一个时间序列作为特征。目标是预测一条道路在时间间隔内的平均速度。另一个有趣的应用是出租车需求预测。这有助于智能交通系统有效利用资源,节约能源。


4、Chemistry


在化学中,研究人员应用图神经网络研究分子的图结构。在分子图中,原子为图中的节点,化学键为图中的边。节点分类、图形分类和图形生成是分子图的三个主要任务,它们可以用来学习分子指纹、预测分子性质、推断蛋白质结构、合成化合物。


5、Others


除了以上四个领域外,图神经网络还已被探索可以应用于其他问题,如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。



-End-


*延伸阅读





CV细分方向交流群


添加极市小助手微信(ID : cv-mart),备注:研究方向-姓名-学校/公司-城市(如:目标检测-小极-北大-深圳),即可申请加入目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割等极市技术交流群(已经添加小助手的好友直接私信),更有每月大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流一起来让思想之光照的更远吧~



△长按添加极市小助手


△长按关注极市平台


觉得有用麻烦给个在看啦~  

登录查看更多
70

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

题目: Continuous Graph Neural Networks

摘要:

本文建立了图神经网络与传统动力系统之间的联系。我们提出了持续图神经网络(CGNN),它将现有的图神经网络与离散动力学进行了一般化,因为它们可以被视为一种特定的离散化方案。关键思想是如何表征节点表示的连续动力学,即关于时间的节点表示的导数。受现有的基于扩散的图方法(如社交网络上的PageRank和流行模型)的启发,我们将导数定义为当前节点表示、邻节点表示和节点初始值的组合。我们提出并分析了两种可能的动态图,包括节点表示的每个维度(又名特征通道)各自改变或相互作用的理论证明。所提出的连续图神经网络在过度平滑方面具有很强的鲁棒性,因此允许我们构建更深层次的网络,进而能够捕获节点之间的长期依赖关系。在节点分类任务上的实验结果证明了我们提出的方法在和基线对比的有效性。

介绍

图神经网络(GNNs)由于其在节点分类等多种应用中的简单性和有效性而受到越来越多的关注;、链接预测、化学性质预测、自然语言理解。GNN的基本思想是设计多个图传播层,通过聚合邻近节点的节点表示和节点本身的表示,迭代地更新每个节点表示。在实践中,对于大多数任务,几层(两层或三层)通常就足够了,更多的层可能导致较差的性能。

改进GNNs的一个关键途径是能够建立更深层次的网络,以了解数据和输出标签之间更复杂的关系。GCN传播层平滑了节点表示,即图中相邻的节点变得更加相似。当我们堆叠越来越多的层时,这会导致过度平滑,这意味着节点表示收敛到相同的值,从而导致性能下降。因此,重要的是缓解节点过平滑效应,即节点表示收敛到相同的值。

此外,对于提高我们对GNN的理论理解,使我们能够从图结构中描述我们可以学到的信号,这是至关重要的。最近关于理解GCN的工作(Oono和Suzuki, 2020)认为GCN是由离散层定义的离散动力系统。此外,Chen等人(2018)证明了使用离散层并不是构建神经网络的唯一视角。他们指出,带有剩余连接的离散层可以看作是连续ODE的离散化。他们表明,这种方法具有更高的记忆效率,并且能够更平滑地建模隐藏层的动态。

我们利用基于扩散方法的连续视角提出了一种新的传播方案,我们使用来自常微分方程(即连续动力系统)的工具进行分析。事实上,我们能够解释我们的模型学习了什么表示,以及为什么它不会遭受在GNNs中常见的过度平滑问题。允许我们建立更深层次的网络,也就是说我们的模型在时间价值上运行良好。恢复过平滑的关键因素是在连续设置中使用了最初在PageRank中提出的原始分布。直观上,重新开始分布有助于不忘记邻接矩阵的低幂次信息,从而使模型收敛到有意义的平稳分布。

本文的主要贡献是:

  • 基于PageRank和扩散方法,提出了两个连续递增模型容量的ODEs;
  • 我们从理论上分析了我们的层学习的表示,并表明当t → ∞我们的方法接近一个稳定的不动点,它捕获图结构和原始的节点特征。因为我们在t→∞时是稳定的,我们的网络可以有无限多个“层”,并且能够学习远程依赖关系;
  • 我们证明了我们的模型的记忆是高效的,并且对t的选择是具有鲁棒性的。除此之外,我们进一步证明了在节点分类任务上,我们的模型能够比许多现有的最先进的方法表现更好。
成为VIP会员查看完整内容
0
103

近年来,人们对学习图结构数据表示的兴趣大增。基于标记数据的可用性,图表示学习方法一般分为三大类。第一种是网络嵌入(如浅层图嵌入或图自动编码器),它侧重于学习关系结构的无监督表示。第二种是图正则化神经网络,它利用图来增加半监督学习的正则化目标的神经网络损失。第三种是图神经网络,目的是学习具有任意结构的离散拓扑上的可微函数。然而,尽管这些领域很受欢迎,但在统一这三种范式方面的工作却少得惊人。在这里,我们的目标是弥合图神经网络、网络嵌入和图正则化模型之间的差距。我们提出了图结构数据表示学习方法的一个综合分类,旨在统一几个不同的工作主体。具体来说,我们提出了一个图编码解码器模型(GRAPHEDM),它将目前流行的图半监督学习算法(如GraphSage、Graph Convolutional Networks、Graph Attention Networks)和图表示的非监督学习(如DeepWalk、node2vec等)归纳为一个统一的方法。为了说明这种方法的一般性,我们将30多个现有方法放入这个框架中。我们相信,这种统一的观点既为理解这些方法背后的直觉提供了坚实的基础,也使该领域的未来研究成为可能。

概述

学习复杂结构化数据的表示是一项具有挑战性的任务。在过去的十年中,针对特定类型的结构化数据开发了许多成功的模型,包括定义在离散欧几里德域上的数据。例如,序列数据,如文本或视频,可以通过递归神经网络建模,它可以捕捉序列信息,产生高效的表示,如机器翻译和语音识别任务。还有卷积神经网络(convolutional neural networks, CNNs),它根据移位不变性等结构先验参数化神经网络,在图像分类或语音识别等模式识别任务中取得了前所未有的表现。这些主要的成功仅限于具有简单关系结构的特定类型的数据(例如,顺序数据或遵循规则模式的数据)。

在许多设置中,数据几乎不是规则的: 通常会出现复杂的关系结构,从该结构中提取信息是理解对象之间如何交互的关键。图是一种通用的数据结构,它可以表示复杂的关系数据(由节点和边组成),并出现在多个领域,如社交网络、计算化学[41]、生物学[105]、推荐系统[64]、半监督学习[39]等。对于图结构的数据来说,将CNNs泛化为图并非易事,定义具有强结构先验的网络是一项挑战,因为结构可以是任意的,并且可以在不同的图甚至同一图中的不同节点之间发生显著变化。特别是,像卷积这样的操作不能直接应用于不规则的图域。例如,在图像中,每个像素具有相同的邻域结构,允许在图像中的多个位置应用相同的过滤器权重。然而,在图中,我们不能定义节点的顺序,因为每个节点可能具有不同的邻域结构(图1)。此外,欧几里德卷积强烈依赖于几何先验(如移位不变性),这些先验不能推广到非欧几里德域(如平移可能甚至不能在非欧几里德域上定义)。

这些挑战导致了几何深度学习(GDL)研究的发展,旨在将深度学习技术应用于非欧几里德数据。特别是,考虑到图在现实世界应用中的广泛流行,人们对将机器学习方法应用于图结构数据的兴趣激增。其中,图表示学习(GRL)方法旨在学习图结构数据的低维连续向量表示,也称为嵌入。

广义上讲,GRL可以分为两类学习问题,非监督GRL和监督(或半监督)GRL。第一个系列的目标是学习保持输入图结构的低维欧几里德表示。第二系列也学习低维欧几里德表示,但为一个特定的下游预测任务,如节点或图分类。与非监督设置不同,在非监督设置中输入通常是图结构,监督设置中的输入通常由图上定义的不同信号组成,通常称为节点特征。此外,底层的离散图域可以是固定的,这是直推学习设置(例如,预测一个大型社交网络中的用户属性),但也可以在归纳性学习设置中发生变化(例如,预测分子属性,其中每个分子都是一个图)。最后,请注意,虽然大多数有监督和无监督的方法学习欧几里德向量空间中的表示,最近有兴趣的非欧几里德表示学习,其目的是学习非欧几里德嵌入空间,如双曲空间或球面空间。这项工作的主要动机是使用一个连续的嵌入空间,它类似于它试图嵌入的输入数据的底层离散结构(例如,双曲空间是树的连续版本[99])。

鉴于图表示学习领域的发展速度令人印象深刻,我们认为在一个统一的、可理解的框架中总结和描述所有方法是很重要的。本次综述的目的是为图结构数据的表示学习方法提供一个统一的视图,以便更好地理解在深度学习模型中利用图结构的不同方法。

目前已有大量的图表示学习综述。首先,有一些研究覆盖了浅层网络嵌入和自动编码技术,我们参考[18,24,46,51,122]这些方法的详细概述。其次,Bronstein等人的[15]也给出了非欧几里德数据(如图或流形)的深度学习模型的广泛概述。第三,最近的一些研究[8,116,124,126]涵盖了将深度学习应用到图数据的方法,包括图数据神经网络。这些调查大多集中在图形表示学习的一个特定子领域,而没有在每个子领域之间建立联系。

在这项工作中,我们扩展了Hamilton等人提出的编码-解码器框架,并介绍了一个通用的框架,图编码解码器模型(GRAPHEDM),它允许我们将现有的工作分为四大类: (i)浅嵌入方法,(ii)自动编码方法,(iii) 图正则化方法,和(iv) 图神经网络(GNNs)。此外,我们还介绍了一个图卷积框架(GCF),专门用于描述基于卷积的GNN,该框架在广泛的应用中实现了最先进的性能。这使我们能够分析和比较各种GNN,从在Graph Fourier域中操作的方法到将self-attention作为邻域聚合函数的方法[111]。我们希望这种近期工作的统一形式将帮助读者深入了解图的各种学习方法,从而推断出相似性、差异性,并指出潜在的扩展和限制。尽管如此,我们对前几次综述的贡献有三个方面

  • 我们介绍了一个通用的框架,即GRAPHEDM,来描述一系列广泛的有监督和无监督的方法,这些方法对图形结构数据进行操作,即浅层嵌入方法、图形正则化方法、图形自动编码方法和图形神经网络。

  • 我们的综述是第一次尝试从同一角度统一和查看这些不同的工作线,我们提供了一个通用分类(图3)来理解这些方法之间的差异和相似之处。特别是,这种分类封装了30多个现有的GRL方法。在一个全面的分类中描述这些方法,可以让我们了解这些方法究竟有何不同。

  • 我们为GRL发布了一个开源库,其中包括最先进的GRL方法和重要的图形应用程序,包括节点分类和链接预测。我们的实现可以在https://github.com/google/gcnn-survey-paper上找到。

成为VIP会员查看完整内容
0
194

【导读】Graph Neural Network(GNN)由于具有分析图结构数据的能力而受到了广泛的关注。本文对Graph Neural Network进行了简要介绍。它涵盖了一些图论,以便于理解图和分析图时遇到的问题。然后介绍了不同形式的Graph神经网络及其原理。它还涵盖了GNN可以做什么以及GNN的一些应用。

图论

首先,我们需要知道什么是图。图是一种由两个部分组成的数据结构:顶点和edge。它用作分析目标和实体之间成对关系的数学结构。通常,将图定义为G =(V,E),其中V是一组节点,E是它们之间的边。

图通常由邻接矩阵A表示。如果图具有N个节点,则A的维数为(N x N)。人们有时会提供另一个特征矩阵来描述图中的节点。如果每个节点都有F个特征,则特征矩阵X的维数为(N x F)。

为什么图难以分析?

首先,在欧几里得空间中不存在图,这意味着它无法用我们熟悉的任何坐标系表示。与其他类型的数据(例如波,图像或时间序列信号)相比,这使得图数据的解释更加困难(“文本”也可以视为时间序列),可以轻松地将其映射为2-D或3-D欧几里德空间。

其次,图没有固定的形式。为什么?看下面的例子。图(A)和图(B)具有完全不同的结构和外观。但是,当我们将其转换为邻接矩阵表示形式时,两个图具有相同的邻接矩阵(如果不考虑边的权重)。那么我们应该考虑这两个图是相同还是不同?

最后,一般来说,图很难直观地显示出来以供人类解释。我不是在谈论像上面的例子这样的小图。我说的是涉及数百或数千个节点的巨型图。它的维数很高,节点密集地分组在一起,甚至使人难以理解图。因此,为该任务训练机器是具有挑战性的。以下示例显示了对集成电路中逻辑门进行建模的图。

Example of a giant graph: circuit netlist. Figure from J. Baehr et. al. “Machine Learning and Structural Characteristics of Reverse Engineering”

为什么要使用图?

人们选择使用图的原因可以归纳为以下几点:

  1. 图提供了一种更好的方式来处理诸如关系和交互之类的抽象概念。它们还提供了直观的视觉方式来思考这些概念。图也构成了在社会环境中分析关系的自然基础。
  2. 图可以通过将问题简化为更简单的表示形式来解决更复杂的问题,或者从不同的角度将问题转换为表示形式。
  3. 图论和概念用于研究和建模社交网络,欺诈模式,功耗模式,病毒性以及在社交媒体中的影响力。社交网络分析(SNA)可能是图论在数据科学中最著名的应用。

传统图分析方法

传统方法主要基于算法,例如:

  1. 搜索算法,例如BFS,DFS
  2. 最短路径算法,例如Dijkstra算法,最近邻居
  3. 生成树算法,例如Prim算法
  4. 聚类方法,例如高度连接的组件,k均值 这种算法的局限性在于,在应用该算法之前,我们需要以一定的置信度获得图的先验知识。换句话说,它对我们研究图本身没有任何意义。最重要的是,没有办法执行图级别分类。

图神经网络

所谓的图神经网络是一种可以直接应用于图的神经网络。它为节点级别,边缘级别和图级别的预测任务提供了一种方便的方法。

文献中主要有三种类型的图神经网络:

  1. 递归图神经网络
  2. 空间卷积网络
  3. 谱卷积网络

GNN的直觉是,节点自然是由其邻居和连接定义的。为了理解这一点,我们可以简单地想象一下,如果删除节点周围的邻居和连接,则该节点将丢失其所有信息。因此,节点的邻居和与邻居的连接定义了节点的概念。

考虑到这一点,我们然后给每个节点一个状态(x)来表示其概念。我们可以使用节点状态(x)产生输出(o),即有关概念的决策。节点的最终状态(x_n)通常称为“节点嵌入”。所有GNN的任务是通过查看其相邻节点上的信息来确定每个节点的“节点嵌入”。 我们将从图神经网络,循环图神经网络或RecGNN的经典版本开始。

递归图神经网络

正如原始GNN论文中介绍的那样,RecGNN是基于Banach不动点定理的假设而构建的。Banach不动点定理指出:(X,d)是一个完整的度量空间,而(T:X→X)是一个压缩映射。然后,T具有唯一的不动点(x ∗),对于任何x∈X,n→∞的序列T_n(x)收敛到(x ∗)。这意味着,如果我申请的映射T上X为ķ倍,X ^ K在几乎等于x ^(K-1),即:

RecGNN定义了一个参数化函数f_w:

其中L_N,l_co,x_ne,l_ne 表示当前节点的特征[n],节点的边缘[n],相邻节点的状态,与相邻节点的功能。(在原始论文中,作者将节点特征称为节点标签。这可能会造成一些混乱。)

An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model” 最终,在经过k次迭代之后,最终的节点状态将用于生成输出,以决定每个节点。输出函数定义为:

空间卷积网络

空间卷积网络的直觉类似于著名的CNN,后者主导着图像分类和分割任务的文献。要了解图像上的CNN,您可以查看这篇文章,其中详细说明了CNN。

简而言之,在图像上进行卷积的想法是对中心像素周围的相邻像素求和,该像素由参数化大小和可学习权重的滤波器指定。空间卷积网络通过将相邻节点的特征聚合到中心节点中采用了相同的思想。

Left: Convolution on a regular graph such as an image. Right: Convolution on the arbitrary graph structure. Figure from “A Comprehensive Survey on Graph Neural Networks”

谱卷积网络

与其他类型的GNN相比,这种类型的图卷积网络具有非常强大的数学基础。谱卷积网络建立在图信号处理理论的基础上。并通过简化和逼近图卷积。 通过Chebyshev多项式逼近 (Hammond et al。2011),图卷积可以简化为以下形式:

进一步简化后,GCN论文提出了一种2层神经网络结构,可以用以下等式描述:

其中A_head是原始图邻接矩阵A的预处理拉普拉斯算子。(有关数学的详细信息,请参见GCN论文。将需要大量的精力来进行充分说明。)

如果您有一些机器学习经验,则此公式看起来非常熟悉。这不过是常用的两个完全连接的层结构。但是在这种情况下,它确实可以用作图卷积。我将在下面说明为什么它可以执行图卷积。

Example of a graph with a feature assigned to each node. Figured by author

让我们考虑一下,我们有一个包含4个节点的简单图。如上图所示,为这些节点中的每个节点分配了一个特征矩阵。图邻接矩阵和特征矩阵很容易得出,如下所示:

Example of the adjacency matrix and feature matrix. Figure by author

注意,邻接矩阵的对角线故意更改为“ 1”,以为每个节点添加一个自环。当我们执行特征聚合时,这将包括每个节点本身的特征。 然后,我们执行A x X(为简单起见,我们先忽略A的拉普拉斯算子和权重矩阵W。)

Example of graph convolution by matrix multiplication. Figure by author

矩阵乘法的结果显示在最右边的矩阵中。让我们以第一个节点的结果功能为例。不难发现结果是[节点1]的所有特征之和,包括[节点1]本身的特征,并且[节点4]中的特征不包括在内,因为它不是[节点1]的邻居。。在数学上,仅当存在边时,图的邻接矩阵才具有值“ 1”,否则具有“ 0”。这使得矩阵乘法成为连接到参考节点的节点的特征之和。 因此,频谱卷积网络和空间卷积网络尽管是在不同的基础上开始的,但是它们共享相同的传播规则。 当前可用的所有卷积图神经网络共享相同的格式。他们都尝试学习通过该消息传递过程传递节点信息并更新节点状态的功能。 任何图神经网络可被表达为与消息传递神经网络(J. Gilmer et al. , 2017)的消息传递功能,节点更新功能和读出功能。

GNN可以做什么?

GNN解决的问题可以大致分为三类:

  1. 节点分类
  2. 链接预测
  3. 图分类 在节点分类中,任务是预测图中每个节点的节点嵌入。通常以半监督的方式训练此类问题,其中仅对部分图进行标记。节点分类的典型应用包括引文网络,Reddit帖子,Youtube视频和Facebook朋友关系。 在链接预测中,任务是了解图中实体之间的关系,并预测两个实体之间是否存在连接。例如,推荐系统可被视为链接预测问题,其中模型被赋予一组用户对不同产品的评论,任务是预测用户的偏好并调整推荐系统以根据用户推送更多相关感兴趣的产品。 在图分类中,任务是将整个图分类为不同的类别。它类似于图像分类,但是目标变为图域。有许多工业问题可以应用图分类,例如在化学,生物医学,物理学中,模型被赋予分子结构并被要求将目标分类为有意义的类别。它加快了对原子,分子或任何其他结构化数据类型的分析。

一些实际的应用

在了解了GNN可以执行哪种类型的分析之后,您一定想知道我可以对图进行哪些实际应用。好了,本节将为您提供有关GNN实际应用的更多见解。

自然语言处理中的GNN

GNN被广泛使用在自然语言处理(NLP)中。实际上,这也是GNN最初开始的地方。如果您中的某些人具有NLP经验,则必须考虑到文本应该是一种序列或时间数据,则可以由RNN或LTSM最好地描述。然而,GNN则从完全不同的角度解决了这个问题。GNN利用单词或文档的内部关系来预测类别。例如,引文网络尝试根据论文引文关系和其他论文中引用的词来预测网络中每篇论文的标签。它也可以通过查看句子的不同部分而不是像RNN或LTSM中那样的纯粹序列来构建语法模型。

计算机视觉中的GNN

许多基于CNN的方法已经在图像中的目标检测中达到了最新的性能,但是我们还不知道目标之间的关系。GNN在CV中的一种成功应用是使用图来建模基于CNN的检测器检测到的物体之间的关系。从图像中检测到目标后,将它们输入到GNN推理中以进行关系预测。GNN推断的结果是生成的图,该图对不同目标之间的关系进行建模。

Scene Graph Generation. Figure from D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017

CV中另一个有趣的应用是根据图描述生成图像。这可以解释为几乎与上述应用相反。图像生成的传统方式是使用GAN或自动编码器生成文本到图像。从图到图像的生成不是使用文本来描述图像,而是提供了有关图像语义结构的更多信息。

Image generated from scene graphs. Figure from J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018 我想分享的最有趣的应用是零样本学习(ZSL)。您可以找到这篇文章,以全面了解ZSL。总之,ZSL是想学给定的一类分类NO(目标类别的)训练样本。这是非常具有挑战性的,因为如果没有给出训练样本,我们需要让模型在逻辑上“思考”以识别目标。例如,如果给了我们三张图像(如下图所示),并告诉我们在其中找到“ okapi”。我们以前可能没有看过“okapi”。但是,如果我们还得到信息,“okapi”是一种有四只腿,斑马纹皮肤的鹿面动物,那么我们就不难确定哪个是“okapii”。典型的方法是通过将检测到的特征转换为文本来模拟这种“思考过程”。但是,文本编码彼此独立。很难对文本描述之间的关系进行建模。换句话说,图表示很好地模拟了这些关系。

Figure from X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018

其他领域的GNN

GNN的更多实际应用包括人类行为检测,交通控制,分子结构研究,推荐系统,程序验证,逻辑推理,社会影响预测以及对抗攻击。下面显示了对社交网络中人际关系建模的图表。GNN可用于将人们分为不同的社区群体。

结论

我们在本文中介绍了一些图论,并强调了分析图的重要性。人们总是将机器学习算法视为“ 黑匣子 ”。大多数机器学习算法仅从训练数据的特征中学习,但没有实际的逻辑可以执行。使用形,我们也许能够将一些“逻辑”传递给机器,并使其更自然地“思考”。

GNN仍然是一个相对较新的领域,值得更多的研究关注。它是分析图数据的强大工具。但是,它不仅限于图中的问题。它可以很容易地推广到任何可以通过图建模的研究中。图建模是分析问题的自然方法。

参考链接:

https://medium.com/datadriveninvestor/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

成为VIP会员查看完整内容
0
94

1、Approximation Ratios of Graph Neural Networks for Combinatorial Problems

作者:Ryoma Sato, Makoto Yamada, Hisashi Kashima;

摘要:本文从理论的角度研究了图神经网络(GNNs)在学习组合问题近似算法中的作用。为此,我们首先建立了一个新的GNN类,它可以严格地解决比现有GNN更广泛的问题。然后,我们弥合了GNN理论和分布式局部算法理论之间的差距,从理论上证明了最强大的GNN可以学习最小支配集问题的近似算法和具有一些近似比的最小顶点覆盖问题比率,并且没有GNN可以执行比这些比率更好。本文首次阐明了组合问题中GNN的近似比。此外,我们还证明了在每个节点特征上添加着色或弱着色可以提高这些近似比。这表明预处理和特征工程在理论上增强了模型的能力。

网址:https://www.zhuanzhi.ai/paper/9cad40c81920dfd71fa91e4ddf778616

2、D-VAE: A Variational Autoencoder for Directed Acyclic Graphs

作者:Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, Yixin Chen;

摘要:图结构数据在现实世界中是丰富的。在不同的图类型中,有向无环图(DAG)是机器学习研究人员特别感兴趣的,因为许多机器学习模型都是通过DAG上的计算来实现的,包括神经网络和贝叶斯网络。本文研究了DAG的深度生成模型,提出了一种新的DAG变分自编码器(D-VAE)。为了将DAG编码到潜在空间中,我们利用了图神经网络。我们提出了一个异步消息传递方案,它允许在DAG上编码计算,而不是使用现有的同步消息传递方案来编码局部图结构。通过神经结构搜索和贝叶斯网络结构学习两项任务验证了该方法的有效性。实验表明,该模型不仅生成了新颖有效的DAG,还可以生成平滑的潜在空间,有助于通过贝叶斯优化搜索具有更好性能的DAG。

网址:https://www.zhuanzhi.ai/paper/80f4d50cc2b619ff8317a9e56f8a47c0

3、End to end learning and optimization on graphs

作者:Bryan Wilder, Eric Ewing, Bistra Dilkina, Milind Tambe;

摘要:在实际应用中,图的学习和优化问题常常结合在一起。例如,我们的目标可能是对图进行集群,以便检测有意义的社区(或者解决其他常见的图优化问题,如facility location、maxcut等)。然而,图或相关属性往往只是部分观察到,引入了一些学习问题,如链接预测,必须在优化之前解决。我们提出了一种方法,将用于常见图优化问题的可微代理集成到用于链接预测等任务的机器学习模型的训练中。这允许模型特别关注下游任务,它的预测将用于该任务。实验结果表明,我们的端到端系统在实例优化任务上的性能优于将现有的链路预测方法与专家设计的图优化算法相结合的方法。

网址:https://www.zhuanzhi.ai/paper/863d6ac1bd27220c6fc1b7c2e4f17c47

4、Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels

作者:Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, Keyulu Xu;

摘要:虽然图内核(graph kernel,GK)易于训练并享有可证明的理论保证,但其实际性能受其表达能力的限制,因为内核函数往往依赖于图的手工组合特性。与图内核相比,图神经网络通常具有更好的实用性能,因为图神经网络使用多层结构和非线性激活函数来提取图的高阶信息作为特征。然而,由于训练过程中存在大量的超参数,且训练过程具有非凸性,使得GNN的训练更加困难。GNN的理论保障也没有得到很好的理解。此外,GNN的表达能力随参数的数量而变化,在计算资源有限的情况下,很难充分利用GNN的表达能力。本文提出了一类新的图内核,即图神经切线核(GNTKs),它对应于通过梯度下降训练的无限宽的多层GNN。GNTK充分发挥了GNN的表现力,继承了GK的优势。从理论上讲,我们展示了GNTK可以在图上学习一类平滑函数。根据经验,我们在图分类数据集上测试GNTK并展示它们实现了强大的性能。

网址:https://www.zhuanzhi.ai/paper/e3feff32dc2f8d03c7b3d4b5beefd61d

5、HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs

作者:Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, Partha Talukdar;

摘要:在许多真实世界的网络数据集中,如co-authorship、co-citation、email communication等,关系是复杂的,并且超越了成对关联。超图(Hypergraph)提供了一个灵活而自然的建模工具来建模这种复杂的关系。在许多现实世界网络中,这种复杂关系的明显存在,自然会激发使用Hypergraph学习的问题。一种流行的学习范式是基于超图的半监督学习(SSL),其目标是将标签分配给超图中最初未标记的顶点。由于图卷积网络(GCN)对基于图的SSL是有效的,我们提出了HyperGCN,这是一种在超图上训练用于SSL的GCN的新方法。我们通过对真实世界超图的详细实验证明HyperGCN的有效性,并分析它何时比最先进的baseline更有效。

网址:https://www.zhuanzhi.ai/paper/8135bfbfd1bca867403e0d7711a4b5f8

6、Social-BiGAT: Multimodal Trajectory Forecasting using Bicycle-GAN and Graph Attention Networks

作者:Vineet Kosaraju, Amir Sadeghian, Roberto Martín-Martín, Ian Reid, S. Hamid Rezatofighi, Silvio Savarese;

摘要:从自动驾驶汽车和社交机器人的控制到安全监控,预测场景中多个交互主体的未来轨迹已成为许多不同应用领域中一个日益重要的问题。这个问题由于人类之间的社会互动以及他们与场景的身体互动而变得更加复杂。虽然现有的文献探索了其中的一些线索,但它们主要忽略了每个人未来轨迹的多模态性质。在本文中,我们提出了一个基于图的生成式对抗网络Social-BiGAT,它通过更好地建模场景中行人的社交互来生成真实的多模态轨迹预测。我们的方法是基于一个图注意力网络(GAT)学习可靠的特征表示(编码场景中人类之间的社会交互),以及一个反方向训练的循环编解码器体系结构(根据特征预测人类的路径)。我们明确地解释了预测问题的多模态性质,通过在每个场景与其潜在噪声向量之间形成一个可逆的变换,就像在Bicycle-GAN中一样。我们表明了,与现有轨迹预测基准的几个baseline的比较中,我们的框架达到了最先进的性能。

网址:https://www.zhuanzhi.ai/paper/4f454de9b5e71da16aed5a03e88d0eab

7、Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

作者:Hongteng Xu, Dixin Luo, Lawrence Carin;

摘要:我们提出了一种可扩展的Gromov-Wasserstein learning (S-GWL) 方法,并建立了一种新的、理论支持的大规模图分析范式。该方法基于Gromov-Wasserstein discrepancy,是图上的伪度量。给定两个图,与它们的Gromov-Wasserstein discrepancy相关联的最优传输提供了节点之间的对应关系,从而实现了图的匹配。当其中一个图具有独立但自连接的节点时(即,一个断开连接的图),最优传输表明了其他图的聚类结构,实现了图的划分。利用这一概念,通过学习多观测图的Gromov-Wasserstein barycenter图,将该方法推广到多图的划分与匹配; barycenter图起到断开图的作用,因为它是学习的,所以聚类也是如此。该方法将递归K分割机制与正则化近似梯度算法相结合,对于具有V个节点和E条边的图,其时间复杂度为O(K(E+V) logk V)。据我们所知,我们的方法是第一次尝试使Gromov-Wasserstein discrepancy适用于大规模的图分析,并将图的划分和匹配统一到同一个框架中。它优于最先进的图划分和匹配方法,实现了精度和效率之间的平衡。

网址:https://www.zhuanzhi.ai/paper/e6d212914ae39ae0002acfaaae261fe5

8、Universal Invariant and Equivariant Graph Neural Networks

作者:Nicolas Keriven, Gabriel Peyré;

摘要:图神经网络(GNN)有多种形式,但应该始终是不变的(输入图节点的排列不会影响输出)或等变的(输入的排列置换输出)。本文考虑一类特殊的不变和等变网络,证明了它的一些新的普适性定理。更确切地说,我们考虑具有单个隐藏层的网络,它是通过应用等变线性算子、点态非线性算子和不变或等变线性算子形成的信道求和而得到的。最近,Maron et al. (2019b)指出,通过允许网络内部的高阶张量化,可以获得通用不变的GNN。作为第一个贡献,我们提出了这个结果的另一种证明,它依赖于实值函数代数的Stone-Weierstrass定理。我们的主要贡献是将这一结果推广到等变情况,这种情况出现在许多实际应用中,但从理论角度进行的研究较少。证明依赖于一个新的具有独立意义的广义等变函数代数Stone-Weierstrass定理。最后,与以往许多考虑固定节点数的设置不同,我们的结果表明,由一组参数定义的GNN可以很好地近似于在不同大小的图上定义的函数。

网址:https://www.zhuanzhi.ai/paper/2236e35c386d62a4df3f687ecdf8e7b5

成为VIP会员查看完整内容
0
34
小贴士
相关资讯
Graph Neural Networks 综述
计算机视觉life
22+阅读 · 2019年8月13日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
390+阅读 · 2019年4月30日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
154+阅读 · 2019年2月14日
图神经网络概述第三弹:来自IEEE Fellow的GNN综述
机器之心
43+阅读 · 2019年1月7日
清华大学图神经网络综述:模型与应用
机器之心
54+阅读 · 2018年12月26日
图神经网络综述:模型与应用
PaperWeekly
165+阅读 · 2018年12月26日
相关VIP内容
相关论文
Wenqi Fan,Yao Ma,Qing Li,Yuan He,Eric Zhao,Jiliang Tang,Dawei Yin
14+阅读 · 2019年11月23日
Wei-Lin Chiang,Xuanqing Liu,Si Si,Yang Li,Samy Bengio,Cho-Jui Hsieh
9+阅读 · 2019年8月8日
Neural Image Captioning
Elaina Tan,Lakshay Sharma
4+阅读 · 2019年7月2日
Position-aware Graph Neural Networks
Jiaxuan You,Rex Ying,Jure Leskovec
9+阅读 · 2019年6月11日
A Comprehensive Survey on Graph Neural Networks
Zonghan Wu,Shirui Pan,Fengwen Chen,Guodong Long,Chengqi Zhang,Philip S. Yu
10+阅读 · 2019年3月10日
Hao Peng,Jianxin Li,Qiran Gong,Senzhang Wang,Yuanxing Ning,Philip S. Yu
5+阅读 · 2019年2月25日
Yao Ma,Ziyi Guo,Zhaochun Ren,Eric Zhao,Jiliang Tang,Dawei Yin
15+阅读 · 2018年10月24日
Felix Laumann,Kumar Shridhar,Adrian Llopart Maurin
18+阅读 · 2018年6月27日
Christian Rupprecht,Iro Laina,Nassir Navab,Gregory D. Hager,Federico Tombari
4+阅读 · 2018年3月30日
Yike Liu,Abhilash Dighe,Tara Safavi,Danai Koutra
4+阅读 · 2017年4月12日
Top