Algorithmus- und System-Co-Design für effiziente subgraphbasierte Graph-Darstellungslernverfahren

Subgraph-basierte Graph-Darstellungslernverfahren (SGRL) wurden kürzlich vorgeschlagen, um grundlegende Herausforderungen zu bewältigen, die mit herkömmlichen Graph-Neural-Networks (GNNs) verbunden sind, und haben sich in zahlreichen bedeutenden Anwendungen der Datenwissenschaft – beispielsweise bei der Link-, Relation- und Motiv-Vorhersage – als vorteilhaft erwiesen. Allerdings leiden aktuelle SGRL-Ansätze unter Skalierbarkeitsproblemen, da für jeden Trainings- oder Testquery die Extraktion von Teilgraphen erforderlich ist. Neuere Ansätze zur Skalierung herkömmlicher GNNs sind für SGRL nicht direkt anwendbar. In diesem Beitrag präsentieren wir einen neuartigen Framework namens SUREL, der skalierbares SGRL durch eine gemeinsame Gestaltung des Lernalgorithmus und seiner systemtechnischen Unterstützung ermöglicht. SUREL nutzt eine auf Wegen basierende Zerlegung von Teilgraphen und wiederverwendet diese Wege zur Bildung von Teilgraphen, wodurch die Redundanz bei der Teilgraphenextraktion erheblich reduziert und parallele Berechnungen unterstützt werden. Experimente an sechs homogenen, heterogenen und höherordentlichen Graphen mit Millionen von Knoten und Kanten belegen die Effektivität und Skalierbarkeit von SUREL. Insbesondere erreicht SUREL gegenüber SGRL-Baselines eine Beschleunigung um das Zehnfache bei vergleichbarer oder sogar besserer Vorhersagegenauigkeit; im Vergleich zu herkömmlichen GNNs verbessert SUREL die Vorhersagegenauigkeit um 50 %.