Research map / Graph learning / Graph algorithms and clustering
Continuous Partitioning for Graph-Based Semi-Supervised Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CutSSL, a nonconvex continuous quadratic program (homotopy in a diagonal perturbation S=sD, solved by ADMM) that recovers integer label assignments for graph-based semi-supervised learning under cardinality constraints.
Problem
Laplace learning for graph-based semi-supervised learning degenerates at low label rates and under class/label imbalance, and thresholding its continuous outputs gives poor discrete predictions.
Approach
Formulate semi-supervised k-way partitioning as an exact continuous nonconvex quadratic program with cardinality constraints, perturb the Laplacian by sD along a homotopy path so minimizers approach 0-1 label assignments, and solve it with ADMM; also shows mean-shift Laplace learning approximates the cardinality-constrained convex problem.
Key results
- On CIFAR-10 with 1 label per class, CutSSL reaches 44.7% accuracy versus 41.8% for Poisson-MBO, the strongest baseline in that table.
- On OGBN-Arxiv with 1 label per class, CutSSL attains 52.37% accuracy versus 46.94% for Poisson-MBO.
- On OGBN-Products with 1 label per class, CutSSL attains 54.22% accuracy versus 49.07% for Poisson-MBO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CutSSL instead of Poisson-MBO | CIFAR-10 graph SSL · CIFAR-10, 1 label/class | accuracy: 41.8 (6.5) -> 44.7 (5.9) | Helped |
| Use CutSSL instead of Poisson-MBO | OGBN-ARXIV graph SSL · OGBN-ARXIV, rate=1 | accuracy: 46.94% -> 52.37% | Helped |
| Use CutSSL instead of Poisson-MBO | OGBN-PRODUCTS graph SSL · OGBN-PRODUCTS, rate=1 | accuracy: 49.07% -> 54.22% | Helped |
| Use CutSSL instead of Poisson-MBO | MNIST graph SSL · MNIST, 1 label/class | accuracy: 96.5 (2.6) -> 97.5 (0.1) | Helped |
| Use CutSSL instead of Poisson-MBO | Fashion-MNIST graph SSL · FASHIONMNIST, 1 label/class | accuracy: 62.0 (5.7) -> 64.3 (4.6) | Helped |
| Use CutSSL instead of Poisson-MBO under imbalanced label rates | CIFAR-10 graph SSL · CIFAR-10, imbalanced labels | accuracy: 55.0 -> 59.4 | Helped |
| Use CutSSL instead of Poisson-MBO under imbalanced class sizes | CIFAR-10 graph SSL · CIFAR-10, class imbalance | accuracy: 52.3 -> 54.5 | Helped |
| Use discrete CutSSL predictions instead of Poisson predictions | CIFAR-10, low-label SSL · CIFAR-10, 1 label/class, smallest-margin 5% | accuracy: 29.1 (2.1) -> 36.2 (4.9) | Helped |
| Use CutSSL instead of Poisson-MBO | Cora graph SSL · CORA, 1 label/class | accuracy: 59.9 (6.4) -> 67.4 (3.4) | Helped |
| Set S = sD rather than S = sI (ablation) | CutSSL on MNIST · MNIST, 1 label/class | accuracy: 97.4 (0.1) -> 97.5 (0.1) | No clear effect |
| Set S = sD rather than S = sI (ablation) | CutSSL on Fashion-MNIST · FASHIONMNIST, 1 label/class | accuracy: 63.3 (4.8) -> 64.3 (4.6) | Helped |
| Use a 15-nearest-neighbor graph rather than a 10-nearest-neighbor graph (ablation) | CutSSL on CIFAR-10 · CIFAR-10, 1 label/class | accuracy change: +0.16 (2.2) | Helped |
Surprising findings
- Mean-shift Laplace learning is shown to be an approximate solution to a cardinality-constrained Laplace problem, and the paper reports that solving that problem exactly yields only 1-2% gains at very low label rates and marginal gains at higher rates.
- Least-squares spectral relaxation (LE-SSL) performs significantly worse than CutSSL, suggesting that searching near binary vectors is critical.
Limitations
- Global optimality is not guaranteed because the quadratic objective is nonconvex and ADMM may converge to poor local minima; strict descent is not guaranteed.
- Results depend on the choice of graph construction and the homotopy sequence of s, which is a hyperparameter.
- Asymptotic consistency and rigorous analysis of cut-based SSL remain open.
Experimental setup
Datasets: MNIST Fashion-MNIST CIFAR-10 Cora Citeseer Pubmed OGBN-Arxiv OGBN-Products
Benchmarks: MNIST Fashion-MNIST CIFAR-10 Cora Citeseer Pubmed OGBN-Arxiv OGBN-Products
Metrics: accuracy cut value runtime (s)
Baselines: Laplace learning Mean-shift Laplace learning Poisson learning Poisson-MBO Volume-MBO LE-SSL Sparse LP GraphHop P-Laplace
Builds on: Laplace learning Poisson learning Hager and Krylyuk continuous graph partitioning volume-constrained MBO
Closest papers by meaning
- Exact Combinatorial Multi-Class Graph Cuts for Semi-Supervised Learning (AAAI 2026 · similarity 0.91)
- Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver (AAAI 2016 · similarity 0.90)
- Optimal Block-wise Asymmetric Graph Construction for Graph-based Semi-supervised Learning (NeurIPS 2023 · similarity 0.89)
- Data driven semi-supervised learning (NeurIPS 2021 · similarity 0.88)
- Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering (NeurIPS 2020 · similarity 0.87)
- HGDL: Heterogeneous Graph Label Distribution Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.