This paper introduces a new class of graph kernels based on shortest paths, which are computable in polynomial time, positive definite, and retain expressiveness. Existing graph kernels based on walks, subtrees, and cycles are either computationally expensive or limited in their expressiveness. The authors propose shortest-path kernels as a solution to these problems. These kernels are based on the comparison of shortest paths in graphs and are shown to outperform walk-based kernels in experiments on protein classification tasks. The paper first reviews existing graph kernels and their limitations. It then defines a graph kernel based on all paths, which is positive definite but computationally NP-hard. The authors then propose a shortest-path kernel that is computationally feasible, positive definite, and expressive. This kernel is tested on a classification task involving graph models of proteins and is shown to achieve significantly higher classification accuracy than walk-based kernels. The paper discusses the computational complexity of existing graph kernels and the problem of "tottering," where repeated visits to the same cycle can artificially inflate similarity scores. The shortest-path kernel avoids this issue by ensuring that no edge is repeated in a single path. The authors also consider variations of the shortest-path kernel, such as the equal-length shortest-path kernel and the k shortest-path kernel, and evaluate their performance. The experiments show that the shortest-path kernel outperforms walk-based kernels in classification accuracy. The results indicate that considering shortest paths rather than walks significantly improves classification performance. The paper concludes that shortest-path kernels are a promising approach for graph classification tasks, particularly in applications such as molecular biology. The authors suggest that further research is needed to explore the use of other path-related features in graph kernels.This paper introduces a new class of graph kernels based on shortest paths, which are computable in polynomial time, positive definite, and retain expressiveness. Existing graph kernels based on walks, subtrees, and cycles are either computationally expensive or limited in their expressiveness. The authors propose shortest-path kernels as a solution to these problems. These kernels are based on the comparison of shortest paths in graphs and are shown to outperform walk-based kernels in experiments on protein classification tasks. The paper first reviews existing graph kernels and their limitations. It then defines a graph kernel based on all paths, which is positive definite but computationally NP-hard. The authors then propose a shortest-path kernel that is computationally feasible, positive definite, and expressive. This kernel is tested on a classification task involving graph models of proteins and is shown to achieve significantly higher classification accuracy than walk-based kernels. The paper discusses the computational complexity of existing graph kernels and the problem of "tottering," where repeated visits to the same cycle can artificially inflate similarity scores. The shortest-path kernel avoids this issue by ensuring that no edge is repeated in a single path. The authors also consider variations of the shortest-path kernel, such as the equal-length shortest-path kernel and the k shortest-path kernel, and evaluate their performance. The experiments show that the shortest-path kernel outperforms walk-based kernels in classification accuracy. The results indicate that considering shortest paths rather than walks significantly improves classification performance. The paper concludes that shortest-path kernels are a promising approach for graph classification tasks, particularly in applications such as molecular biology. The authors suggest that further research is needed to explore the use of other path-related features in graph kernels.