Fugu-MT 論文翻訳(概要): Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points

論文の概要: Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points

arxiv url: http://arxiv.org/abs/2303.12853v3
Date: Sat, 19 Apr 2025 16:26:51 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-30 16:44:30.612993
Title: Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points
Title（参考訳）: $(d-1)$-WLテストの3つの反復は、$d$-次元点の非等尺雲を区別する
Authors: Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, Pablo Barceló,
Abstract要約: Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。 $d$次元ユークリッド空間の任意の2つの非等尺点雲を区別するのに十分な次元はいくつあるか。我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサッフィスを3回だけ繰り返すことである。
参考スコア（独自算出の注目度）: 45.15780579276503
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud. %arbitrary clouds of euclidean points represented by complete distance graphs. % How many dimensions of the Weisfeiler--Lehman test is enough to distinguish any two non-isometric point clouds in $d$-dimensional Euclidean space, assuming that these point clouds are given as complete graphs labeled by distances between the points? This question is important for understanding, which architectures of graph neural networks are capable of fully exploiting the spacial structure of a point cloud. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and that only three iterations of the test suffice. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness. Our paper thus provides complete understanding of the 3-dimensional case: it was shown in previous works that 1-WL is not complete in $\mathbb{R}^3$, and we show that 2-WL is complete there. We also strengthen the lower bound for 1-WL by showing that it is unable to recognize planar point clouds in $\mathbb{R}^3$. Finally, we show that 2-WL is not complete in $\mathbb{R}^6$, leaving as an open question, whether it is complete in $\mathbb{R}^{d}$ for $d = 4,5$.
Abstract（参考訳）: Weisfeiler--Lehman (WL) テストはグラフの同型性をチェックするための基本的な反復アルゴリズムである。また、このテストの表現力の観点から、その能力と性能が理解できるグラフニューラルネットワークアーキテクチャの設計下にあることも確認されている。三次元オブジェクトを含むデータセットへの機械学習応用の最近の発展により、完全距離グラフで表されるユークリッド点の雲に対するWLテストがいつ完備になるか、すなわち、等距離まで、任意の任意の雲を区別できるか、が研究されている。 % のユークリッド点の任意雲は完全距離グラフで表される。 % ワイスフェイラー-リーマン検定の次元は、点間の距離によってラベル付けされた完全グラフとして与えられると仮定して、$d$次元ユークリッド空間の任意の2つの非等尺点雲を区別するのに十分である。この問題は、どのグラフニューラルネットワークのアーキテクチャが点雲の空間構造を完全に活用できるのかを理解する上で重要である。我々の主な結果は、$(d-1)$-dimensional WL テストは、$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$d\ge 2$ に対して完備であり、テストサフィスを3回だけ繰り返すことである。また、$d$-dimensional WL テストは完全性を達成するために 1 つの反復しか必要としない。そこで本論文では, 3次元の場合の完全理解について述べるとともに, 1-WL が $\mathbb{R}^3$ で完備でないことを示し, 2-WL が完備であることを示す。また、1-WL に対する下界は $\mathbb{R}^3$ の平面点雲を認識できないことを示して強化する。最後に、2-WL が $\mathbb{R}^6$ で完備でないことを示す。

関連論文リスト

Weisfeiler Leman for Euclidean Equivariant Machine Learning [3.0222726571099665]
PPGNは, 複雑度が低い全点クラウド上で, 均一に2$-WLをシミュレートできることを示す。第二に、2ドルのWLテストは、位置と速度の両方を含む点雲まで拡張可能であることを示す。
論文参考訳（メタデータ） (2024-02-04T13:25:18Z)
On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters [9.599347633285637]
k$次元Weisfeiler-Leman(k$WL)テストは、グラフ同型を検証するための広く認識されている方法である。本稿では,ラベル付きグラフモチーフパラメータのWL次元を正確に評価する。
論文参考訳（メタデータ） (2023-09-29T08:26:44Z)
Clustering based Point Cloud Representation Learning for 3D Analysis [80.88995099442374]
本稿では,ポイントクラウド分析のためのクラスタリングに基づく教師付き学習手法を提案する。現在のデファクトでシーンワイドなトレーニングパラダイムとは異なり、我々のアルゴリズムは点埋め込み空間上でクラス内のクラスタリングを行う。我々のアルゴリズムは、有名なポイントクラウドセグメンテーションデータセットの顕著な改善を示している。
論文参考訳（メタデータ） (2023-07-27T03:42:12Z)
Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。ベンチマークに基づく表現力の拡張的定義と測定について論じる。
論文参考訳（メタデータ） (2023-07-11T20:06:12Z)
Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。 N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文参考訳（メタデータ） (2023-06-05T21:35:32Z)
Point2Vec for Self-Supervised Representation Learning on Point Clouds [66.53955515020053]
Data2vecをポイントクラウド領域に拡張し、いくつかのダウンストリームタスクで推奨される結果を報告します。我々は、ポイントクラウド上でData2vecライクな事前トレーニングの可能性を解放するpoint2vecを提案する。
論文参考訳（メタデータ） (2023-03-29T10:08:29Z)
Complete Neural Networks for Complete Euclidean Graphs [4.416503115535553]
点雲の集中型グラム行列に3WLグラフ同型テストを適用することにより、点雲を完全に決定できることを示す。次に、中程度の大きさのユークリッドグラフニューラルネットワークによって、我々の完全なユークリッドテストがどのようにシミュレートされるかを示し、その分離能力を高度に対称な点雲上で実証する。
論文参考訳（メタデータ） (2023-01-31T18:07:26Z)
WL meet VC [9.468816647649104]
本稿では,Vapnik-Chervonenkis(VC)次元理論のレンズによるグラフニューラルネットワーク(GNN)の表現力について検討する。我々は、GNNのVC次元と1text-mathsfWL$およびGNNのVC次元によって生成される色数を用いて、GNNのVC次元の上限を導出する。
論文参考訳（メタデータ） (2023-01-26T11:29:36Z)
MATE: Masked Autoencoders are Online 3D Test-Time Learners [63.3907730920114]
MATEは3Dデータ用に設計された最初のTTT(Test-Time-Training)手法である。テストデータで発生する分散シフトに対して、ポイントクラウド分類のためにトレーニングされたディープネットワークを堅牢にする。
論文参考訳（メタデータ） (2022-11-21T13:19:08Z)
MetaSets: Meta-Learning on Point Sets for Generalizable Representations [100.5981809166658]
本稿では,3次元領域一般化(DDG)の新たな課題について検討し,学習過程においてそれらにアクセスすることなく,他の目に見えない点雲の領域にモデルを一般化することを目的とする。本稿ではメタセットを用いてこの問題に対処することを提案する。メタ学習は、慎重に設計された変換された点集合上の分類タスク群からポイントクラウド表現を抽出する。実験結果から,MetaSetsは既存の3次元深層学習手法よりも大きなマージンで優れていることが示された。
論文参考訳（メタデータ） (2022-04-15T03:24:39Z)
On the emergence of tetrahedral symmetry in the final and penultimate layers of neural network classifiers [9.975163460952045]
分類器の最終的な出力である$h$ であっても、$h$ が浅いネットワークである場合、$c_i$ のクラスからのデータサンプルは均一ではない。本研究は,高表現性深層ニューラルネットワークの玩具モデルにおいて,この観察を解析的に説明する。
論文参考訳（メタデータ） (2020-12-10T02:32:52Z)
PMP-Net: Point Cloud Completion by Learning Multi-step Point Moving Paths [54.459879603473034]
我々はPMP-Netと呼ばれる新しいニューラルネットワークを設計し、地球移動体の動作を模倣する。不完全な入力の各点を移動させ、ポイントクラウドを完結させ、ポイント移動パスの合計距離が最も短くなる。点レベルの厳密でユニークな対応を学習し、不完全な形状と完全なターゲットの間の詳細なトポロジーと構造的関係を捉えることができる。
論文参考訳（メタデータ） (2020-12-07T01:34:38Z)
Refinement of Predicted Missing Parts Enhance Point Cloud Completion [62.997667081978825]
点雲完了は、部分的な観測から3次元形状の点集合表現を用いて完全な幾何学を予測するタスクである。従来のアプローチでは、不完全点集合によって供給されるエンコーダ・デコーダモデルにより、点雲全体を直接推定するニューラルネットワークが提案されていた。本稿では、欠落した幾何を計算し、既知の入力と予測点クラウドを融合することに焦点を当てたエンドツーエンドニューラルネットワークアーキテクチャを提案する。
論文参考訳（メタデータ） (2020-10-08T22:01:23Z)

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

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