将任意简单图编码为9字符指令串，支持高效相似性搜索与生成。
Instruction set for the representation of graphs
- 用虚拟机执行9字符指令，通过指针移动和节点插入构建图结构。
- 编码时间多项式，字符串间编辑距离与图编辑距离高度相关。
- 适合图相似性检索、生成及语言模型中的图条件建模任务。
我们提出IsalGraph，一种将任意有限简单图结构压缩为九字符指令字母表上的紧凑字符串的方法。编码由一个包含稀疏图、循环双向链表（CDLL）节点引用及两个遍历指针的微型虚拟机执行。指令可移动指针或向图中插入节点/边。关键设计特性是：所有字母表上的字符串解码后均对应有效图，无不可达无效状态。贪心的GraphToString算法可在节点数的多项式时间内将任意连通图编码为字符串；回溯变体通过在所有起始节点与合法遍历顺序中选择字典序最小的最短串，生成规范字符串。我们在五个真实世界图基准数据集（IAM Letter LOW/MED/HIGH、LINUX、AIDS）上评估该表示，结果显示IsalGraph字符串间的莱文斯坦距离与图编辑距离（GED）显著相关。这些特性使IsalGraph字符串成为紧凑、同构不变且兼容语言模型的图结构序列化编码，可直接应用于图相似性搜索、图生成及图条件语言建模。
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。