論文の概要: Weisfeiler and Lehman Go Topological: Message Passing Simplicial
Networks
- arxiv url: http://arxiv.org/abs/2103.03212v1
- Date: Thu, 4 Mar 2021 18:35:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-05 14:44:31.716229
- Title: Weisfeiler and Lehman Go Topological: Message Passing Simplicial
Networks
- Title（参考訳）: Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
- Authors: Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido
Mont\'ufar, Pietro Li\`o, Michael Bronstein
- Abstract要約: MPSN(Message Passing Simplicial Networks)を提案します。
MPSNはsimplicial Complex (SC)上でメッセージパッシングを行うモデルである
我々は、MPSNがGNNが失敗する挑戦的な強正則グラフを区別できることを示すことによって、理論的な主張を実証的に支持する。
- 参考スコア（独自算出の注目度）: 3.0017241250121383
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The pairwise interaction paradigm of graph machine learning has predominantly
governed the modelling of relational systems. However, graphs alone cannot
capture the multi-level interactions present in many complex systems and the
expressive power of such schemes was proven to be limited. To overcome these
limitations, we propose Message Passing Simplicial Networks (MPSNs), a class of
models that perform message passing on simplicial complexes (SCs) - topological
objects generalising graphs to higher dimensions. To theoretically analyse the
expressivity of our model we introduce a Simplicial Weisfeiler-Lehman (SWL)
colouring procedure for distinguishing non-isomorphic SCs. We relate the power
of SWL to the problem of distinguishing non-isomorphic graphs and show that SWL
and MPSNs are strictly more powerful than the WL test and not less powerful
than the 3-WL test. We deepen the analysis by comparing our model with
traditional graph neural networks with ReLU activations in terms of the number
of linear regions of the functions they can represent. We empirically support
our theoretical claims by showing that MPSNs can distinguish challenging
strongly regular graphs for which GNNs fail and, when equipped with orientation
equivariant layers, they can improve classification accuracy in oriented SCs
compared to a GNN baseline. Additionally, we implement a library for message
passing on simplicial complexes that we envision to release in due course.
- Abstract（参考訳）: グラフ機械学習のペアワイズ相互作用パラダイムは、リレーショナルシステムのモデリングを主に支配している。
しかし、グラフだけでは多くの複雑なシステムに存在するマルチレベル相互作用を捉えることができず、そのようなスキームの表現力は限定的であることが証明された。
これらの制限を克服するために、グラフを高次元に一般化する位相的オブジェクトである単純複素体(SC)上のメッセージパッシングを実行するモデルのクラスであるMessage Passing Simplicial Networks (MPSNs)を提案する。
理論的にモデルの表現性を解析するために,非同型SCを識別するための単純ワイスフェイラー・リーマンカラー化法を導入する。
我々は、SWLのパワーと非同型グラフの識別の問題とを関連づけ、SWLとMPSNがWLテストよりも厳密に強力であり、3WLテストよりも強力でないことを示す。
我々は,従来のグラフニューラルネットワークとReLUアクティベーションを比較して,表現可能な関数の線形領域の数の観点から分析を深めている。
我々は,MPSNがGNNが失敗する難易度の高い正則グラフを識別し,配向同変層を備えると,GNNベースラインと比較して指向性SCの分類精度を向上させることができることを示すことによって,我々の理論的主張を実証的に支持する。
さらに、我々は今後リリースする予定の単純複雑体上でメッセージパッシングのためのライブラリを実装します。
関連論文リスト
- Higher-order Graph Convolutional Network with Flower-Petals Laplacians
on Simplicial Complexes [5.838832985156104]
FPラプラシアンをsimplicial Complex(SC)に組み込んだ高次フラワー・ペタールス(FP)モデルを提案する。
また、FPラプラシアンを基盤とした高階グラフ畳み込みネットワーク(HiGCN)を導入し、様々な位相スケールで固有の特徴を識別する。
HiGCNは、様々なグラフタスクにおける最先端のパフォーマンスを達成し、グラフにおける高次相互作用を探索するためのスケーラブルで柔軟なソリューションを提供する。
論文 参考訳（メタデータ） (2023-09-22T16:11:17Z) - Equivariant Hypergraph Neural Networks [15.096429849049953]
ハイパーグラフ学習の最近のアプローチは、メッセージパッシングに基づくグラフニューラルネットワークを拡張している。
EHNN(Equivariant Hypergraph Neural Network)は,一般ハイパーグラフ学習のための最大表現型同変層を実現するための最初の試みである。
我々は、合成kエッジ識別、半教師付き分類、視覚的キーポイントマッチングなど、様々なハイパーグラフ学習問題において、それらの能力を実証し、強いメッセージパッシングベースラインよりも優れた性能を報告した。
論文 参考訳（メタデータ） (2022-08-22T16:28:38Z) - Learnable Filters for Geometric Scattering Modules [64.03877398967282]
最近提案された幾何散乱変換の緩和に基づく新しいグラフニューラルネットワーク(GNN)モジュールを提案する。
我々の学習可能な幾何散乱(LEGS)モジュールは、ウェーブレットの適応的なチューニングを可能にし、学習された表現に帯域通過の特徴が現れるように促す。
論文 参考訳（メタデータ） (2022-08-15T22:30:07Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Deep Architecture Connectivity Matters for Its Convergence: A
Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。
接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文 参考訳（メタデータ） (2022-05-11T17:43:54Z) - Weisfeiler and Lehman Go Cellular: CW Networks [3.0017241250121383]
グラフニューラルネットワーク(GNN)は、表現力に制限があり、長距離相互作用に苦慮し、高次構造をモデル化する原則的な方法が欠けている。
SC の最近の理論的結果は、SC とグラフを柔軟にサブスムする位相対象である正則なセルコンプレックスに拡張する。
この一般化は、グラフリフトの変換の強力なセットを提供し、それぞれがユニークなメッセージパッシング手順につながることを示す。
論文 参考訳（メタデータ） (2021-06-23T17:59:16Z) - Breaking the Expressive Bottlenecks of Graph Neural Networks [26.000304641965947]
近年, weisfeiler-lehman (wl) graph isomorphism test を用いてグラフニューラルネットワーク (gnns) の表現性の測定を行った。
本稿では,強力なアグリゲータを探索することで表現性を向上する。
論文 参考訳（メタデータ） (2020-12-14T02:36:46Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳（メタデータ） (2020-12-06T03:42:54Z) - Data-Driven Learning of Geometric Scattering Networks [74.3283600072357]
最近提案された幾何散乱変換の緩和に基づく新しいグラフニューラルネットワーク(GNN)モジュールを提案する。
我々の学習可能な幾何散乱(LEGS)モジュールは、ウェーブレットの適応的なチューニングを可能にし、学習された表現に帯域通過の特徴が現れるように促す。
論文 参考訳（メタデータ） (2020-10-06T01:20:27Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳（メタデータ） (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。