Weisfeiler und Leman gehen sparsam: Auf skalierbare höhere Grapheneinbettungen zu

Graph-Kerne basierend auf dem 1-dimensionalen Weisfeiler-Leman-Algorithmus und entsprechende neuronale Architekturen sind kürzlich als leistungsstarke Werkzeuge für (überwachtes) Lernen mit Graphen hervorgetreten. Aufgrund der rein lokalen Natur der Algorithmen können sie jedoch wesentliche Muster in den gegebenen Daten übersehen und verarbeiten nur binäre Relationen. Der $k$-dimensionale Weisfeiler-Leman-Algorithmus behebt dies, indem er $k$-Tupel betrachtet, die über der Menge der Knoten definiert sind, und eine geeignete Adjazenzdefinition zwischen diesen Knotentupeln festlegt. Somit berücksichtigt er höhere Ordnungen von Interaktionen zwischen den Knoten. Allerdings skaliert er nicht gut und kann bei Verwendung in einem maschinellen Lernszenario anfällig für Overfitting sein. Es bleibt daher ein wichtiges offenes Problem, WL-basierte Graph-Lernmethoden zu entwickeln, die gleichzeitig ausdrucksstark, skalierbar und nicht-overfittend sind. In diesem Beitrag schlagen wir lokale Varianten und entsprechende neuronale Architekturen vor, die einen Teil des ursprünglichen Nachbarschaftsbereichs berücksichtigen, wodurch sie skalierbarer werden und weniger anfällig für Overfitting sind. Die Ausdrucksstärke (eines unserer Algorithmen) ist streng höher als die des ursprünglichen Algorithmus, wenn es um die Fähigkeit geht, nicht-isomorphe Graphen zu unterscheiden. Unsere experimentelle Studie bestätigt, dass die lokalen Algorithmen sowohl in Form von Kernen als auch neuronaler Architektur zu erheblich reduzierten Rechenzeiten führen und Overfitting verhindern. Die Kernversion etabliert einen neuen Stand der Technik für die Graphklassifikation auf einer Vielzahl von Benchmark-Datensätzen, während die neuronale Version vielversprechende Ergebnisse bei regressiven Aufgaben auf großen molekularen Datensätzen zeigt.