近年来,人们对学习图结构数据表示的兴趣大增。基于标记数据的可用性,图表示学习方法一般分为三大类。第一种是网络嵌入(如浅层图嵌入或图自动编码器),它侧重于学习关系结构的无监督表示。第二种是图正则化神经网络,它利用图来增加半监督学习的正则化目标的神经网络损失。第三种是图神经网络,目的是学习具有任意结构的离散拓扑上的可微函数。然而,尽管这些领域很受欢迎,但在统一这三种范式方面的工作却少得惊人。在这里,我们的目标是弥合图神经网络、网络嵌入和图正则化模型之间的差距。我们提出了图结构数据表示学习方法的一个综合分类,旨在统一几个不同的工作主体。具体来说,我们提出了一个图编码解码器模型(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
55

相关内容

图神经网络(GNN)是一种学习图结构的神经网络。学习图结构允许我们在欧几里德空间中表示图的节点,这对于一些下游的机器学习任务非常有用。最近关于GNN的工作在链接预测、图分类和半监督任务方面表现出了令人印象深刻的性能(Hamilton et al., 2017b)。由于人们对机器学习社区越来越感兴趣,希望更多地了解这些技术,因此本文提供了关于GNN的介绍。

本文组织如下:首先,介绍了图和网络的基本概念。其次,我们描述了在GNNs中用于计算节点嵌入的主要步骤。接下来,我们将介绍现有文献中经常提到的三种GNN技术。最后,我们对该领域的其他著名作品进行了有限的综述

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

【导读】异构网络表示学习Heterogeneous Network Representation Learning是当前自数据挖掘以及其他应用的研究热点,在众多任务中具有重要的应用。近日,UIUC韩家炜等学者发布了异构网络表示学习的综述大全,共15页pdf115篇参考文献,从背景知识到当前代表性HNE模型和应用研究挑战等,是最新可参考绝好的异构网络表示学习模型的文献。

由于现实世界中的对象及其交互通常是多模态和多类型的,所以异构网络被广泛地用作传统同构网络(图)的一个更强大、更现实和更通用的超类。与此同时,表示学习(representation learning,又称嵌入)最近得到了深入的研究,并被证明对各种网络挖掘和分析任务都是有效的。由于已有大量的异构网络嵌入(HNE)算法,但没有专门的调研综述,作为这项工作的第一个贡献,我们率先提供了一个统一的范式,对各种现有的HNE算法的优点进行系统的分类和分析。此外,现有的HNE算法虽然大多被认为是通用的,但通常是在不同的数据集上进行评估。由于HNE在应用上的天然优势,这种间接的比较在很大程度上阻碍了任务性能的改善,特别是考虑到从真实世界的应用数据构建异构网络的各种可能的方法。因此,作为第二项贡献,我们创建了四个基准数据集,这些数据集具有不同来源的尺度、结构、属性/标签可用性等不同属性,以全面评估HNE算法。作为第三个贡献,我们对十种流行的HNE算法的实现进行了细致的重构和修改,并创建了友好的接口,并在多个任务和实验设置上对它们进行了全方位的比较。

1.概述

网络和图形构成了一种规范的、普遍存在的交互对象建模范式,已经引起了各个科学领域的重要研究关注[59、30、24、3、89、87]。然而,现实世界的对象和交互通常是多模态和多类型的(例如,作者、论文、场所和出版物网络中的术语[69,65];基于位置的社交网络中的用户、地点、类别和gps坐标[101,91,94];以及生物医学网络中的基因、蛋白质、疾病和物种[38,14])。为了捕获和利用这种节点和链路的异构性,异构网络被提出并广泛应用于许多真实的网络挖掘场景中,如基于元路径的相似度搜索[70、64、92]、节点分类和聚类[18、20、11]、知识库补全[68、48、103]和推荐[23、106、31]。

与此同时,目前对图数据的研究主要集中在表示学习(图数据嵌入)方面,特别是在神经网络算法的先行者们展示了前所未有的有效而高效的图数据挖掘的经验证据之后[25,4,13]。他们的目标是将图数据(如节点[49、72、26、77、37、28、9、75]、链接[107、1、50、96]和子图[47、93、97、45])转换为嵌入空间中的低维分布向量,在嵌入空间中保留图的拓扑信息(如高阶邻近性[5、76、105、34]和结构[55、102、42、17])。这样的嵌入向量可以被各种下游的机器学习算法直接执行[58,39,10]。

在异构网络与图嵌入的交叉点上,异构网络嵌入(HNE)近年来也得到了较多的研究关注[8、85、108、16、66、67、27、22、90、35、104、57、52、99、7、98、32、83、95、82、41]。由于HNE的应用优势,许多算法在不同的应用领域分别被开发出来,如搜索和推荐[23,63,6,89]。此外,由于知识库(KBs)也属于异构网络的一般范畴,许多KB嵌入算法可以与HNE算法相比较[81、3、40、68、88、15、48、79、60]。

不幸的是,不同的HNE算法是在学术界和工业界完全不同的社区开发的。无论是在概念上还是在实验中,都没有对其进行系统全面的分析。事实上,由于缺乏基准平台(有现成的数据集和基线),研究人员往往倾向于构建自己的数据集,并重新实现一些最流行的(有时是过时的)比较算法,这使得公平的性能评估和明确的改进属性变得极其困难。

只需考虑图1中发布数据小例子。较早的HNE算法如metapath2vec [16])是在作者、论文和场所节点类型为(a)的异构网络上发展起来的,但是可以像(b)那样用大量的术语和主题作为附加节点来丰富论文,这使得基于随机游走的浅嵌入算法效果不佳,而倾向于R-GCN[57]这样的基于邻域聚合的深度图神经网络。此外,还可以进一步加入术语嵌入等节点属性和研究领域等标签,使其只适用于半监督归纳学习算法,这可能会带来更大的偏差[104、82、33、54]。最后,通常很难清楚地将性能收益归因于技术新颖性和数据调整之间的关系。

在这项工作中,我们首先制定了一个统一而灵活的数学范式,概括了所有的HNE算法,便于理解每个模型的关键优点(第2节)。特别地,基于对现有模型(以及可能的未来模型)进行清晰分类和总结的统一分类,我们提出了网络平滑度的一般目标函数,并将所有现有的模型重新组织成统一的范式,同时突出其独特的新颖贡献(第3节)。我们认为该范式将有助于指导未来新型HNE算法的发展,同时促进它们与现有算法的概念对比。

作为第二个贡献,我们通过详尽的数据收集、清理、分析和整理(第4节),特意准备了四个基准的异构网络数据集,具有规模、结构、属性/标签可用性等多种属性。这些不同的数据集,以及一系列不同的网络挖掘任务和评估指标,构成了未来HNE算法的系统而全面的基准资源。

作为第三个贡献,许多现有的HNE算法(包括一些非常流行的算法)要么没有一个灵活的实现(例如,硬编码的节点和边缘类型、固定的元路径集等),要么不能扩展到更大的网络(例如,在训练期间的高内存需求),这给新的研究增加了很多负担(例如,,在正确的重新实现中需要大量的工程工作)。为此,我们选择了10种流行的HNE算法,在这些算法中,我们仔细地重构和扩展了原始作者的实现,并为我们准备好的数据集的插件输入应用了额外的接口(第5节)。基于这些易于使用和有效的实现,我们对算法进行了全面的经验评估,并报告了它们的基准性能。实证结果在提供了与第3节的概念分析相一致的不同模型的优点的同时,也为我们的基准平台的使用提供了范例,以供今后对HNE的研究参考。

本文的其余部分组织如下。第2节首先介绍我们提出的通用HNE范式。随后,第3节对我们调查中的代表性模型进行了概念上的分类和分析。然后,我们在第4节中提供了我们准备好的基准数据集,并进行了深入的分析。在第5节中,我们对10种常用的HNE算法进行了系统而全面的实证研究,对HNE的发展现状进行了评价。第六部分是对未来HNE平台使用和研究的展望。

异构网络示例

算法分类

Proximity-Preserving Methods

如前所述,网络嵌入的一个基本目标是捕获网络拓扑信息。这可以通过在节点之间保留不同类型的邻近性来实现。在HNE中,有两类主要的接近性保护方法:基于随机步法的方法(灵感来自DeepWalk[49])和基于一阶/二阶接近性的方法(灵感来自LINE[72])。

Message-Passing Methods

网络中的每个节点都可以将属性信息表示为特征向量xu。消息传递方法的目标是通过聚合来自u邻居的信息来学习基于xu的节点嵌入eu。在最近的研究中,图神经网络(GNNs)[37]被广泛用于促进这种聚合/消息传递过程。

Relation-Learning方法

异类网络中的每条边都可以看作是一个三元组(u, l, v),由两个节点u, v∈v和一个边缘类型l∈TE(即。,实体和关系,用KG表示)。关系学习方法的目标是学习一个评分函数sl(u, v),该函数对任意三元组求值并输出一个标量来度量该三元组的可接受性。这种思想在KB嵌入中被广泛采用。由于已经有关于KB嵌入算法的调查[81],我们在这里只讨论最流行的方法,并强调它们与HNE的联系。

基准

未来方向

在这项工作中,我们对各种现有的HNE算法进行了全面的调研,并提供了基准数据集和基线实现,以方便今后在这方面的研究。尽管HNE已经在各种下游任务中表现出了强大的性能,但它仍处于起步阶段,面临着许多尚未解决的挑战。为了总结这项工作并启发未来的研究,我们现在简要地讨论一下当前HNE的局限性和几个可能值得研究的具体方向。

超越同质性。如式(1)所述,目前的HNE算法主要关注网络同质性作用。由于最近对同构网络的研究,研究位置和结构嵌入的组合,探索如何将这种设计原则和范式推广到HNE将是很有趣的。特别是在异构网络中,节点的相对位置和结构角色都可以在不同的元路径或元图下测量,这自然更具有信息性和多样性。然而,这样的考虑也带来了更困难的计算挑战。

超越准确性。大多数,如果不是全部,现有的研究主要集中在对不同的下游任务的准确性。进一步研究HNE的效率和可扩展性(用于大规模网络)、时间适应性(用于动态演化网络)、鲁棒性(用于对抗攻击)、可解释性、不确定性、公平性等将是非常有趣的。

超越节点嵌入。图级和子图级嵌入在同构网络上得到了广泛的研究,但在异构网络上却很少有研究。虽然诸如HIN2Vec[22]等现有的工作都在研究元路径的嵌入以改进节点的嵌入,但是图和子图级嵌入在异构网络环境中的直接应用仍然处于萌芽状态。

回顾KB嵌入。KB嵌入与其他HNE类型的区别主要在于节点和链接类型的数量不同。直接将KB嵌入到异构网络中不能考虑具有丰富语义的元路径,而将HNE直接应用到KB中由于元路径的数量呈指数增长而不现实。然而,研究这两组方法(以及两种类型的数据)之间的交集仍然很有趣。例如,我们如何将异构网络上的元路径和HNE在KB上嵌入转换的思想与更多的语义感知转换结合起来?我们如何设计基于截断随机游走的方法来包含高阶关系的知识库嵌入?

异构上下文建模。异构网络主要模拟不同类型的节点和链接。然而,现在的网络常常与丰富的内容相关联,这些内容提供了节点、链接和子网的上下文。因此,如何通过多模态内容和结构的集成来对多方面环境下的异构交互进行建模可能是一个具有挑战性但值得研究的领域。

理解局限性。虽然HNE(以及许多神经表示学习模型)已经在各个领域显示出了强大的性能,但值得了解其潜在的局限性。例如,与传统的网络挖掘方法(例如,路径计数、子图匹配、非神经或线性传播)相比,现代HNE算法何时能更好地工作?我们怎样才能把两个世界的优点结合起来呢?此外,虽然对同构网络数据的神经网络背后的数学机制(如平滑、低通滤波、不变和等变变换)进行了深入的研究,通过统一现有的HNE模型,本工作也旨在激发对HNE的能力和局限性的进一步理论研究。

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

简介: 在许多将数据表示为图形的领域中,学习图形之间的相似性度量标准被认为是一个关键问题,它可以进一步促进各种学习任务,例如分类,聚类和相似性搜索。 最近,人们对深度图相似性学习越来越感兴趣,其中的主要思想是学习一种深度学习模型,该模型将输入图映射到目标空间,以使目标空间中的距离近似于输入空间中的结构距离。 在这里,我们提供对深度图相似性学习的现有文献的全面回顾。 我们为方法和应用提出了系统的分类法。 最后,我们讨论该问题的挑战和未来方向。

在特征空间上学习足够的相似性度量可以显着确定机器学习方法的性能。从数据自动学习此类度量是相似性学习的主要目的。相似度/度量学习是指学习一种功能以测量对象之间的距离或相似度,这是许多机器学习问题(例如分类,聚类,排名等)中的关键步骤。例如,在k最近邻(kNN)中分类[25],需要一个度量来测量数据点之间的距离并识别最近的邻居;在许多聚类算法中,数据点之间的相似性度量用于确定聚类。尽管有一些通用度量标准(例如欧几里得距离)可用于获取表示为矢量的对象之间的相似性度量,但是这些度量标准通常无法捕获正在研究的数据的特定特征,尤其是对于结构化数据。因此,找到或学习一种度量以测量特定任务中涉及的数据点的相似性至关重要。

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

题目: Representation Learning on Graphs: Methods and Applications

摘要:

图机器学习是一项重要且普遍存在的任务,其应用范围从药物设计到社交网络中的友情推荐。这个领域的主要挑战是找到一种表示或编码图形结构的方法,以便机器学习模型能够轻松地利用它。传统上,机器学习方法依赖于用户定义的启发法来提取对图的结构信息进行编码的特征(例如,度统计或内核函数)。然而,近年来,使用基于深度学习和非线性降维的技术,自动学习将图结构编码为低维嵌入的方法激增。在这里,我们提供了一个概念上的回顾,在这一领域的关键进展,图表示学习,包括基于矩阵分解的方法,随机漫步的算法和图神经网络。我们回顾了嵌入单个节点的方法以及嵌入整个(子)图的方法。在此过程中,我们开发了一个统一的框架来描述这些最近的方法,并强调了一些重要的应用程序和未来工作的方向。

作者简介:

William L. Hamilton是麦吉尔大学计算机科学的助理教授,也是加拿大魁北克Mila AI研究所的CIFAR AI主席。William L. Hamilton开发的机器学习模型可以对这个复杂的、相互联系的世界进行推理。研究兴趣集中在机器学习、网络科学和自然语言处理的交叉领域,目前的重点是快速发展的图表示学习和图神经网络。

Rex Ying是斯坦福大学计算机科学二年级的博士生,研究主要集中在开发应用于图形结构数据的机器学习算法。曾致力于开发可扩展到网络规模数据集的广义图卷积网络,应用于推荐系统、异常检测和生物学。

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

论文摘要

图无处不在,从引文和社交网络到知识图谱(KGs)。它们是最富表现力的数据结构之一,已被用于建模各种问题。知识图谱是图中事实的结构化表示,其中节点表示实体,边表示实体之间的关系。最近的研究已经开发出几种大型知识图谱;例如DBpedia、YAGO、NELL和Freebase。然而,它们都是稀疏的,每个实体只有很少的事实。例如,每个实体只包含1.34个事实。在论文的第一部分,我们提出了缓解这一问题的三个解决方案:(1)KG规范化,即(2)关联提取,它涉及到从非结构化文本中提取实体之间的语义关系的自动化过程;(3)链接预测,它包括基于KG中的已知事实推断缺失的事实。KG的规范化,我们建议CESI(规范化使用嵌入和边信息),一个新颖的方法执行规范化学习嵌入开放KG。KG嵌入的方法扩展了最新进展将相关NP和关系词信息原则的方式。对于关系提取,我们提出了一种远程监督神经关系提取方法,该方法利用KGs中的附加边信息来改进关系提取。最后,对于链路预测,我们提出了扩展ConvE的InteractE,这是一种基于卷积神经网络的链路预测方法,通过三个关键思想:特征置换、新颖的特征重塑和循环卷积来增加特征交互的次数。通过对多个数据集的大量实验,验证了所提方法的有效性。

传统的神经网络如卷积网络和递归神经网络在处理欧几里得数据时受到限制。然而,在自然语言处理(NLP)中图形是很突出的。最近,图卷积网络(Graph Convolutional Networks, GCNs)被提出来解决这一缺点,并成功地应用于多个问题。在论文的第二部分,我们利用GCNs来解决文档时间戳问题,它是文档检索和摘要等任务的重要组成部分。

为此,我们提出利用GCNs联合开发文档语法和时态图结构的NeuralDater,以获得该问题的最新性能。提出了一种灵活的基于图卷积的词嵌入学习方法——SynGCN,该方法利用词的依赖上下文而不是线性上下文来学习更有意义的词嵌入。在论文的第三部分,我们讨论了现有GCN模型的两个局限性,即(1)标准的邻域聚合方案对影响目标节点表示的节点数量没有限制。这导致了中心节点的噪声表示,中心节点在几个跃点中几乎覆盖了整个图。为了解决这个缺点,我们提出了ConfGCN(基于信任的GCN),它通过估计信任来确定聚合过程中一个节点对另一个节点的重要性,从而限制其影响邻居。(2)现有的GCN模型大多局限于处理无向图。然而,更一般和更普遍的一类图是关系图,其中每条边都有与之关联的标签和方向。现有的处理此类图的方法存在参数过多的问题,并且仅限于学习节点的表示。我们提出了一种新的图卷积框架CompGCN,它将实体和关系共同嵌入到一个关系图中。CompGCN是参数有效的,并且可以根据关系的数量进行扩展。它利用了来自KG嵌入技术的各种实体-关系组合操作,并在节点分类、链接预测和图分类任务上取得了明显的优势结果。

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