DEIM2023

1b-8-3

マルチエージェント強化学習に基づく
ソーシャルネットワークの将来予測手法
三宅健太郎†

伊藤 寛祥†

Christos Faloutsos††

森嶋 厚行†† 筑波大学†† Carnegie Mellon University
E-mail: †s2113591@klis.tsukuba.ac.jp, ††ito@slis.tsukuba.ac.jp, †††christos@cs.cmu.edu,††††morishima-oﬃce@ml.cc.tsukuba.ac.jp
あらましソーシャルネットワークにおける将来予測の重要度は高まっている。しかし，既存手法においては，予測に多くの潜在特徴量を用いる必要があり，ブラックボックス性が高く，予測結果の解釈が困難である。本研究では，
ソーシャルネットワーク上の人々の繋がりの変化の系列を学習データとして用い，グラフ構造の変化を確率的に予測し，その予測結果をソーシャルネットワークの研究分野で利用される理論の用語である「ホモフィリー」および「推移性」を用いて説明可能な手法を提案する．具体的には，ソーシャルネットワーク内の各人の充足度を表現する報酬関数のパラメーターを変化の系列から学習し，将来の人々の繋がりを強化学習を用いて推論することで実現する．提案手法により，現実世界のソーシャルネットワークにおけるネットワークの変化の予測において，既存手法と同等以上の精度を実現した。
キーワード ソーシャルネットワーク予測、マルチエージェントシステム、強化学習

1 はじめにソーシャルネットワークとは人と人が何らかの関係を元に接続されているグラフデータのことである．研究者同士の共著関
係の Twitter のフォロー・フォロワーの関係や Facebook の友達機能などがその代表例ある．ソーシャルネットワークは多くの場合，各ノードは自身の特性を表現する属性値を持つ．研究者の共著ネットワークの場合は，研究者が発表した論文に含まれる単語などが例として挙げられ，Twitter の場合はツイートに含まれる単語やハッシュタグなどが挙げられる．また，ソーシャ
ルネットワークは多くの場合，エッジ構造やノードの属性値が時間の経過とともに変化する．例えば，時間の経過によって各ノードの興味関心や意見が変化し，それによって属性値が変化したりする．それに伴ってエッジが出現・消滅したりする．本
研究では，このような動的に変化するソーシャルネットワーク
を対象に，これらの今後の変化を予測することを目的とする．
ソーシャルネットワークの予測に対する重要度は高まっており，
集団の興味関心や繋がりが市場規模の予測，マーケティングなどに活用されている [30], [31]．このように，ソーシャルネット
ワークにおける意見や繋がりの予測の応用であるトレンド予測など，ソーシャルネットワーク上での将来予測は重要視されており，今後も SNS の予測に基づく意思決定に活用されていくと期待されている．
動的に変化するソーシャルネットワークを 予測する手 法は 近 年 活 発 に 研 究 が 行 な わ れ て い る ．こ れ ま で の 研 究 では [3], [10], [12], [23] のように，興味関心の伝搬などを考慮した

図 1 提案手法の概要 提案手法では報酬関数と方策関数を定義し、観測済のネットワーク系列から 2 つの関数のパラメーターを学習する。そして、学習済関数を用いて強化学習の環境をネットワー
クのジェネレータとして用いて、エージェントを振る舞わせることで未来のネットワーク系列を生成する。

潜在的な特徴量に基づいたモデルやグラフニューラルネット
ワークを用いて，ソーシャルネットワークにおける将来の人々の繋がりがどのように変化するかを予測する研究などが行なわれてきた．しかし，既存の手法には予測には多くの潜在特徴量を用いる必要がありブラックボックス性が高い．また，なぜそのように予測されるのかの解釈が困難である．推移性など既存のネットワーク研究で検討されてきた理論を十分考慮されてないという問題点がある．
これらの背景の下，本研究は「ソーシャルネットワークの研究分野で提案されている理論に基づいた機械学習モデル」を用いたソーシャルネットワークの将来予測の手法の提案を行なう

回る未観測ネットワークにおけるエッジの予測精度が可能であ(図 1)．これにより，予測結果の根拠を，これらの理論で用いらることを明らかにした．

れている用語を用いて説明できるようになる．具体的には，過去の SNS 上の人々の繋がりを示すグラフを学習データとして用いて，人々の繋がりの性質として知られるホモフィリー [17]や推移性 [26] などを考慮したモデルを設計し，次のステップでSNS 上のユーザの行動原理の推定と，推定された行動原理に基づく将来予測を行う．(1) まず，SNS 内の各ユーザの充足度を表現する報酬関数のパラメータを推定する．どのような場合にどれだけ報酬が得られるかを推定することによって，各ユーザの価値観を表す「行動原理」が明らかになる．(2) 次に，このモデルに基づき，将来の人々の繋がりと投稿内容を強化学習を用いて推論することで実現する．(1) によりエージェントの行
動の履歴から意思決定における価値関数を学習することができる，これにより，SNS 上のユーザの行動原理が評価関数として

2 関連研究ソーシャルネットワークに対する予測手法は様々なアプロー
チで提案されてきた．主にネットワーク構造を表現する潜在ベ
クトルを学習する手法があり，確率モデルに基づくリンク生成
モデル，ノードが属するコミュニティにおけるエッジ生成とコ
ミュニティ感のエッジ生成をモデル化したもの，グラフニュー
ラルネットワークによる手法などが提案されている．本節は，ソーシャルネットワークグラフの予測・生成に関する関連研究，および既存手法との関係について述べる．また，これらの既存手法と本研究の差違について述べる．

2. 1 ネットワーク成長モデル

学習できると期待される．(2) では (1) で明らかになった行動原

ネットワークとは物事の関係性を分析する分野である．ネッ

理に基づき，将来の人々の繋がりと各個人の属性を複数のエー

トワークの成長とは，ノード同士が次々とリンクしグラフがジェントが同時に学習行動を行うマルチエージェント強化学習

拡大していくことをいう．ネットワークの成長モデルとして，を用いて推論することで実現する． 具体的には (1) で明らかにノードに無作為にリンクを張るランダム・ネットワークがある．

なった環境において，エージェントの報酬を最大にするようなネットワークに参加しているノードの数が変わらないと仮定す

方策を学習し，ユーザの価値関数の期待値が最大になるようにると，ランダム・ネットワークは N 個のノードの組み合わせにネットワークを生成するモデルを提案する．これにより，学習確率 p でエッジを張ることで未観測のネットワークを生成する済みモデルで過去の振る舞いを定性的に説明出来るようになり，

モデルである．また，ランダム・ネットワークにエッジ間の特徴

予測も行なうことが出来るようになると考えている．

を考慮し重み付けをした重み付きネットワークなどのモデルも実験では生成データと実データを対象に本手法の有用性を検存在する．しかし，現実世界のネットワークでは重み付きも含証した．生成データを用いた実験では，コミュニティの分裂とめて一般にランダム・ネットワークの性質は満たさないことがいった実際のソーシャルネットワークにおいて発生すると考え示されている．現実のネットワークでは，次数分布がべき則でられるパターンを生成し，これらの変化を本手法に予測できる近似できるスケールフリー性をもったスケールフリー・ネット

かを検証した．実データを用いた実験では研究者の共著者ネッ

ワークによって説明することが出来る．スケールフリー・ネッ

トワーク（NIPS，DBLP）データセットを対象にし，ソーシャ

トワークでは，多くのエッジが張られているノードほどエッジ

ルネットワークの将来予測における本手法の有用性に関して検の生成率がべき乗に比例して増加する．これによってハブと呼証を行なった．実験の結果，提案手法は既存手法と比較して高ばれる大量のエッジが集約されたノードがネットワーク全体に精度に未観測の時刻におけるソーシャルネットワークの予測出

複数出現する．現実世界の SNS でもこの特徴が現れ，一部のイ来ることを示した．

ンフルエンサーと呼ばれる大量のエッジが張られたユーザーを本研究における貢献は以下の 4 つである．本研究ではネット

中心にハブが形成される．このようなネットワークの成長モデ

ワーク科学や心理学で知られている現象をモデル化したモデル

ルをバラバシ・アルバート・モデルがある．現実のネットワーを提案した．また，パラメーターの数が既存手法と比べて少な

ク構造は一般にスケールフリー性があることが知られている．

いことで説明可能性も向上した．さらに，他のネットワーク科
学や心理学で知られている現象をモデルに組み込めるスケーラ

2. 2 ネットワークの形成に関わる性質

ビリティを有するところも提案手法の優れている点である．まネットワーク形成の特徴の 1 つにホモフィリーという性質がた、これらをマルチエージェントシステムにおいて報酬関数のある [17]．ホモフィリーは「類似した人々との間の接触は，類最適化と強化学習による行動方策の学習を行ない，ネットワー

似していない人々間の接触より高確率で発生する」という性質

ク生成手法を提案した点が新規性である．

である．これらは「類は友を呼ぶ」ということわざにもある性（ 1 ） ネットワーク科学や心理学で使われている用語に基づ質をネットワーク分野で定量的に存在が示されたものである．

くモデルベースの予測手法により解釈可能性が向上した．

他の性質として”ある頂点の隣接頂点間にも辺がある割合が多（ 2 ） 他のネットワーク科学や心理学で知られる現象を簡単くなる”という推移性 [26] というものがある．これは”友人の友に組み込める拡張可能な手法である．

人は友人になりやすいという性質”を説明したものである．

（ 3 ） マルチエージェント強化学習を用いてソーシャルネッ

先行研究 [13] ではこれらの性質を考慮したネットワークの将

トワーク上での行動方策の学習手法を提案

来予測の手法を提案されており，既存手法に対して高い精度で（ 4 ） 実データを用いた実験の結果，本手法が既存手法を上

エッジ生成と属性値の予測が行なわれている．また [20] でも心理学の分野で知られている性質を数学モデルで記述しモデルになどがある．

組み込むことでオピニオンダイナミクスの予測を行なっている．

より近年では，グラフニューラルネットワークを用いた表現

このようにネットワーク科学や心理学の性質を数学モデルで記学習手法が数多く提案されている．CNN のようにフィルタの述するアプローチによって多くの成果が生まれている．

畳み込みをグラフ上で行なうことでグラフやノードの潜在ベク提案手法でも，ネットワーク科学で知られているホモフィ

トルを得る手法である GCN [14] や GIN，グラフデータに対す

リーと推移性に性質に基づいたモデルを構築する．これは，既る変分オートエンコーダーの GVAE [15] やグラフに対する敵対知の性質も満たした説明可能性の高いネットワークの予測を行

生成ネットワークを用いた GraphGAN [24] など様々な方法が存なうことを狙いとしたものである．

在する．これらの研究は観測済みのネットワークグラフに対す

2. 3 マルチエージェント強化学習
マルチエージェント強化学習では複数のエージェントが相互るグラフやノードの特徴量を獲得するための手法で，本研究の目的である未観測の時刻におけるネットワークの予測についての検討は行なわれていない．

に影響を及ぼし合いながらエージェント自身，あるいは集団の充足度を最大化させるような行動を学習するフレームワークの1 つである．マルチエージェント強化学習には完全協調タスク，
対戦型タスクなどが挙げられる．

2. 5 ソーシャルネットワークの予測
ネットワーク構造から新規に生成されるノードの特徴量を手法するに GCN [14] やその改良として学習時に隣接ノードからサ[4] ではマルコフゲームと呼ばれる環境でのエージェントのンプリングすることで精度と速度を向上させた GraphSAGE [11]最適な振る舞いを学習する研究が行なわれている．また [28] でなどの手法が提案されている．ノードの潜在変数の変化をネッ

は社会が個人に与える利益であるソーシャルキャピタルをゲー

トワーク構造における伝搬を考慮した上で予測する手法としム・ベースのフレームワークで定義し，マルチエージェント強て LFP [12] が存在する．ノード集合の意見の群衆としての変化学習の枠組みで新たな社会的ネットワーク構造の出現を予測

化を予測する手法として CoNN [8]，ノードの潜在変数の変化する研究が行なわれている．これらの研究では，ある状況におとコミュニティ構造の変化を抽出し，ネットワーク構造の補完

けるエージェントの最適な行動やそれに伴うネットワーク構造を行う研究として ELSM [9] がある．リンク予測に対して構造の出現を予測する研究は行なわれているが，本研究が目指す観

情報と時間の情報を取り入れたネットワーク構造の予測手法と測済みネットワークから未観測の時系列ネットワークの生成をして STEP [3]， VGAE [15]， VGRNN [10] が存在する．ネット

行なうタスクは行なわれていない．

ワーク構造から，ノードの特徴の変化を予測する手法として

2. 4 ソーシャルネットワークに対する表現学習
ネットワーク表現学習とは，時系列データや自然言語などの要素の予測問題を解くことで特徴量を分散表現として学習する手法のことである．ネットワークデータに対する表現学習手法
はネットワーク構造を表現する潜在的ベクトルを学習するための手法である．特に確率モデルに基づく潜在ベクトルモデル，
ネットワークエンベディング，グラフニューラルネットワーク
といった枠組みの様々な手法が提案されている．
確率モデルに基づくネットワーク表現学習の手法として，潜在ベクトルに基づくリンク生成モデル [18]，ノードが属するコ
ミュニティにおけるエッジ生成，コミュニティ間におけるエッジ生成をモデル化した [1] が提案されている．
ネットワークエンベディングとはネットワークやノードが持つ属性値をベクトルで表現し，最適な埋め込み表現を学習する手法である．代表的な手法として，ネットワーク構造を保存する手法の DeepWalk [21]，その改良である LINE [22] やNode2Vec [7] などがある．また，コミュニティ構造とノードを

ONE-M [19]，TensorCast [2] などがある．
また，データマイニングによる意見集合の分類と心理学で知られている性質と組み合わせることで，ノードの属性値を予測する研究手法 [20] が提案されている．これはフリードキン‐ジョ
ンソンモデル [5] と呼ばれる個人内の他人からの影響度や確証バイアスなどの性質を数学モデルとして表現することでデータのみから学習することで予測精度を向上させた．この研究では心理学などの性質を数学モデルに記述し，それに基づくモデルを構築する点での有用性を示しており提案手法と同じアプロー
チである．しかし，未来の複数の時系列におけるエッジの生成や特徴量の予測については十分に検討が行なわれていない．
本研究では，ネットワーク科学や心理学で知られている性質をモデルにし，ソーシャルネットワークにおいてノードがそれに基づく充足度を高める最善の方策を取っていると仮定している．既存手法と比べるとグラフ構造や属性値の変化を考慮している点，また他の性質を容易に組み込めるスケーラビリティの面において既存研究とは大きく異なる点である．既存手法に対する提案手法の特徴については表 1 にまとめている．

同時に埋め込み学習する手法として M-NMF [25]，動的に変化するネットワークに対する埋め込み学習の手法として [29] など

3 問題定義が存在する．
近年ではノードの変化と属性値の変化の両方を時系列的に埋本節では本研究で対象とする問題の定義について説明する．

め込む手法が提案されている．Twitter におけるユーザーの関心

本研究では，入力となるソーシャルネットワークを属性値つきの変換を追跡する手法として [16]，テキスト情報を持つ動的なのグラフ構造として表現し，各ノード n は各人を表し，属性値

ネットワークにおけるノードと単語の埋め込み手法である [29]xn は単語など各人の興味関心を表すベクトル，エッジは人と人メーターを用いてノード間のエッジの生成および消滅確率を計
Proposed

DualCast [13]Dyngraph2vec

TensorCast [2]PropertyMethod

LFP [12][6]

ネットワークの生成では，学習済の報酬関数と方策関数のパラ"

Scalable Model

算する．この計算結果をもとに未観測の時刻のエッジを生成・削除することでネットワークの将来予測が行なわれる．
以下の節ではこれらの流れについて以下の順に詳説する．

""（ 1 ） 強化学習の環境

Network-forecast

"

"

"

"

（ 2 ） 観測済ネットワークにおける報酬関数の最適化手法

Propagation

"

"

"

"

（ 3 ） 未観測時間における方策関数の最適化""（ 4 ） 未観測時間における時系列ネットワークの生成手法"

Multi-task

Directed edge

表 1 Proposed 提案手法と既存手法との比較， 提案手法はエッジ生成の予測とモデルの拡張性に特に優れている．
表 2 主な記号と定義

4. 2 強化学習の環境
本節では提案手法における強化学習の環境について説明する．
本研究では，時刻 t における状態集合をソーシャルネットワー

G(t) = (V(t) , E(t) ), X(t)

時刻 t におけるグラフ(t)
ク G(t) ，行動空間 At をエッジ集合の差分 ∆E(t) =< E(t)+ , E− > とV(t) = {i}

時刻 t におけるノード集合

E(t) = {e(t)i→ j }

時刻 t におけるエッジ集合

する．ここで，E(t)+ は時刻 t において新たに追加されるエッジ

X(t) = {x}

時刻 t における属性値集合

ni = {ni |ni ∈ V(t) }ノード集合における i 番目のノード

Rt = {Rt |Rt ∈ R}

時刻 t における報酬

Vineighbor ∈ V(t)ノード i の隣接ノードの集合(t)
策関数 π(e(t)
i, j | G , θi ) をもつと仮定する．ここで，報酬関数はe(t)i→ j = (i, j)

i から j への無向エッジ

各ノードのソーシャルネットワークの好ましさを表現し，方策の集合，E(t)− は時刻 t において削除されるエッジの集合を表す．
本研究では，各ノードをエージェントとし，パラメータ集合

ψi をもつ報酬関数 r(G(t) | ψi ) と，パラメータ集合 θi をもつ方関数は現在のソーシャルネットワークの状態における各ノードとの繋がりを表すものとする．すなわち，入力として離散的な時刻 t = 1 ∼ T におけるソーシャルネットワーク G(t) = (V(t) ，E(t)，X(t) ) と，各ノード n ∈ V が与えられるとする．ここで V(t) はノード集合，E(t) はノード間のエッジ集合，X(t) は各ノードがもつ属性値ベクトルの集合とする．時刻 t に u と v の間にエッジが存在することを e(t)∈ E(t) と表現する．
u，vのエッジの変化の傾向を表現する．本研究では強化学習に基づ
き，t = 1 ∼ T のソーシャルネットワークの系列 < G(1) , G(2) , ．
．
．

, G(T ) > から，報酬関数のパラメータ Ψ = {ψi }ni ∈V と，行動方策のパラメータ Θ = {θi }ni ∈V を学習する．

4. 3 報酬関数のパラメータの最適化
本節では入力となったソーシャルネットワークの時系列変化

本研究では新規ノードの出現や消滅は考慮せず，既存のノーから，各ノードの報酬関数のパラメーターを推定する方法につドの間に存在するエッジの存在確率の算出と，それに基づいた

いて述べる．ここで，現在得られたソーシャルネットワークの

将来のネットワークを予測を行う．本研究では，新規ノード・

時系列変化は，強化学習の環境において最適であると仮定し，単語の出現および消滅は考慮せず，時刻 t′ > T におけるソー現在得られたソーシャルネットワークにおける報酬関数の値がシャルネットワーク中の既存のノード i，j 間に存在するエッジ

最大化されるようにパラメータを推定する．

′′の存在確率 P(e(ti，)j ∈ E(t ) ) を求めることが目的である．

本研究では，各ノードの時刻 t のソーシャルネットワーク G(t)における報酬関数を以下の式で定義する．

4 提案手法
本節では, 未来のソーシャルネットを予測するためのモデルに関して記述する．本研究では，マルチエージェント強化学習を用いたネットワークの生成モデルを提案する．本手法は (1) 過去の時系列ネットワークデータを用いた各ノードの報酬関数・方策関数の最適化，(2) 強化学習に基づいた未観測の時系列ネットワークデータの生成，の２つのフェーズから構成される．以
下の節では，強化学習の環境，各ノードの報酬関数・方策関数の学習, 学習結果に基づくネットワーク生成について述べる．

4. 1 提案手法の概要
本節では提案手法の概要を述べる．提案手法では，入力されたソーシャルネットワークの時系列から，各ノードがもつ報酬関数のパラメーターを学習し，推定された報酬関数の値が最大

ri (G(t) |ψi ) =∑αi sim(ni , n j ) − βi cost(ni , n j )(1)

n j ∈N(ni )ここで，ψi = {αi , βi } はノード i のパラメータ集合，N(ni ) はノー
ド ni に隣接するノード集合を表す． sim(ni , n j ) はノード間の類似度を示し，本研究ではノードの属性値集合のコサイン類似度
によって算出する．

sim(ni , n j ) =dot(xi , x j )|xi ||x j |(2)cost はノード i, j がソーシャルネットワーク中で接続している
ことのコストを示し，以下のように定義する.





1 ni , n j にエッジが存在する
cost(ni , n j ) = 0 ni , n j にエッジが存在しない(3)

化されるように方策勾配法により方策関数の最適化を行なう．
時刻 t のソーシャルネットワーク G(t) 全体における報酬関数のうな時系列データ τ を獲得したとする．

総和を以下のように定義する．

r(G(t) | Ψ) =∑ri (G(t) |ψi )(4)

τ =< G(1) , ∆E(1) , R(G(1) | Ψ), G(2) , ∆E(2) , R(G(2) | Ψ),ni ∈V..., G(T ) , ∆E(T ) , R(G(T ) | Ψ) >本研究では，各ノードの報酬関数を入力となったソーシャル
ネットワークの系列について総和をとり，その報酬が最大になるようなパラメーターを求める．
∗

Ψ ← argmaxΨ

T∑

R(G | Ψ)(t)(8)

このとき，ネットワーク中のすべてのノードが未観測の時刻において獲得した累積を割引率 γ を用いて以下のように定義する．

R(τ) = R(G(1) | Ψ)+γR(G(2) | Ψ)+γ2 R(G(3) | Ψ)+···+γT R(G(T ) | Ψ)
(5)

t=1

(9)
本手法では，累積報酬の期待値を最大にする方策関数のパラ提案手法では SGD を用いて報酬を最大化するパラメーターを

メータを学習する．このときの目的関数 J(θ) は以下の式で表現

推定する．

する．

J(Θ) = Eτ∼π(∆E|Θ) [R(τ)]

4. 4 強化学習に基づいた行動方策の最適化
本研究では各ノードの属性値に基づく類似度関数を定義し,ここで目的関数におけるパラメーター θ に関する勾配を求める．

これを用いて方策関数を定義する．類似度関数 sim(ni , n j ) を用[]∇J(Θ) = E R(τ)∇ log(π(∆E | Θ)(t)い，i 番目のノードについての方策関数 π(e(t)
i, j |G , θi ) は以下の式

≈
(6)

)}
{
(
1 − sim(ni , n j )(t)
π− (e(t)
|G
,
θ
)
=
σ
ϵ
exp
i
i
i, j
τi

(7)

+

1 ∑
R(τ(i) )∇ log(π(∆E | Θ)N i=1Nで定義する．

{()}
sim(ni , n j )(t)
π+ (e(t)
|G
,
θ
)
=
σ
ϵ
exp
i
i
i, j
τi

(10)

(11)

τ(i) は，方策関数より生成された i 番目の時系列データである．
これを用いてパラメーターを更新する．ここで α は学習率である．

−

ここで，π (·) は新規に生成するエッジに対する生成確率，π (·)θ ← θ + α∇θ J(θ)

は既存エッジを消滅させる確率を表現する．σ はシグモイド関
数，θi = {ϵi , τi } はノード ni のパラメータ集合である．
次に観測されたソーシャルネットワークの系列から強化学習に基づいて行動方策を学習する．具体的には 4. 3 において最適化(12)以上の式で方策関数のパラメーターの学習を行なう．この方策関数と (1) で学習した報酬関数を用いて未観測のネットワー
クグラフを生成する．

された報酬関数の下で，自身の報酬を最大にするような方策関数のパラメータ学習を勾配降下法の 1 つである REINFORCE [27]4. 5 将 来 予 測によって学習する．この方法では，未観測のソーシャルネット

学習データから求めた報酬関数と方策関数のパラメーターをワークを生成し，そのときの報酬関数の期待値が最大となる方

用いて将来のソーシャルネットワークを予測する．本手法では策関数のパラメータを学習する．これにより，観測されたソーエッジの生成予測と生成結果による各ノードの報酬と特徴量のシャルネットワークでの最適化された報酬関数に基づき，未観

更新を交互に行なうことで複数ステップ先のソーシャルネット

測の時系列における最適な行動を学習することを期待する．

ワークにおけるエッジとノードの状態を予測する．具体的には

ここで未観測の時系列のソーシャルネットワークの生成モデ

学習済報酬関数 [式 1] と方策関数 [式 6, 7] を用いてエッジの生ルについて検討する．報酬関数の最適化で用いた観測済のソー成確率を計算し，それらによってネットワークグラフの状態を

シャルネットワークの系列のうち，最も新しいソーシャルネッ

更新することで未観測時系列のネットワークを生成する．

トワークを G(t) とする．本研究では，ノード ni について，ランダム選択と推移性の考えに基づいてエッジの生成・削除を行な

5 合成データを用いたネットワークの生成実験

う対象を探索する．ノード ni は自身の方策関数を用いて，各ここでは合成データに対して本手法を適用することによりノードに対するエッジ生成・削除の確率に基づき G(t+1) を生成

ネットワークの生成が期待通り行なわれるか実験を行なう．本し，報酬関数によって報酬を計算する．これまでに観測された
ソーシャルネットワークにおいて，各時刻で各ノードが最適な行動を選択していると仮定した場合，未来の報酬を最大化させる方策を獲得することで未観測の時系列のネットワークを予測することが可能となる．
本研究では方策関数のパラメータ Θ を方策勾配法を用いて最適化する．各ノードの方策関数に基づいて未観測の時刻のソー
シャルネットワークを生成した際，「ソーシャルネットワークの状態, ソーシャルネットワークの差分, 報酬」からなる以下のよ

実験ではランダムの生成されたエッジを持つネットワークが徐々に分裂していき，最終的には 2 つのコミュニティに分裂す
る合成データを与える．ここではノード数は 20，属性は「赤」と「青」の 2 つとして実験を行なった．各ノードは「赤」「青」のいずれかの属性値を持ち，この属性値は変化しないものとをする．
本実験で行なうデータセットはランダムに繋がりを持った
ネットワークを生成する．報酬関数の学習にはランダムに生成した 3 時刻分のネットワークを用意する．ここでは最終的に 2

つのコミュニティに分裂することを想定して，同じ属性に対す

ング，データベース，自然言語処理，機械学習，人工知能，情るエッジと異なる属性に対するエッジの比率を各時刻において

報検索，コンピュータビジョンから構成されるの 47 国際会議

1:1，2:1，3:1 となるようにする．エッジの総数は全ノードにその論文データを取得し，2008 年から 2012 年までを学習データ，

れぞれエッジが張られた時の最大値 400 にたいして 15%の比率

2013 年から 2017 年までをテストデータとして用いる．こちらとなるように調整を行なう．この生成データにより各ノードののノード数は 500，属性値数は 3854 である．

報酬関数のパラメータの最適化を行なう．次に方策関数のパラメータの最適化を行なう．エッジの生成は各ノードからノードへのエッジ生成は一様乱数によって 15%の確率で張ったものを入力ネットワークとし提案手法通りの最適化の学習を行なう．
図 2 は合成データセットに対して提案手法を適用した際の強化学習の学習過程とその結果を示したものである．図から各ノードは学習をする毎にランダムなネットワークの状態から同

6. 2 実 験 結 果
本研究では予測精度の検証に AUC（Area Under Curve）を用いた．AUC が高いほど正確に将来のネットワークを予測していることを示している．実験結果では未観測の時系列 t=1 において AUC が NIPS で 0.955，DBLP で 0.809 となった．これは既存手法を超える成果であり，従来手法より高い精度を持ってじ属性値を持つノードとの接続し，異なる属性値を持つノード

エッジ生成を行えることを示すものである．図 3，4 はそれぞとの関係を切るような方策を獲得していることが分かる．そしれ各予測時刻における AUC の値の変化を示す．図を見るとほて，学習後のネットワーク生成において 2 つのコミュニティが分裂したネットワークを生成することが出来た．
これにより提案手法はコミュニティの分裂が起こるネット
ワークについて，その過程における報酬関数の最適化と未観測時間における行動方策の最適化により意図した 2 つのコミュニ

とんどの時刻においてベースライン手法を上回る精度を出していることが分かる．また，ベースライン手法では時間が経過するほど精度が低下するが提案手法では時間経過における精度の落ち込みが少ないことが分かる．

ティが完全に分裂することを予測出来ている事が分かる．

7 ま と め6 実データを用いた実験

ネットワーク上のノードの振る舞いについてモデルベースで予本研究ではネットワーク科学や心理学に基づくソーシャル

本節では，実データを用いて本提案手法がどれだけ正確に未観測のソーシャルネットワークのエッジを予測出来るかを検証する．本実験では，報酬関数と方策関数のパラメーターを更新しない場合をベースライン手法として用いて，パラメーターを更新した場合の予測モデルと比較することで提案手法の有効性を検証する．また，比較手法として潜在ベクトルの特徴量から
エッジと特徴量の予測を行なった DualCast，エッジを生成する
グラフニューラルネットワークに基づく手法として提案された

VGAE，VGRNN を採用しエッジ生成の比較を行なう．

測する手法を提案した．提案モデルはノード間のエッジの予測について，ノード全体の環境と自身の報酬を最大化するような振る舞いを強化学習の枠組みで学習したモデルに基づき行なわれる．また，報酬関数については観測済ネットワークからパラ
メーター最適化を行なうことで過去の現象を明らかにしつつ，それに基づく将来予測が行えることを示した．そして，実データに基づく予測精度の比較で従来手法に対して高い精度でエッジ生成確率を予測することが出来たことを示した．さらに先行手法としてパラメーター数を大きく削減し，同等以上の精度を得ることができた．

6. 1 データセット
データセットとして NIPS，DBLP を用いる．以下にそれぞれのデータセットの収集，作成方法を記述する．

これらの結果により過去のノードの最適な振る舞いを与える
報酬関数の重み付けと，それに基づく方策関数の最適化による未観測時間の振る舞いを予測することが達成できた．これは過NIPS は研究者の共著者ネットワークである．ノードは著者，

去の振る舞いから振る舞いを決定づけた要因を明らかにし，過エッジは共著者の関係で時間区分は年単位である．ある年に 2

去の系列における最適な戦略が未来の時系列でも高い精度で有人の著者 x，y が共著論文を発表したときにその 2 人の間に双方効であることを示した．今後は，振る舞いを決定づける報酬関向の有向エッジが張られる．各ノードは属性値としてある年に数に他のネットワーク科学や心理学で明らかになっている性質

発表した論文のタイトルに含まれる単語を属性値として持ってをモデル化して組み込むことでより高い精度でソーシャルネッ

いる．ノード数は 32 で属性値数は 2411 である．NIPS，DBLP

トワーク上のノードの振る舞いを説明することを目標とする．

ではネットワークを時間区分で 10 年分収集している．このう

さらに，現状のモデルでも未来の予測に有効であることが示さ

ち 5 年分を観測済ネットワークとし報酬関数の最適化に用いる．

れたので，これらの改良を施すことによってさらに高い精度でそして残りの 5 年分のネットワークの生成を行ない，各年毎にソーシャルネットワークの将来予測が可能になると考える．

精度の比較を行なう．

今後の展望としてはノードの持つ属性値の予測を行なってい

DBLP は研究者の共著者ネットワークである．ノードは著者，

こうと計画している．[13] では属性値とエッジの生成の両タス

エッジは共著関係，時間区分は年単位である．エッジ情報や特クを同時に行なっているが，本研究では属性値の予測を行なっ

徴量などのネットワークデータは NIPS と同様の方法で生成をていない．しかし，属性値の変化を予測することなく提案手法

行なっている．2008 年から 2017 年に発表されたデータマイニのモデルにより先行手法に匹敵する精度を出したことは本手法

図 2 合成データによるシミュレーションの結果

トに対する実験も行なっていく予定である．さらに Twitter やFacebook 等のソーシャルネットワーキングサービスにおいて本手法を適用することで未来のコミュニティの変化の予測を行なうことも目指していく．

謝辞

本 研 究 の 一 部 は JSPS 科 研 費 (JP22H00508, JP20K23337,

JP22K17944) の支援を受けたものである．ここに謝意を示す．

文

図 3 DBLP を用いた場合の時間毎の AUC の推移

図 4 NIPS を用いた場合の時間毎の AUC の推移の優れている点である．将来的には属性値の変化も取り入れた
エッジの予測モデルを提案しさらなる精度の向上を目指す．
また，報酬関数の説明可能な因子を増やし，それに基づく予測を行なうことでソーシャルネットワーク上のノードの行動原
理とそれに基づくネットワーク予測をさらに高い精度で行なっていくことを目指す．また，今回の時系列ネットワークは年単位の予測であったが，月や日にち単位といったより短い時間幅における予測モデルについての検討も行うことを計画している．
さらに実装面の課題で実験が行えなかった Twitter データセッ

献[1] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing. Mixedmembership stochastic blockmodels. Journal of machine learning
research, 9(Sep):1981–2014, 2008.
[2] M. Araújo, P. Ribeiro, and C. Faloutsos. Tensorcast: forecastingtime-evolving networks with contextual information. In Proceedingsof the 27th International Joint Conference on Artiﬁcial Intelligence,
pp. 5199–5203, 2018.
[3] H. Chen and J. Li. Exploiting structural and temporal evolution in
dynamic link prediction. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp.
427–436, 2018.
[4] Y. Chen, J. Liu, H. Zhao, and H. Su. Social structure emergence: A multi-agent reinforcement learning framework for relationship building. In Proceedings of the 19th International Conference
on Autonomous Agents and MultiAgent Systems, AAMAS ’20, p.
1807–1809, Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems.
[5] N. E.Friedkin and E. C.Johnsen. Social inﬂuence and opinions. The
Journal of Mathematical Sociology, 15(3-4):193–206, 1990.
[6] P. Goyal, S. R. Chhetri, and A. Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning.
Knowledge-Based Systems, 187:104816, 2020.
[7] A. Grover and J. Leskovec. node2vec: Scalable feature learning for
networks. In Proceedings of the 22nd ACM SIGKDD international
conference on Knowledge discovery and data mining, pp. 855–864,
2016.
[8] Y. Gu, Y. Sun, and J. Gao. The co-evolution model for social network
evolving and opinion migration. In Proceedings of the 23rd ACM
SIGKDD international conference on knowledge discovery and data
mining, pp. 175–184, 2017.
[9] S. Gupta, G. Sharma, and A. Dukkipati. A generative model for
dynamic networks with applications. In Proceedings of the AAAI
Conference on Artiﬁcial Intelligence, Vol. 33, pp. 7842–7849, 2019.
[10] E. Hajiramezanali, A. Hasanzadeh, N. Duﬃeld, K. R. Narayanan,
M. Zhou, and X. Qian. Variational graph recurrent neural networks.
arXiv preprint arXiv:1908.09710, 2019.
[11] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation
learning on large graphs. In Advances in neural information processing systems, pp. 1024–1034, 2017.
[12] C. Heaukulani and Z. Ghahramani. Dynamic probabilistic models
for latent feature propagation in social networks. In International

Conference on Machine Learning, pp. 275–283, 2013.
[13] H. Ito and C. Faloutsos. Dualcast: Friendship-preference coevolution forecasting for attributed networks. In A. Banerjee,
Z. Zhou, E. E. Papalexakis, and M. Riondato eds., Proceedings of the2022 SIAM International Conference on Data Mining, SDM 2022,
Alexandria, VA, USA, April 28-30, 2022, pp. 46–54. SIAM, 2022.
[14] T. N. Kipf and M. Welling. Semi-supervised classiﬁcation with graphconvolutional networks. arXiv preprint arXiv:1609.02907, 2016.
[15] T. N. Kipf and M. Welling. Variational graph auto-encoders. arXiv
preprint arXiv:1611.07308, 2016.
[16] S. Liang, X. Zhang, Z. Ren, and E. Kanoulas. Dynamic embeddings
for user proﬁling in twitter. In Proceedings of the 24th ACM SIGKDDInternational Conference on Knowledge Discovery & Data Mining,pp. 1764–1773, 2018.
[17] M. Mcpherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415–,
01 2001.
[18] K. Miller, M. Jordan, and T. Griﬃths. Nonparametric latent featuremodels for link prediction. Advances in neural information processing systems, 22:1276–1284, 2009.
[19] A. Nigam, K. Shin, A. Bahulkar, B. Hooi, D. Hachen, B. K. Szymanski, C. Faloutsos, and N. V. Chawla. One-m: Modeling theco-evolution of opinions and network connections. In Joint European Conference on Machine Learning and Knowledge Discovery in
Databases, pp. 122–140. Springer, 2018.
[20] M. Okawa and T. Iwata.
Predicting opinion dynamics via
sociologically-informed neural networks. In Proceedings of the 28th
ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, aug 2022.
[21] B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learningof social representations. In Proceedings of the 20th ACM SIGKDD
international conference on Knowledge discovery and data mining,pp. 701–710, 2014.
[22] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line:
Large-scale information network embedding. In Proceedings of the24th international conference on world wide web, pp. 1067–1077,
2015.
[23] R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha. Dyrep: Learning
representations over dynamic graphs. In International Conference on
Learning Representations, 2019.
[24] H. Wang, J. Wang, J. Wang, M. Zhao, W. Zhang, F. Zhang, X. Xie,
and M. Guo. Graphgan: Graph representation learning with generative adversarial nets. arXiv preprint arXiv:1711.08267, 2017.
[25] X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu, and S. Yang. Community preserving network embedding. In AAAI, Vol. 17, pp. 3298239–
3298270, 2017.
[26] S. Wasserman and K. Faust. Social network analysis: Methods andapplications, Vol. 8. Cambridge university press, 1994.
[27] R. J. Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn.,
8(3–4):229–256, may 1992.
[28] L. Yu, J. Song, and S. Ermon. Multi-agent adversarial inverse reinforcement learning. CoRR, abs/1907.13220, 2019.
[29] L.-k. Zhou, Y. Yang, X. Ren, F. Wu, and Y. Zhuang. Dynamic network embedding by modeling triadic closure process. In AAAI, pp.
571–578, 2018.
[30] 壮太郎, 章宏, 永至. ソーシャルメディアの影響を考慮したマス
メディア広告の総合効果測定. 大阪大学経済学, 68(3-4):1–20, 03
2019.
[31] 石野淳一, 中田洋平, 日吉久礎. Sns 上の画像群からのユーザー嗜好の抽出と観光広告への応用. 第 76 回全国大会講演論文集, 第2014 巻, pp. 587–588, mar 2014.