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.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-jiang12, title = {Detecting Network Cliques with Radon Basis Pursuit}, author = {Jiang, Xiaoye and Yao, Yuan and Liu, Han and Guibas, Leonidas}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {565--573}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/jiang12/jiang12.pdf}, url = {https://proceedings.mlr.press/v22/jiang12.html}, 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.} }
Endnote
%0 Conference Paper %T Detecting Network Cliques with Radon Basis Pursuit %A Xiaoye Jiang %A Yuan Yao %A Han Liu %A Leonidas Guibas %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-jiang12 %I PMLR %P 565--573 %U https://proceedings.mlr.press/v22/jiang12.html %V 22 %X 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.
RIS
TY - CPAPER TI - Detecting Network Cliques with Radon Basis Pursuit AU - Xiaoye Jiang AU - Yuan Yao AU - Han Liu AU - Leonidas Guibas BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-jiang12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 565 EP - 573 L1 - http://proceedings.mlr.press/v22/jiang12/jiang12.pdf UR - https://proceedings.mlr.press/v22/jiang12.html AB - 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. ER -
APA
Jiang, X., Yao, Y., Liu, H. & Guibas, L.. (2012). Detecting Network Cliques with Radon Basis Pursuit. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:565-573 Available from https://proceedings.mlr.press/v22/jiang12.html.

Related Material