IEEE Transactions on Neural Networks and Learning Systems · 2014 · 28 citations · 50 references
ComputingComputer ScienceData MiningKnowledge RepresentationMachine LearningGraph AnalyticsGraph-based LearningRepresentation LearningGraph Representation LearningMinimum CutMinimum Spanning Tree AlgorithmsPolynomial Time ComplexityPolynomial-time AlgorithmsSpam DetectionTransductive LearningWeb Spam Detection
Despite the great success of graph-based transductive learning methods, most of them have serious problems in scalability and robustness. In this paper, we propose an efficient and robust graph-based transductive classification method, called minimum tree cut (MTC), which is suitable for large-scale data. Motivated from the sparse representation of graph, we approximate a graph by a spanning tree. Exploiting the simple structure, we develop a linear-time algorithm to label the tree such that the cut size of the tree is minimized. This significantly improves graph-based methods, which typically have a polynomial time complexity. Moreover, we theoretically and empirically show that the performance of MTC is robust to the graph construction, overcoming another big problem of traditional graph-based methods. Extensive experiments on public data sets and applications on web-spam detection and interactive image segmentation demonstrate our method's advantages in aspect of accuracy, speed, and robustness.
50
Carsten Rother, Vladimir Kolmogorov, Andrew Blake · ACM Transactions on Graphics · 2004 · 5.8K citations · Full text
Combining labeled and unlabeled data with co-training
Avrim Blum, Tom M. Mitchell · 1998 · 5.6K citations · Full text
Semi-Supervised Learning Literature Survey
Xiaojin Zhu · Minds at UW (University of Wisconsin) · 2005 · 3.9K citations · Full text
Learning with Local and Global Consistency
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal et al. · MPG.PuRe (Max Planck Society) · 2003 · 3.8K citations · Full text