Verständnis von Over-Squashing und Bottlenecks auf Graphen mittels Krümmung

Die meisten Graph Neural Networks (GNNs) basieren auf dem Message-Passing-Paradigma, bei dem Knotenmerkmale über den Eingabegraphen propagiert werden. Neuere Arbeiten haben darauf hingewiesen, dass die Verzerrung der Information, die von entfernten Knoten ausgeht, einen Faktor darstellt, der die Effizienz des Message Passing für Aufgaben mit langreichweitigen Interaktionen einschränkt. Dieses Phänomen, als „Over-Squashing“ bezeichnet, wurde bisher heuristisch auf Graph-Bottlenecks zurückgeführt, bei denen die Anzahl der $k$-Hop-Nachbarn mit wachsendem $k$ rasch ansteigt. Wir geben eine präzise Beschreibung des Over-Squashing-Phänomens in GNNs an und analysieren, wie es aus Bottlenecks im Graphen entsteht. Dazu führen wir eine neue, kantenbasierte kombinatorische Krümmung ein und beweisen, dass negativ gekrümmte Kanten für das Over-Squashing-Problem verantwortlich sind. Zudem schlagen wir eine auf Krümmung basierende Methode zur Umstrukturierung des Graphen vor und testen sie experimentell, um das Over-Squashing zu mildern.