Eric P. Xing and Michael I. Jordan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1265
June 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1265.pdf

The normalized cut (NC) provides a plausible cost function for clustering. Finding an optimal NC is NP-hard, and the well-known spectral graph partition methods rely on a loose spectral relaxation. In this paper, we study a semidefinite programming (SDP) model for the normalized k-cut ( k-NC), a generalization of the conventional NC on bisection to k-section that naturally relates to multi-way clustering. Our SDP relaxation to k-NC provides a tighter lower bound on the cut weight, as well as a better feasible cut, than that of the spectral relaxation. In applications to clustering, however, the improved solution to k-NC does not translate into improvements in clustering -- the results for the SDP approach and spectral relaxations are very similar. We conclude that the normalized cut criterion is useful in terms of leading via various relaxations to reasonable clustering methods, but normalized cut alone does not characterize optimal clusterings.

BibTeX citation:

@techreport{Xing:CSD-03-1265,
    Author = {Xing, Eric P. and Jordan, Michael I.},
    Title = {On Semidefinite Relaxation for Normalized k-cut and Connections to Spectral Clustering},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6240.html},
    Number = {UCB/CSD-03-1265},
    Abstract = {The normalized cut (NC) provides a plausible cost function for clustering. Finding an optimal NC is NP-hard, and the well-known spectral graph partition methods rely on a loose spectral relaxation. In this paper, we study a semidefinite programming (SDP) model for the normalized <i>k</i>-cut (<i>k</i>-NC), a generalization of the conventional NC on bisection to <i>k</i>-section that naturally relates to multi-way clustering. Our SDP relaxation to <i>k</i>-NC provides a tighter lower bound on the cut weight, as well as a better feasible cut, than that of the spectral relaxation. In applications to clustering, however, the improved solution to <i>k</i>-NC does not translate into improvements in clustering -- the results for the SDP approach and spectral relaxations are very similar. We conclude that the normalized cut criterion is useful in terms of leading via various relaxations to reasonable clustering methods, but normalized cut alone does not characterize optimal clusterings.}
}

EndNote citation:

%0 Report
%A Xing, Eric P.
%A Jordan, Michael I.
%T On Semidefinite Relaxation for Normalized k-cut and Connections to Spectral Clustering
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1265
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6240.html
%F Xing:CSD-03-1265