On spectral partitioning of signed graphs
This work addresses a methodological issue in graph theory for researchers and practitioners, but it is incremental as it critiques and refines existing approaches without introducing a new paradigm.
The paper tackles the problem of spectral partitioning for signed graphs by arguing that the standard graph Laplacian is preferable to the signed Laplacian, as it avoids meaningless partitions and leverages negative eigenvalues to simplify computation of the Fiedler vector.
We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the leading eigenvectors of the signed Laplacian may be meaningless, in contrast to partitioning based on the Fiedler vector of the standard graph Laplacian for signed graphs. We observe that negative eigenvalues are beneficial for spectral partitioning of signed graphs, making the Fiedler vector easier to compute.