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.
Title
On Semidefinite Relaxation for Normalized k-cut and Connections to Spectral Clustering
Published
2003-06-01
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-03-1265
Type
Text
Extent
10 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
