ニューラルグラフ表現と強化学習を用いた近似サブグラフマッチング

要旨: 近似的なサブグラフマッチング（ASM）は、あるクエリグラフが大規模なターゲットグラフ内に近似的に存在するかを判断するタスクです。NP困難問題であるため、ASMはデータベースシステムやネットワーク科学から生化学やプライバシーに至るさまざまな応用分野にわたるグラフ分析において極めて重要です。従来の手法はしばしばヒューリスティック探索戦略を用い、グラフ情報を十分に活用できず、最適でない解に繋がることが多いです。
本論文は、グラフトランスフォーマーを用いてグラフ表現を効果的に抽出し、ASMのための RL ベースのポリシーを活用する、強化学習ベースの近似サブグラフマッチング（RL-ASM）アルゴリズムを提案します。
私たちのモデルは、2つの入力グラフから1組のノードを1度に選択して潜在的な一致を探すブランチ・アンド・バウンドアルゴリズムに基づいています。
ヒューリスティックを用いる代わりに、グラフ情報を全体として符号化する特徴表現を抽出するために Graph Transformer アーキテクチャを活用します。
RLポリシーの訓練を強化するために、模倣学習段階でエージェントを導く教師信号を用います。
その後、エピソードを通じて蓄積された長期報酬を最適化する Proximal Policy Optimization (PPO) でポリシーを微調整します。
合成データセットと実世界データセットの両方を対象とした広範な実験により、我々のRL-ASMが有効性と効率性の点で既存の手法を上回ることを示しています。
ソースコードは https://github.com/KaiyangLi1992/RL-ASM で入手可能です。