# American Institute of Mathematical Sciences

May  2019, 2(2): 127-147. doi: 10.3934/mfc.2019010

## Unsupervised robust nonparametric learning of hidden community properties

 Machine Learning and Optimization Laboratory, EPFL, Lausanne, CH-1015, Switzerland

* Corresponding author: Mikhail Langovoy

Received  April 2019 Published  June 2019

We consider learning of fundamental properties of communities in large noisy networks, in the prototypical situation where the nodes or users are split into two classes according to a binary property, e.g., according to their opinions or preferences on a topic. For learning these properties, we propose a nonparametric, unsupervised, and scalable graph scan procedure that is, in addition, robust against a class of powerful adversaries. In our setup, one of the communities can fall under the influence of a knowledgeable adversarial leader, who knows the full network structure, has unlimited computational resources and can completely foresee our planned actions on the network. We prove strong consistency of our results in this setup with minimal assumptions. In particular, the learning procedure estimates the baseline activity of normal users asymptotically correctly with probability 1; the only assumption being the existence of a single implicit community of asymptotically negligible logarithmic size. We provide experiments on real and synthetic data to illustrate the performance of our method, including examples with adversaries.

Citation: Mikhail Langovoy, Akhilesh Gotmare, Martin Jaggi. Unsupervised robust nonparametric learning of hidden community properties. Mathematical Foundations of Computing, 2019, 2 (2) : 127-147. doi: 10.3934/mfc.2019010
##### References:

show all references

##### References:
Graph scan estimators for the artificial large graph
Political blogosphere graph for the 2004 Elections
Graph scan estimators for the 2004 Elections graph
 $k$ 100 200 500 700 800 $\#(N_w=0)$ 98 98 78 56 55 $\#(N_w=1)$ 2 2 16 22 17 $\#(N_w=2)$ 0 0 3 16 12 $\#(N_w = 3)$ 0 0 3 5 9 $\#(N_w \geq 4)$ 0 0 0 1 7 $\mu_{\hat{a}}$ 1.705 1.815 1.913 1.949 1.961 $\max{\hat{a}}$ 1.806 1.903 1.98 2.03 2.031 $\min{\hat{a}}$ 1.603 1.686 1.824 1.848 1.879 $\sigma_{\hat{a}}$ 0.048 0.04 0.033 0.034 0.029
 $k$ 100 200 500 700 800 $\#(N_w=0)$ 98 98 78 56 55 $\#(N_w=1)$ 2 2 16 22 17 $\#(N_w=2)$ 0 0 3 16 12 $\#(N_w = 3)$ 0 0 3 5 9 $\#(N_w \geq 4)$ 0 0 0 1 7 $\mu_{\hat{a}}$ 1.705 1.815 1.913 1.949 1.961 $\max{\hat{a}}$ 1.806 1.903 1.98 2.03 2.031 $\min{\hat{a}}$ 1.603 1.686 1.824 1.848 1.879 $\sigma_{\hat{a}}$ 0.048 0.04 0.033 0.034 0.029
 [1] Nicolás M. Crisosto, Christopher M. Kribs-Zaleta, Carlos Castillo-Chávez, Stephen Wirkus. Community resilience in collaborative learning. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 17-40. doi: 10.3934/dcdsb.2010.14.17 [2] Ziju Shen, Yufei Wang, Dufan Wu, Xu Yang, Bin Dong. Learning to scan: A deep reinforcement learning approach for personalized scanning in CT imaging. Inverse Problems & Imaging, 2022, 16 (1) : 179-195. doi: 10.3934/ipi.2021045 [3] Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1 [4] Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117 [5] Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901 [6] Christian Soize, Roger Ghanem. Probabilistic learning on manifolds. Foundations of Data Science, 2020, 2 (3) : 279-307. doi: 10.3934/fods.2020013 [7] Mauro Maggioni, James M. Murphy. Learning by active nonlinear diffusion. Foundations of Data Science, 2019, 1 (3) : 271-291. doi: 10.3934/fods.2019012 [8] Gernot Holler, Karl Kunisch. Learning nonlocal regularization operators. Mathematical Control & Related Fields, 2022, 12 (1) : 81-114. doi: 10.3934/mcrf.2021003 [9] Yossi Bokor, Katharine Turner, Christopher Williams. Reconstructing linearly embedded graphs: A first step to stratified space learning. Foundations of Data Science, 2021  doi: 10.3934/fods.2021026 [10] Minlong Lin, Ke Tang. Selective further learning of hybrid ensemble for class imbalanced increment learning. Big Data & Information Analytics, 2017, 2 (1) : 1-21. doi: 10.3934/bdia.2017005 [11] Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008 [12] Cai-Tong Yue, Jing Liang, Bo-Fei Lang, Bo-Yang Qu. Two-hidden-layer extreme learning machine based wrist vein recognition system. Big Data & Information Analytics, 2017, 2 (1) : 59-68. doi: 10.3934/bdia.2017008 [13] Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $\ell^1$ norm. Mathematical Foundations of Computing, 2020, 3 (3) : 205-218. doi: 10.3934/mfc.2020020 [14] Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems & Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017 [15] Hao Li, Honglin Chen, Matt Haberland, Andrea L. Bertozzi, P. Jeffrey Brantingham. PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video. Discrete & Continuous Dynamical Systems, 2021, 41 (9) : 4351-4373. doi: 10.3934/dcds.2021039 [16] Shuhua Wang, Zhenlong Chen, Baohuai Sheng. Convergence of online pairwise regression learning with quadratic loss. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4023-4054. doi: 10.3934/cpaa.2020178 [17] Prashant Shekhar, Abani Patra. Hierarchical approximations for data reduction and learning at multiple scales. Foundations of Data Science, 2020, 2 (2) : 123-154. doi: 10.3934/fods.2020008 [18] Émilie Chouzenoux, Henri Gérard, Jean-Christophe Pesquet. General risk measures for robust machine learning. Foundations of Data Science, 2019, 1 (3) : 249-269. doi: 10.3934/fods.2019011 [19] Yang Wang, Zhengfang Zhou. Source extraction in audio via background learning. Inverse Problems & Imaging, 2013, 7 (1) : 283-290. doi: 10.3934/ipi.2013.7.283 [20] Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks. Journal of Industrial & Management Optimization, 2018, 14 (2) : 719-729. doi: 10.3934/jimo.2017071

Impact Factor: