Learning with Partially Absorbing Random Walks

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 \mathcal{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.