arXiv:2502.08873cs.LGcs.DM2025-02被引 1

通过p-导通率提升图上半监督学习的鲁棒性,应对标签稀疏或错误。

Robust Graph-Based Semi-Supervised Learning via $p$-Conductances

  • 基于p-导通率构建概率割集优化框架,平衡边删减与分布分离。
  • 在低标签率、标签污染等场景下,性能超越现有方法。
  • 适合标签质量差或标注成本高的图数据任务。

我们研究了在标签稀缺或可能被污染的情况下,图上的半监督学习问题。提出一种名为p-导通率学习的方法,通过引入类似p-拉普拉斯正则化的目标函数和标签约束的仿射松弛,推广了p-拉普拉斯与泊松学习方法。该方法形成一族概率测度最小割程序,平衡稀疏边删除与精确分布分离。理论分析揭示其与图上经典变分与概率问题(如随机割、有效电阻、Wasserstein距离)的联系,并为标签经热核扩散时的鲁棒性提供依据。计算上,开发了半光滑牛顿-共轭梯度算法,并扩展以结合类别大小估计,将连续解转换为标签分配。在计算机视觉与引用数据集上的实验表明,该方法在低标签率、标签污染及部分标签场景下达到当前最优准确率。

原文摘要 · Abstract (English)

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.

半监督学习图神经网络鲁棒学习标签噪声

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。