nips nips2009 nips2009-122 nips2009-122-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andrew Guillory, Jeff A. Bilmes
Abstract: We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph. We specifically study methods which choose a single batch of labeled vertices (i.e. offline, non sequential methods). In this setting, we find common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph. Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate. We show improved performance over baseline methods on several real world data sets. 1
P. Afshani, E. Chiniforooshan, R. Dorrigiv, A. Farzan, M. Mirzazadeh, N. Simjour, and H. Zarrabi-Zadeh. On the complexity of finding an unknown cut via vertex queries. In COCOON, 2007. Y. Bengio, O. Delalleau, and N. Le Roux. Label propagation and quadratic criterion. In O. Chapelle, B. Sch¨ lkopf, and A. Zien, editors, Semi-Supervised Learning. MIT Press, 2006. o A. Blum and S. Chawla. Learning from labeled and unlabeled data using graph mincuts. In ICML, 2001. A. Blum, J. Lafferty, M. R. Rwebangira, and R. Reddy. Semi-supervised learning using randomized mincuts. In ICML, 2004. M. Brautbar. Online Learning a Labeling of a Graph. Mining and Learning with Graphs, 2009. O. Chapelle, B. Sch¨ lkopf, and A. Zien. Semi-supervised learning. MIT press, 2006. o W. Cunningham. Optimal attack and reinforcement of a network. Journal of the ACM, 1985. S. Fujishige. Submodular Functions and Optimization. Elsevier Science, 2005. D. Gusfield. Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 1990. S. Hanneke. An analysis of graph cut size for transductive learning. In ICML, 2006. M. Herbster. Exploiting Cluster-Structure to Predict the Labeling of a Graph. In ALT, 2008. M. Herbster, M. Pontil, and L. Wainer. Online learning over graphs. In ICML, 2005. M. Herbster, G. Lever, and M. Pontil. Online Prediction on Large Diameter Graphs. In NIPS, 2008. G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1999. A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. JMLR, 2008. A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2001. K. Pelckmans and J. Suykens. An online algorithm for learning a labeling of a graph. In Mining and Learning with Graphs, 2008. K. Pelckmans, J. Shawe-Taylor, J. Suykens, and B. De Moor. Margin based transductive graph cuts using linear programming. 2007. A. Pucci, M. Gori, and M. Maggini. Semi-supervised active learning in graphical domains. In Mining and Learning With Graphs, 2007. H. Saran and V. V. Vazirani. Finding k cuts within twice the optimal. SIAM Journal on Computing, 1995. M. Wang, X. Hua, Y. Song, J. Tang, and L. Dai. Multi-Concept Multi-Modality Active Learning for Interactive Video Annotation. In International Conference on Semantic Computing, 2007. W. Zhao, J. Long, E. Zhu, and Y. Liu. A scalable algorithm for graph-based active learning. In Frontiers in Algorithmics, 2008. X. Zhu and J. Lafferty. Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003. 9