How does PGM relate to graph theory?

The first part of the Probabilistic Graphical Models course on Coursera finished some weeks ago. I also finished it, but this time as a mentor, instead of a learner.

It was a rewarding experience. I got to talk to a few Coursera employees (whose office is somewhere in Mountain View), and the big, versatile community of Coursera mentors, ranging from retirees in the US, professors in Portugal to some dudes in Cologne. I got to learn how to do online communication constructively, why I should always start with something positive, how to ask questions and stimulate discussions, how to respectfully communicate your opinion without making other people feeling insulted or taking it personal, how to recognize and differentiate between trolls (people who argue only for the sake of arguments) and activists, who really want to change people opinions, etc…

But the most important thing is the more I explain stuff to people, the better I understand it. This applies to almost everything I know, and was partly the reason why I started this blog, but this time it applies at a slightly bigger scale.

There you go. Being a mentor is not only about the mentee, that you gotta teach them lessons, sometimes it is more about you, and often that is even more important.

There are several interesting questions raised during the course, this is one of them:

I keep hearing about graph theory.. How does PGM relate to graph theory?
Is it graph theory, a subset of graph theory, or unrelated?

This is rather a strange question. I learned both graph theory and Graphical Models, but I never really ask myself such a question. Nonetheless, sometimes when you put things that seems unrelated together, and start making reflections, you will learn more about each one of those things. This is such a case. I think it worths an entry:

Hi <>,

This is an interesting question!

I think graphs are used in PGM mainly because it helps with our reasoning. Once we visualize the random variables as vertices and dependencies as edges in a graph, all the reasoning about independencies, d-separation, Markov blankets, etc… becomes very intuitive. PGM itself was built on top of a strong theory of probabilities and random variables, while I haven’t seen many applications of graph theory per-se in PGM.

Probably the only connection between the two fields is we borrow concepts in graph theory (graph, vertices and edges) to represent concepts in probabilistic model (model, random variables and dependencies, correspondingly).

Much of graph theory deal with finding paths, weighted edges, clusters of vertices, flows, etc… which are used heavily in many other areas, but, to the best of my knowledge, not in PGM just yet.

On the other side, PGM has some interesting extension that is not quite “fitted” with traditional graph theory, like template models and so on.

That being said, graphs is a very strong and useful tool for reasoning in complicated problems. We can recall some problems you might already know that use a graph: knowledge base inference, many problems in scheduling that use graph coloring, even mind-maps are graphs by a broad definition of the term! Many problems in CS become easier once modelled as a graph, and PGM is a notable example.

This is what I have for the moment, and I would love to learn what you think!

By the way, I will also be a mentor for the second and third parts of the course. Although I will only be able to spend couple of hours a week for this mentoring exercise, feel free to reach out to me if you follow the course.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s