Partially Absorbing Random Walks: A Unified Framework for Learning on Graphs

Learning on graphs such as ranking, classification, and clustering relies on effectively and efficiently modeling graph topology. Many existing tools for exploring graph structures are based on Markov random walks or Laplacian regularization. Some popular ones include the personalized PageRank algorithm, hitting and commute times, regularized Laplacian kernels such as the pseudoinverse of graph Laplacian, and the Gaussian harmonic function method. In the past two decades, these models have been widely applied in various domains including social network analysis, biological data mining, recommender systems, natural language processing, and computer vision. In this chapter, we show that many of these models can be unified in partially absorbing random walks, a second-order Markov chain with partial absorption at each state where different models correspond to different settings of partial absorption. The unified framework enables collectively analyzing these models, which were studied separately before. Furthermore, it provides new insights for understanding model behavior and opens the door for model selection and design.