label propagation vs belief propagation?

User 512 | 6/1/2015, 10:56:48 PM

The latest GraphLab version includes a new label propagation algorithm in the graph toolkit. It looks very similar to belief propagation algorithm and both of these algorithms are trying to predict the unlabelled nodes with known labelled data. What is the difference? And which algorithm is better?



User 1592 | 6/2/2015, 3:11:56 PM

Hi Shuning, Besides of the similar name there is actually no close relation between the algorithms. Label propagation is a simple algorithm described here: Zhu, X., & Ghahramani, Z. (2002): Learning from labeled and unlabeled data with label propagation. It is a semi supervised algorithm to try and predict missing labels based on graph structure.

Belief propagation is a family of algorithms which runs on top of probabilistic graphical models. There are many variants including variants for discrete and continuous distributions, factor graphs, directed and undirected graphs, etc. the goal is to infer hidden state of the unobserved variables. The max product variant tries to infer the state (argmax) which maximizes some probability function, while the sum product variant tries to infer the marginal probability. I suggest taking the pgm course in coursera.

There is no direct way to compare those algorithms or to say which will work better. It is true that both can use for finding the best assignment of those missing values.

In GraphLab Create we have label propagation implemented and belief propagation is on our roadmap.

User 512 | 6/2/2015, 3:37:28 PM

Thanks for the information! This is very helpful. Do you know approximately when belief propagation would be available in GraphLab? It would be interesting to compare the results between these two algorithms.

User 1592 | 6/3/2015, 7:59:07 AM

We first focus on the high priority algorithms. While I love BP and did my PhD concerning Gaussian BP, it is still a low priority implementation for us as not many people use it in industry.

User 512 | 6/3/2015, 3:29:08 PM

Oh, great to know you are the expert on this! We are planning to use BP algorithm for network fraud detection, so look forward to seeing it in GraphLab!