We present a unified framework to study graph kernels, special cases of which
include the random walk graph kernel \citep{GaeFlaWro03,BorOngSchVisetal05},
marginalized graph kernel \citep{KasTsuIno03,KasTsuIno04,MahUedAkuPeretal04},
and geometric kernel on graphs \citep{Gaertner02}. Through extensions of linear
algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduction to a
Sylvester equation, we construct an algorithm that improves the time complexity
of kernel computation from $O(n^6)$ to $O(n^3)$. When the graphs are sparse,
conjugate gradient solvers or fixed-point iterations bring our algorithm into
the sub-cubic domain. Experiments on graphs from bioinformatics and other
application domains show that it is often more than a thousand times faster
than previous approaches. We then explore connections between diffusion kernels
\citep{KonLaf02}, regularization on graphs \citep{SmoKon03}, and graph kernels,
and use these connections to propose new graph kernels. Finally, we show that
rational kernels \citep{CorHafMoh02,CorHafMoh03,CorHafMoh04} when specialized
to graphs reduce to the random walk graph kernel.

通过扩展线性代数到再生核希尔伯特空间（RKHS）并将其简化为 Sylvester 方程的算法，我们构建了一个统一的框架来研究图形内核，这使得内核计算的时间复杂度从 O（n^6）降至 O（n^3），当图形稀疏时，共轭梯度求解器或固定点迭代带入子立方域。