Unitary Convolutions for Message-passing and Positional Encodings on Directed Graphs

In many real-world networks, relationships are inherently directional, yet most graph neural networks (GNNs) assume undirected edges, and naïve adaptations of undirected GNNs to directed graphs amplify oversmoothing and gradient pathologies that cap model depth. Unitary graph convolutions (UniConv) provably prevent representational collapse and oversmoothing, but cannot incorporate edge directionality or edge features. In this paper, we introduce a directed unitary GNN with edge features (Dune), which retains these guarantees while overcoming UniConv’s limitations by incorporating edge directionality and edge features. Dune keeps gradient norms bounded at any number of layers, allowing it to benefit from neural network depth, unlike existing directed GNNs. The same unitary operator can be embedded in hybrid architectures with graph transformers, where its wavelike propagation supplies positional information and reduces the importance of random-walk or Laplacian-based encodings. We prove that Dune avoids exponential oversmoothing that plagues existing directed GNNs and empirically show that it achieves state-of-the-art performance on 12 directed-graph benchmarks while remaining trainable beyond 100 layers, improving performance by up to 18 percentage points over strong baselines. Our results establish unitary convolutions as a scalable, geometry-aware foundation for deep learning on directed graphs.

The paper introduces Dune, a new type of graph neural network designed for directed graphs, where relationships have a clear direction, such as citations, traffic flow, circuits, or information spread. Many existing graph models either ignore direction or become hard to train when made very deep, because node representations can blur together or gradients can vanish. Dune addresses this by using unitary transformations, which preserve signal size as information moves through the graph. This helps the model remain stable even with many layers. It also supports edge features, meaning it can use information attached to connections, not just nodes. The authors show theoretically that Dune avoids a common failure mode called oversmoothing and can capture useful directed graph structure. In experiments across node classification and graph regression tasks, Dune performs strongly compared with existing directed GNNs and can also improve graph transformer models by providing useful geometric information.