論文の概要: A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$

• arxiv url: http://arxiv.org/abs/2607.03503v1
• Date: Fri, 03 Jul 2026 17:24:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:29.634596
• Title: A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$
• Title（参考訳）: グラフ$p$-Laplacian Semi-Supervised Learning における約Linear-Time Solver
• Abstract要約: グラフベースの半教師付き学習(SSL)は、ディリクレ型エネルギーを最小化することにより、類似性グラフ上にいくつかのラベルを伝播する。 Wecast $p$-Laplacian SSL as a source-form non Laplacian flow。 スパースグラフは直接分解に対して$m1.19$対$m1.45$を与える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: グラフベースの半教師付き学習(SSL)は、ディリクレ型エネルギーを最小化することにより、類似性グラフ上にいくつかのラベルを伝播する。 標準的な二次(p=2$)エネルギーは1つのグラフ-ラプラシアン解に還元されるが、ラベルが不足している場合にSSLがもっとも有用である場所を正確に縮退する: ラベルのないデータを集めると、$d\ge2$ (Nadler-Srebro-Zhou) が常に$d\ge2$ (Nadler-Srebro-Zhou) となる。 正当性には非線形な$p$-ラプラシアンエネルギーと$p>d$が必要である。 既存の解法は、これを重み付けされたラプラシアン解の列に還元するが、それらの参照実装は代わりに直接スパース分解(英語版)(direct sparse factorization)または ichol-preconditioned CG を用いる。 ほぼ直線的なラプラシアン・ソルバを接続するのは簡単ではない: 導電性重みは、平坦な勾配の縁付近で縮退し、システムをほぼ特異にし、減衰した外部イテレーションなしで停滞を引き起こす。 私たちはこのギャップを埋めます。 ソース形式非線形ラプラシアンフローとして$p$-ラプラシアンSSLをリキャストし、$Bρ_p(B^\top x)=b$と、減衰したコード-ニュートン継続による$p$の解法により、全ての線形系はよく調和し、ほぼ線形のラプラシアンエンジンに委譲できる。 サイズスケールのグラフ族では、壁時計は経験的に$m^{0.96}$-$m^{1.02}$ 1 family (approximate Cholesky default)であり、プールされた228 SuiteSparseグラフのグラフは$m^{1.19}$に対して$m^{1.19}$である。 直接因数分解のために$$$m^{1.45}$; 解法は6.8\times10^7$-edge ソーシャルネットワークを数分で処理する。 Cholesky fill は 10$-$280\times$ the graph nonzeros vs. O(m)$ 階層を指定します。 リリースされたFCLソルバに対して、一致する精度で1.5$-14\times$高速です。 MNIST 10$-NN では、$p=3$ スコアはクラスごとに 64\% である。 は$36\%$ for $p=2$。 コード:https://github.com/orenlivne/np。

関連論文リスト

• Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers [9.297355862757838]
  本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 有界時間 $(varepsilon,)$-differentially private algorithm を与え、これはすべての$n$-vertex 未重み付きグラフ $G$ に対して非負重み付き合成グラフを出力する。
  論文  参考訳（メタデータ） (2026-07-21T08:35:05Z)
• Scaling Limits of Constant-Stepsize SGD at Flat Minima [5.608222858044445]
  契約駆動チェーンが生成するマルコフ雑音について検討する。 定段数$$の勾配降下(SGD)に対して、最小値を中心とする反復法の不変法則は、長い時間的地平線上でのアルゴリズムの振舞いを記述する。 この振舞いは、平坦なミニマと(部分)四角形尾を持つ凸対象に対して根本的に変化することを示す。
  論文  参考訳（メタデータ） (2026-07-17T17:22:46Z)
• Closed-form $\ell_r$ norm scaling with data for overparameterized linear regression and diagonal linear networks under $\ell_p$ bias [0.0]
  パラメータノルムの族をスケールするために、統一的で高確率な特徴を与える。 次に、降下によって訓練された線形ネットワークについて研究する。
  論文  参考訳（メタデータ） (2025-09-25T13:59:22Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。 ラプラシアン滑らか化が多様体適応であることを証明する。
  論文  参考訳（メタデータ） (2021-06-03T01:20:41Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。