Erweiterung des Designraums von Graph-Neuralen Netzen durch Neubetrachtung des folklore-Weisfeiler-Lehman-Algorithmus

Message-Passing-Neural-Netzwerke (MPNNs) sind in den letzten Jahren als der beliebteste Rahmen für Graph-Neural-Netzwerke (GNNs) hervorgetreten. Ihre Ausdrucksstärke ist jedoch durch den eindimensionalen Weisfeiler-Lehman-Test (1-WL) begrenzt. Einige Arbeiten haben sich von $k$-WL/FWL (Folklore WL) inspirieren lassen und entsprechende neuronale Versionen entwickelt. Trotz ihrer hohen Ausdrucksstärke gibt es ernsthafte Einschränkungen in dieser Forschungsrichtung. Insbesondere: (1) $k$-WL/FWL erfordert eine Raumkomplexität von mindestens $O(n^k)$, was selbst bei $k=3$ für große Graphen nicht praktikabel ist; (2) Der Entwurfsraum von $k$-WL/FWL ist starr, wobei das einzige einstellbare Hyperparameter $k$ ist.Um die erste Einschränkung zu bewältigen, schlagen wir eine Erweiterung vor, nämlich $(k,t)$-FWL. Wir beweisen theoretisch, dass wir auch dann, wenn wir die Raumkomplexität auf $O(n^k)$ (für jedes $k \geq 2$) in $(k,t)$-FWL festlegen, eine Ausdrucksstufen-Hierarchie bis hin zur Lösung des Graphisomorphieproblems konstruieren können. Um das zweite Problem zu lösen, schlagen wir $k$-FWL+ vor, das jeden äquivarianten Satz als Nachbarn betrachtet anstatt aller Knoten, wodurch der Entwurfsraum von $k$-FWL erheblich erweitert wird. Die Kombination dieser beiden Modifikationen führt zu einem flexiblen und leistungsfähigen Rahmenwerk $(k,t)$-FWL+. Wir zeigen, dass $(k,t)$-FWL+ die meisten bestehenden Modelle mit gleicher Ausdrucksstärke implementieren kann.Daraufhin stellen wir eine Instanz von $(k,t)$-FWL+ vor, die Neighborhood$^2$-FWL (N$^2$-FWL) genannt wird und sowohl praktisch als auch theoretisch fundiert ist. Wir beweisen, dass N$^2$-FWL mindestens so mächtig wie 3-WL ist und viele Unterstrukturen kodieren kann, während sie nur eine Raumkomplexität von $O(n^2)$ erfordert. Schließlich entwerfen wir seine neuronale Version, N$^2$-GNN, und evaluieren ihre Leistung bei verschiedenen Aufgaben. N$^2$-GNN erreicht bahnbrechende Ergebnisse auf ZINC Subset (0,059), wobei es die bisher besten Ergebnisse um 10,6 % übertrifft. Darüber hinaus erreicht N$^2$-GNN neue Bestleistungen auf dem BREC-Datensatz (71,8 %) unter allen existierenden hochausdrucksstarken GNN-Methoden.