The Constrained Laplacian Rank Algorithm for Graph-Based Clustering

Graph-based clustering methods perform clustering on a fixed input data graph. If this initial construction is of low quality then the resulting clustering may also be of low quality. Moreover, existing graph-based clustering methods require post-processing on the data graph to extract the clustering indicators. We address both of these drawbacks by allowing the data graph itself to be adjusted as part of the clustering procedure. In particular, our Constrained Laplacian Rank (CLR) method learns a graph with exactly k connected components (where k is the number of clusters). We develop two versions of this method, based upon the L1-norm and the L2-norm, which yield two new graph-based clustering objectives. We…

• NS
  National Science Foundation

  Awards: 1356628, 1302675, DBI 1356628, 1117965, 1344152
• NI
  National Institutes of Health

  Awards: R01 AG049371, AG049371, NIH R01