LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN

To address the two major limitations of Graph Neural Networks (GNN): over-smoothness and over-compression, researchers proposed Local Embedding Evolution Distance (LEED) as a new local metric to quantify over-smoothness. This metric analyzes nodes at the level of individual nodes by tracking the evolution of node embeddings in each layer, revealing heterogeneous over-smoothness patterns that cannot be captured by global energy metrics. It also generates centrality scores based on embeddings. The study utilized LEED to design a virtual node selection strategy to replace existing methods that rely on multiple heuristic centrality metrics, thereby constructing local virtual nodes to alleviate over-compression issues. Experiments showed that LEED provides richer diagnostic information while maintaining global evaluation, and it can more effectively integrate virtual nodes, thereby improving the performance of GNNs across various datasets.