論文の概要: Can Graph Neural Networks Count Substructures?
- arxiv url: http://arxiv.org/abs/2002.04025v4
- Date: Wed, 28 Oct 2020 18:03:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 08:40:28.954119
- Title: Can Graph Neural Networks Count Substructures?
- Title(参考訳): グラフニューラルネットワークはサブ構造を数えるか?
- Authors: Zhengdao Chen, Lei Chen, Soledad Villar, Joan Bruna
- Abstract要約: グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。
我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
- 参考スコア(独自算出の注目度): 53.256112515435355
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The ability to detect and count certain substructures in graphs is important
for solving many tasks on graph-structured data, especially in the contexts of
computational chemistry and biology as well as social network analysis.
Inspired by this, we propose to study the expressive power of graph neural
networks (GNNs) via their ability to count attributed graph substructures,
extending recent works that examine their power in graph isomorphism testing
and function approximation. We distinguish between two types of substructure
counting: induced-subgraph-count and subgraph-count, and establish both
positive and negative answers for popular GNN architectures. Specifically, we
prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL)
and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count
of substructures consisting of 3 or more nodes, while they can perform
subgraph-count of star-shaped substructures. As an intermediary step, we prove
that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs,
partly answering an open problem raised in Maron et al. (2019). We also prove
positive results for k-WL and k-IGNs as well as negative results for k-WL with
a finite number of iterations. We then conduct experiments that support the
theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure
counting and inspired by Murphy et al. (2019), we propose the Local Relational
Pooling model and demonstrate that it is not only effective for substructure
counting but also able to achieve competitive performance on molecular
prediction tasks.
- Abstract(参考訳): グラフ内の特定の部分構造を検出してカウントする能力は、グラフ構造データ、特に計算化学や生物学の文脈や社会ネットワーク分析の多くの課題を解決する上で重要である。
そこで我々は, グラフニューラルネットワーク(GNN)の表現力について, 属性付きグラフのサブ構造を数える能力を用いて検討し, グラフ同型テストおよび関数近似におけるその能力を検証した最近の研究を拡張した。
我々は2種類のサブストラクチャカウントを区別する: インダクション・サブグラフカウントとサブグラフカウント、そして一般的なGNNアーキテクチャの正と負の両方の答えを確立する。
具体的には,メッセージパッシングニューラルネットワーク (mpnns), 2-weisfeiler-lehman (2-wl), 2-invariant graph networks (2-igns) が3つ以上のノードからなるサブ構造の誘導サブグラフ数を行えないことを証明した。
中間ステップとして、2-WL と 2-IGN が非同型グラフの区別において等価であることを証明する。
また、k-WL と k-IGN の正の結果と、k-WL の負の結果を有限反復数で証明する。
次に,MPNNと2-IGNの理論的結果を支持する実験を行う。
さらに,マーフィーら(2019)に触発されたサブストラクチャーカウントに動機づけられ,局所的リレーショナルプーリングモデルを提案し,サブストラクショナルプーリングに有効であるだけでなく,分子予測タスクにおける競合性能も発揮できることを実証した。
関連論文リスト
- Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳(メタデータ) (2023-12-14T06:08:35Z) - Generalization Limits of Graph Neural Networks in Identity Effects
Learning [12.302336258860116]
グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。
我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。
我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
論文 参考訳(メタデータ) (2023-06-30T20:56:38Z) - T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and
Structure via Teacher-Student Distillation [65.43245616105052]
グラフニューラルネットワーク(GNN)は,様々な解析タスクをグラフデータ上で処理する手法として普及している。
本稿では,教師による蒸留に基づく一般GNNフレームワークを提案し,不完全グラフ上でのGNNの性能向上を図る。
論文 参考訳(メタデータ) (2022-12-24T13:49:44Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳(メタデータ) (2022-05-19T18:40:25Z) - Theoretically Improving Graph Neural Networks via Anonymous Walk Graph
Kernels [25.736529232578178]
グラフニューラルネットワーク(GNN)は、グラフマイニングで大きな成功を収めました。
一般的なGNNとしてMPGNNは、多くのグラフのサブ構造を識別、検出、カウントできないことが理論的に示されている。
理論的にはグラフ構造を区別する能力の強いGNNモデルであるGSKNを提案する。
論文 参考訳(メタデータ) (2021-04-07T08:50:34Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳(メタデータ) (2020-12-06T03:42:54Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。