Current graph neural networks (GNNs) lack generalizability with respect to
scales (graph sizes, graph diameters, edge weights, etc..) when solving many
graph analysis problems. Taking the perspective of synthesizing graph theory
programs, we propose several extensions to address the issue. First, inspired
by the dependency of the iteration number of common graph theory algorithms on
graph size, we learn to terminate the message passing process in GNNs
adaptively according to the computation progress. Second, inspired by the fact
that many graph theory algorithms are homogeneous with respect to graph
weights, we introduce homogeneous transformation layers that are universal
homogeneous function approximators, to convert ordinary GNNs to be homogeneous.
Experimentally, we show that our GNN can be trained from small-scale graphs but
generalize well to large-scale graphs for a number of basic graph theory
problems. It also shows generalizability for applications of multi-body
physical simulation and image-based navigation problems.

通过引入适应计算进程的学习终止机制和具有通用同态函数逼近器的同态转换层，从构造图论程序的角度出发，针对当前图神经网络在解决多个图分析问题时规模（图大小、图直径、边权重等）的泛化性不足问题提出了几种扩展方法，实验结果表明该方法在小规模图上训练，但是对于大规模图也具有很好的泛化性。