图神经网络(GNNs)最近被成功地用于节点和图的分类任务中,但GNNs对邻近节点属性之间的依赖关系建模,而不是对观察到的节点标签之间的依赖关系建模。在这项工作中,我们考虑了在监督和半监督设置中使用GNNs进行归纳节点分类的任务,其目标是合并标签依赖项。因为当前的GNN不是通用的。为了提高现有GNN的表达能力,我们提出了一种通用的集体学习方法。我们的框架结合了集体分类和自监督学习的思想,并使用蒙特卡罗方法来采样嵌入图的归纳学习。我们评估了5个真实网络数据集的性能,并证明了在各种最先进的GNN中,节点分类精度的一致性和显著提高。

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

相关内容

普渡大学位于美国印第安纳州的西拉法叶,是一所以理工科闻名的公立大学,绰号为锅炉工。

题目: Hyperbolic Heterogeneous Information Network Embedding

摘要: 异构信息网络嵌入(Heterogeneous information network, HIN)以将其投射到低维空间为目标,已经引起了相当多的研究关注。现有的HIN嵌入方法主要是在欧几里得空间中保留内部网络结构和语义相关性。然而,一个基本的问题是欧几里得空间是否是HIN的合适的或内在的等距空间?。近年来的研究认为,复杂网络的底层可能具有双曲几何,因为底层的双曲几何可以自然地反映复杂网络的一些特性,如层次结构和幂律结构。在本文中,我们首次尝试将HIN嵌入到双曲空间中。我们分析了两个实际HIN的结构,发现HIN中也存在幂律分布等性质。为此,我们提出了一种新的双曲异构信息网络嵌入模型。具体地说,为了捕获节点之间的结构和语义关系,我们采用元路径引导随机游走对每个节点的序列进行采样。然后利用双曲空间中的距离作为近似度量。双曲距离能满足三角不等式,并能很好地保持HIN中的传递性。我们的模型使节点及其邻域具有小的双曲线距离。进一步推导出有效的优化策略,迭代更新双曲嵌入。实验结果表明,该模型不仅在网络重构和链路预测任务上具有优越的性能,而且在HIN中通过可视化显示了捕获层次结构的能力。

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

题目: Graph Random Neural Networks

摘要:

图神经网络(GNNs)将深度学习方法推广到图结构数据中,在图形挖掘任务中表现良好。然而,现有的GNN常常遇到具有标记节点的复杂图结构,并受到非鲁棒性、过度平滑和过拟合的限制。为了解决这些问题,本文提出了一个简单而有效的GNN框架——图随机神经网络(Grand)。与现有GNNs中的确定性传播不同,Grand采用随机传播策略来增强模型的鲁棒性。这种策略也很自然地使Grand能够将传播从特征转换中分离出来,减少了过度平滑和过度拟合的风险。此外,随机传播是图数据扩充的一种有效方法。在此基础上,利用无标记节点在多个扩展中的分布一致性,提高模型的泛化能力,提出了Grand的一致性正则化方法。在图形基准数据集上的大量实验表明,Grand在半监督的图形学习任务上显著优于最先进的GNN基线。最后,证明了它可以显著减轻过度平滑和过度拟合的问题,并且它的性能与鲁棒性相结合。

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

图神经网络(GNNs)是一种强大的图表示学习工具。然而,最近的研究表明,GNN很容易受到精心设计的干扰,即所谓的对抗攻击。对抗攻击可以很容易地愚弄GNN,使其无法预测后续任务。在对安全性要求很高的应用程序中应用GNN的脆弱性引起了越来越多的关注。因此,开发对抗攻击的鲁棒算法具有重要意义。为对抗攻击辩护的一个自然的想法是清理受干扰的图。很明显,真实世界的图具有一些内在的特性。例如,许多真实世界的图是低秩和稀疏的,并且两个相邻节点的特征趋于相似。事实上,我们发现,对抗攻击很可能会破坏这些图的属性。因此,在本文中,我们探讨这些性质,以防御图的对抗性攻击。特别地,我们提出了一个通用的框架Pro-GNN,它可以联合学习结构图和鲁棒图神经网络模型从摄动图的这些属性指导。在真实图上的大量实验表明,与最先进的防御方法相比,即使在图受到严重干扰的情况下,所提出的框架也能获得更好的性能。我们将Pro-GNN的实现发布到我们的DeepRobust存储库,用于对抗攻击和防御

https://github.com/DSE-MSU/DeepRobust。

复现我们的结果的具体实验设置可以在

https://github.com/ChandlerBang/Pro-GNN

概述

图是在许多领域中普遍存在的数据结构,例如化学(分子)、金融(交易网络)和社交媒体(Facebook朋友网络)。随着它们的流行,学习有效的图表示并将其应用于解决后续任务尤为重要。近年来,图神经网络(Graph Neural Networks, GNNs)在图表示学习取得了巨大的成功(Li et al., 2015;Hamilton,2017;Kipf and Welling, 2016a;Veličkovićet al ., 2018)。GNNs遵循消息传递方案(Gilmer et al., 2017),其中节点嵌入是通过聚合和转换其邻居的嵌入来获得的。由于其良好的性能,GNNs已经应用于各种分析任务,包括节点分类(Kipf和Welling, 2016a)、链接预测(Kipf和Welling, 2016b)和推荐系统(Ying et al., 2018)。

虽然已经取得了令人鼓舞的结果,但最近的研究表明,GNNs易受攻击(Jin et al., 2020;Zugner et al., 2018;Zugner Gunnemann, 2019;Dai et al., 2018;吴等,2019b)。换句话说,在图中不明显的扰动下,GNNs的性能会大大降低。这些模型缺乏健壮性,可能会对与安全和隐私相关的关键应用造成严重后果。例如,在信用卡欺诈检测中,诈骗者可以创建多个交易,只有少数高信用用户可以伪装自己,从而逃避基于GNNs的检测。因此,开发抗攻击的稳健的GNN模型具有重要意义。修改图数据可以扰乱节点特征或图结构。然而,由于结构信息的复杂性,现有的对图数据的攻击主要集中在修改图数据结构,特别是添加/删除/重连边(Xu et al., 2019)。因此,在这项工作中,我们的目标是抵御对图数据的最常见的攻击设置,即,对图结构的毒杀攻击。在这种情况下,图结构在训练GNNs之前已经修改了边,而节点特征没有改变,这已经扰乱了图结构。

设计有效防御算法的一个视角是对扰动图进行清理,如删除反向边和恢复被删除边(Zhu et al., 2019;Tang et al., 2019)。从这个角度来看,关键的挑战是我们应该遵循什么标准来清除扰动图。众所周知,真实世界的图通常具有某些特性。首先,许多真实世界的干净图是低秩和稀疏的(Zhou et al., 2013)。例如,在社交网络中,大多数个体只与少数邻居连接,影响用户之间连接的因素很少(Zhou et al., 2013; Fortunato, 2010)。其次,干净图中连接的节点可能具有相似的特征或属性(或特征平滑度)(McPherson et al., 2001)。例如,在一个引文网络中,两个相连的出版物经常共享相似的主题(Kipf Welling, 2016a)。图1演示了干净和中毒图的这些属性。具体来说,我们用了最先进的图数据中毒攻击metattack (Zugner和Gunnemann, 2019a)来扰乱图数据,并在mettack之前和之后可视化图的属性。如图(a)a所示,metattack扩大了邻接矩阵的奇异值,图(b)b说明metattack可以快速地增加邻接矩阵的秩。此外,当我们分别从摄动图中删除对抗性边和法线时,我们观察到删除对抗性边比删除法线更快地降低了秩,如图(c)c所示。另外,我们在图(d)d中描述了攻击图的连通节点特征差异的密度分布。可以看出,metattack倾向于连接特征差异较大的节点。图1的观察结果表明,对抗性攻击可能破坏这些属性。因此,这些性质有可能作为清除摄动图的指导。然而,利用这些性质来建立鲁棒图神经网络的研究还很有限。

本文旨在探讨图的稀疏性、低秩性和特征平滑性,设计鲁棒的图神经网络。请注意,还有更多的属性有待探索,我们希望将其作为未来的工作。从本质上讲,我们面临着两个挑战:(1)如何在这些属性的引导下,从中毒的图数据中学习干净的图结构;(二)如何将鲁棒图神经网络的参数与净结构联合学习。为了解决这两个问题,我们提出了一个通用的框架属性GNN (Pro-GNN)来同时从摄动图和GNN参数中学习干净的图结构,以抵御对抗攻击。在各种真实世界图形上的大量实验表明,我们提出的模型能够有效地防御不同类型的对抗攻击,并优于最先进的防御方法。

对抗性攻击会对图数据产生精心设计的扰动。我们把精心设计的扰动称为对抗性结构。对抗结构会导致GNNs的性能急剧下降。因此,为了防御竞争攻击,一种自然的策略是消除精心设计的竞争结构,同时保持固有的图结构。在本工作中,我们的目标是通过探索低秩、稀疏性和特征平滑性的图结构特性来实现这一目标。该框架的示意图如图2所示,其中黑色的边为普通边,红色的边为攻击者为降低节点分类性能而引入的对抗性边。为了抵御攻击,Pro-GNN通过保持图的低秩性、稀疏性和特征平滑性,迭代地重构干净图,以减少对抗结构的负面影响。同时,为了保证重构图能够帮助节点分类,Pro-GNN通过求解交替模式下的优化问题,同时更新重构图上的GNN参数。

图神经网络很容易被图对抗攻击所欺骗。为了防御不同类型的图对抗攻击,我们引入了一种新的防御方法Pro-GNN,该方法同时学习图结构和GNN参数。我们的实验表明,我们的模型始终优于最先进的基线,并提高了在各种对抗攻击下的整体鲁棒性。在未来,我们的目标是探索更多的属性,以进一步提高GNNs的鲁棒性。

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

Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success, but GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels. In this work, we consider the task of inductive node classification using GNNs in supervised and semi-supervised settings, with the goal of incorporating label dependencies. Because current GNNs are not universal (i.e., most-expressive) graph representations, we propose a general collective learning approach to increase the representation power of any existing GNN. Our framework combines ideas from collective classification with self-supervised learning, and uses a Monte Carlo approach to sampling embeddings for inductive learning across graphs. We evaluate performance on five real-world network datasets and demonstrate consistent, significant improvement in node classification accuracy, for a variety of state-of-the-art GNNs.

0
19
下载
预览

这也是一篇满分的工作。是由常年战斗在图领域的大佬 Pablo Barceló 团队贡献的。图神经网络(GNN)区分图节点的能力最近已经通过用于检查图同构性的 Weisfeiler-Lehman(WL)测试进行了表征。但是,这种表征并不能解决哪些布尔节点分类器可以由 GNN 来表示 (即,将图中的节点分类为真或假的函数)的问题。这篇文章专注于研究布尔分类器来解决上述问题。首先研究的是流行的GNNs(文中称为 AC-GNNs)开始,在该类 GNN 中仅根据邻居的特征,在连续的层中更新图中每个节点的特征。实验表明,这类 GNN 太弱而无法捕获所有 FOC2(一种一阶逻辑研究) 分类器,并提供了 AC-GNNs 可以捕获的 FOC2 分类器最大子类的语法表征。然后,研究人员研究了,需要在 AC-GNNs 中添加什么来实现捕获所有的 FOC2 分类器,实验表明,添加 readout 就可以了。不仅可以更新节点的邻居,还可以更新全局属性向量。文章称这类 GNNs 为 ACR-GNNs。

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

图神经网络是解决各种图学习问题的有效的机器学习模型。尽管它们取得了经验上的成功,但是GNNs的理论局限性最近已经被揭示出来。因此,人们提出了许多GNN模型来克服这些限制。在这次调查中,我们全面概述了GNNs的表达能力和可证明的强大的GNNs变体。

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

摘要 近年来,使用结构化数据建模的图神经网络(GNNs)取得了巨大的成功。然而,大多数的GNN都是针对同构图设计的,在同构图中,所有的节点和边都属于同一种类型,使得它们无法表示异构结构。在这篇论文中,我们提出了一种异构图 Transformer(HGT)结构来对web级的异构图进行建模。为了对异构性进行建模,我们设计了节点类型和边类型的相关参数来描述每个边上的异构注意力程度,从而使HGT能够维护不同类型节点和边的特定表示。为了处理动态异构图,我们在HGT中引入了相对时间编码技术,该技术能够捕获具有任意持续时间的动态结构依赖关系。针对网络规模图数据的处理问题,设计了高效、可扩展的小批量图数据采样算法HGSampling。在拥有1.79亿个节点和20亿个边的开放学术图上进行的大量实验表明,所提出的HGT模型在各种下游任务上的性能始终比所有最先进的GNN基线高9-21%。

关键词:图神经网络;异构信息网络;表示学习;图嵌入;图注意力

介绍

异构图通常对复杂的系统进行抽象和建模,其中不同类型的对象以各种方式相互交互。此类系统的一些常见实例包括学术图、Facebook实体图、LinkedIn经济图,以及广泛的物联网网络。例如,图1中的开放学术图(OAG)[28]包含五种类型的节点:论文、作者、机构、场所(期刊、会议或预印本)和字段,以及它们之间不同类型的关系。

在过去的十年中,人们对异构图[17]的挖掘进行了大量的研究。其中一个经典的范例就是定义和使用元路径来对异类结构进行建模,例如PathSim[18]和变元ath2vec[3]。最近,鉴于图神经网络(GNNs)的成功[7,9,22],[14,23,26,27]尝试采用GNNs来学习异构网络。然而,这些工作面临着几个问题:首先,它们大多涉及到为每种类型的异构图设计元路径,这需要特定的领域知识;其次,它们要么简单地假设不同类型的节点/边共享相同的特征和表示空间,要么为节点类型或单独的边类型保留不同的非共享权值,使它们不足以捕获异类图的属性;三是大多忽略了每一个(异构)图的动态性;最后,它们固有的设计和实现使得它们无法对web规模的异构图进行建模。

以OAG为例:首先,OAG中的节点和边可能具有不同的特征分布,如论文具有文本特征,而机构可能具有来自附属学者的特征,共同作者明显不同于引文链接;OAG一直在不断发展,例如:1)出版物的数量每12年翻一倍[4];2)KDD会议在1990年代更多地与数据库相关,而近年来更多地与机器学习相关;最后,OAG包含数亿个节点和数十亿个关系,使得现有的异构GNN无法扩展来处理它。

针对这些限制和挑战,我们建议研究异构图神经网络,其目标是维护节点和边类型依赖表示、捕获网络动态、避免自定义元路径和可扩展到web级图。在这项工作中,我们提出了异构图 Transformer(HGT)架构来处理所有这些问题。

为了处理图的异构性,我们引入了节点类型和边类型依赖注意力机制。HGT中的相互注意不是对每一个类型边参数化,而是根据其元关系三元组e=(s,t),即 s为节点类型,s与t之间的e的边类型,t的节点类型。图1展示了异构学术图的元关系。具体来说,我们使用这些元关系来对权重矩阵参数化,以计算每条边上的注意力。因此,允许不同类型的节点和边维护其特定的表示空间。同时,不同类型的连接节点仍然可以交互、传递和聚合消息,而不受其分布差异的限制。由于其架构的性质,HGT可以通过跨层传递消息来整合来自不同类型的高阶邻居的信息,这可以看作是软元路径。也就是说,即使HGT只将其单跳边作为输入,而不需要手动设计元路径,所提出的注意力机制也可以自动、隐式地学习和提取对不同下游任务重要的元路径。

为了处理图数据的动态特性,我们提出了相对时间编码(RTE)策略来增强HGT。我们不打算将输入图分割成不同的时间戳,而是建议将发生在不同时间的所有边作为一个整体进行维护,并设计RTE策略来对任何持续时间长度的结构性时间依赖关系进行建模,甚至包括不可见的和未来的时间戳。通过端到端训练,RTE使HGT能够自动学习异构图的时间依赖性和演化。

为了处理网络规模的图形数据,我们设计了第一个用于小批量GNN训练的异构子图采样算法HGSampling。它的主要思想是样本异构子图中不同类型的节点与类似的比例,由于直接使用现有的(均匀)GNN抽样方法,如GraphSage [7], FastGCN[1],和LADIES[29],结果在高度不平衡的关于节点和边缘的类型。此外,它还被设计成保持采样子图的密度以最小化信息的丢失。通过HGSampling,所有的GNN模型,包括我们提出的HGT,都可以在任意大小的异构图上进行训练和推断。

我们证明了所提出的异构图Transformer在网络规模开放学术图上的有效性和效率,该开放学术图由1.79亿个节点和20亿个边组成,时间跨度从1900年到2019年,这是迄今为止在异构图上进行的规模最大、跨度最长的表示学习。此外,我们还检查领域特定的图表:计算机科学和医学学术图表。实验结果表明,与最先进的GNNs和专用的异构模型相比,在下游任务中HGT可以显著提高9-21%。我们进一步进行了案例研究,表明了所提出的方法确实能够自动捕获不同任务的隐式元路径的重要性。

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

题目: Logical Expressiveness of Graph Neural Networks

摘要:

图神经网络(Graph Neural Networks, GNNs)是近年来在分子分类、知识图谱补全等结构化数据处理领域中流行起来的一类机器学习体系结构。最近关于GNNs表达能力的研究已经建立了它们对图中节点进行分类的能力与用于检查图同构的WeisfeilerLehman (WL)测试之间的紧密联系。具体来说,这两篇论文的作者分别观察到,WL测试产生的节点分类总是细化了任何GNN产生的分类,而且有GNN可以重现WL测试。这些结果表明,GNNs在节点分类方面与WL测试一样强大。然而,这并不意味着GNNs可以表达任何通过WL测试改进的分类器。我们的工作旨在回答以下问题:什么是可以用GNNs捕获的节点分类器?在本文中,我们从逻辑的角度来看待这个问题,将其限制在FOC2中可表达的属性上,即具有计数能力的一阶逻辑的两变量片段进行研究。

作者:

Pablo Barceló是智利天主教大学工程学院和数学学院数学与计算工程研究所所长,研究领域为数据库理论、计算机科学中的逻辑、自动机理论。

成为VIP会员查看完整内容
0
32
小贴士
相关论文
Suyu Ge,Chuhan Wu,Fangzhao Wu,Tao Qi,Yongfeng Huang
20+阅读 · 2020年3月31日
A Collective Learning Framework to Boost GNN Expressiveness
Mengyue Hang,Jennifer Neville,Bruno Ribeiro
19+阅读 · 2020年3月26日
Hongwei Wang,Jure Leskovec
28+阅读 · 2020年2月17日
Xinyu Fu,Jiani Zhang,Ziqiao Meng,Irwin King
41+阅读 · 2020年2月5日
Saurabh Verma,Zhi-Li Zhang
4+阅读 · 2019年9月25日
Junlang Zhan,Hai Zhao
3+阅读 · 2019年3月1日
Deep Node Ranking: an Algorithm for Structural Network Embedding and End-to-End Classification
Blaž Škrlj,Jan Kralj,Janez Konc,Marko Robnik-Šikonja,Nada Lavrač
4+阅读 · 2019年2月11日
Yanbin Liu,Juho Lee,Minseop Park,Saehoon Kim,Eunho Yang,Sungju Hwang,Yi Yang
20+阅读 · 2018年12月25日
Meta-Learning with Latent Embedding Optimization
Andrei A. Rusu,Dushyant Rao,Jakub Sygnowski,Oriol Vinyals,Razvan Pascanu,Simon Osindero,Raia Hadsell
6+阅读 · 2018年7月16日
Junliang Guo,Linli Xu,Xunpeng Huang,Enhong Chen
3+阅读 · 2018年3月5日
Top
微信扫码咨询专知VIP会员