To use the information from this graph to inform our CRF, we can use the graph Laplacian: where D is a diagonal degree matrix with The larger the disparity in v values of similar vertices, the larger the value of v Lv.
the matrix L is positive semi-definite, so v Lv is convex in v. If each entry v a is a linear function of the vector of marginals m described above, then v(m) Lv(m) is convex in m. for any linear v(m), we can use this Laplacian expression as a PR penalty.