論文の概要: Improving Expressivity of Graph Neural Networks using Localization

• arxiv url: http://arxiv.org/abs/2305.19659v1
• Date: Wed, 31 May 2023 08:46:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 17:49:58.657769
• Title: Improving Expressivity of Graph Neural Networks using Localization
• Title（参考訳）: ローカライゼーションを用いたグラフニューラルネットワークの表現性向上
• Authors: Anant Kumar, Shrutimoy Das, Shubhajit Roy, Binita Maity, Anirban Dasgupta
• Abstract要約: 局所$k-$WLのパワーを分析し、$k-$WLよりも表現力が高く、少なくとも$(k+1)-$WLと同じくらい表現力があることを示す。 また,1-$WL のみを用いて,最大 4 個の部分グラフの正確な数を保証するフラグメンテーション手法を提案する。
• 参考スコア（独自算出の注目度）: 2.402661025098803
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose localized versions of Weisfeiler-Leman (WL) algorithms in an effort to both increase the expressivity, as well as decrease the computational overhead. We focus on the specific problem of subgraph counting and give localized versions of $k-$WL for any $k$. We analyze the power of Local $k-$WL and prove that it is more expressive than $k-$WL and at most as expressive as $(k+1)-$WL. We give a characterization of patterns whose count as a subgraph and induced subgraph are invariant if two graphs are Local $k-$WL equivalent. We also introduce two variants of $k-$WL: Layer $k-$WL and recursive $k-$WL. These methods are more time and space efficient than applying $k-$WL on the whole graph. We also propose a fragmentation technique that guarantees the exact count of all induced subgraphs of size at most 4 using just $1-$WL. The same idea can be extended further for larger patterns using $k>1$. We also compare the expressive power of Local $k-$WL with other GNN hierarchies and show that given a bound on the time-complexity, our methods are more expressive than the ones mentioned in Papp and Wattenhofer[2022a].
• Abstract（参考訳）: 本稿では,Weisfeiler-Leman (WL)アルゴリズムの局所化バージョンを提案する。 サブグラフカウントの特定の問題に焦点を当て、任意の$k$に対して$k-$WLのローカライズされたバージョンを与える。 局所$k-$WLのパワーを分析し、$k-$WLよりも表現力が高く、少なくとも$(k+1)-$WLと同じくらい表現力があることを示す。 2つのグラフが局所$k-$WL同値であれば、部分グラフと誘導部分グラフとして数えられるパターンのキャラクタリゼーションを与える。 また、$k-$WL: Layer $k-$WLとrecursive $k-$WLの2つのバリエーションを導入します。 これらの方法はグラフ全体に$k-$WLを適用するよりも時間と空間効率がよい。 また,1-$WL のみを用いて,最大 4 個の部分グラフの正確な数を保証するフラグメンテーション手法を提案する。 同じアイデアは、$k>1$を使って、より大きなパターンにも拡張できる。 また、Local $k-$WL の表現力と他の GNN 階層との比較を行い、時間的複雑さの制限が与えられた場合、我々の手法は Papp や Wattenhofer[2022a] の手法よりも表現力が高いことを示す。

関連論文リスト

• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
  K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。 提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
  論文  参考訳（メタデータ） (2024-06-27T15:10:56Z)
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
  グラフ同型テストの新しい階層構造と対応するGNNフレームワークである$r$-$ell$MPNNを導入し、最大長さ$r + 2$までサイクルをカウントできる。 特に、$r$-$ell$WL がサクタスグラフの準同型を数えることができることを示す。 提案した$r$-$ell$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットに対する最先端の予測性能を示す。
  論文  参考訳（メタデータ） (2024-03-20T16:58:28Z)
• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。 ベンチマークに基づく表現力の拡張的定義と測定について論じる。
  論文  参考訳（メタデータ） (2023-07-11T20:06:12Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。 N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
  論文  参考訳（メタデータ） (2023-06-05T21:35:32Z)
• From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks [8.121462458089141]
  メッセージパッシングニューラルネットワークの表現力を向上させるために、ノードにラベルを割り当てる方法を示す。 実験により,本手法は普遍的に互換性があり,任意のベースGNNモデルの表現性を向上させることができることを示した。 私たちの$k,l$-GNNは、多くの合成および実世界のデータセットで優れたパフォーマンスを実現しています。
  論文  参考訳（メタデータ） (2023-05-08T18:00:50Z)
• 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)
• 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)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。 2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
  論文  参考訳（メタデータ） (2022-03-22T12:58:03Z)
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks [4.355567556995855]
  我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。 2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。 特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
  論文  参考訳（メタデータ） (2020-06-16T20:24:01Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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