Graphpartitionierung für Graph Neural Networks

• Antragsteller: Professor Dr. Ruben Mayer
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme ; Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 438107855

Die Partitionierung von Graphen ist ein wichtiger Vorverarbeitungsschritt für die verteilte Graphverarbeitung. Der Eingabegraph wird in eine Menge gleich großer Komponenten zerlegt, wobei die Schnittgröße minimiert wird. Dieses Problem wurde in den vergangenen Jahren eingehend untersucht und ist heute im Hinblick auf klassische Graphverarbeitungsalgorithmen wie PageRank, Label Propagation, Shortest Paths usw. gut verstanden. In jüngerer Zeit wurde die verteilte Graphverarbeitung jedoch überarbeitet und erweitert, um tiefe neuronale Netze zu trainieren, was als Graph Neural Networks (GNN)-Verarbeitung bezeichnet wird. Während die GNN-Verarbeitung viele Ähnlichkeiten mit der traditionellen Graphverarbeitung aufweist, wie z. B. asynchrone Nachrichtenübermittlung und synchrone Aggregationsschritte, gibt es auch einige bedeutende Unterschiede. In erster Linie betrifft dies größere Vertex-Zustände, DNN-Operationen und Mini-Batch-Training in Kombination mit Neighbor-Sampling. Angesichts dieser Unterschiede werden wir in diesem Projekt Algorithmen zur Graphenpartitionierung überprüfen und anpassen oder erweitern, um sie besser für die GNN-Verarbeitung geeignet zu machen. Aktuelle GNN-Systeme schöpfen die Möglichkeiten der Graphpartitionierung nicht voll aus und führen lediglich leichte Anpassungen bestehender Graphpartitionierungsalgorithmen an die GNN-Verarbeitung durch. Zu diesem Zweck nehmen wir die folgenden Forschungsziele in Angriff: (I) Systematische Untersuchung der Auswirkungen der Graphpartitionierung auf die Leistung der GNN-Verarbeitung unter verschiedenen Mini-Batch-Sampling-Strategien. (II) Entwicklung neuer Graphpartitionierungsstrategien, die auf die Characteristika der GNN-Verarbeitung zugeschnitten sind. (III) Implementierung und Integration der neuen Graphpartitionierungsstrategien in bestehende GNN-Verarbeitungssysteme zur Optimierung der Ende-zu-Ende-Pipeline. (IV) Erweiterung der Konzepte durch Berücksichtigung von heterogenen und dynamischen Graphen. Unser Projekt wird einen Beitrag zu dem aufstrebenden Gebiet der GNN-Systeme leisten. Die Methoden und Techniken, die in diesem Projekt entwickelt werden, dürften sowohl im akademischen Bereich als auch in der Industrie und in open-source GNN-Systemen wie PyTorch Geometric und Deep Graph Library (DGL) breite Anwendung finden. Da das GNN-Training häufig auf spezialisierter Hardware wie GPUs durchgeführt wird, die teuer zu beschaffen oder in der Cloud zu mieten sind, hat die Optimierung der Ende-zu-Ende-Laufzeit der Graphpartitionierung und des GNN-Trainings das Potenzial, immense Kosteneinsparungen zu erzielen.

• DFG-Verfahren: Sachbeihilfen