  Causality graphs are routinely estimated in social sciences, natural
sciences, and engineering due to their capacity to efficiently represent the
spatiotemporal structure of multivariate data sets in a format amenable for
human interpretation, forecasting, and anomaly detection. A popular approach to
mathematically formalize causality is based on vector autoregressive (VAR)
models and constitutes an alternative to the well-known, yet usually
intractable, Granger causality. Relying on such a VAR causality notion, this
paper develops two algorithms with complementary benefits to track time-varying
causality graphs in an online fashion. Their constant complexity per update
also renders these algorithms appealing for big-data scenarios. Despite using
data sequentially, both algorithms are shown to asymptotically attain the same
average performance as a batch estimator which uses the entire data set at
once. To this end, sublinear (static) regret bounds are established.
Performance is also characterized in time-varying setups by means of dynamic
regret analysis. Numerical results with real and synthetic data further support
the merits of the proposed algorithms in static and dynamic scenarios.
