Over-Squashing in Graph Neural Networks: A Comprehensive survey
Graph Neural Networks (GNNs) revolutionize machine learning for
graph-structured data, effectively capturing complex relationships. They
disseminate information through interconnected nodes, but long-range
interactions face challenges known as "over-squashing". This survey delves into
the challenge of over-squashing in Graph Neural Networks (GNNs), where
long-range information dissemination is hindered, impacting tasks reliant on
intricate long-distance interactions. It comprehensively explores the causes,
consequences, and mitigation strategies for over-squashing. Various
methodologies are reviewed, including graph rewiring, novel normalization,
spectral analysis, and curvature-based strategies, with a focus on their
trade-offs and effectiveness. The survey also discusses the interplay between
over-squashing and other GNN limitations, such as over-smoothing, and provides
a taxonomy of models designed to address these issues in node and graph-level
tasks. Benchmark datasets for performance evaluation are also detailed, making
this survey a valuable resource for researchers and practitioners in the GNN
field.
Singh Akansha
# Over-Squashing in Graph Neural Networks:

###### Abstract

Graph Neural Networks (GNNs) revolutionize machine learning for graph-structured data, effectively capturing complex relationships. They disseminate information through interconnected nodes, but long-range interactions face challenges known as "over-squashing". This survey delves into the challenge of over-squashing in Graph Neural Networks (GNNs), where long-range information dissemination is hindered, impacting tasks reliant on intricate long-distance interactions. It comprehensively explores the causes, consequences, and mitigation strategies for over-squashing. Various methodologies are reviewed, including graph rewiring, novel normalization, spectral analysis, and curvature-based strategies, with a focus on their trade-offs and effectiveness. The survey also discusses the interplay between over-squashing and other GNN limitations, such as over-smoothing, and provides a taxonomy of models designed to address these issues in node and graph-level tasks. Benchmark datasets for performance evaluation are also detailed, making this survey a valuable resource for researchers and practitioners in the GNN field.

 Graph Neural Networks (GNNs), Over-squashing, Over-smoothing, Graph-rewiring

## I Introduction

In recent years, the explosion of data in various domains has led to an increased interest in harnessing the power of graph structures for modeling complex relationships [1, 2, 3, 4, 5]. Graphs, which consist of nodes and edges representing entities and their connections, respectively, have emerged as a fundamental data representation in fields such as social networks [2, 6, 7], recommendation systems [8, 9, 10, 11], biology [12, 13], and more. As the diversity and complexity of graph-structured data grow, so does the demand for advanced tools to analyze and understand these intricate relationships.

This surge in interest has sparked the development of a remarkable class of machine learning models known as Graph Neural Networks (GNNs) [14, 15, 16]. GNNs are a novel approach to learning representations from graph-structured data, enabling us to capture both local and global information of nodes in a unified manner [17, 18]. In essence, GNNs extend the neural network architecture to accommodate graph data, where nodes represent entities and edges denote relationships. This extension opens the door to a multitude of applications, ranging from node classification [19, 20, 21] and link prediction to graph-level tasks like community detection [6, 22] and molecular property prediction [23, 24]. GNNs leverage the underlying graph structure to enable information propagation and aggregation, enabling them to capture intricate patterns that traditional machine learning models struggle to discern.

Notwithstanding their remarkable achievements, GNNs are not immune to certain inherent limitations, including over-smoothing [25, 26], vanishing gradients [27, 28], Out-of-Distribution (OOD) data challenges [29, 30], overfitting [31], and the relatively less explored phenomenon of over-squashing [32, 33, 34]. While exhaustive research has been dedicated to addressing the former issues, the latter--over-squashing--remains relatively less explored.

Over-squashing is a phenomenon that manifests in tasks requiring the integration of information from distant nodes [32, 35], primarily through edges that serve as bottlenecks within graph data. To put it succinctly, over-squashing denotes the distortion-prone nature of information transfer between nodes that are widely separated [34]. This distortion emerges due to the inherent tension between the limited feature representation capacity of graph embeddings and the exponential growth in the number of neighbors as graphs expand. This interplay often hampers the faithful transmission of distant information.

This survey article aims to provide a comprehensive panorama of this specific limitation. We delve into the intricate nuances of over-squashing, shedding light on its conceptual framework and its implications. Additionally, we meticulously outline the repertoire of methods proposed thus far to grapple with this intricate issue. By presenting a systematic exploration of the landscape, we contribute to a deeper understanding of over-squashing's impact on GNNs and offer insights into the evolving strategies engineered to surmount this challenge.

To summarize, this paper makes the following key contributions:

1. _Pioneering Survey_: This paper serves as the inaugural comprehensive survey on 'over-squashing,' a pivotal limitation in message-passing graph neural networks. It addresses a burgeoning area of interest among researchers.
2. _Systematic Categorization_: We provide a systematic categorization of existing methods, offering a detailed taxonomy that simplifies the understanding of various strategies to mitigate over-squashing.
3. _Benchmark Datasets_: We extensively discuss commonly used benchmark datasets employed for evaluating mod
els in the context of over-squashing, both at the node and graph levels.
4. _Added Value:_ Additionally, this survey explores the interplay of over-squashing with other fundamental GNN limitations, such as 'over-smoothing,' providing a more holistic perspective on the challenges faced in this domain.

These contributions collectively make this paper a valuable resource for researchers and practitioners delving into the intricate domain of over-squashing in Graph Neural Networks.

## II Background

### _Graph Neural Networks_

A GNN is a neural network architecture designed to operate on graph-structured data. The core idea of a GNN is to iteratively aggregate information from neighboring nodes and update the node features through multiple layers.

Consider a graph denoted as \(G=(V,E)\), where \(V\) represents the set of nodes and \(E\) is the set of edges (or links), with \(E\subseteq V\times V\). In the context of Graph Neural Networks (GNNs), the primary objective is to learn effective representations for nodes, links, and even entire graphs. This is achieved through a fundamental process called message-passing, as defined by Gilmer et al. (2017) and elaborated by Zhang et al. (2022). In this process, GNNs iteratively refine node representations using the following equations:

At layer \(l\):

\[h_{u}^{(l)}=COM\bigg{\{}h_{u}^{(l-1)},AGG\{h_{v}^{(l-1)}\text{ where }v\in N_{u}\}\bigg{\}}\]

Where \(h_{u}^{(l-1)}\) represents the representation of node \(u\) at the \(l-1\)th layer. It is typically initialized with the node's feature at the initial layer. \(N_{u}\) signifies the set of neighbors of node \(u\). \(AGG(\cdot)\) denotes the aggregation function that gathers information from neighboring nodes. \(COM(\cdot)\) is the combination function responsible for integrating aggregated information into the node's representation. By iteratively applying this message-passing mechanism, GNNs refine node representations while considering the relationships with neighboring nodes. This step is crucial for capturing the structural and semantic information within the graph.

Once the node representations are established, GNNs extend their influence to edges (links) and the entire graph. _Link Representations_: The representations of connected nodes are leveraged to derive meaningful representations for the links connecting them. _Graph-Level Representations_: The collective information from all nodes in the graph is distilled using a readout (or pooling) operation. This operation yields a representation of the entire graph, encapsulating its characteristics.

Ultimately, the acquired representations of nodes, links, or entire graphs can be harnessed to address a variety of graph-based tasks. These tasks span different levels of complexity, ranging from node-specific tasks like node classification and link prediction to higher-order tasks involving the entire graph structure.

### _Over-squashing_

The phenomenon of over-squashing has been described as a challenge arising within Message Passing Neural Networks (MPNNs) when messages traverse through distant nodes. This issue stems from the exponential expansion of a node's receptive field, which results in numerous messages being compressed into fixed-size vectors. Topping et al. (2022)[35] have formally substantiated this occurrence through a sensitivity analysis of the Jacobian matrix of node features. They have partly attributed over-squashing to the presence of edges exhibiting high-negative curvature.

To elaborate, let's consider a receptive field \(B_{r}=\{j\in V:d_{G}(i,j)\leq r\}\) associated with a \(r\)-layer GNN, where \(d_{G}\) signifies the shortest-path distance and \(r\) is a natural number. The Jacobian matrix \(\partial h(r)_{i}/\partial x_{j}\) represents the sensitivity of a node embedding \(h(r)_{i}\) to a specific input feature \(x_{j}\) in node \(j\). Over-squashing can be conceptualized as the inability of \(h(r)_{i}\) to be influenced by \(x_{j}\) at a distance \(r\). Topping et al. [35] have mathematically established that

\[\frac{\partial h_{i}^{(r+1)}}{\partial x_{j}}\leq(\alpha\beta)^{r+1}A^{r+1}(i,j)\]

under certain conditions, where \(|\Delta\phi_{l}|\leq\alpha\) and \(|\Delta\psi_{l}|\leq\beta\) for \(0\leq l\leq r\), and \(\phi_{l},\psi_{l}\) are differentiable functions. This inequality highlights how the influence of input features diminishes exponentially with distance \(r\), particularly noticeable when \(|B_{r}|\) grows exponentially.

For instance, in a binary tree where \(d_{G}(i,j)=r+1\), the term \(A^{r+1}(i,j)\) equals \(2^{(-1/3)}*2^{(-r)}\), leading to an exponential decay in node dependence on input features at distance \(r\). This phenomenon is what researchers refer to as the over-squashing of information [34, 35].

In [34] authors tried to answer (1) what is the impact of width in mitigating over-squashing? (2) can over-squashing can be avoided by sufficiently deep models? (3) how does over-squashing relate to graph spectrum and the underlying topology beyond curvature bounds that only apply to 2-hop neighbors? Last question is important because recent works trying to combat over-squashing via methods that depends on the graph spectrum [36, 37, 38]

## III Handling over-squashing in graph neural networks(GNNs)

In scenarios where tasks necessitate spanning multiple layers within a network, the depth of the network often mirrors the range of interactions between nodes. Nevertheless, a rising number of layers corresponds to an exponential increase in the number of nodes contributing to the receptive field of each individual node. This amplification leads to the phenomenon of over-squashing [32, 35]. Essentially, over-squashing manifests as a compression of information originating from a receptive field that encompasses numerous nodes. This compression results in fixed-length node vectors, impeding the accurate propagation of messages from distant nodes. This distortion takes shape due to graph bottlenecks that emerge as
the number of \(k\)-hop neighbors undergoes exponential growth with each \(k\).

In a bid to surmount these challenges, the literature has proposed strategies such as graph rewiring [32]. Consider a graph denoted as \(G\) with number of node as \(n\), adjacency matrix \(A\), and a mapping function \(R:\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n\times n}\). When we talk about the graph \(G\) being "rewired" by \(R\), it signifies a transformation where the message exchanges among nodes occur on a graph denoted as \(R(G)\), rather than the original \(G\). In this context, \(R(G)\) is the graph characterized by its adjacency matrix \(R(A)\).

The challenge of over-squashing within Graph Neural Networks (GNNs) has spurred the development of various methodologies, each aiming to alleviate this phenomenon. Broadly, these methods can be categorized into two types of graph rewiring methods, each offering unique insights into the resolution of the over-squashing predicament.

### _Spatial Graph Rewiring Methods:_

**Curvature-Based Rewiring and Comprehensive Topological Analysis:** Topping et al. [35] and Di Giovanni et al. [34] contributed insights into the origins of over-squashing, its topological implications, and the influence of GNN design choices.

**SDRF** Topping et al. [35] yielded a novel approach, Stochastic Discrete Ricci Flow (SDRF), to mitigating the pervasive issue of over-squashing in Graph Neural Networks (GNNs) through a curvature-based graph rewiring procedure. The crux of this innovative methodology lies in its meticulous treatment of graph edges based on their curvature properties. Specifically, edges exhibiting negative curvatures, indicative of potential sources of over-squashing, become the focal point of attention. By orchestrating the construction of supplementary connections tailored to support these edges, the proposed rewiring process adeptly combats the adverse effects of over-squashing.

**FA** Alon and Yahav [32] introduced a graph rewiring method that adds a fully-adjacent matrix in the last GNN layer to mitigate over-squashing. This approach is simple to implement and can be couple to any existing GNN architecture. It involves incorporating a Fully-adjacent layer (FA) in GNNs to alleviate the problem.

**BORF** Recently, Nguyen introduced a novel rewiring technique known as Batch Ollivier-Ricci Flow (BORF), which harnesses the power of Ollivier-Ricci curvature to address the interrelated challenges of over-smoothing and over-squashing in Graph Neural Networks (GNNs) as detailed in [39]. BORF is a novel approach designed to address the issues of over-squashing and over-smoothing in Graph Neural Networks (GNNs). It operates in batches and begins by identifying two sets of edges in each batch: h edges with minimal curvature and k edges with maximal curvature. By focusing on edges with low and high curvature values, respectively, BORF aims to simultaneously mitigate over-smoothing and over-squashing. It then optimizes the graph's connectivity by adding connections to the minimally curved edges, ensuring efficient communication between distant nodes. This alleviates over-squashing. To minimize computational overhead, BORF reuses previously calculated optimal transport plans for edge addition. Additionally, BORF removes the maximally curved edges to prevent over-smoothing, as these can lead to excessive smoothing of node features. Furthermore, the algorithm's flexibility allows it to operate as a net edge addition, subtraction, or net-zero rewiring, providing adaptability to different data characteristics. BORF effectively balances these two key challenges, enhancing the performance of GNNs in graph-related tasks.

**GTR** Within the realm of addressing over-squashing in Graph Neural Networks (GNNs), Black et al. [40] have conducted a comprehensive analysis by investigating the phenomenon through the lens of commute time between node pairs. They proposed Greedy Total Resistance (GTR) rewiring, method to minimize the total resistance. Effective resistance offers an alternative metric for evaluating bottlenecks within graph topology [41]. This measure quantifies the level of resistance between two nodes in proportion to their commute time. Commute time represents the expected number of steps required for a random walk to traverse back and forth between nodes within the graph. In essence, high resistance between two nodes indicates a greater difficulty for messages to traverse from node \(i\) to node \(j\). Black et al. [40] have established a sensitivity bound which links elevated effective resistance between pairs of nodes to a reduced sensitivity of the representations, \(h^{(r+1)_{i}}\) concerning input features \(x_{j}\). Furthermore, it's important to note that effective resistance exhibits an inverse relationship with the square of the Cheeger constant.

In a parallel vein, Di Giovanni et al. [34] have undertaken similar methodologies, ultimately converging on a shared conclusion. Their findings underline the pivotal role of effective resistance in influencing the degree of over-squashing within GNNs. Furthermore, the work by Di Giovanni et al. [34] extends beyond a singular focus on effective resistance. They delve into the impact of GNN architecture's width and depth on the occurrence of over-squashing. This comprehensive analysis probes into how various dimensions of GNN design interplay with the manifestation of over-squashing, enriching our understanding of this intricate phenomenon.

In their work, Di Giovanni et al. [42] build upon their previous findings and concentrate on two pivotal factors: the network's architecture, characterized by weight norms and depth, and the intrinsic graph structure, evaluated using commute times. In doing so, they establish upper limits on the ability of Message Passing Neural Networks (MPNNs) to efficiently integrate features. Significantly, they introduce the notion of "over-squashing," which is fundamentally linked to MPNNs' maximum node mixing capacity and operates inversely to it.

**DRew** Gutteridge et al. [43] argue that while some rewiring approaches attempt to enhance connectivity for long-range tasks, they often sacrifice the inductive bias provided by graph distance by enabling instant communication between distant nodes at every layer. Hence to tackle these issues a
layer-dependent rewiring technique is proposed in [43] which gradually densify the graph. A delay mechanism that facilitates skip connections based on node distance and layer is also introduced in [43] so that graph's inductive bias is preserved.

### _Spectral Graph Rewiring Methods:_

To explain graph rewiring in the context of spectrum of the graph we would like to explain the connectedness of a graph with eigen values of the graph Laplacian. The connectedness of a graph \(G\) can be measured via a quantity known as the Cheeger constant, denoted as \(h_{Cheeg}\), is defined as follows:

\[h_{Cheeg}=\min(U\subset V)\frac{|\{(u,v)\in E:u\in U,v\in V\ U\}|}{\min(vol(U),vol(V\ U))}\]

Here, \(vol(U)\) represents the volume of set \(U\) and is calculated as the sum of degrees of nodes \(u\in U\).

The Cheeger constant, \(h_{Cheeg}\), essentially quantifies the energy required to divide graph \(G\) into two separate communities. A smaller \(h_{Cheeg}\) implies that \(G\) tends to have two communities with only a few connecting edges. In such cases, over-squashing is more likely to occur when information needs to traverse from one community to another. It's important to note that while computing \(h_{Cheeg}\) is generally a complex task, the Cheeger inequality provides a useful relationship: \(h_{Cheeg}\) is approximately proportional to the smallest positive eigenvalue of the graph Laplacian.

In light of this relationship, some recent approaches have proposed selecting a rewiring strategy that depends on the spectrum of \(G\). The goal is to generate a new graph \(R(G)\) that satisfies \(h_{Cheeg}(R(G))>h_{Cheeg}(G)\). This strategy has been explored in the works [36, 37, 38]. The underlying assumption is that propagating messages over the rewired graph \(R(G)\) can mitigate over-squashing. However, it's important to note that this claim lacks formal analytical proof at this stage.

**Augmenting the Spectral Gap:** The prevailing strategy in mitigating over-squashing has largely revolved around increasing the spectral gap of the graph, specifically targeting the smallest eigenvalue of the Laplacian matrix. Intuitively, the spectral gap is linked to the presence of bottlenecks within graphs, as elucidated by the Cheeger inequality [55]. Consequently, augmenting the spectral gap serves to reduce these bottlenecks, fostering a smoother flow of information. Various strategies have emerged to decrease the spectral gap, encompassing methods such as edge addition [38], edge flipping [47], edge reweighting [36], or the utilization of expanders to perform specific GNN layers [37]. These approaches seek to fine-tune the graph's structural characteristics to mitigate over-squashing while recognizing the pivotal role played by the spectral gap in this intricate balance.

**DiffWire** Arnaiz et al. [36] introduced a unified approach that bridges the concepts of commute time and graph spectral gap. This approach comprises two distinct layers within a Graph Neural Network (GNN). The first layer is a differentiable, parameter-free component designed to learn the commute time, while the second layer, known as the rewiring layer, optimizes the spectral gap based on the specific characteristics of the network and the task at hand. This integrated framework empowers the GNN to adaptively learn and apply rewiring strategies, effectively alleviating the challenges associated with over-squashing while considering the nuances of the graph structure and task requirements.

**EGP Model** Deac et al. [37] introduced the Expander Graph Propagation (EGP) model for graph classification tasks. Their approach leverages expander graphs to tackle bottlenecks in global information propagation within the graph. In graph classification, it's essential to compute node features that consider both local interactions within their neighborhood and the broader global context of the graph structure. Deac et al. achieved this by adding one layer of EGP after each layer of GNN utilizing Cayley graphs to construct efficient expander graphs of a specified size. The EGP model is designed to enhance connectivity for long-range tasks, ensuring efficient communication between distant nodes.

**RLEF** graphs to address bottlenecks in the global propagation of information within a graph. Their method introduces two local graph rewiring algorithms: the Random Local Edge Flip (RLEF) and the Greedy Random Local Edge Flip (G-RLEF). These algorithms operate by adding and removing edges at specific locations while preserving the node degrees and overall connectivity of the graph. This framework provides a robust foundation for conducting a comprehensive analysis of the information decay that arises due to oversquashing in Graph Neural Networks (GNNs). They clarify how an information percolation bound serves as an effective means to encapsulate the core concept of oversquashing. The primary objective of employing these techniques is to enhance connectivity for long-range tasks. They achieve this by ensuring efficient and effective communication between nodes that are geographically distant from each other within the graph structure.

**Trade off between over-smoothing and over-squashing** While these rewiring methods aim to enhance graph connectivity, they come with certain drawbacks, particularly when excessive modifications are made to the input graph. One prominent concern is the loss of valuable topological information inherent to the original graph. When we introduce extensive changes by adding or removing edges, it can diminish the relevance of the original graph's structural characteristics for the given task. Additionally, the act of adding edges has a smoothing effect on the graph. If we introduce an excessive number of edges to the input graph, a standard Graph Convolutional Network (GCN) may encounter a common issue known as oversmoothing, as highlighted by Li et al. in 2018. In simpler terms, when we opt for this straightforward rewiring approach, we find ourselves facing a trade-off between addressing over-squashing and dealing with the problem of oversmoothing.

## IV Unifying approaches for over-squashing and over-smoothing

Certain methodologies have emerged that tackle the intertwined challenges of over-smoothing and over-squashing in
unison, establishing an interconnected relationship between these fundamental limitations within graph neural networks.

**SJLR** Giraldo et al. [33] established a profound connection between over-smoothing and over-squashing and the spectral gap of the graph Laplacian in Graph Neural Networks (GNNs). Their work revealed how these challenges are intricately linked to the spectral gap of the normalized Laplacian matrix, unveiling a noteworthy trade-off illuminated by the Cheeger inequality. In response to these challenges, Giraldo et al. introduced the Stochastic Jost and Liu Curvature Rewiring (SJLR) algorithm, a notable departure from previous curvature-based techniques [35, 38, 47]. SJLR stands out for its computational efficiency and its ability to preserve essential graph properties. One distinctive feature of the SJLR algorithm is its dynamic capability to add and remove edges during the training phase of Graph Neural Networks (GNNs) while maintaining the fundamental graph structure unaltered during the testing phase. This adaptability sets SJLR apart as a promising approach to address the intricate challenges posed by over-smoothing and over-squashing in GNNs.

**MHKG** The study described in [50] takes on the persistent challenges that have plagued the performance of Graph Neural Networks (GNNs), notably over-smoothing, over-squashing, and limited expressive capabilities. Drawing inspiration from physics, the authors employ a novel approach, reversing the direction of the graph heat equation, which substantially sharpens node features. They introduce the Multi-Scaled Heat Kernel based GNN (MHKG), which amalgamates diverse filtering functions to counter these issues. Generalizing MHKG into G-MHKG, they provide an in-depth analysis of its components' roles in controlling over-smoothing, over-squashing, and expressive power. Notably, they uncover a trade-off between over-smoothing and over-squashing, wherein enhancing node feature sharpness may lead to heightened over-squashing, and vice versa. G-MHKG effectively handles these challenges in the graph spectral domain through controlled manipulation of time.

**FoSR** Karhadkar et al. [38] proposed empirical solutions to mitigate both over-smoothing and over-squashing. While acknowledging the trade-off between these issues, their method primarily involves edge addition. The authors introduce a novel rewiring method called FoSR (First-order Spectral Rewiring) with the objective of optimizing the spectral gap of the graph input to the GNN. This algorithm meticulously computes the first-order change in the spectral gap resulting from the addition of each edge and subsequently selects the edge that maximizes this change. Within this framework, the authors propose a comprehensive approach, which not only introduces this innovative rewiring method but also incorporates a relational Graph Neural Network (GNN) to leverage these rewired edges effectively. This GNN operates on the transformed graph, where the relationships within the
network indicate whether each edge was originally part of the input graph or added during the rewiring process. This integrated strategy ensures the preservation of the input graph's underlying topology while utilizing newly added edges to enhance its overall connectivity.

**CurvDrop** Liu et al. [44] addressed both problems by focusing on edge removal based on curvature metrics. They devised a Curvature-based topology-aware Dropout-sampling technique, CurvDrop, which integrates Discrete Ricci Curvature in tGNNs for more expressive graph models. Drawing inspiration from the geometric analogy of Ricci curvature, Liu et al. established a compelling relationship between the Ricci curvature of an edge and the spectral gap. They harnessed this insight to address the challenges of over-smoothing and over-squashing by introducing a sampling layer driven by Ricci curvature. This sampling layer selectively drops a portion of edges with low Ricci curvature at each GNN layer, effectively mitigating the issues associated with over-smoothing and over-squashing.

**CurvPool** CurvPool is a novel graph pooling technique designed by Sanders et al. in [52] to tackle over-smoothing and over-squashing issues in Graph Neural Networks (GNNs) during graph classification tasks. It relies on the Balanced Forman curvature (BFC) to identify critical structures in the graph that contribute to these problems. This method calculates curvature values for each edge and employs a criterion to group nodes into clusters, ensuring that nodes with similar curvature profiles are pooled together. The resulting node clusters are transformed into new nodes in the pooled graph, and node representations within each cluster are aggregated using operators like mean, sum, or maximum. To retain the original graph structure, CurvPool remaps old edges to the new node clusters. By leveraging graph curvature to guide the pooling process, CurvPool effectively balances over-smoothing and over-squashing, ultimately improving the performance of GNNs in graph classification tasks. It offers adaptability to various data characteristics while maintaining computational efficiency and effectiveness.

**CBED** Inspired by the geometric analogy of Ricci curvature, a curvature-based edge dropping algorithm known as Curvature-Based Edge Dropping (CBED) is introduced in the work by Dai Shi et al. [48]. This innovative approach strategically removes edges with the highest positive curvature. By doing so, it aims to enhance the model's adaptability to graphs characterized by heterophily and, in the process, alleviate the issue of over-smoothing.

**PowerEmbed** Huang et al. have introduced a pioneering normalization technique called PowerEmbed in their work [45] aimed at mitigating the challenges of over-smoothing and over-squashing in graph neural networks. PowerEmbed employs a layer-wise normalization approach that empowers message-passing neural networks (MPNNs) to effectively express the top-k eigenvectors of a graph while capturing crucial global spectral information. Remarkably, this technique exhibits adaptability by remaining agnostic to the specific topology of the graph, rendering it suitable for graphs characterized by both homophily and heterophily. Moreover, the authors seamlessly integrated PowerEmbed with an inception network. This synergistic combination is engineered to facilitate the learning of comprehensive representations, allowing for a seamless transition from local message-passing features to the incorporation of essential global spectral information. Notably, this strategic amalgamation is endowed with a provable capability to preemptively mitigate the challenges associated with over-smoothing and over-squashing.

**DGN** Beaini et al. introduced Directional Graph Networks (DGN) to combat over-squashing in Graph Neural Networks (GNNs). Over-squashing hinders GNNs, causing issues like over-smoothing and reduced discriminative power. They contend that over-squashing occurs in GNNs due to their incapacity to capture directional information within graphs, which constrains their grasp of graph structures and feature transformations. To resolve this, Beaini et al. presented globally consistent anisotropic kernels for GNNs, enabling them to incorporate directional flows based on graph topology. Their approach employs vector fields within the graph, utilizing low-frequency eigenvectors to define directional flows at each node. Many GNNs are insensitive to the order of neighbor features, causing multiple layers to focus on simple changes rather than learning higher-level features, contributing to over-squashing. In summary, Beaini et al.'s DGN model, through globally consistent anisotropic kernels and directional information, effectively addresses over-squashing. This empowers GNNs to comprehend local graph structures, perform meaningful feature transformations, and mitigate over-squashing's adverse effects.

## V Graph Transformers and other GNN Architectures

Graph transformers have gained substantial attention as an alternative approach to combating over-smoothing and over-squashing in the context of graph and computer vision domains [56, 57, 58]. This approach leverages the inherent strengths of transformer architectures:

**Over-smoothing Resilience:** Ying et al. [59] observed that transformers are less susceptible to over-smoothing compared to traditional Graph Neural Networks (GNNs). Their ability to model graph data efficiently contributes to mitigating the over-smoothing problem.

**Over-squashing Resilience:** Kreuzer et al. [60] highlighted the resilience of transformers to over-squashing. Transformers establish direct paths connecting distant nodes, which alleviates the over-squashing challenge.

However, it's worth noting that transformers have limitations, including significant computational and memory requirements due to the need for every node to attend to all others. This can make them less suitable for large-scale graph applications and may result in improper training leading to a blend of local and non-local interactions.

**Graph ViT\(\backslash\)Mixer MLP:** Xiaoxin [61] introduces a novel approach as an alternative to global attention mechanisms.
This approach draws inspiration from ViT\Mixer MLP architectures initially introduced in computer vision. The resulting "graph ViT\Mixer MLP" GNNs excel in capturing long-range dependencies while effectively mitigating over-squashing issues. They offer improved computational efficiency, speed, and memory advantages compared to existing models.

Gabrielsson et al. [62] employ Transformer-inspired positional encoding techniques to expand the receptive field of each node within a graph. Gabrielsson et al. [62] employ positional encoding techniques within a modified graph framework to effectively extend the receptive field of each node in Graph Neural Networks (GNNs) to encompass \(r\)-hop neighborhoods. The approach involves expanding the receptive fields by introducing modifications to the graph structure and incorporating positional encodings as both edge and node features. This innovative method differs from conventional graph transformers, which often replace the original graph topology with a complete graph and blend local and global information. Instead, Gabrielsson et al.'s approach facilitates the gradual expansion of the receptive field, allowing nodes to capture inductive biases by spanning from 1-hop neighborhood to \(r\)-hop neighborhoods. This strategic extension of the receptive field is designed to mitigate the challenges associated with over-squashing in GNNs.

**PASTEL** In their recent paper [53], Qingyun et al. tackle the issue of over-squashing in Graph Neural Networks (GNNs) by highlighting its association with topology imbalance. To combat this problem, they introduce PASTEL (Position-Aware STructurLE Learning). They redefine topology imbalance in terms of under-reaching and over-squashing and establish two quantitative metrics to evaluate these issues. PASTEL aims to enhance the intra-class connectivity of nodes in GNNs by optimizing information propagation paths. To achieve this, they employ an anchor-based position encoding mechanism to capture the relative positions of unlabeled nodes concerning labeled nodes. Additionally, a class-wise conflict measure, utilizing Group PageRank, quantifies the influence of labeled nodes from different classes, guiding edge weight adjustments to boost intra-class connectivity. PASTEL's contributions include a novel perspective on topology imbalance, improved modeling of node relationships through position encodings, and demonstrated effectiveness across diverse data annotation scenarios.

**A-DGN** Anti-Symmetric Deep Graph Network (A-DGN) is introduced by Gravina et al. in [51] as an innovative framework tailored to address the challenge of long-term information propagation in Deep Graph Networks (DGNs). This approach is devised by leveraging principles from ordinary differential equations (ODEs) and their connection to deep neural architectures. Gravina et al establishes theoretical conditions under which a stable and non-dissipative ODE system can be realized on graph structures, utilizing anti-symmetric weight matrices. Within the A-DGN framework, the A-DGN layer is formulated through the forward Euler discretization of the obtained graph ODE. This process enforces specific properties on the ODE system, resulting in the preservation of long-term dependencies between nodes within the graph and alleviating the problem of over-squashing in GNNs. Additionally, it mitigates issues related to gradient explosion or vanishing during the training process.

**RFGNN** In their paper [54], Rongqin et al. address the challenge of over-squashing in Graph Neural Networks (GNNs) by identifying its connection to message redundancy during the aggregation process. They observed that conventional GNNs often struggle to efficiently propagate long-length path information, which limits their capacity to learn graph similarities and support long-range interactions. To tackle this issue, they propose the Redundancy-Free Graph Neural Network (RFGNN). RFGNN utilizes a path-search-tree concept, constructed through breadth-first search, to eliminate
redundancy in message propagation. This ensures efficient information transmission without over-squashing. They also introduce the notion of extended paths (epaths) to capture complex graph structures and implement truncated ePaths trees (TPTs) for message-passing. RFGNN's de-redundancy technique balances epath influence, effectively mitigating over-squashing and enhancing GNNs' ability to capture structural information in original graphs. In summary, RFGNN improves structural information propagation by efficiently aggregating information through path-search trees, avoiding redundancy. The reduction of redundancy plays a crucial role in addressing the over-squashing challenge.

**GESN** The Graph Echo State Network (GESN), introduced by Tortorella and Mechelli in their work [46], represents a reservoir computing model designed to address specific challenges in node classification tasks, particularly within heterophilic graphs where nodes from the same class or category are typically positioned farther apart from each other, resulting in a lower density of intra-class edges. One distinctive feature of GESN is its training-free nature. This aspect is intriguing considering that GESN is a reservoir computing model. Reservoir computing models typically involve an untrained reservoir, which acts as a fixed, random structure to process input data. This training-free characteristic makes GESN an efficient and effective solution for node classification tasks, offering a promising approach to mitigate the issues of long-range message passing and over-squashing in heterophilic graphs.

Each of these approaches offers a unique perspective and set of techniques to address the challenges of over-squashing in graph-based machine learning models.

## VI Datasets

The common datasets employed for node and graph classification tasks in the models listed in Table I are presented in Table II, along with detailed dataset statistics. It's important to note that this list is not exhaustive, as there are numerous other datasets, including synthetic and large-scale real-world ones, utilized for various research purposes. Table II displays the statistics of the datasets used in this study, where \(H(G)\) represents the graph's homophily, as defined in [63], calculated as

\[H(G)=\frac{1}{|V|}\sum_{v\in V}\frac{\#v\text{'s neighbors with the same label as }v}{\#v\text{'s neighbors}}\]

For node classification tasks, we employ a diverse set of 12 datasets, encompassing graphs of varying sizes and characteristics.

Cora, CiteSeer, PubMed are paper citation networks. Node features are represented as bag-of-words from paper content, and the task is to classify the research topics. These datasets are characterized by high homophily. Film is constructed based on the co-occurrences of actors on the same Wikipedia page, categorized into five groups. It serves as a node classification task with a low homophily nature. TwitchDE constitutes a social network comprising German gamer accounts from Twitch, categorized as suitable for work or adult profiles. The task involves classifying the profiles. Tolkers is a collaboration network originating from the crowdsourcing platform Toloka. The objective here is to determine whether a user is active or not. Due to class imbalance, the evaluation metric is the area under the ROC curve. Cornell, Texas, Wisconsin are additional node classification tasks, each originating from university-related interactions. The Cornell dataset comprises research paper citation data. The Texas dataset represents friendships in a Texas college, and the Wisconsin dataset is derived from a university-related network. Node features and specific targets for these datasets can vary. Chameleon, Squirrel, Actor are also novel datasets introduced for node classification. Chameleon captures interactions within a university community. Squirrel is a network of interactions among squirrels in a park. The Actor dataset models collaborations among actors in the film industry. Each of these datasets presents unique characteristics and classification tasks.

For graph classification tasks, we utilize the following datasets: NCI-1 and NCI-109 datasets involve classifying molecules as cancerous or non-cancerous. Node input features are one-hot encodings of atom types, and edges represent chemical bonds. Reddit-B, Reddit-5K, Reddit-12K capture interactions between users in Reddit discussion threads. The task is to determine the type of subreddit a discussion belongs to. Collab comprises ego-networks from three distinct scientific collaboration fields. Unlike the previous datasets, Reddit tasks, and Collab, these datasets do not have node input features. Enzymes is a bioinformatics dataset for graph classification. It involves classifying enzymes based on their structures and functions. The BZR dataset is a small molecule dataset used for graph classification tasks. It is commonly employed for evaluating graph-based machine learning algorithms. MUTAG is another bioinformatics dataset for graph classification, primarily used for evaluating chemical informatics algorithms. The task is to predict mutagenicity. PTC is a bioinformatics dataset for graph classification, focusing on carcinogenicity prediction. The graphs represent chemical compounds. COX2 is a small molecule dataset, often used to assess graph-based machine learning models in chemistry-related tasks. The classification task is centered around predicting the inhibition of the COX-2 enzyme. Proteins is a bioinformatics dataset used for graph classification. The task is to classify proteins based on their functions.

In all these tasks, we intentionally avoid introducing structural input features such as node degrees or positional encodings. A summary of relevant dataset statistics is provided in Table II for reference.

## VII Conclusion

This survey has delved into the depths of over-squashing, unearthing its origins in information compression across distant nodes. We've journeyed through a diverse array of strategies aimed at mitigating its impact - from innovative graph rewiring methods and curvature-based approaches to spectral techniques and the promise of graph transformers. As we tre
this path, a nuanced interplay between over-smoothing and over-squashing has come into focus, demanding a balanced resolution. This exploration stands as a testament to the ongoing dialogue among researchers, driven by the pursuit of more refined and capable Graph Neural Networks. In closing, the quest to unravel over-squashing continues to be a beacon guiding our pursuit of more effective models, driven by the dynamic nature of graph data.

## Acknowledgment

I extend my heartfelt appreciation to Dr. Karmvir Singh Phogat for providing invaluable insights and essential feedback on the research problem explored in this article. His thoughtful comments significantly enriched the quality and lucidity of this study.
