Multi-way graph partitioning via generalized eigenvalues and eigenvectors

Graphs are very useful objects in applications including social networks, computer vision, databases and scientific computing. Graph partitioning is a basic task that is applied in nearly all situations, and it is very well studied for 2-way partitioning, i.e. for the case when the goal is to disconnect the graph into two components. However, the problem of multi-way partitioning is still not very well understood, and a common solution involves the recursive application of 2-way partitioning algorithms. New algorithms and approaches are needed as multi-way partitioning is very useful in applications such as community detection in social networks.

 In this work we propose a novel multi-way partitioning algorithm that is based on the solution of a sequence of generalized eigenvalue problems with pairs of graphs and their Laplacians. We show that the approach has many attractive  theoretical properties. It is also very fast since it is based on fast nearly-linear time linear system solvers. We report on the quality of the computed decomposition, comparing them with that of a simple recursive spectral partitioning approach.