Fugu-MT 論文翻訳(概要): Is 3-(F)WL Enough to Distinguish All 3D Graphs?

論文の概要: Is 3-(F)WL Enough to Distinguish All 3D Graphs?

arxiv url: http://arxiv.org/abs/2402.08429v1
Date: Wed, 24 Jan 2024 06:22:08 GMT
ステータス: 処理完了
システム内更新日: 2024-02-18 13:29:55.045831
Title: Is 3-(F)WL Enough to Distinguish All 3D Graphs?
Title（参考訳）: 3-(F)WLは全3Dグラフを識別するのに十分か?
Authors: Wanghan Xu
Abstract要約: グラフ同型性の問題は、グラフ解析の分野において重要な問題であるが挑戦的な問題である。本稿では,グラフ生成の観点からこの問題を探究する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The problem of graph isomorphism is an important but challenging problem in the field of graph analysis, for example: analyzing the similarity of two chemical molecules, or studying the expressive ability of graph neural networks. WL test is a method to judge whether two graphs are isomorphic, but it cannot distinguish all non-isomorphic graphs. As an improvement of WL, k-WL has stronger isomorphism discrimination ability, and as k increases, its discrimination ability is strictly increasing. However, whether the isomorphic discrimination power of k-WL is strictly increasing for more complex 3D graphs, or whether there exists k that can discriminate all 3D graphs, remains unexplored. This paper attempts to explore this problem from the perspective of graph generation.
Abstract（参考訳）: 例えば、2つの化学分子の類似性を解析したり、グラフニューラルネットワークの表現能力を研究するなどである。 WLテストは、2つのグラフが同型かどうかを判断する手法であるが、すべての非同型グラフを区別することはできない。 WLの改善として、k-WLはより強い同型識別能力を有し、kが増加するにつれて、その識別能力は厳密に増大している。しかし、より複雑な3Dグラフに対して k-WL の同型判別力が厳密に増大しているか、あるいは、すべての3Dグラフを識別できる k が存在するかは未解明のままである。本稿では,グラフ生成の観点からこの問題を探究する。

関連論文リスト

Probing Graph Representations [77.7361299039905]
グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
論文参考訳（メタデータ） (2023-03-07T14:58:18Z)
CLEAR: Generative Counterfactual Explanations on Graphs [60.30009215290265]
グラフ上での対実的説明生成の問題について検討する。グラフに関する反実的な説明を調査する研究はいくつかあるが、この問題の多くの課題はまだ十分に適応されていない。本稿では,グラフレベルの予測モデルに対して,グラフ上の反実的説明を生成するための新しいフレームワークCLEARを提案する。
論文参考訳（メタデータ） (2022-10-16T04:35:32Z)
Quantum isomorphism of graphs from association schemes [0.0]
同じ数の頂点上の任意の2つのアダマールグラフが量子同型であることを示す。これは、ある関連スキームから生じるグラフの量子同型を示すより一般的なレシピから従う。
論文参考訳（メタデータ） (2022-09-10T03:22:28Z)
Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文参考訳（メタデータ） (2022-05-19T18:40:25Z)
Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
論文参考訳（メタデータ） (2021-11-15T12:16:21Z)
The expressive power of kth-order invariant graph networks [4.355567556995855]
我々は、kth-次不変(線形)グラフネットワーク(k-IGN)の表現力を考える。 k-IGN はWeisfeiler-Leman (k-WL) グラフ同型テストをシミュレートするのに十分な表現であることが知られている。 k-IGN は k-WL によって表現力で有界であることを示す。
論文参考訳（メタデータ） (2020-07-23T14:30:51Z)
GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
本稿では,グラフ構造形成の暗黙的モデルを学ぶエンドツーエンドフレームワークを提案し,その基盤となる最適化機構を明らかにする。学習した目的は、観測されたグラフプロパティの説明として機能し、ドメイン内の異なるグラフを渡すために自分自身を貸すことができる。 GraphOptは、グラフ内のリンク生成をシーケンシャルな意思決定プロセスとして、最大エントロピー逆強化学習アルゴリズムを用いて解決する。
論文参考訳（メタデータ） (2020-07-07T16:51:39Z)
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文参考訳（メタデータ） (2020-06-16T15:30:31Z)
Graph Homomorphism Convolution [19.94778871237204]
グラフ準同型数は、グラフ分類に使用できる自然な不変量(同型不変量および$mathcalF$-不変量)を提供することを示す。木幅が有界な元を持つ$mathcalF$を選択することで、同型法は他の方法と比較して効率的であることを示す。
論文参考訳（メタデータ） (2020-05-03T23:56:20Z)
Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文参考訳（メタデータ） (2020-02-10T18:53:30Z)

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