Name
Abstract | ||
|---|---|---|
Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Re- duction 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 Gartner et al. (1) and 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 previ- ous 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. |
Year | Venue | Field |
|---|---|---|
2006 | NIPS | Conjugate gradient method,Linear algebra,Computer science,Artificial intelligence,Time complexity,Hilbert space,Kernel (linear algebra),Discrete mathematics,Mathematical optimization,Sylvester equation,Reproducing kernel Hilbert space,Machine learning,Computational complexity theory |
DocType | Citations | PageRank |
Conference | 36 | 2.31 |
References | Authors | |
3 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. V. N. Vishwanathan | 1 | 1991 | 131.90 |
| Karsten M. Borgwardt | 2 | 2799 | 155.36 |
| Nicol N. Schraudolph | 3 | 1185 | 164.26 |
| scholkopf | 4 | 216 | 13.73 |
| John Platt | 5 | 6611 | 1100.14 |
| Thomas Hofmann | 6 | 10064 | 1001.83 |