Dictionary Learning from dependent data samples and networks

---

---

Abstract: Analyzing group behavior of systems of interacting variables is a ubiquitous problem in many fields including probability, combinatorics, and dynamical systems. This problem also naturally arises when one tries to learn essential features (dictionary atoms) from large and structured data such as networks. For instance, independently sampling some number of nodes in a sparse network hardly detects any edges between adjacent nodes. Instead, we may perform a random walk on the space of connected subgraphs, which will produce more meaningful but correlated samples. As classical results in probability were first developed for independent variables and then gradually generalized for dependent variables, many algorithms in machine learning first developed for independent data samples now need to be extended to correlated data samples. In this talk, we discuss some new results that accomplish this including some for online nonnegative matrix and tensor factorization for Markovian data. A unifying technique for handling dependence in data samples we develop is to condition on the distant past, rather than the recent history. As an application, we present a new approach for learning “basis subgraphs” from network data, that can be used for network denoising and edge inference tasks. We illustrate our method using several synthetic network models as well as Facebook, arXiv, and protein-protein interaction networks, that achieve state-of-the-art performance for such network tasks when compared to several recent methods.