Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction

Abstract

A hierarchical gamma process infinite edge partition model is proposed to factorize the binary adjacency matrix of an unweighted undirected relational network under a Bernoulli-Poisson link. The model describes both homophily and stochastic equivalence, and is scalable to big sparse networks by focusing its computation on pairs of linked nodes. It can not only discover overlapping communities and inter-community interactions, but also predict missing edges. A simplified version omitting inter-community interactions is also provided and we reveal its interesting connections to existing models. The number of communities is automatically inferred in a nonparametric Bayesian manner, and efficient inference via Gibbs sampling is derived using novel data augmentation techniques. Experimental results on four real networks demonstrate the models' scalability and state-of-the-art performance.

Appeared in Artificial Intelligence and Statistics (AISTATS), May 2015. 9 pages + 2 page appendix. The paper is updated to fix a typo in the equation right after (25) in the Appendix

References in corpus (3)

• Uncovering the overlapping community structure of complex networks in nature and society
• Line Graphs, Link Partitions and Overlapping Communities
• Modeling homophily and stochastic equivalence in symmetric relational data

Cited by in corpus (25)

• Semi-Implicit Graph Variational Auto-Encoders
• Bayesian Poisson Tucker Decomposition for Learning the Structure of International Relations
• Stochastic gradient variational Bayes for gamma approximating distributions
• Overlapping Community Detection with Graph Neural Networks
• Zero-Truncated Poisson Tensor Factorization for Massive Binary Tensors
• vGraph: A Generative Model for Joint Community Detection and Node Representation Learning
• Dirichlet belief networks for topic structure learning
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• A Poisson Gamma Probabilistic Model for Latent Node-group Memberships in Dynamic Networks
• Permuted and Augmented Stick-Breaking Bayesian Multinomial Regression
• Community Detection in Partially Observable Social Networks
• Deep Generative Models for Relational Data with Side Information
• Graph link prediction in computer networks using Poisson matrix factorisation
• A unified construction for series representations and finite approximations of completely random measures
• Multiresolution Tensor Decomposition for Multiple Spatial Passing Networks
• Discussion on "Sparse graphs using exchangeable random measures" by Francois Caron and Emily B. Fox
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Deep Poisson gamma dynamical systems
• A Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
• Nonparametric Bayesian Sparse Graph Linear Dynamical Systems
• Gamma Belief Networks
• Sequential Edge Clustering in Temporal Multigraphs
• Recurrent Dirichlet Belief Networks for Interpretable Dynamic Relational Data Modelling
• Variational Hetero-Encoder Randomized GANs for Joint Image-Text Modeling
• Small-Variance Asymptotics for Nonparametric Bayesian Overlapping Stochastic Blockmodels