🤖 machine learning

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

This paper proposes LEED (Local Embedding Evolution Distance), a novel node-level metric that quantifies over-smoothing in Graph Neural Networks to enable fine-grained analysis of representation dynamics and guide an efficient virtual node selection strategy for mitigating over-squashing.

Original authors: Killian Cressant, Pedro B. Velloso

Published 2026-08-11

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Killian Cressant, Pedro B. Velloso

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a group of friends how to solve a mystery by having them whisper clues to one another. This is essentially how Graph Neural Networks (GNNs) work. In the world of computer science, a "graph" is just a map of connections—like a social network where people are dots and friendships are lines. GNNs are smart programs that learn by passing information along these lines, layer by layer, to understand the whole picture.

However, this whispering game has two tricky glitches. First, there's "over-smoothing." If you whisper a secret around a large circle too many times, everyone eventually hears the exact same thing, and the unique details get washed out until no one can tell who said what. Second, there's "over-squashing." Imagine trying to squeeze a huge, complex story into a tiny, narrow hallway to get it to the other side; the information gets crushed, distorted, or lost entirely because the path is too crowded or too long. Scientists have been trying to fix these glitches for years, often by adding "virtual nodes"—imaginary super-friends who can instantly connect distant parts of the group to speed things up. But the big question has always been: Which friends should get these superpowers? Usually, researchers just guessed or tried a bunch of different rules to see what worked best.

This paper introduces a new, clever tool called LEED (Local Embedding Evolution Distance) to solve that guessing game. Think of LEED as a super-sensitive microphone that listens to exactly how each individual friend's "voice" (their data representation) changes as the message travels through the group. Instead of just looking at the whole crowd to see if everyone sounds the same, LEED zooms in on every single person to see who is getting lost in the noise or who is stuck in a bottleneck. The authors found that by using LEED to pick the most important "critical nodes" to become virtual super-friends, they could fix the squashing problem without accidentally causing the smoothing problem. Their experiments on six different datasets showed that this new method helps the computer learn better and faster than the old guessing games, proving that listening closely to the details of the conversation is the key to fixing the whole system.

The Story of the Whispering Network

Let's dive deeper into the magic of these digital networks. You can think of a Graph Neural Network like a massive game of "Telephone," but instead of a silly song, the players are passing around complex data about a molecule, a citation, or a social connection. In a standard game, if you pass a message through too many people, it gets garbled. In a GNN, if you pass information through too many layers, the unique features of each node (the dots) start to blur together until they all look identical. This is over-smoothing. It's like if everyone in your class started wearing the exact same uniform and saying the exact same catchphrase; you wouldn't be able to tell your best friend from a stranger anymore.

Then there's the opposite problem: over-squashing. This happens when a message has to travel from one side of a huge graph to the other, but the path is narrow. Imagine trying to send a 50-page letter through a tiny mail slot that can only fit a postcard. The information gets crammed, squished, and distorted. In graph terms, this happens at "bottlenecks"—places where a single node or a few edges have to carry too much traffic from distant parts of the network.

To fix these issues, scientists have tried adding virtual nodes. Think of these as "super-connectors" or "teleporters." If you add a magical friend who is connected to everyone, the message doesn't have to travel through the long, winding path of the original group; it can just hop to the teleporter and jump to the destination. This fixes the squashing problem by shortening the distance. But here's the catch: if you pick the wrong person to be the teleporter, or if you add too many, you might accidentally make the "over-smoothing" problem worse. You might make everyone sound the same too quickly.

For a long time, researchers picked these special nodes using old-school rules, like "who has the most friends?" (Degree) or "who is on the most shortest paths?" (Betweenness). They would try a bunch of these rules, run the experiment, and see which one gave the best score. It was a bit like trying to find the best key for a lock by testing every key in a giant keychain without knowing which one actually fits.

Enter LEED: The Detective's Magnifying Glass

The authors of this paper, Killian Cressant and Pedro B. Velloso, decided to stop guessing. They built a new metric called LEED (Local Embedding Evolution Distance). Instead of looking at the whole graph to see if things are getting blurry, LEED acts like a magnifying glass for every single node. It tracks exactly how a node's "embedding" (its internal representation of itself) evolves as it passes through each layer of the network.

Here is the clever part: LEED doesn't just measure the distance between a node and its neighbors; it measures the minimum distance to its neighbors after a transformation that mimics how the network processes information. It's like checking if a student's answer is getting too similar to their neighbor's answer, but specifically looking at the closest match to see if they are starting to copy each other too much.

By doing this, LEED can spot two things at once:

Who is getting lost? (Nodes that are becoming too similar to everyone else, indicating over-smoothing).
Who is the bottleneck? (Nodes that are struggling to pass information, indicating over-squashing).

The paper argues that these two problems are actually two sides of the same coin. You can't just fix one without thinking about the other. If you add too many connections to fix the squashing, you might smooth everything out too fast. LEED helps find the "critical nodes"—the specific people who need to become virtual nodes to fix the flow without breaking the uniqueness of the group.

The Experiment: Testing the New Strategy

To see if their new detective tool actually worked, the authors ran a series of experiments. They took six different datasets (like MUTAG, ENZYMES, and PROTEINS, which are collections of chemical structures and biological data) and tested their method against the old ways of picking nodes.

They compared their approach, which uses LEED to pick the critical nodes, against two popular existing methods:

LVN (Local Virtual Nodes): A method that adds small groups of virtual nodes to the graph.
PANDA: A method that expands the size of certain nodes to hold more information.

In the old days, these methods had to try out different "centrality" rules (like Degree, PageRank, Betweenness) to see which one worked best for each dataset. It was a trial-and-error process. The authors replaced all those old rules with just LEED.

The results were promising. In their tests, the LVN-LEED combination achieved the best average performance across the datasets. For example, on the MUTAG dataset, the standard GCN (the basic model) got an accuracy of about 74.75%, while the LVN-LEED model reached 83.33%. On ENZYMES, the improvement was even more noticeable, jumping from 29.08% to 31.09% (and even higher in some specific tests).

The authors noted that while the old methods sometimes worked well, they required a lot of tuning. LEED, on the other hand, worked consistently well without needing to test a dozen different rules. It suggested that by focusing on the local evolution of the data, they could find the right nodes to help the network "breathe" better.

What the Paper Says (and Doesn't Say)

It is important to understand what this paper actually proves. The authors show that LEED is a more informative diagnostic tool than the old global energy measures (like Dirichlet energy) because it can see the local details. They also demonstrate that using LEED to pick nodes leads to better performance in their specific experiments compared to using random selection or standard centrality measures.

However, the paper is careful not to claim that this is a magic bullet for every problem. They explicitly state that their results are based on simulations and experiments on specific datasets. They found that for some datasets without clear node features (like COLLAB), the improvement wasn't as dramatic, and in one case with the PANDA framework, the performance dipped slightly, though not significantly. This suggests that while LEED is a powerful new tool, it might need to be tweaked depending on the type of data you are looking at.

The authors also point out that they focused on a specific type of network architecture (GCN) and that there is still a lot to explore. They suggest that future work could look at how LEED works with other types of networks or how it could be used to design even smarter ways to rewire graphs. They don't claim to have solved the over-smoothing problem forever; rather, they have offered a new, sharper lens to see it and a better way to fix it.

The Takeaway

In the end, this paper is about listening better. For years, scientists tried to fix the "Telephone" game of Graph Neural Networks by guessing which friends needed superpowers. The authors of this paper built a new tool, LEED, that listens to every single whisper to see exactly where the message is getting lost or where everyone is starting to sound the same. By using this tool to pick the right "virtual nodes," they showed that the network can learn faster and more accurately. It's a reminder that sometimes, to fix a big problem, you don't need a bigger hammer; you just need a better way to look at the details.

Technical Summary: LEED – Local Embedding Evolution Distance for Over-smoothing Estimation and Virtual Node Selection

Problem Statement
Graph Neural Networks (GNNs) face two fundamental, often antagonistic, limitations: over-smoothing and over-squashing. Over-smoothing occurs when repeated message-passing causes node representations to converge to indistinguishable states, erasing local signal. Over-squashing arises when structural bottlenecks force the compression of long-range information into limited embedding capacities, distorting or discarding critical data.

Existing solutions often address these issues separately. Over-smoothing is typically monitored using global metrics like Dirichlet energy, which lack the resolution to analyze node-level behavior or guide architectural improvements. Conversely, mitigating over-squashing via graph rewiring (e.g., adding virtual nodes) often relies on empirically testing multiple classical centrality measures (Degree, Betweenness, PageRank) to identify "critical" nodes, a process that is computationally inefficient and lacks a principled theoretical basis. Furthermore, current methods struggle to balance the trade-off where structural modifications to alleviate over-squashing (e.g., increasing connectivity) may inadvertently exacerbate over-smoothing.

Methodology
The authors propose LEED (Local Embedding Evolution Distance), a novel metric designed to quantify over-smoothing at the node level while simultaneously guiding the selection of critical nodes for graph rewiring.

Local Embedding Evolution Distance (LEED):
Unlike Dirichlet energy, which aggregates differences across all edges, LEED focuses on the minimum distance between a node's embedding and its neighbors after a transformation. It tracks the evolution of individual node embeddings across layers using a 2-hop neighborhood aggregation.
- Transformation: LEED applies a mean evolution function, $T_m$ , which mimics the dynamics of GCN message passing. For 2-hops, this involves weighted aggregation of neighbors' embeddings, incorporating self-loops and degree-based corrections.
- Metric Definition: For a node $i$ , the local score $\ell(x_i^{(k)})$ is defined as the minimum squared Euclidean distance between the transformed embedding of $i$ and its neighbors:
  $\ell(x_i^{(k)}) = \min_{j \in N_i} \|T_m(x_i^{(k)}) - T_m(x_j^{(k)})\|^2_2$
- Global Correlation: The authors prove that the sum of these local scores, $L(X^{(k)})$ , is bounded by the global Dirichlet energy $E(X^{(k)})$ , ensuring that LEED preserves global over-smoothing trends while offering granular, node-level insights.
Critical Node Selection:
LEED is utilized as a unified criterion to identify critical nodes for graph rewiring strategies, specifically Local Virtual Nodes (LVN) and PANDA (which expands node embedding widths).
- Instead of testing multiple centrality metrics, the method calculates a distance score $D_i$ based on the deviation of a node's initial embedding (or degree, in feature-less graphs) from its 2-hop neighborhood evolution.
- Nodes with the highest scores (top- $k$ quantile) are selected as critical nodes. These nodes are deemed most influential in information propagation and representation learning, serving as anchors for adding virtual nodes or expanding embedding dimensions.

Key Contributions

Novel Local Metric: Introduction of LEED, a node-level metric that captures heterogeneous over-smoothing patterns invisible to global energy-based measures.
Unified Framework: A single metric that addresses both over-smoothing (via diagnostics) and over-squashing (via critical node selection for rewiring), eliminating the need for separate heuristics.
Principled Node Selection: Replaces the empirical testing of multiple classical centrality measures with a single, theoretically grounded criterion derived from embedding dynamics.
Efficiency: Demonstrates that LEED offers comparable computational complexity to Dirichlet energy for sparse graphs while providing significantly more informative diagnostics.

Experimental Results
The authors evaluated LEED on six benchmark datasets (MUTAG, ENZYMES, PROTEINS, REDDIT-BINARY, IMDB-BINARY, COLLAB) using standard GCN architectures.

Performance: The LVN-LEED approach achieved the best average rank (2.3) across all datasets, outperforming standalone GCNs, Cayley graph rewiring, standard LVN (using classical centrality), and PANDA.
Robustness: LEED demonstrated effectiveness even on datasets without intrinsic node features (e.g., COLLAB), where it relies on degree-based approximations.
Over-smoothing Control: Experiments indicated that selecting critical nodes via LEED does not necessarily increase the risk of over-smoothing compared to random selection, and often matches the performance of the best classical centrality measures without the associated hyperparameter tuning.
Complexity: LEED maintains a complexity of $O(l \cdot n \cdot \bar{d})$ , making it efficient for sparse graphs comparable to Dirichlet energy.

Significance and Claims
The paper claims that LEED represents a significant step toward jointly addressing the dual challenges of over-smoothing and over-squashing. By shifting the focus from global regularization to local embedding dynamics, the authors argue that over-smoothing should be viewed fundamentally as a graph connectivity problem rather than solely a message-passing issue.

The significance of this work lies in its ability to:

Provide fine-grained diagnostics that reveal heterogeneous over-smoothing patterns.
Offer a parameter-free, principled strategy for selecting critical nodes in graph rewiring, removing the dependency on dataset-specific centrality tuning.
Improve GNN performance across diverse graph-level tasks by effectively mitigating over-squashing while maintaining control over over-smoothing.

The authors conclude that while their current evaluation is restricted to GCN architectures, the framework of local over-smoothing analysis opens promising avenues for adaptive graph rewiring strategies in future research.

The Story of the Whispering Network

Enter LEED: The Detective's Magnifying Glass

The Experiment: Testing the New Strategy

What the Paper Says (and Doesn't Say)

The Takeaway

More like this