A Spectral Interpretation of Redundancy in a Graph Reservoir

Anna Bison and Alessandro Sperduti · 2025

Read A Spectral Interpretation of Redundancy in a Graph Reservoir by Anna Bison and Alessandro Sperduti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12963.txt.

Introduction

Anna Bison and Alessandro Sperduti rethought in 2025 how graph reservoirs smooth signals, tying the effect to redundant random walks. Reservoir layers help train graph networks faster, but repeated smoothing washes signals toward low frequencies and erases detail. Their variant borrows a fairing filter from surface design in graphics. The filter smooths without shrinking, and it adapts to graphs through the Laplacian operator.

The paper's core is theory: tuning the filter's spectral coefficients equals dialing the weight of redundant walks on the graph. That reading explains when smoothing helps and when it harms. Trials inside a multiresolution graph network showed the approach has promise for tasks like graph classification. The authors frame controlled smoothing as a feature, not a bug. Future work can build architectures on the walk-based view.

Catalog record

CREATORAnna Bison and Alessandro Sperduti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12963

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Spectral Interpretation of Redundancy in a Graph Reservoir Anna Bison and Alessandro Sperduti Abstract Reservoir computing has been successfully applied to graphs as a preprocessing method to improve the training efficiency of Graph Neural Networks (GNNs). However, a common issue that arises when repeatedly applying layer operators on graphs is over-smoothing, which consists in the convergence of graph signals toward low-frequency components of the graph Laplacian. This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN), a spectral reservoir model, and proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics. This algorithm provides a pass-band spectral filter that allows smoothing without shrinkage, and it can be adapted to the graph setting through the Laplacian operator. Given its spectral formulation, this method naturally connects to GNN architectures for tasks where smoothing, when properly controlled, can be beneficial,such as graph classification. The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective. In particular, it shows how tuning the spectral coefficients can be interpreted as modulating the contribution of redundant random walks. Exploratory experiments based on the MRGNN architecture illustrate the potential of this approach and suggest promising directions for future research. Keywords: Reservoir Computing ⋅ \cdot Fairing algorithm ⋅ \cdot GNN 1 Introduction In recent years, Reservoir Computing (RC) has been successfully applied to learning in graph domains in order to reduce the training computational burden while maintaining excellent performances (see, for example, [ 1 , 2 , 10 ] ). In almost all the proposed RC models, the reservoir is based on convolution operators for graphs (e.g., the ones defined in [ 9 ] for Graph Convolutional Neural Networks) that inevitably lead to a smoothing effect on the embeddings of the nodes of the processed graphs. The smoothing effect can be a desirable property in tasks such as graph classification, since it filters node signals that have high local variation, often encoding local information, and selects low-frequency components, which are more likely to encode global information that is more important for this kind of task. For this reason, it could make sense to implement an algorithm that optimizes smoothing in a model that performs graph classification. Indeed, the main risk when dealing with smoothing filters for GNNs is the over-smoothing problem, extensively discussed in [ 12 ] , which consists in the exponential convergence of the node embeddings of a graph to the same vector, or to embeddings whose differences only depend on the node-degree distribution. In recent literature, some methods have been proposed to manage over-smoothing by acting on the input expression without altering the model definition, as in [ 11 ] . These kinds of methods may not solve the problem in cases where GNN layers are defined as low-pass filters, since they will behave like that independently of the input shape. In this work, we explore, mainly from a theoretical point of view, how the Fairing algorithm introduced in [ 5 ] relates to spectral-based GNNs, and in particular to the Multiresolution Reservoir Graph Neural Network (MRGNN), introduced in [ 10 ] . The main motivation for considering the Fairing algorithm hinges on the fact that it proposes a procedure to define a filter that selects not only the desired frequencies to dampen or amplify, but also the number of iterations needed to reach the desired result. Even though it was proposed almost twenty years before the definition of Graph Convolutional Networks (GCN) [ 9 ] , it effectively explains how to perform the equivalent of a convolution of degree- n , obtained by iterating n times a layer that is a degree-one polynomial of a spectral operator (which, in the case of graphs, can be chosen to be the symmetric Laplacian). The difference is that in the case of the Fairing algorithm, the parameters are tuned by the user, who, being familiar with spectral methods for signal processing, knows what is needed. In this work, these parameters will be presented from the perspective of random walks, as equivalent to controlling the weight with which specific walks contribute to the diffusion of signals through graph nodes. Based on this theoretical analysis, we propose a novel Fairing-based reservoir that we preliminary experiment within the MRGNN architecture, obtaining encouraging results. 2 Background Here we concisely present the definitions of the two conceptual assets that form the basis of our analysis. The MRGNN model [ 10 ] , focusing on reservoir computing, and the Fairing algorithm [ 5 ] . Despite their differences, they can be linked via a spectral perspective. 2.1 Notation Uppercase letters will refer to matrices, and the elements of a matrix X are indicated as [X]_{ij}=x_{ij} . Let G(V,E,(X,A)) be a graph, where V denotes the set of nodes, E denotes the set of edges. Nodes are referred to by their indices, i.e., i\in V denotes the i -th node, and (i,j)\in E indicates that there is an edge connecting node i and node j . X denotes the embedding matrix: its i -th row denotes features vector (embedding) of node i , and the j -th column denotes the graph scalar signal associated to the j -th feature. A denotes the adjacency matrix, whose elements a_{ij}=1\iff(i,j)\in E . D denotes the diagonal degree matrix. Let \Delta_{\text{sym}}=I-D^{-1/2}AD^{-1/2} be the symmetric normalized Laplacian. The set of first neighbours of node i is denoted with \mathcal{N}_{i} . 2.2 Multiresolution Reservoir Graph Neural Network The MRGNN is a supervised graph neural network model based on a variant of a reservoir computing model, a k -hop reservoir that is mathematically equivalent to evolve the input embedding matrix with a pass-band filter. In a typical RC model, recursive neurons are run until a precise condition is satisfied (either convergence or maximum number of iterations). In MRGNN instead, the reservoir consists in a forward non-linear model that extracts graph features up to the k -hop neighbourhood, called multiresolution features . Then, intermediate features extracted for all the neighbourhoods of intermediate levels up to the k -th are considered simultaneously, and linearly combined with a method that presents some analogies with a spectral approach. Specifically, the formal definition of the transformation implemented by the reservoir consists in k iterations of a convolution: H^{k,\mathcal{T}}=\begin{bmatrix}X,\sigma(\tilde{A}X),\sigma(\tilde{A}\sigma(\tilde{A}X)),\dots\end{bmatrix}=\begin{bmatrix}H^{\;k,\mathcal{T}}_{(0)},H^{\;k,\mathcal{T}}_{(1)},H^{\;k,\mathcal{T}}_{(2)},\dots,H^{\;k,\mathcal{T}}_{(k)}\end{bmatrix} where \sigma is the tanh activation function, \tilde{A}=\mathcal{T}(A) is a function of the adjacency matrix and H^{\;k,\mathcal{T}}_{(i)} represents the embedding matrix of node representations where the j -th one is obtained by convolving signals from nodes connected through a path of length i from the j -th node. Finally, a readout function is implemented taking in input these multiresolution features and performing the final classification or regression task. In the paper, different definitions of the readout function, spanning from linear model to neural network are analyzed. In the experimental evaluations presented in this work, we considered only the readout architecture with two fully connected layers, which corresponds to the case q=2 as defined in the original MRGNN paper. For further theoretical details on other components of the original model that are not essential for understanding the next sections, refer to the original paper. 2.3 Fairing

Read the complete text