title: Compressive Network Analysis.
abstract: Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas:network data analysisandcompressed sensing. From a nonparametric perspective, we model an observed network using a large dictionary. In particular, we consider the network clique detection problem and show connections between our formulation with a new algebraic tool, namelyRandon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Though this paper is mainly conceptual, we also develop practical approximation algorithms for solving empirical problems and demonstrate their usefulness on real-world datasets.
authors.affiliation: Stanford University, Stanford, CA 94305 USA.
authors.forename: Xiaoye
authors.initials: X
authors.lastname: Jiang
authors.affiliation: Peking University, Beijing 100871, China.
authors.forename: Yuan
authors.initials: Y
authors.lastname: Yao
authors.affiliation: Princeton University, Princeton, NJ 08540 USA.
authors.forename: Han
authors.initials: H
authors.lastname: Liu
authors.affiliation: Stanford University, Stanford, CA 94305 USA.
authors.forename: Leonidas
authors.initials: L
authors.lastname: Guibas
keywords: Clique detection; Radon basis pursuit; compressive sensing; network data analysis; restricted isometry property