用近线性时间求解非线性图 p-拉普拉斯半监督学习，解决标签稀疏时模型失效问题。
A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$
- 通过参数延续法在 p 值上迭代求解非线性 p-拉普拉斯能量
- 在 228 个图上实现比直接分解快 1.5–14 倍，大图仅需数分钟
- 特别适合标签极少但数据量大的场景，如小样本学习
基于图的半监督学习通过最小化类狄利克雷能量，在相似性图上传播少量标签。标准二次型（p=2）可转化为单次图拉普拉斯求解，但在标签稀疏时失效：当维度 d≥2 时，增加未标记数据会使 p=2 估计趋近常数函数（Nadler-Srebro-Zhou）。良好定义需采用非线性 p-拉普拉斯能量，且 p>d。现有求解器将其转化为一系列加权拉普拉斯求解，但其参考实现使用直接稀疏分解或 ichol 预条件共轭梯度法。将近线性拉普拉斯求解器直接接入存在困难：大 p 值下导纳权重在梯度平缓边附近退化，导致系统近乎奇异，无阻尼外层迭代则停滞不前。本文填补该空白：将 p-拉普拉斯半监督学习重构为源形式非线性拉普拉斯流 $Bρ_p(B^ op x)=b$，并采用阻尼弦-牛顿参数延续法求解。每个线性化系统保持良好条件，可交由近线性拉普拉斯引擎处理。在规模缩放图族上，实测耗时为 $m^{0.96}$–$m^{1.02}$ 每族（近似乔列斯基默认），跨 228 个 SuiteSparse 图的合并拟合得 $m^{1.19}$，优于直接分解的 $m^{1.45}$；可处理含 6.8×10⁷ 条边的社交网络，仅需数分钟。内存是主要瓶颈：乔列斯基填充达图非零元的 10–280 倍，而本文方法为 $O(m)$ 层次。相比发布的 FCL 求解器，在相同精度下快 1.5–14 倍。在 MNIST 10-NN 上，$p=3$ 仅需每类一个标签即达 64% 准确率，而 $p=2$ 仅为 36%。代码：https://github.com/orenlivne/np。
原文摘要 · Abstract (English)
Graph-based semi-supervised learning (SSL) propagates a few labels over a similarity graph by minimizing a Dirichlet-type energy. The standard quadratic ($p=2$) energy reduces to a single graph-Laplacian solve, but it degenerates exactly where SSL is most useful when labels are scarce: gathering more unlabeled data drives the $p=2$ estimate to a near-constant function whenever $d\ge2$ (Nadler-Srebro-Zhou). Well-posedness requires the nonlinear $p$-Laplacian energy with $p>d$. Existing solvers reduce this to a sequence of weighted Laplacian solves, but their reference implementations use a direct sparse factorization or ichol-preconditioned CG instead. Plugging a near-linear Laplacian solver is not straightforward: at large $p$ the conductance weights degenerate near flat-gradient edges, making the system nearly singular and causing stagnation without a damped outer iteration. We close this gap. Recasting $p$-Laplacian SSL as a source-form nonlinear Laplacian flow $Bρ_p(B^\top x)=b$ and solving by damped chord-Newton continuation in $p$, every linearized system stays well-conditioned and can be delegated to a near-linear Laplacian engine. On size-scaled graph families the wall-clock is empirically $m^{0.96}$-$m^{1.02}$ per family (approximate Cholesky default), and a pooled fit across 228 SuiteSparse graphs gives $m^{1.19}$ vs.\ $m^{1.45}$ for direct factorization; the solver handles a $6.8\times10^7$-edge social network in minutes. Memory is the binding constraint: Cholesky fill reaches $10$-$280\times$ the graph nonzeros vs.\ our $O(m)$ hierarchy. Against the released FCL solver we are $1.5$-$14\times$ faster at matched accuracy. On MNIST $10$-NN, $p=3$ scores $64\%$ at one label per class vs.\ $36\%$ for $p=2$. Code: https://github.com/orenlivne/np.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。