M. Kim and J. Leskovec. ICML'12

This is a scientific paper authored by M. Kim and J. Leskovec, and appeared in ICML'12. Below is the paper summary written by Tuan Anh.

Online Version

Latent Multi-group Membership Graph Model.

Summary

This is a paper on block based network analysis and prediction. This work furthers the work by Airoldi. et. al (see Related papers) to the extent that each node/ user can actually belong to more than one block and node features are modeled in addition to link existence. The generative process is given as below (see the figure)

On the figure above, $N$, $L$, $K$ is the number of users, number of user feature categories, and number of blocks respectively. The block membership probability of node $i$ at bloc $k$ is $\phi _{ik}\in [0,1]$. Note that this model does not require $\sum _{k}\phi _{ik}=1$

• For each node $i$, and each block $k$, $\phi _{ik}$ is generated from Beta distribution: $\phi _{ik}\sim Beta(\alpha _{k1},\alpha _{k2})$
• Then
  • The truly block membership of node $i$ at block $k$ is a binary indicator which is generated from Bernoulli distribution $z_{ik}\sim Bernoulli(\phi _{ik})$
  • The features of node $i$ at feature category $l$ is a is generated from Bernoulli distribution with the parameter is computed from block membership probabilities using Logistic function
    • $F_{il}\sim Bernoulli(y_{il})$
    • where $y_{il}={\frac {1}{1+exp(w_{l}^{T}\phi _{i})}}$
  • The link between node $i$ and node $j$ is generated from Bernoulli distribution with the parameter is the product of block-wise linking probabilities
    • $A_{ij}\sim Bernoulli(p_{il})$
    • where $p_{ij}=\prod _{k}\theta _{k}(z_{ik},z_{jk})$

Given the hyperparameter $\alpha$, the other parameters are estimated by maximum likelihood function using a variational inference algorithm (see the paper for the details).

Discussion

This work consider the case when a node actually belongs to more than one block and multiple type of links can be existed among nodes. Furthermore, node features are used to regularize the block membership values of nodes. However, the notation of binary block indicator $z_{ik}$ is not well explained. $z_{ik}$ is also a hidden variable and does not a play role that is clearly distinctive from $\phi _{ik}$'s.

Related papers

• Probabilistic graph clustering: Airoldi. et. al. Mixed Membership Stochastic Blockmodels. Journal of Machine Learning Research 9 (2008) 1981-2014
• The paper by Hoff on Multiplicative latent factor models for description and prediction of social networks