# Shapes from Examples: Foundations of Shape Learning in Recursive SHACL

arXiv: https://arxiv.org/abs/2607.27934 · HTML: https://mlsanity.com/paper/2607.27934/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 30 Jul 2026.

## Builds on (most cited first, 5 of 5)

- [Fixpoint Semantics for Recursive SHACL](https://mlsanity.com/paper/2109.08285/) (2021)
- [Extremal Fitting Problems for Conjunctive Queries](https://mlsanity.com/paper/2206.05080/) (2022)
- [Common Foundations for SHACL, ShEx, and PG-Schema](https://mlsanity.com/paper/2502.01295/) (2025)
- [On the Power and Limitations of Examples for Description Logic Concepts](https://mlsanity.com/paper/2412.17345/) (2024)
- [Extremal Separation Problems for Temporal Instance Queries](https://mlsanity.com/paper/2405.03511/) (2024)

## Abstract (arXiv)

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.