Heterophilie in der Knotenklassifizierung mit Graph-Echo-State-Netzwerken behandeln

Knotenklassifizierungsaufgaben in Graphen werden durch vollständig trainierte tiefe Nachrichtenübertragungsmodelle angegangen, die eine Hierarchie von Knotendarstellungen durch mehrfache Aggregation der Nachbarschaft eines Knotens erlernen. Obwohl diese Methode bei Graphen mit einem hohen Verhältnis von innerhalb der Klasse liegenden Kanten effektiv ist, stellt sie bei heterophilen Graphen Herausforderungen dar, bei denen Knoten derselben Klasse in der Regel weiter voneinander entfernt sind. In Graphen mit einem hohen Grad an Heterophilie sind die auf nahegelegenen Nachbarn basierenden geglätteten Darstellungen, die durch Faltungsmodelle berechnet werden, nicht länger effektiv. Bisher wurden architekturale Variationen in den Nachrichtenübertragungsmodellen vorgeschlagen, um übermäßiges Glätten zu reduzieren oder den Eingabegraphen zu neu verdrahten, um eine bessere langreichweitige Nachrichtenübertragung zu ermöglichen. In dieser Arbeit adressieren wir die Herausforderungen heterophiler Graphen mit dem Graph Echo State Network (GESN) für die Knotenklassifizierung. GESN ist ein Reservoir-Computing-Modell für Graphen, bei dem Knoteneinbettungen rekursiv durch eine untrainierte Nachrichtenübertragungsfunktion berechnet werden. Unsere Experimente zeigen, dass Reservoir-Modelle im Vergleich zu den meisten vollständig trainierten tiefen Modellen, die ad hoc Variationen im architektonischen Bias implementieren oder als Vorverarbeitungsschritt das Neuerstellen des Eingabegraphens durchführen, eine bessere oder vergleichbare Genauigkeit erreichen können und sich hinsichtlich des Effizienz/Genauigkeit-Kompromisses verbessern lassen. Darüber hinaus zeigt unsere Analyse, dass GESN in der Lage ist, die strukturellen Beziehungen eines Graphenknotens effektiv zu kodieren, indem es eine Korrelation zwischen den Iterationsschritten der rekursiven Einbettungsfunktion und der Verteilung der kürzesten Pfade in einem Graphen aufzeigt.