論文の概要: Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs

• arxiv url: http://arxiv.org/abs/2210.13978v2
• Date: Mon, 3 Apr 2023 17:09:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-05 00:28:40.379487
• Title: Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs
• Title（参考訳）: I$^2$-GNNを用いたグラフニューラルネットワークのサイクルカウントパワー向上
• Authors: Yinan Huang, Xingang Peng, Jianzhu Ma, Muhan Zhang
• Abstract要約: 本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
• 参考スコア（独自算出の注目度）: 9.806910643086043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message Passing Neural Networks (MPNNs) are a widely used class of Graph Neural Networks (GNNs). The limited representational power of MPNNs inspires the study of provably powerful GNN architectures. However, knowing one model is more powerful than another gives little insight about what functions they can or cannot express. It is still unclear whether these models are able to approximate specific functions such as counting certain graph substructures, which is essential for applications in biology, chemistry and social network analysis. Motivated by this, we propose to study the counting power of Subgraph MPNNs, a recent and popular class of powerful GNN models that extract rooted subgraphs for each node, assign the root node a unique identifier and encode the root node's representation within its rooted subgraph. Specifically, we prove that Subgraph MPNNs fail to count more-than-4-cycles at node level, implying that node representations cannot correctly encode the surrounding substructures like ring systems with more than four atoms. To overcome this limitation, we propose I$^2$-GNNs to extend Subgraph MPNNs by assigning different identifiers for the root node and its neighbors in each subgraph. I$^2$-GNNs' discriminative power is shown to be strictly stronger than Subgraph MPNNs and partially stronger than the 3-WL test. More importantly, I$^2$-GNNs are proven capable of counting all 3, 4, 5 and 6-cycles, covering common substructures like benzene rings in organic chemistry, while still keeping linear complexity. To the best of our knowledge, it is the first linear-time GNN model that can count 6-cycles with theoretical guarantees. We validate its counting power in cycle counting tasks and demonstrate its competitive performance in molecular prediction benchmarks.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(英: Message Passing Neural Networks、MPNN)は、グラフニューラルネットワーク(GNN)の一種。 MPNNの限られた表現力は、証明可能な強力なGNNアーキテクチャの研究を刺激する。 しかし、あるモデルを知ることは、あるモデルが表現できる機能やできない機能についての洞察をほとんど与えない。 これらのモデルが、生物学、化学、社会ネットワーク分析の応用に不可欠な、特定のグラフ部分構造を数えるといった特定の関数を近似できるかどうかはまだ不明である。 そこで本研究では,各ノードのルート付きサブグラフを抽出し,ルートノードにユニークな識別子を割り当て,ルートノードの表現をそのルート付きサブグラフ内にエンコードする,GNNモデルの最近の人気クラスであるSubgraph MPNNのカウント能力について検討する。 具体的には、サブグラフmpnnがノードレベルで4サイクル以上を数えることができないことを証明し、ノード表現が4原子以上の環系のような周囲の部分構造を正しくエンコードできないことを示唆する。 この制限を克服するため、各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで、サブグラフMPNNを拡張するためのI$^2$-GNNを提案する。 I$^2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 さらに重要なことは、I$^2$-GNNは3, 4, 5, 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)
• Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power [27.929167547127207]
  グラフニューラルネットワーク(GNN)の特定のグラフサブ構造、特にサイクルをカウントする能力は重要である。 本稿では,GNNの新しいクラスとして$d$-Distance-Restricted FWL(2) GNNを提案する。 我々のモデルは今までで最も効率的なGNNモデルであり、最大6サイクルまで数えることができる。
  論文  参考訳（メタデータ） (2023-09-10T06:13:29Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。
  論文  参考訳（メタデータ） (2023-03-19T05:35:59Z)
• Nested Graph Neural Networks [20.28732862748783]
  グラフニューラルネットワーク(GNN)のグラフ分類における成功は、Weisfeiler-Lehman (1-WL)アルゴリズムと密接に関連している。 そこで我々は,Nested Graph Neural Networks (NGNN) を提案する。
  論文  参考訳（メタデータ） (2021-10-25T18:22:24Z)
• Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks [12.97622530614215]
  Ego-GNNは、実世界のグラフにおける推移性の優位性を考えると、閉三角形を認識できることを示す。 特に、Ego-GNNは、実世界のグラフにおける推移性の優位性を考えると、閉三角形を認識することができることを示す。
  論文  参考訳（メタデータ） (2021-07-22T23:42:23Z)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels [25.736529232578178]
  グラフニューラルネットワーク(GNN)は、グラフマイニングで大きな成功を収めました。 一般的なGNNとしてMPGNNは、多くのグラフのサブ構造を識別、検出、カウントできないことが理論的に示されている。 理論的にはグラフ構造を区別する能力の強いGNNモデルであるGSKNを提案する。
  論文  参考訳（メタデータ） (2021-04-07T08:50:34Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。 ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。 既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-01-25T18:59:01Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。 これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
  論文  参考訳（メタデータ） (2020-08-04T18:57:36Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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