Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18)

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Downloads (Pure)

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. 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.
Original languageEnglish (US)
Title of host publicationMining and Learning with Graphs Workshop @ ACM KDD 2018
Pages1
Number of pages8
StatePublished - Aug 20 2018

Fingerprint Dive into the research topics of 'Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18)'. Together they form a unique fingerprint.

  • Prizes

    MLG@KDD2018 - Best Paper Award

    Nikolakopoulos, Athanasios (Recipient), Aug 20 2018

    Prize: Prize (including medals and awards)

    Cite this

    Berberidis, D., Nikolakopoulos, A., & Giannakis, G. B. (2018). Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18). In Mining and Learning with Graphs Workshop @ ACM KDD 2018 (pp. 1)