Fast graph-based semi-supervised learning and its applications

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.

Duke Scholars

Author Kaizhu Huang DKU Faculty