Source-linked AI summary
Recent Advances in Graph Partitioning
Aydin Buluc, Henning Meyerhenke, Ilya Safro, Peter Sanders, Christian Schulz
TL;DR
Large and increasingly challenging graph-partitioning instances make practical algorithms important for complexity reduction and parallelization. This paper surveys recent practical algorithms, applications, and future directions, finding strong results on moderately sized regular graphs but substantial open problems in broader settings.
Problem
Graph partitioning is an important subproblem for complexity reduction and parallelization, but growing scientific, social, and road-network instances make it increasingly challenging.
Method
The paper provides a structured overview of practical balanced graph-partitioning algorithms, including local search, coarsening, parallel methods, repartitioning, applications, and benchmarking.
Results
The survey finds that current systems achieve very good quality on moderately sized static graphs with mostly regular structure, while quality-comparable scalable parallel partitioning remains open.
Takeaways & Limitations
Decade-old KL/FM local search and multilevel techniques remain effective on established benchmarks, but wider graph structures, hardware scales, and theory–practice gaps demand further research.
Takeaways & Limitations
The survey highlights that heuristics often perform near-opt optimally despite limited theoretical understanding, while practical solvers do not use sophisticated approximation techniques.
Abstract
from arXiv · showhide
We survey recent trends in practical algorithms for balanced graph partitioning together with applications and future research directions.
1 Introduction
Graph partitioning divides large graphs into smaller pieces and supports complexity reduction and parallelization across diverse applications. The survey organizes the literature around problem variants, applications, and practical solution methods, emphasizing recent work.
- Graph partitioning is a fundamental operation used to reduce complexity or enable parallelization in problems involving large graphs.The paper motivates its importance through scientific simulation, social networks, and road networks.
- The survey first introduces graph-partitioning variants and properties, including applications in parallel processing, road networks, image processing, VLSI design, social networks, and bioinformatics.
- Its core methodological overview covers direct global methods, heuristics, and multilevel algorithms for partitioning large graphs.The survey presents multilevel methods as the most successful approach for large graphs.
2 Preliminaries
Graph partitioning seeks a balanced partition optimized for an application-specific objective, while related hypergraph and approximation formulations alter the model, constraints, or attainable guarantees. In practice, theoretical methods often remain too slow or difficult to use at large scale.
- The graph partitioning problem assigns nodes to k disjoint blocks covering V, with a balance constraint limiting each block to roughly equal weight.The maximum block weight is L_max = (1+ϵ)⌈|V|/k⌉, and ϵ = 0 denotes perfect balance.
- Common objectives include minimizing cut size, communication volume, expansion, conductance, or normalized cut, depending on the application.Cut size remains a practical standard, while communication volume can better reflect parallel-computing costs.
- Repartitioning addresses evolving graphs by computing a new partition after imbalance develops while often seeking to keep changes from the old partition small.
- Hypergraph partitioning generalizes edges to hyperedges and commonly uses the (λ−1) metric rather than ordinary edge cut.Its more complex implementation and running time are worthwhile when the hypergraph model substantially benefits the application.
- Balanced graph partitioning is computationally hard, and approximation quality varies with the permitted imbalance and objective.For perfectly balanced general graphs, no constant-factor approximation exists; practical solvers therefore mostly use heuristics because approximation methods are often unimplemented or too slow.
3 Applications of Graph Partitioning
Graph partitioning supports parallel computation, mesh and network analysis, routing, image segmentation, and domain-specific applications such as power grids and biological networks. These applications adapt graph models and objectives to balance computation, locality, robustness, or semantic grouping.
- In scientific computing, partitioning distributes work across processors while balancing load and minimizing communication, with repartitioning supporting evolving domains such as adaptive mesh refinement.
- Graph partitioning enables parallel processing for eigenvalue computation, breadth-first search, triangle listing, PageRank, and connected-components problems.
- Mesh partitioning maps geometric subdomains to processors, and multilevel and geometric methods have been applied to large-scale and dynamic mesh problems.
- Network applications use partitioning to identify similar entities or robust regions, including communities, power-grid islands, geographically embedded networks, and biological groups.Power-grid islanding can help prevent propagation of cascading failures, while biological clustering supports data reduction and process detection.
- Road-network partitioning accelerates route planning by reducing search or preprocessing costs, although high-quality partitions can be difficult to find despite surprisingly small cuts.
- Image segmentation represents pixels or pixel groups as graph nodes and uses weighted similarity edges so partitions correspond to image objects.Normalized cut was adopted because classical minimum cut can produce segmented objects that are too small.
4 Global Algorithms
Global algorithms partition the entire graph directly and are used mainly for smaller instances or as components within local-search and multilevel methods. The survey covers exact, spectral, graph-growing, flow, geometric, and streaming approaches, each trading quality, scalability, memory, or structural assumptions.
- Direct global methods often target smaller graphs or serve as subroutines in local-search and multilevel algorithms, with many designed primarily for bipartitioning.
- Exact methods rely largely on branch-and-bound with bounds from semidefinite, flow, linear-programming, or continuous-quadratic formulations.
- Exact algorithms trade stronger, expensive bounds and smaller search trees against weaker, faster bounds and larger trees.Some grid bipartitioning instances without holes can be solved optimally in O(n^4) time.
- Spectral bisection uses the second-smallest Laplacian eigenvector to infer global connectivity, but computing it can be expensive.Multilevel approximations to the Fiedler vector reduce this cost.
- Graph-growing methods use breadth-first search from a starting node until a block reaches about half the node weight, then assign remaining nodes to the other block.
- Flow methods compute minimum cuts between node sets but do not directly enforce balance, whereas geometric methods exploit coordinates and streaming methods use very limited memory.Streaming algorithms are especially fast and can benefit dynamic networks when initialized with a stronger static partition.
5 Iterative Improvement Heuristics
Iterative improvement heuristics refine graph partitions through increasingly flexible local or flow-based moves while preserving balance or improving cut quality. The Bubble framework extends graph growing with repeated seed selection, breadth-first partitioning, local refinement, and new-center computation.
- Node-swapping local search: Local search iteratively changes a partition within a neighborhood, selecting moves that reduce cut size and resetting each round to its best encountered solution.The process terminates when a round finds no improvement.
- Node-swapping local search: The KL/FM algorithm reduces local-search running time from O(n^2 log n) for the original KL implementation to O(m).The improvement comes from carefully designed data structures and adaptations.
- Node-swapping local search: Localized KL/FM searches can escape local minima more effectively and yield improved cuts for KaSPar and KaHIP.The search spreads from a single boundary node and stops when further improvement becomes unlikely under a stochastic model.
- Node-swapping local search: Helpful Sets exchange whole node sets between blocks, achieving solution quality often better than other methods with running time comparable to KL/FM.This generalizes the neighborhood beyond single-node migrations in bipartitioning.
- k-way local search: Recursive bisection can produce partitions far from optimal, motivating k-way local search algorithms that directly improve k-partitions.A linear-time k-way KL/FM variant uses one global priority queue and selects moves maximizing local gain while maintaining or improving balance.
- Bubble Framework: The Bubble framework partitions into k > 2 well-shaped blocks by iterating seed selection, breadth-first growth with local balancing and cut improvement, and new seed computation.Iterations stop when seeds stop changing or no improved partition is found for more than 10 iterations.
6 Multilevel Graph Partitioning
Multilevel graph partitioning repeatedly coarsens a graph, partitions a small instance, and uncoarsens with local improvement. Its effectiveness depends on preserving cut structure while selecting coarsening strategies suited to graph structure.
- Core approach: Multilevel GP has three phases: coarsening, initial partitioning, and uncoarsening with improvement.Coarsening creates smaller graphs, initial partitioning solves the coarsest instance, and uncoarsening maps and refines the solution through the hierarchy.
- Coarsening: Contraction replaces matched node sets by coarse nodes and aggregates parallel-edge weights, preserving balanced partitions and cut values across levels.The hierarchy reduces degrees of freedom while maintaining correspondence between coarse and fine solutions.
- Why multilevel works: Coarse-level moves can produce large final-solution changes, while fine-level local improvement starts from a strong inherited solution.Iterative V-cycles and alternative coarsening-uncoarsening chains can further improve solution quality.
- Matching-based coarsening: n-level GP contracts one edge at a time, producing nearly n levels and high-quality partitions with localized local search.Its additional coarsening overhead mainly comes from maintaining a priority queue and dynamic data structures.
- Matching-based coarsening: Matching-based coarsening usually contracts disjoint edge matchings, yielding geometrically smaller graphs and logarithmically many levels.Edge-rating functions balance preferences for heavy edges against uniform coarse-node weights; algebraic distance can improve ratings.
- Coarsening for irregular graphs: Matching-based coarsening can create undesirable hierarchies for irregular graphs: a star permits only one contracted edge per level.Alternative approaches contract groups, identical-neighborhood nodes, or size-constrained clusters for power-law and social-network graphs.
- Flow-based coarsening: Flow-based coarsening reduces road-network graphs by up to two orders of magnitude and supports a two-level solver that quickly produces very good solutions.The method contracts components separated by heuristically identified natural cuts.
7 Evolutionary Methods and Further Metaheuristics
Evolutionary and memetic approaches combine population-based variation with multilevel graph partitioning. Their operators preserve structure from input partitions while local search and modified edge weights generate improved offspring.
- Hybrid evolutionary methods: Hybrid evolutionary GP methods combine evolutionary ideas with multilevel partitioning frameworks.The survey focuses on hybrid approaches rather than evolutionary algorithms in isolation.
- Hybrid evolutionary methods: Combine and mutation operations modify graph edge weights according to input partitions before invoking a multilevel partitioner.This uses the partitioner to produce a new partition of the original graph.
- Memetic algorithms: The memetic approach combines two partitions by maximizing the number of nodes grouped together under a block matching.Nodes preserved from the parent structure remain grouped, while other nodes are assigned subject to balance and then locally improved.
- Distributed evolutionary methods: KaFFPaE supports combining a partition with another partition or clustering and uses multiple mutation operators to maintain population diversity.Its combine operation uses a modified multilevel solver that avoids contracting edges cut in an input partition.
8 Parallel Aspects of Graph Partitioning
Parallel graph partitioning addresses both hardware scalability and the need to distribute graph work with low communication costs. The surveyed methods include parallel multilevel solvers, architecture-aware partitioning, mapping, and repartitioning techniques.
- Parallel algorithms: Parallel GP is important for memory constraints, ubiquitous parallel hardware, and growing networks, but parallelization difficulty depends on the setting.Independent randomized runs are easy to parallelize but eventually show diminishing returns.
- Parallel algorithms: Distributed-memory multilevel partitioners can scale when a reasonable initial distribution improves locality, although quality loss relative to sequential algorithms remains a concern.Parallel matching and pairwise refinement can preserve high quality in suitable graph classes.
- Parallel algorithms: Highly localized KL/FM-style local search is difficult to parallelize because local search is inherently sequential.Restricting parallel execution to improving moves and using speculative parallelism can make parallelization possible.
- Mapping techniques: Architecture-aware partitioning incorporates processor communication costs directly into the partitioning objective using a network cost matrix.Storing the full matrix on every processing element becomes quadratically expensive as the processor count grows.
- Mapping techniques: The mapping problem assigns an existing communication graph to a processor graph using objectives based on communication weights and processor distances.Common formulations include weighted communication cost, dilation, and routing assumptions such as shortest paths.
- Mapping techniques: Metaheuristics obtain high-quality mappings but are significantly slower than problem-specific heuristics.Greedy, RCM, and dual recursive bipartitioning comparisons found no clear winner across tested architectures.
- Mapping techniques: Better topology-aware mappings avoid communication hot spots and significantly reduce communication times.Mapping is worthwhile even when experiments do not identify a single universally best technique.
- Repartitioning: Diffusion-based repartitioning improves edge cut by about 30−50% over ParMetis and about 15% over parallel Jostle with comparable migration volume.Hypergraph-based repartitioning is particularly important for irregular underlying problems.
9 Implementation and Evaluation Aspects
Implementation and evaluation of graph partitioning balance speed, partition quality, scalability, and application relevance. The survey covers data structures, benchmarks, robustness tests, software systems, and distributed implementations.
- Implementation priorities: Successful graph partitioning algorithms must balance speed and quality according to application needs.The survey frames both implementation efficiency and the meaning of quality as application-dependent.
- Data structures: CSR is the predominant partitioning data structure because it efficiently represents static graphs in cache and storage.Its arrays encode node pointers, edges, and optional weights.
- Distributed implementations: Distributed-memory solvers differ in graph distribution: ParMetis and PT-Scotch use 1D node ownership, whereas Zoltan uses 2D edge distribution.The 2D strategy has lower communication requirements in theory.
- Benchmarks: The Walshaw benchmark provides 34 real-world graphs and reference partitions for comparing cut quality across several block counts.It includes applications such as finite elements, matrices, VLSI, and shortest paths.
- Benchmarks: Application-level evaluation can measure the execution time of a parallel PDE solver rather than only the partitions’ edge cuts.The benchmark uses parallel matrix-vector multiplication as its crucial module.
- Robustness: Robustness tests construct difficult instances by weakly connecting graphs with very different structures, exposing susceptibility to local optima.This targets fast methods that seek global solutions through local operations.
- Software tools: Software ecosystems include multilevel, local-search, spectral, sequential, parallel, and hypergraph partitioners, with systems emphasizing different speed or quality goals.Examples include Chaco, Metis, hMetis, PaToH, ParMetis, Scotch, and Jostle.
- Scalability: Recent DIMACS results indicate that scaling current hypergraph partitioners to very large systems is more challenging than scaling graph partitioners.The result concerns large-system scalability rather than partition quality alone.
10 Future Challenges
The survey finds classical partitioning on moderately sized, regular graphs relatively mature, while modern hardware, complex networks, large block counts, and broader objectives leave substantial open problems. It highlights unresolved gaps between theory and practice, multilevel design, scalability, and deployment in emerging systems.
- Maturity and open problems: Current systems achieve very good quality on moderately sized, regular Walshaw graphs, limiting likely gains from established techniques.The survey specifically cites KL/FM local search and multilevel methods as decade-old techniques that remain effective.
- Bridging Gaps Between Theory and Practice: Heuristic partitioners often approach optimal bipartitions despite theoretical barriers to constant-factor approximation and limited practical use of approximation methods.The survey identifies this contrast as a major theory-practice gap.
- Difficult Instances: Complex-network graphs challenge current partitioners through uneven degree distributions and reduced locality, creating opportunities for better coarsening and new approaches.The survey expects improvements in both speed and quality from these directions.
- Difficult Instances: Large k creates substantial quality variation across approaches, while multilevel methods become less attractive because initial partitioning remains difficult.The survey notes that k ≤64 may increasingly represent only a special case for billion-node graphs and million-processor machines.
- Multilevel Approach: Multilevel graph partitioning still uses a limited range of techniques compared with mature multiscale fields, motivating nonlinear coarsening and related designs.The survey calls for closer integration between multiscale computing theory and practical multilevel partitioning.
- Parallelism and Other Hardware Issues: Scalable, high-quality partitioning for exascale machines remains open because millions of processors imply huge block counts and difficult recursive decisions.The survey also questions how sequential partitioners perform on such instances.
- Parallelism and Other Hardware Issues: Complex memory hierarchies and heterogeneous hardware complicate efficient implementation because fine-grained partitioning conflicts with massive data parallelism.GPUs and FPGAs favor highly regular numeric computations more than the discrete operations used by strong sequential partitioners.
- Beyond Balanced k-partitioning with Cut Minimization: Modern applications require objectives beyond balanced k-partitioning and cut minimization, including communication demands that may not correlate with total cut.The survey points toward dynamic partitions adapted to computations such as PageRank or BFS.