# Towards Faster Graph Partitioning via Pre-training and Inductive Inference

arXiv: https://arxiv.org/abs/2409.00670 · HTML: https://mlsanity.com/paper/2409.00670/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 1 Sep 2024.

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks](https://mlsanity.com/paper/2302.08043/) (2023)
- [GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks](https://mlsanity.com/paper/1901.09165/) (2019)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Temporal Link Prediction: A Unified Framework, Taxonomy, and Review](https://mlsanity.com/paper/2210.08765/) (2022)
- [When to Pre-Train Graph Neural Networks? From Data Generation Perspective!](https://mlsanity.com/paper/2303.16458/) (2023)
- [Streaming Graph Challenge: Stochastic Block Partition](https://mlsanity.com/paper/1708.07883/) (2017)
- [Pre-train and Refine: Towards Higher Efficiency in K-Agnostic Community Detection without Quality Degradation](https://mlsanity.com/paper/2405.20277/) (2024)
- [Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge](https://mlsanity.com/paper/1708.07481/) (2017)
- [Community detection using fast low-cardinality semidefinite programming](https://mlsanity.com/paper/2012.02676/) (2020)
- [RaftGP: Random Fast Graph Partitioning](https://mlsanity.com/paper/2312.01560/) (2023)

## Built on by (most cited first, 2 of 2)

- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections](https://mlsanity.com/paper/2508.19737/) (2025)

## Abstract (arXiv)

Graph partitioning (GP) is a classic problem that divides the node set of a graph into densely-connected blocks. Following the IEEE HPEC Graph Challenge and recent advances in pre-training techniques (e.g., large-language models), we propose PR-GPT (Pre-trained & Refined Graph ParTitioning) based on a novel pre-training & refinement paradigm. We first conduct the offline pre-training of a deep graph learning (DGL) model on small synthetic graphs with various topology properties. By using the inductive inference of DGL, one can directly generalize the pre-trained model (with frozen model parameters) to large graphs and derive feasible GP results. We also use the derived partition as a good initialization of an efficient GP method (e.g., InfoMap) to further refine the quality of partitioning. In this setting, the online generalization and refinement of PR-GPT can not only benefit from the transfer ability regarding quality but also ensure high inference efficiency without re-training. Based on a mechanism of reducing the scale of a graph to be processed by the refinement method, PR-GPT also has the potential to support streaming GP. Experiments on the Graph Challenge benchmark demonstrate that PR-GPT can ensure faster GP on large-scale graphs without significant quality degradation, compared with running a refinement method from scratch. We will make our code public at https://github.com/KuroginQin/PRGPT.