核方法的成功激发了新型正半定函数的设计，特别是针对结构化数据。其中一种主要的设计范式是卷积核，它将结构化对象分解为其组成部分，并对所有部分对进行求和。相比之下，分配核则是通过部分之间的最优双射获得的，这可以提供更为合理的相似性度量。然而，一般来说，最优分配会产生不定函数，这使得它们在核方法中的应用变得复杂。我们刻画了一类用于比较部分的基本核函数，这些基本核函数能够保证正半定的最优分配核。这些基本核函数生成了层次结构，通过直方图交集可以在线性时间内计算出最优分配核。我们利用这些结果开发了适用于图的Weisfeiler-Lehman最优分配核。该核在广泛使用的基准数据集上提供了较高的分类准确性，优于原始的Weisfeiler-Lehman核。