Online Machine Learning for Graph Topology Identification from Multiple Time Series

Abstract

High dimensional time series data are observed in many complex systems. In networked data, some of the time series are influenced by other time series. Identifying these relations encoded in a graph structure or topology among the time series is of paramount interest in certain applications since the identified structure can provide insights about the underlying system and can assist in inference tasks. In practice, the underlying topology is usually sparse, that is, not all the participating time series in influence each other. The goal of this dissertation pertains to study the problem of sparse topology identification under various settings. Topology identification from time series is a challenging task. The first major challenge in topology identification is that the assumption of static topology does not hold always in practice since most of the practical systems are evolving with time. For instance, in econometrics, social networks, etc., the relations among the time series can change over time. Identifying the topologies of such dynamic networks is a major challenge. The second major challenge is that in most practical scenarios, the data is not available at once - it is coming in a streaming fashion. Hence, batch approaches are either not applicable or they become computationally expensive since a batch algorithm is needed to be run when a new datum becomes available. The third challenge is that the multi-dimensional time series data can contain missing values due faulty sensors, privacy and security reasons, or due to saving energy. We address the aforementioned challenges in this dissertation by proposing online/-batch algorithms to solve the problem of time-varying topology identification. A model based on vector autoregressive (VAR) process is adopted initially. The parameters of the VAR model reveal the topology of the underlying network. First, two online algorithms are proposed for the case of streaming data. Next, using the same VAR model, two online algorithms under the framework of online optimization are presented to track the time-varying topologies. To evaluate the performance of propose online algorithms, we show that both the proposed algorithms incur a sublinear static regret. To characterize the performance theoretically in time-varying scenarios, a bound on the dynamic regret for one of the proposed algorithms (TIRSO) is derived. Next, using a structural equation model (SEM) for topology identification, an online algorithm for tracking time-varying topologies is proposed, and a bound on the dynamic regret is also derived for the proposed algorithm. Moreover, using a non-stationary VAR model, an algorithm for dynamic topology identification and breakpoint detection is also proposed, where the notion of local structural breakpoint is introduced to accommodate the concept of breakpoint where instead of the whole topology, only a few edges vary. Finally, the problem of tracking VAR-based time-varying topologies with missing data is investigated. Online algorithms are proposed where the joint signal and topology estimation is carried out. Dynamic regret analysis is also presented for the proposed algorithm. For all the previously mentioned works, simulation tests about the proposed algorithms are also presented and discussed in this dissertation. The numerical results of the proposed algorithms corroborate with the theoretical analysis presented in this dissertation.