Research
I am generally interested in machine learning, in particular, learning on graphs. My current research focuses on developing models and tools to understand and analyze the theoretical behaviors of learning algorithms on graphs, as well as their applications in various domains such as computer vision and data mining. My two favorite works are listed below.
Abstract. We find that various well-known graph-based models exhibit a common important harmonic structure in its target function - the value of a vertex is approximately the weighted average of the values of its adjacent neighbors. Understanding of such structure and analysis of the loss defined over such structure help reveal important properties of the target function over a graph. In this paper, we show that the variation of the target function across a cut can be upper and lower bounded by the ratio of its harmonic loss and the cut cost. We use this to develop an analytical tool and analyze five popular graph-based models: absorbing random walks, partially absorbing random walks, hitting times, pseudo-inverse of the graph Laplacian, and eigenvectors of the Laplacian matrices. Our analysis sheds new insights into several open questions related to these models, and provides theoretical justifications and guidelines for their practical use. Simulations on synthetic and real datasets confirm the potential of the proposed theory and tool. [PDF] [Supplemental] [Code] [Poster]
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. [PDF] [Supplemental] [Code] [Poster]