論文の概要: The expressive power of kth-order invariant graph networks

• arxiv url: http://arxiv.org/abs/2007.12035v1
• Date: Thu, 23 Jul 2020 14:30:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-07 12:11:41.876918
• Title: The expressive power of kth-order invariant graph networks
• Title（参考訳）: kth-次不変グラフネットワークの表現力
• Authors: Floris Geerts
• Abstract要約: 我々は、kth-次不変(線形)グラフネットワーク(k-IGN)の表現力を考える。 k-IGN はWeisfeiler-Leman (k-WL) グラフ同型テストをシミュレートするのに十分な表現であることが知られている。 k-IGN は k-WL によって表現力で有界であることを示す。
• 参考スコア（独自算出の注目度）: 4.355567556995855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
• Abstract（参考訳）: グラフニューラルネットワークの表現力は、グラフを識別する能力によって一般的に測定される。 多くの形式主義では、k-次元ワイスフェイラー・リーマングラフ同型テストがヤードスティックとして用いられる。 本稿では,kth-order invariant (linear) graph network (k-IGNs) の表現力について考察する。 k-IGN は k-WL をシミュレートするのに十分表現可能であることが知られている。 これは、k-WLで区別できる任意の2つのグラフに対して、これらのグラフを区別する k-IGN を見つけることができることを意味する。 問題は、k-IGNがk-WLよりも多くのグラフを区別できるかどうかである。 これは k=2 に対して最近偽であることが示されている。 ここで、この結果を任意の k に一般化する。 言い換えれば、k-IGN は k-WL によって表現力で有界である。 これは、k-IGN と k-WL がグラフの区別において等しく強力であることを意味する。

関連論文リスト

• Is 3-(F)WL Enough to Distinguish All 3D Graphs? [0.0]
  グラフ同型性の問題は、グラフ解析の分野において重要な問題であるが挑戦的な問題である。 本稿では,グラフ生成の観点からこの問題を探究する。
  論文  参考訳（メタデータ） (2024-01-24T06:22:08Z)
• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。 ベンチマークに基づく表現力の拡張的定義と測定について論じる。
  論文  参考訳（メタデータ） (2023-07-11T20:06:12Z)
• Improving Expressivity of Graph Neural Networks using Localization [1.323700980948722]
  局所$k-$WLのパワーを分析し、$k-$WLよりも表現力が高く、少なくとも$(k+1)-$WLと同じくらい表現力があることを示す。 また,1-$WL のみを用いて,最大 4 個の部分グラフの正確な数を保証するフラグメンテーション手法を提案する。
  論文  参考訳（メタデータ） (2023-05-31T08:46:11Z)
• Probing Graph Representations [77.7361299039905]
  グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。 本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。 グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
  論文  参考訳（メタデータ） (2023-03-07T14:58:18Z)
• 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)
• 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)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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