Spectral graph clustering is based on the connection between eigenvectors of the normalized graph Laplacian and low-conductance cuts in the graph. However, this connection is not always direct. It is often the case that the cut corresponding to the lowest graph eigenvectors is far from the optimal cut. The code, based on this NeurIPS paper modifies the input graph in a way that approximately preserves its cluster structure, while forcing its lower eigevectors to 'capture' a better cut.
The code is written in MATLAB and depends on the CMG solver.
To run, install CMG and follow the steps suggested by demo.m
This work has been supported by NSF grants CCF-1149048, CCF-1813374.