Abstract
While graphs with continuous node attributes arise in many applications, state-of-the-art graph kernels for comparing continuous-attributed graphs suffer from a high runtime complexity. For instance, the popular shortest path kernel scales as O(n4), where n is the number of nodes. In this paper, we present a class of graph kernels with computational complexity O(n 2(m+log n+δ2 +d)), where is the graph diameter, m is the number of edges, and d is the dimension of the node attributes. Due to the sparsity and small diameter of real-world graphs, these kernels typically scale comfortably to large graphs. In our experiments, the presented kernels outperform state-of-the-art kernels in terms of speed and accuracy on classification benchmark datasets.
| Original language | English |
|---|---|
| Journal | Advances in Neural Information Processing Systems |
| Publication status | Published - 2013 |
| Event | 27th Annual Conference on Neural Information Processing Systems, NIPS 2013 - Lake Tahoe, NV, United States Duration: 5 Dec 2013 → 10 Dec 2013 |
Bibliographical note
This work is supported by the Danish Research Council for Independent Research | Technology and Production, the Knud Høygaard Foundation, AstraZeneca, The Danish Council for Strategic Research, Netherlands Organisation for Scientic Research, and the DFG project ”Kernels for Large, Labeled Graphs (LaLa)”.The research of Professor Dr. Karsten Borgwardt was supported by the Alfried Krupp Prize for Young University Teachers of the Alfried Krupp von Bohlen und Halbach-Stiftung