論文の概要: Position Spaces and Graphs

• arxiv url: http://arxiv.org/abs/2606.25719v1
• Date: Wed, 24 Jun 2026 11:36:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 17:05:30.318146
• Title: Position Spaces and Graphs
• Title（参考訳）: 位置空間とグラフ
• Abstract要約: 位置空間の形式化に基づくグラフベースの推論フレームワークである位置グラフを導入する。 この表現の包括的理論的解析は、まずグラフの一貫性の特徴づけから始める。 この問題は、制限された位置グラフのクラスにおいてもNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 0.9134661726886929
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.
• Abstract（参考訳）: 本稿では,位置空間の形式化に基づくグラフベースの推論フレームワークである位置グラフを紹介する。 この枠組みは2つの厳密な部分順序、すなわち水平方向と垂直方向を表現し、離散トークンの相対的な位置をモデル化する。 一般的な定性的空間計算とは異なり、位置グラフは鎖条件と行や列にフォーカスする互換性要件によって制約される。 この表現の包括的理論的解析は、まずグラフの一貫性の特徴づけから始める。 位置グラフの整合性を確保する条件が確立される。 さらに, 構造パターン発見の計算複雑性について検討し, 帰納的部分グラフ同型問題としてモデル化した。 この問題は、制限された位置グラフのクラスにおいてもNP完全であることを示す。 最初は文書処理に動機づけられていたが、この研究は、基礎となる数学的性質と位置ベースの制約の代数的一貫性に焦点を当て、特定のデータ抽出技術に依存しない形式的な論理層を提供する。

関連論文リスト

• When Do Graph Foundation Models Transfer? A Data-Centric Theory [68.54337055801571]
  グラフ基盤モデル(GFMs)は、様々なグラフドメインにまたがる単一のバックボーンの再利用を目的としているが、それらの転送は不均一であり、負の転送を示すことがある。 我々は、セットベースおよびメッセージパストークン化の両方に対して、任意のリプシッツバックボーンは、クロスドメイン出力シフトの明示的な分解を認めていることを示す。 我々はスペクトルPEの安定性を保証するとともに、固有ベクトルと部分空間に基づくPEの対比挙動を強調する。
  論文  参考訳（メタデータ） (2026-05-28T12:07:27Z)
• A Theory of Random Graph Shift in Truncated-Spectrum vRKHS [26.195791008324495]
  本稿では,ランダムグラフ生成レンズによる領域シフトの下でのグラフ分類の理論を開発する。 我々は、同じランダムグラフモデル(RGM)を共有するクラス内グラフと、RGM成分の変化によって引き起こされる領域シフトについて考察する。
  論文  参考訳（メタデータ） (2026-02-27T10:19:57Z)
• Topological Spatial Graph Coarsening [1.4323566945483497]
  空間グラフの縮小の問題は、初期構造と同じ構造を持つより小さな空間グラフを見つけることを目的としている。 グラフの縮小とトポロジ特性の保存のトレードオフを見出す新しい枠組みに基づくトポロジカル空間グラフ粗大化手法を提案する。 粗いアプローチはパラメータフリーであり、初期空間グラフの回転、変換、スケーリングの下では同変であることが証明される。
  論文  参考訳（メタデータ） (2025-12-30T16:27:48Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• Harnessing spectral representations for subgraph alignment [15.86857474914914]
  本稿では,コンパクトで計算が容易で,トポロジ的変化に頑健で,既存のパイプラインに差し込むのが容易で,特に部分グラフアライメント問題に有効である地図のスペクトル表現を提案する。 サブグラフアライメントタスクで生じる部分性がマップ係数の特別な構造として表される驚くべき現象を初めて報告する。
  論文  参考訳（メタデータ） (2022-05-30T09:03:28Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  スペクトルグラフ理論は、これらのグラフを低次元空間にマッピングし、それらの埋め込みを整列させることで形状と一致させることができる。 我々は、ラプラシア行列の固有関数の最適部分集合を選択することによって、2つの同値な$K$-次元の点集合の最良の整合を求める新しい定式化を導出する。
  論文  参考訳（メタデータ） (2020-12-14T08:49:25Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  本稿では,グラフ構造形成の暗黙的モデルを学ぶエンドツーエンドフレームワークを提案し,その基盤となる最適化機構を明らかにする。 学習した目的は、観測されたグラフプロパティの説明として機能し、ドメイン内の異なるグラフを渡すために自分自身を貸すことができる。 GraphOptは、グラフ内のリンク生成をシーケンシャルな意思決定プロセスとして、最大エントロピー逆強化学習アルゴリズムを用いて解決する。
  論文  参考訳（メタデータ） (2020-07-07T16:51:39Z)

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

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