Advanced Coarsening Schemes for Graph Partitioning

By Ilya Safro, Peter Sanders, Christian Schulz. 2012

114 citations recorded by the source corpus.

The graph partitioning problem is widely used and studied in many practical and theoretical applications. Today, multilevel strategies represent one of the most effective and efficient generic frameworks for solving this problem on large-scale graphs. Most of the attention in designing multilevel partitioning frameworks has been on the refinement phase. In this work, we focus on the coarsening phase, which is responsible for creating structures similar to the original but smaller graphs. We compare different matching- and AMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstrate computational results on several classes of graphs that emphasize the running time and quality advantages of different coarsening schemes.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017, neutral): “This is by no means trivial and there exists a large body of literature on this problem [31].”
Graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells (2017, methodology): “Reference [8]; after that, we density-normalize obtained weights [37, 38] as in Reference [8].”
Graph Based Convolutional Neural Network (2016, background): “AMG provides a set of matrices for the interpolation of the input signal f ; the restriction matrix R and the projection matrix P. Downsampling f ∈ RN on G to f̂ ∈ RN̂ on Ĝ is achieved by the multiplication of the signal with the restriction matrix, f̂s,i = R fs,i, whilst the reverse pooling…”
Recent Advances in Graph Partitioning (2013, methodology): “In [179] a simple strategy for checking the quality of such methods was presented.”
vPipe: A Virtualized Acceleration System for Achieving Efficient and Scalable Pipeline Parallel DNN Training (2022, background): “There are many approximate algorithms [11], [12], [16], [48] that tend to be fast (near-linear) but often yield partitions that are worse than those obtained byKL algorithm [13], [23], [41] .”