This paper explores the challenges and efficient alternatives for kernel methods on labeled directed graphs with general structure. It demonstrates that computing a strictly positive definite graph kernel is at least as hard as solving the graph isomorphism problem, and that computing inner products in a feature space indexed by all possible graphs is NP-hard. However, the paper also introduces a generalized family of kernels based on walks in the graph, which can be computed in polynomial time. These kernels capture more of the graph's structure compared to previous approaches and include special cases of existing kernels. The paper outlines the motivation, defines ideal graph kernels, discusses related work, and provides an intuitive overview of the results.This paper explores the challenges and efficient alternatives for kernel methods on labeled directed graphs with general structure. It demonstrates that computing a strictly positive definite graph kernel is at least as hard as solving the graph isomorphism problem, and that computing inner products in a feature space indexed by all possible graphs is NP-hard. However, the paper also introduces a generalized family of kernels based on walks in the graph, which can be computed in polynomial time. These kernels capture more of the graph's structure compared to previous approaches and include special cases of existing kernels. The paper outlines the motivation, defines ideal graph kernels, discusses related work, and provides an intuitive overview of the results.