从示例学习图形结构，自动构建知识图谱验证规则。
Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
- 基于正负示例节点，用递归形状目录生成匹配规则
- 在ELI描述逻辑下证明存在性与最具体解的计算复杂度为指数级
- 对特定情形给出多项式时间算法，适合知识图谱自动化构建
SHACL形状用于数据图验证，因此自动形状学习对知识图谱应用至关重要。本文研究经典的拟合方法：给定输入图中正例节点集P和负例节点集N，计算一个形状表达式C（可使用递归形状目录中的形状名称），使得所有P中节点被验证通过，而所有N中节点不被验证通过。我们聚焦于C采用对应描述逻辑ELI的核心片段的情形。针对形状目录，考虑良基、稳定和支撑语义。本文解决了拟合存在性及最具体拟合计算问题，建立了两个问题的紧致指数时间上界，并在相关特殊情况下获得多项式时间上界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。