摘要

我们提出了一种称为传播核（propagation kernels）的通用图核框架，用于高效度量结构化数据之间的相似性。传播核的核心思想是通过监测信息在一组给定图中传播的过程来捕捉图的结构特征。该方法利用随机游走等传播机制在早期阶段产生的分布，以提取节点标签、属性及边信息所编码的结构信息。这一方法具有两大优势：其一，可直接采用现成的传播机制，自然地构建适用于多种图类型的核函数，包括带标签、部分标签、无标签、有向图以及属性图等；其二，通过借助已有的高效且信息丰富的传播机制，传播核在保持与当前最先进方法相当预测性能的前提下，显著提升了计算速度。此外，我们还将证明，当所处理的图具有规则结构时（例如在建模图像或视频数据时），可有效利用这种结构规律性，从而将核计算规模扩展至包含数千个节点的大规模图数据库。我们通过在多个来自不同应用领域的实际图数据集上进行的大量实验，充分验证了所提出方法的有效性与优越性。