Eric P. Xing and Michael I. Jordan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1265

, 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 <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.

---

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},
    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