DocumentCode :
739269
Title :
MTC: A Fast and Robust Graph-Based Transductive Learning Method
Author :
Yan-Ming Zhang ; Kaizhu Huang ; Guang-Gang Geng ; Cheng-Lin Liu
Author_Institution :
Nat. Lab. of Pattern Recognition, Inst. of Autom., Beijing, China
Volume :
26
Issue :
9
fYear :
2015
Firstpage :
1979
Lastpage :
1991
Abstract :
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.
Keywords :
computational complexity; graph theory; learning (artificial intelligence); pattern classification; trees (mathematics); MTC; graph approximation; graph-based transductive classification method; graph-based transductive learning methods; linear-time algorithm; minimum tree cut; polynomial time complexity; spanning tree; Accuracy; Algorithm design and analysis; Approximation algorithms; Labeling; Optimization; Prediction algorithms; Robustness; Graph-based method; large-scale manifold learning; semisupervised learning (SSL); transductive learning (TL); transductive learning (TL).;
fLanguage :
English
Journal_Title :
Neural Networks and Learning Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
2162-237X
Type :
jour
DOI :
10.1109/TNNLS.2014.2363679
Filename :
6945907
Link To Document :
بازگشت