Detecting network cliques with radon basis pursuit

Xiaoye Jiang, Yuan Yao, Han Liu, Leonidas Guibas

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)565-573
Number of pages9
JournalJournal of Machine Learning Research
Volume22
StatePublished - Jan 1 2012
Event15th International Conference on Artificial Intelligence and Statistics, AISTATS 2012 - La Palma, Spain
Duration: Apr 21 2012Apr 23 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Detecting network cliques with radon basis pursuit'. Together they form a unique fingerprint.

Cite this