論文の概要: On the uniqueness of compiling graphs under the parity transformation
- arxiv url: http://arxiv.org/abs/2401.11980v1
- Date: Mon, 22 Jan 2024 14:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 13:44:55.934980
- Title: On the uniqueness of compiling graphs under the parity transformation
- Title（参考訳）: パリティ変換下のコンパイルグラフの一意性について
- Authors: Florian Dreier, Wolfgang Lechner
- Abstract要約: グラフ理論の概念を用いてパリティ変換を,可能なすべてのハイパーグラフを包含するマッピングとして定義する。
パリティ変換が単射写像ではないことを示す最適化問題の具体例を示す。
本稿では,理論計算機科学の古典的アルゴリズムに基づくアルゴリズムを提案し,コンパイルされた物理レイアウトを時間内に計算する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this article, we establish a mathematical framework that utilizes concepts
from graph theory to define the parity transformation as a mapping that
encompasses all possible compiled hypergraphs, and investigate uniqueness
properties of this mapping in more detail. By introducing so-called loop
labelings, we derive an alternative expression of the preimage of any set of
compiled hypergraphs under this encoding procedure when all equivalences
classes of graphs are being considered. We then deduce equivalent conditions
for the injectivity of the parity transformation on any subset of all
equivalences classes of graphs. Moreover, we show concrete examples of
optimization problems demonstrating that the parity transformation is not an
injective mapping, and also introduce an important class of plaquette layouts
and their corresponding set of constraints whose preimage is uniquely
determined. In addition, we provide an algorithm which is based on classical
algorithms from theoretical computer science and computes a compiled physical
layout in this class in polynomial time.
- Abstract（参考訳）: 本稿では,グラフ理論の概念を利用して,解析可能なすべてのハイパーグラフを包含する写像としてパリティ変換を定義する数学的枠組みを確立し,この写像の特異性についてより詳細に検討する。
いわゆるループラベリングを導入することで、グラフのすべての同値類が考慮されている場合に、この符号化手順の下でコンパイルされた任意のハイパーグラフのプリイメージの代替表現を導出する。
すると、グラフのすべての同値類の任意の部分集合上のパリティ変換の単射性に対する等価条件を導出する。
さらに,パリティ変換が射影写像ではないことを示す最適化問題の具体例を示すとともに,プラーペットレイアウトの重要クラスとその先行画像が一意に決定される制約セットを導入する。
さらに,理論計算機科学の古典的アルゴリズムに基づくアルゴリズムを提供し,このクラスでコンパイルされた物理レイアウトを多項式時間で計算する。
関連論文リスト
- Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
グラフの有限集合がラプラシアンの重み付き和を通してデータ分布の関係を特徴付けるグラフ辞書信号モデルを定義する。
本稿では,観測データからグラフ辞書表現を推論するフレームワークを提案する。
我々は,脳活動データに基づく運動画像復号作業におけるグラフ辞書表現を利用して,従来の手法よりも想像的な動きをよりよく分類する。
論文 参考訳（メタデータ） (2024-11-08T17:40:43Z) - What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。
本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
論文 参考訳（メタデータ） (2024-06-04T05:30:16Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
複素構造特性をチェックできるグラフ同型を一般化する。
この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。
本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-15T18:12:44Z) - Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。
さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。
化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
論文 参考訳（メタデータ） (2022-11-03T10:18:17Z) - Self-Supervised Graph Representation Learning via Topology
Transformations [61.870882736758624]
本稿では,グラフデータのノード表現のための自己教師型学習の一般的なパラダイムであるトポロジー変換同変表現学習について述べる。
実験では,提案手法を下流ノードおよびグラフ分類タスクに適用し,提案手法が最先端の教師なし手法より優れていることを示す。
論文 参考訳（メタデータ） (2021-05-25T06:11:03Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳（メタデータ） (2021-03-05T04:42:32Z) - Articulated Shape Matching Using Laplacian Eigenfunctions and
Unsupervised Point Registration [38.16866987817019]
スペクトルグラフ理論は、これらのグラフを低次元空間にマッピングし、それらの埋め込みを整列させることで形状と一致させることができる。
我々は、ラプラシア行列の固有関数の最適部分集合を選択することによって、2つの同値な$K$-次元の点集合の最良の整合を求める新しい定式化を導出する。
論文 参考訳（メタデータ） (2020-12-14T08:49:25Z) - Building powerful and equivariant graph neural networks with structural
message-passing [74.93169425144755]
本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。
まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。
次に,メッセージのパラメトリゼーション手法を提案する。
論文 参考訳（メタデータ） (2020-06-26T17:15:16Z) - The general theory of permutation equivarant neural networks and higher
order graph variational encoders [6.117371161379209]
一般置換同変層の式を導出し、各層が列と列を同時に置換することで行列に作用する場合を含む。
このケースはグラフ学習や関係学習アプリケーションで自然に発生する。
2階グラフ変分エンコーダを提案し、同変生成モデルの潜在分布は交換可能である必要があることを示す。
論文 参考訳（メタデータ） (2020-04-08T13:29:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。