Provably Fast Inference of Latent Features from Networks with Applications to Learning Social Circles and Multilabel Classification

A well known phenomenon in social networks is homophily, the tendency of agents to connect with similar agents. A derivative of this phenomenon is the emergence of commu-nities. Another phenomenon observed in numerous networks is the existence of certain agents that belong simultaneously to multiple communities. An understanding of these phe-nomena constitutes a central research topic of network sci-ence. In this work we focus on a fundamental theoretical ques-tion related to the above phenomena with various applica-tions: given an undirected graph G, can we infer efficiently the latent vertex features which explain the observed net-work structure under the assumption of a generative model that exhibits homophily? We propose a probabilistic gener-ative model with the property that the probability of an edge among two vertices is a non-decreasing function of the common features they possess. This property is true for many real-world networks and surprisingly is ignored by many popular overlapping community detection methods as it was shown recently by the empirical work of Yang and Leskovec [44]. Our main theoretical contribution is the first provably rapidly mixing Markov chain for inferring latent features. On the experimental side, we verify the efficiency of our method in terms of run times, where we observe that it significantly outperforms state-of-the-art methods. Our method is more than 2 400 times faster than a state-of-the-art machine learning method [37] and typically provides non-trivial speedups compared to BigClam [43]. Furthermore, we verify on real-data with ground-truth available that our method learns efficiently high quality labelings. We use our method to learn social circles from Twitter ego-networks and perform multilabel classification