摘要
图核（Graph kernels）是连接机器学习与图结构数据之间的重要工具。大多数图核方法基于将图分解为一组模式（patterns），并通过比较对应模式之间的相似性来推断两图之间的整体相似性。基于线性模式的图核在准确率与计算复杂度之间取得了良好的平衡。本文对基于不同线性模式的图核进行了系统性的研究与比较，重点关注路径（paths）与游走（walks）两种典型线性模式。首先，本文对各类图核进行了深入分析，涵盖其数学基础、模式结构特征以及计算复杂度。随后，在多种基准数据集上开展了实验，这些数据集涵盖了不同类型和特性的图结构，包括带标签与无标签图、顶点数量不同的图、平均度数各异的图，以及含环与无环图等。在回归与分类任务中，系统比较并分析了各图核的性能表现与计算开销，进而针对不同类型的图数据集提出相应的核函数选择建议。本研究清晰揭示了各类图核在实际应用中的优势与局限。此外，为促进图核在机器学习领域的推广与应用，本文开发并开源了一个基于Python的实现库，所有讨论过的图核均已在GitHub上公开发布，供学术界与工业界自由使用与进一步研究。