从示例中学习形状：递归 SHACL 中形状学习的理论基础
Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
AI 导读
一篇被 ISWC26 接收的论文研究从知识图谱的正例与反例节点集合中自动学习 SHACL 形状表达式，表达式限定在对应描述逻辑 ELI* 的 SHACL 核心片段，并考虑 well-founded、stable 与 supported 三种递归目录语义。论文解决了拟合存在性与最具体拟合计算两个问题，给出二者的指数时间紧上界，并在相关特殊情形下得到多项式界。
正文 · 原文
Abstract:SHACL shapes enable data graph validation, making automatic shape learning essential for knowledge graph applications. We investigate the well-known fitting approach to this task: given sets P and N of positive and negative example nodes from an input graph, compute a shape expression C, possibly using shape names defined in a recursive shape catalogue, that validates at every node in P and none in N. We focus on the case where C is written in a core fragment of SHACL corresponding to the Description Logic ELI*. For the catalogue, we consider the well-founded, stable, and supported semantics. We address fitting existence and most specific fitting computation, establish tight exponential-time upper bounds for both problems, and obtain polynomial bounds for relevant special cases.
| Comments: | full version of a paper accepted at ISWC26 |
| Subjects: | Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO) |
| Cite as: | arXiv:2607.27934 [cs.AI] |
| (or arXiv:2607.27934v3 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2607.27934 arXiv-issued DOI via DataCite |
Submission history
From: Cem Okulmus [view email]
[v1]
Thu, 30 Jul 2026 09:45:22 UTC (89 KB)
[v2]
Thu, 6 Aug 2026 12:02:36 UTC (88 KB)
[v3]
Fri, 23 Oct 2026 13:52:59 UTC (88 KB)
来源：arXiv cs.AI · arxiv.org