Continuous Partitioning for Graph-Based Semi-Supervised Learning
Chester Holtz, Pengwen Chen, Zhengchao Wan, Chung-Kuan Cheng, Gal Mishne
Abstract
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 .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
- Open Graph Benchmark: Datasets for Machine Learning on GraphsWeihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong et al.NeurIPS 2020 · 3,935 citations
- Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label RatesJeff Calder, Brendan Cook, Matthew Thorpe, Dejan SlepcevICML 2020 · 101 citations
Related papers
- Exact Combinatorial Multi-Class Graph Cuts for Semi-Supervised LearningMohammad Mahdi Omati, Yasin Salajeghe, Mahshad Moradi, Arash AminiAAAI 2026
- Semi-supervised Active Learning for Semi-supervised Models: Exploit Adversarial Examples with Graph-based Virtual LabelsJiannan Guo, Haochen Shi, Yangyang Kang, Kun Kuang et al.ICCV 2021 · 38 citations
- Class-Imbalanced Semi-Supervised Learning with Adaptive ThresholdingLan-Zhe Guo, Yufeng LiICML 2022 · 148 citations
- CODE: Towards Partial Label Graph Learning via Coupled Dual SeparationYiyang Gu, Taian Guo, Hang Zhou, Zihao Chen et al.ACM MM 2025
- Contrastive Self-supervised Learning for Graph ClassificationJiaqi Zeng, Pengtao XieAAAI 2021 · 176 citations
