論文の概要: On the Hölder Stability of Multiset and Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2406.06984v2
- Date: Wed, 09 Oct 2024 19:44:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-11 14:28:03.835223
- Title: On the Hölder Stability of Multiset and Graph Neural Networks
- Title(参考訳): マルチセット・グラフニューラルネットワークのヘルダー安定性について
- Authors: Yair Davidson, Nadav Dym,
- Abstract要約: リプシッツとホルダーのパラメトリック関数への適応に基づくペアワイズ分離品質解析フレームワークを提案する。
一般的な和モデルでは,ネットワークの深さとともに急速に減衰する指数が期待値よりも低いことが証明される。
これらのMPNNは、敵の例を簡単に分類でき、標準的なグラフ学習タスクにおける標準MPNNと良好に比較できることを示す。
- 参考スコア(独自算出の注目度): 3.396731589928944
- License:
- Abstract: Extensive research efforts have been put into characterizing and constructing maximally separating multiset and graph neural networks. However, recent empirical evidence suggests the notion of separation itself doesn't capture several interesting phenomena. On the one hand, the quality of this separation may be very weak, to the extent that the embeddings of "separable" objects might even be considered identical when using fixed finite precision. On the other hand, architectures which aren't capable of separation in theory, somehow achieve separation when taking the network to be wide enough. In this work, we address both of these issues, by proposing a novel pair-wise separation quality analysis framework which is based on an adaptation of Lipschitz and \Holder{} stability to parametric functions. The proposed framework, which we name \emph{\Holder{} in expectation}, allows for separation quality analysis, without restricting the analysis to embeddings that can separate all the input space simultaneously. We prove that common sum-based models are lower-\Holder{} in expectation, with an exponent that decays rapidly with the network's depth . Our analysis leads to adversarial examples of graphs which can be separated by three 1-WL iterations, but cannot be separated in practice by standard maximally powerful Message Passing Neural Networks (MPNNs). To remedy this, we propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz in expectation. We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.
- Abstract(参考訳): マルチセットとグラフのニューラルネットワークを最大限に分離したネットワークを特徴付け、構築する大規模な研究努力が続けられている。
しかし、最近の実証的な証拠は、分離の概念自体がいくつかの興味深い現象を捉えていないことを示唆している。
一方、この分離の質は非常に弱く、「分離可能な」物体の埋め込みが固定された有限精度で同一視される程度である。
一方、理論的には分離できないアーキテクチャは、ネットワークを十分に広くするときに何らかの方法で分離を実現する。
本稿では,リプシッツとホルダー{}安定性のパラメトリック関数への適応に基づく新しいペアワイズ分離品質分析フレームワークを提案することにより,これらの問題に対処する。
提案するフレームワークでは,すべての入力空間を同時に分離できる埋め込みに制限を加えることなく,品質分析を分離することができる。
我々は、一般的な和ベースのモデルが期待値よりも低いことを証明し、ネットワークの深さとともに急速に減衰する指数を持つ。
解析の結果,3つの1-WLイテレーションで分離できるグラフの逆例が得られたが,MPNN(Message Passing Neural Networks)では事実上分離できない。
これを改善するために,分離品質を向上した2つの新しいMPNNを提案し,そのうちの1つはリプシッツの低下を期待する。
これらのMPNNは、敵の例を簡単に分類でき、標準的なグラフ学習タスクにおける標準MPNNと良好に比較できることを示す。
関連論文リスト
- Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs [77.42221150848535]
我々は、Multiset to Multiset GNN(M2M-GNN)と呼ばれる新しいメッセージパッシング機能を提案する。
M2M-GNNは上述のSMPの限界を効果的に緩和し, 比較性能が向上することを示した。
論文 参考訳(メタデータ) (2024-05-31T07:39:22Z) - Manifold Filter-Combine Networks [22.19399386945317]
マニフォールドフィルタ・コミンネットワーク(MFCN)と呼ばれる多様体ニューラルネットワーク(MNN)のクラスを導入する。
このクラスは、様々な人気のあるグラフニューラルネットワーク(GNN)の多様体アナログと考えることができる様々なサブクラスを含んでいる。
論文 参考訳(メタデータ) (2023-07-08T23:19:53Z) - Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。
連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。
また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
論文 参考訳(メタデータ) (2023-06-06T14:12:23Z) - MGNNI: Multiscale Graph Neural Networks with Implicit Layers [53.75421430520501]
暗黙グラフニューラルネットワーク(GNN)は、基礎となるグラフの長距離依存性をキャプチャするために提案されている。
暗黙的GNNの2つの弱点は、長距離依存を捉えるための限られた有効範囲による制約付き表現性と、複数の解像度でグラフ上のマルチスケール情報をキャプチャする能力の欠如である。
グラフ上のマルチスケール構造をモデル化できる暗黙の層(MGNNI)を持つマルチスケールグラフニューラルネットワークを提案する。
論文 参考訳(メタデータ) (2022-10-15T18:18:55Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳(メタデータ) (2021-10-27T11:48:50Z) - Graph Capsule Aggregation for Unaligned Multimodal Sequences [16.679793708015534]
本稿では,グラフベースのニューラルモデルとカプセルネットワークを用いた非整合マルチモーダルシーケンスをモデル化するために,Graph Capsule Aggregation(GraphCAGE)を導入する。
シーケンスデータをグラフに変換することにより、前述のRNNの問題を回避することができる。
さらに、Capsule Networkの集約機能とグラフベースの構造により、我々のモデルは解釈可能になり、長距離依存の問題をよりよく解決できる。
論文 参考訳(メタデータ) (2021-08-17T10:04:23Z) - Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。
本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
論文 参考訳(メタデータ) (2021-06-08T13:26:56Z) - Weisfeiler and Lehman Go Topological: Message Passing Simplicial
Networks [3.0017241250121383]
MPSN(Message Passing Simplicial Networks)を提案します。
MPSNはsimplicial Complex (SC)上でメッセージパッシングを行うモデルである
我々は、MPSNがGNNが失敗する挑戦的な強正則グラフを区別できることを示すことによって、理論的な主張を実証的に支持する。
論文 参考訳(メタデータ) (2021-03-04T18:35:24Z) - On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。
我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
論文 参考訳(メタデータ) (2020-10-28T17:59:59Z) - Permutation-equivariant and Proximity-aware Graph Neural Networks with
Stochastic Message Passing [88.30867628592112]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。
既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。
ノードの近さを保つため,既存のGNNをノード表現で拡張する。
論文 参考訳(メタデータ) (2020-09-05T16:46:56Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳(メタデータ) (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。