Ring Reservoir Neural Networks for Graphs

Claudio Gallicchio, Alessio Micheli

Abstract: Machine Learning for graphs is nowadays a research topic of consolidated relevance. Common approaches in the field typically resort to complex deep neural network architectures and demanding training algorithms, highlighting the need for more efficient solutions. The class of Reservoir Computing (RC) models can play an important role in this context, enabling to develop fruitful graph embeddings through untrained recursive architectures. In this paper, we study progressive simplifications to the design strategy of RC neural networks for graphs. Our core proposal is based on shaping the organization of the hidden neurons to follow a ring topology. Experimental results on graph classification tasks indicate that ring-reservoirs architectures enable particularly effective network configurations, showing consistent advantages in terms of predictive performance.

1. Introduction

Processing graph data, such as molecular structures or social networks, typically requires complex deep neural networks that are computationally expensive and difficult to train. To bypass this, researchers often turn to Reservoir Computing (RC), specifically Graph Echo State Networks (GESNs). In a GESN, the hidden layer (the "reservoir") is left completely untrained; it projects the input graph into a higher-dimensional space using fixed, randomly initialized weights. Only the final linear output layer is trained.

However, this reliance on randomness is a double-edged sword. To ensure results are not due to a "lucky" initialization, researchers must average the performance of dozens of random reservoir guesses, which increases computational overhead. This paper investigates whether a structured, deterministic reservoir topology can eliminate the need for random guessing while maintaining or improving accuracy.

Standard Graph Echo State Network (GESN) architecture featuring a sparse random reservoir and state update mechanism.

2. Proposed Methodology: Ring and Minimal Graph Networks

The authors propose stripping away the randomness of standard GESNs by imposing strict architectural constraints through two new models:

  1. Graph Ring-Reservoir Network (GRN): Instead of a random sparse matrix, the connections between reservoir neurons are organized in a simple cycle (a ring topology). Each neuron feeds its activation to exactly one successor. All recurrent weights share the same value, controlled by a single spectral radius parameter.
  2. Minimal Graph Network (MGN): This model takes GRN a step further by removing all randomness. While GRN still uses random weights for input connections, MGN uses deterministic input weights. All input weights share the same absolute value, with signs assigned deterministically based on the decimal digits of the irrational number $\pi$.
The proposed Ring-Reservoir architecture and the deterministic Minimal Graph Network (MGN) update mechanism.

The MGN model is entirely deterministic. A network's entire hidden state dynamics are defined by just two numbers: input scaling and spectral radius. This eliminates the need for multiple random initializations, allowing for vastly more efficient hyperparameter tuning.

3. Experimental Evaluation

The models were evaluated on six standard graph classification benchmarks, including cheminformatics datasets (MUTAG, NCI1) and social network datasets (IMDB-BINARY, IMDB-MULTI, REDDIT, and COLLAB).

Key Insights

  • Simplicity beats randomness: Imposing a strict ring structure yields better graph embeddings than random sparse connections. In time-series analysis, ring topologies create "orthogonal" recurrence matrices known to improve memory capacity; this paper demonstrates that the concept transfers effectively to spatial graph processing.
  • Efficiency gains: Because MGN is fully deterministic, researchers can explore a larger grid of hyperparameters in the same amount of time it would take to run a single configuration of a standard random GESN.

4. Results and Discussion

Experimental results show that both GRN and MGN outperformed the standard random GESN baseline on five out of six datasets. On the largest dataset, COLLAB, the performance boost exceeded 2% in accuracy. Remarkably, small MGN models often performed as well as standard GESNs that were ten times larger.

Despite having only a single, untrained hidden layer, the proposed models established new state-of-the-art results on IMDB-BINARY (72.7%) and IMDB-MULTI (50.5%), outperforming highly complex, fully trained deep models like DiffPool, GraphSAGE, and DGCNN.

5. Conclusion

Deterministic ring-based reservoirs provide a highly efficient and effective alternative to traditional random reservoirs and complex deep GNNs. Future work may involve extending these constrained topologies to deep Reservoir Computing models or using these insights to design better initialization strategies for standard, fully trained Graph Neural Networks.

Summary updated

Abstract

Machine Learning for graphs is nowadays a research topic of consolidated relevance. Common approaches in the field typically resort to complex deep neural network architectures and demanding training algorithms, highlighting the need for more efficient solutions. The class of Reservoir Computing (RC) models can play an important role in this context, enabling to develop fruitful graph embeddings through untrained recursive architectures. In this paper, we study progressive simplifications to the design strategy of RC neural networks for graphs. Our core proposal is based on shaping the organization of the hidden neurons to follow a ring topology. Experimental results on graph classification tasks indicate that ring-reservoirs architectures enable particularly effective network configurations, showing consistent advantages in terms of predictive performance.
BibTeX
@inproceedings{gallicchio2020ring,
  author = {Claudio Gallicchio and Alessio Micheli},
  title = {{Ring Reservoir Neural Networks for Graphs}},
  booktitle = {IJCNN},
  year = {2020},
  url = {https://openreview.net/forum?id=INGvIBNkMvQ},
}
Figure