Margin based Transductive Graph Cuts using Linear Programming

K. Pelckmans, J. Shawe-Taylor, J.A.K. Suykens, B. De Moor
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:363-370, 2007.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v2-pelckmans07a, title = {Margin based Transductive Graph Cuts using Linear Programming}, author = {Pelckmans, K. and Shawe-Taylor, J. and Suykens, J.A.K. and Moor, B. De}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {363--370}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/pelckmans07a/pelckmans07a.pdf}, url = {https://proceedings.mlr.press/v2/pelckmans07a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Margin based Transductive Graph Cuts using Linear Programming %A K. Pelckmans %A J. Shawe-Taylor %A J.A.K. Suykens %A B. De Moor %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-pelckmans07a %I PMLR %P 363--370 %U https://proceedings.mlr.press/v2/pelckmans07a.html %V 2 %X 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.
RIS
TY - CPAPER TI - Margin based Transductive Graph Cuts using Linear Programming AU - K. Pelckmans AU - J. Shawe-Taylor AU - J.A.K. Suykens AU - B. De Moor BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-pelckmans07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 363 EP - 370 L1 - http://proceedings.mlr.press/v2/pelckmans07a/pelckmans07a.pdf UR - https://proceedings.mlr.press/v2/pelckmans07a.html AB - 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. ER -
APA
Pelckmans, K., Shawe-Taylor, J., Suykens, J. & Moor, B.D.. (2007). Margin based Transductive Graph Cuts using Linear Programming. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:363-370 Available from https://proceedings.mlr.press/v2/pelckmans07a.html.

Related Material