Eine einfache, aber effektive Baseline für die Klassifizierung von nicht-attributierten Graphen

Graphen sind komplexe Objekte, die sich nicht leicht für typische Lernaufgaben eignen. In jüngerer Zeit wurden eine Reihe von Ansätzen basierend auf Graphkernen oder Graphneuralnetzen zur Klassifikation von Graphen und zum Lernen von Repräsentationen auf Graphen im Allgemeinen entwickelt. Da die entwickelten Methodologien zunehmend anspruchsvoller werden, ist es wichtig zu verstehen, welche Komponenten der immer komplexer werdenden Methoden notwendig oder am effektivsten sind.Als ersten Schritt entwickeln wir eine einfache, aber sinnvolle Graphrepräsentation und untersuchen ihre Effektivität in der Graphklassifikation. Wir testen unsere Baseline-Repräsentation für die Aufgabe der Graphklassifikation anhand einer Vielzahl von Graphdatensätzen. Interessanterweise erreicht diese einfache Repräsentation ähnliche Leistungen wie die neuesten Graphkerne und Graphneuralnetze bei der Klassifikation von nicht-attributierten Graphen. Ihre Leistung bei der Klassifikation von attributierten Graphen ist etwas schwächer, da sie Attributen nicht Rechnung trägt. Dennoch glauben wir, dass sie aufgrund ihrer Einfachheit und Effizienz weiterhin als effektive Baseline für die Klassifikation von attributierten Graphen dient. Unsere Graphrepräsentation kann effizient (in linearer Zeit) berechnet werden. Wir stellen auch einen einfachen Zusammenhang mit den Graphneuralnetzen her.Es sei darauf hingewiesen, dass diese Beobachtungen nur für die Aufgabe der Graphklassifikation gelten, während bestehende Methoden oft für einen breiteren Anwendungsbereich entwickelt wurden, einschließlich Knoteneinbettung und Linkprognose. Die Ergebnisse sind wahrscheinlich auch durch die begrenzte Anzahl verfügbarer Benchmark-Datensätze verzerrt. Trotzdem weist die gute Leistung unserer einfachen Baseline auf die Notwendigkeit hin, neue, umfassendere Benchmark-Datensätze zu entwickeln, um verschiedene Methoden des graphbasierten Lernens besser zu bewerten und zu analysieren. Zudem glauben wir, dass aufgrund der rechnerischen Effizienz unserer Graphzusammenfassung sie ein guter Kandidat als Basismethode für zukünftige Studien zur Graphklassifikation (oder sogar andere graphbasierte Lernaufgaben) ist.