複雑なネットワーク分析の効率を向上！中国の科学者が強化学習の新しい枠組みを開発

最近、中国の国立国防科学技術大学、カリフォルニア大学ロサンゼルス校、ハーバード大学医学部の研究者らが、深層強化学習フレームワーク「FINDER」を開発した。既存のソリューションと比較して、FINDER は複雑なネットワーク内で最も重要なノードのセットをより迅速かつ効率的に見つけることができるため、複雑なネットワークをより高い効率で運用できるようになります。

この研究は、Nature傘下の国際誌「Nature Machine Intelligence」に掲載され、論文のタイトルは「深層強化学習による複雑なネットワークの主要人物の発見」となっている。

論文リンク:
https://www.nature.com/articles/s42256-020-0177-2

1. FINDER: より幅広いシナリオに適用可能で、実行速度が数桁高速化

物理科学、情報科学、生物科学などの分野での研究では、ネットワークトポロジ構造を構築することで、実際の状況をシミュレートしたり予測したりすることができます。

このような複雑なネットワークの運用中、ノード間の調整が複雑なネットワークの運用効率を直接決定します。 NP 困難な問題を解決する場合、複雑なネットワーク内のノードの「分業と協力」が特に重要になります。

NP 困難問題とは、多項式時間で正しいことが検証できる問題です。たとえば、伝染病の予防と制御の分野では、複雑なネットワーク モデルを使用して伝染病の拡散をシミュレートしたり、ワクチン薬の分子の発見などに役立ちます。これらのタスクを実行する際、複雑なネットワークは、ウイルスが次の人に伝染するかどうか、特定の薬物分子が有効かどうかなど、さまざまな状況を推測して検証する必要があります。このプロセスでは、最も重要なノードを見つけることで、複雑なネットワークの運用効率を向上させることができます。

このような問題の場合、既存のソリューションは通常、大規模なネットワークをトレーニングし、特定のシナリオに対する戦略を提案することに基づいていますが、統一されたフレームワークが欠けています。対照的に、中国の国立国防科学技術大学、カリフォルニア大学ロサンゼルス校、ハーバード大学医学部の研究者らが提案したFINDERは、広範囲にわたる複雑なネットワークシナリオに適用でき、実行速度が数桁も高速です。

2. 異なる報酬関数を用いた2段階のトレーニング

FINDER フレームワークは、純粋にデータ駆動型のアプローチを採用し、2 段階でトレーニングされます。研究者らは2段階で異なる報酬関数を使ってFINDERを訓練した。

最初の段階では、FINDER は、古典的なモデルによって生成された小さな合成ネットワークを使用してオフラインでトレーニングされます。オフライントレーニングには ϵ-greedy 戦略が使用されます。

オフライン トレーニング フェーズは 3 つのステップに分かれています。まず、研究者が合成グラフのバッチを生成します。次に、研究者が合成グラフからグラフをランダムにサンプリングします。次に、FINDER フレームワークがこのグラフ上の主要なノードを見つけるプロセス全体を実行します。このプロセスでは、エージェントとグラフは一連の状態、アクション、インセンティブを通じて相互作用します。

状態に対する正しいアクションを決定するために、エージェントはまず現在のグラフをエンコードし、各ノードの埋め込みベクトルを取得します。ノードの埋め込みベクトルは、ノードの構造情報とノード機能間の長距離相互作用をキャプチャします。次に、エージェントは埋め込みベクトルをスカラー Q 値にデコードし、すべてのノードが特定のアクションを展開することによる長期的な利益を予測できるようにします。

▲オフライントレーニングフェーズのスケッチ

オフライン トレーニングが完了すると、FINDER は 2 番目のトレーニング フェーズに入り、実際のネットワーク トポロジに適用されます。研究者たちは、アライグマの接触ネットワークの最大の連結コンポーネントに対してテストを実施しました。最大の接続要素は 14 個のノードと 20 個のエッジで構成されます。

このフェーズでは、エージェントはまず現在のネットワークを低次元の埋め込みベクトルにエンコードし、次にこれらのベクトルを使用して各ノードの Q 値をデコードします。

第 2 段階では、「バッチ ノード選択」戦略を採用します。この戦略は、各適応ステップで最高の Q ノードの有限スコアを選択し、反復ごとの選択と埋め込みベクトルおよび Q 値の再計算を回避します。バッチ ノード選択戦略は最終結果には影響しませんが、時間の複雑さを数桁削減できます。

研究者たちは、複雑なネットワークがユーザー定義の終端状態に到達し、削除されたノードが最適なノードセットを形成するまで、このプロセスを繰り返します。

▲ 実際の複雑ネットワークによるトレーニングの図

3. 3つのモデルのパフォーマンスを比較すると、FINDERはキーノードを見つけるのに最も効率的である。

ロボット工学などの従来の強化学習技術（状態と動作が比較的単純）と比較すると、複雑なネットワーク技術はより複雑で、表現が困難です。研究チームの上級研究員である孫一洲氏は、これは複雑ネットワークが離散的なデータ構造を持ち、極めて高次元の空間にあるためだと述べた。

この研究では、研究者はグラフニューラルネットワーク (GNN) を使用してこの問題を解決しました。グラフ ニューラル ネットワーク内のノードはアクションを表し、グラフは状態を表します。

911 テロ攻撃予測ネットワークを例にとると、ネットワーク内の各ノードは 911 テロ攻撃に関与したテロリストを表し、各エッジはテロリストの社会的コミュニケーションを表します。

研究者らは、9/11テロ攻撃を予測したネットワーク上でFINDERフレームワークを実行し、それを既存の高次元（HD）および集合的影響（CI）手法と比較した。

下の図 d は、3 つの方法の ANC 曲線を示しています。フレームワークがアクションを展開した後、残りのノードの重要度が低いほど、フレームワークのパフォーマンスは向上します。

FINDER フレームワークは、複雑なネットワーク内のキーノードを見つけるのに最も効果的であることがわかります。他の 2 つのソリューションと比較すると、削除されたノードの重要度が増すにつれて、FINDER フレームワークを実行する複雑なネットワーク内の残りのノードの重要度は最も低くなります。

▲911テロ攻撃予測ネットワーク（青い点は残りのグラフのノード、赤い点は現在のタイムステップでFINDERによって発見されたキーノード、灰色の点は残りの孤立したノードを表します）

結論：将来的にはより多くの種類の複雑なネットワークに適用できるようになるだろう

FINDER フレームワークは、深層強化学習手法を通じてトレーニングされ、複雑なネットワーク内の重要なノードを見つけることができます。将来的には、FINDER フレームワークは、ソーシャル ネットワーク、電力ネットワーク、感染症拡散ネットワークなどのモデルのパフォーマンスを最適化するために使用される可能性があります。

現在、UCLA の研究チームは、ネットワーク科学の研究に FINDER フレームワークを使用することを計画しています。ハーバード大学医学大学院のチームは、生物学的ネットワークに FINDER を使用して、タンパク質相互作用ネットワークと遺伝子制御ネットワークの主要なプレーヤーを特定したいと考えています。

さらに研究者らは、今後は、重要なノードを見つけるフレームワークのパフォーマンスを向上させるために、より優れたグラフ表現学習アーキテクチャの設計、グラフ間、さらにはドメイン間で知識を転送する方法の検討、複雑なネットワーク上の他のNP問題の研究と解決という3つの側面に取り組む予定であると述べた。