相関ガウス特徴を用いた文脈付きグラフマッチング

Abstract

我々は、両方のネットワークにおいてエッジ重みとノード特徴量が相関しているガウス設定における文脈（コンテキスト）付きグラフマッチングを調査する。正確な復元（exact recovery）に関する情報理論的な厳密な閾値を導出し、グラフと特徴量の相関強度、ノード数、特徴量次元という観点で、ほぼ正確な復元（almost exact recovery）が可能となる条件、また不可能となる条件を特定する。興味深いことに、標準的なグラフマッチングのシナリオでは全か無かの相転移が観測されるのに対し、追加の文脈情報によりより豊かな構造が導入される。すなわち、正確な復元とほぼ正確な復元のための閾値はもはや一致しない。我々の結果は、グラフマッチングにおいて構造情報と文脈情報がどのように相互作用するかを初めて厳密に特徴付けるものであり、効率的なアルゴリズムを設計するためのベンチマークを与える。