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

Xiao Ming Wu, Zhenguo Li, Shih Fu Chang

Research output: Chapter in book / Conference proceedingChapter in an edited book (as author)Academic researchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationCooperative and Graph Signal Processing
Subtitle of host publicationPrinciples and Applications
PublisherElsevier
Pages375-396
Number of pages22
ISBN (Electronic)9780128136782
ISBN (Print)9780128136775
DOIs
Publication statusPublished - 20 Jun 2018

Keywords

  • Learning on graphs
  • Partially absorbing random walk
  • Proximity measure
  • Unified framework

ASJC Scopus subject areas

  • Medicine (miscellaneous)

Cite this