aiqbench analysis
This research addresses the computational complexity of automatically learning SHACL shapes from positive and negative examples within knowledge graphs, focusing on specific fragments of Description Logic ELI. The study establishes tight exponential-time upper bounds for general fitting problems while identifying polynomial solutions for relevant special cases under well-founded semantics.
Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
arXiv:2607.27934v2 Announce Type: replace 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.
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.
Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO)
arXiv:2607.27934 [cs.AI]
(or arXiv:2607.27934v2 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2607.27934 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 219 words
