Graph Unitary Message Passing

[Submitted on 17 Mar 2024 (v1), last revised 4 Jul 2026 (this version, v2)]

View PDF HTML (experimental)

Abstract:Unitarity is a useful principle for stabilizing deep neural networks, but in graph neural networks (GNNs) instability is induced not only by learnable parameters but also by the graph propagation operator. Motivated by this distinction, we propose Graph Unitary Message Passing (GUMP), a message-passing framework that uses a unitary propagation operator on a transformed graph to avoid graph-induced exponential decay under repeated propagation. GUMP combines (i) a graph transformation that maps an input graph to an Eulerian line-graph construction admitting unitary adjacency matrices, and (ii) a practical unitary projection procedure based on Newton-Schulz iteration. Theoretical analysis clarifies that, under standard analysis assumptions, unitary propagation keeps the graph-propagation term depth-stable, while vanilla normalized propagation exhibits exponential decay in its non-trivial spectral components. Across synthetic long-range tasks, TUDataset benchmarks, and LRGB datasets, GUMP improves over vanilla message passing and achieves competitive or superior performance against strong baselines. Code is available at this https URL.

Submission history

From: Haiquan Qiu [view email]
[v1] Sun, 17 Mar 2024 12:55:23 UTC (1,087 KB)
[v2] Sat, 4 Jul 2026 13:39:50 UTC (430 KB)