Cluster-GCN: Ein effizienter Algorithmus für das Training tiefer und großer Graphenkonvolutionalnetze

Das Graph Convolutional Network (GCN) wurde erfolgreich auf viele graphbasierte Anwendungen angewendet; jedoch bleibt das Training eines groß angelegten GCNs weiterhin eine Herausforderung. Aktuelle Algorithmen, die auf stochastischem Gradientenabstieg (SGD) basieren, leiden entweder unter hohen Rechenkosten, die exponentiell mit der Anzahl der GCN-Schichten wachsen, oder sie erfordern viel Speicherplatz, um den gesamten Graphen und die Einbettung jedes Knotens im Arbeitsspeicher zu halten. In dieser Arbeit schlagen wir Cluster-GCN vor, einen neuen GCN-Algorithmus, der durch Ausnutzung der Clustereigenschaften von Graphen für SGD-basiertes Training geeignet ist. Cluster-GCN funktioniert wie folgt: Bei jedem Schritt wird ein Block von Knoten ausgewählt, die mit einem dicht besetzten Teilgraphen verbunden sind, der durch einen Graphclustering-Algorithmus identifiziert wurde, und die Nachbarschaftssuche wird auf diesen Teilgraphen eingeschränkt. Diese einfache aber effektive Strategie führt zu einer erheblichen Verbesserung der Speichereffizienz und Rechengeschwindigkeit, während vergleichbare Testgenauigkeiten wie bei früheren Algorithmen erreicht werden können. Um die Skalierbarkeit unseres Algorithmus zu testen, haben wir einen neuen Datensatz namens Amazon2M erstellt, der 2 Millionen Knoten und 61 Millionen Kanten enthält und mehr als fünfmal so groß ist wie der bisher größte öffentlich verfügbare Datensatz (Reddit). Beim Training eines 3-schichtigen GCNs auf diesen Daten ist Cluster-GCN schneller als der bislang beste VR-GCN (1523 Sekunden gegenüber 1961 Sekunden) und benötigt deutlich weniger Speicherplatz (2,2 GB gegenüber 11,2 GB). Darüber hinainaus kann unser Algorithmus das Training eines 4-schichtigen GCNs in etwa 36 Minuten abschließen, während alle existierenden GCN-Trainingsalgorithmen aufgrund von Speicherproblemen scheitern. Zudem ermöglicht uns Cluster-GCN das Training tiefer gehender GCNs ohne erhebliche zusätzliche Zeitaufwand oder Speicherverbrauch, was zu einer verbesserten Vorhersagegenauigkeit führt – mit einem 5-schichtigen Cluster-GCN erreichen wir den aktuellen Stand der Technik in Form eines Test-F1-Werts von 99,36 beim PPI-Datensatz; das bisher beste Ergebnis lag bei 98,71 nach [16]. Unser Code ist öffentlich zugänglich unter https://github.com/google-research/google-research/tree/master/cluster_gcn.