Organizations: National Engineering School of Sousse, University of Sousse, LATIS – Laboratory of Advanced Technology and Intelligent Systems, 4023, Sousse, Tunisia. · BASIRA Lab, Imperial-X and Department of Computing, Imperial College London, London, UK.
Message passing is a core mechanism in Graph Neural Networks (GNNs), enabling the iterative update of node embeddings by aggregating information from neighboring nodes. Graph Convolutional Networks (GCNs) exemplify this approach by adapting convolutional operations for graph structures, allowing features from adjacent nodes to be combined effectively. However, GCNs encounter challenges with complex or dynamic data. Capturing long-range dependencies often requires deeper layers, which not only increase computational costs but also lead to over-smoothing, where node embeddings become indistinguishable. To overcome these challenges, reservoir computing has been integrated into GNNs, leveraging iterative message-passing dynamics for stable information propagation without extensive parameter tuning. Despite its promise, existing reservoir-based models lack structured convolutional mechanisms, limiting their ability to accurately aggregate multi-hop neighborhood information. To address these limitations, we propose RGC-Net (Reservoir-based Graph Convolutional Network), which integrates reservoir dynamics with structured graph convolution. Key contributions include: (i) a reimagined convolutional framework with fixed-random reservoir weights and a leaky integrator to enhance feature retention; (ii) a robust, adaptable model for graph classification; and (iii) an RGC-Net-powered transformer for graph generation with application to dynamic brain connectivity. Extensive experiments show RGC-Net achieves state-of-the-art performance in classification and generative tasks, including brain graph evolution, with faster convergence and mitigated over-smoothing. Our source code is available at https://github.com/basiralab/RGC-Net.
Figures & tables
Fig. 1: Echo State Network (ESN) architecture with an input layer, a fixed-weight reservoir, and an output layer. Input weights Win∈Rnres×nin map the input vector u(t)∈Rnin into the reservoir. The reservoir uses recurrent weights Wres∈Rnres×nres to capture temporal dependencies. The output layer, with weights Wout∈Rnout×nres , generates the output vector y(t+1)∈Rnout , with only Wout being trainable.
Fig. 2: Proposed RGC-Net architecture, comprising three components: a non-trainable input layer, a graph convolutional reservoir, and a trainable linear output layer.
Fig. 3: RGC-Net Architecture for Graph Classification. The input graph Ginp , defined by its adjacency matrix A and node feature matrix X , is processed through RGC-Net. It begins with an Input Layer that transforms node features using fixed weights. This is followed by the Graph Convolutional Reservoir , where iterative self-iterations capture neighborhood information. The Linear Layer then projects these embeddings to a higher feature space, followed by Batch Normalization , ReLU , Average Global Pooling , and a Feed-Forward Network (FFN) . The SoftMax layer produces the final output label Y′
Fig. 4: Architecture of the RGC-Net-Transformer model for temporal graph generation. The model employs RGC-Net layers within encoder and decoder networks to capture dynamic connectivity patterns and predict future graph structures. The encoder processes the input graph Gt0(At0,Xt0) through Graph Attention (GAT), Batch Normalization, and RGC-Net layers, generating a latent representation Z . This is then decoded to reconstruct the predicted adjacency matrix At1 , utilizing reservoir-based layers to retain features across time steps.
Notation
Definition
Gst={Ast,Xst}
graph of subject s at time point t consists as pairs
of adjacency matrix Ast and node feature matrix Xst
Ast
adjacency matrix of subject s at time point t
A^st
predicted adjacency matrix of subject s at time point t
Aij
weight of the edge between node i and node j
Xst
node features
TABLE I: Major Mathematical Notations
Hyperparameter
Grid Values
Learning rate ( lr )
0.01, 0.005, 0.001
Scheduler step size
500, 200, 100
Reservoir iteration* ( k )
3, 2, 1
Reservoir leaky rate* ( α )
1, 0.9, 0.8, 0.7
TABLE II: Hyperparameter values for model selection via grid search
Dataset
n-layers
GAT
GCN
GraphSAGE
GIN
GraphESN
RGC-Net
TRGC-Net
MUTAG
1
0.7446 ± 0.04
0.7500 ± 0.01
0.7446 ± 0.04
0.8300 ± 0.06
0.6433 ± 0.0071
0.8726 ± 0.01
0.8671 ± 0.05
2
0.7715 ± 0.07
0.8355 ± 0.05
0.7024 ± 0.08
0.7710 ± 0.04
0.6479 ± 0.0064
0.8600 ± 0.01
0.8462 ± 0.09
3
0.7661 ± 0.03
0.8297 ± 0.01
0.5856 ± 0.19
0.6608 ± 0.24
0.6579 ± 0.0075
0.8458 ± 0.02
0.8461 ± 0.06
4
0.7502 ± 0.04
0.7977 ± 0.03
0.7607 ± 0.07
0.8455 ± 0.08
0.6579 ± 0.0075
0.8317 ± 0.04
0.8405 ± 0.02
5
0.7606 ± 0.03
0.7873 ± 0.01
0.7714 ± 0.04
0.8244 ± 0.05
0.6579 ± 0.0075
0.8032 ± 0.02
0.8297 ± 0.06
PROTEINS
1
0.5229 ± 0.11
0.6020 ± 0.03
0.5642 ± 0.09
0.5957 ± 0.03
0.5919 ± 0.0029
0.6038 ± 0.01
0.5337 ± 0.08
TABLE III: The accuracies of graph classification models with different numbers of layers across three datasets. The results showing the highest accuracy are highlighted in blue . Models marked with OOM encountered an out-of-memory error.
n-iteration ( k )
leaky rate ( α )
MUTAG
EMCI-AD
RGC-Net*
TRGC-Net
RGC-Net*
TRGC-Net
1
1
0.8442 ± 0.01
0.8087 ± 0.06
0.4476 ± 0.03
0.4476 ± 0.01
1
0.9
0.8584 ± 0.01
0.8564 ± 0.05
0.4504 ± 0.03
0.4847 ± 0.08
1
0.8
0.8726 ± 0.01
0.8408 ± 0.07
0.4573 ± 0.02
0.4475 ± 0.05
1
0.7
0.8691 ± 0.01
0.8245 ± 0.03
0.4302 ± 0.01
0.4625 ± 0.02
Avg.
0.8611 ± 0.01
0.8207 ± 0.02
0.4464 ± 0.01
0.4606 ± 0.02
TABLE IV: Accuracies of RGC-Net and its variant (TRGC-Net) on graph classification with MUTAG and EMCI-AD datasets for various iterations ( k ) and leaky rates ( α ). The highest accuracy in each iteration is bolded in blue and the best average accuracy across all iterations is bolded in green .
Dataset
Models
Training
Time per
#Epoch
Avg. Memory
Avg. GPU
Time (s)
Epoch (s)
Usage (GB)
Usage (GB)
MUTAG
GAT
5.11±3.72
0.030±0.028
169.27±175.5
1.6251±0.0060
0.01678±0.00007
GCN
5.62±2.26
0.021±0.008
273.80±127.6
1.6391±0.0022
0.01690±0.00007
GraphSAGE
\mathbf{{\color[rgb]{0,0,1}2.85\pm 1.43}}
0.022±0.011
129.90±103.5
1.8790±0.0255
0.02060±0.00008
GIN
5.14±1.13
0.025±0.005
203.33±41.7
1.8792±0.0248
0.02062±0.00010
RGC-NET
6.65±2.97
0.020±0.009
326.91±151.3
1.6489±0.0002
\mathbf{{\color[rgb]{0,0,1}0.01684\pm 0.00005}}
TABLE V: Comparison of Training Time, Time per Epoch, Number of Epochs, Average Memory Usage, and Average GPU Usage across different models and datasets.
Fig. 5: Connectivity distributions of connectomic datasets for brain graph evolution prediction across different time points. Figure (a) shows the EMCI-AD dataset with nearly the same connectivity distribution across time points. Figures (b) and (c) show connectivity distribution for simulated and SLIM160 datasets. The figures show that although the connectivity distribution between time points is quite similar, each time point slightly differs in the maximum density.
Dataset
Models
↓ MAE
↓ Frobenius
↓ MAE
↓ MAE
↓ MAE
↓ MAE
Distance
Node
Clustering
Betweenness
Eigenvector
Strength
Coef.
C.
C.
EMCI-AD
Identity Function
0.0860 ± 0.01
3.9414 ± 0.54
1.3765 ± 0.24
0.0101 ± 0.00
0.1051 ± 0.00
0.0048 ± 0.00
RBGM [ 22 ]
0.2516 ± 0.08
11.3652 ± 3.77
7.2024 ± 2.78
0.0740 ± 0.00
0.0915 ± 0.00
0.0093 ± 0.00
EvoGraphNet [ 21 ]
0.4135 ± 0.02
23.3185 ± 0.61
11.1199 ± 0.30
0.2106 ± 0.02
0.0916 ± 0.01
0.0221 ± 0.00
GCN-Transformer
0.6847 ± 0.56
39.2852 ± 34.8
20.4643 ± 10.7
0.0436 ± 0.02
0.1026 ± 0.01
0.0136 ± 0.00
TABLE VI: Evaluation results for brain graph evolution prediction across three longitudinal connectomic datasets. The best results for each dataset are highlighted in blue . Models marked with OOM encountered an out-of-memory error.
Dataset
Models
Training
Time per
#Epoch
Avg. Memory
Avg. GPU
Time (s)
Epoch (s)
Usage (GB)
Usage (GB)
EMCI-AD
RBGM [ 22 ]
176.42 ± 21.69
3.92 ± 0.69
45 ± 5.73
3.31 ± 0.00
0.17 ± 0.00
EvoGraphNet [ 21 ]
260.29 ± 124.42
1.30 ± 0.62
200 ± 0.00
3.26 ± 0.00
0.03 ± 0.00
GCN-Transformer
8.85 ± 1.75
0.29 ± 0.08
31 ± 6.48
3.29 ± 0.00
0.02 ± 0.00
RGC-Net-Transformer
8.76 ± 0.44
0.30 ± 0.02
29 ± 1.70
4.31 ± 0.27
0.02 ± 0.00
TRGC-Net-Transformer
15.6 ± 10.0
0.33 ± 0.29
47 ± 28.5
4.02 ± 0.22
0.02 ± 0.00
TABLE VII: Comparison of Training Time, Time per Epoch, Number of Epochs, Average Memory Usage, and Average GPU Usage across different models and datasets.
Figure 13Figure 14Figure 15Figure 16
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Fig. A.1: Message passing operation to update target node embedding
Fig. A.2: Illustration of a 2-layer RGC-Net architecture
Fig. A.3: Data distributions of the graph classification datasets: Figures (a)-(c), (d)-(f), and (g)-(i) show the distribution of graph properties—class, nodes, and edges—in the MUTAG, PROTEINS, and DD datasets, respectively. Specifically, Figures (a), (d), and (g) illustrate class distributions; Figures (b), (e), and (h) illustrate node distributions; and Figures (c), (f), and (i) illustrate edge distributions.
Fig. A.4: Extended sensitivity analysis of RGC-Net accuracy on the MUTAG dataset across different reservoir iteration counts ( k ) and leaky rates ( α ). Each curve corresponds to a fixed α value, showing how accuracy varies as the number of reservoir iterations increases. The results indicate that RGC-Net maintains stable performance across a wide range of α and k values, confirming the robustness of the model’s dynamics and its insensitivity to small hyperparameter variations.
Properties
MUTAG
PROTEINS
D&D
General Properties
#Graphs
188
1113
1178
Avg. #Nodes per Graph
17.93 ± 4.58
39.06 ± 45.76
284.32 ± 272.00
Avg. #Edges per Graph
39.59 ± 11.37
145.63 ± 169.20
1431.32 ± 1387.81
#Node Features
7
4
89
Topological Properties
Appendix
TABLE C.1: Datasets used for graph classification experiments
Properties
EMCI-AD
Simulated
SLIM160
General Properties
#Subjects
67
100
109
#Time Points
2
3
3
#Graphs
134
300
327
#Nodes
35
35
160
#Node Features
8
8
8
Appendix
TABLE C.2: Datasets used for graph generation experiments
We introduce the Geometric Evolution Graph Convolutional Network (GEGCN), a novel framework that enhances graph representation learning through explicit modeling of geometric evolution on graph structures. Specifically, GEGCN leverages a Long Short-Term Memory (LSTM) network to capture the dynamic structural sequence generated by discrete Ricci flow, and infuses the learned dynamic representations into a graph convolutional network. Extensive experiments demonstrate that GEGCN achieves excellent performance on classification tasks across various benchmark datasets, including homophilic/heterophilic graphs, filtered graphs, and large-scale graphs.
Jicheng Ma, Yunyan Yang, Juan Zhao +1
School of Mathematics, Renmin University of China, Beijing, China. · School of Mathematical Sciences, Key Laboratory of Mathematics and Complex Systems of MOE, Beijing Normal University, Beijing, China.
Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.
Hugo Attali, Rachid El Jouhri
Université Sorbonne Paris Nord, CNRS, LIPN, France
Graph Neural Networks struggle to capture long-range dependencies due to over-squashing, where information from exponentially growing neighborhoods must pass through a small number of structural bottlenecks. While recent rewiring methods attempt to alleviate this limitation, many rely on local criteria such as curvature, which can overlook global connectivity constraints that restrict information flow. We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks. ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways while controlling graph densification under a fixed edge budget. The procedure is parameter-free beyond the rewiring budget and relies on a single global measure aggregating all paths between node pairs. Beyond predictive performance with GCN models, we analyze how rewiring affects message propagation. By tracking cosine similarity between node embeddings across layers, we examine how the relationship between initial node features and learned representations evolves during message passing, comparing graphs with and without rewiring. This analysis helps determine whether improvements arise from better long-range communication rather than changes in embedding geometry. Experiments on homophilic and heterophilic graphs, including directed settings with DirGCN, reveal a trade-off between over-squashing and oversmoothing, where oversmoothing corresponds to the loss of representation diversity across layers. Resistance-guided rewiring improves connectivity and signal propagation but can accelerate representation mixing in deep models. Combining ERR with normalization techniques such as PairNorm stabilizes this trade-off and improves performance.
Bertran Miquel-Oliver, Manel Gil-Sorribes, Victor Guallar +1
Barcelona Supercomputing Center (BSC), Barcelona, Spain · Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Barcelona, Spain · Nostrum Biodiscovery, Barcelona, 08029, Spain +1