Fugu-MT 論文翻訳(概要): On the Expressibility of the Reconstructional Color Refinement

論文の概要: On the Expressibility of the Reconstructional Color Refinement

arxiv url: http://arxiv.org/abs/2406.09351v1
Date: Thu, 13 Jun 2024 17:38:26 GMT
ステータス: 処理完了
システム内更新日: 2024-06-14 16:25:49.639272
Title: On the Expressibility of the Reconstructional Color Refinement
Title（参考訳）: レコンストラクショナルカラーリファインメントの表現性について
Authors: V. Arvind, Johannes Köbler, Oleg Verbitsky,
Abstract要約: カラー精細アイソモーフィズムテストにおいて、デッキ内の部分グラフが同値となるとき、接続性は依然として決定可能であることを証明した。このことは、リコンストラクション予測にインスパイアされた近年導入されたGNNアーキテクチャであるReコンストラクショングラフニューラルネットワークによって、接続性が認識可能であることを示唆している。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness can still be determined when the subgraphs in the deck are given up to equivalence under the color refinement isomorphism test. Consequently, this implies that connectedness is recognizable by Reconstruction Graph Neural Networks, a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).
Abstract（参考訳）: 有名なウラムの再構成予想に関連する最も基本的な事実の1つは、グラフの連結性はその頂点が削除された部分グラフのデッキによって決定できることである。色精細同型テストにおいて,デッキ内の部分グラフが同値となるとき,接続性は依然として決定可能であることを証明して,この結果を補強する。このことは、リコンストラクション予想(Cotta, Morris, Ribeiro 2021)にインスパイアされた近年導入されたGNNアーキテクチャであるReコンストラクショングラフニューラルネットワークによって接続性が認識可能であることを示唆している。

関連論文リスト

Redesigning graph filter-based GNNs to relax the homophily assumption [31.368672838207022]
グラフニューラルネットワーク(GNN)は、不規則なドメイン上で定義されたデータから学習するためのワークホースアプローチとなっている。ホモフィリー仮定の限界を緩和するために設計された,単純で効果的なアーキテクチャを提案する。提案したアーキテクチャは、畳み込みGNNにおけるグラフフィルタの役割を再解釈し、より一般的なアーキテクチャとなる。
論文参考訳（メタデータ） (2024-09-13T09:43:36Z)
Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
我々は、よりきめ細かいアプローチを論じ、対象パターンの基底''にすべての構造の準同型数を含む。これにより計算複雑性の面で追加のオーバーヘッドを発生させずに、より表現力のあるアーキテクチャが得られる。
論文参考訳（メタデータ） (2024-02-13T16:57:06Z)
Transitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships [69.04014445666142]
Transitivity Recovering Decompositions (TRD) は、抽象的な創発的関係の解釈可能な等価性を識別するグラフ空間探索アルゴリズムである。 TRDは明らかにノイズの多い見方に対して堅牢であり、実証的な証拠もこの発見を支持している。
論文参考訳（メタデータ） (2023-10-24T16:48:56Z)
From axioms over graphs to vectors, and back again: evaluating the properties of graph-based ontology embeddings [78.217418197549]
埋め込みを生成するアプローチの1つは、名前付きエンティティと論理公理構造のためのノードとエッジのセットを導入することである。グラフに埋め込む方法(グラフ射影)は、それらが利用する公理の種類と異なる性質を持つ。
論文参考訳（メタデータ） (2023-03-29T08:21:49Z)
Knowledge Graph Reasoning with Relational Directed Graph [40.555874504438506]
文学における関係経路に基づく手法は、強く、解釈可能で、帰納的推論能力を示す。重なり合う関係経路からなる関係有向グラフ(r-digraph)を新たに導入する。本稿では,グラフニューラルネットワークの変種であるRED-GNNを提案し,GNNの変種を用いてRelational Digraphを学習する。
論文参考訳（メタデータ） (2021-08-13T03:27:01Z)
Temporally-Coherent Surface Reconstruction via Metric-Consistent Atlases [131.50372468579067]
再建された表面をニューラルネットワークを用いてアトラスとして表現する。本手法は,教師なし対応の精度と表面再構成の精度において,その性能を超える結果が得られることを実証的に示す。
論文参考訳（メタデータ） (2021-04-14T16:21:22Z)
Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文参考訳（メタデータ） (2020-12-06T03:42:54Z)
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文参考訳（メタデータ） (2020-06-16T15:30:31Z)
Bayesian network structure learning with causal effects in the presence of latent variables [6.85316573653194]
本稿では,cFCIの制約に基づく部分とスコアに基づく学習を組み合わせた,CCHMと呼ばれるハイブリッド構造学習アルゴリズムについて述べる。ランダム化されたネットワークとよく知られたネットワークの両方に基づく実験により、CCHMは真の祖先グラフの再構築の観点から最先端の改善を図っている。
論文参考訳（メタデータ） (2020-05-29T04:42:28Z)
Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文参考訳（メタデータ） (2020-02-10T18:53:30Z)
Analytic Properties of Trackable Weak Models [2.204918347869259]
強連結トラックブル弱モデルにおける隠れ状態の推測の可能性に関する新しい結果を示す。弱いモデルは、そのような仮説の最悪のケース数が列長のエントロピーとして増加すると追跡可能であると言われる。強連結な追跡可能モデルにおける仮説の数は定数で有界であることを示し、この定数に対する表現を与える。
論文参考訳（メタデータ） (2020-01-08T15:54:56Z)

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