Unifying over-smoothing and over-squashing in graph neural networks: A
  physics informed approach and beyond
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.
Zhiqi Shao, Dai Shi, Andi Han, Yi Guo, Qibin Zhao, Junbin Gao
Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond

###### 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.

## 1 Introduction

Graph Neural Networks (GNNs) have demonstrated exceptional performance in learning the representations of graph-structured data [19, 38]. Within the diverse research avenues of GNNs, one prominent aspect is to interpret GNNs via different perspectives, such as gradient flow [11, 17], neural diffusion [31, 6], and testing of graph isomorphism [40], all of which contribute to a deeper comprehension of GNNs' underlying working mechanism. Concurrently, another trajectory in GNN's development is oriented toward addressing specific challenges. Generally, three inherent limitations in GNNs have been identified: over-smoothing [4], over-squashing [33], and limitations in expressive power [40], each of them is openly acknowledged and arises due to various aspects of GNNs and its graph data input. As such, research efforts are primarily focused on tackling these aspects to effectively address the mentioned problems. For instance, to counteract the over-smoothing phenomenon, researchers have advocated for the augmentation of feature variation by incorporating
a source term [31] or modulating the energy regularization to prevent rapid diminishment [26, 14]. To mitigate over-squashing, strategies may encompass exploring graph topology through methods such as _graph re-weighting_[27] and _graph rewiring_[33]. Lastly, enhancing the capacity to discern non-isomorphic graphs could be achieved by assigning more intricate embeddings to graph nodes [40, 36].

While many efforts have been made on these three issues, little research has been done to consider these issues in a unified manner to reveal their underlying relationships and further seeking for mitigating them via one specific GNN and an unified way. The main difficulties for this situation may be due to

* Some GNNs lack the necessary flexibility to serve as the subjects for investigating the aforementioned triad of issues in a cohesive manner.
* The pursuit of greater flexibility in GNNs in general leads to increased model complexity. Consequently, effectively exploring the roles on GNNs components on these issues becomes a formidable task.
* There's a gap in research regarding the transition between addressing over-smoothing, typically focusing on node features, and tackling over-squashing and enhancing expressive power, which often concentrate on graph topology.

In the present study, we derive inspiration from the physical reality of graph heat equation, leading to a novel perspective that examines the propagation of node features in the reverse direction of time. We demonstrate that many prevailing GNNs can invert the feature propagation process, transitioning from smoothing to sharpening effects, and vice versa. Accordingly, we propose a Multi-Scale Heat Kernel GNN (MHKG) that propagates node features via the balance between smoothing and sharpening effects induced by the low and high pass spectral filtering functions generated from the heat and reverse heat kernels. Furthermore, we generalize the MHKG into a more flexible model, referred to as G-MHKG, and provide a comprehensive examination of the components within G-MHKG that regulate over-smoothing, over-squashing and expressive power. Notably, by utilizing G-MHKG as an analytical tool and examining the properties of the associated filtering functions, we uncover a trade-off between over-squashing and over-smoothing in the graph spectral domain. This relationship is revealed under mild conditions on the filtering functions, offering fundamental insights between these issues. Lastly, we manipulate the time again in G-MHKG to show that its capability of sufficiently handling both issues for heterophily graphs and it is impossible to achieve the same goal for homophily graphs.

Contribution and OutlineOur main goal is to illustrate and verify the underlying relationship between aforementioned issues via our proposed model inspired by the time reversal principle from physics. In addition, we aim to show how our proposed model can handle these issues in a unified manner. In Section 3, we explore the link between graph filtering functions and solutions of a class of ordinary differential equations (ODEs) on graph node features. This connection propels the introduction of two multi-scale heat kernel based models: MHKG and the generalized MHKG (G-MHKG). In Section 4 we show how the filtering matrices in our model control the energy dynamics of node features, thereby effectively addressing the over-smoothing challenge. In Section 5, we demonstrate the weight matrix in G-MHKG determines the model's expressive power and over-squashing. More importantly, in Section 6 and 7 we show there is trade-off between over-smoothing
and over-squashing. We also prove that it is impossible to sufficiently handle both two issues for homophily graphs and for heterophily graphs G-MHKG can handle these issues by a simple manipulation of time. We verify our theoretical claims via comprehensive empirical studies in Section 8.

## 2 Preliminaries

Graph basics and GNNsTo begin, we let \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with nodes set \(\mathcal{V}=\{v_{1},v_{2},\cdots,v_{N}\}\) of total \(N\) nodes and edge set \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\). We also denote the graph adjacency matrix as \(\mathbf{A}\in\mathbb{R}^{N\times N}\). In addition, we consider the symmetric normalized adjacency matrix as \(\widehat{\mathbf{A}}=\mathbf{D}^{-1/2}(\mathbf{A}+\mathbf{I})\mathbf{D}^{-1/2}\) where \(\mathbf{D}\) is the diagonal degree matrix, with the \(i\)-th diagonal entry given by \(d_{i}=\sum_{j}a_{ij}\), the degree of node \(i\). The normalized graph Laplacian is given by \(\widehat{\mathbf{L}}=\mathbf{I}-\widehat{\mathbf{A}}\). We further let \(\rho_{\widehat{\mathbf{L}}}\) denote the largest eigenvalue (also called the highest frequency) of \(\widehat{\mathbf{L}}\). 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) [20] defines the layer-wise propagation rule via the normalized adjacency matrix as

\[\mathbf{H}^{(t)}=\sigma\big{(}\widehat{\mathbf{A}}\mathbf{H}^{(t-1)}\mathbf{W }^{(t)}\big{)}, \tag{1}\]

where we let \(\mathbf{H}^{(t)}\) as the feature matrix at layer \(t\) with \(\mathbf{H}^{(0)}=\mathbf{X}\in\mathbb{R}^{N\times c}\), the input feature matrix, and \(\mathbf{W}^{(t)}\) is the learnable weight matrix performing channel mixing. On the other hand, spectral GNNs such as ChebyNet [10] perform spectral filtering on the spectral domain of the graph as

\[\mathbf{H}^{(t)}=\sigma\left(\mathbf{U}g_{\theta}(\mathbf{\Lambda})\mathbf{U}^ {\top}\mathbf{H}^{(0)}\right), \tag{2}\]

where \(g_{\theta}(\mathbf{\Lambda})\) serves as the filtering function on normalized Laplacian, which utilizes an eigendecomposition \(\widehat{\mathbf{L}}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{\top}\) and \(\mathbf{U}^{\top}\mathbf{h}\) is known as the Fourier transform of a graph signal \(\mathbf{h}\in\mathbb{R}^{N}\). In this paper, we let \(\{(\lambda_{i},\mathbf{u}_{i})\}_{i=1}^{N}\) be the set of eigenvalue and eigenvector pairs of \(\widehat{\mathbf{L}}\) where \(\mathbf{u}_{i}\) are the column vectors of \(\mathbf{U}\).

Graph heat kernelGeneralizing from the so-called heat equation defined on a manifold, one can define graph heat equation as \(\frac{\partial\mathbf{H}^{(t)}}{\partial t}=-\widehat{\mathbf{L}}\mathbf{H}^{ (t)}\), in which \(\mathbf{H}^{(t)}\) is the feature representation at a specific iteration time \(t\). The solution of the graph heat equation, denoted as \(\mathbf{H}^{(t)}\), is given by \(\mathbf{H}^{(t)}=\mathrm{e}^{-t\widehat{\mathbf{L}}}\mathbf{H}^{(0)}\) with \(\mathbf{H}^{(0)}=\mathbf{X}\) as the initial condition. It is well-known that the application of Euler discretization leads to the propagation of the linear GCN models [20, 37] and this process is with the name of Laplacian smoothing [8]. The characteristic of the solution is indeed governed by the so-called Heat Kernel, denoted by \(\mathbf{K}_{t}=\mathrm{e}^{-t\widehat{\mathbf{L}}}\). The heat kernel defines a continuous-time random walk, and defines a semi-group, i.e., \(\mathbf{H}^{(t+s)}=\mathbf{H}^{(t)}\cdot\mathbf{H}^{(s)}\) for any \(t,s\geq 0\), and \(\lim_{t\rightarrow\infty}\mathbf{H}^{(t)}=\mathbf{I}\)[8]. This fact indicates non-distinguishment for the nodes with same degrees, known as over-smoothing. We included a more detailed discussion on both heat operator and heat kernel in Appendix A.1

## 3 Turning Smoothing to Sharpening
We now delve deeper into the graph heat kernel \(\mathbf{K}_{t}\). At a specific time \(t\), if one considers \(t\) is flowed at integer interval, then \(\mathbf{H}^{(t)}=\mathrm{e}^{-t\widehat{\mathbf{L}}}\mathbf{H}^{(0)}\) can be interpreted as a linear diffusion (i.e., \(\mathrm{e}^{-\widehat{\mathbf{L}}}\)) on \(\mathbf{H}^{(0)}\) repeated for \(t\) times. Consequently, at each step, one can treat \(\mathrm{e}^{-\widehat{\mathbf{L}}}\) as a low pass filtering function (_monotonically decreasing_) on the graph spectra. More generally, one can assign one function \(f\) onto \(\widehat{\mathbf{L}}\) to build a class of ODEs with the form of \(\frac{\partial\mathbf{H}^{(t)}}{\partial t}=-f(\widehat{\mathbf{L}})\mathbf{H} ^{(t)}\) and, similar to the basic heat equation, we can consider the generalized heat kernel \(\widehat{\mathbf{K}}_{t}=\mathrm{e}^{-tf(\widehat{\mathbf{L}})}\). We note that in the sequel, \(f(\widehat{\mathbf{L}})\) serve as a filtering function (i.e., polynomial or analytic functions) acting element-wisely on the eigenvalues of \(\widehat{\mathbf{L}}\), that is \(f(\widehat{\mathbf{L}})=\mathbf{U}f(\mathbf{\Lambda})\mathbf{U}^{\top}\).

A physical interpretation of the aforementioned class of ODEs suggests that heat flows in a constant direction and speed. This aligns with the _second law of thermodynamics_, indicating an inevitable evolution of the heat distribution in an isolated system, leading to what is known as _thermal equilibrium_. In analogy to GNNs, such phenomenon indicates all node features eventually become equal to each other, typically known as the over-smoothing issue. Together with the recent challenge on fitting GNNs to the so-called heterophily graphs, GNNs are preferred to produce a mixed dynamic, involving not only smoothing but also sharpening the features of connected nodes with different labels. Therefore, **we wish to turn the diffusion into a reverse direction** which is equivalent to providing external (anti)-force to the system and expect to achieve a fusion of heat in certain areas of the system while allowing diffusion in others during each evolution step. Since for any given \(f\) on \(\widehat{\mathbf{L}}\), one can induce another system that produces reverse process by assigning a negative sign before \(f\). Accordingly, one can obtain a reverse filtering effect once the diffusion direction is turned. Additionally, if we further require the filtering process \(\mathcal{F}:\mathbb{R}^{N\times c}\rightarrow\mathbb{R}^{N\times c}\) such that \(\mathcal{F}(\mathbf{H})=\mathrm{e}^{-tf(\widehat{\mathbf{L}})}\mathbf{H}^{(0)}\) to be bijective 1, then by replacing \(t\) to the \(-t\), one can recover \(\mathbf{H}^{(0)}\) from \(\mathbf{H}^{(t)}\). We note that, in this case, the propagation and recovery of \(\mathbf{H}^{(0)}\) is aligned with those physical variables (i.e., electric potential, energy density of the electromagnetic field) that are unchanged through inverse time operators in both classic and quantum mechanics. Figure. 1 shows how graph diffusion smooths the node feature and reverse diffusion makes features more distinct. With this understanding, we next show how the novel heat kernel GCN is constructed.

Footnote 1: Other requirements such as homeomorphism or isomorphism can also be applied.

### Multi-scale Heat Kernel GCN (Mhkg)

Following by the idea that at each discrete time step, i.e., from \(\ell-1\) to \(\ell\), the heat kernel based GCN model shall possess mixed dynamic (smoothing & sharpening) on node features. We thus propose the multi-scale heat kernel GCN (MHKG) as:

\[\mathbf{H}^{(\ell)}=\mathbf{U}\mathrm{diag}(\theta_{1})\mathbf{\Lambda}_{1} \mathbf{U}^{\top}\mathbf{H}^{(\ell-1)}\mathbf{W}^{(\ell-1)}+\mathbf{U} \mathrm{diag}(\theta_{2})\mathbf{\Lambda}_{2}\mathbf{U}^{\top}\mathbf{H}^{( \ell-1)}\mathbf{W}^{(\ell-1)}, \tag{3}\]

in which \(\mathrm{diag}(\theta_{1})\) and \(\mathrm{diag}(\theta_{2})\) are learnable filtering matrices with \(\mathbf{\Lambda}_{1}=-f(\mathbf{\Lambda})=\mathrm{diag}(\{\mathrm{e}^{-f( \lambda_{i})}\}_{i=1}^{N})\) and \(\mathbf{\Lambda}_{2}=f(\mathbf{\Lambda})=\mathrm{diag}(\{\mathrm{e}^{f( \lambda_{i})}\}_{i=1}^{N})\). Referring to the previous note on \(f\), one can denote \(f_{\theta}(\widehat{\mathbf{L}})=\mathbf{U}\mathrm{diag}(\theta_{1})\mathbf{U} ^{\top}\mathbf{H}^{(\ell-1)}\).

Figure 1: Top: The evolution of the node feature of diffusion (smoothing) process (i.e., from distinct features to over-smoothing). Bottom: the reverse diffusion (sharpening) process (i.e., from nearly identical to distinct node features).
\(\mathbf{U}\mathrm{diag}(\theta)f(\mathbf{\Lambda})\mathbf{U}^{\top}\).

Beyond time reversal: an even more general caseIn light of the construction of MHKG, one can consider a more generalized model with more flexible choice of dynamics as:

\[\frac{\partial\mathbf{H}^{(t)}}{\partial t}=f(\widehat{\mathbf{L}})\mathbf{H}^{( t)},\quad\frac{\partial\mathbf{H}^{(t)}}{\partial t}=g(\widehat{\mathbf{L}}) \mathbf{H}^{(t)}, \tag{4}\]

We note that for simplicity reasons, in this paper we only consider two fixed dynamic on \(\mathbf{H}\) and the conclusion we provided can be easily generalized to the multiple dynamic cases. With simple discretization, the corresponding GNN induced from Eq. (4) is:

\[\mathbf{H}^{(\ell)} =f_{\theta_{1}}(\widehat{\mathbf{L}})\mathbf{H}^{(\ell-1)} \mathbf{W}^{(\ell-1)}+g_{\theta_{2}}(\widehat{\mathbf{L}})\mathbf{H}^{(\ell- 1)}\mathbf{W}^{(\ell-1)}\] \[=\mathbf{U}\mathrm{diag}(\theta_{1})\mathrm{e}^{f(\mathbf{ \Lambda})}\mathbf{U}^{\top}\mathbf{H}^{(\ell-1)}\mathbf{W}^{(\ell-1)}+ \mathbf{U}\mathrm{diag}(\theta_{2})\mathrm{e}^{g(\mathbf{\Lambda})}\mathbf{U} ^{\top}\mathbf{H}^{(\ell-1)}\mathbf{W}^{(\ell-1)}. \tag{5}\]

We named this generalized model as G-MHKG. It is not difficult to verify that G-MHKG is a general form of various GNN models. The simplest case one can obtain is to set \(\theta_{2}=\mathbf{0}_{N}\) and \(\mathrm{e}^{f(\mathbf{\Lambda})}=\mathrm{e}^{-\xi\mathbf{\Lambda}}\), where \(\xi\in\mathbb{R}\) is a constant or learnable coefficient, we recover the GraphHeat proposed in [39]. If we let \(g(\mathbf{\Lambda})=\mathbf{0}_{N\times N}\), and \(\theta_{2}=\mathbf{c}_{N}\), where \(\mathbf{c}_{N}\) as an \(N\)-dimensional vector with arbitrary constant as \(c\), then the model is equivalent to GRAND++ [32] with a layer dependent source term, see Appendix B for more detailed illustrations. In the following sections, we show the roles of \(\theta\) and \(\mathbf{W}\) in controlling the three aforementioned issues of GNNs.

## 4 Filtering matrices control model dynamics & over-smoothing

In this section, we illustrate the role of the filtering matrices, i.e., \(\mathrm{diag}(\theta_{1})\) and \(\mathrm{diag}(\theta_{2})\), in G-MHKG control model's energy dynamic and how a controllable energy dynamic affects model's adaption on homophily and heterophily graphs. For the simplicity of the analysis we further assume that \(f(\cdot)\) and \(g(\cdot)\) to be _monotonically decrease/increase_ in the spectral domain of the graph so that they can be considered as low/high pass filtering functions. We note that this assumption is aligned with the settings in many recent works such as [44, 23, 22] and the conclusion we represent can be easily applied to MHKG which is a special version of G-MHGK. To quantify model's energy dynamics, we consider the Dirichlet energy of the node features \(\mathbf{H}\), defined by \(\mathbf{E}(\mathbf{H})=\mathrm{Tr}(\mathbf{H}^{\top}\widehat{\mathbf{L}} \mathbf{H})\). It is well-known that Dirichlet energy becomes \(0\) when the model encounters over-smoothing issue. To represent such asymptotic energy behavior, [11, 17, 29] consider a general dynamic as \(\mathbf{\dot{H}}^{(t)}=\mathrm{G}NN_{\theta}(\mathbf{H}^{(t)},t)\), with \(\mathrm{G}NN_{\theta}(\cdot)\) as an arbitrary GNN function characterising its behavior by low/high-frequency-dominance (L/HFD).

**Definition 1** ([11]).: \(\mathbf{\dot{H}}^{(t)}=\mathrm{G}NN_{\theta}(\mathbf{H}^{(t)},t)\) is Low-Frequency-Dominant (LFD) if \(\mathbf{E}\big{(}\mathbf{H}^{(t)}/\|\mathbf{H}^{(t)}\|\big{)}\to 0\) as \(t\to\infty\), and is High-Frequency-Dominant (HFD) if \(\mathbf{E}\big{(}\mathbf{H}^{(t)}/\|\mathbf{H}^{(t)}\|\big{)}\to\rho_{\widehat{ \mathbf{L}}}/2\) as \(t\to\infty\), where \(\rho_{\widehat{\mathbf{L}}}\) stands for the largest eigenvalue of \(\widehat{\mathbf{L}}\).

**Lemma 1** ([11]).: _A GNN model is LFD (resp. HFD) if and only if for each \(t_{j}\to\infty\), there exists a sub-sequence indexed by \(t_{j_{\kappa}}\to\infty\) and \(\mathbf{H}_{\infty}\) such that \(\mathbf{H}_{j_{\kappa}}^{(t)}/\|\mathbf{H}_{j_{\kappa}}^{(t)}\|\to\mathbf{H}_{\infty}\) and \(\widehat{\mathbf{L}}\mathbf{H}_{\infty}=0\) (resp. \(\widehat{\mathbf{L}}\mathbf{H}_{\infty}=\rho_{\widehat{\mathbf{L}}}\mathbf{H}_{ \infty}\))._
**Remark 1** (Dirichlet energy, graph homophily and heterophily).: It has been shown [3] that if the graph is heterophily where the connected node are unlikely to share the same labels, one may prefer a GNN with sharpening effect, corresponding to increase of energy. Whereas, when the graph is highly homophily, a smoothing effect is preferred. Based on the settings above, we show our conclusion on the property of energy dynamic of G-MHKG in the following.

**Theorem 1**.: _G-MHKG can induce both LFD and HFD dynamics. Specifically, let \(\theta_{1}=\mathbf{1}_{N}\) and \(\theta_{2}=\zeta\mathbf{1}_{N}\) with a positive constant \(\zeta\). Then, with sufficient large \(\zeta\) (\(\zeta>1\)) so that \(\mathrm{e}^{f(\mathbf{A})}+\zeta\mathrm{e}^{g(\mathbf{A})}\) is monotonically increasing on spectral domain, G-MHKG is HFD. Similarly, if \(0<\zeta<1\) and is sufficient small such that \(\mathrm{e}^{f(\mathbf{A})}+\zeta\mathrm{e}^{g(\mathbf{A})}\) is monotonically decreasing, the model is LFD._

We leave the proof in Appendix C.1. Theorem 1 directly shows the benefits of constructing multi-scale GNNs because such a model provides flexible control of the dominant dynamic that always amplifies/shrinks the node feature differences at every step of its propagation. Accordingly, once the model is HFD, there will be no over-smoothing issue. Furthermore, it is straightforward to verify that single-scale GNN [20, 5] may satisfy the conditions of frequency dominance described in Theorem 1, and in fact some of them can never be HFD to fit heterophily graphs. See [11] for more details. Finally, we note that there are many other settings of \(\theta_{1}\) and \(\theta_{2}\) that make the model HFD, the example in Theorem 1 is one of them to illustrate its existence.

**Remark 2**.: Recent research on GNNs dynamics [11] suggests that to induce HFD, the weight matrix \(\mathbf{W}\) must be symmetric and contain at least one negative eigenvalue. However, from Theorem 1, G-MHKG can be L/HFD without considering the impact of \(\mathbf{W}\). This further supports the flexibility and generalizability of G-MHKG. However, as we will illustrate in the next section, \(\mathbf{W}\) has direct impact on the model's expressive power and over-squashing.

## 5 Weights Control Expressive Power & Over-squashing

We have demonstrated in Section 4 that the L/HFD induced by G-MHKG does not impose any specific conditions on the weight matrix \(\mathbf{W}\). However, it is intriguing to investigate the functionality of \(\mathbf{W}\) in G-MHKG. Recent developments in [12] shed light on the fact that \(\mathbf{W}\) significantly influences the model's expressive power which refers to the class of functions that GNN can learn, taking node features into consideration. This influence becomes evident through the pairwise (over) squashing phenomenon, which interacts with the number of layers denoted as \(\ell\), i.e. the depth of the model. Specifically, let \(\mathcal{Q}:\mathbb{R}^{N\times c}\rightarrow\mathbb{R}^{N\times d}\) be the function that GNNs aim to learn, where \(d\) is the dimension of the node features after certain layers of propagation. One can characterize the **expressive power** of one GNN model by estimating the amount of mixing of \(\mathcal{Q}(\mathbf{X})\) among any pair of nodes by the following definition.

**Definition 2** (Maximal Mixing).: For a smooth function \(\mathcal{Q}\) of \(N\times c\) variables, the maximal mixing induced from \(\mathcal{Q}\) associated with nodes \(u,v\) can be measured as:

\[\mathrm{mix}_{\mathcal{Q}}(v,u)=\max_{\mathbf{X}}\left\|\frac{\partial( \mathcal{Q}(\mathbf{X}))_{v}}{\partial\mathbf{x}_{u}}\right\|, \tag{6}\]

where \(\|\cdot\|\) is the spectral norm of the matrix. Here the \(\mathrm{mix}_{\mathcal{Q}}(u,v)\in\mathbb{R}\) depends on the maximal component of Jacobian matrix between the output of GNN and the initial node features.
Furthermore if one replaces the \(\mathcal{Q}(\mathbf{X})\) in Eq. (6) by the feature representation from an \(\ell\)-layer GNN, the quantity presented in Eq. (6) aligns with the so-called _sensitivity_ which was proposed to measure the over-squashing issue [33]. Therefore, it is natural to see that if **one GNN has strong mixing (expressive) power, the over-squashing issue in this GNN tends to be smaller**. We note that similar definitions and discussions can be found in [12]. Accordingly, we define **over-squashing** (OSQ) as

\[\text{OSQ}_{v,u}=\big{(}\text{mix}_{\mathcal{Q}}(v,u)\big{)}^{-1}. \tag{7}\]

Now we present the upper bound of \(\text{mix}_{\mathcal{Q}}(v,u)\) for G-MHKG, also standing for the upper bound of its expressive power. Specifically, the upper bound of \(\text{mix}_{\mathcal{Q}}(v,u)\) is determined by \(\mathbf{W}\), depth \(\ell\) and \(\mathbf{S}=\sum\widehat{\mathbf{A}}^{l}+\widehat{\mathbf{A}}^{h}\), where \(\widehat{\mathbf{A}}^{l}=\mathbf{I}-\mathbf{U}\mathbf{\Lambda}_{1}\mathbf{U} ^{\top}\) and \(\widehat{\mathbf{A}}^{h}=\mathbf{I}-\mathbf{U}\mathbf{\Lambda}_{2}\mathbf{U} ^{\top}\) stand for the (weighted) adjacency matrices generated from the low pass and high pass filtering functions, respectively. We note that for the sake of simplicity, we set both \(\theta_{1}=\theta_{2}=\mathbf{1}_{N}\) in Eq. (5).

**Lemma 2**.: _Let \(\mathcal{Q}(\mathbf{X})=\mathbf{H}^{(\ell)}\), \(\|\mathbf{W}^{(\ell-1)}\|\leq\mathrm{w}\) and \(\mathbf{S}=\widehat{\mathbf{A}}^{l}+\widehat{\mathbf{A}}^{h}\). Given \(u,v\in\mathcal{V}\), with \(\ell\) layers, then the following holds:_

\[\left\|\frac{\partial\mathbf{h}_{v}^{(\ell)}}{\partial\mathbf{x}_{u}}\right\| \leq\mathrm{w}^{\ell}\left(\mathbf{S}\right)_{v,u}^{\ell}, \tag{8}\]

_where \(\|\cdot\|\) is the spectral norm of the matrix._

We present the proof in Appendix C.2. The conclusion in Lemma 2 indicates that the incorporation of W serves a dual purpose: it not only plays a role in defining the model's expressive capabilities but also helps us understand the connection between the model's expressiveness and the concern of over-squashing.

**Remark 3** (HFD, over-smoothing and over-squashing).: Based on the discussion in Section 4, to adapt G-MHKG to HFD dynamic, one shall require at least one of \(f(\cdot)\) and \(g(\cdot)\) to be _monotonically increasing_ and ensure that G-MHKG always amplifies the output induced from such high pass filter determined domain (i.e., Theorem 1). Similarly, if one wants to decrease the over-squashing, it is sufficient to increase all entries of \(\mathbf{S}\), so that the upper bound of mixing power increases, resulting a potentially smaller over-squashing. We note that this observation supports that any _graph re-weighting_ that increases the quantity of \(\mathbf{S}\) and _graph rewiring_ that makes \(\mathbf{S}\) denser can mitigate the over-squashing issue. Therefore it is not difficult to verify that based on the form of \(\mathbf{S}\) in Lemma 2, to increase \(\mathbf{S}\), it is sufficient to require \((\mathbf{U}\text{diag}(\theta_{1})\mathrm{e}^{f(\mathbf{\Lambda})}+\text{ diag}(\theta_{2})\mathrm{e}^{g(\mathbf{\Lambda})}\mathbf{U}^{\top})_{i,j}<\widehat{ \mathbf{L}}_{i,j}\,\forall i,j\). This suggests that similar to the model dynamics, the over-squashing issue can also be investigated through the filtering functions in spectral domain.

## 6 Trade-off Between two issues in spectral domain

Building upon the findings from Section 4 and Section 5, this section explores a discernible trade-off between _over-smoothing_ and _over-squashing_. Assuming we have two G-MHKGs namely G-MHKG(1) and G-MHKG(2), with the same assumptions in Lemma 2, additionally let two models share the same weight matrix \(\mathbf{W}\). Then it is sufficient to have the following conclusion.
**Lemma 3** (Trade-off).: _For two G-MHKGs namely G-MHKG(1) and G-MHKG(2), if G-MHKG(1) has lower over-squashing than G-MHKG(2) i.e., \(\mathrm{e}^{f_{1}(\mathbf{\Lambda})}+\mathrm{e}^{g_{1}(\mathbf{\Lambda})}< \mathrm{e}^{f_{2}(\mathbf{\Lambda})}+\mathrm{e}^{g_{2}(\mathbf{\Lambda})}\), where \(f_{1},g_{1}\) and \(f_{2},g_{2}\) are filtering functions of two models, respectively, then on any iteration, i.e., from \(\mathbf{H}^{(\ell-1)}\) to \(\mathbf{H}^{(\ell)}\). With the same initial node feature \(\mathbf{H}^{(\ell-1)}\), we have the following inequality in terms of Dirichlet energy of two models_

\[\mathbf{E}(\mathbf{H}^{(\ell)})_{1}<\mathbf{E}(\mathbf{H}^{(\ell)})_{2}.\]

_In words, more feature smoothing effect is induced from lower over-squashing model G-MHKG(1)._

We include the proof in Appendix C.3. Our conclusion can be applied to single-scale GNNs. To gain a clear understanding of the trade-off described in Lemma 3, one can consider that since the sum of the filtering functions of G-MHKG(2) over G-MHKG(1) indicating a higher Dirichlet energy of the node features, and thus G-MHKG(2) produces less smoothing than G-MHKG(1). Meanwhile, the higher values of eigenvalues from G-MHKG(2) also increase model's over-squashing based on Lemma 2 and Remark 3. These observations directly suggest that imposing more sharpening effect in a model to prevent over-smoothing will lead to more over-squashing.

## 7 Time manipulation: How to handle two issues and beyond

While we have illustrated the fundamental relationship (trade-off) between over-smoothing and over-squashing, whether GNN models can handle both issues naturally becomes the next question. Specifically, one shall require a GNN to be HFD to avoid over-smoothing and increasing the quantities in \(\mathbf{S}\) to decrease over-squashing. In terms of G-MHKG, one can see that due to the property of exponential function, it is not possible to have the summation of the diagonal position of \(\mathrm{diag}(\theta_{1})\mathrm{e}^{f(\mathbf{\Lambda})}+\mathrm{diag}( \theta_{2})\mathrm{e}^{g(\mathbf{\Lambda})}=0\) unless we set \(\theta_{1}=\theta_{2}=0\) under the situation that \(\mathrm{e}^{f(\mathbf{\Lambda})}\neq\mathrm{e}^{g(\mathbf{\Lambda})}\), or \(\theta_{1}=-\theta_{2}\) when \(\mathrm{e}^{f(\mathbf{\Lambda})}=\mathrm{e}^{g(\mathbf{\Lambda})}\). Nonetheless, to satisfy the condition, we delay the occurrence of HFD by setting \(\theta_{1}=\theta_{2}=0\) when \(\lambda=0\), and our result is summarized in the following theorem.

**Theorem 2** (Delayed HFD (D-HFD)).: _G-MHKG is capable of handling both two issues with HFD dynamic and non-increasing over-squashing. Specifically, let \(k\) be the number of connected components of \(\mathcal{G}\) and \(\theta_{1}\), \(\theta_{2}\geq 0\) then both two issues can be sufficiently handled by setting \(\mathrm{diag}(\theta_{1})_{i,i}=\mathrm{diag}(\theta_{2})_{i,i}=0\)\(i\in[1,k]\) and \(\mathrm{diag}(\theta_{1})\mathrm{e}^{f(\mathbf{\Lambda}_{i},i)}+\mathrm{diag}( \theta_{2})\mathrm{e}^{g(\mathbf{\Lambda}_{i},i)}<\mathbf{\Lambda}_{i,i}\)\(i\in[k+1,N]\)._

We included the detailed proof in Appendix C.4 with additional discussions and clarifications. Importantly from Theorem 2, the reason that we consider zero eigenvalues of the graph is to sufficiently decrease the over-squashing, one shall require the filtered eigenvalues are not larger than the graph spectra. Therefore when eigenvalues are \(0\), the sufficient condition is to require the filtering results equal to \(0\) to maintain the over-squashing level. Figure. 2 shows the comparison between different kinds of filtering functions in regard to the effect on over-smoothing and over-squashing. In addition, although Theorem 2 show how a D-HFD model handle two issues, this conclusion is more applicable to heterophily graphs according to Remark 1. However, as we will show in the next theorem, it is not possible for the model to be LFD and decrease over-squashing.

**Theorem 3**.: _Suppose \(\theta_{1}\) and \(\theta_{2}\geq 0\), then it is impossible for the model to be LFD and decrease OSQ. In other words, there must exist at least one \(\mathbf{\Lambda}^{*}\subseteq\mathbf{\Lambda}\) such that \(\mathrm{diag}(\theta_{1})\mathrm{e}^{f(\mathbf{\Lambda}^{*})}+\mathrm{diag}( \theta_{2})\mathrm{e}^{g(\mathbf{\Lambda}^{*})}\) is (1): monotonically increasing (HFD); (2): with constant quantity (thus not LFD); (3): monotonically decreasing with image greater than \(\mathbf{\Lambda}\) thus OSQ is increased._
The proof of theorem is in Appendix C.5. Figure. 2 (right) illustrates the situation in Theorem 3. The model with the dynamic shown in Figure. 2 (right) (i.e., first \(k\) components being 0 + dashed HFD + LFD) is not a LFD and in fact asymptotically dominated by the HFD part, thereby according to Definition 1 and Lemma 1, the model is not L/HFD.

Relation to existing worksCompared to the existing work [15] 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. This suggests the effectiveness for incorporating multi-scale GNNs in terms of investigating the over-smoothing issue via model dynamics. Furthermore, although similar motivation for inducing sharpening effect to the node features was explored [7], its effect was only verified empirically. Our analysis under the scope of dominant dynamic and maximal mixing of the function learned from GNNs pave the path of evaluating well-known GNN issues in a unified platform. 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 [15] and rewiring the communities connected with very negatively curved edges which is responsible for the over-squashing issue [33]. Although the relationship between the graph edge curvature and spectra was explored [2], a detailed comparison between spatial (curvature based surgery) and spectral method is still wanted, especially on how the spatial surgery affects the eigen-distribution of the graph spectra [27].

## 8 Experiment

In this section, we show a variety of numerical tests for MHKG and G-MHKG. Specifically, Section 8.1 verifies how a controlled model dynamic enhances model's adaption power on homophily and heterophily graphs. In Section 8.2 we will compare model performance under four different dynamics to illustrate how D-HFD dynamic assists model in handling two issues. Furthermore, Section 8.3 will show the performance (node classification) of MHKG and G-MHKG via real-world citation networks as well as large-scale graph dataset. We include more discussions (i.e., computational complexity) and ablation studies in Appendix D. All experiments were conducted using PyTorch on Tesla V100 GPU with 5,120 CUDA cores and 16GB HBM2 mounted on an HPC cluster. The source code can be found in [https://anonymous.4open.science/r/G_MHKG_accept](https://anonymous.4open.science/r/G_MHKG_accept).

Experiment SetupFor the settings in MHKG, we followed form of MHKG defined in Eq. (3) by setting \(f(\mathbf{\Lambda})=\mathbf{U}(\mathrm{e}^{\mathbf{\Lambda}})\mathbf{U}^{\top}\). We note that in general the form of \(f\) can be any _monotonic positive_ function on \(\mathbf{\Lambda}\), here we only choose the one in Eq. (3) for the consistency reason. In regarding to G-MHKG, we assign one initial warm-up coefficient \(\gamma>1\) that is multiplied with \(f(\widehat{\mathbf{L}})\) if the graph is homophily otherwise on \(g(\widehat{\mathbf{L}})\) if a graph is heterophily. We note that this operation aims to

Figure 2: The figure on the left represents different types of HFD filtering outcomes and the trade-off between two issues. One can check that to induce more sharpening (filtering function from bottom to top), the model will suffer more from OSQ. The figure on the right illustrates the situation described in Theorem 3.
ensure G-MHKG to induce more smoothing/sharpening effect for fitting different types of graphs according to Remark 1. We then re-scale the result of the filtering functions back to \([0,2]\) so that the assumption of Lemma 2 holds. We included **Cora, Citeseer, Pubmed** for homophily datasets and applied public split [25] and **Wisconsin, Texas, Cornell** as heterophily datasets with 60% for training, 20% for testing and validation. In addition, we also included one large-scale graph dataset **ogbn-arxiv** to illustrate model scalability for large scale datasets. The summary statistics of all included benchmarks as well as the model hyper-parameter search space are included in Appendix D.1. We set the maximum number of epochs of 200 for citation networks and 500 for **ogbn-arxiv**. The average test accuracy and its standard deviation come from 10 runs.

### Controlled Model Dynamic

In this section, we verify Theorem 1 by assigning different quantities of \(\zeta\) so that G-MHKG can be L/HFD. Specifically, we fixed \(\theta_{1}=\mathbf{1}_{N}\), \(\mathbf{2}_{N}\), and \(\mathbf{3}_{N}\) and set the value of \(\zeta\) from 0.5 to 3 with the unit of change as 0.5 so that model dynamics changed from HFD to LFD (i.e., \(\zeta=0.5\)). All other hyperparameters were fixed across the models. We conducted the experiment on **Cora** and **Texas**, and Fig. 3 shows the changes in the learning accuracy on both datasets. It is clear to see that with the increase of \(\zeta=\theta_{1}/\theta_{2}\), model's dynamics change from LFD to HFD, resulting in more adaption power from homophily to heterophily graphs.

### Handling both issues with D-HFD and ablation

In this section, we show how G-MHKG with D-HFD dynamic handles both over-smoothing and over-squashing issues. Specifically, we compare G-MHKG's performance via the following four dynamics: LFD (\(\theta_{1}>\theta_{2}>0\)), HFD + increase in OSQ (sufficient large of \(\theta_{2}\)), D-HFD + increase in OSQ (\(\theta_{2}\) sufficient large and first \(k\) components of both \(\theta_{1}\) and \(\theta_{2}\) are 0) and D-HFD + decrease in

Figure 4: Results on model with different dynamics. Number of layers from 8, 16, 32, 64, and 96.

Figure 3: Model Accuracy(%) via different ratios between filtering matrices. Left: Accuracy on **Cora**, Right: Accuracy on **Texas**.
OSQ (Theorem 2). We include more details on the model setup for inducing the aforementioned dynamics in Appendix D.2. We select two homophily graphs (**Cora** with \(k=25\) and **Citeseer**\(k=115\)) and heterophily graphs (**Cornell**\(k=6\) and **Wisconsin**\(k=16\)). We tested G-MHKG with \(8,16,32,64\) and \(96\) layers to illustrate the asymptotic behavior of the model via different dynamics. We note that this experiment can also be served as an ablation study which proves the advantage of D-HFD for heterophily graphs. Fig. 4 illustrates the accuracy comparison between four dynamics. One can see from Fig. 4 that for homophily graphs, LFD (blue) models always present the top performances compared to other three dynamics, followed by the dynamic of D-HFD + decreasing OSQ (violet) as such dynamic assists model to handle over-squashing issue. The last two ranks are achieved by D-HFD + increase OSQ (orange) and HFD + increase OSQ (green) with the former dynamic not increase OSQ with the first \(k\) eigenvalues and latter suffering from both issues. For heterophily graphs, with the best accuracy achieved via D-HFD + decreased OSQ across all layers, and the worst outcome in LFD which is unnecessary for homophily graphs.

### Results of Node classification on real-world data

We include the introduction of the baseline models and the reason of choosing them in Appendix D.1. We design MHKG and G-MHKG with two convolution layers followed by softmax activation function. The results of node classification are included in Table 1, and all baseline results are listed according to the existing publications. One can check that G-MHKG show remarkable performance on both homophily and heterophily graphs.

### Discussion on Limitation and ways forward

Limitation on L/HFD, why there is an accuracy drop?We found that there is a considerable accuracy drop between the results in Table. 1 and model with four different dynamics and different layers. This observation suggests that although L/HFD are proved to be more suitable for homo/heterophily graphs, under large number of layers, i.e., GNNs propagates feature information from large hops, the measure of homophily level [45] become powerless, since such level varies through hops and thus requiring GNNs to induce a layer-wise rather than overall dynamics when the layer number is high. This observation aligns with the motivation of the work in [21].

The measure of OSQLemma 2 establishes an upper bound for the node sensitivity measure on the issue of over-squashing. While Lemma 2 offers a necessary condition, it does not guarantee that G-MHKG possesses the desired mixing power. Hence, a complementary lower bound that

\begin{table}
\begin{tabular}{c c c c c c c c} \hline Methods & Cora & Citeseer & Pubmed & Cornell & Texas & Wisconsin & Arxiv \\ \hline MLP & 55.1 & 59.1 & 71.4 & **91.3\(\pm\)0.7** & **92.3\(\pm\)0.7** & **91.8\(\pm\)3.1** & 55.0\(\pm\)0.3 \\ GCN & 81.5\(\pm\)0.5 & 70.9\(\pm\)0.5 & 79.0\(\pm\)0.3 & 66.5\(\pm\)13.8 & 75.7\(\pm\)1.0 & 66.7\(\pm\)1.4 & **72.7\(\pm\)0.3** \\ GAT & 83.0\(\pm\)0.7 & **72.0\(\pm\)0.7** & 78.5\(\pm\)0.3 & 76.0\(\pm\)1.0 & 78.8\(\pm\)0.9 & 71.0\(\pm\)4.6 & 72.0\(\pm\)0.5 \\ GIN & 78.6\(\pm\)1.2 & 71.4\(\pm\)1.1 & 76.9\(\pm\)0.6 & 78.0\(\pm\)1.9 & 74.6\(\pm\)0.8 & 72.9\(\pm\)2.5 & 64.5\(\pm\)2.5 \\ HKGCN & 81.9\(\pm\)0.9 & 72.4\(\pm\)0.4 & 79.9\(\pm\)0.3 & 74.2\(\pm\)2.1 & 82.4\(\pm\)0.7 & 85.5\(\pm\)2.7 & 69.6\(\pm\)1.7 \\ GRAND & 82.9\(\pm\)1.4 & 70.8\(\pm\)1.1 & 79.2\(\pm\)1.5 & 72.2\(\pm\)3.1 & 80.2\(\pm\)1.5 & 86.4\(\pm\)2.7 & 71.2\(\pm\)0.2 \\ UFG & **83.3\(\pm\)0.5** & 71.0\(\pm\)0.6 & 79.4\(\pm\)0.4 & 83.2\(\pm\)0.3 & 82.3\(\pm\)0.9 & **91.9\(\pm\)2.1** & **72.6\(\pm\)0.1** \\ SJLR & 81.3\(\pm\)0.5 & 70.6\(\pm\)0.4 & 78.0\(\pm\)0.3 & 71.9\(\pm\)1.9 & 80.1\(\pm\)0.9 & 66.9\(\pm\)2.1 & 72.0\(\pm\)0.4 \\ \hline MHKG & 82.8\(\pm\)0.2 & 71.6\(\pm\)0.1 & 78.9\(\pm\)0.3 & 86.2\(\pm\)0.6 & 84.5\(\pm\)0.3 & 88.9\(\pm\)0.3 & 72.1\(\pm\)0.6 \\ G-MHKG & **83.5\(\pm\)0.2** & **72.8\(\pm\)0.2** & **80.1\(\pm\)0.4** & **90.2\(\pm\)0.9** & **89.6\(\pm\)0.6** & 91.2\(\pm\)1.5 & 72.4\(\pm\)0.3 \\ \hline \end{tabular}
\end{table}
Table 1: Performance on node classification using public split. Top two in **bold**.
provides a sufficient condition becomes essential. Thereby in scenarios where both over-smoothing and over-squashing need to be considered, an adjusted conclusion is sought after.

## 9 Conclusion

In this paper, we explored the underlying relationship between three fundamental issues of GNNs: over-smoothing, over-squashing, and expressive power via proposed G-MHKG induced by reversing the time direction of so-called graph heat equation. We revealed the roles of the filtering and weight matrices via gradient flow and maximal mixing perspectives to illustrate their capability of controlling aforementioned issues. Furthermore, we show that under mild conditions on the filtering equations in G-MHKG, there is a fundamental trade-off between over-smoothing and over-squashing via graph spectral domain. We further showed that our proposed model is capable of handling both issues and own its advantage in terms of mixing smoothing and sharpening effects compared to single-scale GNNs. While we have shown superior performance of G-MHKG empirically, many unknown issues we have listed still inspire us to explore further. In future works, we will attempt to discover the necessary conditions (such as lower bound of \(\mathbf{S}\) and more complex model dynamic other than L/HFD) for one GNN that is capable of handling all mentioned issues.
