💻 computer science

Shapes from Examples: Foundations of Shape Learning in Recursive SHACL

This paper investigates the problem of learning recursive SHACL shapes in the Description Logic ELI fragment from positive and negative node examples, establishing tight exponential-time upper bounds for fitting existence and most specific fitting computation while identifying polynomial-time solutions for special cases.

Original authors: Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan

Published 2026-07-31

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a massive, chaotic library where the books have no titles, no authors, and no shelves. They are just piled up in a giant heap, connected by invisible strings that show how one story relates to another. This is what a "knowledge graph" looks like to a computer: a giant web of facts about the world, from people and places to products and orders. Unlike a traditional library with rigid rules about where everything goes, this digital library is messy and flexible. But that flexibility creates a problem: how do you know if the information is actually correct? How do you spot a story that doesn't fit the pattern?

To fix this, computer scientists invented a system called SHACL (Shapes Constraint Language). Think of SHACL as a set of "molds" or "stencils." If you have a mold shaped like a "Valid Order," you can press it over your data. If the data fits perfectly inside the mold, it's good. If it spills over or has gaps, it's broken. But here's the tricky part: in a messy library, nobody knows what the perfect molds should look like. You can't just guess them. You need a way to learn what a "good" shape looks like by looking at examples of things that are good and things that aren't. This is the challenge of "shape learning": teaching a computer to draw the right stencil based on a few examples of success and failure.

This paper, titled "Shapes from Examples: Foundations of Shape Learning in Recursive SHACL," dives deep into the math behind teaching computers to draw these stencils. The authors, researchers from TU Wien and Paderborn University, tackle a specific and difficult version of this problem. They focus on a scenario where the rules can be recursive—meaning a rule can refer to itself, like a story that loops back on its own ending. They ask: If I show you a list of "good" examples (positive) and "bad" examples (negative), can you write a rule that catches all the good ones and none of the bad ones? And if there are many possible rules, can you find the best one—the most specific rule that describes the pattern without being too vague?

The researchers prove that for a specific, powerful type of rule (which they call ELI∗, a fancy way of saying rules that can describe paths of any length, even loops), this task is computationally possible but very hard. They show that finding any rule that fits the examples is a problem that takes a massive amount of computing power to solve, specifically a complexity class known as "ExpTime-complete." This means that as your data grows, the time it takes to find the answer grows exponentially, like a snowball rolling down a hill getting bigger and bigger. However, they don't just say "it's hard"; they provide a concrete method to do it. They designed an algorithm that can decide if a perfect rule exists and, if it does, actually build it.

One of the most exciting findings is about speed. While the general problem is slow, the authors discovered a "sweet spot." If the number of "good" examples you give the computer is small and fixed (like just a handful of examples), the problem suddenly becomes much easier, solvable in "polynomial time." This is a huge deal because it means that in many practical situations where you only have a few examples to start with, a computer could learn these complex, looping rules very quickly. They also explored different ways the computer could interpret the rules (called semantics) and found their methods work reliably across all the major ways these rules are currently understood.

In short, this paper lays the mathematical foundation for a new kind of AI that can look at a messy web of data, spot the patterns in a few examples, and automatically generate the strict rules needed to keep that data clean. It proves that while the math is tough, it's not impossible, and it gives us the tools to build systems that can learn the "shape" of truth from a few scattered examples.

Technical Summary: Shapes from Examples: Foundations of Shape Learning in Recursive SHACL

Problem Statement

The paper addresses the fundamental challenge of learning SHACL shapes from data examples. While Knowledge Graphs and RDF graphs lack rigid schemas, ensuring data quality requires structural validation via SHACL (Shapes Constraint Language). The authors investigate the "fitting" approach: given a data graph $G$ and two sets of nodes, positive examples $P$ and negative examples $N$ , the goal is to compute a shape expression $C$ that validates at every node in $P$ and none in $N$ .

The study focuses on recursive SHACL, where shape definitions may contain cyclic dependencies and negation. To ensure the problem remains non-trivial (avoiding trivial solutions like enumerating positive examples via disjunctions or nominals), the authors restrict the target language to a core fragment of SHACL corresponding to the Description Logic ELI $^*$ . This logic extends ELI with reflexive transitive closure ( $r^*$ ) on roles, allowing the expression of reachability over paths of arbitrary length, which is crucial for graph-structured data.

The problem is analyzed under three standard semantics for recursive SHACL:

Well-Founded Semantics (WFS)
Stable Semantics (STS)
Supported Semantics (SUS)

The authors tackle two specific decision and computation problems:

Fitting Existence: Does there exist an ELI $^*$ shape that fits the given examples?
Most Specific Fitting (MSF): If a fitting exists, is there a "most specific" one (a shape that is more specific than all other valid fittings), and can it be computed?

Methodology

1. Formal Framework and Semantics

The authors formalize the fitting problem using adorned graphs. By Lemma 1, solving a fitting problem with a shape catalogue $C$ under a specific semantics $S$ is equivalent to solving the problem on an adorned graph $G_\alpha$ (where nodes are labeled with the shapes they satisfy under assignment $\alpha$ ) with an empty catalogue. This reduction allows the authors to decouple the complexity of the catalogue semantics from the fitting computation itself.

2. Complexity of Fitting Existence

To determine the existence of an ELI $^*$ fitting, the authors employ Two-Way Alternating Parity Tree Automata (2ATA).

Pre-matches: They define a "pre-match" as a homomorphism from an ELI $^*$ description tree (representing a shape) to a pointed graph that respects reflexive transitive closures.
Automaton Construction: For each positive example $p \in P$ , they construct a 2ATA $A_{G,p}$ that accepts trees having a pre-match into $(G, p)$ . For each negative example $n \in N$ , they construct the complement automaton $\overline{A_{G,n}}$ which accepts trees that do not have a pre-match into $(G, n)$ .
Intersection: The intersection of these automata accepts exactly those trees representing valid fittings.
Boundedness: They prove (Lemma 4) that if a fitting exists, one exists with a description tree degree bounded by the number of nodes in $G$ ( $|V|$ ). This ensures the automata operate on a finite, manageable structure.

3. Computation of Most Specific Fittings (MSF)

For computing the MSF, the authors move away from automata to a constructive approach based on graph products and unravellings.

Star Product: They define a "star product" $\Pi^\star(G, v^+, \Sigma)$ $Π^{⋆} (G, v^{+}, Σ)$ of the positive examples. This involves:
1. Making the graph $\star$ -closed (explicitly adding $r^\star$ edges for all $r^*$ reachability).
2. Computing the standard product of the pointed graphs.
3. Removing redundant $r^\star$ edges.
Simulation and Unravelling: The MSF candidate is the shape corresponding to the unravelling of this star product. However, an MSF only exists if this unravelling is finite and complete (i.e., it captures all necessary simulations without infinite expansion).
Algorithm: The authors present algorithms (Alg. 1 and Alg. 2) that:
1. Construct the star product.
2. Check if the product fits the negative examples (does not simulate any $n \in N$ ).
3. Compute the depth of a Complete Bounded Unravelling (CBU). If a CBU exists, its corresponding shape is the MSF.

Key Contributions and Results

Complexity Bounds

Fitting Existence: The problem of deciding the existence of an ELI $^*$ fitting is ExpTime-complete under WFS, STS, and SUS. This holds even for empty catalogues. The hardness is inherited from EL fitting, and the authors show that the added expressivity of $r^*$ does not increase the worst-case complexity.
MSF Existence and Computation: Deciding the existence of an ELI $^*$ MSF and computing it is also in ExpTime under all three semantics.
Polynomial Tractability: A significant finding is that if the number of positive examples $|P|$ is bounded by a constant, the MSF existence and computation problems become Polynomial Time (PTime) under the Well-Founded Semantics (WFS). This is because WFS yields a unique, polynomially computable adorned graph, and the star product construction becomes polynomial when $|P|$ is fixed.

Theoretical Insights

ELI vs. ELI $^*$ MSF: The existence of an ELI $^*$ MSF implies the existence of an ELI MSF, but the converse is false. The authors provide examples where an ELI MSF exists, but no ELI $^*$ MSF exists because the most specific ELI $^*$ fitting requires infinite expansion (due to cycles and $r^*$ ).
Semantics Independence: The results for fitting existence and MSF computation hold for any semantics that satisfies the conditions in Theorem 1 (unique well-founded assignment, polynomial computability of assignments, and polynomial testing of assignments).

Significance and Claims

The paper claims to provide the first systematic formal analysis of the limits and properties of learning algorithms for SHACL. Prior work has focused on pragmatic, machine-learning-based approaches or combinatorial manipulations without rigorous formal guarantees regarding soundness, completeness, and termination.

The authors state that their work:

Establishes Foundations: Provides robust formal guarantees (soundness, completeness, termination) for SHACL shape learning.
Defines Complexity: Precisely characterizes the computational complexity (ExpTime-completeness) of the fitting problem in the presence of recursion and path expressions.
Identifies Tractability: Highlights specific conditions (bounded positive examples under WFS) where the problem is tractable, offering a pathway for efficient algorithms in practical scenarios.
Lays Groundwork: Serves as a basis for future research into broader fragments of SHACL, including features like counting, path equality, and closedness, as well as the development of practical algorithms for real-world RDF graphs.

The paper explicitly notes that it does not propose new experimental benchmarks or applications but rather focuses on the theoretical underpinnings necessary to build such tools. It acknowledges that while the results are theoretical, they are intended to guide the development of future efficient learning algorithms.