論文の概要: From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining
- arxiv url: http://arxiv.org/abs/2611.15778v1
- Date: Wed, 11 Nov 2026 17:54:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.245079
- Title: From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining
- Title(参考訳): リンク予測から線形コミュニティ検出へ:グラフ事前学習のための有限サンプル保証
- Abstract要約: リンク予測(LP)はグラフニューラルネットワーク(GNN)の標準事前学習目標である
エッジレベルの目的がノード分類に線形に有用な埋め込みを生成する理由を考察する。
- 参考スコア(独自算出の注目度): 55.67175290377199
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Link prediction (LP) is a standard pretraining objective for graph neural networks (GNNs): hide edges, train an encoder-decoder to predict them, and reuse the node embeddings for downstream node tasks. Despite its empirical success, there is little quantitative theory explaining why an edge-level objective should produce embeddings that are linearly useful for node classification. We study this question in the finite-sample stochastic block model (SBM). For any bounded GNN encoder paired with a symmetric bilinear decoder, we prove a conditional reduction: small population held-out LP excess risk implies small community-classification error for a transductive linear classifier on the learned embeddings. The bound decomposes into an optimization residual, an architectural approximation residual, and explicit statistical terms of order $\tilde{O}(\sqrt{d/n})$ in bounded dense regimes. We further give a constructive few-label classifier: nearest-centroid classification under the positive semidefinite quadratic form $G = W Z^\top Z W$, whose label error is coupled to LP quality. The framework is architecture-agnostic through the approximation residual, and we instantiate this residual as $O(\log n / n)$ for a graph isomorphism network (GIN) with spectral positional encoding and a bilinear decoder. Synthetic SBM experiments validate the theorem chain from LP risk to score error to classification error, and show when the worst-case constants become conservative.
- Abstract(参考訳): リンク予測(LP)は、グラフニューラルネットワーク(GNN)の標準的な事前トレーニング対象である。エッジを隠蔽し、エンコーダデコーダをトレーニングして予測し、下流ノードタスクのノード埋め込みを再利用する。
経験的成功にもかかわらず、なぜエッジレベルの目的がノード分類に線形に有用な埋め込みを生成するべきかを説明する定量的な理論はほとんどない。
本研究では,有限サンプル確率ブロックモデル (SBM) でこの問題を考察する。
対称双線形デコーダと組み合わせた任意の有界GNNエンコーダに対して、条件付きリダクションを証明した: LP過剰リスクは、学習された埋め込み上のトランスダクティブ線形分類器に対する小さなコミュニティ分類誤差を意味する。
境界は最適化残差(英語版)、アーキテクチャ近似残差(英語版)、および順序 $\tilde{O}(\sqrt{d/n})$ の明示的な統計的項に分解される。
さらに、構成的な数ラベル分類器を与える: 正の半定値二次形式$G = W Z^\top Z W$で、ラベル誤差はLP品質に結びついている。
このフレームワークは近似残差を通じてアーキテクチャに依存しず、スペクトル位置符号化と双線型復号器を備えたグラフ同型ネットワーク(GIN)に対して$O(\log n / n)$としてインスタンス化する。
合成SBM実験は、LPリスクからスコアエラーから分類誤差までの定理連鎖を検証し、最悪のケース定数がいつ保守的になるかを示す。
関連論文リスト
- Robust Latent Variable Graphical Models: Exact Recovery and Fundamental Limits [1.7430416823420511]
スパース行列として分解されるガウス精度行列のロバストな推定について検討した。
我々は,フロベニウス推定,グラフ復元,慣性回復のための情報理論上の限界を証明した。
論文 参考訳(メタデータ) (2026-10-19T11:19:49Z) - A Minimal ReLU Classifier on Non-Linearly Separable Data: Convergence and Implicit Bias at and beyond the Edge of Stability [14.08915249552023]
古典的スムーズ性に基づく学習条件に違反しても、勾配降下(GD)設定がネットワークの最適化に成功できることが示される。
具体的には,線形学習体制以外の2つの制度を解析する。
我々は、このスケジュールがより多くのデータに対して$O(/logT)$よりも高速な損失率を達成することを証明している。
論文 参考訳(メタデータ) (2026-10-16T06:31:59Z) - Online Bayesian Node Classification on Inductive Graphs under Distribution Shift [4.12346015436419]
我々は,エンコーダと近似した最終層後層を共同で訓練する変分ベイズ最終層(VBLL)の目的を導入する。
オンラインGVBLLは、データセット毎に最適な精度と負のログ類似性を達成する唯一の方法である。
最強の非GVBLLベースラインよりも最大17ポイント、Ogbn-arxiv14ポイントの精度が向上する。
論文 参考訳(メタデータ) (2026-09-12T02:23:30Z) - Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence [6.908972852063454]
主要声楽アンサンブルは、多種多様なほぼ独立した基礎学習者に対して平均化することにより、ばらつきの低減を実現する。
固定次元マルコフ集合における離散的な分類のために、この現象のミニマックス的特徴付けを行う。
合成マルコフ連鎖、2次元空間格子、128データセットのUCRアーカイブ、アタリDQNアンサンブルに関する実験は、理論的な予測を検証している。
論文 参考訳(メタデータ) (2026-04-15T02:32:30Z) - Semi-Supervised Learning on Graphs using Graph Neural Networks [7.3886152750469]
グラフニューラルネットワーク(GNN)は、半教師付きノード回帰において極めてうまく機能する。
本稿では,複数の共通メッセージパッシングアーキテクチャを含むアグリゲート・アンド・リードアウトモデルについて検討する。
我々は、誤差近似、収束、最適化を分離する急激な非漸近的リスク境界を証明した。
論文 参考訳(メタデータ) (2026-02-19T06:25:13Z) - Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
グラフニューラルネットワーク(GNN)におけるラベルフリップの正確な認証手法を提案する。
本稿では,ノード分類タスクにおける広範囲なGNNアーキテクチャの認証に本手法を適用した。
私たちの研究は、ニューラルネットワークによって引き起こされた毒殺攻撃に対する最初の正確な認証を提示します。
論文 参考訳(メタデータ) (2024-11-30T17:05:12Z) - Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。
本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。
これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
論文 参考訳(メタデータ) (2023-10-14T07:02:54Z) - Semi-Supervised Laplace Learning on Stiefel Manifolds [48.3427853588646]
グラフベースで教師付きサンプルを低ラベルレートで作成するためのフレームワークSequential Subspaceを開発した。
我々の手法は極めて低いレートで、高いラベルレートで達成できる。
論文 参考訳(メタデータ) (2023-07-31T20:19:36Z) - On the Effective Number of Linear Regions in Shallow Univariate ReLU
Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。
我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
論文 参考訳(メタデータ) (2022-05-18T16:57:10Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。