Publication
Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels
Marion Neumann; Roman Garnett; Kristian Kersting
In: Cheng Soon Ong; Tu Bao Ho (Hrsg.). Asian Conference on Machine Learning, ACML 2013. Asian Conference on Machine Learning (ACML-2013), November 13-15, Canberra, Australia, Pages 357-372, JMLR Workshop and Conference Proceedings, Vol. 29, JMLR.org, 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.