  We propose a deep Graph Neural Network (GNN) model that alternates two types
of layers. The first type is inspired by Reservoir Computing (RC) and generates
new vertex features by iterating a non-linear map until it converges to a fixed
point. The second type of layer implements graph pooling operations, that
gradually reduce the support graph and the vertex features, and further improve
the computational efficiency of the RC-based GNN. The architecture is,
therefore, pyramidal. In the last layer, the features of the remaining vertices
are combined into a single vector, which represents the graph embedding.
Through a mathematical derivation introduced in this paper, we show formally
how graph pooling can reduce the computational complexity of the model and
speed-up the convergence of the dynamical updates of the vertex features. Our
proposed approach to the design of RC-based GNNs offers an advantageous and
principled trade-off between accuracy and complexity, which we extensively
demonstrate in experiments on a large set of graph datasets.
