RECORD
Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond
Machine Learning · Submitted 6 Sep 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our conclusive experiments highlight the effectiveness of proposed models.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Graph Neural Networks (GNNs) have emerged as one of the leading approaches for machine learning on graph-structured data. Despite their great success, critical computational challenges such as over-smoothing, over-squashing, and limited expressive power continue to impact the performance of GNNs. In this study, inspired from the time-reversal principle commonly utilized in classical and quantum physics, we reverse the time direction of the graph heat equation. The resulted reversing process yields a class of high pass filtering functions that enhance the sharpness of graph node features. Leveraging this concept, we introduce the Multi-Scaled Heat Kernel based GNN (MHKG) by amalgamating diverse filtering functions' effects on node features. To explore more flexible filtering conditions, we further generalize MHKG into a model termed G-MHKG and thoroughly show the roles of each element in controlling over-smoothing, over-squashing and expressive power. Notably, we illustrate that all aforementioned issues can be characterized and analyzed via the properties of the filtering functions, and uncover a trade-off between over-smoothing and over-squashing: enhancing node feature sharpness will make model suffer more from over-squashing, and vice versa. Furthermore, we manipulate the time again to show how G-MHKG can handle both two issues under mild conditions. Our conclusive experiments highlight the effectiveness of proposed models. It surpasses several GNN baseline models in performance across graph datasets characterized by both homophily and heterophily.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Graph Neural Networks (GNNs) have emerged as one of the leading approaches for machine learning on graph-structured data. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| s1 | Despite their great success, critical computational challenges such as over-smoothing, over-squashing, and limited expressive power continue to impact the performance of GNNs. | background 0.76 | 0.05 | 0.03 | asserted 1.00 |
| s2 | In this study, inspired from the time-reversal principle commonly utilized in classical and quantum physics, we reverse the time direction of the graph heat equation. | method 0.79 | 0.90 | 0.03 | asserted 0.97 |
| s3 | The resulted reversing process yields a class of high pass filtering functions that enhance the sharpness of graph node features. | result 0.71 | 0.91 | 0.06 | asserted 1.00 |
| s4 | Leveraging this concept, we introduce the Multi-Scaled Heat Kernel based GNN (MHKG) by amalgamating diverse filtering functions' effects on node features. | method 0.57 | 0.94 | 0.05 | asserted 1.00 |
| s5 | To explore more flexible filtering conditions, we further generalize MHKG into a model termed G-MHKG and thoroughly show the roles of each element in controlling over-smoothing, over-squashing and expressive power. | contribution 0.70 | 0.94 | 0.09 | asserted 1.00 |
| s6 | Notably, we illustrate that all aforementioned issues can be characterized and analyzed via the properties of the filtering functions, and uncover a trade-off between over-smoothing and over-squashing: enhancing node feature sharpness will make model suffer more from over-squashing, and vice versa. | result 0.54 | 0.94 | 0.51 | asserted 1.00 |
| s7 | Furthermore, we manipulate the time again to show how G-MHKG can handle both two issues under mild conditions. | method 0.57 | 0.94 | 0.12 | asserted 0.98 |
| s8 | Our conclusive experiments highlight the effectiveness of proposed models. | result 0.98 | 0.91 | 0.45 | asserted 1.00 |
| s9 | It surpasses several GNN baseline models in performance across graph datasets characterized by both homophily and heterophily. | result 1.00 | 0.90 | 0.27 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Graph Neural Networks (GNNs) have emerged as one of the leading approaches for machine learning on graph-structured data. Despite their great success, critical computational challenges such as over-smoothing, over-squashing, and limited expressive power continue to impact the performance of GNNs. In this study, inspired from the time-reversal principle commonly utilized in classical and quantum physics, we reverse the time direction of the graph heat equation. The resulted reversing process yields a class of high pass filtering functions that enhance the sharpness of graph node features. Leveraging this concept, we introduce the Multi-Scaled Heat Kernel based GNN (MHKG) by amalgamating diverse filtering functions' effects on node features. To explore more flexible filtering conditions, we further generalize MHKG into a model termed G-MHKG and thoroughly show the roles of each element in controlling over-smoothing, over-squashing and expressive power. Notably, we illustrate that all aforementioned issues can be characterized and analyzed via the properties of the filtering functions, and uncover a trade-off between over-smoothing and over-squashing: enhancing node feature sharpness will make model suffer more from over-squashing, and vice versa. Furthermore, we manipulate the time again to show how G-MHKG can handle both two issues under mild conditions. Our conclusive experiments highlight the effectiveness of proposed models. It surpasses several GNN baseline models in performance across graph datasets characterized by both homophily and heterophily.
Human review
How the literature uses it
9 arXiv papers cite this in 17 sentences
Papers citing it · 13 sentences without a confident label
Compares with it 1 paper
-
In contrast to dimension-level gating, MHKG [ref] introduces a filter-level gating strategy for modulation based on the reverse heat kernel.
A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions · Neural Diffusion Process · 0.98
Cites it as support 2 papers
-
As network depth increases, they often suffer from over-smoothing, i.e., node representations become indistinguishable, and limited receptive fields, which hinder their ability to capture long-range dependencies [ref] .
Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees · Graph and Hypergraph Neural Networks · 0.96
-
Specifically, it has been demonstrated in [ref] that, when the MPNNs dynamic is dominated by the highest eigenvalue of the graph Laplacian, namely high frequency dominant (HFD), MPNNs will sharp the node features from the beginning of the propagation, thus resulting in no OSM problem.
Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges · Empirical Open Questions · 0.99
Cites it as background 1 paper
-
Nevertheless, many attempts have been made to mitigate the OSM issue via the lens of dynamic systems [ref] , multi-scale spectral filtering [ref] as well as feature optimizations [ref] .
Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks · Related Works · 0.97
What it cites · 16 sentences without a confident label
Contests 1 paper
-
Relation to existing works Compared to the existing work [ref] that claimed both issues can not be alleviated simultaneously, our conclusion shows that once the model is HFD, it is possible to handle both issues.
On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks · Time manipulation: How to handle two issues and beyond · contest 0.79
Cites as support 2 papers
-
Recent research on GNNs dynamics [ref] suggests that to induce HFD, the weight matrix $𝐖$ must be symmetric and contain at least one negative eigenvalue.
Understanding convolution on graphs via energies · Filtering matrices control model dynamics & over-smoothing · 0.96
-
Furthermore, it is straightforward to verify that single-scale GNN [ref] may satisfy the conditions of frequency dominance described in Theorem [ref],
Semi-Supervised Classification with Graph Convolutional Networks · Filtering matrices control model dynamics & over-smoothing · 0.96
Cites as background 4 papers
-
Moreover, recent studies also attempted to mitigate both issues via graph surgery by dropping highly positive cured edges which often lead to over-smoothing issue [ref] and rewiring the communities connected with very negatively curved edges which is responsible for the over-squashing issue [ref] .
On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks · Time manipulation: How to handle two issues and beyond · 0.85
-
In terms of GNNs, we note that in general there are two types of GNNs, the spatial-based GNNs such as graph convolution network (GCN) [ref] defines the layer-wise propagation rule via the normalized adjacency matrix as [equation] where we let $𝐇^(t)$ as the feature matrix at layer $t$ with $𝐇^(0) = 𝐗 ∈ℝ^N ×c$, the input feature matrix, and $𝐖^(t)$ is the learnable weight matrix performing channel mixing.
Semi-Supervised Classification with Graph Convolutional Networks · Preliminaries · 0.87
-
Within the diverse research avenues of GNNs, one prominent aspect is to interpret GNNs via different perspectives, such as gradient flow [ref] , neural diffusion [ref] , and testing of graph isomorphism [ref] , all of which contribute to a deeper comprehension of GNNs' underlying working mechanism.
Understanding convolution on graphs via energies · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.