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

Lukas Fesser, Bobak Kiani, Melanie Weber
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:30968-30991, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-fesser26b, title = {Unitary Convolutions for Message-passing and Positional Encodings on Directed Graphs}, author = {Fesser, Lukas and Kiani, Bobak and Weber, Melanie}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {30968--30991}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/fesser26b/fesser26b.pdf}, url = {https://proceedings.mlr.press/v306/fesser26b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Unitary Convolutions for Message-passing and Positional Encodings on Directed Graphs %A Lukas Fesser %A Bobak Kiani %A Melanie Weber %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-fesser26b %I PMLR %P 30968--30991 %U https://proceedings.mlr.press/v306/fesser26b.html %V 306 %X 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.
APA
Fesser, L., Kiani, B. & Weber, M.. (2026). Unitary Convolutions for Message-passing and Positional Encodings on Directed Graphs. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:30968-30991 Available from https://proceedings.mlr.press/v306/fesser26b.html.

Related Material