Detecting Network Cliques with Radon Basis Pursuit


Xiaoye Jiang, Yuan Yao, Han Liu, Leonidas Guibas ;
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:565-573, 2012.


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.

Related Material