Continuous Partitioning for Graph-Based Semi-Supervised Learning

Laplace learning algorithms for graph-based semi-supervised learning have been shown to produce degenerate predictions at low label rates and in imbalanced class regimes, particularly near class boundaries. We propose CutSSL: a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming, which provably obtains \emph{integer} solutions. Our framework is naturally motivated by an \emph{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 Colab\footnote{\url{https: //colab. research. google. com/drive/1tGU5rxE1N5d0KGcNzlvZ0BgRc7_vob7b? usp=sharing}}.

Authors

• Chester Holtz
• Pengwen Chen Singapore Management University
• Zhengchao Wan
• Chung-Kuan Cheng
• Gal Mishne

Keywords

No keywords are indexed for this paper.