UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Margin based transductive graph cuts using linear programming

Pelckmans, K; Shawe-Taylor, J; Suykens, JAK; De Moor, B; (2007) Margin based transductive graph cuts using linear programming. In: (pp. 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
UCL classification: UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Engineering Science
URI: http://discovery.ucl.ac.uk/id/eprint/79216
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item