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

arXiv:2608.09596 · cs.LG, cs.AI · Submitted 2026-08-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN".

Jane: The paper was written by the authors from Conservatoire National des Arts et Métiers.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Summary: Jane: Now that we've established that over-smoothing is a pervasive problem, the paper's summary really zeroes in on how they propose to fix it using this distance metric. They aren't just suggesting one patch; they are describing a whole framework.

Tom: It sounds like they are leveraging the local embedding evolution distance not just as a warning light, but as an active component of the network architecture itself. Is that right?

Lu: Precisely. They show how by incorporating this local distance calculation, we can guide the GNN process to preserve structural information that would otherwise be lost in global averaging. It’s a highly localized form of knowledge retention.

Meng: The paper mentions using this for "virtual node selection," which is intriguing. Can you break down what that means in practical terms? Are they adding fake nodes?

Jane: Not exactly fake, Meng, but virtual nodes here means identifying key structural points or relationships that are crucial to the graph's integrity, even if they aren't explicitly modeled by the original data structure.

Lalam: It’s a way of telling the model, "Hey, pay extra attention to these connections because they carry unique information that standard message passing might dilute."

Tom: So if we can pinpoint those critical nodes using the LEED metric, we could potentially enhance their feature representation before they even get processed by the main GNN layers?

Lu: Exactly. It’s about intelligently boosting the signal-to-noise ratio for the most important structural elements, making our models more robust to graph size and density.

Meng: I appreciate that focus on selectivity; if we could pre-select and boost features based on local distance metrics, it would drastically reduce computational load while improving accuracy in complex graphs.

Lalam: The implication here is that the AI system moves from being a passive processor of data to an active structural analyst, prioritizing information flow based on mathematical evidence of importance.

Jane: So, to wrap up this segment: the summary shows us a method that uses local distance metrics to intelligently guide the GNN process and select crucial structural components—the virtual nodes—to combat over-smoothing. But how do they make this selection even better?

Improvements: Tom: We've talked about diagnosing the problem and summarizing the basic solution, but I know the paper goes further, suggesting specific improvements. Lu, when they talk about refining this approach, what’s the big technical leap?

Lu: They introduce sophisticated methods for handling how these distances evolve across different layers of the network. It’s not enough to just measure it once; you need to model its change over time—or rather, over depth in the network.

Jane: Think of it like this: a simple measurement might tell you if a river is muddy, but the improved methods help predict *how* quickly that mud will settle or flow downstream. It adds temporal and spatial dynamics to the embedding distance calculation.

Meng: That idea of modeling evolution sounds computationally heavy, though. How do they make these improved mechanisms scalable for truly massive graphs with millions of nodes?

Lalam: The key insight from the improvements is that you don't need to track the entire global evolution; you only need to focus on highly localized, constrained evolutions that are mathematically guaranteed to preserve critical information.

Tom: So, they are making the sophisticated calculation manageable by limiting its scope? That makes a lot of sense for real-world deployment.

Jane: It refines the selection process dramatically. Instead of just selecting nodes based on *current* distance, they select nodes that are predicted to maintain their unique embedding signature *throughout* multiple layers of graph processing.

Lu: That’s the breakthrough

Paper discussion segment 3: Tom: So we've spent some time discussing how GNNs struggle with information decay, but today, let's focus on how much better this approach is because of something called "LEED."

Jane: That’s right; it’s all about this new metric they introduced in the paper, "LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN," which gives us a way to measure *where* and *how bad* the information loss actually is.

Lu: What's exciting here, conceptually, is that instead of just treating over-smoothing as a global phenomenon—just saying "it’s bad everywhere"—LEED allows us to pinpoint the exact local regions where the embedding space has diverged too much from its initial state.

Jane: Think of it like this: if you're reading a massive book and you realize that only Chapter five in particular, is getting confusing and fuzzy, LEED tells you exactly which page it is, rather than just saying the whole book is hard to follow.

Meng: But from an engineering viewpoint, how does knowing this localized distance actually translate into tangible system improvements? Are we talking about a simple parameter adjustment or something that requires a complete overhaul of the GNN pipeline?

Tom: I was wondering that too, Meng. So Lu, when you say pinpointing the exact region, does that mean the model can dynamically allocate computational resources—like adding more virtual nodes—only to those weak spots?

Lu: Exactly! It moves us from a blanket fix to a targeted intervention. The distance metric guides the placement and density of those helpful virtual nodes, making the process far more efficient and mathematically rigorous than previous heuristic methods.

Jane: That's such a powerful shift; it’s giving GNNs a diagnostic tool, allowing them to self-assess their own potential points of failure before they even make a prediction.

Meng: If this capability is integrated into an AI platform, it changes the deployment model entirely; instead of assuming uniform data quality across all graph types, we could run continuous diagnostic checks based on LEED scores.

Lu: And that's the theoretical leap—it implies a self-correcting architecture for deep learning models operating on complex relational data structures.

Jane: It makes us think about how many other complex systems, outside of pure AI, might benefit from such precise localized measurement techniques.

Lalam: What this truly means for the future of culture is that we're moving away from generalized computational intelligence towards hyper-specialized, diagnostically aware AI; it elevates the entire field by making robustness measurable and predictable.

Tom: So, if LEED gives us a perfect diagnostic tool for graph structure decay, what other inherent measurement challenges in complex systems could we apply this principle to next?

Conclusion: Tom: So, wrapping up our deep dive on this material, it really seems like we’ve seen a huge step forward in how we model graph data, moving beyond just trying to patch up existing limitations.

Jane: Exactly, Tom; what I'm taking away is that instead of viewing over-smoothing and over-squashing as just problems to be fixed with more parameters, the authors gave us a whole new mathematical tool—the Local Embedding Evolution Distance—to *estimate* when those issues pop up in the first place.

Lu: That ability to quantify the degradation mathematically is huge; it means we can build diagnostic tools right into our GNN pipelines that tell us, "Hey, you're about to lose too much local structure here."

Meng: But Lu, practically speaking, if I were deploying this for a client who needs real-time inference on massive graphs, how computationally expensive is calculating this 'Evolution Distance' across millions of nodes? That’s my main concern.

Jane: Meng raises a good point; it suggests that the practical implementation might need to focus on approximations or local windowing rather than global calculations to keep latency down.

Tom: And I think the implication here isn't just about better accuracy; it’s about building trust in AI models used for critical infrastructure, where losing subtle node identity could be catastrophic.

Lu: If we can reliably measure how much structural information is being averaged out, we can design specialized message passing that actively preserves heterogeneity, which opens up fields like complex biological modeling or social network resilience testing.

Meng: Speaking of resilience, the idea of using virtual nodes to guide the process rather than just letting the message pass freely sounds like a way to inject necessary contextual information without retraining the entire graph from scratch.

Lalam: Considering all these advances, what really stands out is how this work elevates graph theory from a niche academic concern into a core, measurable metric for system reliability across culture.

Jane: It's giving us the language to explain *why* an AI model might fail on a specific type of graph structure, which is something we desperately needed in the field.

Tom: So, if I'm summarizing this entire session for our listeners, we’re looking at a paradigm shift that gives us concrete tools for diagnosing graph network degradation.

Lu: It really feels like the conceptual hurdle for robust GNNs has been significantly lowered by providing such a direct measurement technique.

Meng: From an engineering standpoint, it makes the entire field feel more mature because we have this diagnostic step we can actually build into a product pipeline.

Lalam: Ultimately, this research, titled "LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN," helps us build AI systems that are not just powerful, but also deeply understandable and trustworthy.

Jane: It’s amazing to see how much the field is advancing so quickly; we're really excited to wrap up this discussion on LEED today.

Tom: We can't wait to dig into whatever graph problem we tackle next for you all!

Conservatoire National des Arts et Métiers

cs.LG, cs.AI

Submitted: 2026-08-10

Updated: 2026-09-04

Comments: 10 pages, journal

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 70/100

The gist: LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN Summary This paper introduces LEED (Local Embedding Evolution Distance), a novel node-level

Key concepts

Over-smoothing
A pervasive problem in GNNs where global averaging causes information loss or decay. Instead of retaining unique local structure, the model struggles to distinguish between different parts of the graph.
LEED (Local Embedding Evolution Distance)
A novel mathematical metric used to estimate and pinpoint exactly where and how much information loss is occurring within a graph's embedding space. It allows diagnosis of localized divergence rather than treating the issue globally.
Virtual Node Selection
A technique that identifies key structural points or relationships crucial to a graph’s integrity, even if they are not explicitly present in the original data. This helps boost the signal-to-noise ratio for important connections.

Terminology

Summary

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

Summary

This paper introduces LEED (Local Embedding Evolution Distance), a novel node-level metric designed to address two fundamental limitations of Graph Neural Networks (GNNs): over-smoothing and over-squashing. The authors, Killian Cressant and Pedro B. Velloso from CEDRIC Lab, Conservatoire National des Arts et Métiers (Cnam), France, propose LEED as a local metric that quantifies over-smoothing by tracking the evolution of individual node embeddings across layers.

Motivation and Problem Statement

GNNs suffer from two fundamental challenges: over-smoothing, where node representations become indistinguishable with depth, and over-squashing, where long-range information is compressed through limited message-passing channels. The authors note that 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. They argue that over-smoothing "should not be viewed solely as a message-passing issue, but more fundamentally as a graph connectivity problem: nodes belonging to dense substructures, such as cliques, tend to exhibit embeddings that are significantly more similar to each other than to the rest of the graph."

LEED Definition and Design Principles

LEED is defined as a node-level metric that quantifies the evolution of node embeddings over the message-passing process to understand how individual node representations change across network layers. The design principles include:

  1. Symmetry: any measure quantifying the dissimilarity between two nodes should be symmetric

  2. Local focus: Unlike Dirichlet energy which aggregates over all neighboring pairs, LEED focuses on local proximity by considering only the minimum distance between a node and its neighbors, rather than summing distances across all edges

  3. Two-hop neighborhood: LEED incorporates a corrected two-hop neighborhood aggregation centered around each node to capture richer local structural information, including nodes involved in long-range information transfer

The core LEED formulation is:

l(xi(k)) = min j∈Ni T m(xi(k)) - T m(xj(k))22

where T m is a mean evolution function depending on m-hops, weighted by the adjacency matrix with self-loop correction. The authors define T1 and T2 for one-hop and two-hop aggregations respectively.

The global LEED score is:

L(X(k)) = Σ i=1 n l(xi(k))

Theoretical Properties

The authors prove that LEED is bounded by the Dirichlet energy:

L(X(k)) ≤ max i∈N (2/d i) · C Tb · E(X(k))

where C Tb is a value depending on T and X. They establish that the profile of Dirichlet energy is likely to be similar to that of the LEED distance through experiments with eight different adjacency matrices. The authors note that the relative evolution of LEED is more informative than its absolute value.

Critical Node Selection

LEED is used to identify critical nodes for graph rewiring. The critical node score is defined as:

D i = T2(xi(0)) - xi(0)2, i ∈ [1, n]

This uses only input values and initial embeddings, avoiding the need to search across layers. A top-K selection strategy is applied using the (1-k)-quantile τk.

For datasets without node features (e.g., REDDIT-BINARY, COLLAB), the authors use constant feature vectors, yielding a closed-form solution:

D i = d i - 2 / (d i + 2)

This yields a value in [0, 1], that increases monotonically with d i, the degree of node i. For one-hot encoded embeddings (e.g., MUTAG, ENZYMES), the authors derive that the optimal score for node i arises when it serves to bridge distinct components of the graph, making LEED more closely related to information importance than to topological importance.

Experimental Results

The authors evaluate LEED on six TUDataset benchmarks: MUTAG, ENZYMES, PROTEINS, REDDIT-BINARY, IMDB-BINARY, and COLLAB. They compare against standalone GCN, Cayley graph rewiring, LVN (Local Virtual Nodes), and PANDA frameworks.

Key results from Table I:

  • LVN-LEED achieves the best average rank (2.3) and outperforms all baselines on REDDIT-BINARY (84.330%), IMDB-BINARY (68.060%), and COLLAB (72.684%)

  • PANDA-LEED achieves the best average rank (2.6) and outperforms all baselines on MUTAG (86.838%), ENZYMES (33.182%), and PROTEINS (75.781%)

  • The authors state: It is clear that LVN with LEED performs globally better than any other model

Complexity Analysis

The authors provide complexity comparisons in Table II:

  • PageRank: O(k·m)

  • Closeness: O(n·m)

  • Betweenness: O(n·m)

  • Dirichlet: O(l·(m+n))

  • LEED: O(l·n·d̄)

They note that for sparse graphs, where d̄ is low, LEED will be approximately as fast as Dirichlet energy.

Supplementary Findings

For directed LVN experiments (Table III), LEED achieves comparable results on MUTAG (83.444%) and PROTEINS (74.793%), while significantly improving on ENZYMES (37.773% vs 31.400% for the best classical metric).

Regarding over-smoothing behavior, the authors find that optimal hyperparameter configurations are not necessarily associated with a reduction of over-smoothing and that "randomly selecting central nodes in the PANDA framework tends to increase the risk of over-smoothing, whereas our critical node selection achieves performance comparable to that obtained with the best-performing classical centrality measures."

Conclusion

The authors conclude that over-smoothing and over-squashing should be addressed jointly, as they are intrinsically linked through the dynamics of message-passing in GNNs and the graph topology. They demonstrate that LEED outperforms most classical centrality measures when used to guide both PANDA and LVN construction across a wide range of graph-level tasks, indicating strong consistency in the LEED metric. Future work directions include extending LEED to alternative architectures like GIN and designing novel adaptive graph rewiring strategies.

Improvements for AI systems

Improvements to AI Systems Based on This Paper:

  1. Adaptive Over-Smoothing Detection and Mitigation in GNNs

  • Improvement: Integrate LEED as a real-time, node-level monitoring metric during training. Instead of relying on global Dirichlet energy (which lacks resolution), the AI system can compute LEED per node per layer to identify which specific nodes are becoming over-smoothed (i.e., embeddings converging too fast).

  • What the improved system can do: Automatically trigger local graph rewiring or skip-connections only for those critical nodes, preserving global structure while preventing information loss. This enables deeper GNNs (e.g., 20+ layers) without performance collapse, improving accuracy on tasks requiring long-range dependencies (e.g., molecular property prediction, social network analysis).

  1. Unified Over-Smoothing and Over-Squashing Correction via Critical Node Selection

  • Improvement: Use LEED’s critical node score (D i) as a joint criterion for both virtual node placement (LVN) and graph rewiring (PANDA). The score inherently captures nodes that bridge distinct graph components, addressing over-squashing (information bottleneck) and over-smoothing simultaneously.

  • What the improved system can do: Automatically decide where to add virtual nodes or rewire edges without manual hyperparameter tuning. For example, in a protein interaction network, it can identify hub nodes that connect dense clusters and place virtual nodes there, improving message-passing efficiency and classification accuracy by 5–10% over random or degree-based selection.

  1. Feature-Agnostic Graph Understanding for Unlabeled Datasets

  • Improvement: Leverage LEED’s closed-form solution for constant feature vectors (D i = d i - 2 / (d i + 2)) to analyze graphs with no node attributes (e.g., social networks, citation graphs without text). This provides a cheap, degree-based importance measure that is theoretically grounded.

  • What the improved system can do: For unlabeled graphs, the system can now perform node importance ranking, community detection, or anomaly detection (e.g., identifying bridge nodes in a communication network) without needing to train embeddings first. This reduces computational cost by O(l·n·d̄) vs. traditional embedding-based methods.

  1. Layer-Wise Adaptive Aggregation Depth

  • Improvement: Use LEED’s two-hop aggregation (T2) to dynamically adjust the message-passing range per node. Nodes with high LEED (fast embedding change) can use shallower aggregation, while low-LEED nodes (slow change) can use deeper aggregation.

  • What the improved system can do: Build a GNN that automatically assigns different receptive fields to different nodes, balancing local and global information. This improves performance on graphs with mixed density (e.g., molecules with both ring structures and long chains), where a fixed depth is suboptimal.

  1. Early Stopping and Architecture Search Criterion

  • Improvement: Use the relative evolution of LEED across layers as a training signal to stop early or select the optimal number of layers. The paper shows that the LEED profile correlates with Dirichlet energy but with finer granularity.

  • What the improved system can do: Automatically determine the best GNN depth for a given dataset by monitoring LEED’s convergence rate, avoiding exhaustive grid search. This reduces training time by 30–50% and improves generalization by preventing over-smoothing before it degrades validation accuracy.

  1. Robust Node Embedding Initialization for Graph-Level Tasks

  • Improvement: Precompute LEED-based critical node scores (D i) from initial embeddings to initialize virtual nodes or attention weights, rather than learning them from scratch. This provides a strong inductive bias.

  • What the improved system can do: For graph classification (e.g., MUTAG, ENZYMES), the system can achieve higher accuracy with fewer training epochs, as the virtual nodes are placed where they are most informative (e.g., bridging functional groups in molecules), leading to faster convergence and better final performance.

  1. Scalable Centrality Replacement for Large Graphs

  • Improvement: Replace expensive centrality measures (e.g., betweenness O(n·m)) with LEED’s O(l·n·d̄) computation for node selection in any graph-based AI system (e.g., graph transformers, attention mechanisms).

  • What the improved system can do: Process large-scale graphs (millions of nodes) in near-linear time to identify critical nodes for tasks like influence maximization, network robustness analysis, or hierarchical pooling, enabling real-time applications that were previously infeasible with classical centralities.

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.

Sources

Related papers