八篇NeurIPS 2019最新公布的【图神经网络(GNN)】相关论文

2019 年 9 月 10 日 专知
八篇NeurIPS 2019最新公布的【图神经网络(GNN)】相关论文

【导读】最近,人工智能和机器学习领域的国际顶级会议NeurIPS 2019接收论文公布,共有1428篇论文被接收。为了带大家抢先领略高质量论文,专知小编特意整理了八篇NeurIPS 2019最新GNN相关论文,并附上arXiv论文链接供参考。


IJCAI2019GNN_Part1IJCAI2019GNN_Part2、 KDD2019GNNACL2019GNNCVPR2019GNN ICML2019GNN


1. Approximation Ratios of Graph Neural Networks for Combinatorial Problems

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

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

网址:

https://arxiv.org/abs/1905.10261

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://arxiv.org/abs/1904.11088

3. End to end learning and optimization on graphs

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

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

网址:

https://arxiv.org/abs/1905.13732

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://arxiv.org/abs/1905.13192

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://arxiv.org/abs/1809.02589

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://arxiv.org/abs/1907.03395

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://arxiv.org/abs/1905.07645


8. Universal Invariant and Equivariant Graph Neural Networks

作者:Nicolas Keriven, Gabriel Peyré;

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

网址:

https://arxiv.org/abs/1905.04943

-END-
专 · 知


专知,专业可信的人工智能知识分发,让认知协作更快更好!欢迎登录www.zhuanzhi.ai,注册登录专知,获取更多AI知识资料!
欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程视频资料和与专家交流咨询
请加专知小助手微信(扫一扫如下二维码添加),加入专知人工智能主题群,咨询技术商务合作~
专知《深度学习:算法到实战》课程全部完成!560+位同学在学习,现在报名,限时优惠!网易云课堂人工智能畅销榜首位!
点击“阅读原文”,了解报名专知《深度学习:算法到实战》
登录查看更多
74

相关内容

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

知识荟萃

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

更多

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

【导读】作为世界数据挖掘领域的最高级别的学术会议,ACM SIGKDD(国际数据挖掘与知识发现大会,简称 KDD)每年都会吸引全球领域众多专业人士参与。今年的 KDD大会计划将于 2020 年 8 月 23 日 ~27 日在美国美国加利福尼亚州圣地亚哥举行。上周,KDD 2020官方发布接收论文,共有1279篇论文提交到Research Track,共216篇被接收,接收率16.8%。近期KDD官网公布了接受论文列表,为此,上个月专知小编为大家整理了图神经网络相关的论文,这期小编继续为大家奉上KDD 2020必读的五篇图神经网络(GNN)相关论文-Part 2——多层次GCN、无监督预训练GCN、图Hash、GCN主题模型、采样

KDD 2020 Accepted Paper: https://www.kdd.org/kdd2020/accepted-papers

KDD2020GNN_Part1、CVPR2020SGNN、CVPR2020GNN_Part2、CVPR2020GNN_Part1、WWW2020GNN_Part1、AAAI2020GNN、ACMMM2019GNN、CIKM2019GNN、ICLR2020GNN、EMNLP2019GNN、ICCV2019GNN_Part2、ICCV2019GNN_Part1、NIPS2019GNN、IJCAI2019GNN_Part1、IJCAI2019GNN_Part2、KDD2019GNN、

1. Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction

作者:Hongxu Chen, Hongzhi Yin, Xiangguo Sun, Tong Chen, Bogdan Gabrys, Katarzyna Musial

摘要:跨平台的账号匹配在社交网络分析中发挥着重要作用,并且有利于广泛的应用。然而,现有的方法要么严重依赖于高质量的用户生成内容(包括用户兴趣模型),要么只关注网络拓扑结构,存在数据不足的问题,这使得研究这个方向变得很困难。为了解决这一问题,我们提出了一种新的框架,该框架统一考虑了局部网络结构和超图结构上的多级图卷积。该方法克服了现有工作中数据不足的问题,并且不一定依赖于用户的人口统计信息。此外,为了使所提出的方法能够处理大规模社交网络,我们提出了一种两阶段的空间协调机制,在基于网络分区的并行训练和跨不同社交网络的帐户匹配中对齐嵌入空间。我们在两个大规模的真实社交网络上进行了广泛的实验。实验结果表明,该方法的性能比现有的模型有较大幅度的提高。

网址:

https://arxiv.org/abs/2006.01963

2. GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training

作者:Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, Jie Tang

摘要:图表示学习已经成为解决现实问题的一种强有力的技术。包括节点分类、相似性搜索、图分类和链接预测在内的各种下游图学习任务都受益于它的最新发展。然而,关于图表示学习的现有技术集中于领域特定的问题,并为每个图训练专用模型,这通常不可转移到领域之外的数据。受自然语言处理和计算机视觉在预训练方面的最新进展的启发,我们设计了图对比编码(Graph Contrastive Coding,GCC)一个无监督的图表示学习框架来捕捉跨多个网络的通用网络拓扑属性。我们将GCC的预训练任务设计为网络内部和网络之间的子图级别的实例判断,并利用对比学习来增强模型学习内在的和可迁移的结构表征能力。我们在三个图学习任务和十个图数据集上进行了广泛的实验。结果表明,GCC在一组不同的数据集上进行预训练,可以获得与从头开始的特定任务训练的方法相媲美或更好的性能。这表明,预训练和微调范式对图表示学习具有巨大的潜力。

网址:

https://arxiv.org/abs/2006.09963

代码链接:

https://github.com/THUDM/GCC

3. GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases

作者:Zongyue Qin, Yunsheng Bai, Yizhou Sun

摘要:图相似搜索的目的是根据给定的邻近度,即图编辑距离(GED),在图形数据库中找到与查询最相似的图。这是一个被广泛研究但仍具有挑战性的问题。大多数研究都是基于剪枝验证框架,该框架首先对非看好的图进行剪枝,然后在较小的候选集上进行验证。现有的方法能够管理具有数千或数万个图的数据库,但由于其精确的剪枝策略,无法扩展到更大的数据库。受到最近基于深度学习的语义哈希(semantic hashing)在图像和文档检索中的成功应用的启发,我们提出了一种新的基于图神经网络(GNN)的语义哈希,即GHash,用于近似剪枝。我们首先用真实的GED结果训练GNN,以便它学习生成嵌入和哈希码,以保持图之间的GED。然后建立哈希索引以实现恒定时间内的图查找。在回答一个查询时,我们使用哈希码和连续嵌入作为两级剪枝来检索最有希望的候选对象,并将这些候选对象发送到精确的求解器进行最终验证。由于我们的图哈希技术利用了近似剪枝策略,与现有方法相比,我们的方法在保持高召回率的同时,实现了显著更快的查询时间。实验表明,该方法的平均速度是目前唯一适用于百万级数据库的基线算法的20倍,这表明GHash算法成功地为解决大规模图形数据库的图搜索问题提供了新的方向。

网址:

http://web.cs.ucla.edu/~yzsun/papers/2020_KDD_GHashing.pdf

4. Graph Structural-topic Neural Network

作者:Qingqing Long, Yilun Jin, Guojie Song, Yi Li, Wei Lin

摘要:图卷积网络(GCNS)通过有效地收集节点的局部特征,取得了巨大的成功。然而,GCNS通常更多地关注节点特征,而较少关注邻域内的图结构,特别是高阶结构模式。然而,这种局部结构模式被显示为许多领域中的节点属性。此外,由于网络很复杂,每个节点的邻域由各种节点和结构模式的混合组成,不只是单个模式,所有这些模式上的分布都很重要。相应地,在本文中,我们提出了图结构主题神经网络,简称GraphSTONE,这是一种利用图的主题模型的GCN模型,使得结构主题广泛地从概率的角度捕捉指示性的图结构,而不仅仅是几个结构。具体地说,我们使用 anonymous walks和Graph Anchor LDA(一种LDA的变体,首先选择重要的结构模式)在图上建立主题模型,以降低复杂性并高效地生成结构主题。此外,我们设计了多视图GCNS来统一节点特征和结构主题特征,并利用结构主题来指导聚合。我们通过定量和定性实验对我们的模型进行了评估,我们的模型表现出良好的性能、高效率和清晰的可解释性。

网址:

https://arxiv.org/abs/2006.14278

代码链接:

https://github.com/YimiAChack/GraphSTONE/

5. Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks

作者:Weilin Cong, Rana Forsati, Mahmut Kandemir, Mehrdad Mahdavi

摘要:抽样方法(如节点抽样、分层抽样或子图抽样)已成为加速大规模图神经网络(GNNs)训练不可缺少的策略。然而,现有的抽样方法大多基于图的结构信息,忽略了最优化的动态性,导致随机梯度估计的方差较大。高方差问题在非常大的图中可能非常明显,它会导致收敛速度慢和泛化能力差。本文从理论上分析了抽样方法的方差,指出由于经验风险的复合结构,任何抽样方法的方差都可以分解为前向阶段的嵌入近似方差和后向阶段的随机梯度方差,这两种方差都必须减小,才能获得较快的收敛速度。我们提出了一种解耦的方差减小策略,利用(近似)梯度信息自适应地对方差最小的节点进行采样,并显式地减小了嵌入近似引入的方差。理论和实验表明,与现有方法相比,该方法即使在小批量情况下也具有更快的收敛速度和更好的泛化能力。

网址:

https://arxiv.org/abs/2006.13866

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

【导读】ICML(International Conference on Machine Learning),即国际机器学习大会, 是机器学习领域全球最具影响力的学术会议之一,因此在该会议上发表论文的研究者也会备受关注。因疫情的影响, 今年第37届ICML大会将于2020年7月13日至18日在线上举行。据官方统计,ICML 2020共提交4990篇论文,接收论文1088篇,接收率为21.8%。与往年相比,接收率逐年走低。在会议开始前夕,专知小编为大家整理了ICML 2020图神经网络(GNN)的六篇相关论文供参考——核GNN、特征变换、Haar 图池化、无监督图表示、谱聚类、自监督GCN。

ICML 2020 Accepted Papers https://icml.cc/Conferences/2020/AcceptedPapersInitial

ACL2020GNN_Part1、WWW2020GNN_Part1、AAAI2020GNN、ACMMM2019GNN、CIKM2019GNN、ICLR2020GNN

1. Convolutional Kernel Networks for Graph-Structured Data

作者:Dexiong Chen, Laurent Jacob, Julien Mairal

摘要:我们引入了一系列多层图核,并在图卷积神经网络和核方法之间建立了新的联系。我们的方法通过将图表示为核特征映射序列将卷积核网络推广到图结构数据,其中每个节点携带关于局部图子结构的信息。一方面,核的观点提供了一种无监督的、有表现力的、易于正规化的数据表示,这在样本有限的情况下很有用。另一方面,我们的模型也可以在大规模数据上进行端到端的训练,从而产生了新型的图卷积神经网络。我们的方法在几个图分类基准上取得了与之相当的性能,同时提供了简单的模型解释。

网址: https://arxiv.org/abs/2003.05189

代码链接: https://github.com/claying/GCKN

2. GNN-FILM: Graph Neural Networks with Feature-Wise Linear Modulation 作者:Marc Brockschmidt

摘要:本文提出了一种新的基于特征线性调制(feature-wise linear modulation,FiLM)的图神经网络(GNN)。许多标准GNN变体仅通过每条边的源的表示来计算“信息”,从而沿着图的边传播信息。在GNN-FILE中,边的目标节点的表示被附加地用于计算可以应用于所有传入信息的变换,从而允许对传递的信息进行基于特征的调制。基于基线方法的重新实现,本文给出了在文献中提到的三个任务上的不同GNN体系结构的实验结果。所有方法的超参数都是通过广泛的搜索找到的,产生了一些令人惊讶的结果:基线模型之间的差异比文献报道的要小。尽管如此,GNN-FILE在分子图的回归任务上的表现优于基线方法,在其他任务上的表现也具有竞争性。

网址: https://arxiv.org/abs/1906.12192

3. Haar Graph Pooling

作者:Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, Yanan Fan

摘要:深度图神经网络(GNNs)是用于图分类和基于图的回归任务的有效模型。在这些任务中,图池化是GNN适应不同大小和结构的输入图的关键因素。本文提出了一种新的基于压缩Haar变换的图池化操作-HaarPooling。HaarPooling实现了一系列池化操作;它是通过跟随输入图的一系列聚类序列来计算的。HaarPooling层将给定的输入图变换为节点数较小、特征维数相同的输出图;压缩Haar变换在Haar小波域中过滤出细节信息。通过这种方式,所有HaarPooling层一起将任何给定输入图的特征合成为大小一致的特征向量。这种变换提供了数据的稀疏表征,并保留了输入图的结构信息。使用标准图卷积层和HaarPooling层实现的GNN在各种图分类和回归问题上实现了最先进的性能。

网址: https://arxiv.org/abs/1909.11580

4. Interferometric Graph Transform: a Deep Unsupervised Graph Representation 作者:Edouard Oyallon

摘要:我们提出了Interferometric Graph Transform(IGT),这是一类用于构建图表示的新型深度无监督图卷积神经网络。我们的第一个贡献是提出了一种从欧几里德傅立叶变换的推广得到的通用复数谱图结构。基于一个新颖的贪婪凹目标,我们的学习表示既包括可区分的特征,也包括不变的特征。通过实验可以得到,我们的学习过程利用了谱域的拓扑,这通常是谱方法的一个缺陷,特别是我们的方法可以恢复视觉任务的解析算子。我们在各种具有挑战性的任务上测试了我们的算法,例如图像分类(MNIST,CIFAR-10)、社区检测(Authorship,Facebook graph)和3D骨架视频中的动作识别(SBU,NTU),在谱图非监督环境下展示了一种新的技术水平。

网址:

https://arxiv.org/abs/2006.05722

5. Spectral Clustering with Graph Neural Networks for Graph Pooling

作者:Filippo Maria Bianchi, Daniele Grattarola, Cesare Alippi

摘要:谱聚类(SC)是发现图上强连通社区的一种流行的聚类技术。SC可以在图神经网络(GNN)中使用,以实现聚合属于同一簇的节点的池化操作。然而,Laplacian的特征分解代价很高,而且由于聚类结果是特定于图的,因此基于SC的池化方法必须对每个新样本执行新的优化。在本文中,我们提出了一种图聚类方法来解决SC的这些局限性。我们建立了归一化minCUT问题的连续松弛公式,并训练GNN来计算最小化这一目标的簇分配。我们的基于GNN的实现是可微的,不需要计算谱分解,并且学习了一个聚类函数,可以在样本外的图上快速评估。从提出的聚类方法出发,我们设计了一个图池化算子,它克服了现有图池化技术的一些重要局限性,并在多个监督和非监督任务中取得了最好的性能。

网址: https://arxiv.org/abs/1907.00481

6. When Does Self-Supervision Help Graph Convolutional Networks?

作者:Yuning You, Tianlong Chen, Zhangyang Wang, Yang Shen

摘要:自监督作为一种新兴的技术已被用于训练卷积神经网络(CNNs),以提高图像表示学习的可传递性、泛化能力和鲁棒性。然而,自监督对操作图形数据的图卷积网络(GCNS)的介绍却很少被探索。在这项研究中,我们首次将自监督纳入GCNS的系统探索和评估。我们首先阐述了将自监督纳入GCNS的三种机制,分析了预训练&精调和自训练的局限性,并进而将重点放在多任务学习上。此外,我们还提出了三种新的GCNS自监督学习任务,并进行了理论分析和数值比较。最后,我们进一步将多任务自监督融入到图对抗性训练中。研究结果表明,通过合理设计任务形式和合并机制,自监督有利于GCNS获得更强的泛化能力和鲁棒性。

网址: https://arxiv.org/abs/2006.09136

代码链接: https://github.com/Shen-Lab/SS-GCNs

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

【导读】计算语言学协会(the Association for Computational Linguistics, ACL)年度会议作为顶级的国际会议,在计算语言学和自然语言处理领域一直备受关注。其接收的论文覆盖了语义分析、文本挖掘、信息抽取、问答系统、机器翻译、情感分析和意见挖掘等众多自然语言处理领域的研究方向。今年,第58届计算语言学协会(the Association for Computational Linguistics, ACL)年度会议将于2020年7月5日至10日在美国华盛顿西雅图举行。受COVID-19疫情影响,ACL 2020将全部改为线上举行。本次ACL大会共提交了3429篇论文,共有571篇长论文、以及208篇短论文入选。不久之前,专知小编为大家整理了大会的图神经网络(GNN)相关论文,这期小编继续为大家奉上ACL 2020图神经网络(GNN)相关论文-Part 2供参考——多文档摘要、多粒度机器阅读理解、帖子争议检测、GAE。

ACL2020GNN_Part1、WWW2020GNN_Part1、AAAI2020GNN、ACMMM2019GNN、CIKM2019GNN、ICLR2020GNN

1. Leveraging Graph to Improve Abstractive Multi-Document Summarization

作者:Wei Li, Xinyan Xiao, Jiachen Liu, Hua Wu, Haifeng Wang, Junping Du

摘要:捕捉文本单元之间关系图对于从多个文档中检测显著信息和生成整体连贯的摘要有很大好处。本文提出了一种神经抽取多文档摘要(MDS)模型,该模型可以利用文档的常见图表示,如相似度图和话语图(discourse graph),来更有效地处理多个输入文档并生成摘要。我们的模型使用图对文档进行编码,以捕获跨文档关系,这对于总结长文档至关重要。我们的模型还可以利用图来指导摘要的生成过程,这有利于生成连贯而简洁的摘要。此外,预训练的语言模型可以很容易地与我们的模型相结合,进一步提高了摘要的性能。在WikiSum和MultiNews数据集上的实验结果表明,所提出的体系结构在几个强大的基线上带来了实质性的改进。

网址: https://arxiv.org/abs/2005.10043

2. Document Modeling with Graph Attention Networks for Multi-grained Machine Reading Comprehension

作者:Bo Zheng, Haoyang Wen, Yaobo Liang, Nan Duan, Wanxiang Che, Daxin Jiang, Ming Zhou, Ting Liu

摘要:“自然问题”是一种具有挑战性的新的机器阅读理解基准,其中包含两个答案:长答案(通常是一个段落)和短答案(长答案中的一个或多个实体)。尽管此基准测试的现有方法很有效,但它们在训练期间单独处理这两个子任务,忽略了它们间的依赖关系。为了解决这个问题,我们提出了一种新颖的多粒度机器阅读理解框架,该框架专注于对文档的分层性质进行建模,这些文档具有不同的粒度级别:文档、段落、句子和词。我们利用图注意力网络来获得不同层次的表示,以便它们可以同时学习。长答案和短答案可以分别从段落级表示和词级表示中提取。通过这种方式,我们可以对两个粒度的答案之间的依赖关系进行建模,以便为彼此提供证据。我们联合训练这两个子任务,实验表明,我们的方法在长答案和短答案标准上都明显优于以前的系统。

网址: https://arxiv.org/abs/2005.05806

代码链接:

https://github.com/DancingSoul/NQ_BERT-DM

3. Integrating Semantic and Structural Information with Graph Convolutional Network for Controversy Detection

作者:Lei Zhong, Juan Cao, Qiang Sheng, Junbo Guo, Ziang Wang

摘要:识别社交媒体上有争议的帖子是挖掘公众情绪、评估事件影响、缓解两极分化观点的基础任务。然而,现有的方法不能1)有效地融合来自相关帖子内容的语义信息;2)保留回复关系建模的结构信息;3)正确处理与训练集中主题不同的帖子。为了克服前两个局限性,我们提出了主题-帖子-评论图卷积网络(TPC-GCN),它综合了来自主题、帖子和评论的图结构和内容的信息,用于帖子级别的争议检测。对于第三个限制,我们将模型扩展到分离的TPC-GCN(DTPC-GCN),将主题相关和主题无关的特征分离出来,然后进行动态融合。在两个真实数据集上的大量实验表明,我们的模型优于现有的方法。结果和实例分析表明,该模型能够将语义信息和结构信息有机地结合在一起,具有较强的通用性。

网址: https://arxiv.org/abs/2005.07886

4. Knowledge Graph-Augmented Abstractive Summarization with Semantic-Driven Cloze Reward

作者:Luyang Huang, Lingfei Wu, Lu Wang

摘要:用于抽取摘要的序列到序列(sequence-to-sequence )模型已经被广泛研究,但是生成的摘要通常受到捏造的内容的影响,并且经常被发现是near-extractive的。我们认为,为了解决这些问题,摘要生成器应通过输入获取语义解释,例如通过结构化表示,以允许生成更多信息的摘要。在本文中,我们提出了一种新的抽取摘要框架--Asgard,它具有图形增强和语义驱动的特点。我们建议使用双重编码器-序列文档编码器和图形结构编码器-来保持实体的全局上下文和局部特征,并且相互补充。我们进一步设计了基于多项选择完形填空测试的奖励,以驱动模型更好地捕捉实体交互。结果表明,我们的模型在纽约时报和CNN/每日邮报的数据集上都比没有知识图作为输入的变体产生了更高的Rouge分数。与从大型预训练的语言模型中优化的系统相比,我们也获得了更好或可比的性能。评委进一步认为我们的模型输出信息更丰富,包含的不实错误更少。

网址: https://arxiv.org/abs/2005.01159

5. A Graph Auto-encoder Model of Derivational Morphology

作者:Valentin Hofmann, Hinrich Schutze, Janet B. Pierrehumberty

摘要:关于派生词的形态良好性(morphological well-formedness, MWF)建模工作在语言学中被认为是一个复杂而困难的问题,并且这方面的研究工作较少。我们提出了一个图自编码器学习嵌入以捕捉派生词中词缀和词干的兼容性信息。自编码器通过将句法和语义信息与来自心理词典的关联信息相结合,很好地模拟了英语中的MWF。

网址: http://www.phon.ox.ac.uk/jpierrehumbert/publications/Hofmann_etal_DGA_ACL2020.pdf

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

1、MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing(MixHop: 通过稀疏邻域混合实现的高阶图卷积结构)

作者:Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, Aram Galstyan

摘要:现有的基于图神经网络的半监督学习方法(如图卷积网络)不能学习一般的邻域混合关系。为了解决这个缺点,我们提出了一个新的模型,MixHop,它可以通过在不同距离重复混合邻居的特征表示来学习这些关系,包括不同的操作符。MixHop不需要额外的内存或计算复杂度,并且在一些具有挑战性的baseline上性能更好。此外,我们建议使用稀疏正则化,使我们能够可视化网络如何跨不同的图数据集对邻居信息进行优先级排序。我们对所学体系结构的分析表明,每个数据集的邻域混合是不同的。

网址:http://proceedings.mlr.press/v97/abu-el-haija19a.html

代码链接: https://github.com/samihaija/mixhop

2、Compositional Fairness Constraints for Graph Embeddings(图嵌入的组合公平性约束)

作者:Avishek Bose, William Hamilton

摘要:学习高质量的节点嵌入是基于图数据(如社交网络和推荐系统)的机器学习模型的关键步骤。然而,现有的图嵌入技术无法处理公平约束,例如,确保所学习的表示与某些属性(如年龄或性别)不相关。在这里,我们引入一个对抗框架来对图嵌入实施公平性约束。我们的方法是组合的,这意味着它可以灵活地适应推理过程中公平约束的不同组合。例如,在社会推荐的上下文中,我们的框架允许一个用户要求他们的推荐对他们的年龄和性别都是不变的,同时也允许另一个用户只对他们的年龄要求不变。在标准知识图和推荐系统基准测试上的实验突出了我们提出的框架的实用性。

网址:http://proceedings.mlr.press/v97/bose19a.html

代码链接: https://github.com/joeybose/Flexible-Fairness-Constraints

3、Learning Discrete Structures for Graph Neural Networks(学习图神经网络的离散结构)

作者:Luca Franceschi, Mathias Niepert, Massimiliano Pontil, Xiao He

摘要:图神经网络(GNNs)是一种流行的机器学习模型,已成功地应用于一系列问题。它们的主要优势在于能够显式地合并数据点之间的稀疏和离散依赖结构。不幸的是,只有在这种图结构可用时才能使用GNN。然而,在实践中,真实世界中的图常常是嘈杂的、不完整的,或者根本就不可用。在此基础上,我们提出通过近似求解一个学习图边缘离散概率分布的双层程序来共同学习图卷积网络(GCNs)的图结构和参数。这不仅允许在给定图不完整或损坏的场景中应用GCNs,还允许在图不可用的场景中应用GCNs。我们进行了一系列的实验,分析了该方法的行为,并证明了它比相关的方法有显著的优势。

网址:http://proceedings.mlr.press/v97/franceschi19a.html

代码链接: https://github.com/lucfra/LDS

4、Graph U-Nets

作者:Hongyang Gao, Shuiwang Ji

摘要:我们研究了图数据的表示学习问题。卷积神经网络可以很自然地对图像进行操作,但在处理图数据方面存在很大的挑战。由于图像是二维网格上节点图的特殊情况,图的嵌入任务与图像的分割等像素级预测任务具有天然的对应关系。虽然像U-Nets这样的编解码器结构已经成功地应用于许多图像的像素级预测任务,但是类似的方法在图数据上还是很缺乏。这是由于池化操作和上采样操作对图数据不是自然的。为了解决这些挑战,我们提出了新的图池化(gPool)和反池化(gUnpool)操作。gPool层根据节点在可训练投影向量上的标量投影值,自适应地选择节点,形成较小的图。我们进一步提出了gUnpool层作为gPool层的逆操作。gUnpool层使用在相应gPool层中选择的节点位置信息将图恢复到其原始结构。基于我们提出的gPool和gUnpool层,我们开发了一个基于图的编解码器模型,称为Graph U-Nets。我们在节点分类和图分类任务上的实验结果表明,我们的方法比以前的模型具有更好的性能。

网址:http://proceedings.mlr.press/v97/gao19a.html

代码链接: https://github.com/HongyangGao/gunet

5、Graph Neural Network for Music Score Data and Modeling Expressive Piano Performance(图神经网络用于乐谱数据和钢琴演奏表现力的建模)

作者:Dasaem Jeong, Taegyun Kwon, Yoojin Kim, Juhan Nam

摘要:乐谱通常被处理为一维序列数据。与文本文档中的单词不同,乐谱中的音符可以由复调性质同时演奏,并且每个音符都有自己的持续时间。在本文中,我们使用图神经网络表示乐谱的独特形式,并将其应用于从乐谱中渲染表现力的钢琴演奏。具体地,我们设计了使用note-level门控图神经网络和采用迭代反馈方法的双向LSTM测量级层次注意网络的模型。此外,为了对给定输入分数的不同性能风格建模,我们使用了一个变分自编码器。听力测试结果表明,与baseline模型和层次注意网络模型相比,我们提出的模型生成了更多的类人性能,而层次注意网络模型将音乐得分处理为类词序列。

网址:http://proceedings.mlr.press/v97/jeong19a.html

代码链接: https://github.com/jdasam/virtuosoNet

6、Graph Matching Networks for Learning the Similarity of Graph Structured Objects(用于学习图结构物体相似性的图匹配网络)

作者:Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, Pushmeet Kohli

摘要:本文针对图结构物体的检索与匹配这一具有挑战性的问题,做了两个关键的贡献。首先,我们演示了如何训练图神经网络(GNN)在向量空间中嵌入图,从而实现高效的相似性推理。其次,提出了一种新的图匹配网络模型,该模型以一对图作为输入,通过一种新的基于注意力的交叉图匹配机制,对图对进行联合推理,计算出图对之间的相似度评分。我们证明了我们的模型在不同领域的有效性,包括具有挑战性的基于控制流图的功能相似性搜索问题,该问题在软件系统漏洞检测中发挥着重要作用。实验分析表明,我们的模型不仅能够在相似性学习的背景下利用结构,而且它们还比那些为这些问题精心手工设计的领域特定baseline系统表现得更好。

网址:http://proceedings.mlr.press/v97/li19d.html

7、Disentangled Graph Convolutional Networks(Disentangled图卷积网络)

作者:Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, Wenwu Zhu

摘要:真实世界图形的形成通常来自于许多潜在因素之间高度复杂的交互作用。现有的基于图结构数据的深度学习方法忽略了潜在因素的纠缠,使得学习表示不鲁棒,难以解释。然而,在图神经网络的研究中,如何将潜在因素分解出来的学习表示方法面临着巨大的挑战,并且在很大程度上还没有得到探索。本文引入解纠缠(Disentangled)图卷积网络(DisenGCN)来学习disentangled节点表示。特别地,我们提出了一种新的邻域路由机制,它能够动态地识别可能导致节点与其相邻节点之间产生边的潜在因素,并相应地将相邻节点分配到一个提取和卷积特定于该因素的特性的信道。从理论上证明了该路由机制的收敛性。实验结果表明,我们提出的模型可以获得显著的性能提升,特别是当数据表明存在许多纠缠因素时。

网址:http://proceedings.mlr.press/v97/ma19a.html

8、GMNN: Graph Markov Neural Networks(GMNN: 图马尔可夫神经网络)

作者:Meng Qu, Yoshua Bengio, Jian Tang

摘要:本文研究关系数据中的半监督对象分类问题,这是关系数据建模中的一个基本问题。在统计关系学习(如关系马尔可夫网络)和图神经网络(如图卷积网络)的文献中,这一问题得到了广泛的研究。统计关系学习方法可以通过条件随机场对对象标签的依赖关系进行有效的建模,用于集体分类,而图神经网络则通过端到端训练学习有效的对象表示来分类。在本文中,我们提出了一种集两种方法优点于一体的Graph Markov Neural Networks (GMNN)。GMNN利用条件随机场对目标标签的联合分布进行建模,利用变分EM算法对其进行有效训练。在E-step中,一个图神经网络学习有效的对象表示,逼近对象标签的后验分布。在M-step中,利用另一个图神经网络对局部标签依赖关系进行建模。在对象分类、链路分类和无监督节点表示学习等方面的实验表明,GMNN取得了较好的效果。

网址:http://proceedings.mlr.press/v97/qu19a.html

代码链接: https://github.com/DeepGraphLearning/GMNN

9、Simplifying Graph Convolutional Networks(简化图卷积网络)

作者:Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, Kilian Weinberger

摘要:图卷积网络(GCNs)及其变体得到了广泛的关注,已成为学习图表示的实际方法。GCNs的灵感主要来自最近的深度学习方法,因此可能会继承不必要的复杂性和冗余计算。在本文中,我们通过连续消除非线性和折叠连续层之间的权重矩阵来减少这种额外的复杂性。我们从理论上分析了得到的线性模型,结果表明它对应于一个固定的低通滤波器,然后是一个线性分类器。值得注意的是,我们的实验评估表明,这些简化不会对许多下游应用程序的准确性产生负面影响。此外,生成的模型可以扩展到更大的数据集,这是自然可解释的,并且比FastGCN的速度提高了两个数量级。

网址:http://proceedings.mlr.press/v97/wu19e.html

代码链接: https://github.com/Tiiiger/SGC

10、Position-aware Graph Neural Networks(位置感知图神经网络)

作者:Jiaxuan You, Rex Ying, Jure Leskovec

摘要:学习节点嵌入,捕捉节点在更广泛的图结构中的位置,对于图上的许多预测任务是至关重要的。然而,现有的图神经网络(GNN)结构在获取给定节点相对于图中所有其他节点的position/location方面的能力有限。本文提出了一种计算位置感知节点嵌入的新型神经网络—Position-aware Graph Neural Networks (P-GNNs)。P-GNN首先对锚节点集进行采样,计算给定目标节点到每个锚集的距离,然后学习锚集上的非线性距离加权聚集方案。通过这种方式,P-GNNs可以捕获节点相对于锚节点的位置。P-GNN有几个优点: 它们具有归纳性,可扩展性,并且可以包含节点特征信息。我们将P-GNNs应用于多个预测任务,包括链路预测和社区检测。我们显示,P-GNNs始终优于最先进的GNNs, 在ROC AUC分数方面提高了66%。

网址:http://proceedings.mlr.press/v97/you19b.html

代码链接: https://github.com/JiaxuanYou/P-GNN

论文下载

百度云链接:https://pan.baidu.com/s/1hOSkrDD2VWRJCTj9_uGrjw

提取码:vcc3

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

1、 Adversarial Graph Embedding for Ensemble Clustering

作者:Zhiqiang Tao , Hongfu Liu , Jun Li , ZhaowenWang and Yun Fu;

摘要:Ensemble Clustering通常通过图分区方法将基本分区集成到共识分区(consensus partition)中,但这种方法存在两个局限性: 1) 它忽略了重用原始特征; 2)获得具有可学习图表示的共识分区(consensus partition)仍未得到充分研究。在本文中,我们提出了一种新颖的对抗图自动编码器(AGAE)模型,将集成聚类结合到深度图嵌入过程中。具体地,采用图卷积网络作为概率编码器,将特征内容信息与共识图信息进行联合集成,并使用简单的内积层作为解码器,利用编码的潜变量(即嵌入表示)重建图。此外,我们还开发了一个对抗正则化器来指导具有自适应分区依赖先验的网络训练。通过对8个实际数据集的实验,证明了AGAE在几种先进的深度嵌入和集成聚类方法上的有效性。

网址:https://www.ijcai.org/proceedings/2019/0494.pdf

2、Attributed Graph Clustering via Adaptive Graph Convolution

作者:Xiaotong Zhang, Han Liu, Qimai Li and Xiao-Ming Wu;

摘要:Attributed Graph聚类是一项具有挑战性的工作,它要求对图结构和节点属性进行联合建模。图卷积网络的研究进展表明,图卷积能够有效地将结构信息和内容信息结合起来,近年来基于图卷积的方法在一些实际属性网络上取得了良好的聚类性能。然而,对于图卷积如何影响聚类性能以及如何正确地使用它来优化不同图的性能,人们的了解有限。现有的方法本质上是利用固定低阶的图卷积,只考虑每个节点几跳内的邻居,没有充分利用节点关系,忽略了图的多样性。本文提出了一种自适应图卷积方法,利用高阶图卷积捕获全局聚类结构,并自适应地为不同的图选择合适的顺序。通过对基准数据集的理论分析和大量实验,验证了该方法的有效性。实验结果表明,该方法与现有的方法相比具有较好的优越性。

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

3、Dynamic Hypergraph Neural Networks

作者:Jianwen Jiang , Yuxuan Wei , Yifan Feng , Jingxuan Cao and Yue Gao;

摘要:近年来,基于图/超图(graph/hypergraph)的深度学习方法引起了研究者的广泛关注。这些深度学习方法以图/超图结构作为模型的先验知识。然而,隐藏的重要关系并没有直接表现在内在结构中。为了解决这个问题,我们提出了一个动态超图神经网络框架(DHGNN),它由两个模块的堆叠层组成:动态超图构造(DHG)和超图卷积(HGC)。考虑到最初构造的超图可能不适合表示数据,DHG模块在每一层上动态更新超图结构。然后引入超图卷积对超图结构中的高阶数据关系进行编码。HGC模块包括两个阶段:顶点卷积和超边界卷积,它们分别用于聚合顶点和超边界之间的特征。我们已经在标准数据集、Cora引文网络和微博数据集上评估了我们的方法。我们的方法优于最先进的方法。通过更多的实验验证了该方法对不同数据分布的有效性和鲁棒性。

网址:https://www.ijcai.org/proceedings/2019/0366.pdf

4、Exploiting Interaction Links for Node Classification with Deep Graph Neural Networks

作者:Hogun Park and Jennifer Neville;

摘要:节点分类是关系机器学习中的一个重要问题。然而,在图边表示实体间交互的场景中(例如,随着时间的推移),大多数当前方法要么将交互信息汇总为链接权重,要么聚合链接以生成静态图。在本文中,我们提出了一种神经网络结构,它可以同时捕获时间和静态交互模式,我们称之为Temporal-Static-Graph-Net(TSGNet)。我们的主要观点是,利用静态邻居编码器(可以学习聚合邻居模式)和基于图神经网络的递归单元(可以捕获复杂的交互模式),可以提高节点分类的性能。在我们对节点分类任务的实验中,与最先进的方法相比,TSGNet取得了显著的进步——与四个真实网络和一个合成数据集中的最佳竞争模型相比,TSGNet的分类错误减少了24%,平均减少了10%。

网址:https://www.ijcai.org/proceedings/2019/0447.pdf

5、Fine-grained Event Categorization with Heterogeneous Graph Convolutional Networks

作者:Hao Peng, Jianxin Li, Qiran Gong, Yangqiu Song, Yuanxing Ning, Kunfeng Lai and Philip S. Yu;

摘要:事件在现实世界中实时发生,可以是涉及多个人和物体的计划和组织场合。社交媒体平台发布了大量包含公共事件和综合话题的文本消息。然而,由于文本中事件元素的异构性以及显式和隐式的社交网络结构,挖掘社会事件是一项具有挑战性的工作。本文设计了一个事件元模式来表征社会事件的语义关联,并构建了一个基于事件的异构信息网络(HIN),该网络融合了外部知识库中的信息,提出了一种基于对偶流行度图卷积网络(PP-GCN)的细粒度社会事件分类模型。我们提出了一种基于事件间社会事件相似度(KIES)的知识元路径实例,并建立了一个加权邻域矩阵作为PP-GCN模型的输入。通过对真实数据收集的综合实验,比较各种社会事件检测和聚类任务。实验结果表明,我们提出的框架优于其他可选的社会事件分类技术。

网址:https://www.zhuanzhi.ai/paper/65dbfd1c2b65d01b2db1b66a3b4efdb6

6、Graph Contextualized Self-Attention Network for Session-based Recommendation

作者:Chengfeng Xu, Pengpeng Zhao, Yanchi Liu, Victor S. Sheng, Jiajie Xu, Fuzhen Zhuang, Junhua Fang and Xiaofang Zhou;

摘要:基于会话的推荐旨在预测用户基于匿名会话的下一步行动,是许多在线服务(比如电子商务,媒体流)中的关键任务。近年来,在不使用递归网络和卷积网络的情况下,自注意力网络(SAN)在各种序列建模任务中取得了显著的成功。然而,SAN缺乏存在于相邻商品上的本地依赖关系,并且限制了其学习序列中商品的上下文表示的能力。本文提出了一种利用图神经网络和自注意力机制的图上下文自注意力模型(GC-SAN),用于基于会话的推荐。在GC-SAN中,我们动态地为会话序列构造一个图结构,并通过图神经网络(GNN)捕获丰富的局部依赖关系。然后,每个会话通过应用自注意力机制学习长期依赖关系。最后,每个会话都表示为全局首选项和当前会话兴趣的线性组合。对两个真实数据集的大量实验表明,GC-SAN始终优于最先进的方法。

网址:https://www.ijcai.org/proceedings/2019/0547.pdf

7、Graph Convolutional Network Hashing for Cross-Modal Retrieval

作者:Ruiqing Xu , Chao Li , Junchi Yan , Cheng Deng and Xianglong Liu;

摘要:基于深度网络的跨模态检索近年来取得了显著的进展。然而,弥补模态差异,进一步提高检索精度仍然是一个关键的瓶颈。本文提出了一种图卷积哈希(GCH)方法,该方法通过关联图学习模态统一的二进制码。一个端到端深度体系结构由三个主要组件构成:语义编码模块、两个特征编码网络和一个图卷积网络(GCN)。我们设计了一个语义编码器作为教师模块来指导特征编码过程,即学生模块,用于语义信息的挖掘。此外,利用GCN研究数据点之间的内在相似性结构,有助于产生有区别的哈希码。在三个基准数据集上的大量实验表明,所提出的GCH方法优于最先进的方法。

网址:https://www.ijcai.org/proceedings/2019/0138.pdf

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

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
29
小贴士
相关VIP内容
相关论文
Filippo Maria Bianchi,Daniele Grattarola,Cesare Alippi
20+阅读 · 2020年6月3日
Hyper-Parameter Optimization: A Review of Algorithms and Applications
Tong Yu,Hong Zhu
12+阅读 · 2020年3月12日
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
12+阅读 · 2019年11月6日
Invariance-Preserving Localized Activation Functions for Graph Neural Networks
Luana Ruiz,Fernando Gama,Antonio G. Marques,Alejandro Ribeiro
4+阅读 · 2019年11月5日
Simon S. Du,Kangcheng Hou,Barnabás Póczos,Ruslan Salakhutdinov,Ruosong Wang,Keyulu Xu
8+阅读 · 2019年11月4日
Muhan Zhang,Shali Jiang,Zhicheng Cui,Roman Garnett,Yixin Chen
7+阅读 · 2019年5月30日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Naganand Yadati,Madhav Nimishakavi,Prateek Yadav,Vikram Nitin,Anand Louis,Partha Talukdar
9+阅读 · 2019年5月22日
Yue Yu,Jie Chen,Tian Gao,Mo Yu
5+阅读 · 2019年4月22日
Kevin Scaman,Francis Bach,Sébastien Bubeck,Yin Tat Lee,Laurent Massoulié
7+阅读 · 2018年6月1日
Top