論文の概要: Homomorphism Counts for Graph Neural Networks: All About That Basis
- arxiv url: http://arxiv.org/abs/2402.08595v3
- Date: Sat, 24 Feb 2024 00:31:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 00:01:43.561777
- Title: Homomorphism Counts for Graph Neural Networks: All About That Basis
- Title(参考訳): グラフニューラルネットワークの準同型数:その基礎について
- Authors: Emily Jin, Michael Bronstein, Ismail Ilkan Ceylan, Matthias Lanzinger
- Abstract要約: グラフニューラルネットワークは、グラフ上の不変関数を学習するためのアーキテクチャである。
グラフ内の特定のパターンを数えることのできないことは、そのような制限の中心にある。
我々は、対象パターンの「基底」に全ての構造の準同型数を含むよりきめ細かいアプローチを論じる。
- 参考スコア(独自算出の注目度): 9.014929555228916
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks are architectures for learning invariant functions over
graphs. A large body of work has investigated the properties of graph neural
networks and identified several limitations, particularly pertaining to their
expressive power. Their inability to count certain patterns (e.g., cycles) in a
graph lies at the heart of such limitations, since many functions to be learned
rely on the ability of counting such patterns. Two prominent paradigms aim to
address this limitation by enriching the graph features with subgraph or
homomorphism pattern counts. In this work, we show that both of these
approaches are sub-optimal in a certain sense and argue for a more fine-grained
approach, which incorporates the homomorphism counts of all structures in the
"basis" of the target pattern. This yields strictly more expressive
architectures without incurring any additional overhead in terms of
computational complexity compared to existing approaches. We prove a series of
theoretical results on node-level and graph-level motif parameters and
empirically validate them on standard benchmark datasets.
- Abstract(参考訳): グラフニューラルネットワークは、グラフ上で不変関数を学ぶためのアーキテクチャである。
多くの研究がグラフニューラルネットワークの特性を調査し、特に表現力に関するいくつかの制限を特定している。
グラフ内の特定のパターン(例えばサイクル)を数えることのできないことは、そのような制限の中心にある。
2つの顕著なパラダイムは、グラフの特徴をグラフや同型パターン数で豊かにすることで、この制限に対処することを目指している。
本研究では,これら2つのアプローチが,ある意味では準最適であることを示すとともに,対象パターンの「ベイズ」における全ての構造の準同型数を組み込んだ,よりきめ細かいアプローチを主張する。
これにより、既存のアプローチに比べて計算複雑性の面で追加のオーバーヘッドを伴わずに、厳密に表現力のあるアーキテクチャが得られる。
ノードレベルおよびグラフレベルのモチーフパラメータに関する一連の理論的結果が証明され、標準ベンチマークデータセットで実証的に検証される。
関連論文リスト
- Structural Node Embeddings with Homomorphism Counts [2.0131144893314232]
準同型は局所構造情報を捉えます
準同型数に基づくノード埋め込みの有効性を実験的に示す。
本手法は,有界木幅グラフクラスに対するグラフ準同型カウントの効率的な計算可能性に着目している。
論文 参考訳(メタデータ) (2023-08-29T13:14:53Z) - Weisfeiler and Lehman Go Paths: Learning Topological Features via Path
Complexes [5.002862787862848]
グラフニューラルネットワーク(GNN)は理論上、1-Weisfeiler-Lehmanテストによって拘束される。
本研究では, トポロジ的メッセージパッシング過程において, グラフ内の単純な経路に着目し, 新たな視点を示す。
論文 参考訳(メタデータ) (2023-08-13T19:45:20Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳(メタデータ) (2022-12-01T11:49:07Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:59:41Z) - Learning to Learn Graph Topologies [27.782971146122218]
ノードデータからグラフ構造へのマッピングを学習する(L2O)。
このモデルは、ノードデータとグラフサンプルのペアを使ってエンドツーエンドでトレーニングされる。
合成データと実世界のデータの両方の実験により、我々のモデルは、特定のトポロジ特性を持つグラフを学習する際の古典的反復アルゴリズムよりも効率的であることが示された。
論文 参考訳(メタデータ) (2021-10-19T08:42:38Z) - Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。
実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
論文 参考訳(メタデータ) (2021-02-23T07:45:58Z) - Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
グラフ畳み込みネットワークにおける既存の表現学習手法は主に、各ノードの近傍を知覚全体として記述することで設計される。
本稿では,グラフの潜在意味パスを学習することで暗黙的な意味を探索する意味グラフ畳み込みネットワーク(sgcn)を提案する。
論文 参考訳(メタデータ) (2021-01-16T16:18:43Z) - Building powerful and equivariant graph neural networks with structural
message-passing [74.93169425144755]
本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。
まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。
次に,メッセージのパラメトリゼーション手法を提案する。
論文 参考訳(メタデータ) (2020-06-26T17:15:16Z) - 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) - Deep Graph Mapper: Seeing Graphs through the Neural Lens [4.401427499962144]
我々はMapperとグラフニューラルネットワーク(GNN)の表現力を組み合わせることで、グラフの階層的でトポロジカルな視覚化を生成する。
これらの視覚化は、複雑なグラフの構造を識別するだけでなく、様々なタスクを解くためにそれらに適用されたモデルを理解する手段を提供する。
論文 参考訳(メタデータ) (2020-02-10T15:29:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。