Machine Learning Department
School of Computer Science, Carnegie Mellon University


Graph Walks and Graphical Models

William W. Cohen

March 2010


Keywords: Graphical models, Markov random fields, personalized PageRank, random walk with restart, graph similarity

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(Xi = j) can be reduced to computing a small set of personalized-PageRank similarity vectors, followed by a very limited postprocessing stage.

34 pages

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by