新智元引荐
来历：专知 (ID:Quan_Zhuanzhi)
【新智元导读】最近，人工智能和机器学习范畴的国际尖端会议 NeurIPS 2019 接纳论文发布，共有 1428 篇论文被接纳。为了带咱们抢先领会高质量论文，本文整理了八篇 NeurIPS 2019 最新 GNN 相关论文，并附上 arXiv 论文链接供参阅。
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
