DEIM Forum 2021 I25-3

動的なソーシャルネットワークにおける興味関心の伝搬を考慮した将来予測モデル
伊藤寛祥†

Christos Faloutsos††† 筑波大学†† Carnegie Mellon University
E-mail: †ito@slis.tsukuba.ac.jp, ††christos@cs.cmu.edu
あらまし

本研究では時間の経過とともに変化するソーシャルネットワークを対象に，未観測の時刻におけるエッジと，ノードの属性値の双方を予測する手法を提案する．本手法では，ノードと属性値の潜在ベクトルの相関に基づく生成モデルを構成し，未観測の時刻における潜在ベクトルを予測することで，未来のソーシャルネットワークの状態を予測する．本研究では特に（１）ネットワーク構造の変化と興味関心の変化の相互作用，および（２）ネットワー
クを媒介した潜在的な特徴の伝搬に着目したモデル化を行う．ノードと属性値の潜在的な特徴はネットワークを通じて隣接するノードと属性値に伝搬すると仮定し，その過程を取り入れた潜在ベクトルの予測モデルを構成する．ここで，各ノードと属性値はネットワークにおける影響力と受容性のパラメータをもつと仮定し，これらに基づいて時間経過後の潜在ベクトルが予測される．実世界のソーシャルネットワークを用いた実験により，提案手法は既存の手法と比較して，より高精度に未観測の時刻におけるエッジおよびノードの属性値を予測できることを示した．
キーワード ソーシャルネットワーク予測

1 はじめにChangeForecast?

ソーシャルネットワークとは，人と人とが何らかの関係のもとで接続されているグラフデータのことを指し，研究者同士の?

共著関係や，Twitter・Facebook などの SNS におけるフォロー
関係などがその代表例である．ソーシャルネットワークは多くの場合，各ノードは自身の特性を表現する属性値をもつ．研究

Initial Network

者の共著ネットワークの場合は，研究者が発表した論文に含まれる単語などが例として挙げられ，Twitter の場合はツイートに含まれる単語やハッシュタグなどが挙げられる．ソーシャル
ネットワークは多くの場合，エッジ構造やノードの属性値が時間の経過とともに変化する．例えば時間の経過によって各ノー

図 1: 研究目的．本研究の目的は，各ノードが属性を持つ動的なソーシャルネットワークにおける (1) グラフ構造の変化 (2)各ノードの属性の変化の双方を予測することである．

ドの興味関心が変化し，それによって属性値が変化したり，それに伴ってエッジが出現・消滅したりする．本研究では，この本研究ではソーシャルネットワークの変化の予測を目的とし，ような動的に変化するソーシャルネットワークを対象に，これ（１）グラフ構造の変化と興味関心の変化の相互作用，（２）友らの今後の変化を予測することを目的とする．時間の経過によ

人関係を通じた興味関心の伝搬の二つに着目した予測モデルをるソーシャルネットワークの変化を分析・予測することで，市提案する．ここで，本研究ではソーシャルネットワークの変化

場規模の予測やソーシャルネットワークにおける人間関係の創の予測を，未観測の時刻のエッジとノードの属性値の予測とし発のメカニズムの解明への応用が期待できる．

て定義する．本研究では潜在ベクトルに基づくネットワークの動的に変化するネットワークの変化を予測する手法は近年

生成モデルを構成し，未観測の時刻の潜在ベクトルの変化の予活発に研究されており，ノードの潜在的な特徴に基づきネット

測を通じて，未来のネットワークのエッジ構造とノードの属性

ワーク構造を予測する手法 [1], [11], [22] や，グラフニューラル

値を予測する．

ネットワークを時系列グラフに拡張した手法 [4], [9], [26] などがエッジおよび属性値の生成に関しては，ノードはネットワー

近年提案されている．しかしながら，ネットワーク構造とノーク構造と興味関心のそれぞれに関する潜在的な特徴をもつと仮ドの属性値のそれぞれの予測のみについて研究がほとんどであ定し，これらを組み合わせることでエッジを生成するためのモり，ネットワーク構造と属性値の変化の相互作用を利用した予デルを構築する．より具体的には，ノードがもつネットワーク

測に関しては未だ十分な検討が行われていない．

構造の潜在的特徴と，興味関心の潜在的特徴のそれぞれの相関とバイアスに基づいて生成されると仮定し，各ノードの属性値

埋め込みを学習するための方法であり，代表的な手法として，は興味関心の特性と，ある用語の特性の相関とバイアスに基づ

ネットワーク構造を保存する手法の DeepWalk [24]，LINE [25]，いて生成されると仮定する．

Node2vec [6]，コミュニティ構造とノードを同時にエンべディ

潜在ベクトルの予測に関しては，ネットワークを通じてノーングする手法として， M-NMF [28],ComE [3]，ネットワーク

ドの潜在ベクトルが伝搬すると仮定し，自らの潜在ベクトルの構造に加えてノードの属性に着目した手法として，ASNE [18]変化の傾向と，ネットワークを通じた潜在ベクトルを重み付け

LANE [13]，動的に変化するネットワークに対するネットワー

して足し合わせた値の変化の傾向に基づいた予測を行う．よりクエンべディング手法として [29] などが存在する．より近年で具体的には，各ノードの潜在的特徴は，ソーシャルネットワー

はノードの変化と属性値の変化の双方を時系列的に埋め込む手

クにおける友人の影響力と，個人の受容性にもとづいて変化さ法が提案されており，Twitter におけるユーザの関心の変化をせると仮定し，これらをモデルに組み込んだ予測モデルを提案

追跡する手法 [19]，テキスト情報を持つ動的なネットワークにする．さらに，属性値もノードからの影響を受けて変化するとおけるノードと単語のエンべディング手法 [14]，動的に変化す仮定し，属性値自身の時間経過による変化と，関連するノード

る Attributed network におけるノードのエンべディング [18]からの影響による特徴の変化を予測モデルに組み込む．これになどが提案されてきた．

より，ソーシャルネットワークの及び各ノードの興味関心の変より近年ではグラフニューラルネットワーク [15] を用いた表化を同時に予測し，それらを相互に関連づけることによってネッ

現学習手法が多く提案されており，グラフデータに対する変分

トワークの変化を予測する．本予測モデルはソーシャルネット

オートエンコーダーの GVAE [16] や敵対的生成ネットワーク

ワークが生成されるもっともらしさを最大化するように学習さを用いた GraphGAN [27] などが存在する．

れ，各個人の影響力と受容性およびモデル中の各パラメータはそれらの事前分布を考慮した MAP 推定により求める．
実験では生成データと実データを対象に本手法の有用性を検証した．生成データを用いた実験では，コミュニティの統合・分裂といった実際のソーシャルネットワークにおいて発生すると考えられるパターンを生成し，これらの変化を本手法により予測できるかを検証した．実データを用いた実験では NIPS,

DBLP （研究者の共著者ネットワーク）と Twitter （ユーザ間これらの研究は観測済みのネットワークデータに対する手法
で，本研究の目的である未観測の時刻におけるネットワークの状態の予測に関しては検討を行っていない．

2. 2 ソーシャルネットワークの予測
ネットワーク構造から新規に生成されるノードの特徴量を予測する手法 GraphSAGE [10] ノードの潜在変数の変化をネッ
トワーク構造における伝搬を考慮した上で予測する手法としてのリツイートネットワーク）データセットを対象にし，ソーシャ

LFP [11] が存在する．ノード集合の意見の群衆としての変化を

ルネットワークの将来予測における本手法の有用性に関して検予測する手法として CoNN [7]，ノードの潜在変数の変化とコ討を行った．実験の結果，提案手法は既存手法と比較してより高精度に未観測の時刻におけるネットワークの構造及びノードの属性値を予測できることを示した．

ミュニティ構造の変化を抽出し，ネットワーク構造の補完を行う研究として ELSM [8] がある．リンク予測に対して構造情報と時間の情報を取り入れたネットワーク構造の予測手法 としてSTEP [4]，DyRep [26]，VGRNN [9] が存在する．これらの研

2 関連研究

究ではネットワーク構造の変化の予測のみに着目しており，そのノードの属性値の予測は行っていないため，本研究とは目的

動的に変化するネットワークデータに対する予測手法は様々が異なる．

なアプローチで提案されてきた．本節ではそれら関連研究を示

ネットワーク構造から，ノードの特徴の変化を予測する手法

すとともに，本研究との差異および本研究の位置づけに関して

ONE-M [23] TensorCast [2] ユーザとアイテムの関係の履歴か述べる．

らそれぞれの特徴量の変化を予測し，ユーザとアイテムと今後の2. 1 ネットワークデータに対する表現学習
ネットワークデータに対する表現学習手法とは，ネットワー
ク構造をよく表現する潜在的ベクトルを学習するための手法であり，特に確率モデルに基づく潜在ベクトルモデル，ネット
ワークエンべディング，グラフニューラルネットワークといった文脈で近年様々な手法が提案されている．
確率モデルに基づくネットワークの表現学習手法として，潜在ベクトルに基づくリンク生成モデル [22]，ノードが属するコ
ミュニティにおけるエッジ生成とコミュニティ間のエッジ生成をモデル化した [1] などが提案されている．

リンク関係をする手法として DeepCoevolve [5] や JODIE [17]が存在する．これらの手法は前述の手法とは異なり，ユーザとアイテムとの関係を予測する手法であり，本件研究とは目的が異なる．
本研究ではグラフ構造と属性値の変化の双方を対象にし，これらの相互作用と相関関係に着目したモデル化を行う点でこれ
らの既存研究とは異なる．

3 問題定義本節では本研究で対象とする問題の厳密な定義について記述

ネットワークエンべディングとは，ネットワーク構造やノーする．本研究では入力として離散的な時刻 t = 1 ∼ T における

ドがもつ属性値をできるだけよく保存するようにノードの有向ソーシャルグラフ G (t) = (V (t) , E (t) ) と，各ノード u ∈ V

𝑖

$

𝑒!→#

𝑗

($)

$

𝑦!→#

𝑖

Item

表 1: 主な記号と定義

𝑗

($)

𝒖*→

𝒖→#

($)

𝒗*

($)

($)

𝒗→#

𝒗*→

𝑹ℰ&

𝒙#

𝑹𝓎

𝑹ℰ'

$

𝑃 𝑦!→# ∈ 𝓎 ($)$
𝑒!→# ∈ ℰ ($)

図 2: エッジ及び属性値の生成モデル．各ノードはネットワーク
(t)

(t)

構造を表現する潜在ベクトル u→i ，ui→ と興味関心を表現する
(t)

(t)

時刻 t におけるグラフ

A(t) = (V (t) , X (t) , Y (t) )時刻 t における属性グラフ

V (t) = {i}

時刻 t におけるノード集合(t)
E (t) = {ei→j }(t)ei→j = (i, j)
X (t) = {x}

時刻 t におけるエッジ集合i から j への有向エッジ
時刻 t における属性値集合

(t)

𝑏ℰ

⊕

𝑏ℰ

⊕
𝑃

z

G (t) = (V (t) , E (t) )(t)潜在ベクトル v→i ，vi→ をもち，各属性値も潜在ベクトル xi

Y (t) = {yi→x }時刻 t における属性エッジ集合(t)
yi→x = (i, x)(t)
U = {U(t) } (U(t) = {ui })
(t)
(t)
(t)
V = {V } (V = {vi })(t)
X = {X(t) } (X(t) = {xi })i から x への属性エッジ

Θ = {ΘE , ΘY , Θu , Θv , Θx , }

全モデルパラメータ

ΘE = {RE1 , RE2 , bE }エッジ生成パラメータ

ΘY = {RY , bE }属性生成パラメータ

エッジ構造ベクトル
興味関心ベクトル
属性値潜在ベクトルΘu = {W1 , W2 , b, {mi }, {wi }} エッジ構造予測パラメータをもつ．エッジはネットワーク構造および興味関心の相関に基

Θv = {W1 , W2 , b, {mi }, {wi }}興味関心予測パラメータ

づいて生成され，属性値はノードの興味関心の潜在ベクトルと

Θx = {W1 , W2 , b, {qx }, {ri }}属性値予測パラメータ

属性値の潜在ベクトルとの相関に基づいて生成される．
すときに，ノード間ににエッジが張られると仮定する．これは) が与え類似した特性を持つ人物間には人間関係が発生しやすいというられるとする．ここで V (t) はノード集合，X (t) は属性値集合，

homophily [21] 現象と，友人の友人は友人になりやすいというがもつ関心を表す二部グラフ A

(t)

= (V

(t)

,X

(t)

,Y

(t)

E (t) はノード間のエッジ集合，Y (t) は二部グラフにおけるノードと属性値間のエッジである．時刻 t に u から v にエッジが(t)

存在することを eu→v ∈ E (t) ，u が x に対して関心を持つこと(t)を yu→x ∈ Y (t) と表現する．ここで，本研究では特に人と人transitivity [12] といった，ソーシャルネットワークの構造特性を捉えることを狙いとしている．
本研究では各ノードにおける (1) ネットワークの構造的な特徴と (2) 興味関心の特徴を，潜在ベクトルによって表現する．ノードとの関係性をあらわすソーシャルネットワークを対象に検討を

i のネットワークにおける構造の特徴の潜在ベクトルを ui ，興味

おこなうため，ソーシャルグラフのノードは人物を表し，属性

関心の特徴を表す潜在ベクトルを vi とする．ここで，エッジの発値は単語や Twitter におけるハッシュタグなどに対応する．本信側としての特徴を ui→ ∈ Rk1 , vi→ ∈ Rk2 ，エッジの受信側と

(t)

(t)

′

研究の目的は，時刻 t′ > T におけるソーシャルグラフ G (t )′と関心を表す二部グラフ A(t ) を予測することである．本研究では，新規ノード・単語の出現および消滅は考慮せず，既存の
(t′ )

′

ノード i, j 間に存在するエッジの存在確率 P (ei→j ∈ E (t ) ) お′(t′ )
よび P (yi→x ∈ Y (t ) ) を予測する．

4 提案手法
本節では，本論文で提案する未来のソーシャルネットワーク
を予測するためのモデルに関して記述する．提案手法は，(1)潜在ベクトルの相関に基づネットワークく生成モデル，(2) 未

(t)

(t)

しての特徴を u→i ∈ Rk1 , v→i ∈ Rk2 とし，これらを結合したベ(t)クトルを ui

(t)

(t)

(t)

= ui→ ⊕ u→i ∈ R2k1 , vi

(t)

(t)

= vi→ ⊕ v→i ∈ R2k2(t)と表記する．また，属性値の潜在ベクトルを xj∈ Rk2 とする．すべての時間における潜在ベクトルの集合をそれぞれU = {U(t) }t∈T , V = {V(t) }t∈T , X = {X(t) }t∈T と表現する．
(t)

これらを用い，エッジ ei→j が生成される確率は以下の式に基づいて計算する．

(
(t)
(t) ⊤
(t)
P (ei→j ∈ E (t) | ΘE ) = σ ui→ RE1 u→j
(t) ⊤

+vi→

(t)

RE2 v→j + bE)
(1)

来の潜在ベクトルを予測するための生成モデルから構成されこ こ で ，RE1 , RE2 は 潜 在 ベ ク ト ル の 相 関 を 表 す 行 列 ，bEる．学習データから各時刻の潜在ベクトル，ネットワーク生成は エッジ 生 成 の た め の バ イ ア ス 項 ，σ は シ グ モ イ ド 関 数

および未来の潜在ベクトルを予測するためのモデルパラメータ1
σ(x) = 1+exp(x)である．ΘE = {RE1 , RE2 , bE } はエッジ生を学習し，それらを用いて未来の潜在ベクトルを予測し，ネッ

成のためのパラメータ集合で，すべての時刻において共通のパ

トワーク生成モデルに入力することで未来のソーシャルネット

ラメータを用いるものとする．同様に，あるノード i ∈ V の属

ワークにおけるエッジの生成確率を予測する．以下の節ではそれぞれの構成要素について記述する．

4. 1 潜在ベクトルの相関に基づくネットワーク生成モデル
提案手法では，(1) ネットワークの構造的な特徴が類似している．(2) 興味関心が類似している．という二つの条件を満た

性値 x ∈ X の生成確率は以下で求める．
(
)
(t)
(t) ⊤
(t)
P (yi→j ∈ Y (t) | ΘY ) = σ vi
RY xj + bY

(2)

ここでも，ノードの潜在ベクトルと属性値の潜在ベクトルとの相関が大きいほどエッジが生成される確率が大きくなる．これらを踏まえ，すべての時刻 t = 1 ∼ T におけるソーシャルグラ
フの生成確率に対する対数尤度関数は以下のようになる．

...

P (ui

𝑚!

𝑾𝟐

...

...

(#$%)

𝒗!

Rk

($)

(

∑$∈ &(") ! 𝑤$()(t)
| V(t−1) , Θv ) = N vi ; µ(t)(8)
v , σv I ,∑(t−1)
j∈E (t) (i) wj vj
(t−1)
∑
+b
µ(t)
+ mi W2
v = W1 vij∈E (t) (i) wj

𝑾𝟐 𝒗$"

𝑾𝟏 𝒗"

𝑚! 𝑾𝟐

(t)

P (vi
∑$∈ &(") ! 𝑤$ 𝒗$(")∑$∈ &(") ! 𝑤$+~𝓝∑$∈ &(") ! 𝑤$ 𝒗$(")

𝒃

+

,

𝝈"

(

𝑖

(
)
(t)
| U(t−1) , Θu ) = N ui ; µ(t)(7)
u , σu I ,∑(t−1)
j∈E (t) (i) wj uj
(t−1)
∑
µ(t)
+ mi W2+bu = W1 uij∈E (t) (i) wj
(t)

𝒗! "

ここで，wi ∈ R+ はノード i の影響力の大きさで，mi ∈ R+
はノード i の受容性の大きさを示している．E (t) (i) は時刻

t に お い て ノ ー ド i が 接 続 し て い る ノ ー ド の 集 合 で あ り，{}(t)
E (t) (i) = j | ei→j ∈ E (t) である．上記予測モデルの第一

図 3: 潜在ベクトルの伝搬．黄色枠で囲まれたようなグラフが項は潜在ベクトル自身の時間経過による変化を表しており，第与えられたとき，あるノード i の潜在ベクトルは，そのノード

二項はネットワーク中で接続する他のノードからの影響を考慮が接続するノードの潜在ベクトルの重みに対して線形変換を施した時間経過による変化を表している．これらに基づく特徴

したベクトルの重み付き線形和の方向に対して変化が生じる．

量の変化を線形変換と非線形関数による変換によって，未来の

ここで各ノードの影響力 wj が大きいほどそのノードに対応す

潜在ベクトルの状態を予測する．ここで，σu , σv はハイパパ

るベクトルの影響が大きくなり，ノード i の受容性 mi が大きラメータであり，その他変数および行列は学習データから推定

いほど，隣接ノードからの潜在ベクトルの伝搬による影響が大

する．

きくなる．

同様に，属性値の潜在ベクトルの変化は，

)
(
(t)
(9)
| V(t−1) , X(t−1) , Θx ) = N xi ; µ(t)x , σx I∑(t−1)
j∈Y (t) (x) rj vj
(t−1)
∑
=
W
x
+
q
W
µ(t)
+b
1 i
i
2
x
j∈Y (t) (x) rj
(t)

P (xi

T
∏

LE = log

P (E (t) | U(t) , V(t) , ΘE )

(3)

t=1

=

T
∑

∑

(t)

log P (ei→j ∈ E (t) | ΘE )とする．ここで，Y (t) (x) は時刻 t において属性値 x をもつ}{(t)
ノード集合であり， Y (t) (x) = i | yi→x ∈ Y (t) である．

t=1 (t)ei→j ∈E (t)

+

T
∑

(
)
(t)
log 1 − P (ei→j ∈ E (t) | ΘE )∑(4)

t=1 (t)ei→j ∈E/ (t)

時間経過による潜在ベクトルの変化に関する対数尤度関数は以下で表される．
(t)

LY = logT∏L∆u = log
P (Y

(t)

|V

(t)

,X

(t)

, ΘY )

i∈V

(5)

t=1

=

T
∑

= log
∑

T
∑

(t)

log P (yi→x ∈ Y (t) | ΘY )

∑

(
)
(t)
log 1 − P (yi→x ∈ Y (t) | ΘY )

∏

(t)

P (ui

| U(t−1) , Θu )

(
)
(t)
(t)
N ui ; µu , σu I

(10)
(11)

i∈V

=−

t=1 (t)yi→x ∈Y (t)

+

∏

(6)

∑ 1
(t)
(t)
∥u − µu ∥22 + const.
2σu i
i∈V

(12)

同様に，

t=1 (t)yi→x ∈Y/ (t)(t)

L∆v = log

∏

(t)

P (vi

| V(t−1) , Θv )

(13)

i∈V

=−

4. 2 未来の潜在ベクトルの生成モデル
ここでは，ネットワークを通じた潜在ベクトルの伝搬を考慮することによる，未来の潜在ベクトルの生成モデルについて記(t)L∆x = log

∑ 1
(t)
(t)
∥vi − µv ∥22 + const.
2σ
v
i∈V
∏

(t)

P (xi

| X(t−1) , V(t−1) , Θx )

(14)

(15)

i∈X

述する．本研究では各ノードの影響力と受容性をそれぞれモデ=−

ル化し，これらを考慮した未来の潜在ベクトルの生成を行う．

∑

1
(t)
(t)
∥xi − µx ∥22 + const.
2σ
x
i∈X

(16)

各ノードの影響力が大きいほど，他のノードの潜在ベクトルの変化に対する影響力が大きくなり，受容性が大きいほど，自身の潜在ベクトルを変化させる際に他のノードの潜在ベクトルの影響を強く受けるというモデル化がなされる．
本研究では各潜在ベクトルの変化の確率分布を以下の式で定義する．

4. 3 学習

本節では，予測モデルのパラメータ学習について記述する．
予測モデルのパラメータは出力されるソーシャルネットワークの出現確率が最大化されるように学習する．ここで，本研究では事前分布を考慮した MAP 推定によりパラメータを推定す𝐔 (")

𝐔 ($)

𝓔(")

𝓔($)

4. 4 将 来 予 測

...

𝐔 (%)

𝐔 (&)

学習データから求めたモデルのパラメータを用いて未来の

...

𝓔(%)

ソーシャルネットワークを予測する．本手法では，ソーシャル𝓔(&)

𝓔("#$)

ネットワークの生成と潜在ベクトルの予測を交互に行うことで，
複数ステップ先のソーシャルネットワークにおけるエッジを予

𝐕 (")

𝐕 ($)

...

𝐕 (%)

測する．より具体的には各ノード及び用語の潜在ベクトルの変

𝐕 (&)

化を求め，その潜在ベクトルから未知の時間におけるノード間
𝐗 (")

𝓨(")

𝐗 (&)

...

𝓨(%)

𝓨($)

のエッジ及びエッジと用語との関係が生成される確率を求める．

...

𝐗 (%)

𝐗 ($)

潜在ベクトルの変化は以下の等式により求める．

∑
𝓨(&)

𝓨(&'")

図 4: ネットワーク生成過程のグラフィカルモデル．各時刻の

(t+1)

ui

(t)

= W1 ui + mi W2

(t)

j∈E
∑

(t) (i)wj ujj∈E (t) (i) wj

+b

(24)

ここでパラメータ W1 , W2 , b, {wi , mi }i∈V は学習データからネットワークはその時刻の潜在ベクトルから生成され，次の時最適化したパラメータを用いる．V(t) および X(t) に関しても刻の潜在ベクトルはその時刻の潜在ベクトルと，新しく生成さ同様に求める．

れたネットワークを通じた伝搬によって生成される．

5 合成データを用いた実験
る．ベイズの定理および潜在ベクトルの依存関係 (図 4) に基づ
き変数を分離すると以下のように変形できる．

ここでは合成データに対して本手法を適用することにより，手法の特性を検証する．本実験では，密に接続された２つのコミュニティが徐々に統合していく場合のデータと，徐々に分裂

U, V, X, Θ

していく場合の２つのデータを合成する．ここではノード数は()= arg max P U, V, X | {E (t) , Y (t) }t∈1···T , Θ(17)

U,V,X,Θ

()= arg max P U, V, X, {E (t) , Y (t) }t∈1···T | Θ

統合していく場合のデータは以下のような手順で生成した．
(18)

U,V,X,Θ
(1)) + log P (V

(t)

|U

= arg max log P (U

(1)

(1)

) + log P (X+に一定確率 p でエッジを張る．(3) 時刻 t における隣接行列を
log P (E

(t)

,V

(t)

A(t) ，属性との関係行列を T(t) とし，以下の更新式で次の時, ΘE )

t=1

刻のグラフを生成する．

+ log P (Y (t) | V(t) , X(t) , ΘY )+T∑(1) ２つの非連結なクリークを生成し，それぞれの連結成分が「赤」と「青」をもつように設定する．(2) 2 つのクリークの間)

U,V,X,Θ
T∑

20，属性は「赤」と「青」の 2 つとして実験した．

()
A(t+1) = min ⌊A(t) + ϵA(t)⊤ A(t) ⌋, 1()
T(t+1) = min ⌊T(t) + ϵA(t)⊤ T(t) ⌋, 1

log P (U(t) | U(t−1) , Θu )t=2

+ log P (V(t) | V(t−1) , Θv )+ log P (X(t) | V(t−1) , X(t−1) , Θx )= arg max R + LE + LY +U,V,X,Θ

T
∑

(t)
(t)
(t)
L∆u + L∆v + L∆x .

(19)
(20)

(25)
(26)

ここで，⌊·⌋ は床関数であり，行列の各要素に適用する．本実
験では p = 0.1 とし，ϵ = 0.5 とした分裂していく場合のデータは以下の手順で生成した．(1) 統

t=2合する場合と同様に２つの非連結なクリークを生成し，一定確

本研究ではこの損失関数を勾配降下法に基づいて最大化する．

率のもとで，２つのクリークに存在するノード間にエッジを生

ここで，成する．(2) 時刻をひとつ進めるたびに，クリーク間にあるエッR = log P (U(1) ) + log P (V(1) ) + log P (X(1) )
(21)
∏
∏
(1)
(1)
= log
N (ui ; 0, σu I) + log
N (vi ; 0, σv I)
i∈V

+ log

∏

i∈V
(1)

N (xi ; 0, σx I)

i∈X

∑ 1
(1)
∥x ∥22 + Const.
2σx i
i∈X

図 5 は合成データセットに対して提案手法を適用した際の予測結果である．図 (a)(b) において，左３つのグラフが学習デー
タ，右２つのグラフが予測結果である．これらの図をみると，

(22)

∑ 1
∑ 1
(1)
(1)
∥ui ∥22 +∥vi ∥22
=
2σ
2σ
x
u
i∈V
i∈V
+

ジを一定確率で消失させる．

提案手法はコミュニティの統合，分裂および属性の伝播の様子を予測できていることがわかる．

(23)

であり，各潜在ベクトルに対する正則化項の役割をする．

6 実データを用いた実験
本節では，実データを用いて本提案手法がどれだけ正確にネットワークを予測できるかを検証する．本実験では，提案手法において潜在ベクトルを更新しない場合の手法をベースライ

Training

Forecast(a) ２つのコミュニティが統合していく合成データにおける予測結果

Training

Forecast(b) ２つのコミュニティが分裂していく合成データにおける予測結果

図 5: 合成データに対する予測結果: 図 (a), 図 (b) はそれぞれ２つのコミュニティが統合，分裂していく生成データセットに対して提案手法を適用した際の予測結果を示した図である．ノードの色はそのノードがもつ属性値を表しており，ここでは「青」と「赤」の２つの属性が存在する．
「紫」は両方の属性をもつことを示している．これらの図を見ると，提案手法は，コミュニティの統合，
分裂のパターンをもっともらしく予測できることがわかる．

ン手法として用い，用いた場合の予測モデルと比較することで理，機械学習，人工知能，情報検索，コンピュータビジョンか

提案手法の有効性を検証する．以下の節では実験に用いたデーら構成されるの 47 国際会議の論文データを取得し，2008 年か

タセットの説明および得られた予測結果について述べる．

ら 2012 年までを学習データ，2013 年から 2017 年までをテス

を論文では，比較手法として，提案手法のエッジの潜在ベクトルに対して Recurrent Neural Network (RNN) を適用した

トデータとして用いる．ノード数は 500 で，属性値数は 3854
である．

モデルとして RNN edge ，興味関心の潜在ベクトルと属性値のTwitter はユーザ間のリツイートネットワークであり，時間

潜在ベクトルに対して RNN を適用した手法として RNN attr ，

区分は月単位である．ノードはユーザで，ある月にユーザ u

すべての潜在ベクトルに対して RNN を適用した RNN both ，のツイートを他のユーザ v がリツートした際に u から v におよびエッジを生成するグラフニューラルネットワークに基づ対して有向エッジが張られる．各ユーザは各時間区分のツイーく手法として Variational Graph Auto-Encoder (VGAE ) [16]，トに含まれていたハッシュタグを属性値としてもつ．収集期間

VGRNN [9] を採用する．

は 2010 年１月から 2010 年 10 月までで，学習データとして 1

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

月から 5 月，テストデータとして 6 月から 10 月までのデータを用いた [20]．ここで，すべての時間区分を通じて一度しか出現しなかったユーザはデータセットから除外した．ノード数は234305 で，属性値数は 5372 である．

NIPS は研究者の共著者ネットワークである．ノードは著者，
エッジは共著関係，時間区分は年単位である．ある年に二人の6. 2 実 験 結 果

著者 u, v が共著論文を発表したとき，その二人の著者間に双本 研 究 で は 予 測 精 度 の 検 証 に NLL (Negative Log-

方向の有向エッジが張られる．各ノードはある年に発表した論

Likelihood) と AUC (Area Under Curve) を用いた．NLL

文のタイトルに含まれる単語を属性値としてもつ．2008 年かは低いほど予測対象をよりもっともらしく生成したことを示し

ら 2017 年に発表された機械学習分野の 7 国際会議の論文デーており，AUC は高いほどより正確にエッジおよび属性値の出タを取得し，2008 年から 2012 年までを学習データ，2013 年

現を予測できていることを示している．

から 2017 年までをテストデータとして用いる．前処理として

図 6，図 7 はそれぞれ各予測時刻における負の対数尤度，各単語はステミング処理を行い，全時間区分に出現しない著者

AUC の値の変化を示している．図を見ると，提案手法（青色はデータセットから除外した．ノード数は 32 で，属性値数はの線）はほぼすべての時間において既存手法（橙色の線）と比2411 である．

較してより正確にネットワークを予測していることがわかる．

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

また，ベースライン手法は，時間の経過とともに NLL が上昇

クデータは NIPS と同様の方法で作成した．2008 年から 2017

し AUC が減少する傾向にある一方で，提案手法は時間が経過

年に発表されたデータマイニング，データベース，自然言語処しても精度が低下していないことが図から確認できる．

108

104

103
Proposed
RNN edge
RNN both
VGAE
VGRNN

102
1

2

104

Proposed
RNN edge
RNN both
VGAE
VGRNN

107

106
3
Time segment

4

5

1

(a) NIPS : エッジの NLL

2

3Time segment

4

5

1

(b) DBLP : エッジの NLL

104

3Time segment

4

5

108

106

Attribute NLL

Attribute NLL

Proposed
RNN attr
RNN both2(c) Twitter : エッジの NLL

Proposed
RNN attr
RNN both105
Attribute NLL

Edge NLL

Proposed
RNN edge
RNN both
VGAE
VGRNN

Edge NLL

Edge NLL

105

Proposed
RNN attr
RNN both

107

105
106
1

2

3
Time segment

4

5

1

(d) NIPS : 属性値の NLL

2

3Time segment

4

5

1

(e) DBLP : 属性値の NLL

2

3Time segment

45(f) Twitter : 属性値の NLL

図 6: 予測を行った時刻と負の対数尤度 (Negative Log-Likelihood): 値が低いほど，よりもっともらしくネットワークを生成していることを示す．横軸は予測を行った時刻で縦軸は NLL である．提案手法（青色）はほぼすべての時刻において，ベースライン手法と比較してよりもっともらしいネットワークを生成していることがわかる．

0.825

0.80
Proposed
RNN edge
RNN both
VGAE
VGRNN

0.70
1

2

0.750
0.725

3
Time segment

4

5

0.675

1

2

3
Time segment

4

Attribute AUC

0.70
Proposed
RNN attr
RNN both

0.60

0.85

0.64

0.80

0.62

0.75

Proposed
RNN attr
RNN both

0.70
0.65

3
Time segment

4(d) NIPS : 属性値の AUC

5

2

3Time segment

45

Proposed
RNN attr
RNN both

0.60
0.58
0.56
0.54
0.52

0.55
2

1

(c) Twitter : エッジの AUC

0.60

0.55
1

0.50

5

(b) DBLP : エッジの AUC

0.75

0.65

0.60
0.55

0.700

(a) NIPS : エッジの AUC

Attribute AUC

0.65

0.775

Attribute AUC

0.75

0.800

Proposed
RNN edge
RNN both
VGAE
VGRNN

0.70

Edge AUC

Edge AUC

Edge AUC

0.85

0.65

Proposed
RNN edge
RNN both
VGAE
VGRNN

0.850

0.90

1

2

3
Time segment

4(e) DBLP : 属性値の AUC

5

1

2

3
Time segment

45(f) Twitter : 属性値の AUC

図 7: 予測を行った時刻と AUC (Area Under Curve): 値が高いほど，より正確にネットワークを生成していることを示す．
横軸は予測を行った時刻で縦軸は AUC である．提案手法（青色）はほぼすべての時刻において，ベースライン手法と比較してよりもっともらしいネットワークを生成していることがわかる．

として振る舞い，これらが生成される確率を最大化するよう

7 ま と め本研究ではソーシャルネットワークの時間経過による変化を予測する手法を提案した．提案モデルはノード間のエッジと，
ノードと属性値との関係性の二部グラフのエッジの生成モデルにパラメータを学習する．本研究における予測モデルはネット
ワーク生成のためのモデルと，各ノードおよび属性値の潜在ベクトルの変化の予測モデルから構成される．ネットワークの生成モデルは，潜在ベクトルの相関とバイアスに基づいてエッジの生成確率を決定する．潜在ベクトルの予測モデルは，あるノードの自発的な興味関心の変化と，ネットワーク中で隣接するノード，および属性値から潜在ベクトルの伝搬に基づいて，
新しい時刻における潜在ベクトルを生成すると仮定し，これらを考慮した予測モデルを構成した．生成データを用いた実験より，コミュニティの統合・分裂というソーシャルネットワークの変化を予測できることを示した．実データを用いた実験より，提案手法はベースライン手法と比較して，未観測の時刻における実際のソーシャルネットワークをより正確に予測できることを示した．
今後の展望としては，本論文では離散的な時間における予測モデルを構築したが，連続的な時間における予測モデルについて今後検討を行うことを計画している．

謝辞

本研究は JSPS 科研費 20K23337 の支援を受けたものです．

文

献[1] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing.
Mixed membership stochastic blockmodels. Journal of machine learning research, 9(Sep):1981–2014, 2008.
[2] M. Araújo, P. Ribeiro, and C. Faloutsos. Tensorcast: forecasting time-evolving networks with contextual information.
In Proceedings of the 27th International Joint Conferenceon Artiﬁcial Intelligence, pp. 5199–5203, 2018.
[3] S. Cavallari, V. W. Zheng, H. Cai, K. C.-C. Chang, andE. Cambria. Learning community embedding with community detection and node embedding on graphs. In Proceedings of the 2017 ACM on Conference on Information andKnowledge Management, pp. 377–386, 2017.
[4] H. Chen and J. Li. Exploiting structural and temporal evolution in dynamic link prediction. In Proceedings of the27th ACM International Conference on Information andKnowledge Management, pp. 427–436, 2018.
[5] H. Dai, Y. Wang, R. Trivedi, and L. Song. Deep coevolutionary network: Embedding user and item features forrecommendation. arXiv preprint arXiv:1609.03675, 2016.
[6] A. Grover and J. Leskovec. node2vec: Scalable featurelearning for networks. In Proceedings of the 22nd ACM
SIGKDD international conference on Knowledge discovery
and data mining, pp. 855–864, 2016.
[7] Y. Gu, Y. Sun, and J. Gao. The co-evolution model forsocial network evolving and opinion migration. In Proceedings of the 23rd ACM SIGKDD international conference onknowledge discovery and data mining, pp. 175–184, 2017.
[8] S. Gupta, G. Sharma, and A. Dukkipati. A generative modelfor dynamic networks with applications. In Proceedings of
the AAAI Conference on Artiﬁcial Intelligence, Vol. 33, pp.
7842–7849, 2019.
[9] 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.
[10] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in neural
information processing systems, pp. 1024–1034, 2017.
[11] 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.

[12] P. W. Holland and S. Leinhardt. A dynamic model for social networks. Journal of Mathematical Sociology, 5(1):5–
20, 1977.
[13] X. Huang, J. Li, and X. Hu. Label informed attributed
network embedding. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining,pp. 731–739, 2017.
[14] H. Ito, T. Komamizu, T. Amagasa, and H. Kitagawa.
Network-word embedding for dynamic text attributed networks. In 2018 IEEE 12th International Conference on
Semantic Computing (ICSC), pp. 334–339. IEEE, 2018.
[15] T. N. Kipf and M. Welling. Semi-supervised classiﬁcation with graph convolutional networks. arXiv preprint
arXiv:1609.02907, 2016.
[16] T. N. Kipf and M. Welling. Variational graph auto-encoders.
arXiv preprint arXiv:1611.07308, 2016.
[17] S. Kumar, X. Zhang, and J. Leskovec. Predicting dynamic
embedding trajectory in temporal interaction networks. In
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1269–
1278, 2019.
[18] J. Li, H. Dani, X. Hu, J. Tang, Y. Chang, and H. Liu. Attributed network embedding for learning in a dynamic environment. In Proceedings of the 2017 ACM on Conferenceon Information and Knowledge Management, pp. 387–396,
2017.
[19] S. Liang, X. Zhang, Z. Ren, and E. Kanoulas. Dynamic embeddings for user proﬁling in twitter. In Proceedings of the24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1764–1773, 2018.
[20] T. Lou, J. Tang, J. Hopcroft, Z. Fang, and X. Ding. Learning to predict reciprocity and triadic closure in social networks. ACM Transactions on Knowledge Discovery from
Data (TKDD), 7(2):1–25, 2013.
[21] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds ofa feather: Homophily in social networks. Annual review ofsociology, 27(1):415–444, 2001.
[22] K. Miller, M. Jordan, and T. Griﬃths. Nonparametric latent feature models for link prediction. Advances in neural
information processing systems, 22:1276–1284, 2009.
[23] A. Nigam, K. Shin, A. Bahulkar, B. Hooi, D. Hachen, B. K.
Szymanski, C. Faloutsos, and N. V. Chawla. One-m: Modeling the co-evolution of opinions and network connections.
In Joint European Conference on Machine Learning andKnowledge Discovery in Databases, pp. 122–140. Springer,
2018.
[24] B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online
learning of social representations. In Proceedings of the 20th
ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701–710, 2014.
[25] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei.
Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wideweb, pp. 1067–1077, 2015.
[26] R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha. Dyrep:
Learning representations over dynamic graphs. In International Conference on Learning Representations, 2019.
[27] 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.
[28] 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.
[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.