George Karypis and collaborator receive SC21 test of time award for 1998 graph partitioning paper

George Karypis, an Amazon senior principal scientist within the Amazon Web Services organization, has been awarded the SC21 Test of Time Award for a 1998 paper he coauthored which presented algorithms that have subsequently been applied in diverse application domains, from multi-physics scientific simulations and VLSI computer-aided design systems, to database and geographic information systems.

The paper, “Multilevel Algorithms for Multi-constraint Graph Partitioning”, introduced multi-constraint graph partitioning algorithms that address the need to load balance multi-phase scientific simulations across high-performance computing system nodes to enable efficient parallel execution of computations when each mesh element requires different computation resources (e.g., CPU cycles, memory and network bandwidth). Karypis coauthored the paper with fellow University of Minnesota professor Vipin Kumar.

“The paper generalized the standard min-cut balanced graph partitioning problem to one that seeks a min-cut partitioning that satisfies multiple balancing constraints, analyzes the feasibility of the partitions, and presents efficient and effective multilevel algorithms for computing them,” Karypis explained.

The need to compute graph partitions that simultaneously satisfy multiple constraints arise in many domains, and the algorithms introduced in the paper have subsequently been used for developing electronic design automation (EDA) tools for field programmable gate arrays (FPGA), determining electoral districts that address US states’ different requirements, partitioning the computational graphs of large deep-learning models, and computations performed during graph neural network training, among other applications. The algorithms also have been incorporated into the Metis, ParMetis and hMetis graph and hypergraph partitioning software applications.

How graph partitioning algorithms work

In parallel and distributed processing, sparse graphs are often used to model the computational tasks (via vertices) and their interactions (via edges). In these graphs, each vertex has a weight that corresponds to the amount of computation associated with it, and each edge has a weight that corresponds to the amount of data that needs to be exchanged.

Graph partitioning algorithms are used to divide the graph into k parts (where k is usually the number of processors/systems) and assign the tasks corresponding to the vertices of each partition to a single processor or system for execution. For the computations to be performed efficiently, the sum of the weights of the tasks of each partition must be nearly identical across the different partitions, leading to a work assignment that is load balanced.

At the same time, to reduce communication costs, the partitioning needs to minimize the number of edges that cross partition boundaries. The class of graph partitioning algorithms that meet these requirements are typically called bounded-capacity min-cut graph partitioning algorithms, where the term “bounded capacity” refers to the balance constraint and the term “min-cut” relates to the objective of minimizing the sum of the weights of the edges that cross partition boundaries.

Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions.

In many applications, the bounded capacity min-cut formulation is not sufficient to meet requirements. For example, a computation’s tasks may require different amounts of computation and memory. If a standard bounded-capacity algorithm is used to balance the computations, it could lead to a task assignment that is severely unbalanced in terms of memory requirements. If the bounded-capacity algorithm is used to compute a partitioning that balances the memory requirements, it could lead to a computations load imbalance.

In either case, Karypis explains, the overall performance of the system will be negatively impacted. “Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions,” he said.

To address these challenges, the paper’s coauthors introduced a model that allows an application to express its multiple balancing requirements, and developed multilevel graph partitioning algorithms that produce partitions that address the constraints, or come close.

“Since our formulation and algorithms can simultaneously satisfy multiple balancing criteria, I refer to them as multi-constraint partitioning algorithms,” Karypis explained.

Other honors

The SC21 Test of Time Award is one of several Karypis has earned within the past year.

In May, he received the Distinguished Contributions Award during the 2021 Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD).  Karypis, who also is a professor within the University of Minnesota’s computer science and engineering department, was honored for his outstanding contributions to the field of knowledge discovery and data mining, as well as for his long-standing participation in PAKDD.

In November 2020, Karypis was awarded the 10-Year-Highest Impact Award at the 2020 IEEE Conference on Data Mining (ICDM).

More recently, Karypis presented a talk, “Deep Graph Library: Deep Graph learning at scale”, at the AWS Machine Learning Summit held earlier this year.  Prior to his presentation, Amazon Science interviewed Karypis about his forthcoming talk on deep graph neural networks.