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

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

15 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

Labels
Landing
Scalability
Classifiers
Topology
Hot Temperature
Deep neural networks

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)

Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18). / Berberidis, Dimitris; Nikolakopoulos, Athanasios; Giannakis, Georgios B.

Mining and Learning with Graphs Workshop @ ACM KDD 2018. 2018. p. 1.

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

Berberidis, D, Nikolakopoulos, A & Giannakis, GB 2018, Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18). in Mining and Learning with Graphs Workshop @ ACM KDD 2018. pp. 1.
Berberidis D, Nikolakopoulos A, Giannakis GB. Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18). In Mining and Learning with Graphs Workshop @ ACM KDD 2018. 2018. p. 1
Berberidis, Dimitris ; Nikolakopoulos, Athanasios ; Giannakis, Georgios B. / Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18). Mining and Learning with Graphs Workshop @ ACM KDD 2018. 2018. pp. 1
@inproceedings{b5081e0ad6ef4a74b84737bfbd0ea3d9,
title = "Adaptive Diffusions for Scalable Learning over Graphs (MLG@KDD18)",
abstract = "Diffusion-based classifiers such as those relying on the PersonalizedPageRank and the Heat kernel, enjoy remarkable classification accuracyat modest computational requirements. Their performancehowever is affected by the extent to which the chosen diffusion capturesa typically unknown label propagation mechanism, that can bespecific to the underlying graph, and potentially different for eachclass. The present work introduces a disciplined, data-efficient approachto learning class-specific diffusion functions adapted to the underlyingnetwork topology. The novel learning approach leveragesthe notion of “landing probabilities” of class-specific random walks,which can be computed efficiently, thereby ensuring scalability tolarge graphs. This is supported by rigorous analysis of the propertiesof the model as well as the proposed algorithms. Classificationtests on real networks demonstrate that adapting the diffusion functionto the given graph and observed labels, significantly improvesthe performance over fixed diffusions; reaching--and many timessurpassing--the classification accuracy of computationally heavierstate-of-the-art competing methods, that rely on node embeddingsand deep neural networks.",
author = "Dimitris Berberidis and Athanasios Nikolakopoulos and Giannakis, {Georgios B}",
year = "2018",
month = "8",
day = "20",
language = "English (US)",
pages = "1",
booktitle = "Mining and Learning with Graphs Workshop @ ACM KDD 2018",

}

TY - GEN

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

AU - Berberidis, Dimitris

AU - Nikolakopoulos, Athanasios

AU - Giannakis, Georgios B

PY - 2018/8/20

Y1 - 2018/8/20

N2 - Diffusion-based classifiers such as those relying on the PersonalizedPageRank and the Heat kernel, enjoy remarkable classification accuracyat modest computational requirements. Their performancehowever is affected by the extent to which the chosen diffusion capturesa typically unknown label propagation mechanism, that can bespecific to the underlying graph, and potentially different for eachclass. The present work introduces a disciplined, data-efficient approachto learning class-specific diffusion functions adapted to the underlyingnetwork topology. The novel learning approach leveragesthe notion of “landing probabilities” of class-specific random walks,which can be computed efficiently, thereby ensuring scalability tolarge graphs. This is supported by rigorous analysis of the propertiesof the model as well as the proposed algorithms. Classificationtests on real networks demonstrate that adapting the diffusion functionto the given graph and observed labels, significantly improvesthe performance over fixed diffusions; reaching--and many timessurpassing--the classification accuracy of computationally heavierstate-of-the-art competing methods, that rely on node embeddingsand deep neural networks.

AB - Diffusion-based classifiers such as those relying on the PersonalizedPageRank and the Heat kernel, enjoy remarkable classification accuracyat modest computational requirements. Their performancehowever is affected by the extent to which the chosen diffusion capturesa typically unknown label propagation mechanism, that can bespecific to the underlying graph, and potentially different for eachclass. The present work introduces a disciplined, data-efficient approachto learning class-specific diffusion functions adapted to the underlyingnetwork topology. The novel learning approach leveragesthe notion of “landing probabilities” of class-specific random walks,which can be computed efficiently, thereby ensuring scalability tolarge graphs. This is supported by rigorous analysis of the propertiesof the model as well as the proposed algorithms. Classificationtests on real networks demonstrate that adapting the diffusion functionto the given graph and observed labels, significantly improvesthe performance over fixed diffusions; reaching--and many timessurpassing--the classification accuracy of computationally heavierstate-of-the-art competing methods, that rely on node embeddingsand deep neural networks.

UR - http://www.mlgworkshop.org/2018/papers/MLG2018_paper_21.pdf

M3 - Conference contribution

SP - 1

BT - Mining and Learning with Graphs Workshop @ ACM KDD 2018

ER -