MTC: A Fast and Robust Graph-Based Transductive Learning Method

• Published in: IEEE transaction on neural networks and learning systems 2015-09, Vol.26 (9), p.1979-1991
• Main Authors: Zhang, Yan-Ming, Huang, Kaizhu, Geng, Guang-Gang, Liu, Cheng-Lin
• Format: Article
• Language: English
• Subjects: Accuracy; Algorithm design and analysis; Approximation algorithms; Graph-based method; Labeling; large-scale manifold learning; Methods; Optimization; Prediction algorithms; Robustness; semisupervised learning (SSL); transductive learning (TL)
• ISSN: 2162-237X; 2162-2388
• DOI: 10.1109/TNNLS.2014.2363679

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.