Classical graph algorithms work well for combinatorial problems that can be thoroughly formalized and abstracted. Once the algorithm is derived, it generalizes to instances of any size. However, developing an algorithm that handles complex structures and interactions in the real world can be challenging. Rather than specifying the algorithm, we can try to learn it from the graph-structured data. Graph Neural Networks (GNNs) are inherently capable of working on graph structures; however, they struggle to generalize well, and learning on larger instances is challenging. In order to scale, we focus on a recurrent architecture design that can learn simple graph problems end to end on smaller graphs and then extrapolate to larger instances. As our main contribution, we identify three essential techniques for recurrent GNNs to scale. By using (i) skip connections, (ii) state regularization, and (iii) edge convolutions, we can guide GNNs toward extrapolation. This allows us to train on small graphs and apply the same model to much larger graphs during inference. Moreover, we empirically validate the extrapolation capabilities of our GNNs on algorithmic datasets.
翻译:古典图形算法对于可彻底正规化和抽象的组合问题效果良好。 一旦算法产生, 它就会概括到任何大小的例子。 但是, 开发一个处理真实世界中复杂结构和相互作用的算法可能会是挑战性的。 我们不用指定算法, 我们可以尝试从图形结构的数据中学习它。 图形神经网络( GNN) 具有内在能力, 可以对图形结构开展工作; 但是, 它们很难将它加以概括化, 而在更大的案例中学习是一个挑战。 为了扩大规模, 我们专注于一个经常性的建筑设计, 可以学习简单的图形问题, 结束在小图表中, 然后将它推到更大的例子中。 作为我们的主要贡献, 我们为经常性的 GNNS 找到三种基本技术。 通过使用 (i) 跳过连接, (ii) 状态正规化, 和 (iii) 边缘共变, 我们可以引导 GNNNs 进行外推。 这使我们能够对小图表进行培训, 并在推算过程中将同样的模型应用到大得多的图表中。 此外, 我们通过实验来验证我们的 GNNNN的外推法的外推能力。