NIPS12

Xiao-Ming Wu, Zhenguo Li, Anthony Man-Cho So, John Wright, Shih-Fu Chang. Learning with Partially Absorbing Random Walks. In Proceedings of Annual Conference on Neural Information Processing Systems (NIPS), Lake Tahoe, NV, USA, 2012.

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Note on this paper

Supplementary material available here

Abstract

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

BibTex Reference

@InProceedings{NIPS12,
Author = {Wu, Xiao-Ming and Li, Zhenguo and So, Anthony Man-Cho and Wright, John and Chang, Shih-Fu},
Title = {Learning with Partially Absorbing Random Walks},
BookTitle = {Proceedings of Annual Conference on Neural Information Processing Systems (NIPS)},
Address = {Lake Tahoe, NV, USA},
Year = {2012}
}

EndNote Reference [help]

Get EndNote Reference (.ref)

For problems or questions regarding this web site contact The Web Master.

This document was translated automatically from BibTEX by bib2html (Copyright 2003 © Eric Marchand, INRIA, Vista Project).