要約
グラフカーネルは、機械学習とグラフとして符号化されたデータの間のギャップを埋める強力なツールである。大多数のグラフカーネルは、グラフをパターンの集合に分解するアプローチに基づいている。2つのグラフ間の類似性は、対応するパターン間の類似性から導かれる。線形パターンに基づくカーネルは、精度と計算複雑性の間で良好なトレードオフを実現するため、特に有用である。本研究では、異なる線形パターン、すなわちウォーク（歩行）とパス（経路）に基づくグラフカーネルについて、包括的な調査と比較を提案する。まず、これらのカーネルの数学的基礎、パターンの構造、計算複雑性について詳細に検討する。次に、ラベル付き・ラベルなしグラフ、頂点数が異なるグラフ、平均次数が異なるグラフ、循環的・非循環的グラフなど、さまざまなタイプのグラフを含む複数のベンチマークデータセットを用いて実験を実施する。最後に、回帰および分類タスクにおいて、各カーネルの性能と計算複雑性を比較・分析し、グラフデータセットの種類に応じたカーネル選定のための提案を行う。本研究により、これらのカーネルの強みと弱みが明確に比較された。また、本研究で議論されたすべてのカーネルを実装したオープンソースのPythonライブラリをGitHub上で公開しており、コミュニティに開放されている。これにより、グラフカーネルが機械学習問題における活用を促進・容易化することが期待される。