Graph partitioning is the problem of dividing the nodes of a graph into balanced partitions while minimizing the edge cut across the partitions. Due to its combinatorial nature, many approximate solutions have been developed, including variants of multi-level methods and spectral clustering. We propose GAP, a Generalizable Approximate Partitioning framework that takes a deep learning approach to graph partitioning. We define a differentiable loss function that represents the partitioning objective and use backpropagation to optimize the network parameters. Unlike baselines that redo the optimization per graph, GAP is capable of generalization, allowing us to train models that produce performant partitions at inference time, even on unseen graphs. Furthermore, because we learn the representation of the graph while jointly optimizing for the partitioning loss function, GAP can be easily tuned for a variety of graph structures. We evaluate the performance of GAP on graphs of varying sizes and structures, including graphs of widely used machine learning models (e.g., ResNet, VGG, and Inception-V3), scale-free graphs, and random graphs. We show that GAP achieves competitive partitions while being up to 100 times faster than the baseline and generalizes to unseen graphs.

本研究提出了基于深度学习的GAP框架来解决节点分割问题。通过定义不同iable损失函数以及利用反向传播来优化网络参数，实现基于图结构的节点分割。相较于传统的分割方法，GAP不仅更快，并且具有良好的扩展性能力，可适用于不同的图结构，并可推广到未知的图形结构上。研究表明，GAP能够取得与传统分割方式相媲美的结果。

GAP: 通用的近似图分区框架