Transduction on Directed Graphs via Absorbing Random Walks
  In this paper we consider the problem of graph-based transductive
classification, and we are particularly interested in the directed graph
scenario which is a natural form for many real world applications. Different
from existing research efforts that either only deal with undirected graphs or
circumvent directionality by means of symmetrization, we propose a novel random
walk approach on directed graphs using absorbing Markov chains, which can be
regarded as maximizing the accumulated expected number of visits from the
unlabeled transient states. Our algorithm is simple, easy to implement, and
works with large-scale graphs. In particular, it is capable of preserving the
graph structure even when the input graph is sparse and changes over time, as
well as retaining weak signals presented in the directed edges. We present its
intimate connections to a number of existing methods, including graph kernels,
graph Laplacian based methods, and interestingly, spanning forest of graphs.
Its computational complexity and the generalization error are also studied.
Empirically our algorithm is systematically evaluated on a wide range of
applications, where it has shown to perform competitively comparing to a suite
of state-of-the-art methods.
