LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN
2026-08-10 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors study two problems in Graph Neural Networks (GNNs): over-smoothing, where nodes become too similar when the network gets deeper, and over-squashing, where important information gets compressed while passing through the network. They introduce LEED, a new way to measure over-smoothing by looking at individual nodes instead of the whole graph, which helps understand how each node's representation changes layer by layer. Using LEED, they also create a better method to add special 'virtual nodes' that help fix over-squashing. Their experiments show that LEED gives better insights and improves GNN performance compared to older methods.
Graph Neural NetworksOver-smoothingOver-squashingNode embeddingsDirichlet energyMessage passingVirtual nodesCentrality measuresRepresentation learningLocal metrics
Authors
Killian Cressant, Pedro B. Velloso
Abstract
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.