# Gibbs Sampling for Mixed Membership Stochastic Blockmodels

Mixed Membership Stochastic Blockmodels (MMSB)[1] is a generative model for links in a network. Simply put, give an adjacency matrix , MMSB assume  is governed by the memberships/topics  of each nodes. Since the original paper[1] only introduced the Variational Inference, this post derives a Gibbs Sampling method for the purpose of parameter estimation in MMSB (actually the MMSB presented in this post is slightly different from[1], as I put a prior on interaction matrix ).

The generative process of MMSB is given below:

For each node :

Draw a membership distribution vector

For each entry in :

Draw

For each pair of nodes :

Draw a membership

Draw a membership

Draw

Here is a simple explanation for the notations:

is (number of topics) dimensional hyperparameter for membership/topic distribution.

are two scalar hyperparameters for .

is the membership/topic distribution for node .

is the interaction probability matrix of memberships.

is the membership of node when it interacts with node (the link can be treated as directional, as well as unidirectional). Note that  is abbreviated for .

is the adjacency matrix, each entry is either one or zero.

Later on, I am also going to use the following notations:

is the count of node assigning to membership when it interacts with the rest nodes in the network. For directional network, it can be divided into two sets: and  (), the former is the assignment of node when it links to other nodes, the latter is the assignment of node when other nodes link to it.

is the count of linked node pairs with membership assignments and (sum up  and if don’t consider direction).

is the count of un-linked node pairs with membership assignment and (sum up and if don’t consider direction).

To perform Gibbs Sampling, we need to find the posterior for joint probability of both data and latent variables . Well, here it is:

(1)

Now that we obtained the joint probability of data and latent variables, we can start to derive the conditioned probability of latent variable as following:

(2)

(3)

Given samples of generated from Gibbs Sampling, parameters can be estimated in the following ways:

For , we have

(4)

E.q. 4 is a Dirichlet p.d.f, using Dirichlet variable property, we get the expectation(mean) of :

For , we have

(5)

E.q. 5 is a Beta p.d.f, using Beta variable property, we get the expectation(mean) of :

One may want to sample multiple de-correlated samples of to calculate the above parameters.

#### Likelihood and perplexity

Until now, I didn’t mention the formula for calculating the likelihood of data , which can be important some time for testing of convergence (or using ). In [2], the authors mentioned an approximation technique for computing , it is the harmonic mean of a set of values of from samples, where is sampled from the posterior . So that is:

Where

Using the previous derivation, we can easily compute that:

(6)

Where is a constant:

Now with , we can compute in the way:

(7)

Where , is introduced to make log-sum-exp computed correctly, usually we can set .

The likelihood of hold out data sometime is also an useful quantity, it reflects generalized predictive power of the model, and usually it is measured by perplexity, essentially it is the inverse of the geometric mean per-link likelihood. It is defined by:

This term can be evaluated by first hold out some subset of links and non-links, and evaluated by computing:

(8)

Where and are estimated in the training data.

#### Discussions

The Mixed Membership Stochastic Blockmodels is not scalable as it requires to examining edges (this is a lot even for medium size network with only thousands of nodes!), in sharp contrast to sparse networks as arise more often in real datasets. But in practice, for those non-existing edges, instead of using them all, we can sample a small portion of them, this could effectively reduce the computational complexity, especially for sparse networks where we expect the sample ratio of non-existing edges to be even fewer. However, it is still remained to be examined that the relationship between the loss of performance and sampling ratio of non-existing links.

Also due to the scalability issue, one may consider the MMSB without prior for each document topic distribution, which can be also by EM rather than Gibbs Sampling. Also, one can derive Gibbs Sampling for combined LDA and MMSB [3] in similar ways to Gibbs Sampling for LDA (see here) and MMSB individually (basically key is to derive , where ).

[1] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic blockmodels,” in Advances in neural information processing systems, 2009, pp. 33-40.
[Bibtex]
@inproceedings{airoldi2009mixed,
title={Mixed membership stochastic blockmodels},
author={Airoldi, Edoardo M and Blei, David M and Fienberg, Stephen E and Xing, Eric P},
booktitle={Advances in Neural Information Processing Systems},
pages={33--40},
year={2009}
}
[2] T. L. Griffiths and M. Steyvers, “Finding scientific topics,” Proceedings of the national academy of sciences of the united states of america, vol. 101, iss. Suppl 1, pp. 5228-5235, 2004.
[Bibtex]
@article{griffiths2004finding,
title={Finding scientific topics},
author={Griffiths, Thomas L and Steyvers, Mark},
journal={Proceedings of the National academy of Sciences of the United States of America},
volume={101},
number={Suppl 1},
pages={5228--5235},
year={2004},
}
@inproceedings{nallapati2008joint,
}