Fast SDP relaxations of graph cut clustering, transduction, and other combinatorial problems

TEP De Bie, N Cristianini

Research output: Contribution to journalArticle (Academic Journal)peer-review

42 Citations (Scopus)

Abstract

The rise of convex programming has changed the face of many research fields in recent years, machine learning being one of the ones that benefitted the most. A very recent developement, the relaxation of combinatorial problems to semi-definite programs (SDP), has gained considerable attention over the last decade (Helmberg, 2000; De Bie and Cristianini, 2004a). Although SDP problems can be solved in polynomial time, for many relaxations the exponent in the polynomial complexity bounds is too high for scaling to large problem sizes. This has hampered their uptake as a powerful new tool in machine learning. In this paper, we present a new and fast SDP relaxation of the normalized graph cut problem, and investigate its usefulness in unsupervised and semi-supervised learning. In particular, this provides a convex algorithm for transduction, as well as approaches to clustering. We further propose a whole cascade of fast relaxations that all hold the middle between older spectral relaxations and the new SDP relaxation, allowing one to trade off computational cost versus relaxation accuracy. Finally, we discuss how the methodology developed in this paper can be applied to other combinatorial problems in machine learning, and we treat the max-cut problem as an example.
Translated title of the contributionFast SDP relaxations of graph cut clustering, transduction, and other combinatorial problems
Original languageEnglish
Pages (from-to)1409 - 1436
Number of pages28
JournalJournal of Machine Learning Research
Volume7
Publication statusPublished - Jul 2006

Bibliographical note

Publisher: JMLR

Fingerprint

Dive into the research topics of 'Fast SDP relaxations of graph cut clustering, transduction, and other combinatorial problems'. Together they form a unique fingerprint.

Cite this