論文の概要: On dimensionality of feature vectors in MPNNs

• arxiv url: http://arxiv.org/abs/2402.03966v1
• Date: Tue, 6 Feb 2024 12:56:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 14:54:07.061356
• Title: On dimensionality of feature vectors in MPNNs
• Title（参考訳）: MPNNにおける特徴ベクトルの次元性について
• Authors: C\'esar Bravo, Alexander Kozachinskiy, Crist\'obal Rojas
• Abstract要約: 我々は、メッセージパッシンググラフニューラルネットワーク(MPNN)がWeisfeiler--Leman(WL)同型テストに対する識別力に等しいというモリスら(AAAI'19)の古典的な結果を再考する。 我々は,MPNNがWLテストと同値であることを保証するために,非ポリノミカルな(シグモイドのような)アクティベーション関数を具現化するために,次元$d=1$の特徴ベクトルがすべて必要であることを示す。
• 参考スコア（独自算出の注目度）: 49.32130498861987
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and $O(n)$-dimensional feature vectors, where $n$ is the number of nodes of the graph. Recently, by introducing randomness into the architecture, Aamand et al.~(NeurIPS'22) were able to improve this bound to $O(\log n)$-dimensional feature vectors, although at the expense of guaranteeing perfect simulation only with high probability. In all these constructions, to guarantee equivalence to the WL test, the dimension of feature vectors in the MPNN has to increase with the size of the graphs. However, architectures used in practice have feature vectors of constant dimension. Thus, there is a gap between the guarantees provided by these results and the actual characteristics of architectures used in practice. In this paper we close this gap by showing that, for \emph{any} non-polynomial analytic (like the sigmoid) activation function, to guarantee that MPNNs are equivalent to the WL test, feature vectors of dimension $d=1$ is all we need, independently of the size of the graphs. Our main technical insight is that for simulating multi-sets in the WL-test, it is enough to use linear independence of feature vectors over rationals instead of reals. Countability of the set of rationals together with nice properties of analytic functions allow us to carry out the simulation invariant over the iterations of the WL test without increasing the dimension of the feature vectors.
• Abstract（参考訳）: morrisらによる古典的結果を再検討する。 ~(aaai'19) メッセージパッシンググラフニューラルネットワーク(mpnn)は、weisfeiler-leman (wl) 同型テストと区別力において等しい。 モリスら。 ~reluアクティベーション関数と$o(n)$-dimensional feature vectorでシミュレーション結果を示し、ここで$n$はグラフのノード数である。 最近、アーキテクチャにランダム性を導入することで、Aamand et al。 ~(NeurIPS'22)は$O(\log n)$-dimensional特徴ベクトルへのバウンドを改善できたが、完全なシミュレーションは高い確率でしか保証できなかった。 これらすべての構成において、WLテストと等価性を保証するため、MPNNにおける特徴ベクトルの次元はグラフのサイズによって増加する必要がある。 しかし、実際に使われるアーキテクチャは定次元の特徴ベクトルを持つ。 したがって、これらの結果によって提供される保証と、実際に使用されるアーキテクチャの実際の特性との間にはギャップがある。 本稿では、sgmoid のアクティベーション関数のような)非多項解析関数 \emph{any} に対して、mpnn が wl テストと同値であることを保証するために、次元 $d=1$ の特徴ベクトルは、グラフのサイズとは無関係に、我々が必要とするすべてであることを示すことにより、このギャップを閉じる。 我々の主要な技術的洞察は、WLテストにおける多重集合をシミュレートするには、実数ではなく有理数上の特徴ベクトルの線形独立性を利用するだけで十分であるということである。 解析関数の優れた性質とともに有理数の集合の可算性は、特徴ベクトルの次元を増大させることなく、WLテストの反復に対してシミュレーション不変性を実行することができる。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• GRIL: A $2$-parameter Persistence Based Vectorization for Machine Learning [0.49703640686206074]
  本稿では,パラメータ持続モジュールに対してGRIL(Generalized Rank Invariant Landscape)と呼ばれる新しいベクトル表現を導入する。 このベクトル表現は1$-Lipschitz 安定であり、下層の濾過関数に対して微分可能であることを示す。 また、GRILがグラフニューラルネットワーク(GNN)に富む追加機能をキャプチャできることを示す性能の向上も観察している。
  論文  参考訳（メタデータ） (2023-04-11T04:30:58Z)
• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks [22.36443060418036]
  非同型グラフの識別におけるグラフニューラルネットワーク(GNN)の表現力は、Weisfeiler-Lehmanグラフテストと全く同じであることを示す。 本稿では,GNN 上での WL テストの高速化について述べる。
  論文  参考訳（メタデータ） (2022-11-06T22:38:49Z)
• On the Identifiability and Estimation of Causal Location-Scale Noise Models [122.65417012597754]
  位置スケール・異方性雑音モデル(LSNM)のクラスについて検討する。 症例によっては, 因果方向が同定可能であることが示唆された。 我々は,LSNMの2つの推定器を提案し,その1つは(非線形)特徴写像に基づく推定器と,1つはニューラルネットワークに基づく推定器を提案する。
  論文  参考訳（メタデータ） (2022-10-13T17:18:59Z)
• A Feedforward Unitary Equivariant Neural Network [3.6220250022337335]
  我々は新しいタイプのフィードフォワードニューラルネットワークを考案した。 これはユニタリ群 $U(n)$ に対して同変である。 入力と出力は任意の次元が$n$の$mathbbCn$のベクトルである。
  論文  参考訳（メタデータ） (2022-08-25T15:05:02Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks [0.0]
  最大固有値は、よく知られた線形確率行列のアンサンブルと同じ極限(確率)を持つことを示す。 これは機械学習の応用にとって大きな関心事かもしれない。
  論文  参考訳（メタデータ） (2022-01-13T00:48:20Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。 得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
  論文  参考訳（メタデータ） (2021-05-21T14:26:28Z)
• On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression [79.86233860519621]
  我々は,ディープニューラルネットワーク(DNN)に基づくベクトル-ベクトル回帰の損失関数として,平均絶対誤差(MAE)の特性を利用する。 我々は,MAEをラプラシアン分布によってモデル化された誤差として解釈できることを示す。
  論文  参考訳（メタデータ） (2020-08-12T22:41:26Z)
• Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
  我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。 実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
  論文  参考訳（メタデータ） (2020-06-29T05:15:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。