%0 Conference Proceedings
%F NIPS12
%A Wu, Xiao-Ming
%A Li, Zhenguo
%A So, Anthony Man-Cho
%A Wright, John
%A Chang, Shih-Fu
%T Learning with Partially Absorbing Random Walks
%B Proceedings of Annual Conference on Neural Information Processing Systems (NIPS)
%C Lake Tahoe, NV, USA
%X We propose a novel stochastic process that is with probability $\alpha_i$ being absorbed at current state $i$, and with probability $1-\alpha_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 $\mathcal{S}$ of low conductance will be mostly absorbed in $\mathcal{S}$. Moreover, the absorption probabilities vary slowly inside $\mathcal{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
%U http://www.ee.columbia.edu/ln/dvmm/publications/12/nips2012_parw.pdf
%D 2012