ニューラルグラフマッチングネットワーク：Lawlerの二次割当問題の学習とハイパーブラフおよび複数グラフマッチングへの拡張

グラフマッチングは、エッジ間の親和性行列に基づく組合せ最適化を含んでおり、一般的にはロウラーの二次割当問題（Quadratic Assignment Problem: QAP）として定式化されます。本論文では、親和性行列（または関連グラフ）を直接学習するQAPネットワークを提案し、マッチング問題を制約付き頂点分類タスクに変換します。関連グラフは、頂点分類のための埋め込みネットワークによって学習され、その後シンクホーン正規化とクロスエントロピー損失が用いられてエンドツーエンドで学習されます。さらに、我々はシンクホーンに基づくマッチング認識制約とダミーノードの導入により、異なるサイズのグラフに対応するための関連グラフ上の埋め込みモデルを改善しています。我々の知る限り、これは一般的なロウラーのQAPを直接学習する最初のネットワークの一つです。一方、最近の深層マッチング手法は主に2つのグラフにおけるノード/エッジ特徴量の学習に焦点を当てています。また、我々のネットワークをハイパーグラフマッチングや複数グラフのマッチングへ拡張する方法も示します。合成グラフと実世界画像に対する実験結果はその有効性を示しています。合成データとQAPLIBベンチマークにおける純粋なQAPタスクにおいて、我々的方法は競争力があり、時間コストが大幅に少ないにもかかわらず最先端のグラフマッチングおよびQAPソルバーよりも優れた性能を発揮します。プロジェクトホームペー ジは http://thinklab.sjtu.edu.cn/project/NGM/index.html で提供されています。