Inference in Markov random fields, and development and evaluation of similarity measures for nodes in graphs, are both active areas of data-mining research. In this paper, we demonstrate a formal connection between inference in tree-structured Markov random fields and personalized PageRank, a widely-used similarity measure for graph nodes based on graph-walks. In particular we show a connection between computation of marginal probabilities in tree-structured discretevariable pairwise MRFs, and computation of similarity between vertices of a graph using the personalized PageRank measure: roughly speaking, for these MRFs, computing a marginal probability
Pr(X_i = j) can be reduced to computing a small set of personalized-PageRank similarity vectors, followed by a very limited postprocessing stage.

34 pages

This page maintained by reports@cs.cmu.edu