3
$\begingroup$

This is a long question but I would be very grateful if someone can help or provide some reference! And I believe this is a common confusion among beginners of MCMC.

Background

Given a directed graph $G=(V,E)$ where $V$ is the vertex set and $E\subseteq V^2$, define a labeling function $z:V \to \{1,...,k\}$ where $z$ partitions the graph in to multiple "communities" or "groups" or so-called "planted partitions" $C_1,...,C_k$

$C_i=\{v\in V: z(v)=i\}$

and $z(v),v\in V$ can be viewed as the "membership" of vertex $v$. Now also define:

  1. A cross-group edge probability matrix, or the so-called stochastic block matrix ${\bf P}$ where a vertex in partition $i$ has probability ${\bf P}(i,j)$ with a vertex in partition $j$.

  2. $e_{i,j}$ is the number of edges between partition $i$ and partition $j$ observed in $E$, $n_{i,j}$ is the maximum number of edges between partition $i$ and partition $j$. Note $e_{i,j}$ and $n_{i,j}$ are determined by $z$, or we can say they are functions of $z$.

We assume the edge set is generated by the following simple process:

for every pair of nodes $u,v$, let $(u,v) \in E$ by probability ${\bf P}(z(u),z(v))$.

This is the so-called standard stochastic block model. The probability of $E$ given $z,\bf P$ is

$\mathbb{P}\left( {E|{z},{\mathbf{P}}} \right) = \mathop \prod \limits_{i,j \in \{ 1, \ldots ,k\} } {\mathbf{P}}{(i,j)^{{e_{i,j}}}}{\left( {1 - {\mathbf{P}}(i,j)} \right)^{{n_{i,j}} - {e_{i,j}}}}$

whose log-likelihood (the MLE of ${\bf P}(i,j)$ is simply $\frac{e_{i,j}}{n_{i,j}}$, plug this back in above $\Bbb P$, take log and after some calculation) is

$\ln \mathcal{L}\left( z \right) = \mathop \sum \limits_{i,j \in \left\{ {1, \ldots ,k} \right\}} {e_{i,j}}\ln {e_{i,j}} - {n_{i,j}}\ln {n_{i,j}} + \left( {{n_{i,j}} - {e_{i,j}}} \right)\ln \left( {{n_{i,j}} - {e_{i,j}}} \right)$

there is a simplified likelihood when $E$ is assumed sparse,

$\ln \mathcal{L} = \mathop \sum \limits_{i,j \in \left\{ {1, \ldots ,k} \right\}} {e_{i,j}}\ln \frac{{{e_{i,j}}}}{{{n_{i,j}}}}$

Markov Chain Monte Carlo

Now the job is to infer $z$. I encountered three different methods that claim themselves as "Markov Chain Monte Carlo", or "Gibbs Sampler" in different literature. Some of them are not rigorous math or statistics, so they may be wrong and are causing confusions to me.

The same idea among them is to change or "re-sample" the membership of each vertexes one by one, the difference is how to make the change. Suppose now we are changing the membership of vertex $v$,

Type I.

Let $z(v)$ be the one that mostly increases $\ln \cal L$, that is, $z(v) = \arg {\max _{z(v) \in \{ 1,...,k\} }}\ln \mathcal{L}(z)$.

I am not sure but this does not look like Monte Carlo to me. It looks more like coordinate ascent from optimization. The computation of above is actually not very high, since changing $z(v)$ only requires re-computation of some of $e_{i,j}$ and $n_{i,j}$.

However, Type I makes most sense to me because it tries to maximize the likelihood.

Type II.

Re-sample $z(v)$ based on the distribution conditioned on $E$ and other values of $z$, i.e. re-sample based on $\mathbb{P}\left( {z(v)|{z^{( - v)}},E} \right)$ where $z^{(-v)}$ denotes "given all other values of $z$". If we assume the prior of $z$ as uniform, then it is easy to see $\mathbb{P}\left( {z(v)|{z^{( - v)}},E} \right) \propto \mathbb{P}\left( {E|{z^{( - v)}},z(v)} \right)$ through Bayesian's formula, then we basically just re-sample proportional to the likelihood ${\cal L}({z^{( - v)}},z(v))$.

This seems the standard Gibbs sampler that I learned from class, and its stationary distribution is $\mathbb{P}\left( {z|E} \right)$. But this does not make sense to me. Why sampling $z(v)$ while we can just greedily choose the best one as in Type I?

Type III.

Randomly choose $t$ from $1,...,k$, and let $z(v)$ be reassigned as $t$ with probability $\mathbb{P}\left( {z(v) = t|{z^{( - v)}},E} \right)$ (or we say the proposal of $z(v)=t$ is accepted), and let $z(v)$ remains where it was with probability $1-\mathbb{P}\left( {z(v) = t|{z^{( - v)}},E} \right)$ (or we say the proposal of $z(v)=t$ is rejected).

This is Monte Carlo, but I am not sure if it is equivalent to type II, not sure if it has $\mathbb{P}\left( {z|E} \right)$ as the stationary distribution. Also I am puzzled why we are doing this?

Improve this question
$\endgroup$
11
  • $\begingroup$ I also fail to understand why you replace the $\mathbf{P}(i,j)$ by an estimate when running inference on $(z,\mathbf{P})$. A standard Bayesian approach would simulate both $z$ and $\mathbf{P}$. $\endgroup$
    – Xi'an
    Mar 5, 2017 at 10:04
  • $\begingroup$ I voted for closing the question in that the goal for looking at this plug-in quantity is unclear. If you are looking for the optimum of the profile likelihood, many stochastic optimisation methods are available. If you are looking at simulating from this function, there is no particular meaning in the output since this is not a Bayesian framework. $\endgroup$
    – Xi'an
    Mar 5, 2017 at 10:16
  • $\begingroup$ @Xi'an For first question. A simple directed graph, if group $i$ has $n_i$ nodes, group $j$ has $n_j$ nodes, then $n_{i,j} = n_i \times n_j$ if $i=j$ and $n_{i,i}= n_i \times (n_i - 1)$ $\endgroup$
    – Tony
    Mar 5, 2017 at 14:07
  • $\begingroup$ I presume you mean if $i\ne j$. $\endgroup$
    – Xi'an
    Mar 5, 2017 at 14:07
  • $\begingroup$ @Xi'an For second question, when finding the optimum of a function $f(x,y)$, if you can solve $y = g(x)$ always holds for the optimum, you can plug $y=g(x)$ back in $f$, equivalent to find optimum of $f$ with restriction $y = g(x)$. In the above problem, the maximum likelihood estimator of $P_{i,j}$ is $P(i,j)= \frac{e_{i,j}}{n_{i,j}}$ no matter what $z$ is, so you can plug this back in $\ln \cal L$. To see it is a MLE, check on each group the edge formulation is i.i.d. Bernoulli, or a binomial sequence. $\endgroup$
    – Tony
    Mar 5, 2017 at 14:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.