Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
arXiv:2607.27934
The paper studies automatic learning of SHACL shapes for knowledge graph validation by fitting positive and negative example nodes, focusing on a core SHACL fragment equivalent to the Description Logic ELI and analyzing different semantics for recursive shape catalogs.
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.
full version of a paper accepted at ISWC26