Neuronale Prioritätswarteschlangen für Graph Neural Networks

Graph Neural Networks (GNNs) haben erheblichen Erfolg bei der neuronalen algorithmischen Schlussfolgerung gezeigt. Viele klassische Algorithmen nutzen eine explizite Speicherstruktur in Form einer Datenstruktur. Die Erweiterung von GNNs um externen Speicher wurde jedoch bisher nur wenig erforscht. In diesem Paper stellen wir Neural Priority Queues vor – eine differenzierbare Analogie zu algorithmischen Prioritätswarteschlangen – für GNNs. Wir formulieren und begründen eine Reihe von wünschenswerten Eigenschaften für Speichermodule und zeigen, dass Neural PQs diese Eigenschaften erfüllen. Zudem diskutieren wir deren Einsatz im Kontext algorithmischer Schlussfolgerung. Diese Aussagen werden empirisch anhand des CLRS-30-Datensatzes bestätigt. Darüber hinaus zeigen wir, dass Neural PQs nützlich sind, um langreichweitige Wechselwirkungen zu erfassen, wie anhand eines Datensatzes aus dem Long-Range Graph Benchmark empirisch nachgewiesen wird.