Papers › GAP: Generalizable Approximate Graph Partitioning Framework

GAP: Generalizable Approximate Graph Partitioning Framework

2 Mar 2019arXiv:1903.00614archive 2025-07-28

Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, Azalia Mirhoseini

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.

Paper PDF Code

In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

Code

saurabhdash/GCN_Partitioning mentioned on GitHubpytorch report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Clustering graph partitioning

Results from the paper archive 2025-07-28

Task	Dataset	Model	Metric	Value	Rank at snapshot	Leaderboard	Report
graph partitioning	custom	GAP	All	min	#1 of 1	Archive leaderboard	report

Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.

Methods

1x1 Convolution Average Pooling Batch Normalization Bottleneck Residual Block Convolution Dense Connections Dropout Global Average Pooling Kaiming Initialization Max Pooling ReLU Residual Block Residual Connection Softmax

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections