チャネル独立埋め込みとハンガリアンアテンションを用いた深層グラフマッチングの学習

グラフマッチングは、二つのグラフ間でノード同士の対応関係を確立することを目的とする問題であり、古典的な組合せ最適化問題として知られ、一般にはNP完全である。近年まで、この分野では深層学習に基づくグラフマッチング手法が登場するまで、従来のアプローチが主に用いられてきた。しかし、最近では深層ネットワークを活用した深層グラフマッチング手法が、従来にない高いマッチング精度を達成するようになりつつある。本研究は、この流れに沿って、既存手法に容易に統合可能な二つの補完的な貢献を提供する。第一に、アテンションモデルにおけるマルチヘッド戦略を模倣する新しいノードおよびエッジ埋め込み戦略を提案する。この戦略により、各チャネル内の情報が独立して統合可能となる。これに対して、従来の手法ではノード埋め込みのみが考慮されていた。第二に、損失関数上に普遍的なマスキング機構を設計し、グラフマッチングにおける目的関数の学習の滑らかさを向上させる。さらに、ハンガリアンアルゴリズムを用いて、最も寄与度の高いマッチングペアをハードアテンションとして捉え、構造的かつ疎接続なレイヤーを動的に構築する。本手法は、三つの公開ベンチマークにおけるマッチング精度において、競争力のある性能を発揮し、既存の最先端手法に対してもプラグインとして適用可能であり、その性能をさらに向上させることを示している。