Search

• We propose to generate graphs node by node in a sequential fashion. • Generation is carried out by two Recurrent Neural Networks that sample the nodes attached to an edge sequentially. • Our model is capable of producing novel and unique graphs that retain structural features of those in the training set. Graph generation with Machine Learning is an open problem with applications in various research fields. In this work, we propose to cast the generative process of a graph into a sequential one, relying on a node ordering procedure. We use this sequential process to design a novel generative model composed of two recurrent neural networks that learn to predict the edges of graphs: the first network generates one endpoint of each edge, while the second network generates the other endpoint conditioned on the state of the first. We test our approach extensively on five different datasets, comparing with two well-known baselines coming from graph literature, and two recurrent approaches, one of which holds state of the art performances. Evaluation is conducted considering quantitative and qualitative characteristics of the generated samples. Results show that our approach is able to yield novel, and unique graphs originating from very different distributions while retaining structural properties very similar to those in the training sample. Under the proposed evaluation framework, our approach is able to reach performances comparable to the current state of the art on the graph generation task. [ABSTRACT FROM AUTHOR]

[Display omitted] • Extended Graph Echo State Network (GESN) to supervised node classification tasks. • Improved efficiency/accuracy trade-off on medium- and large-scale heterophilic graphs. • Reservoirs outside stability constraints can be more effective for node-level tasks. • GESN allows effective node encoding by message-passing up to the largest shortest path. 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. [ABSTRACT FROM AUTHOR]

The analysis of deep Recurrent Neural Network (RNN) models represents a research area of increasing interest. In this context, the recent introduction of Deep Echo State Networks (DeepESNs) within the Reservoir Computing paradigm, enabled to study the intrinsic properties of hierarchically organized RNN architectures.In this paper we investigate the DeepESN model under a dynamical system perspective, aiming at characterizing the important aspect of stability of layered recurrent dynamics excited by external input signals.To this purpose, we develop a framework based on the study of the local Lyapunov exponents of stacked recurrent models, enabling the analysis and control of the resulting dynamical regimes. The introduced framework is demonstrated on artificial as well as real-world datasets. The results of our analysis on DeepESNs provide interesting insights on the real effect of layering in RNNs. In particular, they show that when recurrent units are organized in layers, then the resulting network intrinsically develops a richer dynamical behavior that is naturally driven closer to the edge of criticality. As confirmed by experiments on the short-term Memory Capacity task, this characterization makes the layered design effective, with respect to the shallow counterpart with the same number of units, especially in tasks that require much in terms of memory. [ABSTRACT FROM AUTHOR]

In this paper, we propose an empirical analysis of deep recurrent neural network (RNN) architectures with stacked layers. The main aim is to address some fundamental open research issues on the significance of creating deep layered architectures in RNN and to characterize the inherent hierarchical representation of time in such models, especially for efficient implementations. In particular, the analysis aims at the study and proposal of approaches to develop and enhance hierarchical dynamics in deep architectures within the efficient Reservoir Computing (RC) framework for RNN modeling. The effect of a deep layered organization of RC models is investigated in terms of both occurrence of multiple time-scale and increasing of richness of the dynamics. It turns out that a deep layering of recurrent models allows an effective diversification of temporal representations in the layers of the hierarchy, by amplifying the effects of the factors influencing the time-scales and the richness of the dynamics, measured as the entropy of recurrent units activations. The advantages of the proposed approach are also highlighted by measuring the increment of the short-term memory capacity of the RC models. [ABSTRACT FROM AUTHOR]