Stochastic Block Model

[abojchevski]

Can I define/learn a stochastic block model (SBM) with edward, and if I can what inference engine should I use?

With pymc3 I would define SBM, for some value K (number of blocks/clusters) as such:

# group assignment probabilities
pi = Dirichlet(name='pi', a=5 * np.ones(K)) 
# group assignments for nodes
q = Categorical(name='q', p=pi, shape=N) 
# connection probabilities among groups
eta = Beta(name='eta', alpha=1, beta=1, shape=(K, K))
# adjacency matrix
R = Bernoulli(name='R', p=eta[q, :][:, q], observed=R_observed, shape=(N, N))

As a probabilistic graphical model it would look like this:

In other words I model my graph (with N nodes and some edges) by modeling the adjacency matrix R. Each edge i, j is independent from the other edges and is generated as such:

1. sample pi from Dirichlet
2. sample q_i the categorical cluster assignment for the i-th node given pi
3. sample q_j the categorical cluster assignment for the j-th node given pi
4. from the K x K matrix of Beta variables pick the Beta variable corresponding to the cluster assignments (e.g. q_i=a and q_j=b => we sample from the Beta variable at index a, b)
5. form an edge according to a Bernoulli with probability of 1 given the chosen Beta in the previous step

The adjacency matrix R is what is observed, and I would like to learn the latent eta and q. The MCMC approach with pycm3 works well enough, but a variational approach might be better.

If this kind of question is not suited here please let me know.

[dustinvtran]

Hi @abojchevski. A stochastic blockmodel can be fit using the variational inference engine here. To do so here, you would write down the log joint density which is the sum of the log Dirichlet density, Categorical densities, and Bernoulli. We'll have a mixture model example soon to demonstrate this so I'm keeping this issue open.

[abojchevski]

@dustinvtran Thanks for the reply. I'll give it a try myself as well.

[alexlenail]

@dustinvtran Hello! I'm also interested in (Mixed Membership) Stochastic Block Models. It seems like the relevant example you post here is outdated (following the link). What might be a relevant example for figuring out how to implement this model in Edward?

[dustinvtran]

I think a very fast and distributed implementation of MMSB would try to vectorize a lot of its data generating process. Take a look at the matrix factorization and latent space model tutorials/examples. My guess is you can write MMSB in this matrix factorization approach where one of the factors is composed of many indicator rows.

[alexlenail]

This isn't quite my expertise. I found this method from graph-tool which solves my problem for now. Thanks!

[dustinvtran]

Consider modeling an n x n adjacency matrix Y. Write it as a matrix product, Y = Zpq^T B Zqp, where Zpq and Zqp are n x k matrices of people-by-membership (each row is a one-hot vector) and B is a k x k matrix of parameters. Writing these as distributions, for example,

Y = Bernoulli(probs=tf.matmul(tf.matmul(Zpq, B, transpose_a=True), Zqp))

a multinomial distribution for Zpq,Zqp and

B = tf.Variable(tf.zeros([K, K]))

should work.

[alexlenail]

Hmm I think that's the entire model you've just described, isn't it? That's elegant. =)

[dustinvtran]

Fixed in #715.