Label propagation through minimax paths for scalable semi-supervised learning

• A new framework for efficient graph-based semi-supervised learning is proposed.
• The method propagates labels through only a few important paths (“minimax paths”).
• With early-stopping, the method takes O(N) time and space on a graph of N nodes.
• The computational cost of the method is independent of the number of classes.
• The method is especially useful for large-scale data with many classes.

Semi-supervised learning (SSL) is attractive for labeling a large amount of data. Motivated from cluster assumption, we present a path-based SSL framework for efficient large-scale SSL, propagating labels through only a few important paths between labeled nodes and unlabeled nodes. From the framework, minimax paths emerge as a minimal set of important paths in a graph, leading us to a novel algorithm, minimax label propagation. With an appropriate stopping criterion, learning time is (1) linear with respect to the number of nodes in a graph and (2) independent of the number of classes. Experimental results show the superiority of our method over existing SSL methods, especially on large-scale data with many classes.