Multilevel algorithms for partitioning power-law graphs

By Amine Abou-Rjeili, George Karypis. Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, 2006

323 citations recorded by the source corpus.

Graph partitioning is an enabling technology for parallel processing as it allows for the effective decomposition of unstructured computations whose data dependencies correspond to a large sparse and irregular graph. Even though the problem of computing high-quality partitionings of graphs arising in scientific computations is to a large extent well-understood, this is far from being true for emerging HPC applications whose underlying computation involves graphs whose degree distribution follows a power-law curve. This paper presents new multilevel graph partitioning algorithms that are specifically designed for partitioning such graphs. It presents new clustering-based coarsening schemes that identify and collapse together groups of vertices that are highly connected. An experimental evaluation of these schemes on 10 different graphs show that the proposed algorithms consistently and significantly outperform existing state-of-the-art approaches.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/aa8eb7db54fd5c7648b0d3379a431c1590c13072

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Hardware and Architecture

Citations in the corpus

Recent Advances in Graph Partitioning (2013, methodology): “A successful recent approach is to delegate this tradeoff between edge weights and uniformity to an edge rating function [1,102].”
Relaxation-based coarsening and multiscale graph organization (2010, unknown): “However, only the introduction of multilevel methods for partitioning [30, 35, 2, 34, 46, 3, 37, 4, 27, 29, 1] has really provided a breakthrough in eﬃciency and quality.”
GraphX: a resilient distributed graph system on Spark (2013, background): “In contrast to edge-cuts which have been shown [8, 1, 7] to perform poorly on real-world graphs, there are theoretical [2] and experimental [6] results indicating that real-world graphs have good vertex-cuts.”
PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012, unknown): “Furthermore, power-law graphs are difficult to partition [1, 28] and represent in a distributed environment.”
Evaluation of clustering algorithms for financial risk analysis using MCDM methods (2014, methodology): “The graph is then divided into k-clusters using a minimum cut graph partitioning algorithm, which is based on the multilevel partitioning algorithms in Metis [1,14].”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, background): “The diverse properties inside and among graph datasets raise new challenges to efficiently partition and process such graphs [1, 24, 42].”
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing (2019, background): “ accelerators for several reasons. (i) GCN applications have highly unbalanced non-zero data distributions: non-zeros can be clustered or appear in only a few rows. This leads to computing challenges [1,19,29] due to workload imbalance [40]. Figure1compares the distribution of non-zeros between a ty”