Fast graph-based semi-supervised learning and its applications

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

Research output: Chapter in Book or Report/Conference proceedingChapterpeer-review


Despite the great success of graph-based transductive learning methods, most of them have serious problems in scalability and robustness. In this chapter, 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 text extraction fromimages demonstrate our method’s advantages in aspect of accuracy, speed, and robustness.

Original languageEnglish
Title of host publicationSemi-Supervised Learning
Subtitle of host publicationBackground, Applications and Future Directions
PublisherNova Science Publishers, Inc.
Number of pages32
ISBN (Electronic)9781536135572
ISBN (Print)9781536135565
Publication statusPublished - 1 Jan 2018


  • Graph-based learning method
  • Semi-supervised learning
  • Transductive learning


Dive into the research topics of 'Fast graph-based semi-supervised learning and its applications'. Together they form a unique fingerprint.

Cite this