Continuous Partitioning for Graph-Based Semi-Supervised Learning

Laplace learning algorithms for graph-based semi-supervised learning have been shown to suffer from degeneracy at low label rates and in imbalanced class regimes. Here, we propose CutSSL: a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming, which provably obtains integer solutions. Our framework is naturally motivated by an exact quadratic relaxation of a cardinality-constrained minimum-cut graph partitioning problem. Furthermore, we show our formulation is related to an optimization problem whose approximate solution is the mean-shifted Laplace learning heuristic, thus providing new insight into the performance of this heuristic. We demonstrate that CutSSL significantly surpasses the current state-of-the-art on k-nearest neighbor graphs and large real-world graph benchmarks across a variety of label rates, class imbalance, and label imbalance regimes. Our implementation is available on github 1 . Preliminaries In this section, we review graph semi-supervised learning, Laplace learning, the combinatorial minimum cut problem, and an associated continuous extension. Laplace learning Let V = v 1 , v 2 , . . . , v M denote the M vertices of the graph G with weight matrix W whose entries w ij ≥ 0 are the edge weights between v i and v j . We assume the graph is symmetric, i.e., w ij = w ji . We define the degree d i = n j=1 w ij . Without loss of generality, we assume the first m vertices l = v 1 , v 2 , . . . , v m are assigned labels y 1 , y 2 , . . . , y m , where 0 < m ≪ M . In the context of k-class classification we take each y i to be one of the k standard basis vectors e 1 , e 2 , . . . , e k of the form e i = (0, . . . 0, 1, 0, . . . , 0), i.e. a one-hot row vector. Let n denote the number of unlabeled vertices, i.e. n = M -m. The problem of graph-based semi-supervised learning is to smoothly propagate the labels over the unlabeled vertices u = v m+1 , v m+2 , . . . , v M .