The sparse dictionary coding framework represents signals as a linear combination of a few predefined dictionary atoms. It has been employed for images, time series, graph signals and recently for 2-way (or 2D) spatio-temporal data employing jointly temporal and spatial dictionaries. Large and over-complete dictionaries enable high-quality models, but also pose scalability challenges which are exacerbated in multi-dictionary settings. Hence, an important problem that we address in this paper is: How to scale multi-dictionary coding for large dictionaries and datasets?We propose a multi-dictionary atom selection technique for low-rank sparse coding named LRMDS. To enable scalability to large dictionaries and datasets, it progressively selects groups of row-column atom pairs based on their alignment with the data and performs convex relaxation coding via the corresponding sub-dictionaries. We demonstrate both theoretically and experimentally that when the data has a low-rank encoding with a sparse subset of the atoms, LRMDS is able to select them with strong guarantees under mild assumptions. Furthermore, we demonstrate the scalability and quality of LRMDS in both synthetic and real-world datasets and for a range of coding dictionaries. It achieves 3 times to 10 times speed-up compared to baselines, while obtaining up to two orders of magnitude improvement in representation quality on some of the real world datasets given a fixed target number of atoms.

Tensor decomposition methods are popular tools for analysis of multi-way datasets from the social media, healthcare, spatio-temporal domains, and others. Widely adopted models such as Tucker and canonical polyadic decomposition (CPD) follow a data-driven philosophy: they decompose a tensor into factors that approximate the observed data well. In some cases side information is available about the tensor modes. For example, in a temporal user-item purchases tensor a user influence graph, an item similarity graph, and knowledge about seasonality or trends in the temporal mode may be available. Such side information may enable more succinct and interpretable tensor decomposition models and improved quality in downstream tasks. We propose a framework for Multi-Dictionary Tensor Decomposition (MDTD) which takes advantage of prior structural information about tensor modes in the form of coding dictionaries to obtain sparsely coded tensor factors. We derive a general optimization algorithm for MDTD that handles both complete inputs and inputs with missing values. MDTD handles large sparse tensors typical in many real-world application domains. We experimentally demonstrate its utility in both synthetic and real-world datasets. It learns more concise models than dictionary-free counterparts and improves (i) reconstruction quality (up to 60% smaller models coupled with reduced representation error); (ii) missing values imputation quality (two-fold MSE reduction with up to orders of magnitude time savings) and (iii) the estimation of the tensor rank. MDTD’s quality improvements do not come with a running time premium: it can decompose 19GB datasets in less than a minute. It can also impute missing values in sparse billion-entry tensors more accurately and scalably than state-of-the-art competitors.

Machine learning and data analytics tasks on graphs enjoy a lot of attention from both researchers and practitioners due to the utility that a graph structure among data entities adds for downstream tasks. In many cases, however, a graph structure is not known a priori, and instead has to be inferred from data. Specifically, learning a graph associating time series may elucidate hidden dependencies and also enable improved performance in tasks like classification, forecasting and clustering. While approaches based on pairwise correlation and precision matrix estimation have been employed widely, recent approaches that model observations as signals on graphs have been shown to be more advantageous.

Dynamic interaction data is often aggregated in a sequence of network snapshots before being employed in downstream analysis. The two common ways of defining network snapshots are i) a fixed time interval or ii) fixed number of interactions per snapshot. The choice of aggregation has a significant impact on subsequent analysis, and it is not trivial to select one approach over another for a given dataset. More importantly assuming snapshot regularity is data-agnostic and may be at odds with the underlying interaction dynamics. To address these challenges, we propose a method for community-aware detection of network states (CADENCE) based on the premise of stable interaction time-frames within network communities. We simultaneously detect network communities and partition the global interaction activity into scale-adaptive snapshots where the level of interaction within communities remains stable. We model a temporal network as a node-node-time tensor and use a structured canonical polyadic decomposition with a piece-wise constant temporal factor to iteratively identify communities and their activity levels. We demonstrate that transitions between network snapshots learned by CADENCE constitute network change points of better quality than those predicted by state-of-the-art network change point detectors. Furthermore, the network structure within individual snapshots reflects ground truth communities better than baselines for adaptive tensor granularity. Through a case study on a real-world Reddit dataset, we showcase the interpretability of CADENCE motivated snapshots as periods separated by significant events.

Graphs are widely employed models for structural dependencies in complex systems such as social, infrastructure, and information networks. Graph datasets are often massive, computationally challenging to mine, and non-trivial to understand by humans. Hence, there is a large body of literature on graph summarization aiming to improve algorithmic efficiency, quality of analytics tasks, and visualization. Most existing graph summarization methods focus solely on the structure of the graph and assume that node properties are static. In this paper we focus on graphs with temporal measurements on their nodes, which we call temporal graph signals. Our goal is to learn a graph aggregation (summary) that best reflects both the structure and the temporal node measurements. We propose a signal-aware graph aggregation framework called SAGA. The key idea is to group well-connected nodes whose behavior exhibits consistent temporal patterns. SAGA learns simultaneously how to (i) aggregate the graph into supernode groups and (ii) represent the groups' collective temporal behavior succinctly via a sparse dictionary encoding. The obtained aggregations offer insights into the functional organization of the graph and the learned model enables improved performance for state-of-the-art approaches for downstream tasks like temporal graph signal decomposition, forecasting and link prediction. We demonstrate, in both synthetic and real-world data sets, that SAGA's learned aggregations improve (i) reconstruction quality for temporal graph signals by up to 75%, (ii) link prediction accuracy by up to 40% and (iii) the accuracy of forecasting by up to 63% while also offering 50% scalability improvements.

Temporal graph signals are multivariate time series with individual components associated with nodes of a fixed graph structure. Data of this kind arises in many domains including activity of social network users, sensor network readings over time, and time course gene expression within the interaction network of a model organism. Traditional matrix decomposition methods applied to such data fall short of exploiting structural regularities encoded in the underlying graph and also in the temporal patterns of the signal. How can we take into account such structure to obtain a succinct and interpretable representation of temporal graph signals?