Wissensgraphen

Wissensgraphen

Grundlagen von Wissensgraphen

Einleitung

Im Grunde ist ein Knowledge Graph, KG (Wissensgraph - WG) ein Graph, der Entitäten darstellt, wie z.B. „Josef Strauss“ oder „Wien“ mit begrenzten semantischen Beziehungen zwischen ihnen, wie z.B. ,,Ort_der_Geburt“. Die Entitäten werden durch die Knoten repräsentiert, während Kanten die semantischen Beziehungen angeben. Ein Knoten kann auch eine Gruppe ähnlicher Entitäten darstellen, wie z. B. „Person“, die als Klasse oder Konzept bezeichnet wird. Ein KG kann wie folgt durch seine Eigenschaften definiert werden. Ein KG

1. beschreibt reale Entitäten und ihre Beziehungen in Diagrammform,
2. definiert Konzepte und mögliche Beziehungen von Entitäten,
3. ermöglicht die potenzielle Verknüpfung beliebiger Entitäten miteinander und
4. deckt zahlreiche Themenbereiche ab.

Ein Beispiel für einen KG ist in Abbildung 7 dargestellt.

Abbildung 7: Beispiel für einen KG. Knoten repräsentieren Entitäten, Kanten repräsentieren semantische Beziehungen (Quelle: [Nickel et al.(2016)]).

Wissensdatenbank (Knowledge Base - KB) ist eine Datenbank, die das gleiche Wissen wie eine KG speichern kann. Daher realisiert der Wissensgraph die Wissensdatenbank in einem graphstrukturierten Datenmodell.

KG geht auf das Projekt „Knowledge Graphs“ zurück, das in den 1980er Jahren von zwei Universitäten in den Niederlanden ins Leben gerufen wurde, um spezifische semantische Netzwerke mit Kanten zu entwerfen, die eine eingeschränkte Menge von Beziehungen repräsentieren.

Zu den verwandten Bereichen der KG gehören Data Mining, NLP, Datenbanken, Ontologie und Semantic Web (SW). Die Beziehungen zu diesen Bereichen sind vielfältig. Methoden dieser Bereiche, wie z.B. NLP oder Ontologie tragen zum Erstellen von KG bei. Andererseits können KGs zum Durchführen einiger Aufgaben dieser Bereiche eingesetzt werden, wie dies bei mehreren Aufgaben im Data Mining oder NLP der Fall ist.

Data Mining beschäftigt sich mit dem Entdecken und Extrahieren von Mustern in großen Datenmengen, wie z.B. Sammlung von Ton- und Videodateien. Es handelt sich um ein interdisziplinäres Fachgebiet, da es Methoden aus der Statistik, ML oder Datenbanksystemen nutzt.

Bei der NLP geht es um die Identifizierung der syntaktischen und semantischen Struktur von Sprache in jeglicher Form mithilfe von ML-Techniken. Typische NLP-Aufgaben umfassen optische Texterkennung, Spracherkennung, Text-to-Speech, POS tagging oder Semantic Role Labeling (semantic role labeling). Bei der Semantic Role Labelling geht es darum, verbale Einheiten im gegebenen Satz zu identifizieren und zu klassifizieren.

Eine Datenbank kann als strukturierte Speicherung und Organisation von Daten und Datentypen betrachtet werden, die von einem Datenbankverwaltungssystem (database management system - DBMS) verwaltet wird. DBMS bietet in der Regel Dienste zum Zugriff und zur Manipulation der gespeicherten Inhalte an. Der Begriff „Datenbanksystem“ wird als Sammelbegriff für die Datenbank, das DBMS und die zugehörigen Anwendungen verwendet. Der Begriff „Datenbank“ wird auch allgemein für das Datenbanksystem verwendet. Für die Bearbeitung der in einer Datenbank gespeicherten Daten stehen Datenbanksprachen zur Verfügung. Eine beliebte Datenbanksprache ist die Structured Query Language (SQL), die zum Schreiben und Abfragen von Daten in zweidimensionalen relationalen Datenbanken verwendet wird.

Die Ontologie in der Informationswissenschaft befasst sich mit der Darstellung von Entitäten, Konzepten und den Beziehungen zwischen ihnen, wie z.B. Instanz (instance), Attribut (attribute) oder Eigenschaft (property) sein. Eine Ontologie-Sprache (ontology language) wird verwendet, um die in der Ontologie gespeicherten relationalen Informationen auszunutzen, d. h. um ontologische Aussagen (ontological statements) zu erstellen.

Das Semantic Web ist ein Konzept des maschinenlesbaren semantischen World Wide Web (semantic World Wide Web - semantic WWW). Es wird auch als Web 3.0 bezeichnet, da es durch Standards realisiert wird, die vom World Wide Web Consortium (W3C) zur Erweiterung des WWW erstellt wurden. Das Semantic Web wird durch die Veröffentlichung und Implementierung von Standards und Technologien zur Kodierung von Semantik in Daten realisiert, wie z.B. Resource Description Framework (RDF) Resource Description Framework und Web Ontology Language (OWL) Web Ontology Language.

Die Wurzeln der KG lassen sich in den verwandten Bereichenn erkennen. Einige davon sind unten aufgeführt.

• Die Schritte Named Entity Recognition (NER) und Relation Extraction (RE) der KG Konstruktion entstanden ursprünglich im Bereich der Informationsextraktion unter Anwendung von NLP.
• Das RDF-Framework, welches in KG weit verbreitet ist, stammt aus dem Bereich des Semantic Web.
• Das Empfehlungssystem, eine Anwendung von KG, basiert auf Knowledge Discovery in Databases (KDD), welches mit Data Mining in Beziehung steht.

Eine Folge dieser starken Verbindung von KG zu seinen verwandten Fachgebieten ist, dass es für das Fachgebiet KG keine einheitliche Terminologie gibt. Für die gleiche oder eine ähnliche Aufgabe gibt es in den verwandten Fachgebieten alternative, teilweise fachgebietsspezifische Namen. Beispielsweise wird der Schema-Matching, bei dem festgestellt wird, dass zwei Objekte semantisch verwandt sind (d. h. eine Beziehung haben), auch als Entity Resolution (ER), Type-Matching oder Ontology Alignment bezeichnet.

Elemente von KG

Im Kontext von KG werden Aussagen in Form von Tripletts (triplets) dargestellt: Subjekt, Prädikat, Objekt (subject, predicate, object). Zum Beispiel wird die Aussage „Wien ist die Hauptstadt Österreichs“ durch die Triplett modelliert: (,,Wien“, ,,Hauptstadt von“, „Österreich“). Hier ist „Wien“ das Subjekt, „Hauptstadt von“ ist das Prädikat, das sich auf das Objekt „Österreich“ bezieht. Das (Subjekt, Prädikat, Objekt) Triplett wird als (SPO-) Triplett abgekürzt. In einigen Kontexten werden die alternativen Namen „Head“, „Relation“ und „Tail“ für Subjekt, Prädikat bzw. Objekt verwendet.

Eine Wissensdatenbank kann als Container betrachtet werden, der Sachinformationen in Form von Entitäten und semantischen Beziehungen zwischen ihnen speichert. Die Fakten werden in Form von (SPO-)Tripletts dargestellt. KG ist eine grafische Darstellung von KB, in der alle (SPO-)Tripletts zu einem Diagramm zusammengefasst werden. Subjekte und Objekte werden als Knoten dargestellt, während jede markierte Kante als gerichtete Verbindung vom Subjekt zum Objekt das Prädikat zwischen ihnen darstellt. Auf diese Weise werden die Daten in der KG als Menge von Tripletts gespeichert. Abbildung 8 zeigt ein Beispiel KG

Abbildung 8: Ein Beispiel KG (Quelle: [Ji et al.(2022)]).

KG kann als strukturierte grafische Darstellung von Informationen in Form von Entitäten und semantischen Beziehungen (auch einfach Beziehungen genannt) zwischen ihnen definiert werden.

Hier werden die Entitäten durch die Knoten des Diagramms dargestellt, während Kanten mit Richtung die Beziehungen zwischen den Entitäten darstellen. Zu diesen Beziehungen gehören

• Relationen (relations), z.B. Hauptstadt von, oder
• Attribut einer Entität (attribute of an entity), z.B. Körpergröße einer Person.

Die Entitäten können konkrete Objekte (wie z. B. Wien) oder Klassen darstellen, die semantische Entitätstypen (semantic type of entities), wie z. B. Stadt, darstellen. Was der Entität durch ein Attribut zugewiesen wird, ist ein Literal, das einen Wert darstellt, wie z.B. Höhe beträgt 180 cm. Somit kann die erweiterte Menge der Elemente eines KG wie folgt angegeben werden.

• Knoten

  • Head Knote: Entität, die ein konkretes Objekt darstellt

  • Tail Knote: Entität, die ein

    • konkretes Objekt oder

    • Literal oder

    • Klasse

    darstellt,

• gerichtete Kanten mit Beschriftung – Beziehungen, wie

  • Relationen: Entität - Relation - Entität

  • Attribut einer Entität: Entität - Attribut - Entität

  • Typ der Entitätsbeziehung (= spezielle Art der Beziehung): Entität - „type of“ (Art der Entität) - class

Ein Beispiel für einen KG Fragment ist in Abbildung 9 dargestellt

Abbildung 9: Ein KG Fragment - Konzepte sind orange schattiert (Quelle: [Kejriwal(2022)]).

Im Kontext der Ontologie werden für die einzelnen Entitätstypen andere Namen verwendet als

• Klasse ${\textstyle \rightarrow }$ Konzept
• Entität, die eine konkrete Objekt darstellt ${\textstyle \rightarrow }$ Instanz

Semantic Web wendet alternative Namen für die Knoten und Kanten an, indem es die Begriffe „Ressourcen-Wert-Paare“ (,,resource - value pairs“) und „Eigenschaften“ (,,properties“) verwendet. Die alternative Namen mittels dieser Begriffen lauten wie folgt.

• Klasse – Entität (konkretes Objekt) ${\textstyle \rightarrow }$ Ressource – Wert
• Entität (konkretes Objekt) – Literal ${\textstyle \rightarrow }$ Ressource – Wert
• Relation ${\textstyle \rightarrow }$ Objekteigenschaft
• Attribut ${\textstyle \rightarrow }$ Datentypeigenschaft

Die Abbildung 9 veranschaulicht auch das Konzept von A-Box und T-Box. Die Knoten, die konkrete Objekte oder Literale darstellen, gehören zur A-Box (eigentliches KG-Fragment), während die Knoten, die Konzepte darstellen (orange schattiert), Teile der T-Box sind (Informationen aus der Ontologie).

Die mathematische Definition von KG kann wie folgt angegeben werden. KG ${\textstyle {\mathcal {G}}}$ ist ein markierter gerichtete Graph einer Menge von Tripletts ${\textstyle {\mathcal {T}}}$, gegeben durch ${\textstyle {\mathcal {T}}\in {\mathcal {E}}\times {\mathcal {R}}\times ({\mathcal {E}}\cup {\mathcal {L}}\cup {\mathcal {C}})}$, wobei

• ${\textstyle {\mathcal {E}}}$ ist eine Menge von Entitäten, die konkrete Objekte darstellen,
• ${\textstyle {\mathcal {R}}}$ ist eine Menge von Beziehungen,
• ${\textstyle {\mathcal {L}}}$ ist eine Menge von Literalen (Text, Datum, Zahl, Bilder usw.) und
• ${\textstyle {\mathcal {C}}}$ ist eine Menge von Klassen.

Von nun an werden wir Beziehungen auch einfach als Relation bezeichnen.

KG in der Praxis

${\textstyle \mathrm {\ \ \ \ } }$ KG-Erstellung – vereinfachte Funktionsansicht

In einer vereinfachten Funktionsansicht kann der KG-Erstellungsprozess (KG creation process) durch die folgenden Schritte beschrieben werden:

1. Wissensextraktion (knowledge extraction)
2. Graphkonstruktion (graph construction)

Im Schritt der Wissensextraktion werden die Entitäten im Text identifiziert und die Beziehungen zwischen ihnen extrahiert. Dies erfolgt in der Regel durch die Anwendung von NLP-Aufgaben wie Annotation und Semantic Role Labelling sowie verschiedenen IE-Techniken unter Verwendung von Grammatiken und gelernten Modellen. Das Ergebnis ist das Extraktionsgraph (extraction graph). Das Extraktionsgraph kann nicht als vollständliche KG betrachtet werden, da der hinsichtlich Mehrdeutigkeit, Unvollständigkeit und Inkonsistenz er noch viele Verbesserungsschritte erfordert.

Der zweite Schritt, die Graphkonstruktion, hat die Ziele, die oben genannten Probleme des Extraktionsgraphen zu überwinden. Dazu gehören Aufgaben wie

• Knoten mit derselben Entität zu identifizieren,
• Knoten hinzufügen, die Konzepte darzustellen,
• neue Kanten zu entdecken und
• falsche Tripletts zu entdecken.

Beispiele

${\textstyle \mathrm {\ \ \ \ } }$ KG Beispiele

KGs können kategorisiert werden als

• Offene KGs (open KGs) und
• Unternehmen KGs (enterprise KGs).

Zunächst werden einige Beispiele für offene KGs angegeben.

• YAGO2 (YAGO2)
• Freebase (Freebase)
• Wikidata (Wikidata)
• DBpedia (DBpedia)

DBpedia wurde 2007 mit dem Ziel ins Leben gerufen, die Inhalte von Wikipedia maschinenlesbarer und damit zugänglicher zu machen. DBpedia wurde aus strukturierten Informationen in Wikipedia abgeleitet und verwendet das standardisierte Format der DBpedia-Ontologie. DBpedia ist eine große Open-Source-KG, die als Ressource für viele Anwendungen dient, darunter Empfehlungssysteme, NLP Tools und Suchmaschinen.

Unternehmens KGs werden mit kommerziellen Zielen entwickelt. Im Folgenden werden einige Beispiele für Unternehmens-KGs angegeben.

• Google Knowledge Graph (Google KG) (Google KG)
• Microsoft Satori
• eBay
• Amazon
• Uber

Die Google KG wurde 2012 mit dem Ziel gegründet, umfassendere (auch relevantere, informativere und kontextbezogenere) Suchergebnisse durch die Nutzung der Beziehungen zwischen verschiedenen Einheiten bereitzustellen. Die Google KG wird in verschiedenen Google-Diensten eingesetzt, wie z.B. Google-Suche oder Google Assistant. Während der Verarbeitung der Suche zeigt Google KG in Google ein Knowledge Panel an, das einen schnellen Zugriff auf wichtige Entitäten, Beziehungen usw. ermöglicht.

Microsoft Satori wurde 2012 eingeführt und hat das gleiche Ziel wie die Google KG: umfassendere Suchergebnisse bereitzustellen. Es wird in verschiedenen Microsoft-Diensten eingesetzt, wie z.B. Bing-Suchmaschine oder virtueller Assistent Cortana.

Größe von einigen KG

		Anzahl von
Wissensgraph	Entitäten	Relationstypen	Fakten
YAGO2 ([1])	9.8 M	114	447 M
Freebase ([2])	40 M	35000	637 M
Wikidata	18 M	1632	66 M
DBpedia	4,58 M	1367	583 M
Google KG	570 M	35000	18000 M

${\textstyle \mathrm {\ \ \ \ } }$ Beispiele für Ontologie und Ontologiesprachen

Hier sind Zwei Beispielontologien gegeben.

• Im Bereich Kulturerbe: Konzeptionelles Referenzmodell (Conceptual Reference Model - CRM)
  

https://cidoc-crm.org

• Biomedizinischer Bereich: Genontologie (Gene Ontology)
  

https://geneontology.org

Ein Beispiel für eine leistungsstarke Ontologiesprache ist Web Ontology Language (OWL) https://www.w3.org/OWL/. Es ermöglicht die Formulierung ontologischer Aussagen mit komplexen Randbedingungen.

Erstellung von Wissensgraphen

Das Erstellen einer KG ist ein mehrstufiger Prozess. Obwohl die Schritte des KG-Erstellungsprozesses klar identifiziert werden können, können sie in einer alternativeren Reihenfolge ausgeführt werden. Es gibt keine einheitliche Sicht auf den gesamten Erstellungsprozess.

KG-Entwicklungsprozess – vollständige Funktionsansicht

Der Erstellungsprozess einer KG aus Daten kann durch einen
KG-Entwicklungsprozess (KG development process) charakterisiert werden, der eine vollständige funktionale Sicht bietet. Die Schritte des KG-Entwicklungsprozesses sind wie folgt angegeben.

1. Ontologie und Graphdatenbankdesign
2. Datenerfassung (data acquisition)
3. Knowledge Graph Konstruktion (KGC)
4. KG Refinement (KG-Verfeinerung)
5. Auswählen einer Speicherarchitektur und Speichern des KG

Das Ziel des Ontologie- und Graphdatenbankdesigns besteht darin, eine Domänenmodellierung bereitzustellen und eine Datenstruktur zu entwickeln um die Entitäten und ihrer Beziehungen darzustellen. In diesem Zusammenhang werden sowohl das Domänenmodell als auch die Datenstruktur als Ontologie bezeichnet. Ontologiedesign lässt sich am besten im Bereich des Semantic Web untersuchen. Das Entwerfen einer Ontologie von Grund auf ist ein komplexer Prozess. Daher wird vorgeschlagen, lieber eine vorhandene Standardontologie wiederzuverwenden oder einem neuen Zweck zuzuweisen, was im Wesentlichen ein einfacherer Prozess ist. Basierend auf der Ontologie wird eine Datenbank für den Umgang mit Graphdaten konzipiert.

Bei der Datenerfassung handelt es sich um Erwerben und Erfassung der Datenquelle, aus der die KG erstellt wird. Die Daten können direkt zugänglich sein, wie z.B. Daten aus dem Web oder über eine bereitgestellte Anwendungsprogrammierschnittstelle (Application Programming Interface - API), wie z.B. die Twitter Application Programming Interface.

Knowledge Graph-Konstruktion (Knowledge Graph Construction - KGC), auch Wissensextraktion (knowledge extraction) oder Wissenserwerb (knowledge acquisition) genannt, ist der Schritt, in dem ein KG aus den Daten erstellt wird. Dazu gehören Aufgaben wie

• nach Entitäten im Text zu suchen,
• Beziehungen zwischen Entitäten zu extrahieren,
• Entitäten mit Entitäten im kanonischen KG, wie Wikipedia zu verknüpfen und
• grammatikalische Satzeinheiten (grammatical sentence units), wie Relativpronomen, mit der rechten Entität zu verknüpfen.

Die Ausgabe von KGC ist das anfängliche KG (initial KG), auch Extraktionsgraph genannt. Es ist nicht vollständig, in der Regel fehlen darin viele Fakten und er kann auch falsche Fakten enthalten.

Die Knowledge Graph Refinement (KG Refinement), auch bekannt als Graphkonstruktion (graph construction) oder Knowledge Graph Identification (KGI), zielt auf die Vervollständigung von KG ab, indem fehlendes Wissen hinzugefügt wird, sowie hat die Aufgabe falsche Fakten in KG (d.h. Fehlern) zu identifizieren. Damit deckt Knowledge Graph Refinement die folgende Aufgaben ab.

• Zusammenknüpfen der verschiedenen Varianten einer Entität,
• Erstellung der Konzeptknoten,
• Vorhersage neuer Tripletts und
• Beurteilung die Richtigkeit der vorhandenen Triplett.

Das Ergebnis der KG Refinement ist das KG selbst.

Der letzte Schritt des KG-Entwicklungsprozesses ist die Auswahl einer Speicherarchitektur und Speichern. Dazu gehören die folgenden Aufgaben.

• Auswahl einer Abfrage- und Speicherarchitektur (querying and storage architecture), wie z.B. Graphdatenbank, Triplestore (triplestore) mit RDF-Graphen.
• Festlegen des Standorts der Speicherinfrastruktur:
  • Entweder wird die Infrastruktur auf dem lokalen Server eingerichtet,
  • oder einen Cloud-Dienst, wie z.B. Amazon Neptun wird benutzt.
• Speichern des KG im ausgewählten Speicher.

Nach diesem Schritt ist das KG erreichbar, d.h. Abfrage/Behandlung (querying/handling) von KG möglich.

Ansätze für KG-Konstruktion

KG construction lassen sich in folgende Fällen einteilen:

• Kuratierter Ansatz (curated approach). Bei diesem Ansatz werden Tripletts von Experten manuell erstellt.
  

${\textstyle \Rightarrow }$ Dies führt zu KG mit hoher Genauigkeit, kann jedoch aufgrund der begrenzten Anzahl verfügbarer Experten nur für kleinere Korpora angewendet werden.

• Kollaborativer Ansatz (collaborative approach). Wenn Tripletts von Freiwilligen manuell erstellt werden, spricht man von einem kollaborativen Ansatz.
  

${\textstyle \Rightarrow }$ In diesem Fall kann jeder beitreten, um am Erstellungsprozess teilzunehmen, und daher ist dieser Ansatz auch für größere KB geeignet. Allerdings ist die Genauigkeit der resultierenden KG begrenzt, da Freiwillige keine Experten sind.

• Automatisierter halbstrukturierte Ansatz (automated semi-structured approach). Die Extraktion von Tripletts erfolgt automatisch mittels händisch erstellter Regeln oder Grammatikregeln (grammar rules) aus halbstrukturiertem Text, wie z.B. Wikipedia.
  

${\textstyle \Rightarrow }$ Dieser Ansatz ermöglicht etwas größere KB mit hoher Genauigkeit zu erzeugen. Der Ansatz weist jedoch eine geringe Auslastung der Textquellen auf, da nur ein kleiner Teil des Textes im Web in halbstrukturierter Form verfügbar ist.

• Automatisierter unstrukturierte Ansatz (automated unstructured approach). Dabei handelt es sich um den Ansatz, bei dem Tripletts mithilfe von NLP- und ML-Techniken vollautomatisch extrahiert werden. Daher funktioniert es bei unstrukturiertem Text.
  

${\textstyle \Rightarrow }$ Der Ansatz kann einen großen Teil des verfügbaren Textes nutzen, da das Text nicht strukturiert werden muss. Daher ist dieser Ansatz geeignet, um sehr große KBs zu erstellen. Allerdings sind die erstellten KGs aufgrund der angewandten ML- und NLP-Techniken fehlerhaft, d. h. sie sind „geräuschvoll“. Infolgedessen ist ein Nachbearbeitungsschritt erforderlich, um dieses Rauschen zu reduzieren, z. B. mithilfe von Erkenntnissen aus vorhandenen hochwertigen externen Datenquellen.

Tabelle 2 gibt einen Überblick über Ansätze für KG-Konstruktion und für ausgewählte Beispiel-KGs.

Ansätze für KG-Konstruktion [Nickel et al.(2016)]

Ansatz	Wird Schema	Beispiele
	verwendet ?
kuratierter	ja	WordNet [3], UMLS [4]
kollaborativer	ja	Freebase [5], Wikidata [6]
automatisierter	ja	YAGO [1], DBPedia [7]
halbstrukturierte
automatisierter	ja	NELL [8], Knowledge Vault [2]
unstrukturierte
automatisierter	nein	PRISMATIC [9]
unstrukturierte

KG-Konstruktion

Während der KG Construktion wird aus der Datenquelle eine grafisch strukturierte Darstellung der Daten erstellt.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Vorbereitende Aufgaben

Bevor Wissen erworben werden kann, ist eine gewisse Vorverarbeitung notwendig. Bei der Nutzung des Internets als Datenquelle sind einige Teile der Daten, wie z. B. Layoutinformationen oder Werbung, für die KG construction nicht relevant. Solche Geräusche müssen herausgefiltert werden. Zunächst werden die standardmäßig vorbereitenden Aufgaben gelistet.

• NLP-Teilaufgaben:
  • Annotation zur Identifizierung der syntaktischen Rolle von Wörtern und Wortzusammensetzungen und
  • Semantic Role Labelling zur Identifizierung der semantischen Rolle von Wörtern und Phrasen auf Satzebene, wie z.B. Ort oder Patient.
• IE-Teilaufgabe zum Extrahieren von Strukturen durch die Nutzung z.B. Grammatik.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Aufgaben der KG-Konstruktion

Die KG-Konstruktion wird durch die folgenden Schritten durchgeführt.

• Entity Discovery
  • Named Entity Recognition (NER)
  • Entity Typing
  • Entity Linking (Entitätsverknüpfung)
• Relation Extraction (Relationsextraktion)
• Co-reference Resolution (Co-Referenzauflösung)

Einige Autoren nennen die Gruppe der Aufgaben NER, Entity Typing und Entity Linking zusammen Entity Discovery. Neben den unten diskutierten Ansätzen gibt es auch auf Large Language Models basierende Ansätze [Pan et al.(2024)] für jeden der Schritte der KG construction.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Named Entity Recognition

NER (in English auch entity recognition genannt) identifiziert Entitäten im Text und klassifiziert sie entsprechend ihrer semantischen Rolle, z. B. Ort, Person, durch Anwendung von IE-Techniken. Beispielsweise wird im Satz „Sigmund Freud lebte in Wien“ die Wortzusammensetzung „Sigmund Freud“ als Person und „Wien“ als Ort identifiziert. NER weist den identifizierten Entitäten Tags anhand ihrer Position und Klassifizierung zu. NER wird auf unstrukturierten und halbstrukturierten Text angewendet. Halbstrukturierter Text kann einige Hinweise zur Semantik enthalten. z.B. über das Format der Beschreibung, das zum Beispiel XML sein kann.

Die für NER verwendeten Ansätze einschließen

• Wörterbuch und regelbasierte Methoden,
• statistische und ML-Methoden,
• Deep Learning.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Entity Typing

Die Aufgabe der Entity Typing besteht darin, die Entitäten in Konzepte (Typen) zu gruppieren. Im obigen Beispiel würde „Sigmund Freud“ als Arzt kategorisiert, während „Wien“ als Stadt kategorisiert würde, wobei beide spezifischer als Person bzw. Ort wären. Normalerweise enthalten halbstrukturierte Daten Informationen über diesen Typ.

Entity Typing verwendet Ansätze wie

• ML-Methoden und
• neue Methoden unter anderem Deep Learning oder Einbettungsbasierte Ansätze (embedding based approaches) [Zhong et al.(2023)].

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Entity linking

Die Entity Linking, auch Named-Entity Linking (NEL), Named-Entity Disambiguation (NED), Named-Entity Recognition and Disambiguation (NERD) oder Named-Entity Normalization (NEN) genannt, identifiziert die Entität des in der Datenquelle gefundenen Substantivs (auch Link Entity Mention oder einfach Mention genannt) als eine Entität der KG. Somit ordnet die Entity Linking die in der Datenquelle gefundene Mention einem vorhandenen Knoten in der KG oder einem neuen Knoten zu, der in der KG für diese Entität erstellt werden soll. Das Ziel der Entity Linking besteht darin, die Entität der gefundenen Mention eindeutig zu machen. Beispielsweise wird bei der gefundenen Mention „Paris“ festgestellt, dass es sich bei der KG um die Entität Paris als Stadt und nicht um die Entität Paris Hilton als Person handelt. Die Entity Linking einer Entität in KG kann identifiziert werden, indem die Entität mit ihrem Äquivalent in einer kanonischen KB verknüpft wird, wie z. B. Wikipedia.

Ein System für Entity Linking kann durch Verwendung von

• typischem Ansatz oder
• neuen Methoden unter Verwendung von Entitätseinbettungen (entity embeddings) [Zhong et al.(2023)]

realisiert werden.

Ein typischer Ansatz für ein System für Entity Linking besteht aus drei Funktionseinheiten:

• Kandidaten-Entitätsgenerierung (Candidate Entity Generation)
• Kandidaten-Entitätsranking (Candidate Entity Ranking)
• Vorhersage von nicht verlinkbare Mention (Unlinkable Mention Prediction)

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Relation Extraction

Die Relation Extraction hat die Aufgabe, Kanten mit semantischen Relationen aus Daten zu extrahieren und diese in die KB einzufügen, indem sie mit den entsprechenden Entitäten verbunden werden. Die semantische Relation von Kanten basiert auf zuvor identifizierten semantischen Rollen des Wortes oder der Phrase, aus denen die Kante besteht. Auf diese Weise transformiert die Relation Extraction die Fakten in den Daten in ein Triplett im KG. Beispielsweise wird im Satz „Sigmund Freud lebte in Wien.“ die verbale Konstruktion „lebte in“ als Kante mit semantischer Relation extrahiert und in das KG eingefügt, um die Entitäten „Sigmund Freud“ und „ Wien“ zu verbinden.

Strategien zur Relation Extraction können in die folgenden Gruppen eingeteilt werden

• Extraktion offener Relation (open relation extraction)
• Domänenspezifische Klassifizierung (domain-specific classification)
• Fernüberwachungsstrategien (distant supervision strategies)
• Relation extraction auf Dokumentebene (document-level relation extraction)
• Neuartige Modelle für relation extraction (novel relation extraction models) wie gemeinsame Relationsextraktionsmodelle (joint relation extraction models), Graph Convolutional Network (GCN)-Modelle oder einbettungsbasierte Modelle [Zhong et al.(2023)]

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Co-reference Resolution

Co-reference Resolution (in English auch Entity coreference genannt), findet alle Wörter und Phrasen, die sich auf dieselbe Entität beziehen. Solche Wörter sind z.B. die Relativpronomen: er oder sie. Beispielsweise kann der vorherige Beispielsatz erweitert werden, da „Sigmund Freud in Wien lebte. Er war der Begründer der Psychoanalyse.“ Bei der Co-Referenzauflösung wird das Pronomen „Er“ mit der Entität „Sigmund Freud“ verbunden. Der sequentielle Ablauf der Co-Referenzauflösung besteht aus drei Teilen:

1. die Mention zu erkennen,
2. das referenzierte Wort zu finden und
3. die beide zu verbinden.

Die wichtigsten Arten von Ansätzen zur Co-Referenzauflösung beinhalten:

• linguistische Ansätze,
• statistische und ML-Ansätze und
• neuartige Ansätze, einschließlich Deep-Learning-basierter Modelle.

KG Refinement

Die KG Refinement verfeinert, wie der Name schon sagt, die KG weiter, indem sie Duplikate auflöst (resolving duplications), Typen von Entitäten identifiziert, neue Fakten entdeckt und einfügt und den Wahrheitsgehalt der Tripletts überprüft.

${\textstyle \mathrm {\ \ \ \ } }$ Aufgaben der KG Refinement

Die Aufgaben der KG refinement können wie folgt aufgeführt werden.

• Entity Resolution (Entitätsauflösung),
• Collective Classification (kollektive Klassifizierung)
• Link Prediction
• Triplet Classification and
• Link Based Clustering.

Einige Autoren bezeichnen die oben genannten Aufgaben als KG Completion (Vervollständigung von WG) und schließen auch die Aufgabe der KG Fusion in den Bereich der KG Refinement ein. KG Fusion erweitern den Wissensgehalt der KG durch die Zusammenlegung mit anderen KGs. In einem anderen Zusammenhang wird die KG Completion als alternativer Name für die Link Prediction verwendet.

${\textstyle \mathrm {\ \ \ \ } }$ Entity Resolution

Entity Resolution (in English auch record linkage, data matching, data linkage, object identification, instance matching and deduplication - Duplikaterkennung genannt), hat die Aufgabe, die verschiedenen, aber semantisch identischen Varianten einer Entität zu finden, zu identifizieren und sie mit derselben Entität zu verknüpfen um unnötige Doppelarbeit zu vermeiden. Diese unterschiedlichen Varianten entstehen möglicherweise in unterschiedlichen Datenquellen, wie z.B. Datendateien, Websites und Datenbanken. Zum Beispiel die Mention „Alexander Van der Bellen“, und die Mention „A. Van der Bellen“ werden dedupliziert, da es sich um dieselbe Entität handelt.

Normalerweise wird zur Entity Resolution ein relationaler Ansatz verwendet. Der Sinn dabei ist, dass, wenn KG-Teile mit den verschiedenen Varianten strukturell ähnlich aussehen, angenommen wird, dass diese Varianten semantisch identisch sind. Ein Beispiel befindet sich dafür in Abbildung 10.

Abbildung 10: Beispiel einer Entity Resolution für die Knoten ,,A. Guiness“ und „Alec Guiness“ (Quelle: [Nickel et al.(2016)]).

${\textstyle \mathrm {\ \ \ \ } }$ Collective Classification

Collective Classification hat die Aufgabe die (gleichzeitige) Vorhersage des Typs mehrerer Knoten, d. h. der Konzepte von Entitäten, basierend auf der Ähnlichkeit von Merkmalen (Typ, Nachbarschaftsrelationen) und Relationen der Knoten. Wenn beispielsweise ein anderer Knoten ${\textstyle v_{i}}$ mit Nachbarn existiert, die ähnliche Typen oder Relationen wie die Nachbarn des betrachteten Knotens haben, dann wird der Typ dieses anderen Knotens ${\textstyle v_{i}}$ als Vorhersage für den Typ des betrachteten Knotens verwendet.

${\textstyle \mathrm {\ \ \ \ } }$ Link Prediction

Link Prediction hat die Aufgabe, neue Fakten in die KG einzufügen. Dies geschieht durch die Vorhersage eines fehlenden Teils eines Tripletts. Es kann wie folgt weiter unterteilt werden als

• Entity Prediction:
  • Head and Tail prediction,
  • Entity Type Prediction,
• und Relation prediction.

Bei einer Head Prediction werden der Tail und die Relation angegeben und der Kopf vorhergesagt. In ähnlicher Weise werden bei der Tail Prediction der Kopf und die Relation angegeben und der Tail vorhergesagt. Die Entity Type Prediction ist eine spezielle Tail Prediction, bei der die Relation ein „type of“ ist.

Entity Type Prediction wird in ein Klassifizierungsproblem umgewandelt. Beobachte die Ähnlichkeit der Entity Type Prediction mit der Aufgabe der Entity Typing in der KG construction.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Ansätze für Link Prediction

Für die Link Prediction werden viele Ansätze angewendet. Nachfolgend befindet sich eine Liste solcher Ansätze.

• Traditionelle statistische relationale Lernens (statistical relational learning), einschließlich
  • Regelbasiertes Denken (rule-based reasoning), wie
    • Logische Programmierung, Prädikatenlogik, erster Ordnung (first-order logic programming),
    • Induktive logische Programmierung (inductive logic programming - ILP),
  • oder grafische Modelle (graphical models) wie
    • Conditional Random Fields (CRFs)
    • probabilistische relationale Modelle (probabilistic relational models),
    • Relational Markov Networks und
    • Relational Dependency Networks.
• Graph Representation Learning, einschließlich
  • Graph Feature Based Methods,
  • Graph Neural Networks (GNNs) und
  • Einbettungen von Wissensgraphen (knowledge graph embeddings).

Ein Beispiel für eine Link Prediction mit regelbasiertem Denken ist in Abbildung 11 zu sehen.

Abbildung 11: Link Prediction mithilfe von Regeln (Quelle: [Pflueger et al.(2022)]).

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Paradigmen für nicht existierende Tripletts

Vorhandene Tripletts in KG repräsentieren immer bekannte Fakten (d. h. wahre Aussagen). Allerdings kann die Link Prediction auch eine Annahme über die Bedeutung der nicht vorhandenen Tripletts erfordern, da sie einen erheblichen Einfluss auf die Ausgabe der Link Prediction haben kann. Dabei kommen unterschiedliche Paradigmen zum Einsatz.

• Closed World Assumption (CWA). Ein nicht existierendes Triplett bedeutet eine falsche Relation.
• Open World Assumption (OWA). Ein nicht existierendes Triplett bedeutet eine unbekannte Relation, d. h. die entsprechende Aussage kann entweder wahr oder falsch sein.
• Local-closed World Assumption (LCWA). Wenn für ein bestimmtes Subjekt-Prädikat paar ${\textstyle e_{i},r_{k}}$ ein Triplett beobachtet wird, dann bedeuten alle nicht existierenden Tripletts ${\textstyle (e_{i},r_{k},.)}$ eine falsche Relation. Für Subjekt-Prädikat paare ohne beobachtetes Triplett gilt, dass ihr Triplett mit beliebigen Objekten eine unbekannte Relation bedeutet, d. h. die entsprechende Aussage kann entweder wahr oder falsch sein.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Relation Prediction

Relation Prediction kann durch Triplet Classification vervollständigt werden. Ein Beispiel für die Identifizierung einer Relation und damit eines neuen Tripletts mithilfe der Triplet Classification ist in Abbildung 12 dargestellt.

Abbildung 12: Identifizieren einer neuen Relation durch Anwendung der Triplet Classification (Quelle: [Biswas(2003)]).

${\textstyle \mathrm {\ \ \ \ } }$ Triplet Classification

Ziel der Triplet Classification ist es, die Korrektheit der Kanten im KG vorherzusagen. Die Korrektheit einer Kante kann z.B. gemessen werden mit Hilfe der Wahrscheinlichkeit seiner Existenz. Die Triplet Classification wird durch einen trainierten binären Klassifikator implementiert.

Relation Prediction kann auch als Teil der Triplet Classification verstanden werden. In diesem Fall können sie beide dann als Teil der Link Prediction angesehen werden.

${\textstyle \mathrm {\ \ \ \ } }$ Link Based Clustering

Link Based Clustering (in English auch link-based object classification) hat die Aufgabe, ähnliche Entitäten zu gruppieren. Im Kontext der Social Media Analysis wird diese Teilaufgabe als Community-Erkennung (community detection) bezeichnet.

Link Based Clustering nutzt die Ähnlichkeit von Merkmalen (wie z. B. Typen) und Relationen von Entitäten.

Qualität der KG

Die beiden wichtigsten Qualitätsmaßstäbe einer KG sind

• Vollständigkeit und
• Genauigkeit.

Die Vollständigkeit bezieht sich auf die Bewertung der Anzahl vorhandener Tripletts im KG, während die Genauigkeit darauf abzielt, die Anzahl richtiger und falscher Tripletts im KG zu messen. Nach KG Completion wird der resultierende Extraktionsgraph als noch nicht fertiges KG betrachtet. Daher ist die Qualitätsmessung von KG erst nach der KG Refinement relevant.

${\textstyle \mathrm {\ \ \ \ } }$ Bewertungsmethoden

Die üblichen Methoden zur Bewertung des fertigen KG nach der KG Refinement können wie folgt angegeben werden.

• Silberstandard (silver standard)
• Teilweiser Goldstandard (partial gold standard)
• Ex-post-Bewertung (ex post evaluation)

Bei der Silberstandardmethode wird ein Referenz-KG durch einen anderen KG-Verfeinerungsansatz erstellt. Anschließend wird das zu bewertende KG mit diesem Referenz-KG verglichen. Dieser Ansatz kann als halbüberwacht bezeichnet werden, da die als „Labels“ dienenden Referenz-KGs automatisch erstellt werden. Der Silberstandard-Ansatz eignet sich nicht zur Beurteilung der Genauigkeit, da er davon ausgeht, dass das KG korrekt ist.

Bei der partiellen Goldstandard-Methodik wird ein Teil eines KG manuell ausgewählt und markiert. Dieser Teil dient als Referenz. Der Vergleich kann durch Stichproben aus dem markierten Teil des KG durchgeführt werden. Die Methode des partiellen Goldstandards ist für die Bewertung sowohl der Vollständigkeit als auch der Genauigkeit geeignet. Die Verwendung eines vom Menschen markierten Goldstandards kann zu qualitativ hochwertigen Daten führen, ist jedoch kostspielig.

Im Falle einer Ex-post-Bewertung wird das fertige KG einem menschlichen Tester übergeben, um die zu bewertenden Tripletts nach der KG Refinements zu beurteilen und zu kommentieren. Eine solche Auswertung ist sinnvoll, wenn die betrachtete Klasse der Tripletts selten ist.

Während die partielle Goldstandard-Methodik für den Vergleich verschiedener Methoden für KG Refinement geeignet ist, wäre dies bei einer Ex-post-Bewertung sehr kostspielig.