論文の概要: Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings

• arxiv url: http://arxiv.org/abs/2201.13410v1
• Date: Mon, 31 Jan 2022 18:17:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2022-02-01 18:20:13.549783
• Title: Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
• Title（参考訳）: weisfeilerとleman go:スペクトルとコンビネーションのプレカラー化
• Authors: Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, Chaim Baskin
• Abstract要約: Wesfeiler-Leman (WL) test infinitum の表現力を高めることができることを示す。 本稿では,バニラWLテストの表現力を向上するスペクトル特性に基づく効率的な事前色付けを提案する。
• 参考スコア（独自算出の注目度）: 1.4941013982958207
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., obtained via the Weisfeiler-Leman (WL) test) and spectral invariants. While the exact power of the latter is still an open question, the former is regularly criticized for its limited power, when a standard configuration of uniform pre-coloring is used. This drawback hinders the applicability of Message Passing Graph Neural Networks (MPGNNs), whose expressive power is upper bounded by the WL test. Relaxing the assumption of uniform pre-coloring, we show that one can increase the expressive power of the WL test ad infinitum. Following that, we propose an efficient pre-coloring based on spectral features that provably increase the expressive power of the vanilla WL test. The above claims are accompanied by extensive synthetic and real data experiments. The code to reproduce our experiments is available at https://github.com/TPFI22/Spectral-and-Combinatorial
• Abstract（参考訳）: グラフ同型テストは通常、グラフ不変量の比較を通してアプローチされる。 表現力と計算効率の良好なトレードオフを提供する2つの一般的な選択肢は、組合せ(すなわち、Weisfeiler-Leman (WL) テストによって得られる)とスペクトル不変量である。 後者の正確なパワーはまだ未解決の問題であるが、均一なプリカラー化の標準構成を用いる場合、前者は限られたパワーで定期的に批判される。 この欠点は、メッセージパッシンググラフニューラルネットワーク(mpgnns)の適用性を妨げる。 均一な事前色付けの仮定を緩和することにより,WLテストアドフィニトゥムの表現力を高めることができることを示す。 次に,バニラWLテストの表現力を向上するスペクトル特徴に基づく効率的な事前色付けを提案する。 以上の主張には、広範な合成および実データ実験が伴う。 実験を再現するコードはhttps://github.com/TPFI22/Spectral-and-Combinatorialで公開されている。

関連論文リスト

• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。 ベンチマークに基づく表現力の拡張的定義と測定について論じる。
  論文  参考訳（メタデータ） (2023-07-11T20:06:12Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。 本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。 複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
  論文  参考訳（メタデータ） (2023-03-02T07:36:23Z)
• A Practical, Progressively-Expressive GNN [27.267362661067285]
  近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。 MPNNは、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。 我々は,k-tuples ノードから =c 連結成分上で定義された=k ノードの集合へ移動することで,k-WL から k-WL への複雑性を大幅に低減した (k, c)(=)-SETWL 階層を提案する。
  論文  参考訳（メタデータ） (2022-10-18T01:27:21Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。 このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。 提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
  論文  参考訳（メタデータ） (2022-07-06T08:13:06Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワークの一種である。 まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成することを証明した。 また、スペクトルGNNの表現力とグラフアイソモーフィズム(GI)テストの関連性を確立する。
  論文  参考訳（メタデータ） (2022-05-23T10:22:12Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。 本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
  論文  参考訳（メタデータ） (2021-06-08T13:26:56Z)
• Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm [3.158346511479111]
  グラフニューラルネットワーク(GNN)は、グラフベースのデータ処理のパワーのために急速に進歩している。 ほとんどのGNNはメッセージパッシング方式に従い、その表現力はワイスファイラー・リーマン(WL)テストの識別能力によって数学的に制限される。 本稿では、WLテストの限界を理論的に破るWeisfeiler-Lehman-Tinhofer GNN(WLT-GNN)と呼ばれるメッセージパッシング方式のバリエーションを提案する。
  論文  参考訳（メタデータ） (2021-04-05T10:54:22Z)
• Breaking the Expressive Bottlenecks of Graph Neural Networks [26.000304641965947]
  近年, weisfeiler-lehman (wl) graph isomorphism test を用いてグラフニューラルネットワーク (gnns) の表現性の測定を行った。 本稿では,強力なアグリゲータを探索することで表現性を向上する。
  論文  参考訳（メタデータ） (2020-12-14T02:36:46Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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