Balanced Graph Partitioning is a classical optimization problem where quality guarantees are computationally infeasible, and practical solvers therefore rely on manually engineered heuristics. Yet, the problem has also proven difficult for approaches that rely heavily on machine learning - especially since applications often need to partition graphs of huge scale in a short amount of time. Instead, we demonstrate how to achieve practical improvements with a more careful approach that uses machine learning to improve heuristic decisions within the state-of-the-art solver Mt-KaHyPar. We use a pre-trained neural network to predict a score for each edge, which then guides clustering decisions in the first phase of the partitioning (the coarsening). Combined with corresponding adjustments to the clustering algorithm and an efficient implementation of the neural network logic, we improve the overall solution quality while preserving the efficiency and scalability of the original algorithm. Our detailed evaluation on more than 180 graphs shows an average quality improvement of 2% on a class of graphs with beneficial properties, and unchanged quality on all remaining graphs. Moreover, our improvements generalize to a set of instances from the literature that are much larger than the graphs used during training.

The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as single-level algorithms and streaming algorithms. We demonstrate how to achieve the best of both worlds with a linear time multilevel algorithm. Multilevel algorithms construct a hierarchy of increasingly smaller graphs by repeatedly contracting clusters of nodes. Our approach preserves their distinct advantage, allowing refinement of the partition over multiple levels with increasing detail. At the same time, we use edge sparsification to guarantee geometric size reduction between the levels and thus linear running time. We provide a proof of the linear running time as well as additional insights into the behavior of multilevel algorithms, showing that graphs with low modularity are most likely to trigger worst-case running time. We evaluate multiple approaches for edge sparsification and integrate our algorithm into the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent parallel scalability. As demonstrated in detailed experiments, this results in a 1.49× average speedup (up to 4× for some instances) with only 1% loss in solution quality. Moreover, our algorithm clearly outperforms state-of-the-art single-level and streaming approaches.

We present TeraPart, a memory-efficient multilevel graph partitioning method that is designed to scale to extremely large graphs. In balanced graph partitioning, the goal is to divide the vertices into$k$blocks with balanced size while cutting as few edges as possible. Due to its NP-hard nature, heuristics are prevalent in this field, with the multilevel framework as the state-of-the-art method. Recent work has seen tremendous progress in speeding up partitioning algorithms through parallelism. The current obstacle in scaling to larger graphs is the high memory usage due to auxiliary data structures and storing the graph itself in memory. In this paper, we present and study several optimizations to significantly reduce their memory footprint. We devise parallel label propagation clustering and graph contraction algorithms that use$O(n)$auxiliary space instead of$O(n p)$, where$p$is the number of processors. Moreover, we employ an existing compressed graph representation that enables iterating over a neighborhood by on-the-fly decoding at speeds close to the uncompressed graph. Combining these optimizations yields up to a 16 -fold reduction in peak memory, while retaining the same solution quality and similar speed. This configuration can partition a graph with one trillion edges in under 8 minutes on a single machine using around 900 GiB of RAM. This is the first work to employ the multilevel framework at this scale, which is vital to achieving low edge cuts. Moreover, our distributed memory implementation handles graphs of up to 16 trillion edges on 128 machines with 256 GiB each in just under 10 minutes. Finally, we present a version of shared-memory parallel FM local search that uses$O(m)$space instead of$O(n k)$, reducing peak memory by factor 5.8 on medium-sized graphs without affecting running time.

We present new refinement heuristics for the balanced graph partitioning problem that break with an age-old rule. Traditionally, local search only permits moves that keep the block sizes balanced (below a size constraint). In this work, we demonstrate that admitting large temporary balance violations drastically improves solution quality. The effects are particularly strong on irregular instances such as social networks. Designing efficient implementations of this general idea involves both careful selection of candidates for unconstrained moves as well as algorithms for rebalancing the solution later on. We explore a wide array of design choices to achieve this, in addition to our third goal of high parallel scalability. We present compelling experimental results, demonstrating that our parallel unconstrained local search techniques outperform the prior state of the art by a substantial margin. Compared with four state-of-the-art solvers, our new technique finds 75% of the best solutions on irregular graphs. We achieve a 9.6% improvement in edge cut over the next best competitor, while being only 7.7% slower in the geometric mean.

The Message-Passing Interface (MPI) and C++ form the backbone of high-performance computing, but MPI only provides $\mathbf{C}$ and Fortran bindings. While this offers great language interoperability, high-level programming languages like C++ make software development quicker and less error-prone.We propose novel $\mathrm{C}_{++}$language bindings that cover all abstraction levels from low-level MPI calls to convenient STL-style bindings, where most parameters are inferred from a small subset of parameters, by bringing named parameters to C++. This enables rapid prototyping and fine-tuning runtime behavior and memory management. A flexible type system and additional safety guarantees help to prevent programming errors.By exploiting C++’s template metaprogramming capabilities, this has (near) zero overhead, as only required code paths are generated at compile time.We demonstrate that our library is a strong foundation for a future distributed standard library using multiple application benchmarks, ranging from text-book sorting algorithms to phylogenetic interference.

Partitioning a graph into blocks of roughly equal weight while cutting only few edges is a fundamental problem in computer science with numerous practical applications. While shared-memory parallel partitioners have recently matured to achieve the same quality as widely used sequential partitioners, there is still a pronounced quality gap between distributed partitioners and their sequential counterparts. In this work, we shrink this gap considerably by describing the engineering of an unconstrained local search algorithm suitable for distributed partitioners. We integrate the proposed algorithm in a distributed multilevel partitioner. Our extensive experiments show that the resulting algorithm scales to thousands of PEs while computing cuts that are, on average, only 3.5% larger than those of a state-of-the-art high-quality shared-memory partitioner. Compared to previous distributed partitioners, we obtain on average 6.8% smaller cuts than the best-performing competitor while being more than 9 times faster.

The Message-Passing Interface (MPI) and C++ form the backbone of high-performance computing and algorithmic research in the field of distributed-memory computing, but MPI only provides C and Fortran bindings.This provides good language interoperability, but higher-level programming languages make development quicker and less error-prone.We propose novel C++ language bindings designed to cover the whole range of abstraction levels from low-level MPI calls to convenient STL-style bindings, where most parameters are inferred from a small subset of the full parameter set.This allows for both rapid prototyping and fine-tuning of distributed code with predictable runtime behavior and memory management.Using template-metaprogramming, only code paths required for computing missing parameters are generated at compile time, which results in (near) zero-overhead bindings.

Addressing the challenges of processing massive graphs, which are prevalent in diverse fields such as social, biological, and technical networks, we introduce HeiStreamE and FreightE, two innovative (buffered) streaming algorithms designed for efficient edge partitioning of large-scale graphs. HeiStreamE utilizes an adapted Split-and-Connect graph model and a Fennel-based multilevel partitioning scheme, while FreightE partitions a hypergraph representation of the input graph. Besides ensuring superior solution quality, these approaches also overcome the limitations of existing algorithms by maintaining linear dependency on the graph size in both time and memory complexity with no dependence on the number of blocks of partition. Our comprehensive experimental analysis demonstrates that HeiStreamE outperforms current streaming algorithms and the re-streaming algorithm 2PS in partitioning quality (replication factor), and is more memory-efficient for real-world networks where the number of edges is far greater than the number of vertices. Further, FreightE is shown to produce fast and efficient partitions, particularly for higher numbers of partition blocks.

Abstract We describe the engineering of the distributed-memory multilevel graph partitioner . It scales to (at least) 8192 cores while achieving partitioning quality comparable to widely used sequential and shared-memory graph partitioners. In comparison, previous distributed graph partitioners scale only in more restricted scenarios and often induce a considerable quality penalty compared to non-distributed partitioners. When partitioning into a large number of blocks, they even produce infeasible solution that violate the balancing constraint. achieves its robustness by a scalable distributed implementation of the deep-multilevel scheme for graph partitioning. Crucially, this includes new algorithms for balancing during refinement and coarsening.

A directed acyclic hypergraph is a generalized concept of a directed acyclic graph, where each hyperedge can contain an arbitrary number of tails and heads.Directed hypergraphs can be used to model data flow and execution dependencies in streaming applications.Thus, hypergraph partitioning algorithms can be used to obtain efficient parallelizations for multiprocessor architectures.However, an acyclicity constraint on the partition is necessary when mapping streaming applications to embedded multiprocessors due to resource restrictions on this type of hardware.The acyclic hypergraph partitioning problem is to partition the hypernodes of a directed acyclic hypergraph into a given number of blocks of roughly equal size such that the partition is acyclic while minimizing an objective function.Here, we contribute the first n-level algorithm for the acyclic hypergraph partitioning problem.Based on this, we engineer a memetic algorithm to further reduce communication cost, as well as to improve scheduling makespan on embedded multiprocessor architectures.Experiments indicate that our algorithm outperforms previous algorithms that focus on the directed acyclic graph case which have previously been employed in the application domain.Moreover, our experiments indicate that using the directed hypergraph model for this type of application yields a significantly smaller makespan.

Partitioning a graph into blocks of "roughly equal" weight while cutting only few edges is a fundamental problem in computer science with a wide range of applications. In particular, the problem is a building block in applications that require parallel processing. While the amount of available cores in parallel architectures has significantly increased in recent years, state-of-the-art graph partitioning algorithms do not work well if the input needs to be partitioned into a large number of blocks. Often currently available algorithms compute highly imbalanced solutions, solutions of low quality, or have excessive running time for this case. This is due to the fact that most high-quality general-purpose graph partitioners are multilevel algorithms which perform graph coarsening to build a hierarchy of graphs, initial partitioning to compute an initial solution, and local improvement to improve the solution throughout the hierarchy. However, for large number of blocks, the smallest graph in the hierarchy that is used for initial partitioning still has to be large. In this work, we substantially mitigate these problems by introducing deep multilevel graph partitioning and a shared-memory implementation thereof. Our scheme continues the multilevel approach deep into initial partitioning - integrating it into a framework where recursive bipartitioning and direct k-way partitioning are combined such that they can operate with high performance and quality. Our integrated approach is stronger, more flexible, arguably more elegant, and reduces bottlenecks for parallelization compared to existing multilevel approaches. For example, for large number of blocks our algorithm is on average at least an order of magnitude faster than competing algorithms while computing partitions with comparable solution quality. At the same time, our algorithm consistently produces balanced solutions. Moreover, for small number of blocks, our algorithms are the fastest among competing systems with comparable quality.

Edge-centric distributed computations have appeared as a recent technique to improve the shortcomings of think-like-a-vertex algorithms on large scale-free networks. In order to increase parallelism on this model, edge partitioning—partitioning edges into roughly equally sized blocks—has emerged as an alternative to traditional (node-based) graph partitioning. In this work, we develop a fast parallel split-and-connect graph construction algorithm in the distributed setting and show that combining our parallel construction with advanced parallel node partitioning algorithms yields high-quality edge partitions in a scalable way. Our technique scales to networks with billions of edges, and runs efficiently on thousands of PEs. Our extensive experiments show that our algorithm computes solutions of high quality on large real-world networks and large hyperbolic random graphs—which have a power law degree distribution and are therefore specifically targeted by edge partitioning.