Transduction on Directed Graphs via Random Walks
Li Cheng
NICTA SEMINARDATE: 2013-11-29
TIME: 14:00:00 - 15:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
In this talk we consider the problem of graph-based classification, and we are particularly interested in transductive inference on directed graphs, a natural form for many real world applications including web hyperlinks, paper citations, and image based tracing. 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. Our algorithm works with the fundamental matrix, and can be regarded as maximizing the accumulated expected number of visits from the unlabelled transient states. It is also closely related to a number of existing methods, including graph kernels, PageRank, and graph Laplacian based methods. Its computational complexity and the generalization error are also studied. Empirically our algorithm has shown to perform competitively comparing to a suite of state-of-the-art graph-based classification methods.
