Online factorization and partition of complex networks by random walk

Lin Yang, Zheng Yu, Vladimir Braverman, Tuo Zhao, Mengdi Wang

Research output: Contribution to conferencePaper

Abstract

Finding the reduced-dimensional structure is critical to understanding complex networks. Existing approaches such as spectral clustering are applicable only when the full network is explicitly observed. In this paper, we focus on the online factorization and partition of implicit large lumpable networks based on observations from an associated random walk. We formulate this into a nonconvex stochastic factorization problem and propose an efficient and scalable stochastic generalized Hebbian algorithm (GHA). The algorithm is able to process random walk data in a streaming fashion and learn a low-dimensional representation for each vertex. By applying a diffusion approximation analysis, we show that the continuous-time limiting process of the stochastic algorithm converges globally to the “principal components” of the Markov chain. We also establish a finite-sample error bound that matches the nonimprovable state-of-art result for online factorization. Once learned the low-dimensional state representations, we further apply clustering techniques to recover the network partition. We show that when the associated Markov process is lumpable, one can recover the partition exactly with high probability given sufficient data. We apply the proposed approach to model the traffic flow of Manhattan as city-wide random walks. By using our algorithm to analyze the taxi trip data, we discover a latent partition of the Manhattan city that closely matches the traffic dynamics.

Original languageEnglish (US)
StatePublished - Jan 1 2019
Event35th Conference on Uncertainty in Artificial Intelligence, UAI 2019 - Tel Aviv, Israel
Duration: Jul 22 2019Jul 25 2019

Conference

Conference35th Conference on Uncertainty in Artificial Intelligence, UAI 2019
CountryIsrael
CityTel Aviv
Period7/22/197/25/19

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Online factorization and partition of complex networks by random walk'. Together they form a unique fingerprint.

  • Cite this

    Yang, L., Yu, Z., Braverman, V., Zhao, T., & Wang, M. (2019). Online factorization and partition of complex networks by random walk. Paper presented at 35th Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel.