17日前

部分グラフマッチングのための微分可能Top-Kを用いた深層学習

{Junchi Yan, Xiaokang Yang, Shaofei Jiang, Ziao Guo, Runzhong Wang}
部分グラフマッチングのための微分可能Top-Kを用いた深層学習
要約

グラフマッチング(GM)は、マッチングされた要素間のノードおよびエッジワイズな類似度を最大化することにより、グラフ間のノード対応関係を発見することを目的とする。NP困難な問題であるため、実用上頻出する外れノード(outlier node)を含む状況下ではその課題がさらに顕著になる。特に視覚系の問題においては、外れノードの存在は普遍的な現象である。しかし、従来の類似度最大化に基づくアプローチは、誤マッチングを抑制する体系的な枠組みを欠き、手動で設定された閾値を用いて外れノードを除外するにとどまっている。この制限は、理想的な外れノードなし設定において優れた性能を示すニューラルGMソルバーにも引き継がれている。本研究では、内点(inlier)数kが事前に与えられたり推定されたりする条件下で、部分的グラフマッチング(partial GM)問題を「トップk選択」タスクとして定式化する。具体的には、最適輸送層における効果的な勾配降下を可能にする微分可能なトップkモジュールを設計した。このモジュールは、二次的マッチングネットワークNGMv2や線形マッチングネットワークGCANを含む最先端の深層GMパイプラインに容易に統合可能である。同時に、注意メカニズムを統合したアグリゲーション層を導入し、kの推定を可能とすることで、実世界における自動的な外れノード耐性マッチングを実現した。最後に、IMC-PTステレオマッチングデータセットから着想を得た新しいベンチマーク「IMC-PT-SparseGM」を再構築・公開した。この新ベンチマークは、スケール変動が大きいグラフや実世界由来の部分マッチングインスタンスを多数含んでおり、より現実的な評価環境を提供する。実験の結果、提案手法は既存の部分マッチング手法を、代表的なベンチマークにおいて上回ることを示した。