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 state-of-the- art kernel- and walk-based methods on the task of nodelabel prediction in sparsely labeled graphs. 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 network of interlinked populated places extracted from the DBpedia knowledge base.
展开▼
