Multi-level technique

In mathematics, the multi-level technique is a technique used to solve the graph partitioning problem.

The idea of the multi-level technique is to reduce the magnitude of a graph by merging vertices together, compute a partition on this reduced graph, and finally project this partition on the original graph.

In the first phase the magnitude of the graph is reduced by merging vertices. The merging of vertices is done iteratively: of a graph a new coarser graph is created and of this new coarser graph an even more coarse graph is created. This is done until a certain small magnitude is reached. Thus graphs with different magnitudes are induced.

In the second phase a partition of the graph with the smallest magnitude – the coarsest graph – is computed.

In the third and last phase, the computed partition is iteratively projected back to the original graph. In each iteration a refinement heuristic is applied. The merging of vertices induces a map between vertices of a graph and vertices of its coarser graph which is used for the back projection. A rebalancing to ensure the size of the partition may be needed since vertices not belonging to the same partition may be merged.

The multi-level technique has shown to significantly improve the results, in terms of both quality and running time. Especially when used on heuristics considering the graph only locally, as the multi-level technique constitutes a more global view on the graph.