Margin Based Transductive Graph Cuts Using Linear Programming
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
Text
Pelckmans et al. "Margin Based Transductive Graph Cuts Using Linear Programming." Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007.Markdown
[Pelckmans et al. "Margin Based Transductive Graph Cuts Using Linear Programming." Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007.](https://mlanthology.org/aistats/2007/pelckmans2007aistats-margin/)BibTeX
@inproceedings{pelckmans2007aistats-margin,
title = {{Margin Based Transductive Graph Cuts Using Linear Programming}},
author = {Pelckmans, K. and Shawe-Taylor, J. and Suykens, J.A.K. and De Moor, B.},
booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics},
year = {2007},
pages = {363-370},
volume = {2},
url = {https://mlanthology.org/aistats/2007/pelckmans2007aistats-margin/}
}