Learning with partially absorbing random walks

Xiaoming Wu, Zhenguo Li, Anthony Man Cho So, John Wright, Shih Fu Chang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

63 Citations (Scopus)

Abstract

We propose a novel stochastic process that is with probability αibeing absorbed at current state i, and with probability 1 - αifollows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set S of low conductance will be mostly absorbed in S. Moreover, the absorption probabilities vary slowly inside S, while dropping sharply outside, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in retrieval and classification.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 25
Subtitle of host publication26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Pages3077-3085
Number of pages9
Volume4
Publication statusPublished - 1 Dec 2012
Externally publishedYes
Event26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 - Lake Tahoe, NV, United States
Duration: 3 Dec 20126 Dec 2012

Conference

Conference26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Country/TerritoryUnited States
CityLake Tahoe, NV
Period3/12/126/12/12

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this