論文の概要: Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2605.01136v1
- Date: Fri, 01 May 2026 22:26:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-05 20:33:49.605087
- Title: Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks
- Title（参考訳）: スペクトルグラフスペーシフィケーションはグラフニューラルネットワークにおける表現幾何学を保存する
- Authors: Sanjukta Krishnagopal,
- Abstract要約: スペクトルグラフスペーシフィケーションは、グラフニューラルネットワーク(GNN)の計算を高速化するためにしばしば用いられる。
スペクトルスペーシフィケーションはグラフ演算子だけでなく、GNN埋め込みの下流での解釈性向上を支援する表現幾何学も保存していることを示す。
- 参考スコア（独自算出の注目度）: 2.0305676256390934
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spectral graph sparsification is a classical tool for reducing graph complexity while preserving Laplacian quadratic forms. In graph neural networks (GNNs), sparsification is often used to accelerate computation while maintaining predictive performance. In this work, we study a complementary representation-level question: does sparsification preserve the geometry of learned embeddings? For polynomial-filter GNNs, we prove that any $ε$-spectral sparsifier induces $O(ε)$ perturbations in polynomial graph filters, multilayer hidden representations, and their Gram matrices. These guarantees imply stability of squared pairwise distances, class means, and covariance structure in embedding space. We further establish finite-time training stability: under smoothness and boundedness assumptions, gradient descent on dense and sparsified graphs produces weight trajectories whose separation grows at most proportionally to the sparsification distortion. Empirically, effective-resistance sparsification validates the predicted perturbation chain on synthetic graphs and preserves hidden representation geometry on real datasets. In our experiments, the gram matrix and training dynamics show low divergence even under substantial sparsification, consistent with the predicted stability under spectral sparsification. Hidden Gram preservation strongly predicts neighborhood preservation and class-centroid stability across FashionMNIST, Cora, and Paul15. Together, these results show that spectral sparsification preserves not only graph operators, but also the representation geometry that supports downstream use of GNN embeddings for interpretability.
- Abstract（参考訳）: スペクトルグラフスペーシフィケーションは、ラプラシア二次形式を保存しながらグラフの複雑さを減少させる古典的なツールである。
グラフニューラルネットワーク(GNN)では、予測性能を維持しながら計算を高速化するためにスパーシフィケーションがよく用いられる。
本研究では,学習した埋め込みの幾何学をスパース化は保っているかという,相補的な表現レベル問題について考察する。
多項式フィルタ GNN に対して、任意の$ε$スペクトルスペーサーは多項式グラフフィルタ、多層隠れ表現およびそれらの文法行列において$O(ε)$摂動を誘導することを示す。
これらのことは、二乗対距離、クラス平均、および埋め込み空間における共分散構造を暗示的に安定することを保証する。
さらに、滑らかさと有界性の仮定の下では、密度とスパース化グラフ上の勾配勾配は、スパース化歪みに最も比例して分離が成長する重みトラジェクトリを生成する。
経験的に、有効抵抗スペーシフィケーションは、合成グラフ上の予測摂動連鎖を検証し、実際のデータセット上に隠された表現幾何学を保存する。
実験では, スペクトルスカラー化条件下では, スペクトルスカラー化条件下での安定性の予測値と一致して, かなりのスカラー化条件下においても, グラム行列とトレーニングダイナミクスのばらつきが低かった。
隠れたグラム保存は、FashionMNIST, Cora, Paul15の近傍保存とクラスセントロイド安定性を強く予測する。
これらの結果から,スペクトルスペーシフィケーションはグラフ演算子だけでなく,GNN埋め込みの下流での解釈性向上を支援する表現幾何学も維持できることが示された。
関連論文リスト
- Improved large-scale graph learning through ridge spectral sparsification [65.84577791298442]
分散ストリーミング環境におけるラプラシアンLの学習問題を考察する。
この設定では、L の分散表現を維持しながら、素早く、あるいはほぼ学習することは困難である。
本稿では, 有効抵抗の小さなサブセットを維持することにより, ラプラシアンを効率的に分散させる新しいアルゴリズムGSQUEAKを提案する。
論文 参考訳（メタデータ） (2026-04-22T00:49:31Z) - Semi-Supervised Learning on Graphs using Graph Neural Networks [7.3886152750469]
グラフニューラルネットワーク(GNN)は、半教師付きノード回帰において極めてうまく機能する。
本稿では,複数の共通メッセージパッシングアーキテクチャを含むアグリゲート・アンド・リードアウトモデルについて検討する。
我々は、誤差近似、収束、最適化を分離する急激な非漸近的リスク境界を証明した。
論文 参考訳（メタデータ） (2026-02-19T06:25:13Z) - A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。
コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。
この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
論文 参考訳（メタデータ） (2025-07-17T10:02:57Z) - Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。
本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
論文 参考訳（メタデータ） (2025-06-19T08:01:00Z) - Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
本稿では,RDPG (Random Dot Product Graph) の組込み問題の解法について述べる。
そこで我々は, 結果の多様体に対して, 実現可能な新しい最適化手法を開発した。
当社のオープンソースアルゴリズムの実装はスケーラブルで、エッジデータに欠ける堅牢さと異なり、ストリーミンググラフからゆっくりと、潜伏した位置を追跡することができます。
論文 参考訳（メタデータ） (2023-07-25T21:09:55Z) - Limitless stability for Graph Convolutional Networks [8.1585306387285]
この研究は、グラフ畳み込みネットワークに対する厳密で斬新で広く適用可能な安定性保証と転送可能性境界を確立する。
グラフ畳み込みネットワークは、GSOがグラフラプラシアンであり、フィルタが無限大で正則である場合、グラフ粗粒化法の下で安定であることを示す。
論文 参考訳（メタデータ） (2023-01-26T22:17:00Z) - Stability of Graph Convolutional Neural Networks to Stochastic
Perturbations [122.12962842842349]
グラフ畳み込みニューラルネットワーク(GCNN)は、ネットワークデータから表現を学ぶ非線形処理ツールである。
現在の分析では決定論的摂動を考慮しているが、トポロジカルな変化がランダムである場合、関連する洞察を与えられない。
本稿では,リンク損失に起因する乱れグラフ摂動に対するGCNNの安定性について検討する。
論文 参考訳（メタデータ） (2021-06-19T16:25:28Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Convergence and Stability of Graph Convolutional Networks on Large
Random Graphs [22.387735135790706]
グラフ畳み込みネットワーク(GCN)の特性をランダムグラフの標準モデル上で解析することによって検討する。
まず,GCNの連続的な収束について検討し,ノード数の増加について検討する。
ランダムグラフモデルの小さな変形に対するGCNの安定性を解析する。
論文 参考訳（メタデータ） (2020-06-02T18:36:19Z) - Graphon Pooling in Graph Neural Networks [169.09536309161314]
グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。
本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
論文 参考訳（メタデータ） (2020-03-03T21:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。