Detecting Network Cliques with Radon Basis Pursuit

Abstract

In this paper, we propose a novel formulation of the network clique detection problem by introducing a general network data representation framework. We show connections between our formulation with a new algebraic tool, namely Radon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Practical approximation algorithms are also developed for solving empirical problems and their usefulness is demonstrated on real-world datasets. Our work connects two seemingly different areas: network data analysis and compressed sensing, which helps to bridge the gap between the research of network data and the classical theory of statistical learning and signal processing.