MTC: A fast and robust graph-based transductive learning method

Yan Ming Zhang, Kaizhu Huang, Guang Gang Geng, Cheng Lin Liu

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)


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.

Original languageEnglish
Article number6945907
Pages (from-to)1979-1991
Number of pages13
JournalIEEE Transactions on Neural Networks and Learning Systems
Issue number9
Publication statusPublished - 1 Sept 2015


  • Graph-based method
  • large-scale manifold learning
  • semisupervised learning (SSL)
  • transductive learning (TL)


Dive into the research topics of 'MTC: A fast and robust graph-based transductive learning method'. Together they form a unique fingerprint.

Cite this