Point at a handful of nodes in a knowledge graph and say: these belong, those do not. That is the whole input. Out of it, a machine is supposed to write a rule, a formal description precise enough to check every other node in the database against. Four researchers, Bente Gortworst, Cem Okulmus, Magdalena Ortiz and Anni-Yasmin Turhan, have worked out what that job actually costs.

Their paper, posted to arXiv on 30 July 2026 and accepted at the ISWC26 conference, concerns SHACL. The name stands for a constraint language used to validate data graphs: a SHACL shape is a description a node either satisfies or fails. Think of it as a schema for messy, linked data. A shape might say that every node it applies to must have an author, and that the author must in turn have an affiliation. Run the shape over a graph and it sorts the nodes into passing and failing.

Writing shapes by hand is work, and knowledge graphs are large. So the appeal of learning them automatically is easy to see. The authors study what they call the fitting approach, which is the well-known formulation of this task: you are given a graph, a set P of positive example nodes and a set N of negative ones, and you must compute a shape expression that validates at every node in P and at none in N. Fitting is a familiar idea in machine learning, but here the object being learned is not a numeric model. It is a logical expression, and it has to be exactly right on the examples rather than approximately right.

What the team pinned down

Two questions organise the paper. The first is fitting existence: given the graph and the examples, does any shape do the job at all? Not every set of positive and negative examples can be separated by a shape in a given language, so this is a real question rather than a formality. The second is computing a most specific fitting, meaning the tightest shape that still covers all of P while excluding all of N. A shape that is too loose is technically correct and practically useless, since it would admit far more than the examples suggest.

For both questions the authors establish tight exponential-time upper bounds. "Tight" is the important word. An upper bound alone says an algorithm exists that runs within some limit; tightness means the limit cannot be improved, that the cost is genuinely there and not an artifact of a clumsy method. Exponential time means the work can grow steeply with the size of the input. That sounds discouraging, and in the general case it is a real constraint. But the team also identifies special cases, ones they describe as relevant, where the bounds drop to polynomial. Polynomial is the rough dividing line computer scientists use between what scales and what does not.

The paper narrows its scope deliberately. The shapes it considers are written in a core fragment of SHACL that corresponds to the description logic ELI, a small, well-understood logical language chosen because its behaviour is already mapped. And the shapes may refer to names defined in a shape catalogue that is recursive, meaning a shape's definition can refer back to itself or loop through others. Recursion is where SHACL gets genuinely difficult. When a definition points at itself, deciding what it means requires a semantics, a rule for resolving the circularity, and the community has more than one. The authors work with three: well-founded, stable and supported. Rather than pick a favourite, they analyse all three.

Why it matters

Knowledge graphs sit underneath a great deal of infrastructure, from product catalogues to biomedical databases to the structured data search engines consume. They are only as trustworthy as the constraints that police them, and those constraints are often absent because nobody had time to write them. Learning shapes from a few hand-picked examples is a plausible route to filling that gap, and it puts the human in the role they are best at: pointing at cases, not authoring logic.

What this paper supplies is the groundwork underneath that idea. Knowing that fitting existence and most specific fitting are solvable in exponential time, and that the bound is tight, tells tool builders where the hard edge is. Knowing that certain special cases fall to polynomial time tells them where to aim. The distinction matters more than it might sound: a system that is fast on the shapes people actually write is useful even if the general problem is expensive.

This is foundations work, and it should be read as such. The paper reports complexity results, not an implemented shape learner or an evaluation on real graphs. It is a preprint, though it has cleared peer review for ISWC26. What it settles is the shape of the problem itself, which is usually the thing you want settled before anyone builds on top of it.