Transduction on Directed Graphs via Absorbing Random Walks

摘要

In this paper we consider the problem of graph-based transductiveclassification, and we are particularly interested in the directed graphscenario which is a natural form for many real world applications. Differentfrom existing research efforts that either only deal with undirected graphs orcircumvent directionality by means of symmetrization, we propose a novel randomwalk approach on directed graphs using absorbing Markov chains, which can beregarded as maximizing the accumulated expected number of visits from theunlabeled transient states. Our algorithm is simple, easy to implement, andworks with large-scale graphs. In particular, it is capable of preserving thegraph structure even when the input graph is sparse and changes over time, aswell as retaining weak signals presented in the directed edges. We present itsintimate 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 ofapplications, where it has shown to perform competitively comparing to a suiteof state-of-the-art methods.