Renormalized Graph Neural Networks
Graph Neural Networks (GNNs) have become essential for studying complex data,
particularly when represented as graphs. Their value is underpinned by their
ability to reflect the intricacies of numerous areas, ranging from social to
biological networks. GNNs can grapple with non-linear behaviors, emerging
patterns, and complex connections; these are also typical characteristics of
complex systems. The renormalization group (RG) theory has emerged as the
language for studying complex systems. It is recognized as the preferred lens
through which to study complex systems, offering a framework that can untangle
their intricate dynamics. Despite the clear benefits of integrating RG theory
with GNNs, no existing methods have ventured into this promising territory.
This paper proposes a new approach that applies RG theory to devise a novel
graph rewiring to improve GNNs' performance on graph-related tasks. We support
our proposal with extensive experiments on standard benchmarks and baselines.
The results demonstrate the effectiveness of our method and its potential to
remedy the current limitations of GNNs. Finally, this paper marks the beginning
of a new research direction. This path combines the theoretical foundations of
RG, the magnifying glass of complex systems, with the structural capabilities
of GNNs. By doing so, we aim to enhance the potential of GNNs in modeling and
unraveling the complexities inherent in diverse systems.
Francesco Caso, Giovanni Trappolini, Andrea Bacciu, Pietro Liò, Fabrizio Silvestri
# Renormalized Graph Neural Networks

###### Abstract

Graph Neural Networks (GNNs) have become essential for studying complex data, particularly when represented as graphs. Their value is underpinned by their ability to reflect the intricacies of numerous areas, ranging from social to biological networks. GNNs can grapple with non-linear behaviors, emerging patterns, and complex connections; these are also typical characteristics of complex systems. The renormalization group (RG) theory has emerged as the language for studying complex systems. It is recognized as the preferred lens through which to study complex systems, offering a framework that can untangle their intricate dynamics. Despite the clear benefits of integrating RG theory with GNNs, no existing methods have ventured into this promising territory. This paper proposes a new approach that applies RG theory to devise a novel graph rewiring to improve GNNs' performance on graph-related tasks. We support our proposal with extensive experiments on standard benchmarks and baselines. The results demonstrate the effectiveness of our method and its potential to remedy the current limitations of GNNs. Finally, this paper marks the beginning of a new research direction. This path combines the theoretical foundations of RG, the magnifying glass of complex systems, with the structural capabilities of GNNs. By doing so, we aim to enhance the potential of GNNs in modeling and unraveling the complexities inherent in diverse systems.

## 1 Introduction

Graph Neural Networks (GNNs) have emerged as a powerful tool for analyzing and modeling complex relational data. Unlike traditional neural networks that operate on grid-like structures such as images (Li et al., 2021) or sequences (Vaswani et al., 2017), GNNs are designed specifically for data represented as graphs. Graphs are mathematical structures composed of nodes (representing entities) and edges (representing relationships or connections between entities). Examples of graph-structured data abound in various domains, including social networks, citation networks, biological networks, and recommendation systems Zhang et al. (2019); Eraslan et al. (2019); Zhou et al. (2020). GNNs have gained significant attention in recent years due to their ability to effectively capture and exploit
the inherent structural information encoded within graphs. They extend traditional neural networks by incorporating graph-based operations, allowing them to learn from both the node attributes and the underlying graph topology. This enables GNNs to model complex relationships (systems), propagate information between interconnected nodes, and make predictions or classifications based on the learned representations (Kipf and Welling, 2016; Velickovic et al., 2017). The importance of GNNs lies in their versatility and broad applicability across different domains. In social network analysis, GNNs can reveal patterns of influence, community structure, and information diffusion. In biological research, GNNs have proven valuable for protein-protein interaction prediction, drug discovery, and gene expression analysis. In recommendation systems, GNNs can leverage the graph structure to capture user-item interactions, leading to more accurate personalized recommendations. This makes GNNs particularly well-suited for tasks such as node classification, link prediction, graph generation, and graph-level classification.

Despite their impressive capabilities, Graph Neural Networks (GNNs) also exhibit certain limitations that the research community has been studying. Three significant challenges faced by GNNs are over-squashing, under-reaching, and over-smoothing (Alon and Yahav, 2020; Topping et al., 2021; Di Giovanni et al., 2023; Rusch et al., 2023). Over-squashing refers to the phenomenon where the GNN is unable to propagate information between distant nodes due to the fixed size of the hidden representation. Under-reaching, on the other hand, refers to the limited ability of GNNs to effectively capture and propagate information across dependencies whose range is higher than the number of GNN layers. Finally, Oversmoothing is the tendency to get similar representations between different nodes when using a high number of GNN layers.

Research on overcoming GNNs' limitations is critical, as GNNs' ability to effectively capture and analyze graph-structured data makes them a valuable tool for modeling and understanding complex systems. Complex systems, i.e., systems composed of many interacting components, exist in various domains such as social networks, biological networks, transportation networks, and communication networks (Cavagna et al., 2010; Hidalgo, 2021).

Complex systems are characterized by their non-linear dynamics, emergent behavior, and intricate interdependencies, even between different scales. This has posed significant challenges to understanding and analyzing their underlying principles, and in this context, the theory of the renormalization group (RG) has naturally emerged as a powerful language to deal with such systems (Lepage, 1989; Fisher, 1974; Delamotte, 2004). RG provides a framework for systematically studying the behavior of complex systems across multiple scales, from microscopic to macroscopic. It allows researchers to identify and analyze the relevant degrees of freedom, discard irrelevant details, and uncover the universal properties that govern the system's behavior. By employing RG techniques, researchers can gain a deeper understanding of collective behavior, tackling arduous problems like critical phenomena (Toner et al., 2018; Fisher, 1974).

Surprisingly enough, even though graph neural networks aim to tract complex systems and the renormalization group has emerged as a sort of magnifying glass (even though zooming-out) for studying those same complex systems, to the best of our knowledge, there are no methods that employ renormalization group theory for graph neural networks.

The aim of this paper is precisely to fill this gap. Namely, borrowing from the theory of the renormalization group, we develop a method that represents the input graph at a different granularity. Instead of being obliged to consider only the smallest granularity, where each node and edge in the graph is visible, we allow the GNN to also look at larger granularities, where nodes are grouped into clusters, and it's possible to study the relations between these clusters; in order to analyze the large-scale behavior of complex networks, such as the Internet, social networks, or biological networks.

Our contributions are: (a) To the best of our knowledge, we are the first to consider renormalization group theory for graph neural networks. (b) We lay out an extensive experimental section to back our claims, proving that our method improves performance significantly on standard benchmarks and baselines. (c) Finally, we hope to lay out the foundation for a new research agenda that aims to borrow theoretical properties from the renormalization group to enhance current GNNs architectures.
## 2 Renormalization of a graph

### Background

We define a graph to be \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) where \(\mathcal{V}\) is the set of nodes of the graph, and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is the set of edges. We will consider only unweighted graphs so the set of edges can also be represented through an adjacency matrix \(A\in\mathcal{R}^{|\mathcal{V}|\times|\mathcal{V}|}\), whose elements are

\[A_{ij}=\begin{cases}1&(i,j)\in\mathcal{E}\\ 0&(i,j)\notin\mathcal{E}\end{cases}. \tag{1}\]

We consider the Laplacian matrix defined as

\[L_{ij}=[(\delta_{ij}\sum_{k}A_{ik})-A_{ij}] \tag{2}\]

where \(\delta_{ij}\) is the Kronecker delta function. The theory we propose is limited to undirected graphs and we define the neighborhood of node \(u\) to be

\[\mathcal{N}_{u}=\{v|(u,v)\in\mathcal{E}\}\quad. \tag{3}\]

We consider for each node \(u\in\mathcal{V}\) a vector of features \(x_{u}\in\mathbb{R}^{k}\) and, as in Velickovic (2023), we represent the multiset of all the features of neighbor nodes as

\[X_{\mathcal{N}_{u}}=\{\{x_{v}|v\in\mathcal{N}_{u}\}\}\quad. \tag{4}\]

We will not consider edge features or graph features. We will also limit ourselves to considering graphs with a single connected component, in order to fulfill the ergodic hypothesis. Rewiring the graph means changing the set of neighborhoods \(\{\mathcal{N}_{u}\}_{u\in\mathcal{V}}\) or, equivalently, changing the adjacency matrix.

For what concerns GNNs, we recognize that the main paradigm at their basis is that of message passing and, as in Bronstein et al. (2021), we write the generic update function of a GNN as

\[h_{u}=\phi(x_{u},\bigoplus_{v\in\mathcal{N}_{u}}\psi(x_{u},x_{v})) \tag{5}\]

where \(\phi\) and \(\psi\) are generic neural networks and \(\bigoplus\) is a permutation-invariant aggregator. In the following, we will consider two possible aggregators for \(\bigoplus\): \(\sum\) and average. While equation 5 is exactly the message passing update rule, the attentional and convolutional ones can be obtained with a suitable definition of \(\psi(x_{u},x_{v})\):

\[h_{u}=\phi(x_{u},\bigoplus_{v\in\mathcal{N}_{u}}c_{vu}\psi^{\prime}(x_{v})) \quad(\text{Convolutional}), \tag{6}\]

\[h_{u}=\phi(x_{u},\bigoplus_{v\in\mathcal{N}_{u}}a(x_{u},x_{v})\psi^{\prime}(x _{v}))\quad(\text{Attentional}). \tag{7}\]

Simplifying, we could also write

\[h_{u}=\phi^{\prime}(x_{u},X_{\mathcal{N}_{u}}) \tag{8}\]

for some function \(\phi^{\prime}\), meaning that the representation of node \(u\) is a function of the features of the node itself and of the features of the neighbor nodes.

### Real space decimation.

Villegas et al. (2022, 2023) showed that information diffusion in networks can unravel clusters of nodes connected by strong information communicability at each time \(\tau\). In particular, since we are assuming the graph to be connected and undirected, we can compute the normalized sum of all the diffusion trajectories connecting node \(i\) to node \(j\):

\[\rho(\tau)_{ij}=\frac{(e^{-\tau L})_{ij}}{Tr(e^{-\tau L})}\quad. \tag{9}\]
Two nodes are considered to reciprocally process the same information when the sum of the diffusion trajectories between them reaches a greater than or equal value to the sum of auto-diffusion trajectories of one of the two nodes. Thus, if we define

\[\rho^{\prime}_{ij}=\frac{\rho_{ij}}{\min(\rho_{ii},\rho_{jj})}\quad, \tag{10}\]

the meta graph is defined as

\[\zeta_{ij}=\Theta(\rho^{\prime}_{ij}-1) \tag{11}\]

where \(\Theta\) is the Heaviside step function. The element \(\zeta_{ij}\) is equal to \(1\) if the nodes \(i\) and \(j\) belong to the same supernode, and is equal to \(0\) otherwise. Notice that since equation 10 is a ratio, it's not necessary to compute the denominator in equation 9. The decimation procedure in real space requires substituting each cluster of nodes, as identified by the meta graph \(\zeta\), with a single supernode whose edges are all the edges of the original constituent nodes that go outside the cluster. We call the graph composed by the supernodes the decimated graph. We call \(\mathcal{W}\) the set of supernodes, similarly to how \(\mathcal{V}\) is the set of nodes in the original graph. Let \(\mathcal{Z}_{w}\) be the set of nodes of the original graph that compose the supernode \(w\in\mathcal{W}\) in the decimated graph. Finally, let \(\mathcal{M}_{w}\) for \(w\in\mathcal{W}\) be the neighborhood of \(w\) in the decimated graph. Notice that the generic update function of a GNN, equation 5, applied to the decimated graph would yield:

\[h_{w}=\phi(x_{w},\bigoplus_{v\in\mathcal{M}_{w}}\psi(x_{w},x_{v}))\quad. \tag{12}\]

Similarly to equation 8, we could also write

\[h_{w}=\phi^{\prime}(x_{w},X_{\mathcal{M}_{w}})\quad. \tag{13}\]

Nonetheless, not only Laplacian Renormalization Group (LRG) doesn't explain how to renormalize the features of each original node into the features of the supernodes, but such a renormalization of the features should be learnable, e.g. when renormalizing a molecule, if the task is "count how many hydrogens there are", you want the features of the supernode to lose all the information unrelated to hydrogens, whilst if it is "predict its structure", you may want the renormalized features to retain some of the information from all the atoms in the supernode. Moreover, saving the information of all the original nodes in the vectors associated with their supernodes could increase over-squashing. For these reasons, we propose to use LRG from a different, almost dual, point of view. We look at the decimation procedure as a rewiring one. In fact, notice that implying that the features of the supernodes are functions of the features of their constituent original nodes, we could rewrite equation 13 as

\[h_{w}=\phi^{\prime\prime}(X_{\mathcal{Z}_{w}},X_{\mathcal{Z}_{v},v\in \mathcal{M}_{w}})\quad, \tag{14}\]

or equivalently

\[h_{w}=\phi^{\prime\prime\prime}(x_{u,u\in\mathcal{Z}_{w}},X_{\mathcal{Z}_{w} \backslash u\cup\mathcal{Z}_{v},v\in\mathcal{M}_{w}})\quad, \tag{15}\]

where \(\phi,\phi^{\prime},\phi^{\prime\prime},\phi^{\prime\prime\prime}\) are not derivatives but different functions. In this way, the update on the decimated graph can be seen as an update on a rewired graph, i.e. on a graph with a different set of neighborhoods.

### Our Rewiring

In order to rewire the graph, we identify the clusters that form the supernodes of the decimated graph. Then, instead of reducing the number of nodes, we increase the number of edges. Specifically, we require all the nodes belonging to the same cluster to share the same incoming and outgoing edges (Fig. 1). This is obtained by computing a new adjacency matrix \(A^{*}\) whose columns are given by

\[A^{*}_{:,i}=\Theta(\sum_{j}\zeta_{i,j}A_{:,j})\quad, \tag{16}\]

and whose rows are given by

\[A^{*}_{i,:}=\Theta(\sum_{j}\zeta_{i,j}A_{j,:})\quad. \tag{17}\]

It's easy to see that in this way, the neighborhood of \(u\) in the rewired graph is

\[\mathcal{N}^{\prime}_{u}=(\mathcal{Z}_{w}\backslash u)\cup\bigcup_{v\in \mathcal{M}_{w}}\mathcal{Z}_{v}\quad. \tag{18}\]
**Theorem 2.1**: _Computing the generic GNN update function, equation 5, on a node of the rewired graph, with the aggregator \(\bigoplus\) chosen as the sum or the average operator and with \(\phi(x,y)=\sigma_{\phi}(W^{(1)}x+W^{(2)}y+b_{\phi})\) where \(\sigma_{\phi}\) is an activation function and \(W^{(1)}\) has linearly independent rows, is equivalent to computing a GNN update function on a node of the decimated graph._

The proof of the theorem is given in the supplementary material, see Appendix A, but intuition is given by the fact that equation 8 becomes equation 15: this means that the representation of node \(u\) depends on the features of node \(u\) itself, the features of the other nodes that are in the same supernode and the features of the nodes that compose the neighbor supernodes. Theorem 2.1 means that the rewiring procedure effectively allows the GNN to act as if it was looking at the decimated graph obtained through LRG when computing a node representation. Moreover, the features of the original nodes are not saved in a different vector associated with the supernode, which could have increased over-squashing. Finally, the equivalence allows us not to compute the renormalized features of the supernodes. In fact, they are implicitly represented by functions of the features of the original nodes, with some of the parameters learnable, thus allowing for task-dependent renormalization.

## 3 Experimental Setup

### Datasets

We run our experiments on the following datasets:

We use the _Cora_ dataset (McCallum et al., 2000), which contains 2708 scientific publications. These publications are classified into one of seven classes, and the citation network contains 5429 links. Each publication in the dataset is described by a 0/1-valued word vector indicating the absence or presence of the corresponding word from the dictionary. The dictionary comprises 1433 unique words.

The _PubMed_ dataset (Namata et al., 2012) is another source we test on. This set includes 19717 scientific publications from the PubMed database, all of which are related to diabetes and are classified into one of three classes. The citation network here consists of 44338 links, and each publication in the dataset is described by a Term Frequency-Inverse Document Frequency (TF-IDF) word vector from a dictionary of 500 unique words.

We are also utilizing the _Citeseer_(Giles et al., 1998) dataset, which encompasses 3327 scientific publications classified into six classes. The citation network has 4732 links. Each publication in the dataset is described by a binary word vector indicating the absence or presence of the corresponding word from the dictionary, which consists of 3703 unique words.

Finally, we are using the _Amazon Photo_ dataset (McAuley et al., 2015; Shchur et al., 2018). This is a subset of the Amazon co-purchase graph that contains 7650 products with 119043 edges. Each

Figure 1: A visualization of the proposed rewiring procedure. The nodes of the original graph, left, are clustered in three supernodes, center. The graph is rewired in such a way that nodes in the same supernode share the same incoming and outgoing edges, right.
product in the dataset is described by a bag-of-words encoding of its reviews. The graph is formed based on the "Also Bought" feature on Amazon, where an edge from item A to item B implies that item A is frequently co-purchased with item B.

### Model

During our testing process, we utilize a 2-layer graph encoder, e.g, GCN (Kipf and Welling, 2016) and GAT (Velickovic et al., 2017), as the fundamental architecture. Building upon this foundation, we create multiple variations. Specifically, we develop two configurations: one referred to as "dual" and the other as "mono". In the "mono" case, we input a single graph, whether it has been rewired or not, into the network. Instead, to encode the graphs at two different scales, we propose the "dual" setting, where we feed two graphs into the network: one that has been renormalized and another that remains unchanged, or twice the latter in the vanilla setting. The information from both graphs is then combined to generate the final prediction. To train our model, we do not perform hyperparameter tuning, and we opt instead for standard values used in the literature. In fact, we use the Categorical Cross-Entropy, Adam Optimizer (Kingma and Ba, 2014), with a standard learning rate of 0.0001, over 200 epochs, using the highest accuracy achieved on the validation set as our checkpointing strategy. We perform our experiments on a workstation equipped with an Intel Core i9-10940X (14-core CPU running at 3.3GHz) and 256GB of RAM, and a single Nvidia RTX A6000 with 48GB of VRAM.

### Methods

We compare our method against Graph Diffusion Convolution (GDC) (Gasteiger et al., 2019). GDC substitutes the adjacency matrix with one obtained through a generalized diffusion process on graphs. We consider two generalized diffusion processes, presented in (Gasteiger et al., 2019), for which closed-form solutions are available: Personalized PageRank (PPR) and the heat kernel diffusion. GDC proposes to substitute the adjacency matrix with a sparsified version of \(S=\sum_{k=0}^{\infty}\theta_{k}T^{k}\) where \(T\) and \(\{\theta_{k}\}\) must satisfy the constraint necessary for \(S\) to converge. The set \(\{\theta_{k}\}\) is given by the chosen diffusion process, either PPR or heat kernel in our case. Notice that GDC has been shown to act like a low-pass filter, and similarly, LRG, in the approach _a la Wilson_, disregards the highest Laplacian eigenvalues and eigenvectors.

### Task & Evaluation Metrics

We train, validate, and test on the task of node classification. We report the results in terms of the Accuracy metric on the (multi) node classification task for each dataset introduced in Section 3.1. We also include standard errors for the accuracy term in our results. These errors are obtained with a bootstrap procedure and, in particular, using a bias-corrected and accelerated bootstrap.

## 4 Experimental Results

In this section, we present comprehensive results in terms of accuracy on four different popular benchmarks, which serve as crucial evaluation standards in the field. These benchmarks provide a rigorous testing ground for assessing the performance of various methodologies. In our investigation, we compare six different methodologies, aiming to identify the most effective approach for the given tasks.

One of the methodologies we consider is the Vanilla method, which represents the plain graph at the "default" scale. This serves as our baseline for comparison. Additionally, we examine the performance of two competitor methodologies, namely Heat and PPR, as identified in the work by Gasteiger et al. (2019) on diffusion-based algorithms.

To gain further insights, we explore the effects of varying scales (\(\tau\)) within our own methodology. By considering different scales, we can evaluate how our approach performs under different conditions. The results we obtained clearly demonstrate the superiority of our method across all the datasets considered. Notably, the Cora dataset exhibits the largest nominal markup, indicating the high effectiveness of our methodology in this particular case.

Another intriguing observation is the variability of the optimal scale (\(\tau\)) across different datasets, in accordance with the LRG theory which states that different networks have different characteristic
scales: we find that the best performing \(\tau\) value varies depending on the dataset under consideration. Furthermore, it appears that when a larger \(\tau\) produces the best performance, the Heat and PPR methodologies struggle to achieve comparable results.

In light of these findings, we plan to conduct further studies to unravel the intricate connection between the time scale (\(\tau\)) and its dependence on specific datasets and tasks. This exploration will enable us to gain a deeper understanding of the underlying dynamics and uncover valuable insights for future research.

Overall, our results highlight the high quality and efficacy of the proposed methodology. We observe a significant lift in performance, reaching up to 12.1%. This improvement underscores the value of our approach and its potential impact on the broader research community and related applications.

## 5 Related works

Graph Neural NetworksGraph neural networks (GNNs) are a class of deep learning models designed to operate on graph data structures, such as social networks (Bruna and Li, 2017), chemical compounds (Zitnik et al., 2018; Long et al., 2020), or traffic networks (Guo et al., 2019; Yu et al., 2017). Unlike traditional neural networks, which operate on grid-like structures, GNNs can model complex relationships and dependencies among nodes and edges in a graph. GNNs have shown promising results in various applications, including node classification, link prediction, and graph generation. One of the most popular GNN models is the Graph Convolutional Network (GCN) proposed by Kipf and Welling (2016), which uses a localized convolutional operation to aggregate information from neighboring nodes. Other notable GNN models include GraphSAGE (Hamilton et al., 2017) and GAT (Velickovic et al., 2017), which employ different aggregation strategies and attention mechanisms to capture the graph structure. Overall, GNNs have become an active area of research in machine learning and have the potential to transform various fields that involve graph data; other than a vast field of research. For a broader perspective, we refer the reader to the following surveys Zhou et al. (2020) and Wu et al. (2020).

Renormalization GroupThe Renormalization group (RG) is a powerful framework describing the change in the mathematical representation of a system when looked at different scales. RG was first introduced in quantum electrodynamics (Bethe, 1947) to remove the infinities that arise from the small-scale description of the system (we refer the reader to the following surveys Lepage (1989) and Delamotte (2004)). After its first appearance in quantum electrodynamics, the RG reached full

\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & \multicolumn{4}{c}{**Datasets**} \\
**Method** & **Cliteseer** & **Cora** & **Photo** & **Pubmed** \\ \hline Vanilla & 0.683 \({}^{\star}\)\(\pm\) 0.004 & 0.739 \({}^{\dagger}\)\(\pm\) 0.005 & 0.942 \({}^{\dagger}\)\(\pm\) 0.005 & 0.738 \({}^{\dagger}\)\(\pm\) 0.002 \\ Vanilla (dual) & 0.683 \({}^{\dagger}\)\(\pm\) 0.004 & 0.728 \({}^{\dagger}\)\(\pm\) 0.005 & 0.947 \({}^{\star}\)\(\pm\) 0.005 & 0.752 \({}^{\star}\)\(\pm\) 0.002 \\ Heat & 0.725 \({}^{\star}\)\(\pm\) 0.005 & 0.790 \({}^{\star}\)\(\pm\) 0.006 & 0.939 \({}^{\star}\)\(\pm\) 0.005 & 0.738 \({}^{\star}\)\(\pm\) 0.002 \\ Heat (dual) & 0.719 \({}^{\dagger}\)\(\pm\) 0.005 & 0.790\({}^{\star}\)\(\pm\) 0.006 & **0.948 \({}^{\star}\)\(\pm\)** 0.005 & 0.762 \({}^{\star}\)\(\pm\) 0.002 \\ PPR & 0.722 \({}^{\star}\)\(\pm\) 0.005 & 0.745 \({}^{\dagger}\)\(\pm\) 0.005 & 0.941\({}^{\star}\)\(\pm\) 0.005 & 0.740 \({}^{\star}\)\(\pm\) 0.002 \\ PPR (dual) & 0.728 \({}^{\dagger}\)\(\pm\) 0.005 & 0.780 \({}^{\star}\)\(\pm\) 0.006 & 0.944\({}^{\star}\)\(\pm\) 0.005 & 0.764 \({}^{\star}\)\(\pm\) 0.002 \\ \hline
**Ours** (\(\tau\)-1) & 0.681 \({}^{\dagger}\)\(\pm\) 0.004 & 0.746 \({}^{\dagger}\)\(\pm\) 0.005 & 0.811 \({}^{\dagger}\)\(\pm\) 0.004 & 0.778 \({}^{\dagger}\)\(\pm\) 0.002 \\
**Ours** (\(\tau\)-1) (dual) & 0.716 \({}^{\dagger}\)\(\pm\) 0.005 & 0.766 \({}^{\star}\)\(\pm\) 0.005 & 0.944 \({}^{\star}\)\(\pm\) 0.005 & **0.781 \({}^{\star}\)\(\pm\)** 0.002 \\
**Ours** (\(\tau\)-2) & 0.707 \({}^{\star}\)\(\pm\) 0.004 & 0.750 \({}^{\dagger}\)\(\pm\) 0.005 & 0.768 \({}^{\dagger}\)\(\pm\) 0.003 & 0.767 \({}^{\star}\)\(\pm\) 0.002 \\
**Ours** (\(\tau\)-2) (dual) & **0.731**\({}^{\dagger}\)\(\pm\) 0.005 & 0.774 \({}^{\dagger}\)\(\pm\) 0.006 & **0.948 \({}^{\star}\)\(\pm\)** 0.005 & 0.773 \({}^{\star}\)\(\pm\) 0.002 \\
**Ours** (\(\tau\)-4) & 0.709 \({}^{\star}\)\(\pm\) 0.004 & 0.693 \({}^{\dagger}\)\(\pm\) 0.004 & 0.717 \({}^{\dagger}\)\(\pm\) 0.002 & 0.752 \({}^{\star}\)\(\pm\) 0.002 \\
**Ours** (\(\tau\)-4) (dual) & 0.726 \({}^{\dagger}\)\(\pm\) 0.005 & **0.818 \({}^{\star}\)\(\pm\)** 0.006 & **0.948 \({}^{\star}\)\(\pm\)** 0.005 & 0.775 \({}^{\star}\)\(\pm\) 0.002 \\ \hline \hline \end{tabular}
\end{table}
Table 1: We report results on 6 different methodologies and 4 popular dataset benchmarks. Results are reported in terms of accuracy on the multi-classification task. We also provide bootstrapped confidence intervals for the results. As the experimental results indicate, our rewiring procedure is highly effective in terms of performance and a valid method to improve current graph neural network techniques. The \(\dagger\) symbol indicates that the result has been produced by a GAT, while the \(\star\) symbol indicates that a GCN was used.
maturity with the work on continuous phase transitions by Wilson and Kogut (1974) (we refer the reader to the following survey (Fisher, 1974)). Wilson's approach was that of eliminating microscopic degrees of freedom. This was paralleled by Kadanoff's intuition (Kadanoff, 1966) that the strong correlation acting in the critical regime could allow for describing the system using blocks of the initial smaller components. Despite the challenges posed by their strong topological heterogeneity, decades later a renormalization group for complex networks was ultimately found in the Laplacian Renormalization Group (LRG) (Villegas et al., 2023, 2022). Such an approach was able to overcome the limitations of previous attempts (Garcia-Perez et al., 2018) like the impossibility to reconnect it to ordinary renormalization when applied to regular lattices. To our knowledge, the present paper is the first attempt to use LRG in combination with GNNs. Nonetheless, since RG is deeply connected with diffusion processes, it's important to remember that diffusion processes have been used as a pre-processing step in graph learning (Gasteiger et al., 2018, 2019).

## 6 Limitations

Some of the limitations of the proposed procedure are difficult to overcome since the LRG theory that we used suffers from the same constraints: it requires working with undirected graphs with a single connected component. Similarly, the equivalence between the GNN update function on the rewired graph and on the decimated one was proved only for an aggregator of the \(\sum\) or average type, whilst it seems improbable that such an equivalence could be extended to aggregators of the min and max type, which as well are possible choices. We as well defined the procedure only for unweighted graphs, not considering, for example, edge features, even though this seems a problem that we could tackle in future works. Finally, what we believe is the main limitation of the proposed procedure is the fact that it increases the density of the edges, sometimes to such a degree that it requires reducing the dimensionality of the node features in order to train the models. When we faced this issue in some of the experiments, the results were obtained by reducing the dimensionality of the node features to the highest power of 2 that fitted into memory. Limiting the increase in edge density will most probably be the principal focus of future work in order to make the procedure easily implementable in practical situations.

## 7 Conclusion

We propose a way of integrating the renormalization group (RG) with current GNN practices. We prove that our rewiring allows the GNN to look at the input graph with different granularities. The proposed implementation also frees from the necessity of defining a renormalization of the features, making it learnable, and it does so in such a way as not to provoke over-squashing. We experimentally verify that by "coarse-graining" the network, or reducing its complexity by grouping nodes, one can gain insights into its overall structure and behavior. This approach has been verified on different benchmarks and baselines and will allow researchers to understand how the properties of these networks change as we zoom in or out: for example helping to identify universal behaviors, where different systems exhibit similar behaviors at large scales.

Our method has the potential to solve some of the GNNs' most severe limitations. In particular, we claim our method can alleviate the problems of under-reaching and over-squashing; both of them are in fact related to propagating information between distant nodes and, zooming out, we can vary the distance through the parameter \(\tau\). Furthermore, it could also be seen as a filter on the graph laplacian higher frequencies, significantly reducing the noise problem that naturally emerges in GNNs.

We hope to lay out the foundation for a new research agenda that aims to borrow theoretical properties from the renormalization group to enhance current GNNs architecture but we as well believe that it could be used in many other problems of both geometric deep learning and general deep learning.

## 8 Acknowledgements

This work was partially supported by projects FAIR (PE0000013) and SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU. Supported also by the ERC Advanced Grant 788893 AMDROMA, EC H2020RIA project "SoBigData++" (871042), PNRR MUR project IR0000013-SoBigData.it.