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

• URL: http://arxiv.org/abs/2608.09596v1
• Date: Mon, 10 Aug 2026 13:30:46 GMT
• Title: LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN
• Abstract summary: Graph Neural Networks (GNNs) suffer from two fundamental limitations: over-smoothing and over-squashing.<n>We propose LEED (Local Embedding Evolution Distance), a novel local metric that quantifies over-smoothing.<n>By operating at the node level, LEED enables fine-grained analysis of representation dynamics during training.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily [10.0426843232642]
  We develop a theoretical framework that links local structural and label characteristics to information propagation dynamics.<n>We propose a novel adaptive-depth GNN architecture that dynamically selects node-specific aggregation depths.<n>Our method seamlessly adapts to both homophilic and heterophilic patterns within a unified model.
  arXiv  Detail & Related papers  (2025-11-10T01:37:51Z)
• Virtual Nodes Improve Long-term Traffic Prediction [9.125554921271338]
  This study introduces a novel framework that incorporates virtual nodes, which are additional nodes added to the graph and connected to existing nodes.<n>Our proposed model incorporates virtual nodes by constructing a semi-adaptive adjacency matrix.<n> Experimental results demonstrate that the inclusion of virtual nodes significantly enhances long-term prediction accuracy.
  arXiv  Detail & Related papers  (2025-01-17T09:09:01Z)
• Diss-l-ECT: Dissecting Graph Data with Local Euler Characteristic Transforms [13.608942872770855]
  We introduce the Local Euler Characteristic Transform ($ell$-ECT) to enhance expressivity and interpretability in graph representation learning.<n>Our method exhibits superior performance compared to standard Graph Neural Networks (GNNs) on a variety of node-classification tasks.
  arXiv  Detail & Related papers  (2024-10-03T16:02:02Z)
• Spatiotemporal Graph Learning with Direct Volumetric Information Passing and Feature Enhancement [62.91536661584656]
  We propose a dual-module framework, Cell-embedded and Feature-enhanced Graph Neural Network (aka, CeFeGNN) for learning.<n>We embed learnable cell attributions to the common node-edge message passing process, which better captures the spatial dependency of regional features.<n>Experiments on various PDE systems and one real-world dataset demonstrate that CeFeGNN achieves superior performance compared with other baselines.
  arXiv  Detail & Related papers  (2024-09-26T16:22:08Z)
• GNUMAP: A Parameter-Free Approach to Unsupervised Dimensionality Reduction via Graph Neural Networks [0.8192907805418583]
  We show thatMAP consistently outperforms existing state-of-the-art GNN embedding methods in a variety of contexts. We introduce a robust and parameter-free method for unsupervised node representation learning that merges the traditional UMAP approach with the expressivity of the GNN framework.
  arXiv  Detail & Related papers  (2024-07-30T22:58:23Z)
• On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems [28.351050664151536]
  A common problem in Message-Passing Neural Networks is oversquashing -- the limited ability to facilitate effective information flow between distant nodes.<n>This paper introduces a novel perspective to address oversquashing, leveraging systems properties of global and local non-dissipativity.<n>We present SWAN, a uniquely parameterized GNN model with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity.
  arXiv  Detail & Related papers  (2024-05-02T05:23:58Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. The sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. We propose an online propagation framework and two novel node-adaptive propagation methods.
  arXiv  Detail & Related papers  (2023-10-17T05:03:00Z)
• A Topological Perspective on Demystifying GNN-Based Link Prediction Performance [72.06314265776683]
  Topological Concentration (TC) is based on the intersection of the local subgraph of each node with the ones of its neighbors. We show that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density. We propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the complexity.
  arXiv  Detail & Related papers  (2023-10-06T22:07:49Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• DeHIN: A Decentralized Framework for Embedding Large-scale Heterogeneous Information Networks [64.62314068155997]
  We present textitDecentralized Embedding Framework for Heterogeneous Information Network (DeHIN) in this paper. DeHIN presents a context preserving partition mechanism that innovatively formulates a large HIN as a hypergraph. Our framework then adopts a decentralized strategy to efficiently partition HINs by adopting a tree-like pipeline.
  arXiv  Detail & Related papers  (2022-01-08T04:08:36Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.