💻 computer science

Shapes from Examples: Foundations of Shape Learning in Recursive SHACL

Dit artikel onderzoekt het probleem van het leren van recursieve SHACL-shapes in het Description Logic ELI-fragment op basis van positieve en negatieve node-voorbeelden, waarbij nauwe exponentiële tijd bovengrenzen vaststelt voor het berekenen van de existentie en de meest specifieke passing, terwijl het polynomiale tijdoplossingen identificeert voor speciale gevallen.

Oorspronkelijke auteurs: Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan

Gepubliceerd 2026-07-31

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je door een enorme, chaotische bibliotheek loopt waar de boeken geen titels hebben, geen auteurs en geen planken. Ze liggen gewoon opgestapeld in een gigantische hoop, verbonden door onzichtbare draden die laten zien hoe het ene verhaal met het andere verband houdt. Dit is hoe een "knowledge graph" eruitziet voor een computer: een gigantisch web van feiten over de wereld, van mensen en plaatsen tot producten en bestellingen. In tegenstelling tot een traditionele bibliotheek met strikte regels over waar alles thuishoort, is deze digitale bibliotheek rommelig en flexibel. Maar die flexibiliteit creëert een probleem: hoe weet je of de informatie eigenlijk wel correct is? Hoe herken je een verhaal dat niet in het patroon past?

Om dit op te lossen, hebben computerwetenschappers een systeem uitgevonden genaamd SHACL (Shapes Constraint Language). Zie SHACL als een set "vormen" of "sjablonen". Als je een vorm hebt die de vorm heeft van een "Geldige Bestelling", kun je deze over je data heen drukken. Als de data er perfect in past, is het goed. Als het eroverheen stroomt of gaten vertoont, is het kapot. Maar hier komt het lastige deel bij: in een rommelige bibliotheek weet niemand hoe die perfecte vormen eruit moeten zien. Je kunt ze niet zomaar raden. Je hebt een manier nodig om te leren wat een "goede" vorm is door te kijken naar voorbeelden van dingen die wél goed zijn en dingen die dat niet zijn. Dit is de uitdaging van "shape learning": een computer leren om het juiste sjabloon te tekenen op basis van een paar voorbeelden van succes en falen.

Dit artikel, getiteld "Shapes from Examples: Foundations of Shape Learning in Recursive SHACL", duikt diep in de wiskunde achter het leren van computers om deze sjablonen te tekenen. De auteurs, onderzoekers van de TU Wien en de Universiteit van Paderborn, pakken een specifieke en moeilijke versie van dit probleem aan. Ze richten zich op een scenario waarin de regels recursief kunnen zijn—wat betekent dat een regel naar zichzelf kan verwijzen, zoals een verhaal dat terugkeert naar zijn eigen einde. Ze vragen zich af: als ik je een lijst geef van "goede" voorbeelden (positief) en "slechte" voorbeelden (negatief), kun je dan een regel schrijven die alle goede gevallen vangt en geen van de slechte? En als er veel mogelijke regels zijn, kun je dan de beste vinden—de meest specifieke regel die het patroon beschrijft zonder te vaag te zijn?

De onderzoekers bewijzen dat voor een specifieke, krachtige soort regel (die ze ELI∗ noemen, een chique manier om regels te beschrijven die paden van willekeurige lengte kunnen beschrijven, zelfs lussen), deze taak computationeel mogelijk maar zeer moeilijk is. Ze tonen aan dat het vinden van elke willekeurige regel die bij de voorbeelden past een probleem is dat een enorme hoeveelheid rekenkracht vereist om op te lossen, specifiek een complexiteitsklasse die bekend staat als "ExpTime-complete". Dit betekent dat naarmate je data groeit, de tijd die nodig is om het antwoord te vinden exponentieel toeneemt, zoals een sneeuwbal die een heuvel afrolt en steeds groter wordt. Echter, ze zeggen niet alleen "het is moeilijk"; ze bieden een concrete methode om het te doen. Ze hebben een algoritme ontworpen dat kan beslissen of er een perfecte regel bestaat en, als dat zo is, deze ook daadwerkelijk kan bouwen.

Een van de meest opwindende bevindingen gaat over snelheid. Hoewel het algemene probleem traag is, ontdekten de auteurs een "sweet spot". Als het aantal "goede" voorbeelden dat je de computer geeft klein en vaststaat (zoals slechts een handvol voorbeelden), wordt het probleem plotseling veel gemakkelijker en oplosbaar in "polynomiale tijd". Dit is een grote zaak, want het betekent dat in veel praktische situaties, waar je slechts een paar voorbeelden hebt om mee te beginnen, een computer deze complexe, lussenmakende regels zeer snel kan leren. Ze verkenden ook verschillende manieren waarop de computer de regels kan interpreteren (semantiek) en ontdekten dat hun methoden betrouwbaar werken over alle belangrijke manieren waarop deze regels momenteel worden begrepen.

Kortom, dit artikel legt de wiskundige fundering voor een nieuw soort AI dat naar een rommelig web van data kan kijken, patronen in een paar voorbeelden kan herkennen, en automatisch de strikte regels kan genereren die nodig zijn om die data schoon te houden. Het bewijst dat hoewel de wiskunde pittig is, het niet onmogelijk is, en het geeft ons de instrumenten om systemen te bouwen die de "vorm" van de waarheid kunnen leren uit een paar verspreide voorbeelden.

Technisch Samenvatting: Vormen uit Voorbeelden: Fundamenten van Vormleerproces in Recursieve SHACL

Probleemstelling

Het artikel behandelt de fundamentele uitdaging van het leren van SHACL-vormen uit datavoorbeelden. Hoewel Knowledge Graphs en RDF-grafen geen rigide schema's missen, vereist het waarborgen van datakwaliteit structurele validatie via SHACL (Shapes Constraint Language). De auteurs onderzoeken de "fitting"-benadering: gegeven een datagraf $G$ en twee verzamelingen knopen, positieve voorbeelden $P$ en negatieve voorbeelden $N$ , is het doel om een vormexpressie $C$ te berekenen die elke knoop in $P$ valideert en geen enkele in $N$ .

De studie richt zich op recursieve SHACL, waarbij vormdefinities cyclische afhankelijkheden en negatie kunnen bevatten. Om te voorkomen dat het probleem triviaal wordt (door het vermijden van triviale oplossingen zoals het enumereren van positieve voorbeelden via disjuncties of nominalen), beperken de auteurs de doeltaal tot een kernfragment van SHACL dat overeenkomt met de Description Logic ELI $^*$ . Deze logica breidt ELI uit met reflexieve transitieve afsluiting ( $r^*$ ) op rollen, wat de expressie van bereikbaarheid over paden van willekeurige lengte mogelijk maakt, wat cruciaal is voor grafische structuren.

Het probleem wordt geanalyseerd onder drie standaardsemantieken voor recursieve SHACL:

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

De auteurs pakken twee specifieke beslissings- en berekeningsproblemen aan:

Fitting Bestaan: Bestaat er een ELI $^*$ vorm die de gegeven voorbeelden past?
Meest Specifieke Fitting (MSF): Als een fitting bestaat, bestaat er dan een "meest specifieke" (een vorm die specifieker is dan alle andere geldige fittings), en kan deze worden berekend?

Methodologie

1. Formeel Kader en Semantiek

De auteurs formaliseren het fitting-probleem met behulp van geadorneerde grafen. Volgens Lemma 1 is het oplossen van een fitting-probleem met een vormcatalogus $C$ onder een specifieke semantiek $S$ equivalent aan het oplossen van het probleem op een geadorneerde graaf $G_\alpha$ (waarbij knopen zijn gelabeld met de vormen die ze voldoen onder toewijzing $\alpha$ ) met een lege catalogus. Deze reductie stelt de auteurs in staat om de complexiteit van de catalogussemantiek te ontkoppelen van de berekening van de fitting zelf.

2. Complexiteit van Fitting Bestaan

Om het bestaan van een ELI $^*$ fitting te bepalen, maken de auteurs gebruik van Two-Way Alternating Parity Tree Automata (2ATA).

Pre-matches: Ze definiëren een "pre-match" als een homomorfisme van een ELI $^*$ beschrijvingboom (die een vorm representeert) naar een gepunteerde graaf die de reflexieve transitieve afsluitingen respecteert.
Automaton Constructie: Voor elk positief voorbeeld $p \in P$ construeren ze een 2ATA $A_{G,p}$ die bomen accepteert die een pre-match hebben in $(G, p)$ . Voor elk negatief voorbeeld $n \in N$ construeren ze het complementaire automaat $\overline{A_{G,n}}$ dat bomen accepteert die geen pre-match hebben in $(G, n)$ .
Intersectie: De intersectie van deze automaten accepteert precies die bomen die geldige fittings representeren.
Begrensdheid: Ze bewijzen (Lemma 4) dat als een fitting bestaat, er een bestaat met een ELI $^*$ beschrijvingboom-graad begrensd door het aantal knopen in $G$ ( $|V|$ ). Dit zorgt ervoor dat de automaten opereren op een eindige, beheersbare structuur.

3. Berekening van Meest Specifieke Fittings (MSF)

Voor het berekenen van de MSF bewegen de auteurs weg van automaten naar een constructieve benadering gebaseerd op grafenproducten en unravellings.

Star Product: Ze definiëren een "star product" $\Pi^\star(G, v^+, \Sigma)$ $Π^{⋆} (G, v^{+}, Σ)$ van de positieve voorbeelden. Dit omvat:
1. Het maken van de graaf $\star$ -gesloten (het expliciet toevoegen van $r^\star$ randen voor alle $r^*$ bereikbaarheid).
2. Het berekenen van het standaardproduct van de gepunteerde grafen.
3. Het verwijderen van redundante $r^\star$ randen.
Simulatie en Unravelling: De MSF-kandidaat is de vorm die overeenkomt met de unravelling van dit star product. Een MSF bestaat echter alleen als deze unravelling eindig en volledig is (d.w.z. het vangt alle noodzakelijke simulaties zonder oneindige expansie).
Algoritme: De auteurs presenteren algoritmen (Alg. 1 en Alg. 2) die:
1. Het star product construeren.
2. Controleren of het product de negatieve voorbeelden past (geen enkele $n \in N$ simuleert).
3. De diepte van een Complete Bounded Unravelling (CBU) berekenen. Als een CBU bestaat, is de bijbehorende vorm de MSF.

Belangrijkste Bijdragen en Resultaten

Complexiteitsgrenzen

Fitting Bestaan: Het beslissen van het bestaan van een ELI $^*$ fitting is ExpTime-compleet onder WFS, STS en SUS. Dit geldt zelfs voor lege catalogi. De hardheid is overgenomen van EL fitting, en de auteurs tonen aan dat de toegevoegde expressiviteit van $r^*$ de worst-case complexiteit niet verhoogt.
MSF Bestaan en Berekening: Het beslissen van het bestaan van een ELI $^*$ MSF en het berekenen ervan is ook in ExpTime onder alle drie de semantieken.
Polyloog Tractabele: Een belangrijke bevinding is dat als het aantal positieve voorbeelden $|P|$ begrensd is door een constante, de MSF-existentie en -berekening problemen Polynomiale Tijd (PTime) worden onder de Well-Founded Semantics (WFS). Dit komt omdat WFS een unieke, polynomiaal berekenbare geadorneerde graaf oplevert, en de star product-constructie polynomiaal wordt wanneer $|P|$ vaststaat.

Theoretische Inzichten

ELI vs. ELI $^*$ MSF: Het bestaan van een ELI $^*$ MSF impliceert het bestaan van een ELI MSF, maar het omgekeerde is niet waar. De auteurs geven voorbeelden waar een ELI MSF bestaat, maar geen ELI $^*$ MSF bestaat omdat de meest specifieke ELI $^*$ fitting een oneindige expansie vereist (door cycli en $r^*$ ).
Semantiek Onafhankelijkheid: De resultaten voor fitting-existentie en MSF-berekening gelden voor elke semantiek die voldoet aan de voorwaarden in Theorem 1 (unieke well-founded toewijzing, polynomiale berekenbaarheid van toewijzingen, en polynomiale controle van toewijzingen).

Betekenis en Claims

Het artikel claimt de eerste systematische formele analyse te bieden van de grenzen en eigenschappen van algoritmen voor het leren van SHACL. Eerdere werken richtten zich op pragmatische, op machine learning gebaseerde benaderingen of combinatorische manipulaties zonder rigoureuze formele garanties met betrekking tot soundheid, volledigheid en terminatie.

De auteurs stellen dat hun werk:

Fundamenten Legt: Robuuste formele garanties (soundheid, volledigheid, terminatie) biedt voor het leren van SHACL-vormen.
Complexiteit Definieert: De computationele complexiteit (ExpTime-compleetheid) van het fitting-probleem in aanwezigheid van recursie en padexpressies nauwkeurig karakteriseert.
Tractabiliteit Identificeert: Specifieke condities belicht (gebonden positieve voorbeelden onder WFS) waar het probleem tractabel is, wat een pad biedt naar efficiënte algoritmen in praktische scenario's.
Grondslag Biedt: Dient als basis voor toekomstig onderzoek naar bredere fragmenten van SHACL, inclus inclusief functies zoals tellingen, pad-gelijkheid en geslotenheid, evenals de ontwikkeling van praktische algoritmen voor real-world RDF-grafen.

Het artikel merkt expliciet op dat het geen nieuwe experimentele benchmarks of toepassingen voorstelt, maar zich richt op de theoretische onderbouwing die nodig is om dergelijke instrumenten te bouwen. Het erkent dat hoewel de resultaten theoretisch zijn, ze bedoeld zijn om de ontwikkeling van toekomstige efficiënte leeralgoritmen te sturen.