リンク予測のためのエッジ提案集合

グラフは、ソーシャルネットワークやタンパク質相互作用といった複雑な関係データをモデル化する際に一般的に用いられる枠組みであり、これらのデータは時間とともに変化する（例えば、新しい友人関係の形成）場合や、ノイズを含む（例えば、測定されていない相互作用）場合がある。リンク予測は、グラフにおける将来のエッジを予測するか、欠落しているエッジを推定することを目的としており、レコメンデーションシステム、実験設計、複雑系など多岐にわたる応用が存在する。リンク予測アルゴリズムは、グラフ内のエッジ集合に強く依存しているにもかかわらず、従来の手法では性能向上のためにグラフのトポロジーを改変するというアプローチがほとんど取られていない。本研究では、グラフに事前に追加する一連のエッジ（我々はこれを「提案セット（proposal set）」と呼ぶ）を導入するという単純な前処理ステップが、複数のリンク予測アルゴリズムの性能を向上させることを示す。その背後にある考え方は、提案セットに含まれるエッジがグラフの構造と一般的に整合している場合、リンク予測アルゴリズムが正しいエッジをより適切に予測する方向へ導かれるという点にある。言い換えれば、提案セットの追加は、信号強化を目的とした前処理ステップとして機能する。また、既存のリンク予測アルゴリズムを用いて効果的な提案セットを生成する方法を提示し、さまざまな合成データおよび実データセットを用いてこのアプローチの有効性を評価した。その結果、近傍ヒューリスティクスに基づくアルゴリズムおよびグラフニューラルネットワーク（Graph Neural Networks）を用いた手法の両方において、提案セットがリンク予測の精度を有意に向上させることを確認した。実装コードは以下のURLから公開されている：\url{https://github.com/CUAI/Edge-Proposal-Sets}。