【NeurIPS2020】点针图网络，Pointer Graph Networks

图神经网络(GNNs)通常应用于静态图，这些静态图可以认为是预先已知的。这种静态输入结构通常完全由机器学习从业者的洞察力决定，对于GNN正在解决的实际任务可能不是最佳的。在缺乏可靠的领域专家知识的情况下，人们可能求助于推断潜在的图结构，但由于可能的图的搜索空间很大，这往往是困难的。这里我们引入了点针图网络(PGNs)，它增加了集合或图的推断边的能力，以提高模型的表达能力。PGNs允许每个节点动态地指向另一个节点，然后通过这些点针传递消息。这种可适应图结构的稀疏性使学习变得容易处理，同时仍然具有足够的表现力来模拟复杂的算法。关键的是，指向机制可以直接监督的，以对经典数据结构上的长期操作序列建模，并结合了来自理论计算机科学的有用的结构归纳偏差。定性地说，我们证明了PGNs可以学习基于点针的数据结构的可并行变体，即不相交集并和链接/修剪树。PGNs在动态图连通性任务中将分布外概括为5个较大的测试输入，优于不受限制的GNNs和深度集合。