Poster
Learning with Partially Absorbing Random Walks
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang · John Wright · Anthony Man-Cho So
Harrah’s Special Events Center 2nd Floor
[
Abstract
]
Abstract:
We propose a novel stochastic process that is with probability αi being absorbed at current state i, and with probability 1−αi follows 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 S, 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 graph-based learning.
Live content is unavailable. Log in and register to view live content