UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Margin based transductive graph cuts using linear programming

Pelckmans, K; Suykens, JAK; De Moor, B; Shawe-Taylor, J; (2007) Margin based transductive graph cuts using linear programming. In: Journal of Machine Learning Research. (pp. 363 - 370). Gold open access


This paper studies the problem of inferring a partition (or a graph cut) of an undirected deterministic graph where the labels of some nodes are observed thereby bridging a gap between graph theory and probabilistic inference techniques. Given a weighted graph, we focus on the rules of weighted neighbors to predict the label of a particular node. A maximum margin and maximal average margin based argument is used to prove a generalization bound, and is subsequently related to the classical MINCUT approach. From a practical perspective a simple and intuitive, but efficient convex formulation is constructed. This scheme can readily be implemented as a linear program which scales well till a few thousands of (labeled or unlabeled) data-points. The extremal case is studied where one observes only a single label, and this setting is related to the task of unsupervised clustering.

Type:Proceedings paper
Title:Margin based transductive graph cuts using linear programming
Open access status:An open access publication
Publisher version:http://www.jmlr.org/
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record