論文の概要: Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

• arxiv url: http://arxiv.org/abs/2006.09252v3
• Date: Mon, 5 Jul 2021 13:22:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-20 20:11:33.350859
• Title: Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Title（参考訳）: 部分グラフ同型カウントによるグラフニューラルネットワーク表現性の向上
• Authors: Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, Michael M. Bronstein
• Abstract要約: グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
• 参考スコア（独自算出の注目度）: 63.04999833264299
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power of standard GNNs is bounded by the Weisfeiler-Leman (WL) graph isomorphism test, from which they inherit proven limitations such as the inability to detect and count graph substructures. On the other hand, there is significant empirical evidence, e.g. in network science and bioinformatics, that substructures are often intimately related to downstream tasks. To this end, we propose "Graph Substructure Networks" (GSN), a topologically-aware message passing scheme based on substructure encoding. We theoretically analyse the expressive power of our architecture, showing that it is strictly more expressive than the WL test, and provide sufficient conditions for universality. Importantly, we do not attempt to adhere to the WL hierarchy; this allows us to retain multiple attractive properties of standard GNNs such as locality and linear network complexity, while being able to disambiguate even hard instances of graph isomorphism. We perform an extensive experimental evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings including molecular graphs and social networks. The code is publicly available at https://github.com/gbouritsas/graph-substructure-networks.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は様々なアプリケーションで顕著な成果を上げているが、近年の研究により、基盤となるグラフの構造を捉える能力に重大な欠点が明らかになった。 標準GNNの表現力はWeisfeiler-Leman(WL)グラフ同型テスト(英語版)によって制限され、そこからグラフのサブ構造を検出・カウントできないような証明済みの制限を継承することが示されている。 一方、ネットワーク科学やバイオインフォマティクスでは、サブ構造はしばしば下流のタスクと密接に関連しているという重要な経験的証拠がある。 そこで本研究では,下位構造符号化に基づく位相認識型メッセージパッシング方式である"graph substructure networks" (gsn)を提案する。 理論的には、アーキテクチャの表現力を分析し、WLテストよりも厳密な表現力を示し、普遍性に十分な条件を提供する。 重要なことに、我々はWL階層に固執しようとはしない。これは局所性や線形ネットワーク複雑性といった標準GNNの複数の魅力的な特性を維持できると同時に、グラフ同型(英語版)の硬いインスタンスさえも曖昧にすることができる。 我々は,グラフ分類と回帰タスクに関する広範な実験を行い,分子グラフやソーシャルネットワークなど実世界の様々な設定における最先端の成果を得た。 コードはhttps://github.com/gbouritsas/graph-substructure-networksで公開されている。

関連論文リスト

• Beyond 1-WL with Local Ego-Network Encodings [0.42970700836450487]
  Ego-networksはWeisfeiler-Lehman (1-WL) テストよりも高い表現性を持つ任意のグラフの構造的符号化スキームを作成できることを示す。 我々は,ego-networksをスパースベクトルに符号化することで,ノード表現を増強する機能を前処理で生成するIGELを紹介した。
  論文  参考訳（メタデータ） (2022-11-27T18:14:03Z)
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations [26.77596449192451]
  グラフニューラルネットワーク(GNN)は、グラフ上の機械学習問題を解決するための有望なツールとして登場した。 本論文では,Weisfeiler-Leman(WL)アルゴリズムによって生成される階層に基づいて,ノード間の距離関数を定義する。 本稿では,ノード間の距離を保存する表現を学習するモデルを提案する。
  論文  参考訳（メタデータ） (2022-11-04T15:03:41Z)
• Graph Neural Networks Are More Powerful Than we Think [124.97061497512804]
  グラフニューラルネットワーク(GNN)は、様々なノードレベルおよびグラフレベルタスクにおいて顕著なパフォーマンスを示す強力な畳み込みアーキテクチャである。 彼らの成功にもかかわらず、GNNの表現力は限られており、Weisfeiler-Lehman (WL)アルゴリズムと同じくらい差別的であるという共通の信念がある。 GNNは、少なくとも1つの固有値が異なるグラフと、WLアルゴリズムよりも確実に表現可能な単純なGNNアーキテクチャを区別できることを示す。
  論文  参考訳（メタデータ） (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)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  我々はグラフ信号処理を活用してグラフニューラルネットワーク(GNN)の表現空間を特徴付ける。 GNNにおけるグラフ畳み込みフィルタの役割について議論し、そのようなフィルタで構築されたアーキテクチャは、置換同値の基本的な性質と位相変化に対する安定性を持つことを示す。 また,ロボット群に対するリコメンデータシステムや分散型コントローラの学習におけるGNNの利用について検討した。
  論文  参考訳（メタデータ） (2020-03-08T13:02:15Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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