Rethinking Over-Smoothing in Graph Neural Networks: A Perspective from Anderson Localization
This addresses the issue of node representations losing distinctiveness in deep GNNs, which is a critical bottleneck for graph data analysis, but the approach is incremental as it builds on existing theoretical frameworks.
The paper tackles the problem of over-smoothing in Graph Neural Networks (GNNs) by analyzing it through the analogy to Anderson localization, introducing participation degree as a metric to quantify the phenomenon, and proposing that reducing disorder in information propagation can alleviate it.
Graph Neural Networks (GNNs) have shown great potential in graph data analysis due to their powerful representation capabilities. However, as the network depth increases, the issue of over-smoothing becomes more severe, causing node representations to lose their distinctiveness. This paper analyzes the mechanism of over-smoothing through the analogy to Anderson localization and introduces participation degree as a metric to quantify this phenomenon. Specifically, as the depth of the GNN increases, node features homogenize after multiple layers of message passing, leading to a loss of distinctiveness, similar to the behavior of vibration modes in disordered systems. In this context, over-smoothing in GNNs can be understood as the expansion of low-frequency modes (increased participation degree) and the localization of high-frequency modes (decreased participation degree). Based on this, we systematically reviewed the potential connection between the Anderson localization behavior in disordered systems and the over-smoothing behavior in Graph Neural Networks. A theoretical analysis was conducted, and we proposed the potential of alleviating over-smoothing by reducing the disorder in information propagation.