論文の概要: Provable Guarantees for Spectral Structured Prediction

• arxiv url: http://arxiv.org/abs/2609.18527v1
• Date: Wed, 16 Sep 2026 11:55:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.78799
• Title: Provable Guarantees for Spectral Structured Prediction
• Title（参考訳）: スペクトル構造予測のための確率的保証
• Abstract要約: エッジフリップ雑音を持つ符号付きグラフ上でのバイナリノードラベルの復元について検討する。 我々はノードラベルの近似推論のためのグラフ構造に依存しない理論的保証を開発する。
• 参考スコア（独自算出の注目度）: 19.05034403749305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.
• Abstract（参考訳）: 構造化予測は複数のラベルの同時予測であり、自然言語処理やコンピュータビジョンなど様々な分野で広く使われている。 本稿では,エッジフリップ雑音を持つ符号付きグラフ上でのバイナリノードラベルの復元について,ノイズ符号付き隣接行列の主固有ベクトルの符号からノードラベルを復号する単純なスペクトル法を用いて検討する。 我々は,ノードラベルの近似推定のためのグラフ構造に依存しない理論的保証と,基底真理ノードラベルに対する最大角度偏差の保証を開発する。 行列集中理論と固有ベクトル摂動解析のツールを活用することで、隣接行列のスペクトルギャップ、ノード数、次数分布、ノイズレベルの影響を明示的に定量化する新しい濃度不等式を導出する。 結論として、一般的な結果をチーガー定数に関連付け、グラフの異なるクラスに対して結果を提供する。 我々は理論を検証するためにいくつかの合成実験を行った。 私たちの知識を最大限に活用するために、スペクトルベースのアプローチに関する理論的保証を最初に提供します。 分析の副産物として、独立して興味を持ち、他の機械学習問題に有用な技術結果が導出されます。

関連論文リスト

• Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion [82.7007012514703]
  偏極的目的の下では、線形注意は準最適であり、トレーニング分布に対して平均スペクトル偏極フィルタを学習することしかできないことを示す。 本稿では、入力グラフスペクトルを直接利用し、分布のスペクトル多様性に支配されるマージンによって線形注意を確実に上回るスペクトル注意法を提案する。 ブロックモデルでは、GCAは理想化されたスペクトルアテンション機構に確実に適合する。
  論文  参考訳（メタデータ） (2026-07-07T17:52:17Z)
• Which Graph Shift Operator? A Spectral Answer to an Empirical Question [2.0917449835910404]
  入力信号とラベル部分空間の間の幾何学的歪みを定量化する新しいアライメントゲイン計量を導入する。 我々の理論的解析は、このアライメントをリプシッツ定数のスペクトルプロキシを介して一般化境界に直結させる。 これにより、計算をランク付けし、トレーニング前の任意の予測タスクに対して最適なGSOを選択するという、原則的かつ効率的な基準が得られる。
  論文  参考訳（メタデータ） (2026-02-06T09:59:54Z)
• An Improved and Generalised Analysis for Spectral Clustering [2.2129910930772003]
  グラフ分割のための古典的アルゴリズムであるスペクトルクラスタリングの理論的性能を再検討する。 スペクトルクラスタリングは、最小の固有値が行列表現のスペクトルの他の部分から十分に分離された群に現れる限り、うまく機能することを示す。 本結果は,実世界の合成データセット上でのスペクトルクラスタリングの性能を正確に予測できることを実証する。
  論文  参考訳（メタデータ） (2025-11-28T15:14:27Z)
• Resolving Node Identifiability in Graph Neural Processes via Laplacian Spectral Encodings [9.343292907600913]
  固有ベクトル符号のフリップや固有空間内の回転の基底に不変なラプラシアン位置符号化の理論を提供する。 この符号化により、一定数の観測からノード識別性が得られ、Weisfeiler-Lehmanテストで制約されたアーキテクチャからサンプル複雑度を分離することが証明される。
  論文  参考訳（メタデータ） (2025-11-24T12:20:36Z)
• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  エッジ差分プライバシー(DP)下におけるスペクトルグラフクラスタリングの問題点について検討する。 具体的には, (i) エッジフリップによるグラフ摂動と, エッジプライバシを強制する隣接行列シャッフルを併用したグラフ摂動, (ii) 次元と複雑性の複雑さを低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフプロジェクション, (iii) 収束性を維持しながらエッジDPを確保するために反復的にガウス雑音を分散するノイズの多いパワーイテレーション手法である。
  論文  参考訳（メタデータ） (2025-10-08T15:30:27Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。 合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning [33.05104609131764]
  オープンワールド半教師あり学習は、未知のデータに既知のクラスと新しいクラスの両方を推定することを目的としている。 本稿では,オープンワールド設定に適したグラフ理論フレームワークを定式化する。 我々のグラフ理論フレームワークは実用的なアルゴリズムを照らし、保証を提供する。
  論文  参考訳（メタデータ） (2023-11-06T21:15:09Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  従来の知恵は、スペクトル畳み込みネットワークは無向グラフ上にしか展開できないと規定している。 ここでは、このグラフフーリエ変換への伝統的な依存が超フルであることを示す。 本稿では,新たに開発されたフィルタの周波数応答解釈を行い,フィルタ表現に使用するベースの影響を調査し,ネットワークを基盤とする特性演算子との相互作用について議論する。
  論文  参考訳（メタデータ） (2023-10-03T17:42:09Z)
• Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks [8.563354084119062]
  空間領域やスペクトル領域におけるグラフ畳み込み過程の等価性を示す。 提案フレームワークは、空間領域に適用しながら、独自の周波数プロファイルを持つスペクトル領域の新しい畳み込みを設計するために使用される。
  論文  参考訳（メタデータ） (2020-03-26T01:49:24Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく 我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。 EGAEは1つのエンコーダと2つのデコーダで構成される。
  論文  参考訳（メタデータ） (2020-02-20T09:53:28Z)

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

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