Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph

Andreas Roth, Franka Bause, Nils Morten Kriege, Thomas Liebig
Proceedings of the Third Learning on Graphs Conference, PMLR 269:14:1-14:24, 2025.

Abstract

The ability of message-passing neural networks (MPNNs) to fit complex functions over graphs is limited as most graph convolutions amplify the same signal across all feature channels, a phenomenon known as rank collapse, and over-smoothing as a special case. Most approaches to mitigate over-smoothing extend common message-passing schemes, e.g., the graph convolutional network, by utilizing residual connections, gating mechanisms, normalization, or regularization techniques. Our work contrarily proposes to directly tackle the cause of this issue by modifying the message-passing scheme and exchanging different types of messages using multi-relational graphs. We identify a sufficient condition to ensure linearly independent node representations. As one instantion, we show that operating on multiple directed acyclic graphs always satisfies our condition and propose to obtain these by defining a strict partial ordering of the nodes. We conduct comprehensive experiments that confirm the benefits of operating on multi-relational graphs to achieve more informative node representations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v269-roth25a, title = {Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph}, author = {Roth, Andreas and Bause, Franka and Kriege, Nils Morten and Liebig, Thomas}, booktitle = {Proceedings of the Third Learning on Graphs Conference}, pages = {14:1--14:24}, year = {2025}, editor = {Wolf, Guy and Krishnaswamy, Smita}, volume = {269}, series = {Proceedings of Machine Learning Research}, month = {26--29 Nov}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v269/main/assets/roth25a/roth25a.pdf}, url = {https://proceedings.mlr.press/v269/roth25a.html}, abstract = {The ability of message-passing neural networks (MPNNs) to fit complex functions over graphs is limited as most graph convolutions amplify the same signal across all feature channels, a phenomenon known as rank collapse, and over-smoothing as a special case. Most approaches to mitigate over-smoothing extend common message-passing schemes, e.g., the graph convolutional network, by utilizing residual connections, gating mechanisms, normalization, or regularization techniques. Our work contrarily proposes to directly tackle the cause of this issue by modifying the message-passing scheme and exchanging different types of messages using multi-relational graphs. We identify a sufficient condition to ensure linearly independent node representations. As one instantion, we show that operating on multiple directed acyclic graphs always satisfies our condition and propose to obtain these by defining a strict partial ordering of the nodes. We conduct comprehensive experiments that confirm the benefits of operating on multi-relational graphs to achieve more informative node representations.} }
Endnote
%0 Conference Paper %T Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph %A Andreas Roth %A Franka Bause %A Nils Morten Kriege %A Thomas Liebig %B Proceedings of the Third Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2025 %E Guy Wolf %E Smita Krishnaswamy %F pmlr-v269-roth25a %I PMLR %P 14:1--14:24 %U https://proceedings.mlr.press/v269/roth25a.html %V 269 %X The ability of message-passing neural networks (MPNNs) to fit complex functions over graphs is limited as most graph convolutions amplify the same signal across all feature channels, a phenomenon known as rank collapse, and over-smoothing as a special case. Most approaches to mitigate over-smoothing extend common message-passing schemes, e.g., the graph convolutional network, by utilizing residual connections, gating mechanisms, normalization, or regularization techniques. Our work contrarily proposes to directly tackle the cause of this issue by modifying the message-passing scheme and exchanging different types of messages using multi-relational graphs. We identify a sufficient condition to ensure linearly independent node representations. As one instantion, we show that operating on multiple directed acyclic graphs always satisfies our condition and propose to obtain these by defining a strict partial ordering of the nodes. We conduct comprehensive experiments that confirm the benefits of operating on multi-relational graphs to achieve more informative node representations.
APA
Roth, A., Bause, F., Kriege, N.M. & Liebig, T.. (2025). Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph. Proceedings of the Third Learning on Graphs Conference, in Proceedings of Machine Learning Research 269:14:1-14:24 Available from https://proceedings.mlr.press/v269/roth25a.html.

Related Material