Parallel Graph Partitioning for Complex Networks

Henning Meyerhenke; Peter Sanders; Christian Schulz

Source-linked AI summary

Parallel Graph Partitioning for Complex Networks

Henning Meyerhenke, Peter Sanders, Christian Schulz

arXiv:1404.4797v3Apr 18, 2014cs.DCcs.DScs.NEcs.SIphysics.soc-ph

TL;DR

Large complex networks need balanced, low-cut partitions for parallel processing, but partitioners designed for regular graphs struggle on these networks. The paper parallelizes size-constrained label propagation within a multilevel scheme and uses an evolutionary algorithm on the coarsened graph, achieving higher quality and scalability than competing systems on complex networks.

Problem
Large complex networks require balanced, low-cut partitions for parallel processing, but existing partitioners struggle with these irregular graphs.
Method
The paper parallelizes size-constrained label propagation for multilevel coarsening and refinement, then applies KaFFPaE to the coarsened graph.
Results
On social networks and web graphs, the method produces smaller cuts and faster runtimes than ParMetis, while scaling to thousands of processors.
Takeaways & Limitations
The approach enables high-quality partitioning of web-scale complex networks that competing systems may fail to partition.

Abstract

from arXiv · show

Processing large complex networks like social networks or web graphs has recently attracted considerable interest. In order to do this in parallel, we need to partition them into pieces of about equal size. Unfortunately, previous parallel graph partitioners originally developed for more regular mesh-like networks do not work well for these networks. This paper addresses this problem by parallelizing and adapting the label propagation technique originally developed for graph clustering. By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of multilevel graph partitioning. We obtain very high quality by applying a highly parallel evolutionary algorithm to the coarsened graph. The resulting system is both more scalable and achieves higher quality than state-of-the-art systems like ParMetis or PT-Scotch. For large complex networks the performance differences are very big. For example, our algorithm can partition a web graph with 3.3 billion edges in less than sixteen seconds using 512 cores of a high performance cluster while producing a high quality partition -- none of the competing systems can handle this graph on our system.

I. INTRODUCTION

The paper targets balanced, low-cut partitions for large complex networks, where existing approaches struggle, and integrates constrained label propagation into a multilevel framework. The resulting system improves speed and solution quality on irregular social and web graphs.

I. INTRODUCTION: Balanced graph partitioning minimizes edges between blocks while keeping each block within (1 + ϵ) times the average size.The problem is important for parallel processing, where a graph is divided across processing elements.
I. INTRODUCTION: Multilevel partitioning recursively contracts the graph, partitions the smallest graph, then refines the solution while uncoarsening.This hierarchy is intended to preserve the input graph’s basic structure at smaller scales.
I. INTRODUCTION: The method parallelizes size-constrained label propagation for coarsening and refinement, uses KaFFPaE on the coarsest graph, and repeats contraction until the graph is small enough.The same size constraint connects clustering, coarsening, and local search within the multilevel framework.
I. INTRODUCTION: The system speeds computation and improves solution quality on irregular social networks and web graphs, including web graphs with billions of edges.The introduction reports partitioning a web graph with billions of edges in only a few seconds while maintaining high-quality solutions.

B. Related Work

Prior parallel partitioners rely on multilevel or alternative strategies, but their scalability, balance maintenance, or suitability for complex networks is limited. Existing label-propagation and geometric approaches also do not directly provide the paper’s target combination of strict balance and high-quality partitioning.

B. Related Work: General-purpose partitioners for large real-world graphs commonly use the multilevel principle, contracting graphs before refinement.The related-work discussion traces this strategy to multigrid ideas and practical graph partitioners.
B. Related Work: ParMetis is fast, whereas Jostle, PT-Scotch, KaPPa, and PDiBaP impose restrictions or face parallelism, balance, or scale-related challenges.The cited systems use different strategies, including recursive bipartitioning, matching-based coarsening, and diffusion.
B. Related Work: Hash-based partitioning often balances complex networks acceptably but can produce very high edge cuts, motivating more structure-aware methods.A toolkit-specific alternative combines matching-based coarsening with ParMetis on the coarsest graph.
B. Related Work: Earlier label-propagation partitioning approaches use unconstrained refinement or relaxed balance, so they do not directly yield high-quality partitions under strict balance constraints.Other work computes geometric partitions after embedding networks into coordinate space.

C. KaHIP

KaHIP supplies the multilevel and evolutionary components used to partition the coarsest graph. Its distributed evolutionary algorithm maintains local populations and combines partitions through multilevel recombination while preserving solution quality.

C. KaHIP: The system uses KaHIP’s distributed evolutionary algorithm KaFFPaE to create high-quality partitions at the coarsest hierarchy level.KaHIP also contains flow-based methods, localized searches, and parallel or sequential meta-heuristics.
C. KaHIP: KaFFPaE assigns each processing element a local population and graph copy, then applies combination and mutation operations.This coarse-grained evolutionary design supports parallel exploration of partitions.
C. KaHIP: The combination operator prevents edges cut by either parent partition from being contracted during coarsening.The better parent partition is then applied to the coarsest graph as the initial partition.
C. KaHIP: Because local search does not worsen the input partition, uncoarsening preserves partition quality while allowing good solution parts to be exchanged.Processors exchange best local partitions through a scalable randomized communication protocol.

III. CLUSTER CONTRACTION

The paper adapts label propagation with block-size limits and uses the resulting clusterings for aggressive multilevel contraction. Contraction preserves cut and balance, while the same constrained procedure supports refinement during uncoarsening.

III. CLUSTER CONTRACTION: Repeated clustering and contraction can shrink irregular social and web graphs by orders of magnitude while preserving the partition objective and balance.Each cluster becomes one coarse node, and the resulting hierarchy is used until the graph is small.
III. CLUSTER CONTRACTION: In the label-propagation rounds, nodes are traversed in random order and moved toward the neighboring cluster with the strongest connection.The algorithm begins with each node in its own cluster.
III. CLUSTER CONTRACTION: Contracted node and edge weights aggregate the corresponding fine-graph weights, so a coarse partition induces a fine partition with the same cut and balance.The contraction is illustrated by mapping each fine-level cluster to one coarse-level node.
III. CLUSTER CONTRACTION: Size-constrained label propagation moves each node to the strongest eligible neighboring block, keeping every cluster at or below an upper bound U.The constraint prevents coarse clusters from becoming too large for a feasible balanced partition and can be implemented in linear time per round.
III. CLUSTER CONTRACTION: Increasing-degree node ordering can improve both clustering quality and running time compared with random ordering.The ordering lets low-degree nodes change clusters earlier in the first propagation round.
III. CLUSTER CONTRACTION: The size constraint is reused during uncoarsening as a fast local-search rule, with modifications for overloaded blocks.The hierarchy is refined by transferring each coarse node’s assignment to its finer-level representatives.

IV. PARALLELIZATION

The paper parallelizes size-constrained label propagation over distributed subgraphs, using local processing, hashed cluster lookup, asynchronous communication, and parallel node ordering.

Each processing element receives a contiguous node range plus incident edges and ghost nodes, enabling distributed storage of the input graph.
Local label propagation moves nodes toward strongly connected blocks while hashing arbitrarily distributed cluster IDs for efficient lookup.
Asynchronous phased communication exchanges changed interface-node block IDs while overlapping computation and communication across adjacent processing elements.
During coarsening, each processing element orders only its local nodes by degree, whereas uncoarsening uses random node ordering.

B. Balance/Size Constraint

The parallel method uses size-constrained label propagation and distinct balance-maintenance strategies for coarsening and uncoarsening before constructing the contracted graph.

Size-constrained label propagation controls cluster sizes during both coarsening and uncoarsening, with different balance strategies because their block counts and constraint strictness differ.
During coarsening, processing elements maintain local estimates of block weights and use local information to bound weights as nodes move between blocks.
During uncoarsening, exact block weights are aggregated and broadcast with an allreduce operation so every processing element knows global block weights.
After clustering, each cluster becomes a weighted coarse node, and intercluster edges form the coarse graph.
Parallel contraction counts distinct cluster IDs, maps them to contiguous IDs using prefix sums, and exchanges weighted quotient edges among responsible processing elements.
During uncoarsening, processing elements request each fine node’s coarse representative block ID from the processing element holding that coarse node.

D. Miscellanea

The system supports iterated multilevel schemes by preserving input-partition cut edges during clustering and combining coarsening, evolutionary partitioning, and uncoarsening.

Iterated Multilevel Schemes:: Iterated V-cycles restrict each clustering to individual input-partition blocks, ensuring that input cut edges remain uncontracted.
Iterated Multilevel Schemes:: The overall system combines parallel cluster coarsening, KaFFPaE partitioning of the coarsest graph, and parallel uncoarsening or local search.
Iterated Multilevel Schemes:: The input partition is supplied as a starting individual for the evolutionary algorithm after the first multilevel iteration.

E. The Overall Parallel System

The overall system recursively coarsens and refines graphs with size constraints, optionally uses iterated V-cycles, and evaluates fast and eco configurations against parallel partitioning baselines.

The system repeatedly applies parallel size-constrained label propagation and contraction until the graph has 10 000 · k nodes, then recursively refines it to obtain a k-partition.
With iterated V-cycles, the given coarse partition seeds the evolutionary algorithm, ensuring the resulting partition is at least as good as that input.
Experiments evaluate solution quality and weak and strong scalability against ParMetis, while PT-Scotch results are omitted because they were consistently worse in quality and running time than ParMetis.
The fast and eco configurations trade execution time against partitioning quality, with the fast setting used by default.
The fast configuration uses three coarsening and six refinement label-propagation iterations, limited evolutionary initialization, and two V-cycles.

Systems:

The evaluation uses two systems and a benchmark set spanning numeric simulations, social networks, web graphs, and graph families such as rgg and del.

System A evaluates solution quality, while System B is used for scalability experiments on a cluster.
Table I summarizes the benchmark graphs’ basic properties and classifies them broadly as social or web graphs versus mesh-type networks.
The benchmark set covers numeric simulations, social networks, web graphs, and the rgg and del graph families.
The rgg and del families include very large graphs, with up to about 21.9 billion and 6.4 billion edges, respectively.

B. Main Results and Comparison to ParMetis

Across solvable instances, the proposed configurations generally improve cut quality over ParMetis, especially on social and web graphs, while also scaling to larger networks that ParMetis cannot handle. The advantage is strongest for irregular complex networks, whereas mesh-like graphs yield smaller quality gains and higher runtime costs.

Solution quality and runtime: ParMetis cannot solve several largest instances because ineffective coarsening leaves uk-2007 with more than 60M coarse vertices, whereas the proposed method reduces it by two orders of magnitude after one contraction.On arabic, ParMetis requires 15 PEs, cuts nearly twice as many edges, and takes 37 times longer than the fast variant.
Solution quality and runtime: 38% smaller cuts and more than twice the speed are achieved on social and web graphs by the fast configuration versus ParMetis.The eco configuration achieves 45% smaller cuts on these networks.
Solution quality and runtime: 6.8% and 16.1% smaller cuts are obtained overall by the fast and eco configurations, respectively, than by ParMetis.This comparison includes instances where ParMetis relaxes the balance constraint, reaching up to 6% imbalance.
Solution quality and runtime: On mesh-type networks, the fast configuration improves cuts by only 2.9% while requiring more than five times ParMetis's runtime, although the eco configuration achieves 11.8% smaller cuts.The weaker advantage is attributed to the absence of community structure that can be contracted effectively.
Weak scalability: 19.5% and 11.5% better solution quality are achieved on random geometric and Delaunay graphs, respectively, while weak scalability extends to the largest tested core count.On the largest Delaunay graph ParMetis can solve, the proposed method is five times faster and produces a 9.5% smaller cut.
Strong scalability: Strong scaling reaches 2048 cores for sufficiently large graphs, requiring roughly 6.5 minutes for del31 and 73 seconds for rgg31.Delaunay partitioning is slower despite fewer edges because more than 40% of its edges are ghost edges, versus less than 0.5% for the largest random geometric graph.

VI. CONCLUSION AND FUTURE WORK

The paper presents a scalable multilevel partitioning scheme for massive complex networks, combining size-constrained label propagation with evolutionary partitioning. It reports better quality and running time than ParMetis on social and web graphs, including web-scale instances, while offering quality–time trade-offs.

Conclusion: The multilevel scheme uses size-constrained clusterings for rapid contraction, evolutionary partitioning on the coarsest graph, and label propagation for local refinement.V-cycles and coarsest-level evolutionary processing provide a gradual trade-off between solution quality and running time.
Conclusion: The approach targets a limitation of current partitioners: ineffective coarsening on massive complex networks.The authors report that parallel size-constrained label propagation can reduce graph size very quickly.
Conclusion: The system achieves much better average solution quality and running time than ParMetis on social networks and web graphs, and scales to thousands of processors.Its drastic network shrinkage enables high-quality web-scale partitions in seconds, whereas ParMetis fails to compute any partition.
Future Work: The authors anticipate further running-time savings in cloud-based graph-processing toolkits because their method outperforms ParMetis on large complex networks.They identify large-scale graph-processing systems as an important application scenario.
Future Work: Future work includes a fast prepartitioner, reuse of previous partitions to reduce communication, and extensions to modularity-based clustering and other objective functions.The proposed prepartitioner is intended for systems such as Apache Giraph, Giraph++, and GraphLab.

APPENDIX

Table III compares partitioning algorithms using average cut, running time, and best achieved result for k = 32. The experiments use 32 processing elements, with memory-overflow markers and a reduced-processing-element ParMetis result for Arabic.

Appendix: Table III reports average cut, running time, and best results for different partitioning algorithms at k = 32.
Appendix: All tools are evaluated using 32 processing elements on machine A.
Appendix: An asterisk denotes that a partitioner exceeded the available 512 GB of memory, while the Arabic ParMetis result used 15 processing elements.