論文の概要: Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power

• arxiv url: http://arxiv.org/abs/2309.04941v3
• Date: Thu, 11 Jan 2024 04:35:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-13 03:29:07.126416
• Title: Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power
• Title（参考訳）: 確率サイクルカウントパワーを有する距離制限型エルクローヤ・レスファイラー・リーマンGNN
• Authors: Junru Zhou, Jiarui Feng, Xiyuan Wang, Muhan Zhang
• Abstract要約: グラフニューラルネットワーク(GNN)の特定のグラフサブ構造、特にサイクルをカウントする能力は重要である。 本稿では,GNNの新しいクラスとして$d$-Distance-Restricted FWL(2) GNNを提案する。 我々のモデルは今までで最も効率的なGNNモデルであり、最大6サイクルまで数えることができる。
• 参考スコア（独自算出の注目度）: 27.929167547127207
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ability of graph neural networks (GNNs) to count certain graph substructures, especially cycles, is important for the success of GNNs on a wide range of tasks. It has been recently used as a popular metric for evaluating the expressive power of GNNs. Many of the proposed GNN models with provable cycle counting power are based on subgraph GNNs, i.e., extracting a bag of subgraphs from the input graph, generating representations for each subgraph, and using them to augment the representation of the input graph. However, those methods require heavy preprocessing, and suffer from high time and memory costs. In this paper, we overcome the aforementioned limitations of subgraph GNNs by proposing a novel class of GNNs -- $d$-Distance-Restricted FWL(2) GNNs, or $d$-DRFWL(2) GNNs. $d$-DRFWL(2) GNNs use node pairs whose mutual distances are at most $d$ as the units for message passing to balance the expressive power and complexity. By performing message passing among distance-restricted node pairs in the original graph, $d$-DRFWL(2) GNNs avoid the expensive subgraph extraction operations in subgraph GNNs, making both the time and space complexity lower. We theoretically show that the discriminative power of $d$-DRFWL(2) GNNs strictly increases as $d$ increases. More importantly, $d$-DRFWL(2) GNNs have provably strong cycle counting power even with $d=2$: they can count all 3, 4, 5, 6-cycles. Since 6-cycles (e.g., benzene rings) are ubiquitous in organic molecules, being able to detect and count them is crucial for achieving robust and generalizable performance on molecular tasks. Experiments on both synthetic datasets and molecular datasets verify our theory. To the best of our knowledge, our model is the most efficient GNN model to date (both theoretically and empirically) that can count up to 6-cycles.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)が特定のグラフサブ構造、特にサイクルをカウントする能力は、幅広いタスクにおいてGNNの成功にとって重要である。 GNNの表現力を評価するための一般的な指標として最近使用されている。 証明可能なサイクルカウント能力を持つ多くのGNNモデルは、入力グラフからサブグラフの袋を抽出し、各サブグラフの表現を生成し、それらを使用して入力グラフの表現を増強する。 しかし、これらの手法は重い前処理を必要とし、高い時間とメモリコストに悩まされる。 本稿では,GNNの新たなクラスである$d$-Distance-Restricted FWL(2) GNN,あるいは$d$-DRFWL(2) GNNを提案することによって,前述のGNNの制限を克服する。 $d$-DRFWL(2) GNNは、表現力と複雑性のバランスをとるためにメッセージパッシングの単位として、互いに距離が最大$d$のノードペアを使用する。 元のグラフで距離制限ノードペア間でメッセージパッシングを行うことで、$d$-DRFWL(2) GNNはグラフGNNにおける高価なサブグラフ抽出操作を避け、時間と空間の複雑さを下げる。 理論的には、$d$-DRFWL(2) GNNの判別力は、$d$の増加とともに厳密に増加する。 さらに重要なのは、$d$-DRFWL(2) GNNは、$d=2$であっても、確実に強力なサイクルカウント能力を持つことだ。 6-サイクル(例えばベンゼン環)は有機分子中でユビキタスであるため、分子のタスクにおいて堅牢で一般化可能な性能を達成するためには、それらを検出して数えることができる。 合成データセットと分子データセットの両方の実験は、この理論を検証する。 我々の知る限りでは、我々のモデルは6サイクルまで数えられる最も効率的なGNNモデルである(理論的にも経験的にも)。

関連論文リスト

• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。
  論文  参考訳（メタデータ） (2023-03-19T05:35:59Z)
• Some Might Say All You Need Is Sum [2.226803104060345]
  グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。 我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
  論文  参考訳（メタデータ） (2023-02-22T19:01:52Z)
• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
  論文  参考訳（メタデータ） (2022-10-22T09:40:00Z)
• Nested Graph Neural Networks [20.28732862748783]
  グラフニューラルネットワーク(GNN)のグラフ分類における成功は、Weisfeiler-Lehman (1-WL)アルゴリズムと密接に関連している。 そこで我々は,Nested Graph Neural Networks (NGNN) を提案する。
  論文  参考訳（メタデータ） (2021-10-25T18:22:24Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。 我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
  論文  参考訳（メタデータ） (2021-06-12T07:43:51Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• GPT-GNN: Generative Pre-Training of Graph Neural Networks [93.35945182085948]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データのモデリングにおいて強力であることが示されている。 生成事前学習によりGNNを初期化するためのGPT-GNNフレームワークを提案する。 GPT-GNNは、様々な下流タスクにおいて、事前トレーニングを最大9.1%行うことなく、最先端のGNNモデルを大幅に上回ることを示す。
  論文  参考訳（メタデータ） (2020-06-27T20:12:33Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。 GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。 我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:52:43Z)

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

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