This paper presents a unified framework for studying graph kernels, including random walk graph kernels, marginalized graph kernels, and geometric kernels on graphs. The authors extend linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduce the problem to solving a Sylvester equation, achieving a time complexity improvement from $O(n^6)$ to $O(n^3)$. For sparse graphs, conjugate gradient solvers or fixed-point iterations further reduce the complexity to sub-cubic. Experiments on bioinformatics and other datasets show that the proposed method is significantly faster than previous approaches. The paper also explores connections between diffusion kernels, regularization on graphs, and rational kernels, proposing new graph kernels. Finally, it demonstrates that rational kernels specialized for graphs reduce to random walk graph kernels.This paper presents a unified framework for studying graph kernels, including random walk graph kernels, marginalized graph kernels, and geometric kernels on graphs. The authors extend linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduce the problem to solving a Sylvester equation, achieving a time complexity improvement from $O(n^6)$ to $O(n^3)$. For sparse graphs, conjugate gradient solvers or fixed-point iterations further reduce the complexity to sub-cubic. Experiments on bioinformatics and other datasets show that the proposed method is significantly faster than previous approaches. The paper also explores connections between diffusion kernels, regularization on graphs, and rational kernels, proposing new graph kernels. Finally, it demonstrates that rational kernels specialized for graphs reduce to random walk graph kernels.