論文の概要: Instruction set for the representation of graphs

• arxiv url: http://arxiv.org/abs/2603.11039v1
• Date: Wed, 11 Mar 2026 17:57:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-12 16:22:33.09514
• Title: Instruction set for the representation of graphs
• Title（参考訳）: グラフ表現のための命令セット
• Authors: Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez,
• Abstract要約: 有限な単純なグラフの構造を9文字の命令上のコンパクトな文字列として表現するIsalGraphを提案する。 鍵となる性質は、アルファベット上の全ての文字列が有効なグラフにデコードされ、無効な状態が到達できないことである。 実世界の5つのグラフベンチマークデータセットの表現を評価する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We present IsalGraph, a method for representing the structure of any finite, simple graph as a compact string over a nine-character instruction alphabet. The encoding is executed by a small virtual machine comprising a sparse graph, a circular doubly-linked list (CDLL) of graph-node references, and two traversal pointers. Instructions either move a pointer through the CDLL or insert a node or edge into the graph. A key design property is that every string over the alphabet decodes to a valid graph, with no invalid states reachable. A greedy \emph{GraphToString} algorithm encodes any connected graph into a string in time polynomial in the number of nodes; an exhaustive-backtracking variant produces a canonical string by selecting the lexicographically smallest shortest string across all starting nodes and all valid traversal orders. We evaluate the representation on five real-world graph benchmark datasets (IAM Letter LOW/MED/HIGH, LINUX, and AIDS) and show that the Levenshtein distance between IsalGraph strings correlates strongly with graph edit distance (GED). Together, these properties make IsalGraph strings a compact, isomorphism-invariant, and language-model-compatible sequential encoding of graph structure, with direct applications in graph similarity search, graph generation, and graph-conditioned language modelling
• Abstract（参考訳）: 有限な単純なグラフの構造を9文字の命令アルファベット上のコンパクトな文字列として表現するIsalGraphを提案する。 符号化は、スパースグラフと、グラフノード参照の円形二重リンクリスト(CDLL)と、2つのトラバースポインタとからなる小さな仮想マシンによって実行される。 命令は、ポインタをCDLLに移動させるか、ノードやエッジをグラフに挿入する。 鍵となる設計特性は、アルファベット上の全ての文字列が有効なグラフにデコードされ、無効な状態が到達できないことである。 greedy \emph{GraphToString} アルゴリズムは、任意の連結グラフをノード数における時間多項式の文字列にエンコードする。 実世界の5つのグラフベンチマークデータセット(IAM Letter LOW/MED/HIGH, LINUX, AIDS)の表現を評価し,IsalGraph文字列間のLevenshtein距離がグラフ編集距離(GED)と強く相関していることを示す。 これらの性質は、IsalGraph文字列をコンパクトで同型不変かつ言語モデル互換なグラフ構造のシーケンシャルエンコーディングとし、グラフ類似性探索、グラフ生成、グラフ条件付き言語モデリングに直接応用する。

関連論文リスト

• GraphSOS: Graph Sampling and Order Selection to Help LLMs Understand Graphs Better [13.742220809751627]
  GraphSOSは、グラフデータを自然言語テキストに変換する新しいフレームワークである。 Order Selector Moduleはグラフの適切なシリアライズ順序を保証するもので、Subgraph Smpling Moduleはより良い推論のためにより良い構造を持つサブグラフをサンプリングする。 ノード分類とグラフ問合せのための複数のデータセットの実験は、GraphSOSがグラフタスクにおけるLLMのパフォーマンスと能力を改善することを示した。
  論文  参考訳（メタデータ） (2025-01-24T11:55:57Z)
• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。 MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。 本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
  論文  参考訳（メタデータ） (2024-05-31T09:26:26Z)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。 既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。 本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-04-10T15:41:53Z)
• GraphEdit: Large Language Models for Graph Structure Learning [14.16155596597421]
  グラフ構造学習(GSL)は、グラフ構造データ中のノード間の固有の依存関係と相互作用をキャプチャすることに焦点を当てている。 既存のGSL法は、監督信号として明示的なグラフ構造情報に大きく依存している。 グラフ構造化データの複雑なノード関係を学習するために,大規模言語モデル(LLM)を利用したグラフ編集を提案する。
  論文  参考訳（メタデータ） (2024-02-23T08:29:42Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  我々は、非ユークリッドグラフを学習可能なグラフワードに変換するGraph2Seqエンコーダを特徴とするGraphsGPTを紹介する。 GraphGPTデコーダは、元のグラフをGraph Wordsから再構成し、情報等価性を保証する。
  論文  参考訳（メタデータ） (2024-02-04T12:29:40Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
  グラフ上の部分グラフ同型カウントは重要な問題である。 本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
  論文  参考訳（メタデータ） (2023-02-07T05:32:11Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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