摘要

图划分是指在最小化各划分之间边切割的同时，将图的节点划分为平衡的子集。由于其组合性质，许多近似解决方案已经被开发出来，包括多级方法的变体和谱聚类。我们提出了GAP（Generalizable Approximate Partitioning），一种采用深度学习方法的可泛化近似划分框架。我们定义了一个可微分的损失函数来表示划分目标，并使用反向传播来优化网络参数。与每次针对不同图重新进行优化的基线方法不同，GAP具有泛化能力，可以在推理时生成高效的划分结果，即使是在未见过的图上也是如此。此外，由于我们在联合优化划分损失函数的同时学习图的表示，因此GAP可以轻松调整以适应各种图结构。我们在不同大小和结构的图上评估了GAP的性能，包括广泛使用的机器学习模型（如ResNet、VGG和Inception-V3）对应的图、无标度图和随机图。实验结果表明，GAP不仅能够实现竞争性的划分效果，而且比基线方法快至100倍，并且能够泛化到未见过的图上。