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

arXiv: https://arxiv.org/abs/2608.09596 · HTML: https://mlsanity.com/paper/2608.09596/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 34 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [On the Connection Between MPNN and Graph Transformer](https://mlsanity.com/paper/2301.11956/) (2023)
- [Virtual Node Tuning for Few-shot Node Classification](https://mlsanity.com/paper/2306.06063/) (2023)
- [Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature](https://mlsanity.com/paper/2309.09384/) (2023)
- [Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study](https://mlsanity.com/paper/2108.10521/) (2021)
- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization](https://mlsanity.com/paper/2305.19903/) (2023)
- [The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited](https://mlsanity.com/paper/2407.09381/) (2024)
- [PANDA: Expanded Width-Aware Message Passing Beyond Rewiring](https://mlsanity.com/paper/2406.03671/) (2024)
- [Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective of Operator Semigroup Theory](https://mlsanity.com/paper/2402.15326/) (2024)
- [Fast and Distributed Equivariant Graph Neural Networks by Virtual Node Learning](https://mlsanity.com/paper/2506.19482/) (2025)
- [Fault Detection in Telecom Networks using Bi-level Federated Graph Neural Networks](https://mlsanity.com/paper/2311.14469/) (2023)
- [Graph Neural Networks in Computer Vision -- Architectures, Datasets and Common Approaches](https://mlsanity.com/paper/2212.10207/) (2022)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Self-Supervised Node Representation Learning via Node-to-Neighbourhood Alignment](https://mlsanity.com/paper/2302.04626/) (2023)
- [Enhancing 5G Radio Planning with Graph Representations and Deep Learning](https://mlsanity.com/paper/2309.03603/) (2023)
- [Gradient Rewiring for Editable Graph Neural Network Training](https://mlsanity.com/paper/2410.15556/) (2024)
- [Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks](https://mlsanity.com/paper/2508.20597/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) suffer from two fundamental limitations: over-smoothing, where node representations become indistinguishable with depth, and over-squashing, where long-range information is compressed through limited message-passing channels. Existing metrics such as Dirichlet energy provide global characterizations of over-smoothing but lack the resolution to analyze node-level behavior and guide architectural improvements. In this paper, we propose LEED (Local Embedding Evolution Distance), a novel local metric that quantifies over-smoothing by tracking the evolution of individual node embeddings across layers. By operating at the node level, LEED enables fine-grained analysis of representation dynamics during training, revealing heterogeneous over-smoothing patterns that are invisible to global energy-based measures. This locality induces informative node importance scores, interpreted as embedding-driven centrality measures. We leverage LEED to design a more efficient strategy for virtual node selection. Unlike existing approaches that depend on multiple heuristic centrality measures, our method uses LEED as a unique criterion to guide the construction of Local Virtual Nodes to mitigate over-squashing. Experiments show that LEED provides more informative diagnostics than Dirichlet energy while preserving global evaluation, and enables more effective virtual node integration, improving GNN performance across datasets.