Graph Partition - Spectral Partitioning and Spectral Bisection

Spectral Partitioning and Spectral Bisection

Given a graph with adjacency matrix A, where an entry A_ij implies an edge between node i and j, and degree matrix D, which is a diagonal matrix, where each diagonal entry of a row i, d_ii, represents the node degree of node i. The Laplacian of the matrix L is defined as L = D − A. Now, a ratio-cut partition for graph G = (V, E) is defined as a partition of V into disjoint U, and W, such that cost of cut(U,W)/(|U|·|W|) is minimized.

In such a scenario, the second smallest eigenvalue (λ) of L, yields a lower bound on the optimal cost (c) of ratio-cut partition with c ≥ λ/n. The eigenvector (V) corresponding to λ, called the Fiedler vector, bisects the graph into only two communities based on the sign of the corresponding vector entry. Division into a larger number of communities is usually achieved by repeated bisection, but this does not always give satisfactory results. The examples in Figures 1,2 illustrate the spectral bisection approach.

Minimum cut partitioning however fails when the number of communities to be partitioned, or the partition sizes are unknown. For instance, optimizing the cut size for free group sizes puts all vertices in the same community. Additionally, cut size may be the wrong thing to minimize since a good division is not just one with small number of edges between communities. This motivated the use of Modularity (Q) as a metric to optimize a balanced graph partition. The example in Figure 3 illustrates 2 instances of the same graph such that in (a) modularity (Q) is the partitioning metric and in (b), ratio-cut is the partitioning metric. However, it has recently demonstrated that Q suffers a resolution limit, what produces unreliable results when dealing with small communities. In this context, Surprise has been proposed as a novel promising approach for evaluating the quality of a partition.