  Node classification tasks on graphs are addressed via fully-trained deep
message-passing models that learn a hierarchy of node representations via
multiple aggregations of a node's neighbourhood. While effective on graphs that
exhibit a high ratio of intra-class edges, this approach poses challenges in
the opposite case, i.e. heterophily, where nodes belonging to the same class
are usually further apart. In graphs with a high degree of heterophily, the
smoothed representations based on close neighbours computed by convolutional
models are no longer effective. So far, architectural variations in
message-passing models to reduce excessive smoothing or rewiring the input
graph to improve longer-range message passing have been proposed. In this
paper, we address the challenges of heterophilic graphs with Graph Echo State
Network (GESN) for node classification. GESN is a reservoir computing model for
graphs, where node embeddings are recursively computed by an untrained
message-passing function. Our experiments show that reservoir models are able
to achieve better or comparable accuracy with respect to most fully trained
deep models that implement ad hoc variations in the architectural bias or
perform rewiring as a preprocessing step on the input graph, with an
improvement in terms of efficiency/accuracy trade-off. Furthermore, our
analysis shows that GESN is able to effectively encode the structural
relationships of a graph node, by showing a correlation between iterations of
the recursive embedding function and the distribution of shortest paths in a
graph.
