31
$\begingroup$

Introductions to graphical models describe them as "... a marriage between graph theory and probability theory."

I get the probability theory part but I have trouble understanding where exactly graph theory fits in. What insights from graph theory have helped deepen our understanding of probability distributions and decision making under uncertainty?

I am looking for concrete examples, beyond the obvious use of graph theoretic terminology in PGMs, such as classifying a PGM as a "tree" or "bipartite" or "undirected", etc.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
36
$\begingroup$

There is very little true mathematical graph theory in probabilistic graphical models, where by true mathematical graph theory I mean proofs about cliques, vertex orders, max-flow min-cut theorems, and so on. Even something as fundamental as Euler's Theorem and Handshaking Lemma are not used, though I suppose one might invoke them to check some property of computer code used to update probabilistic estimates. Moreover, probabilist graphical models rarely use more than a subset of the classes of graphs, such as multi-graphs. Theorems about flows in graphs are not used in probabilistic graphical models.

If student A were an expert in probability but knew nothing about graph theory, and student B were an expert in graph theory but knew nothing about probability, then A would certainly learn and understand probabilistic graphical models faster than would B.

Improve this answer
$\endgroup$
0
8
$\begingroup$

In a strict sense, graph theory seems loosely connected to PGMs. However, graph algorithms come in handy. PGMs started with message-passing inference, which is a subset of general class of message-passing algorithms on graphs (may be, that is the reason for the word “graphical” in them). Graph-cut algorithms are widely used for Markov random field inference in computer vision; they are based on the results akin to Ford–Fulkerson theorem (max flow equals min cut); most popular algorithms are probably Boykov–Kolmogorov and IBFS.

References. [Murphy, 2012, §22.6.3] covers graph cuts usage for MAP inference. See also [Kolmogorom and Zabih, 2004; Boykov et al., PAMI 2001], which cover optimization rather than modelling.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Interesting to note that graph-cut algorithms are used in MRFs. Could you point to a reference? Based on David Stork's answer above, it seems like these algorithms arise due to the fact that graph theory was a useful modeling tool, rather than some fundamental connection between graph theory and PGMs. $\endgroup$
    – Vimal
    Commented Jul 4, 2015 at 2:53
  • 1
    $\begingroup$ @overrider could you provide full references so the papers could be easily searched..? Googling may lead people to the references, but could also end up with wasting time for irrelevant results. So titles, publishers, journal names, links etc. are good thing to add. $\endgroup$
    – Tim
    Commented Jul 6, 2015 at 17:43
  • 2
    $\begingroup$ Graph cut algorithms are useful in computer vision but not probabilistic graphical models. One problem in stereo vision is the correspondence problem: finding which points in image A correspond to points in image B. One can set up a graph where the vertices correspond to feature points in the two images and a graph represents all possible correspondences. Then the problem of finding the "proper" correspondences can be cast as a graph-cut problem. There is no such use in generic graphical models, though I suppose one could try to map this computer vision problem onto graphical models. $\endgroup$
    – David G. Stork
    Commented Jul 6, 2015 at 17:53
  • 2
    $\begingroup$ @DavidG.Stork There are other computer vision problems that apply graph cuts in a similar way: image segmentation, making collages, etc., so the approach is general enough. Those problems can be naturally expressed in terms of undirected graphical models (although papers do not always do that). That allows using different MRF inference algorithms, as well as model fitting. On the other hand, graph cuts can optimize a quite large subset of MRFs, thus can be applied beyond vision, e.g. for social network analysis (although I cannot recall specific papers now). $\endgroup$
    – Roman Shapovalov
    Commented Jul 7, 2015 at 9:05
  • 1
    $\begingroup$ @overrider providing links is great but links have tendency to die, so always it is better to provide a full reference. Someone may find your answer in several months time, when some of the links can be already inactive. $\endgroup$
    – Tim
    Commented Jul 7, 2015 at 9:25
4
$\begingroup$

There has been some work investigating the link between the ease of decoding of Low Density Parity Check codes (which gets excellent results when you consider it a probablistic graph and apply Loopy Belief Propagation), and the girth of the graph formed by the parity check matrix. This link to girth goes right the way back to when LDPCs were invented[1] but there's been further work in the last decade or so[2][3] after the were separately rediscovery by Mackay et al [4] and their properties noticed.

I often see pearl's comment on the convergence time of belief propagation depending on the diameter of the graph being cited. But I don't know of any work looking at graph diameters in non-tree graphs and what effect that has.

  1. R. G. Gallager. Low Density Parity Check Codes. M.I.T. Press, 1963
  2. I.E. Bocharova, F. Hug, R. Johannesson, B.D. Kudryashov, and R.V. Satyukov. New low-density parity-check codes with large girth based on hypergraphs. In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 819 –823, 2010.
  3. S.C. Tatikonda. Convergence of the sum-product algorithm. In Information Theory Workshop, 2003. Proceedings. 2003 IEEE, pages 222 – 225, 2003
  4. David J. C. MacKay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, 33(6):457–458, 1997.
Improve this answer
$\endgroup$
2
$\begingroup$

One successful application of graph algorithms to probabilistic graphical models is the Chow-Liu algorithm. It solves the problem of finding the optimum (tree) graph structure and is based on maximum spanning trees (MST) algorithm.

A joint probability over a tree graphical model can be written as: \begin{equation} p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)} \end{equation} We can write down a normalized log-likelihood as follows: \begin{equation} \frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st}) \end{equation} where $I(x_s;x_t|\theta_{st})$ is the mutual information between $x_s$ and $x_t$ given the empirical Maximum Likelihood (ML) distribution which counts the number of times a node $x$ was in state $k$. Since the first term is independent of the topology $T$, we can ignore it and focus on maximizing the second term.

The log-likelihood is maximized by computing the maximum weight spanning tree, where the edge weights are the pairwise mutual information terms $I(x_s;x_t|\theta_{st})$. The maximum weight spanning tree can be found using Prim's algorithm and Kruskal's algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi Vadim. Thanks for your response. As a formulation in graph theoretic terms, it makes sense. But one could see it as an optimisation problem as well. The spirit of the question was to enquire a more fundamental connection. For instance, one can formulate the sorting problem as a topological sort on a graph, where the nodes are numbers, and arrows denote <= relationship. But that doesn't make a fundamental connection between sorting and graph algorithms, right? $\endgroup$
    – Vimal
    Commented Nov 2, 2017 at 22:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.