arXiv cs.AI· Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan·· 12 小时前AI 评分18
从样例中学习形状：递归 SHACL 中形状学习的理论基础
Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
AI 导读
研究从正负样例节点集合 P 和 N 出发，计算 SHACL 形状表达式 C 使其验证 P 中全部节点且不验证 N 中任何节点，C 采用对应 Description Logic 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