我々は、構造化データの類似度を効率的に測定するための一般的なグラフカーネルフレームワークである「伝搬カーネル（propagation kernels）」を提案する。伝搬カーネルは、与えられた複数のグラフ上で情報がどのように拡散するかをモニタリングすることに基づいている。これらのカーネルは、ランダムウォークなどの既存の伝搬スキームから得られる初期段階の分布を活用し、ノードラベル、属性、エッジ情報に符号化された構造情報を捉える。このアプローチには二つの利点がある。第一に、市販の伝搬スキームを用いることで、ラベル付き、部分ラベル付き、ラベルなし、有向、属性付きなど、さまざまなタイプのグラフに対して自然にカーネルを構築できる。第二に、既存の効率的かつ情報豊かな伝搬スキームを活用することで、予測性能を損なうことなく、最先端の手法よりも著しく高速なカーネル計算が可能となる。さらに、取り扱うグラフが規則的な構造（たとえば画像や動画データのモデリング時など）を持つ場合、その規則性を活かすことで、数千ノードを含む大規模なグラフデータベースに対してもカーネル計算をスケーラブルに実行できることが示される。これらの貢献を裏付けるために、多様な応用分野に由来する多数の実世界グラフを用いた包括的な実験を行った。