  The graph partitioning problem is widely used and studied in many practical
and theoretical applications. The multilevel strategies represent today one of
the most effective and efficient generic frameworks for solving this problem on
large-scale graphs. Most of the attention in designing the multilevel
partitioning frameworks has been on the refinement phase. In this work we focus
on the coarsening phase, which is responsible for creating structurally 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 coarsenings.
