用拓扑特征向量实现快速可解释的图分类,兼顾效率与精度。
Fast, Accurate and Interpretable Graph Classification with Topological Kernels
- 基于图的拓扑指标生成紧凑特征向量,结合RBF核衡量图相似性。
- 相比经典子结构核,计算速度提升最高20倍,准确率提升达12%。
- 适合追求高效且可解释图学习的工业场景或小样本应用。
我们提出一种基于拓扑指标的显式特征映射,将每个图表示为紧凑特征向量,实现快速且可解释的图分类。在这些紧凑向量上使用径向基函数核,定义图间的相似性度量。在标准分子数据集上的评估显示,仅使用单一拓扑指标的特征向量分类准确率低于当前最优的子结构核方法。然而,其雅可比矩阵计算速度最高可达魏斯费勒-莱曼子树核的20倍。为提升性能,我们提出两种扩展:1)将多个拓扑指标拼接成扩展特征向量(EFV),2)通过线性组合单个拓扑指标特征向量对应的RBF核,构建拓扑核的线性组合(LCTK)。这两种方法在所有分子数据集上实现最高12%的准确率提升。复杂度分析表明,部分向量分量存在指数级量子加速潜力。结果表明,LCTK与EFV在准确率与效率之间取得良好平衡,是实际图学习应用的有力候选方案。
原文摘要 · Abstract (English)
We introduce a novel class of explicit feature maps based on topological indices that represent each graph by a compact feature vector, enabling fast and interpretable graph classification. Using radial basis function kernels on these compact vectors, we define a measure of similarity between graphs. We perform evaluation on standard molecular datasets and observe that classification accuracies based on single topological-index feature vectors underperform compared to state-of-the-art substructure-based kernels. However, we achieve significantly faster Gram matrix evaluation -- up to $20\times$ faster -- compared to the Weisfeiler--Lehman subtree kernel. To enhance performance, we propose two extensions: 1) concatenating multiple topological indices into an \emph{Extended Feature Vector} (EFV), and 2) \emph{Linear Combination of Topological Kernels} (LCTK) by linearly combining Radial Basis Function kernels computed on feature vectors of individual topological graph indices. These extensions deliver up to $12\%$ percent accuracy gains across all the molecular datasets. A complexity analysis highlights the potential for exponential quantum speedup for some of the vector components. Our results indicate that LCTK and EFV offer a favourable trade-off between accuracy and efficiency, making them strong candidates for practical graph learning applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。