カーネル手法の成功は、特に構造化データ向けの新しい正定値関数の設計を促進しました。これに対する主要な設計パラダイムは畳み込みカーネルであり、構造化されたオブジェクトをその部分に分解し、すべての部分ペアについて和をとります。一方、割り当てカーネルは部分間の最適な全単射から得られ、より妥当な類似性の概念を提供することができます。しかし一般的には、最適な割り当ては不定関数となり、これがカーネル手法での使用を複雑にします。私たちは、部分を比較するために使用される基底カーネルの一クラスを特徴付け、正定値である最適割り当てカーネルを保証するものとしました。これらの基底カーネルからヒストグラム交差によって線形時間で最適割り当てカーネルが計算されます。この結果を応用して、グラフ向けのWeisfeiler-Lehman最適割り当てカーネルを開発しました。これは広く使用されているベンチマークデータセット上で高い分類精度を提供し、元のWeisfeiler-Lehmanカーネルよりも改善しています。注：「Weisfeiler-Lehman」は固有名詞であり、「ワイスフェイラー・レハマン」とも表記されますが、ここでは原文に忠実に「Weisfeiler-Lehman」と表記しています。