論文の概要: On the Stability of Expressive Positional Encodings for Graphs

• arxiv url: http://arxiv.org/abs/2310.02579v3
• Date: Sat, 8 Jun 2024 16:09:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-12 05:07:26.438431
• Title: On the Stability of Expressive Positional Encodings for Graphs
• Title（参考訳）: グラフの表現的位置符号化の安定性について
• Authors: Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, Pan Li,
• Abstract要約: ラプラシア固有ベクトルを位置符号化として使用することは、2つの根本的な課題に直面している。 SPE(Stable and Expressive Positional Generalizations)を紹介する。 SPEは(1)確率的に安定であり、(2)基底不変関数に対して普遍的に表現できる最初のアーキテクチャである。
• 参考スコア（独自算出の注目度）: 46.967035678550594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks. Although widespread, using Laplacian eigenvectors as positional encodings faces two fundamental challenges: (1) \emph{Non-uniqueness}: there are many different eigendecompositions of the same Laplacian, and (2) \emph{Instability}: small perturbations to the Laplacian could result in completely different eigenspaces, leading to unpredictable changes in positional encoding. Despite many attempts to address non-uniqueness, most methods overlook stability, leading to poor generalization on unseen graph structures. We identify the cause of instability to be a ``hard partition'' of eigenspaces. Hence, we introduce Stable and Expressive Positional Encodings (SPE), an architecture for processing eigenvectors that uses eigenvalues to ``softly partition'' eigenspaces. SPE is the first architecture that is (1) provably stable, and (2) universally expressive for basis invariant functions whilst respecting all symmetries of eigenvectors. Besides guaranteed stability, we prove that SPE is at least as expressive as existing methods, and highly capable of counting graph structures. Finally, we evaluate the effectiveness of our method on molecular property prediction, and out-of-distribution generalization tasks, finding improved generalization compared to existing positional encoding methods. Our code is available at \url{https://github.com/Graph-COM/SPE}.
• Abstract（参考訳）: グラフのための効果的な位置エンコーディングを設計することは、強力なグラフトランスフォーマーを構築し、メッセージパッシンググラフニューラルネットワークを強化する上で鍵となる。 広く使われているが、位置符号化としてラプラシアン固有ベクトルを使用するには、(1) \emph{Non-uniqueness}:同じラプラシアンの多くの異なる固有分解が存在し、(2) \emph{Instability}: ラプラシアンへの小さな摂動は、完全に異なる固有空間をもたらす可能性があり、位置符号化の予測不可能な変化をもたらす。 非特異性に対処しようとする多くの試みにもかかわらず、ほとんどの手法は安定性を見落とし、目に見えないグラフ構造への一般化が不十分になる。 不安定性の原因は固有空間の ` `hard partition'' である。 そこで本研究では,固有ベクトルを 'softly partition''' 固有空間に変換するアーキテクチャであるSPE(Stable and Expressive Positional Encodings)を導入する。 SPEは(1)確率的に安定であり、(2)固有ベクトルのすべての対称性を尊重しながら基底不変関数に対して普遍的に表現される最初のアーキテクチャである。 保証された安定性に加えて、SPEは既存の手法と同じくらい表現力があり、グラフ構造を数えることができることを証明している。 最後に,本手法が分子特性予測および分布外一般化タスクに与える影響を評価し,既存の位置符号化法と比較して一般化性の向上が認められた。 私たちのコードは \url{https://github.com/Graph-COM/SPE} で利用可能です。

関連論文リスト

• Transformers as Support Vector Machines [54.642793677472724]
  自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。 勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。 これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
  論文  参考訳（メタデータ） (2023-08-31T17:57:50Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Sparse Graph Learning with Eigen-gap for Spectral Filter Training in Graph Convolutional Networks [38.92746674849527]
  スパースグラフ Laplacian matrix $L$ to $barC-1$ は、より深いグラフ畳み込みニューラルネット(GCN)アーキテクチャを促進するために使用できることを示す。 実験の結果,提案手法は明示的な固有ギャップ最適化を伴わない競合方式と比較して,より深いGCNとより小さな誤差を生じることがわかった。
  論文  参考訳（メタデータ） (2022-02-28T03:39:48Z)
• Sign and Basis Invariant Networks for Spectral Graph Representation Learning [75.18802152811539]
  SignNetとBasisNetは、すべての必須対称性に不変な新しいニューラルアーキテクチャであり、したがって、原則化された方法で固有空間のコレクションを処理する。 我々のネットワークは理論的にはグラフ表現学習に強い -- 任意のスペクトルグラフ畳み込みを近似することができる。 実験により、スペクトルグラフフィルタの学習とグラフ位置エンコーディングの学習のためのネットワークの強みが示された。
  論文  参考訳（メタデータ） (2022-02-25T23:11:59Z)
• Symmetry-driven graph neural networks [1.713291434132985]
  ノード座標に影響を及ぼすいくつかの変換に同値なグラフネットワークアーキテクチャを2つ導入する。 我々はこれらの機能を$n$次元の幾何学的オブジェクトからなる合成データセット上で実証する。
  論文  参考訳（メタデータ） (2021-05-28T18:54:12Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。 まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。 次に,メッセージのパラメトリゼーション手法を提案する。
  論文  参考訳（メタデータ） (2020-06-26T17:15:16Z)

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

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