Title: Adaptive Diffusions for Scalable Learning over Graphs,
Abstract: Diffusion-based classifiers such as those relying on the Personalized
PageRank and the Heat kernel, enjoy remarkable classification accuracy at
modest computational requirements. Their performance however is affected by the
extent to which the chosen diffusion captures a typically unknown label
propagation mechanism, that can be specific to the underlying graph, and
potentially different for each class. The present work introduces a
disciplined, data-efficient approach to learning class-specific diffusion
functions adapted to the underlying network topology. The novel learning
approach leverages the notion of "landing probabilities" of class-specific
random walks, which can be computed efficiently, thereby ensuring scalability
to large graphs. This is supported by rigorous analysis of the properties of
the model as well as the proposed algorithms. Furthermore, a robust version of
the classifier facilitates learning even in noisy environments.
Classification tests on real networks demonstrate that adapting the diffusion
function to the given graph and observed labels, significantly improves the
performance over fixed diffusions; reaching -- and many times surpassing -- the
classification accuracy of computationally heavier state-of-the-art competing
methods, that rely on node embeddings and deep neural networks.