Robust Graph-Based Semi-Supervised Learning via $p$-Conductances
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909490615418880 |
|---|---|
| author | Robertson, Sawyer Jack Holtz, Chester Wan, Zhengchao Mishne, Gal Cloninger, Alexander |
| author_facet | Robertson, Sawyer Jack Holtz, Chester Wan, Zhengchao Mishne, Gal Cloninger, Alexander |
| contents | We study the problem of semi-supervised learning on graphs in the regime where data labels are scarce or possibly corrupted. We propose an approach called $p$-conductance learning that generalizes the $p$-Laplace and Poisson learning methods by introducing an objective reminiscent of $p$-Laplacian regularization and an affine relaxation of the label constraints. This leads to a family of probability measure mincut programs that balance sparse edge removal with accurate distribution separation. Our theoretical analysis connects these programs to well-known variational and probabilistic problems on graphs (including randomized cuts, effective resistance, and Wasserstein distance) and provides motivation for robustness when labels are diffused via the heat kernel. Computationally, we develop a semismooth Newton-conjugate gradient algorithm and extend it to incorporate class-size estimates when converting the continuous solutions into label assignments. Empirical results on computer vision and citation datasets demonstrate that our approach achieves state-of-the-art accuracy in low label-rate, corrupted-label, and partial-label regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08873 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robust Graph-Based Semi-Supervised Learning via $p$-Conductances Robertson, Sawyer Jack Holtz, Chester Wan, Zhengchao Mishne, Gal Cloninger, Alexander Machine Learning Discrete Mathematics Optimization and Control 68Q87, 90C35, 05C90, 90C53 We study the problem of semi-supervised learning on graphs in the regime where data labels are scarce or possibly corrupted. We propose an approach called $p$-conductance learning that generalizes the $p$-Laplace and Poisson learning methods by introducing an objective reminiscent of $p$-Laplacian regularization and an affine relaxation of the label constraints. This leads to a family of probability measure mincut programs that balance sparse edge removal with accurate distribution separation. Our theoretical analysis connects these programs to well-known variational and probabilistic problems on graphs (including randomized cuts, effective resistance, and Wasserstein distance) and provides motivation for robustness when labels are diffused via the heat kernel. Computationally, we develop a semismooth Newton-conjugate gradient algorithm and extend it to incorporate class-size estimates when converting the continuous solutions into label assignments. Empirical results on computer vision and citation datasets demonstrate that our approach achieves state-of-the-art accuracy in low label-rate, corrupted-label, and partial-label regimes. |
| title | Robust Graph-Based Semi-Supervised Learning via $p$-Conductances |
| topic | Machine Learning Discrete Mathematics Optimization and Control 68Q87, 90C35, 05C90, 90C53 |
| url | https://arxiv.org/abs/2502.08873 |