GAP: Generalizable Approximate Graph Partitioning Framework

Abstract

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.

References in corpus (11)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering
• Deep Unsupervised Clustering with Gaussian Mixture Variational Autoencoders
• Device Placement Optimization with Reinforcement Learning
• SpectralNet: Spectral Clustering using Deep Neural Networks
• Variational Deep Embedding: An Unsupervised and Generative Approach to Clustering
• Understanding Regularized Spectral Clustering via Graph Conductance
• Neural Graph Machines: Learning Neural Networks Using Graphs
• Balanced k-Means and Min-Cut Clustering

Cited by in corpus (7)

• Chip Placement with Deep Reinforcement Learning
• End to end learning and optimization on graphs
• Graph Neural Network Based Coarse-Grained Mapping Prediction
• Mask-GVAE: Blind Denoising Graphs via Partition
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks
• Partition and Code: learning how to compress graphs