Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels

Marion Neumann, Roman Garnett, Kristian Kersting
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:357-372, 2013.

Abstract

Exploiting autocorrelation for node-label prediction in networked data has led to great success. However, when dealing with sparsely labeled networks, common in present-day tasks, the autocorrelation assumption is difficult to exploit. Taking a step beyond, we propose the coinciding walk kernel (cwk), a novel kernel leveraging label-structure similarity – the idea that nodes with similarly arranged labels in their local neighbourhoods are likely to have the same label – for learning problems on partially labeled graphs. Inspired by the success of random walk based schemes for the construction of graph kernels, cwk is defined in terms of the probability that the labels encountered during parallel random walks coincide. In addition to its intuitive probabilistic interpretation, coinciding walk kernels outperform existing kernel- and walk-based methods on the task of node-label prediction in sparsely labeled graphs with high label-structure similarity. We also show that computing cwks is faster than many state-of-the-art kernels on graphs. We evaluate cwks on several real- world networks, including cocitation and coauthor graphs, as well as a graph of interlinked populated places extracted from the dbpedia knowledge base.

Cite this Paper

BibTeX
@InProceedings{pmlr-v29-Neumann13, title = {Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels}, author = {Neumann, Marion and Garnett, Roman and Kersting, Kristian}, booktitle = {Proceedings of the 5th Asian Conference on Machine Learning}, pages = {357--372}, year = {2013}, editor = {Ong, Cheng Soon and Ho, Tu Bao}, volume = {29}, series = {Proceedings of Machine Learning Research}, address = {Australian National University, Canberra, Australia}, month = {13--15 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v29/Neumann13.pdf}, url = {https://proceedings.mlr.press/v29/Neumann13.html}, abstract = {Exploiting autocorrelation for node-label prediction in networked data has led to great success. However, when dealing with sparsely labeled networks, common in present-day tasks, the autocorrelation assumption is difficult to exploit. Taking a step beyond, we propose the coinciding walk kernel (cwk), a novel kernel leveraging label-structure similarity – the idea that nodes with similarly arranged labels in their local neighbourhoods are likely to have the same label – for learning problems on partially labeled graphs. Inspired by the success of random walk based schemes for the construction of graph kernels, cwk is defined in terms of the probability that the labels encountered during parallel random walks coincide. In addition to its intuitive probabilistic interpretation, coinciding walk kernels outperform existing kernel- and walk-based methods on the task of node-label prediction in sparsely labeled graphs with high label-structure similarity. We also show that computing cwks is faster than many state-of-the-art kernels on graphs. We evaluate cwks on several real- world networks, including cocitation and coauthor graphs, as well as a graph of interlinked populated places extracted from the dbpedia knowledge base.} }
Endnote
%0 Conference Paper %T Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels %A Marion Neumann %A Roman Garnett %A Kristian Kersting %B Proceedings of the 5th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Cheng Soon Ong %E Tu Bao Ho %F pmlr-v29-Neumann13 %I PMLR %P 357--372 %U https://proceedings.mlr.press/v29/Neumann13.html %V 29 %X Exploiting autocorrelation for node-label prediction in networked data has led to great success. However, when dealing with sparsely labeled networks, common in present-day tasks, the autocorrelation assumption is difficult to exploit. Taking a step beyond, we propose the coinciding walk kernel (cwk), a novel kernel leveraging label-structure similarity – the idea that nodes with similarly arranged labels in their local neighbourhoods are likely to have the same label – for learning problems on partially labeled graphs. Inspired by the success of random walk based schemes for the construction of graph kernels, cwk is defined in terms of the probability that the labels encountered during parallel random walks coincide. In addition to its intuitive probabilistic interpretation, coinciding walk kernels outperform existing kernel- and walk-based methods on the task of node-label prediction in sparsely labeled graphs with high label-structure similarity. We also show that computing cwks is faster than many state-of-the-art kernels on graphs. We evaluate cwks on several real- world networks, including cocitation and coauthor graphs, as well as a graph of interlinked populated places extracted from the dbpedia knowledge base.
RIS
TY - CPAPER TI - Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels AU - Marion Neumann AU - Roman Garnett AU - Kristian Kersting BT - Proceedings of the 5th Asian Conference on Machine Learning DA - 2013/10/21 ED - Cheng Soon Ong ED - Tu Bao Ho ID - pmlr-v29-Neumann13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 29 SP - 357 EP - 372 L1 - http://proceedings.mlr.press/v29/Neumann13.pdf UR - https://proceedings.mlr.press/v29/Neumann13.html AB - Exploiting autocorrelation for node-label prediction in networked data has led to great success. However, when dealing with sparsely labeled networks, common in present-day tasks, the autocorrelation assumption is difficult to exploit. Taking a step beyond, we propose the coinciding walk kernel (cwk), a novel kernel leveraging label-structure similarity – the idea that nodes with similarly arranged labels in their local neighbourhoods are likely to have the same label – for learning problems on partially labeled graphs. Inspired by the success of random walk based schemes for the construction of graph kernels, cwk is defined in terms of the probability that the labels encountered during parallel random walks coincide. In addition to its intuitive probabilistic interpretation, coinciding walk kernels outperform existing kernel- and walk-based methods on the task of node-label prediction in sparsely labeled graphs with high label-structure similarity. We also show that computing cwks is faster than many state-of-the-art kernels on graphs. We evaluate cwks on several real- world networks, including cocitation and coauthor graphs, as well as a graph of interlinked populated places extracted from the dbpedia knowledge base. ER -
APA
Neumann, M., Garnett, R. & Kersting, K.. (2013). Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels. Proceedings of the 5th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 29:357-372 Available from https://proceedings.mlr.press/v29/Neumann13.html.

Related Material