DEIM Forum 2018 A1-1

ノードがテキスト情報を持つ動的ネットワークにおけるノードと単語の分散表現学習
伊藤

寛祥†

駒水

孝裕††

天笠 俊之††

北川 博之††† 筑波大学大学院システム情報工学研究科 〒 305–8577 茨城県つくば市天王台 1-1-1†† 筑波大学計算科学研究センター 〒 305–8577 茨城県つくば市天王台 1-1-1
E-mail: †hiro.3188@kde.cs.tsukuba.ac.jp, ††taka-coma@acm.org ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
あらまし ネットワークにおけるノードの分散表現学習手法として network embedding が存在する．ノードの分散表
現を得ることで，ノードに対してベクトル空間ベースの機械学習手法を適用できるようになり，ノードの分類，クラスタリング，可視化などの多様なアプリケーションに応用できる．本論文ではノードがテキスト情報を持つ動的ネッ
トワークにおけるノードと単語の分散表現学習手法を提案する．本手法を入力となるネットワークデータに適用すると，ノードおよび単語の分散表現が得られ，さらに，分散表現の時系列的な変化が得られる．学術論文データベース
における共著ネットワークを用いた実験より以下を示した．(1) 本手法で得られたノードの特徴に対して機械学習手法を適用すると，既存の手法と比較して高精度に分類，クラスタリングできる．(2) ノードと単語の分散表現学習において時系列性を考慮することで，考慮しない場合と比較して高い精度を実現する．(3) 本手法により学習されるノードと単語の分散表現の類似度は，入力となるネットワークにおけるノードの隣接性と単語の共起性の強さをそれぞれ反映しており，さらに，それらの時系列的な変化を捉えられる．
キーワード 分散表現学習，グラフデータマイニング，時系列データ

1. は じ め にトワークの構造のみに着目した手法がほとんどだった．近年，ノードが持つ属性を利用し，network embedding の性能を向上

ノードがテキスト情報を持つネットワークは実世界に多く存させる取り組みが行われてきた [5], [10], [17]．これらの手法は，在する．このようなネットワークの例として，SNS におけるネットワーク構造と属性値の間の相関関係を利用し，それらをソーシャルネットワークや，学術研究における共著ネットワー

補い合わせた上でノードの分散表現を学習する手法で，ネットクなどが挙げられる．共著ネットワークを例にすると，研究者

ワーク構造のみを用いる手法よりも，機械学習のタスクにおいがノード，共著関係がエッジとなり，各ノード（研究者）は各々てより有用な分散表現が得られることが示されてきた．しかしがこれまでに発表した論文のタイトルまたはアブストラクトをながら，これまでの研究は，ノードをベクトル空間に埋め込む

テキスト情報として保持する．このようなネットワークにおけことに注目しており，単語の分散表現は得ることができない．

る，グラフ構造とテキスト情報を利用したデータマイニング手

すなわち，既存の手法では，単語とノードの相互関係を分散表法は数多く研究されている [4], [22], [24]．また，このような研現の類似度として得ることができず，ノードの分散表現の意味

究のなかで，エッジ情報とテキスト情報には相関関係があるこ付けが困難であるという問題がある．

とが明らかにされてきた（homophily eﬀect [6], [11]）．この性

さらに，ノードがテキスト情報をもつネットワークは，時間質を捉えて，エッジ情報とテキスト情報を同時に用いることで，の経過とともに変化する場合がある．すなわち，時間の経過とコミュニティ検出 [24]，感情分析 [4]，ノード分類 [22] といった

ともに，ネットワークにおけるノードやエッジが増減したり，問題に対して，エッジ情報やテキスト情報のみを考慮する場合ノードが保持するテキスト情報が変化するという状況が考えらと比較してより高精度な分析が行えることが報告されている．

れる．研究者ネットワークを例にすると，時間の経過により新ネットワークデータに対するデータマイニング手法のひとしい研究者が登場し，また既存の研究者も新しい共著関係を構

つに network embedding [3], [14], [18] という手法が存在する．

成する可能性がある．また，研究者の研究分野も変化する場合

network embedding とは，ネットワークにおけるノード間の隣があるため，関連するテキスト情報も時間とともに変化する場

接関係に基づいてノードをベクトル空間に埋め込み，ノードの合がある．これらのことから，ノードおよび単語の分散表現は分散表現を得る手法である．この手法をネットワークデータに

時間の経過とともに変化すると考えられる．このような時系列

対して適用することで，ノード集合に対してベクトル空間ベー変化するネットワークにおける分散表現学習のための最も単純

スの様々な機械学習手法が適用できるようになる．例として，な方策としては，各時刻ごとに既存の分散表現学習手法を適用

ノードの分類 [25]，クラスタリング [24]，リンク予測 [2]，ネッ

することが考えられる．しかしながら，このアプローチでは，トワークの可視化 [16] に対して有用であることが知られている．

前の時刻における分散表現の学習結果を考慮することができな

Network embedding に関するこれまでの多くの研究は，ネッ

いため，現時刻におけるデータにオーバーフィットする可能性

があるという問題が存在する．

embedding 手法が提案されている．DeepWalk [14] では，ネッ

本稿では，ノードがテキスト情報をもつ動的ネットワークに

トワークのランダムウォークにより得られるノードのシーケン

おけるノードと単語の分散表現学習手法を提案する．本手法でスに対して skip-gram [12] を適用することでノードの分散表現

は，ノードと単語の分散学習は相互に補い合いながら同時に学を得る．LINE [18] では，1 次の隣接性，2 次の隣接性を保存

習され，さらにこれらの分散表現の時間的な変化が検出される．

する手法を提案した．node2vec [3] では，DeepWalk における本研究における基本的な仮定は，以下の３つである．(i) ネッ

ノードのシーケンス作成の際，深さ優先探索と幅優先探索の双トワーク中で隣接性が高いノード同士の分散表現は類似度が高方を考慮することで，network embedding の性能向上に成功

い．(ii) あるノードとそれに関連する単語の分散表現の類似度した．

は高い．(iii) 隣接する時間区分におけるノードと単語の分散表

単語の分散表現学習手法は，自然言語処理，情報検索，データ

現は大きく変化しない．本研究では仮定 (i),(ii),(iii) を非負値

マイニングにおいて近年多くの注目を集めている．Skip-gram行列分解 [8], [9] として定式化し，これらを同時に最適化するアと CBOW [12], [13] は word2vec としても知られ，最もよく知

ルゴリズムを提案する．

られる単語の分散表現学習手法である．この手法は，単語の意味

実験では，学術論文データベースにおける共著ネットワーク

的な類似度を表現するベクトル表現を効率的に学習する手法でを用い，本手法の有用性に関して検証を行った．実験では以下ある．また，この手法は多くの拡張手法が存在しており，その例の３つの項目に関して検討を行った．(Q1) 本手法により得らとして，文書と単語の分散表現学習手法の ParagraphVector [7]れるノードの分散表現は，機械学習手法に対してどれだけ有用が存在する．この手法では，PV-DM と PV-DBOW 2 つのモーであるか？(Q2) ノードがテキスト情報をもつ動的ネットワーク

ドが存在する．

における分散表現学習において，前の時刻の分散表現を考慮す

ネットワークのリンク構造に加え，ノードの属性情報を考ることがどれだけ有益であるか？(Q3) ノードと単語の分散表

慮した network embedding 手法が提案されている．ノード

現の類似度はノードの隣接性，単語の共起性の強さを反映してのテキスト情報を考慮した network embedding 手法としているか？またそれらの時間的な変化が検出できるか？実験の結TADW [23] が存在する．また，この研究では，DeepWalk は果，以下の３つの結論が得られた．(A1) 本手法により得られ

行列分解モデルとして表現できることを示した．ノードの属性

たノードの分散表現に対して，ベクトル空間ベースの分類手法

情報を考慮した network embedding 手法として，LANE [5] が(one-vs-rest SVM)，クラスタリング手法 (k-means) を適用す存在する．この手法は，ネットワーク中でのノードの隣接性がると，既存の分散表現学習により得られた分散表現に対して適高く，属性の類似度が高いノードは分散表現の類似度が高いと用するよりも高い精度を実現する．(A2) 提案手法において前いう直感に基づいている．

の時刻の分散表現を考慮することで，分類とクラスタリングに本研究では，ノードの分散表現と単語の分散表現を同時に獲おいてより有用な分散表現が得られる．(A3) 提案手法により得するという新しいアプローチをとり，ネットワークの時系列得られた分散表現の類似度は，ノードの隣接関係と，単語と単的変化に対応した新しい分散表現学習手法を提案する．

語の共起性，ノードと単語の共起性の強さを反映しており，さらに，それらの時間的な変化を検出できる．
本研究の貢献は以下にまとめられる．

•

ノードがテキスト情報をもつ動的ネットワークにおけるノードと単語の分散表現学習手法を提案した．本手法により以下が得られる． (a) ノードの分散表現，(b) 単語の分散表現，(c) 分散表現の時間的な変化．
•

3. 問 題 設 定
本節では，本手法の入力となる，ノードがテキスト情報を持つ動的ネットワークの定義，および，本研究の目的である，ノードと単語の分散表現学習の定義に関して記述する．
時刻 t における，n 個のノードがそれぞれ d 次元の単語特徴量を持つ，ノードがテキスト情報を持つ動的ネットワークを本手法により得られたノードの分散表現は，既存の分散

G (t) = {A(t) , X(t) } とする．ここで，A(t) ∈ Rn×n はネット

表現学習手法により得られた分散表現と比較して，ベクトル空

ワークの重み付き隣接行列を表し，行列 A(t) の各要素 Au,v は間ベースの分類，クラスタリング手法に対して有用である．

ノード u と v のエッジの重みを表す．X(t) ∈ Rn×d は単語特

•

(t)

(t)

本手法により得られる分散表現の類似度は，ノードの隣

徴量行列を表し，各要素 Xu,x はノード u の単語 x に対する

接性，単語の共起性を表現しており，それらの時系列的な変化

重みを表現する．ノードがテキスト情報を持つネットワークのが得られる．

時刻 t = 0 ∼ T におけるすべてのスナップショットを G (t) の

2. 関 連 研 究集合とし，G = {G (t) }T
t=0 と表現する．本研究では [20] と同様の設定を用い，ノードの数は時間の経過で変化させず，エッジ

Network embedding 手法は，ネットワーク分析の研究分野

数のみを変化させる（ある時刻 t で存在しないノードはエッジ

において，近年多くの注目を集めている．ネットワークのエッと単語特徴を持たない）．これにより，行列 A(t) および X(t)ジ情報を保存する network embedding 手法として，LLE [15]，のサイズは時間の経過で変化しなくなる．

Isomap [19]，Laplacian eigenmap [1] が存在する．これらの手本研究の目的は，ノードと単語の k 次元の分散表現を獲得

法は隣接行列の固有ベクトルを検出することにより達成される．

し，それらの時間的な変化を検出することである．ここで，kより最近では，ノードのより高次の隣接性を保存する network

は n と d と比較して十分に小さいとする（k ≪ {n, d}）．本研

究の目的は以下に定義される．
定義 3.1 (研究目的)

Lword = X(t) − U(t) (M(t) )T

ノードがテキスト情報を持つ動的ネット

ワーク G が与えられた時，本研究の目的は時刻 t = 0 ∼ T におけるすべてのノードの分散表現を表す非負行列 U

(t)

∈R

2

(2)
F

4. 1. 3 前時刻からの分散表現の保存
時刻 t における分散表現を得る際，前時刻 t − 1 における分n×k

散表現を考慮させることは，ある時刻 t におけるデータへの∈ Rd×k を

オーバーフィットを避けるために有効である．さらに，直感的(t)得ることである．ここで，Ui ∈ Rk （行列 U の i 行目）は(t)
ノード i の分散表現を表し，Mi ∈ Rk （行列 M の i 行目）には，時刻 t における分散表現は，前時刻 t − 1 の分散表現か

は単語 i の分散表現を表す．□

における分散表現行列のフロベニウスノルムの大きさで測ること，すべての単語の分散表現を表す非負行列 M(t)ら大きく変化しないと考えられる．この直感は時刻 t と t − 1とができる．

4. 提 案 手 法

Lshif t = U(t) − U(t−1)

本節では，本研究の提案手法である，ノードがテキスト情報

F+ V(t) − V(t−1)+ M(t) − M(t−1)

をもつ動的ネットワークにおける分散表現学習手法に関して説明する．本手法では，ノードと単語の分散表現を k 次元の非負

2

時刻

2

(3)
F
2
F

t と t − 1 における分散表現が類似している時，Lshif tベクトルで表現する．本手法では，ノードと単語の分散表現にの値は小さくなる．このことから，Lshif t の項を考慮すること関する以下の３つの損失関数を設定する．
（1）ノードの隣接性

で，時刻 t − 1 における分散表現を時刻 t における分散表現にの保存，（2）ノードと単語の関連性の保存，（3）前時刻における対して影響を与えられるということを示している．

分散表現の保存．これらを統合した損失関数を，複数の制約付

4. 1. 4 統合した損失関数

き Non-negative Matrix Factorization (NMF) として定式化

ノードがテキスト情報をもつ動的ネットワークにおけるノー

し，それらを同時に最適化することで，ノードと単語の分散表

ドと単語の分散表現を得るためには，上記の 3 つの損失関数が現を得る．

最小化されなければならない．以下は３つの損失関数を統合し

4. 1 損 失 関 数た損失関数である．

4. 1. 1 ノードの隣接性の保存
L = δLnode + (1 − δ)Lword + αLshif t

本研究では，[21] に倣い，ノード間の隣接性を，1 次の隣接性と 2 次の隣接性の線形和で表現する．ノード間の 1 次の隣接性
(t)

(t)

を表す行列 S1 ∈ Rn×n を S1 = A(t) とする．ノード間の 2
(t)

(t)

次の隣接性を表す行列 S2 ∈ Rn×n を S2 = (A(t) )T A(t) と
(t)

(t)

する．最後に，ノード間の隣接性行列を S(t) = S1 + ηS2 とする．ここで，η > 0 は 1 次と 2 次の重みパラメータで，本研(4)

ここで，δ ∈ [0, 1] は Lnode と Lword のバランスを調整するパ
ラメータ，α ∈ [0, ∞) は前時刻における影響の大きさを調整す
るパラメータである．本論文では，δ = 0.5 で固定する．

4. 2 最 適 化
提案手法における最適化問題は以下で記述される．

究では η = 3 で固定する．

Network embedding の基本的な方策は，ノード同士の分散{}
U(t) , V(t) , M(t) =表現の類似度とノード同士の隣接性との差異を最小化することである [14]．本研究では非負の重み行列 V

(t)

∈R

n×k

arg minL(5)

U(t) ,V(t) ,M(t) >=0を設定

し，分散表現行列 U(t) ∈ Rn×k との行列積で隣接性行列 S(t)式 4 はすべての変数行列に関して同時に凸にならない．ここを復元させることで，ノードの分散表現を得る．これは以下ので，[8] の最適化方式にならい，式 4 の最適化アルゴリズムを導損失関数で記述される．

出する．
最適化問題 5 の KKT 条件は以下である．

Lnode = S

(t)

−U

(t)

(V

(t) T

2

(1)

)

F

ここで，∥·∥2F はフロベニウスノルムである．

4. 1. 2 ノードと単語の関連性の保存
直感的には，ノード i が単語 w と関連するとき，i と w の分散表現の類似度は高くなると考えられる．ノードと単語の関

(t)
(t) >
U (t) >
=0
= 0, M >= 0, V(6)∇U (t) L >=0= 0, ∇M (t) L >= 0, ∇V (t) L >(7)

U (t) ⊙ ∇U (t) L = 0, V (t) ⊙ ∇V (t) L = 0, M (t) ⊙ ∇M (t) L = 0(8)

連性は，ノードがもつテキスト情報における単語の出現頻度として表現される．本研究では分散表現の類似度を内積として定
(t)

(t)

(t)

義すると，上記の直感に関する損失は (Xi,w − Ui · Mw )2 と表現される．この損失をすべてのノードと単語の組み合わせに関して考慮すると，ノードと単語の関連性の保存に関する損失関数は以下で記述される．

ここで，⊙ はアダマール積である．つづいて各変数に関する勾配は以下で表される．

∇U(t) L = − δS(t) M(t) − (1 − δ)X(t) M(t) − αU(t−1) (9)
+ δU

(t)

(V

(t) T

) V

(t)

+ (1 − δ)U

(t)

(M

(t) T

) M

(t)

′

1: ϵ′ ← maxInt, ϵ ← ϵ2

∇V(t) L = − δ(S(t) )T U(t) − αV(t−1)
+ δV

(U

(t) T

) U

(t)

+ αV

(10)
(t)

∇M(t) L = − (1 − δ)(X(t) )T U(t) − αM(t−1)+ (1 − δ)M

(t)

(U

(t) T

) U

(t)

+ αM

(11)

U(t) , V(t) , M(t) ← random non-negative init

4:

while abs(ϵ′ − ϵ) >= δ doU(t) ← U(t) ⊙5:

δS(t) M(t) +(1−δ)X(t) M(t) +αU(t−1)
U(t) (δ(V(t) )T V(t) +(1−δ)(M(t) )T M(t) )+αU(t)δ(S(t) )T U(t) +αV(t−1)δV(t) (U(t) )T U(t) +αV(t)6:V(t) ← V(t) ⊙7:

M(t) ← M(t) ⊙8:U(t) ← U(t) QU

9:

V(t) ← V(t) QV (t)

(12)

10:

M(t) ← M(t) QM (t)δS(t) M(t) + (1 − δ)X(t) M(t) + αU(t−1)(t)
U (δ(V(t) )T V(t) + (1 − δ)(M(t) )T M(t) ) + αU(t)11:ϵ′ ← ϵを導出した．

U

2: for t ∈ 0 : T do
3:(t)

式 8 に対して勾配を代入することで，各変数に関して更新式(t)Input: {A(t) , X(t) }T
t=0 , δ, αOutput: {U(t) , V(t) , M(t) }T
t=0+ αU(t)(t)

Algorithm 1 Optimization Algorithm

←U

(t)

⊙

δ(S(t) )T U(t) + αV(t−1)δV(t) (U(t) )T U(t) + αV(t)(13)

M(t) ← M(t) ⊙(1 − δ)(X(t) )T U(t) + αM(t−1)(1 − δ)M(t) (U(t) )T U(t) + αM(t)(14)

上記更新式を繰り返し実行することで，損失関数 4 は単調減
少し，ある程度収束したところで行列分解が完了する．

Algorithm 1 は 最 適 化 問 題 5 を 最 適 化 す る た め の ア
ル ゴ リ ズ ム で あ る ．行 列 の 正 規 化 は 行 列 の 更 新 の 後 に 行
わ れ る ．QU (t) , QV (t) , QM (t) は 正 規 化 行 列 で ，QU (t) =Diagonalize(U(t) ), QV (t) = Diagonalize(V(t) ), QM (t) =Diagonalize(M(t) ) である．ここで，Diagonalize(Z ∈ Ra×b ) = Diag

( b
∑
i=1

Z1,i · · · ,()ϵ ← L U(t) , V(t) , M(t)12:end while

13:

V(t) ← V(t) ⊙

b
∑

)
Za,i

i=1

(15)

(1−δ)(X(t) )T U(t) +αM(t−1)(1−δ)M(t) (U(t) )T U(t) +αM(t)(t)

14: end for

著者，会議といった情報を保持するデータベースである．本研
究では使用する論文データを，データベース (DB)，データマ
イニング (DM)，機械学習 (ML)，情報検索 (IR) の 4 つの分
野に絞り，それぞれの分野に関して 5 つずつ会議を選択して，2016 までにそれらの会議で発表された論文を対象にして実験を行った．実験で使用した会議の内訳を表 1 に示す．ノイズの削減のため，5 本以上論文を出していない著者はデータから除いた．テキスト情報に関しては，前処理としてストップワードの除去とステミングを行った．各著者は各年において最も多く著作を投稿した分野にラベル付けされる．
本実験では，ノードがテキスト情報を持つ動的ネットワーク
は以下の方式で構成される．ノードは著者（研究者）である．各
著者は共著関係に基いてエッジが張られており，エッジの重みである．Diag(·) は対角行列の成分のリストを入力とし，対角行列を返す関数である．

5. 実

験

は共著論文の数である．ネットワークのスナップショットは各年ごとに構成される．ノードのテキスト情報は，各著者が各年に発表した論文のタイトルをすべて連結したものを bag-of-words
ベクトルに変換したものとする．著者（ノード）の数は 6625

本節では，実データを用いた実験を通して提案手法の有用性に関して議論する．本実験では以下の 3 つの項目に関して議論を行う．(Q1) 本手法により得られるノードの分散表現は，機械学習手法に対してどれだけ有用であるか？(Q2) ノードがテで，特徴となる単語数は 2845 である．本実験では簡単のため
エッジの消去は考慮しない．図 1 はグラフにおける各年でのエッジ数を示しており，時間の経過とともにエッジ数が線形に増えていることがわかる．

キスト情報をもつ動的ネットワークにおける分散表現学習におるか？(Q3) ノードと単語の分散表現の類似度はノードの隣接性，単語の共起性の強さを表現しているか？またそれらの時間的な変化が検出できるか？

5. 1 データセット# of edge

いて，前の時刻の分散表現を考慮することがどれだけ有益であ

140000120000100000
80000
60000
40000
20000
0
2000

2002

2004

2006

2008

2010

2012

2014

2016

year

図 1: ネットワークの各年におけるエッジ数

本研究では，コンピュータサイエンス分野の学術論文データベースの DBLP (Digital Bibliography Project)（注 1） を用いて本手法の有用性の検証を行う．DBLP は各著作のタイトルや

5. 2 定量的評価
本節では，(Q1) 本手法で得られるノードの分散表現は，機械学習手法に関してどれだけ有用であるか？ に関して検証を（注 1）：http://dblp.uni-trier.de/表 1: 各研究分野において選出した国際学会のリスト

る．この図を見ると，α = 0.01, 0.1 のときに，全く考慮しない場合と比較してより高い精度で分類，クラスタリングできてい

DB

DM

ML

IR

SIGMOD, VLDB

KDD, ICDM

NIPS, ICMLSIGIR, ECIR

ることがわかる．図 3(b) は各年におけるノードのクラスタリ

PODS, EDBTPKDD, SDM

ECML, UAI

JCDL, ECDL

ング精度を示したものである．これを見ると α = 0.1, 1 のとき

ICDT

PAKDD

COLT

TREC

に特に高い精度を示していることが分かる．これらの結果から，前の時刻における分散表現をある程度考慮することで，分類と行う．ここでは，本手法と比較手法それぞれによって得られたノードの分散表現に対して，線形代数ベースの機械学習手法を適用することで，分類，クラスタリングを行い，本手法によって得られるノードの分散表現の有用性に関して議論する．分類に関しては one-vs-rest SVM を用いてノードのラベルの推定を行う．分類精度は 10 分割交差検定で検証を行い，学習デー
タに 90%，テストデータに 10% の割合でデータを分割する．
クラスタリングには k-means を用い，精度は 10 回実験を行ったときの精度の平均で測る．
比較手法には以下の 2 つの手法を用いた．

•

DeepWalk [14]: ノードの分散表現学習手法のベースラ

インで，ネットワークのエッジ構造のみから分散表現を学習する手法である．この手法ではノードのシーケンスを，複数のラン
ダムウォークから生成し，そのシーケンスに対して skip-gramを適用することで，ノードの分散表現を得る．

•

PV-DBOW [7]: 単語の分散表現学習手法のベースラ

インで，文書の分散表現と単語の分散表現を同時に得る手法である．
これらの手法は，ネットワークの動的な変化に対応できない
ため，各時刻のスナップショットに対してこれらの手法を適用することで，それぞれの分散表現を得る．本実験では，すべての手法における埋め込み空間の次元を 100 に固定して実験を行う．
図 2(a) は各時刻における，既存手法と提案手法の分類精度を示したものである．この図から，本手法は既存の手法と比較してより高い精度で分類を行えることが分かる．図 2(b) は各時刻における，既存手法と提案手法のクラスタリングの精度を示したものである．この図から，本手法は既存の手法と比較してより高い精度でクラスタリングを行えることが分かる．

5. 3 パラメータ α の影響
本節では，(Q2) ノードがテキスト情報をもつ動的ネットワー
クにおける分散表現学習において，前の時刻の分散表現を考慮することがどれだけ有益であるか？ に関して議論する．本実験
では，提案手法におけるパラメータ α を変化させることにより，分類，クラスタリング精度がどのように変化するのかを検証する．パラメータ α は分散表現の学習において，前時間における分散表現をどれだけ考慮するかを調節するパラメータである．α = 0 のときは前の時刻における分散表現を全く考慮しな
くなり，α = ∞ のときは学習される分散表現は前の時刻における分散表現と全く同じになる．このため，本実験では最も適切な α を探索することで，前の時刻における分散表現をどれだけ考慮することが最も有効なのかに関して調査する．
図 3(a) は各年におけるノードの分類精度を示したものであ

クラスタリングにおいてより有用な分散表現が得られることが示された．

5. 4 定性的評価
本節では，(Q3) ノードと単語の分散表現の類似度はノードの隣接性，単語の共起性の強さを表現しているか？またそれらの時間的な変化が検出できるか？に関して議論する．本実験では，ノードとノード，単語と単語，ノードと単語の分散表現の類似度を測り，それが大きいものがどのようなノードまたは単語であるかを観察することで，学習された分散表現の特性を調査する．本実験では，分散表現の類似度は内積の大きさとする．
図 4 は 2000 年，2005 年，2010 年，2015 年 において，ノード

jiawei han の分散表現と最も類似する単語の分散表現の top-10を並べたものである．この図を見ると，2000 年において最も類似度が高い単語は “knowledge discovery” や “database”，2005
年においては “eﬃcient itemset” や “graph mining”，2010 年
では “network mining”，2015 年では “heterogeneous network

mining” と時間の経過とともに類似度が高い単語が変化していることが分かる．これは，時間の経過による “jiawei han” の研
究テーマの変化を検出できたということを示している．
図 5 は 2000 年，2005 年，2010 年，2015 年 において，ノード jiawei han の分散表現と最も類似するノードの分散表現のtop-10 を並べたものである．この図をみると，jiawei han はすべての時刻において raymond t. ng, philip s. yu, jian peiと最も類似度が高く，また，時間の経過とともに，類似度が高いノードの内訳が変化していることがわかる．これは，研究活動における定常的な共著関係（教授職同士の共著）と一時的な共著関係（教授と学生の共著）のそれぞれが検出できていることを示している．
図 6 は 2000 年，2005 年，2010 年，2015 年 において単語

neural の分散表現と最も類似度が高い単語の分散表現の top-10を示したものである．この図を見ると，2000 年には “recogni-tion” と類似度が高く，2005 年には “kernel” や “bayesian”，
2010 年には “convolution”，2015 年には “deep neural networks” や “recurrent neural network” といった単語との類似度が高いということが分かる．これらのことは，ある単語と関連する単語が時間の経過とともに変化していることを示しており，研究トピックに関連する単語の時間経過による変化を検出できていることを示している．しかしながら，2010 年，

2015 年においては，類似度が高い単語に “social” が含まれている．この結果は “network” という単語が，“neural network”と “social network” の二通りの使われ方が存在することに起因していると考えられる．このような単語の多義性に対応していくことは今後の課題として挙げられる．

Accuracy(%)

80
60
40

100

60
40
20

20
0

Proposed
DeepWalk
PV-DBOW

80

Accuracy(%)

Proposed
DeepWalk
PV-DBOW

100

2000

2005

2010

0

2015

2000

2005

year

2010

2015

year

(a) 分類精度(b) クラスタリング精度

90

80

85

70

Accuracy(%)

Accuracy(%)

図 2: 既存手法と提案手法の各年における分類精度とクラスタリング精度

80
75
70
65
60
2000

α=0
α=0.01
α=0.1
α=1
α=10
2002

60

α=0
α=0.01
α=0.1
α=1
α=10

50
40

2004

2006

2008

2010

2012

2014

2016

30
2000

2002

2004

2006

year

2008

2010

2012

2014

2016

year

(a) 分類精度(b) クラスタリング精度

図 3: 提案手法のパラメータ α を変化させた際の各年における分類精度とクラスタリング精度

6. ま と め謝

本稿では，ノードがテキスト情報を持つ動的なネットワーク

本研究は AMED の課題番号 JP16lk1010017h0001 の支援をにおけるノードと単語の分散表現学習手法を提案した．実験の辞受けたものである．

結果より，以下の 3 つを示した．
（1）本手法より学習されたノードの分散表現は，既存手法による分散表現と比較して分類とク
ラスタリングに関して有用である．
（2）時間的な変化を考慮することで，分類とクラスタリングに関してより有効な分散表現が得られる．
（3）本手法により学習される分散表現同士の類似度は，ノードの隣接性と，単語の共起性，ノードと単語の関連性をそれぞれ反映しており，それらの時間的な変化を捉えられている．
今後の展望としては以下の二つが挙げられる．(i) 単語の多義性の問題の解消．実験において議論したとおり，データ工学の分野では “network” という単語は “social network” と“neural network” の２通りの使用方法がある．このような単語の多義性は，ノードおよび単語の埋め込みにおいて，“social”と “neural” の類似度が不当に高くなるといった，誤った学習をもたらす可能性がある．今後はこのような単語の多義性がもたらす問題を解決する方策に関して検討していく予定である．

(ii) 分散表現の予測．まだ観測されていないネットワークの状態を予測し，分散表現を得ることは様々なアプリケーションに
おいて極めて有用である．このような問題設定に対応し，現時刻までに得られた分散表現から次の時刻の分散表現を予測する手法を検討していく予定である．

文

献[1] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps andspectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585–
591, 2002.
[2] Sheng Gao, Ludovic Denoyer, and Patrick Gallinari. Temporal link prediction by integrating content and structure
information. In Proceedings of the 20th ACM international
conference on Information and knowledge management, pp.
1169–1174, 2011.
[3] Aditya Grover and Jure 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.
[4] Xia Hu, Lei Tang, Jiliang Tang, and Huan Liu. Exploitingsocial relations for sentiment analysis in microblogging. In
Proceedings of the sixth ACM international conference on
Web search and data mining, pp. 537–546, 2013.
[5] Xiao Huang, Jundong Li, and Xia Hu. Label informed attributed network embedding. In Proceedings of the Tenth
ACM International Conference on Web Search and Data
Mining, pp. 731–739, 2017.
[6] Denise B Kandel. Homophily, selection, and socializationin adolescent friendships. American journal of Sociology,
Vol. 84, No. 2, pp. 427–436, 1978.
[7] Quoc Le and Tomas Mikolov. Distributed representations

2000

2005

2000

2005

2010

2015

2010

2015

図 4: “jiawei han” の分散表現と最も類似度が高い 単語の分 図 5: “jiawei han”
散表現

2000

2005

2010

2015

図 6: “neural”の分散表現と最も類似度が高い 単語の分散

表現

[8]

[9]

[10]

[11]
[12]

[13]

[14]

の分散表現と最も類似度が高い ノードの分散表現

of sentences and documents. In Proceedings of the 31st International Conference on Machine Learning (ICML-14),
pp. 1188–1196, 2014.
Daniel D Lee and H Sebastian Seung. Learning the parts ofobjects by non-negative matrix factorization. Nature, Vol.
401, No. 6755, pp. 788–791, 1999.
Daniel D Lee and H Sebastian Seung. Algorithms for nonnegative matrix factorization. In Advances in neural information processing systems, pp. 556–562, 2001.
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang,and Huan Liu. Attributed network embedding for learning
in a dynamic environment. arXiv:1706.01860, 2017.
Peter V Marsden. Homogeneity in confiding relations. Social networks, Vol. 10, No. 1, pp. 57–76, 1988.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeﬀrey Dean.
Eﬃcient estimation of word representations in vector space.
arXiv:1301.3781, 2013.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado,and Jeﬀ Dean. Distributed representations of words andphrases and their compositionality. In Advances in neural
information processing systems, pp. 3111–3119, 2013.
Bryan Perozzi, Rami Al-Rfou, and Steven 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.
[15] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, Vol.
290, No. 5500, pp. 2323–2326, 2000.
[16] Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high-dimensional data. In Proceedings of the 25th International Conference on World Wide
Web, pp. 287–297, 2016.
[17] Jian Tang, Meng Qu, and Qiaozhu Mei. Pte: Predictive
text embedding through large-scale heterogeneous text networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1165–1174, 2015.
[18] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun
Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International
Conference on World Wide Web, pp. 1067–1077, 2015.
[19] Joshua B Tenenbaum, Vin De Silva, and John C Langford.
A global geometric framework for nonlinear dimensionality
reduction. science, Vol. 290, No. 5500, pp. 2319–2323, 2000.
[20] Hanghang Tong, Spiros Papadimitriou, Jimeng Sun,
Philip S Yu, and Christos Faloutsos. Colibri: fast mining oflarge static and dynamic graphs. In Proceedings of the 14th
ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 686–694, 2008.
[21] Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu,
and Shiqiang Yang. Community preserving network embedding. In AAAI, pp. 203–209, 2017.
[22] Yuto Yamaguchi, Christos Faloutsos, and Hiroyuki Kitagawa. Omni-prop: Seamless node classification on arbitrarylabel correlation. In AAAI, pp. 3122–3128, 2015.
[23] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and
Edward Y Chang. Network representation learning withrich text information. In IJCAI, pp. 2111–2117, 2015.
[24] Jaewon Yang, Julian McAuley, and Jure Leskovec. Community detection in networks with node attributes. In 2013
IEEE 13th International Conference on Data Mining, pp.
1151–1156, 2013.
[25] Shenghuo Zhu, Kai Yu, Yun Chi, and Yihong Gong. Combining content and link for classification using matrix factorization. In Proceedings of the 30th annual international
ACM SIGIR conference on Research and development in
information retrieval, pp. 487–494, 2007.