Cover Image

On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Chehreghani, Mostafa Haghir
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph Neural Networks in Multi-Omics Cancer Research: A Structured Survey
by: Zohari, Payam, et al.
Published: (2025)

Strong Transitivity Relations and Graph Neural Networks
by: Mohamadi, Yassin, et al.
Published: (2024)

Content Augmented Graph Neural Networks
by: Nasrabadi, Fatemeh Gholamzadeh, et al.
Published: (2023)

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
by: Hossen, Md Sazzad, et al.
Published: (2026)

Neighborhood-Order Learning Graph Attention Network for Fake News Detection
by: Lakzaei, Batool, et al.
Published: (2025)

A Decision-Based Heterogenous Graph Attention Network for Multi-Class Fake News Detection
by: Lakzaei, Batool, et al.
Published: (2025)

LOSS-GAT: Label Propagation and One-Class Semi-Supervised Graph Attention Network for Fake News Detection
by: Lakzaei, Batool, et al.
Published: (2024)

Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning
by: Arnaiz-Rodriguez, Adrian, et al.
Published: (2025)

Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP
by: Lischka, Attila, et al.
Published: (2024)

Shift of Pairwise Similarities for Data Clustering
by: Chehreghani, Morteza Haghir
Published: (2021)

Anchor-based oversampling for imbalanced tabular data via contrastive and adversarial learning
by: Mohammadi, Hadi, et al.
Published: (2025)

Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
by: Rydin, Filip, et al.
Published: (2025)

Are We Measuring Oversmoothing in Graph Neural Networks Correctly?
by: Zhang, Kaicheng, et al.
Published: (2025)

A Benchmark Dataset for Graph Regression with Homogeneous and Multi-Relational Variants
by: Samoaa, Peter, et al.
Published: (2025)

Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
by: Attali, Hugo, et al.
Published: (2025)

An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
by: Aronsson, Linus, et al.
Published: (2025)

Heterophily-Aware Fair Recommendation using Graph Convolutional Networks
by: Gholinejad, Nemat, et al.
Published: (2024)

Oversmoothing Alleviation in Graph Neural Networks: A Survey and Unified View
by: Jin, Yufei, et al.
Published: (2024)

Hierarchical Correlation Clustering and Tree Preserving Embedding
by: Chehreghani, Morteza Haghir, et al.
Published: (2020)

A GREAT Architecture for Edge-Based Graph Problems Like TSP
by: Lischka, Attila, et al.
Published: (2024)

Contrastive Matrix Completion with Denoising and Augmented Graph Views for Robust Recommendation
by: Nemati, Narges, et al.
Published: (2025)

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Neural Networks
by: Chakraborty, Biswadeep, et al.
Published: (2024)

PBiLoss: Popularity-Aware Regularization to Improve Fairness in Graph-Based Recommender Systems
by: Naeimi, Mohammad, et al.
Published: (2025)

Two-Stage Learned Decomposition for Scalable Routing on Multigraphs
by: Rydin, Filip, et al.
Published: (2026)

Bayesian Analysis of Combinatorial Gaussian Process Bandits
by: Sandberg, Jack, et al.
Published: (2023)

Analysing the Behaviour of Tree-Based Neural Networks in Regression Tasks
by: Samoaa, Peter, et al.
Published: (2024)

Oversmoothing: A Nightmare for Graph Contrastive Learning?
by: Li, Jintang, et al.
Published: (2023)

Tactical Decision Making for Autonomous Trucks by Deep Reinforcement Learning with Total Cost of Operation Based Reward
by: Pathare, Deepthi, et al.
Published: (2024)

Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models
by: Sun, Li, et al.
Published: (2025)

Multi-Objective Reinforcement Learning for Tactical Decision Making for Trucks in Highway Traffic
by: Pathare, Deepthi, et al.
Published: (2026)

Tree Ensembles for Contextual Bandits
by: Nilsson, Hannes, et al.
Published: (2024)

Cold-Start Active Correlation Clustering
by: Aronsson, Linus, et al.
Published: (2025)

Short-Range Oversquashing
by: Mishayev, Yaaqov, et al.
Published: (2025)

Temporal Graph Rewiring with Expander Graphs
by: Petrović, Katarina, et al.
Published: (2024)

Modality as Heterogeneity: Node Splitting and Graph Rewiring for Multimodal Graph Learning
by: Zhang, Yihan, et al.
Published: (2026)

Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics
by: Benoit, Alexandre, et al.
Published: (2025)

Tackling Oversmoothing in GNN via Graph Sparsification: A Truss-based Approach
by: Hossain, Tanvir, et al.
Published: (2024)

AFABench: A Generic Framework for Benchmarking Active Feature Acquisition
by: Schütz, Valter, et al.
Published: (2025)

Adaptive Long-term Embedding with Denoising and Augmentation for Recommendation
by: Akhlaghi, Zahra, et al.
Published: (2025)

Oversmoothing as Representation Degeneracy in Neural Sheaf Diffusion
by: Dönmez, Arif, et al.
Published: (2026)