Search

[Display omitted] • Introduced DynGESN, a deep reservoir computing model for discrete-time dynamic graphs • Proved a theoretical sufficient condition for the echo state property of DynGESN • Best efficiency/accuracy trade-off w.r.t. temporal graph kernels and neural networks Relations between entities evolving through discrete time-steps can be represented by discrete-time dynamic graphs. Examples include hourly interactions between social network users or daily infection spreading. In this paper, we present Dynamic Graph Echo State Network (DynGESN), a reservoir computing model for the efficient processing of discrete-time dynamic temporal graphs. We prove a sufficient condition for the echo state property, which ensures that graph embeddings are independent of initial conditions, and we briefly analyze reservoir dynamics. DynGESN is compared against temporal graph kernels (TGKs) on twelve graph classification tasks, and against ten different end-to-end trained temporal graph convolutional networks (TGNs) on four vertex regression tasks, since TGKs are limited to graph-level tasks. Compared to TGKs that need to hold the entire history of vertex interactions, our model provides a vector encoding for the dynamic graph that is updated at each time-step without requiring training. Experiments show that our model achieves accuracy in line with TGKs that have comparable computational complexity, while still offering space and time requirements better suited to scale to large-size data. Moreover, DynGESN overall achieves superior or on par accuracy with respect to TGNs, while improving efficiency by up ten times on inference and training time. [ABSTRACT FROM AUTHOR]

• 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]

Abstract: The paper introduces an input-driven generative model for tree-structured data that extends the bottom-up hidden tree Markov model to non-homogeneous state transition and emission probabilities. We show how the proposed input-driven approach can be used to realize different types of structured transductions between trees. A thorough experimental analysis is proposed to investigate the advantage of introducing an input-driven dynamics in structured-data processing. The results of this analysis suggest that input-driven models can capture more discriminative structural information than homogeneous approaches in computational learning tasks, including document classification and more general substructure categorization. [Copyright &y& Elsevier]

Abstract: In this paper we present the Tree Echo State Network (TreeESN) model, generalizing the paradigm of Reservoir Computing to tree structured data. TreeESNs exploit an untrained generalized recursive reservoir, exhibiting extreme efficiency for learning in structured domains. In addition, we highlight through the paper other characteristics of the approach: First, we discuss the Markovian characterization of reservoir dynamics, extended to the case of tree domains, that is implied by the contractive setting of the TreeESN state transition function. Second, we study two types of state mapping functions to map the tree structured state of TreeESN into a fixed-size feature representation for classification or regression tasks. The critical role of the relation between the choice of the state mapping function and the Markovian characterization of the task is analyzed and experimentally investigated on both artificial and real-world tasks. Finally, experimental results on benchmark and real-world tasks show that the TreeESN approach, in spite of its efficiency, can achieve comparable results with state-of-the-art, although more complex, neural and kernel based models for tree structured data. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to start a comparison between recursive neural networks (RecNN) and kernel methods for structured data, specifically support vector regression (SVR) machine using a tree kernel, in the context of regression tasks for trees. Both the approaches can deal directly with a structured input representation and differ in the construction of the feature space from structured data. We present and discuss preliminary empirical results for specific regression tasks involving well-known quantitative structure-activity and quantitative structure-property relationship (QSAR/QSPR) problems, where both the approaches are able to achieve state-of-the-art results. [Copyright &y& Elsevier]

Self-organization constitutes an important paradigm in machine learning with successful applications e.g. in data- and web-mining. Most approaches, however, have been proposed for processing data contained in a fixed and finite dimensional vector space. In this article, we will focus on extensions to more general data structures like sequences and tree structures. Various modifications of the standard self-organizing map (SOM) to sequences or tree structures have been proposed in the literature some of which are the temporal Kohonen map, the recursive SOM, and SOM for structured data. These methods enhance the standard SOM by utilizing recursive connections. We define a general recursive dynamic in this article which provides recursive processing of complex data structures by recursive computation of internal representations for the given context. The above mentioned mechanisms of SOMs for structures are special cases of the proposed general dynamic. Furthermore, the dynamic covers the supervised case of recurrent and recursive networks. The general framework offers an uniform notation for training mechanisms such as Hebbian learning. Moreover, the transfer of computational alternatives such as vector quantization or the neural gas algorithm to structure processing networks can be easily achieved. One can formulate general cost functions corresponding to vector quantization, neural gas, and a modification of SOM. The cost functions can be compared to Hebbian learning which can be interpreted as an approximation of a stochastic gradient descent. For comparison, we derive the exact gradients for general cost functions. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of one day-ahead hourly electricity price forecast for smart grid applications. To this aim, we investigate the application of a number of predictive models for time-series, including methods based on empirical strategies frequently adopted in the smart grid community, Kalman Filters and Echo State Networks (ESNs). The considered methods have been suitably modified to address the electricity price forecast problem. Strategies based on daily re-adaptation of models’ parameters are taken into consideration as well. The predictive performance achieved by the considered models is assessed, and the methods are compared among each other on recent real data from the Italian electricity market. As a result of the comparison over three years data, ESN methods appear to provide the most accurate price predictions, which could imply significant economic savings in many smart grid activities, such as switching on power plants to support power generation from renewable sources, electric vehicle recharging or usage of household appliances. [ABSTRACT FROM AUTHOR]

The increasing digitization and datification of all aspects of people's daily life, and the consequent growth in the use of personal data, are increasingly challenging the current development and adoption of Machine Learning (ML). First, the sheer complexity and amount of data available in these applications strongly demands for ML algorithms that can be trained directly on complex structures, which can be naturally described by graphs. In fact, graphs inherently capture information about entities, their attributes, and relationships between them. Directly applying ML to graphs relieves domain experts and data scientists from the challenging and time-consuming problem of designing a suitable vector-based data representation used by classical ML techniques. Second, ML algorithms should not only be designed to achieve high technical and functional standards; as the automated decisions provided by these algorithms can have a relevant impact on people's lives, their behavior has to be aligned with the values and principles of individuals and society. This demands for designing automated algorithms that we, as humans, can trust, fulfilling the requirements of fairness, robustness, privacy, and explainability. Third, designing effective ML algorithms requires skills and expertise developed at different levels. This substantially hinders the democratization and widespread availability of such technology for society at large, which in turn demands for improving the level of automatization and systematization of their design process, while also providing guarantees on their performance. For this reason, this paper provides an overview of the current works focused towards learning trustworthily, automatically, and with guarantees on graphs. [ABSTRACT FROM AUTHOR]