NP-Schwer: Graphoptimierung gegen Oversmoothing & Oversquashing

Graph Neural Networks (GNNs) stoßen beim Einsatz tiefer Architekturen auf zwei zentrale Probleme: Oversmoothing, bei dem Knotendarstellungen sich zu ähnlichen Vektoren zusammenziehen, und Oversquashing, bei dem Informationen aus weit entfernten Knoten nicht mehr durch Engpässe gelangen. Ein neues Papier auf arXiv untersucht, ob die zugrunde liegende Graphstruktur gezielt umgestaltet werden kann, um diese Schwächen zu mildern.

Die Autoren formulieren die Reduzierung von Oversmoothing und Oversquashing als Optimierungsaufgaben, die sich auf den Spektralabstand bzw. die Durchflussleitfähigkeit (Conductance) beziehen. Durch Reduktionen vom Minimum‑Bisection‑Problem zeigen sie, dass die exakte Optimierung beider Probleme NP‑schwer ist und die Entscheidungsvarianten NP‑vollständig werden. Damit wird klar, dass keine effiziente, allgemeine Lösung existiert.

Die Ergebnisse liefern eine solide theoretische Basis, warum in der Praxis auf Approximationen und heuristische Verfahren zurückgegriffen werden muss. Gleichzeitig verdeutlichen sie die Grenzen der Graph‑Rewiring‑Strategien und geben Forschern klare Richtungen für zukünftige Ansätze vor.