論文の概要: Theoretically Improving Graph Neural Networks via Anonymous Walk Graph
Kernels
- arxiv url: http://arxiv.org/abs/2104.02995v1
- Date: Wed, 7 Apr 2021 08:50:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-08 13:03:16.276767
- Title: Theoretically Improving Graph Neural Networks via Anonymous Walk Graph
Kernels
- Title(参考訳): 匿名ウォークグラフカーネルによるグラフニューラルネットワークの理論的改善
- Authors: Qingqing Long, Yilun Jin, Yi Wu, Guojie Song
- Abstract要約: グラフニューラルネットワーク(GNN)は、グラフマイニングで大きな成功を収めました。
一般的なGNNとしてMPGNNは、多くのグラフのサブ構造を識別、検出、カウントできないことが理論的に示されている。
理論的にはグラフ構造を区別する能力の強いGNNモデルであるGSKNを提案する。
- 参考スコア(独自算出の注目度): 25.736529232578178
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks (GNNs) have achieved tremendous success in graph
mining. However, the inability of GNNs to model substructures in graphs remains
a significant drawback. Specifically, message-passing GNNs (MPGNNs), as the
prevailing type of GNNs, have been theoretically shown unable to distinguish,
detect or count many graph substructures. While efforts have been paid to
complement the inability, existing works either rely on pre-defined
substructure sets, thus being less flexible, or are lacking in theoretical
insights. In this paper, we propose GSKN, a GNN model with a theoretically
stronger ability to distinguish graph structures. Specifically, we design GSKN
based on anonymous walks (AWs), flexible substructure units, and derive it upon
feature mappings of graph kernels (GKs). We theoretically show that GSKN
provably extends the 1-WL test, and hence the maximally powerful MPGNNs from
both graph-level and node-level viewpoints. Correspondingly, various
experiments are leveraged to evaluate GSKN, where GSKN outperforms a wide range
of baselines, endorsing the analysis.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)はグラフマイニングにおいて大きな成功を収めている。
しかしGNNがグラフのサブ構造をモデル化できないことは大きな欠点である。
特に、メッセージパスGNN(MPGNN)は、理論上、多くのグラフサブ構造を識別、検出、カウントできないことが示されている。
不可能性を補完する努力が払われているが、既存の作業は事前に定義されたサブストラクチャセットに依存しているため、柔軟性が低いか、理論的な洞察に欠けている。
本稿では,グラフ構造を識別する理論上より強力なGNNモデルであるGSKNを提案する。
具体的には、匿名ウォーク(AW)と柔軟なサブ構造ユニットに基づいてGSKNを設計し、グラフカーネル(GK)の機能マッピングに基づいて導出する。
理論的には、gskn は 1-wl テストを拡張し、グラフレベルとノードレベルの両方の観点から最大に強力な mpgnn を示す。
それに対応して、GSKNの評価には様々な実験が利用され、GSKNは幅広いベースラインを上回り、分析を裏付ける。
関連論文リスト
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。
我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文 参考訳(メタデータ) (2024-06-07T19:25:02Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳(メタデータ) (2021-06-12T07:43:51Z) - 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) - Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文 参考訳(メタデータ) (2020-06-28T16:35:45Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z) - Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
既存のGNNモデルの多くは浅く、本質的に機能中心である。
我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。
本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文 参考訳(メタデータ) (2020-06-08T02:47:38Z) - XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。
GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。
我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文 参考訳(メタデータ) (2020-06-03T23:52:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。