論文の概要: Exponentially Improving the Complexity of Simulating the
Weisfeiler-Lehman Test with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2211.03232v1
- Date: Sun, 6 Nov 2022 22:38:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 16:00:10.666738
- Title: Exponentially Improving the Complexity of Simulating the
Weisfeiler-Lehman Test with Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークを用いたWeisfeiler-Lehmanテストの複雑さの指数論的改善
- Authors: Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt
Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner
- Abstract要約: 非同型グラフの識別におけるグラフニューラルネットワーク(GNN)の表現力は、Weisfeiler-Lehmanグラフテストと全く同じであることを示す。
本稿では,GNN 上での WL テストの高速化について述べる。
- 参考スコア（独自算出の注目度）: 22.36443060418036
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent work shows that the expressive power of Graph Neural Networks (GNNs)
in distinguishing non-isomorphic graphs is exactly the same as that of the
Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test
can be simulated by GNNs. However, those simulations involve neural networks
for the 'combine' function of size polynomial or even exponential in the number
of graph nodes $n$, as well as feature vectors of length linear in $n$.
We present an improved simulation of the WL test on GNNs with
\emph{exponentially} lower complexity. In particular, the neural network
implementing the combine function in each node has only a polylogarithmic
number of parameters in $n$, and the feature vectors exchanged by the nodes of
GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds
for the feature vector length and the size of the neural networks, showing the
(near)-optimality of our construction.
- Abstract（参考訳）: 最近の研究は、非同型グラフを識別するグラフニューラルネットワーク(GNN)の表現力は、Weisfeiler-Lehmanグラフテストと全く同じであることを示している。
特に、彼らはWLテストがGNNによってシミュレート可能であることを示した。
しかし、これらのシミュレーションには、サイズ多項式の'結合'関数やグラフノード数を指数関数的に n$ とするニューラルネットワークや、n$ で線形な長さベクトルなどが含まれる。
本稿では,GNN 上での WL テストのシミュレーションを,より低い複雑性で改良した。
特に、各ノードに合成関数を実装するニューラルネットワークは、$n$のパラメータの多元数しか持たず、GNNのノードによって交換される特徴ベクトルは、$O(\log n)$ bitsのみである。
また、特徴ベクトル長とニューラルネットワークの大きさの対数的下界も与え、構築の(近く)最適性を示している。
関連論文リスト
- Non-convolutional Graph Neural Networks [46.79328529882998]
畳み込み演算子を完全に含まない単純なグラフ学習モジュールを設計し、RUMニューラルネットワークを用いたランダムウォークを作成した。
RUMは競合する性能を実現するが、より堅牢で、メモリ効率が高く、スケーラブルで、最も単純な畳み込みGNNよりも高速である。
論文 参考訳（メタデータ） (2024-07-31T21:29:26Z) - Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳（メタデータ） (2024-05-29T14:28:08Z) - Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。
このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
論文 参考訳（メタデータ） (2023-12-16T14:09:23Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳（メタデータ） (2023-05-18T07:27:18Z) - Higher-order Sparse Convolutions in Graph Neural Networks [17.647346486710514]
グラフ信号のソボレフノルムに基づく新しい高次スパース畳み込みを導入する。
S-SobGNNは、最先端のいくつかの手法と比較して、全てのアプリケーションで競合性能を示す。
論文 参考訳（メタデータ） (2023-02-21T08:08:18Z) - From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。
MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。
MPNNは、過密や過密といった問題に悩まされる可能性がある。
論文 参考訳（メタデータ） (2022-09-24T17:19:00Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳（メタデータ） (2021-06-12T07:43:51Z) - Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。
本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
論文 参考訳（メタデータ） (2021-06-08T13:26:56Z) - A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。
本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。
UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文 参考訳（メタデータ） (2020-10-05T04:57:18Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳（メタデータ） (2020-08-04T18:57:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。