nips nips2006 nips2006-77 nips2006-77-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Karsten M. Borgwardt, Nicol N. Schraudolph, S.v.n. Vishwanathan
Abstract: Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Reduction to a Sylvester equation allows us to compute many of these kernels in O(n3 ) worst-case time. This includes kernels whose previous worst-case time complexity was O(n6 ), such as the geometric kernels of G¨ rtner et al. [1] and a the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed and undirected graphs more effectively than previous methods, yielding sub-cubic computational complexity when combined with conjugate gradient solvers or fixed-point iterations. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than 1000 times faster than existing approaches. 1
[1] T. G¨ rtner, P. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient alternatives. In a B. Sch¨ lkopf and M. K. Warmuth, editors, Proc. Annual Conf. Comput. Learning Theory. Springer, 2003. o
[2] H. Kashima, K. Tsuda, and A. Inokuchi. Kernels on graphs. In K. Tsuda, B. Sch¨ lkopf, and J. Vert, editors, o Kernels and Bioinformatics, Cambridge, MA, 2004. MIT Press.
[3] K. M. Borgwardt, C. S. Ong, S. Schonauer, S. V. N. Vishwanathan, A. J. Smola, and H. P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(Suppl 1):i47–i56, 2005.
[4] F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1969.
[5] J. D. Gardiner, A. L. Laub, J. J. Amato, and C. B. Moler. Solution of the Sylvester matrix equation AXB + CXD = E. ACM Transactions on Mathematical Software, 18(2):223–231, 1992.
[6] C. F. V. Loan. The ubiquitous kronecker product. Journal of Computational and Applied Mathematics, 123:85 – 100, 2000.
[7] J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research, 1999.
[8] G. H. Golub and C. F. Van Loan. Matrix Computations. John Hopkins University Press, Baltimore, MD, 3rd edition, 1996.