Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks
Our study reveals new theoretical insights into over-smoothing and feature over-correlation in deep graph neural networks. We show the prevalence of invariant subspaces, demonstrating a fixed relative behavior that is unaffected by feature transformations. Our work clarifies recent observations related to convergence to a constant state and a potential over-separation of node states, as the amplification of subspaces only depends on the spectrum of the aggregation function. In linear scenarios, this leads to node representations being dominated by a low-dimensional subspace with an asymptotic convergence rate independent of the feature transformations. This causes a rank collapse of the node representations, resulting in over-smoothing when smooth vectors span this subspace, and over-correlation even when over-smoothing is avoided. Guided by our theory, we propose a sum of Kronecker products as a beneficial property that can provably prevent over-smoothing, over-correlation, and rank collapse. We empirically extend our insights to the non-linear case, demonstrating the inability of existing models to capture linearly independent features.
- Published in:
Workshop on Mining and Learning with Graphs at European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - Type:
Inproceedings - Authors:
Roth, Andreas; Liebig, Thomas - Year:
2023
Citation information
Roth, Andreas; Liebig, Thomas: Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks, Workshop on Mining and Learning with Graphs at European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023, https://proceedings.mlr.press/v231/roth24a.html, Roth.Liebig.2023a,
@Inproceedings{Roth.Liebig.2023a,
author={Roth, Andreas; Liebig, Thomas},
title={Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks},
booktitle={Workshop on Mining and Learning with Graphs at European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
url={https://proceedings.mlr.press/v231/roth24a.html},
year={2023},
abstract={Our study reveals new theoretical insights into over-smoothing and feature over-correlation in deep graph neural networks. We show the prevalence of invariant subspaces, demonstrating a fixed relative behavior that is unaffected by feature transformations. Our work clarifies recent observations related to convergence to a constant state and a potential over-separation of node states, as the...}}