Neue Methode zur Klassifizierung von Graphen verbessert Anwendungen wie die Arzneimittelforschung

Graph Neural Networks (GNNs) sind leistungsstarke Modelle zur Klassifizierung von Graphen und zum Erlernen von Graphdarstellungen. Wie die meisten Deep-Learning-Modelle haben jedoch auch GNNs mit Überanpassung zu kämpfen, insbesondere wenn die Datensätze begrenzt sind. Um die Robustheit von GNNs zu verbessern, wurden Datenvergrößerungsmethoden eingesetzt, um aus bestehenden Graphen synthetische Daten zu erstellen. Aktuelle Methoden zur Graphvergrößerung, wie z. B. das zufällige Entfernen von Knoten, neigen jedoch dazu, die wesentliche Struktur von Graphen zu stören, was zu einer potenziellen Leistungsminderung führen kann.

Diese Herausforderung wurde in einer aktuellen Veröffentlichung des Zentrums für Künstliche Intelligenz der ZHAW und der Ca' Foscari Universität Venedig mit dem Titel „Topology-Aware Node Dropping Augmentation for Graph Classification” behandelt. Die Veröffentlichung stellt eine neuartige Augmentationsmethode namens NDAUG (Node-Dropping Augmentation) vor, die den Grad der Knoten nutzt, um weniger wichtige Knoten mit niedrigem Grad selektiv zu entfernen und gleichzeitig wesentliche Graphstrukturen zu erhalten, wodurch sichergestellt wird, dass GNNs ihre Leistung beibehalten.

Diese Herausforderung wurde in einer aktuellen Veröffentlichung des Zentrums für Künstliche Intelligenz der ZHAW und der Ca' Foscari Universität Venedig mit dem Titel „Topology-Aware Node Dropping Augmentation for Graph Classification” behandelt. Die Veröffentlichung stellt eine neuartige Augmentationsmethode namens NDAUG (Node-Dropping Augmentation) vor, die den Grad der Knoten nutzt, um weniger wichtige Knoten mit niedrigem Grad selektiv zu entfernen und gleichzeitig wesentliche Graphstrukturen zu erhalten, wodurch sichergestellt wird, dass GNNs ihre Leistung beibehalten.
NDAUG ist ein dreistufiger Prozess:

1. Motivbewahrung: Identifiziert wichtige Teilstrukturen (Motive) im ursprünglichen Graphen, wie z. B. chemische Funktionsgruppen in Molekülgraphen, und stellt sicher, dass diese während der Augmentierung erhalten bleiben.
2. Knoten-gradbasiertes Löschen: Löscht Knoten mit niedrigem Grad, die für die Topologie des Graphen weniger wichtig sind, während Knoten mit hohem Grad, die wichtige Strukturelemente darstellen, beibehalten werden.
3. Strukturlernen: Verbindet alle isolierten Knoten, die durch den Knoten-Entfernungsprozess entstanden sind, mithilfe eines aufmerksamkeitsbasierten Mechanismus wieder, um die Konnektivität des Graphen aufrechtzuerhalten.

Experimente mit acht Benchmarks zur Graphklassifizierung, darunter Datensätze für die Molekülklassifizierung und die Analyse sozialer Netzwerke, zeigen, dass NDAUG herkömmliche Augmentationsmethoden wie NodeDrop, DropEdge und GraphCrop übertrifft und die Leistung um durchschnittlich 2 bis 5 % verbessert. So verbesserte NDAUG beispielsweise die Klassifizierungsgenauigkeit beim NCI1-Datensatz um 4,5 % und beim BZR-Datensatz um 6,7 % im Vergleich zu den modernsten Methoden.

Die wichtigste Innovation von NDAUG ist seine Fähigkeit, die wesentliche Topologie von Graphen beizubehalten, insbesondere in komplexen Netzwerken wie sozialen Interaktionen oder molekularen Verbindungen, in denen die Konnektivität der Knoten entscheidend ist. Die Robustheit der Methode zeigt sich besonders deutlich in Bereichen wie der Arzneimittelforschung, wo die Beibehaltung der Struktur molekularer Graphen einen direkten Einfluss auf die Genauigkeit von Vorhersagen haben kann.

Diese Arbeit stellt einen wichtigen Fortschritt in der Graphen-Datenvergrößerung dar und bietet eine effizientere Möglichkeit, GNNs zu verbessern, ohne die Integrität der Graphenstrukturen zu beeinträchtigen. Die Methode ebnet auch den Weg für zukünftige Forschungen zur Vergrößerung von Graphendaten unter Beibehaltung wichtiger struktureller Merkmale, wodurch die Gesamtleistung graphenbasierter KI-Systeme gesteigert wird.

Bildunterschrift zum beigefügten Diagramm/zur beigefügten Abbildung:
Abb. 1: Der Ablauf der vorgeschlagenen NDAUG-Methode. Im ersten Schritt werden die wichtigen strukturellen Motive des Eingabegraphen identifiziert. In Schritt 2 werden die Knoten mit niedrigem Grad entfernt, während die durch Knoten mit hohem Grad gebildeten topologischen Schlüsselstrukturen beibehalten werden. Im letzten Schritt wird der endgültige augmentierte Graph generiert, um die in Schritt 1 identifizierten signifikanten Motivstrukturen zu erhalten, und es wird eine Strukturlernmethode angewendet, um die Konnektivität des augmentierten Graphen beizubehalten, indem alle isolierten Knoten, die durch den Knotenentfernungsprozess entstanden sind, wieder verbunden werden.

Vollständige Publikation: https://digitalcollection.zhaw.ch/items/1df9eaf9-4a5a-4170-90e2-601b2d8bb893

Forscher: Prof. Marcello Pelillo, Prof. Sebastiano Vascon und Dr. Waqar Ali