DEIM2021 A31-2

時系列グラフを活用する着目ノードに特化したリンク予測
山口

寛人†

前川

政司†

佐々木

勇和†

鬼塚

真†

† 大阪大学情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{yamaguchi.hiroto,maekawa.seiji,sasaki,onizuka}@ist.osaka-u.ac.jp
あらましグラフのリンク予測は，Web 広告の推薦や消費者の購買予測など幅広い分野で利用されている．中でも，

SNS 上で特定の企業アカウント (ノード) に対して将来のリンクを予測し，フォロワーの拡大を目指すというユース
ケースが知られている．しかし，既存のリンク予測手法はグラフ中の全リンクを予測することを目的としている．そのため，グラフ中のリンクを均等に扱って学習しており，特定の企業アカウントのリンク予測のようなユースケース
においては十分な精度が期待できない．したがって，本稿では特定のノードに特化したリンク予測手法を提案する．
提案手法では，予測対象のノードの時系列的なグラフ構造の変化情報を利用するとともに，予測対象のノードに特化した学習を行うためのリンクのサンプリングとロス関数の設計を行うことで，特定の 1 ノードに対するリンク予測精度向上を図る．実験では，特定の 1 ノードに対するリンク予測精度の評価を行う．これにより，予測対象のノードに特化した学習を行うことで特定の 1 ノードに対するリンク予測精度が向上することを示した．
キーワード リンク予測，時系列グラフ，グラフマイニング
学習モデルが数多く提案されている [5, 6, 9–13]．これらの手

1 はじめにグラフはノードと呼ばれる頂点とリンクと呼ばれる辺によってノード間のつながりを表現するデータ構造であり，社会学
や生物学，コンピュータ科学など幅広い領域で用いられている [1]．このグラフを用いて表されるデータの例として，ソーシャルネットワーク [1]，消費者の購買履歴 [2]，道路交通ネッ
トワーク [3] などが挙げられる．このようなグラフからコミュ
ニティを抽出するクラスタリングやノードを分類するクラシ
フィケーション，将来のリンクを予測するリンク予測などのグ
ラフ解析は様々なアプリケーションに利用することが可能であり，幅広く研究が行われている [4–6]．中でも，リンク予測はSNS 上の広告の推薦 [7] や将来の消費者の購買予測 [2]，道路の劣化予測 [3] などに利用可能であり，広く研究が行われている．実際に SNS 上の企業アカウントのフォロワー拡大を目的として，ソーシャルネットワーク上の企業アカウントに対して将来のリンクを予測し，その企業アカウントをフォローする確率が高いユーザーに対して企業アカウントのフォローを推薦するといったような SNS ビジネスが知られている [8]．
このようなリンク予測には 2 種類の応用例が考えられる．一つ目は，道路の劣化予測のようにグラフ全体のリンク予測が必要なものである．この場合，任意の 2 ノード間のリンクの存在を予測するために，既知のグラフのリンクを均等に学習する必要がある．二つ目は，前述した SNS 上の企業アカウントのフォ
ロー推薦のように特定の 1 ノードに対してリンクを予測するものである．この場合，特定のノードのリンクについて予測を行う必要があるが，その他のリンクについては予測する必要はな
い．そのため，既知のグラフのリンクを均等に学習する必要はなく，特定のノードのリンク予測に特化した学習が必要である．
既存手法では，グラフ全体のリンク予測を目的とした深層法はグラフ全体の構造情報や属性情報を均等に学習することでリンク予測を行う．これらの手法では，jaccard 係数 [14] やAdamic adar [15] など既知のグラフ構造からノード間の類似度を表す指標に基づいて予測を行うヒューリスティックな方法に比べて高精度なリンク予測が可能である．中でも，時系列グラフを活用したリンク予測手法 [11–13] ではグラフ構造の時系列
変化の傾向も学習することが可能であり，静的なグラフのみからリンクを予測手法と比べても高精度なリンク予測が可能であることが知られている．一方で，既存手法を特定の 1 ノードのリンク予測に適用する場合には十分な予測精度を期待できない．
既存手法はグラフ中の任意のノード間のリンクに対する予測精度を上昇させるために，グラフ中のリンクを均等に学習しているため，特定の 1 ノードのリンク予測に対しては十分な精度が期待できない．したがって，1 ノードのリンク予測においては，
特定の 1 ノードに特化したモデルの学習を行う必要がある．
本稿では，時系列グラフを活用する特定の 1 ノードに特化したリンク予測手法を提案する．以降では，この予測対象となる

1 ノードを着目ノードと呼ぶ．提案手法では，着目ノードのリンク予測に特化した学習を行うために，着目ノード近傍のグラフ構造を重点的に学習するようにリンクのサンプリングを行う．
さらに，着目ノードからの距離が近いリンクほど着目ノードのグラフ構造に与える影響が大きくなると考えられるため，サン
プリングしたリンクに対して着目ノードからの距離に応じて重み付け学習を行う．これにより，着目ノード近傍のグラフ構造をより重視したリンク予測モデルの学習を実現する．
実験では，提案手法の着目ノードのリンク予測精度を既存手法と比較する．これにより，着目ノード近傍のグラフ構造をより重視してリンク予測モデルを学習することで着目ノードのリ
ンク予測精度が向上することを確認した．また，提案手法のサ
ンプリングに用いるパラメータを変化させてリンク予測精度を

入力

提案手法

1

出力

1

h：2
：着目ノード

…

…

…

t

1
t

t

t+1

ランダムウォークによりリンクをサンプリング
ランダムウォークの始点とするノードを決定着⽬ノードからの距離に応じて重み付き学習図 1: モデル概要図．提案手法は，入力として時刻 t までの時系列グラフと着目ノード，学習の対象とするリンクのサンプリングに関するパラメー
タ h を入力し，時刻 t + 1 のおける着目ノードとその他の任意のノードとのリンクの存在を予測する．提案手法は，ランダムウォークの始点とするノードを決定するステップとランダムウォークにより学習の対象とするリンクのサンプリングを行うステップ，サンプリングした
リンクに対し重み付き学習を行うステップの 3 つのステップからなる．図は h = 1 の場合の例を示している．この場合，提案手法では，はじめに着目ノードから 1 ホップのノードをランダムウォークの始点として決定する．その後，ランダムウォークによりリンクをサンプリン
グすることで着目ノード近傍のグラフ構造を重点的にサンプリングする．最後に，サンプリングしてきたリンクを着目ノードからの距離に応じて重み付けしたロス関数を用いてモデルを学習する．

測定することで，着目ノードのリンク予測において有効なリン

うなリンクのサンプリングとロス関数の設計を行う．リンクのクのサンプリング方法を確認した．

サンプリングでは，着目ノードから h ホップ先までのノードを

本稿の構成は以下の通りである．2 章で提案手法について詳始点とするランダムウォークで得られるリンクを学習の対象と細に述べた後，3 章で実験結果を示し，考察を行う．また，4

してサンプリングを行う．これにより，着目ノードから h ホッ章では既存のリンク予測に用いられる関連研究を紹介する．最プまでのグラフ構造をより重視したモデルの学習が可能とな

後に，5 章で結論を述べる．

る．さらに，着目ノードから h ホップまでのノードをランダムウォークの始点としてリンクをサンプリングすることで，着目2 提案手法ノードから h ホップまでのグラフ構造に限定することなく，グ

時系列グラフを活用する着目ノードに特化したリンク予測手法を提案する．提案手法の概要図を図 1 に示す．提案手法は，入力として時刻 t までの時系列グラフと着目ノード，学習の対象とするリンクのサンプリングに関するパラメータ h を入力
し，時刻 t + 1 のおける着目ノードとその他の任意のノードとのリンクの存在を予測する．提案手法は，ランダムウォークの始点とするノードを決定するステップとランダムウォークにより学習の対象とするリンクのサンプリングを行うステップ，サ

ラフ全体の構造についても考慮した学習が可能である．さらに，
サンプリングしてきたリンクの中でも着目ノードからの距離が近いリンクほど着目ノードのグラフ構造に与える影響が大きくなると考えられるため，提案手法ではサンプリングしてきたリンクを着目ノードからの距離に応じた重み付けをして学習を行うロス関数を設計する．提案手法では，着目ノードのリンク予測において適切な重み付けを検証するために以下の 3 つの重み付けした binary cross entropy loss を導入する．

ンプリングしたリンクに対し重み付き学習を行うステップの 3
つのステップからなる．

Ld =

T
∑
∑

(−

t=1 v∈V t
sub

2. 1 問 題 定 義る．また，Gt = (V, E t ) はタイムステップ t のグラフを表す．

V = {v1 , . . . , vn } はノードセットを表し，既存手法の問題定Lroot =

G = {G , ..., G } とリンクを予測する特定の 1 ノードを入力と2. 2 提案手法のアプローチ
提案手法では，着目ノードのリンク予測に特化した学習を行うために，着目ノード近傍のグラフ構造を重点的に学習するよ(1)log(1 − êv,u′ ))min(dv , du ) + 1∑√

u∈Γt (v)log(êv,u )min(dtv , dtu ) + 1

log(1 − êv,u′ )√− wn ·)min(dtv , dtu ) + 1
u′ ∈P t (v)Lnor =

T∑∑(−

t=1 v∈V t

sub

して，タイムステップ t + 1 のおける着目ノードとその他の任意のノードとのリンクの存在を予測する．

log(êv,u )min(dv , du ) + 1∑

ぞれのリンクは eti,j = (i, j) ∈ E t と表す．着目ノードは vf と
t

(−

sub

E t ⊆ V × V はタイムステップ t のリンクセットを表し，それ

1

T
∑
∑
t=1 v∈V t

義と同様にノードセットは時刻変化しないものとする [12]．

表す．本稿では，タイムステップ 1 〜 t までの時系列グラフ∑
u′ ∈P t (v)は G = {G , ..., G } で表され，T はタイムステップ数とすT1u∈Γt (v)− wn ·

はじめに，提案手法が扱う問題を定義する．時系列グラフ∑− wn ·(2)∑log(êv,u )min(dtv ,dtu )u∈Γt (v) max(min(dta ,dt )) + 1
b
a,b

∑

log(1 − êv,u′ )min(dtv ,dtu )u′ ∈P t (v) max(min(dta ,dt )) + 1
a,b

(3)

)

b

t
ここで，Vsubは着目ノードから h ホップのサブグラフに含まれるノードセットを表し，Γt (v) はタイムステップ t におけるノード v からのランダムウォークでノード v と共起するノードセットを返す関数である．êi,j はノード i とノード j 間のリ

Algorithm 1 リンクのサンプリングアルゴリズム

ンクの存在確率の出力結果を表している．また，P t (v) はタイ

Require: Gt , vf , h

ムステップ t においてノード v とリンクを持っていないノード

Ensure: Γt , P tのネガティブサンプリング分布を表し，wn はネガティブサン# Search start nodes for random walks

プリングレートを表している．di はノード i の着目ノードからt
1: Vsub= {}の距離を表す．Ld は単純に着目ノードからの距離をそのまま

2: for v = 1 to n do

重みとして扱うロス関数である．Lroot は着目ノードから離れたリンクのロスを過剰に減少させないようにするために，距離による重みに対して平方根をとったロス関数である．Lnor は，
単純に着目ノードからの距離をそのまま重みとして扱う場合に

t
t ∪v
Vsub
= Vsub4:

end if5:

6: end fort |7: Γt = [ ] ∗ |Vsub

は，距離によって過剰に重み付けしてしまう可能性があるため，全体的な距離による重みを和らげるためにサンプリングしてき

if dtv <= h then3:

# Random walk samplingt |8: walks = [ ] ∗ |Vsub

た各リンクの着目ノードからの距離を正規化したものを重みと9: for counter = 1 to num walks do

するロス関数である．以上のアプローチにより，着目ノードか

10:

t )
random shuf f le(Vsub11:tfor v in Vsubdo

らの距離がより近いグラフ構造を重視したリンク予測モデルの学習を行う．

walks[v] = walks[v] ∪ random walk(start node = v)

12:

end for13:

2. 3 提案手法アルゴリズム
提案手法では，既存の時系列グラフのリンク予測手法で用い14: end fort
15: for v in VsubdoΓt [v] = [(v, random sample(walks)) for i = 1 to sam-

16:

られているモデルアーキテクチャを利用して，着目ノード近傍
をより重点的に学習するためのリンクのサンプリングとロス関

ple size]
17: end for# Negative sampling数を用いてモデルの学習を行う．具体的なリンクのサンプリン
グアルゴリズムをアルゴリズム 1 に示す．はじめに提案手法では，入力のパラメータ h に基づいて着目ノードから h ホップ
先までのノードを探索し，リンクをサンプリングしてくるためt
18: for v in Vsubdo

19:

while len(P t [v]) < sample size do do20:

u = ramdom sample(range(n))

21:

if u not in walks[v] thenのランダムウォークの始点とする．
（1 − 5 行目）その後，各始22:点からのランダムウォークで共起したノードとのリンクをポジ

23:

end ifティブリンクとしてサンプリングする．
（8 − 17 行目）また，各24:

end while

始点のランダムウォークで共起しなかったノードの中からラン

25: end forダムでサンプリングしてきたものをネガティブリンクとしてサP t [v] = P t [v] ∪ u

26: return Γt , P t

ンプリングを行う．
（18 − 25 行目）そして，これらのサンプリングされたリンクに対して，既存の時系列グラフのリンク予測

履歴を表したグラフである．本実験では，最も送受信履歴の多手法で用いられているモデルアーキテクチャを利用し，2. 2 節

かった年の半年間の履歴を１ヶ月ごとに区切り，6 タイムステッ

で紹介した 3 つのロス関数のいずれかを用いて学習を行う．

プの時系列グラフを作成した．

3 実

験

3. 1. 2 実 験 設 定
本実験では，最新のタイムステップを除いたグラフを訓練

本稿では，以下の二つの実験を行う．はじめに，提案手法のデータとし，最新のグラフの着目ノードに対するリンクを予着目ノードの予測精度と既存手法の予測精度を比較する．これ測する．着目ノードは訓練データの中で最も合計のエッジ数がにより，着目ノード近傍のグラフ構造をより重視してモデルを大きいものを着目ノードに設定する．また，静的グラフのリ学習する提案手法の有効性を確認する．次に，提案手法のサン

ンク予測手法の精度評価では，データセットの情報量を保つた

プリングに用いるパラメータを変化させてリンク予測精度を測めに各タイムステップで出現するノードとエッジを一つのグラ定する．これにより，提案手法のパラメータが着目ノードのリフに集約したグラフを用いて実験を行う．評価指標にはリンク

ンク予測精度に与える影響を確認する．

予測で一般的に用いられている Area Under the ROC Curve

3. 1 精 度 評 価
3. 1. 1 データセット(AUC) を用いる．また，提案手法は既存手法で最も高精度に時系列グラフのリンク予測を行うことができる DySAT のモデ
ルアーキテクチャを利用する．

本実験で用いるデータセットについての説明を以下に示す．

Enron 1 ：ヨーロッパの研究機関における電子メールの送受信

3. 1. 3 比 較 手 法
我々は提案手法のリンク予測精度を以下の 5 手法と比較する．

•
1：http://networkrepository.com/ia-enron-email-dynamic.php

baseline：各手法の評価のための基準として設定した手データセット

Enronbaseline Jaccard node2vec SEAL DySAT 提案手法 Ld
0.616

0.838

0.778

0.701

0.882

提案手法 Lroot

提案手法 Lnor

0.922

0.914

0.926

表 1: 着目ノードのリンク予測結果．提案手法 Ld ，提案手法 Lroot ， 提案手法 Lnor はそれぞれ式 1, 式 2, 式 3 をを用いた場合の提案手法のことを示している．また，提案手法のパラメータ h は h = 2 に設定した場合の結果を示す．

データセット名

ノード数

エッジ数

タイムステップ数

Enron

43661

16490〜44440

6

0.95
0.9
0.85

ある．エッジ数は全タイムステップでのエッジ数の値域を表して
いる．

AUC

表 2: データセット．ノード数は全タイムステップで累計のノード数で

0.8
0.75
0.7
0.65

法である．予測対象となるタイムステップのグラフ構造は直近

0.6
1hop

2hop

3hop

いう観点から，直近のタイムステップの着目ノードのリンクを予測結果とする手法である．

•

jaccard 係数：2 ノード間で共通する隣接ノードの割合

4hop

5hop

パラメータ hのタイムステップのグラフ構造と類似している可能性が高いと
L_d

L_rootL_nor

図 2: パラメータ h による着目ノードのリンク予測精度の変化. Ld ，

Lroot ，Lnor のロス関数を用いてそれぞれで h = 1, 2, 3, 4, 5 に設定した場合のリンク予測精度を図に示している．

が多いほどそのノード間でリンクを持ちやすいだろうという考えに基づき，2 ノード間の共通隣接ノードの割合をリンクの存在確率のスコアとして扱うリンク予測手法である．

3. 2 パラメータセンシティビティ

node2vec：深層学習を用いた静的グラフのグラフ埋め提案手法では，ランダムウォークの始点とするノードとして込み手法である．ランダムウォークによってグラフの隣接情報

着目ノードからの距離が h ホップ以内であるノードを選択する．

をサンプリングし，このランダムウォークを訓練データとして

本節では，このパラメータ h を変更することにより提案手法

ノードの表現ベクトルを取得する．

の着目ノードのリンク予測精度に与える影響を確認する．Ld ，•SEAL：深層学習を用いた静的グラフのリンク予測手法

Lroot ，Lnor のロス関数を用いてそれぞれで h = 1, 2, 3, 4, 5 にである．任意の 2 ノードから h ホップのサブグラフを取得す設定した場合のリンク予測精度を図 2 に示す．図 2 からどのロることでグラフのサンプリングを行い，そのサブグラフから

ス関数を用いた場合にも h = 2 とした場合に最も高い精度と2 ノード間にリンクが存在するかを予測するグラフニューラル

なっていることが確認できる．このことから，着目ノードからネットワークモデルを学習する．

1 ホップのノードを始点とした場合では十分に近傍のグラフ構•

DySAT：深層学習を用いた時系列グラフのリンク予測手造をサンプリングすることができず，精度が向上していないと法である．構造と時系列の二次元で自己注意ネットワークを構考えられる．また，着目ノードから 3 ホップ以上のノードをラ成することで，構造的特徴と時系列変化の両方を考慮したリン

ンダムウォークに始点とした場合には着目ノードから離れたリ

ク予測が可能である．この手法は，既存の時系列グラフを活用

ンクを多くサンプリングしてしまうため，着目ノードの近傍のしたリンク予測モデルの中でも最も高精度なリンク予測が可能

グラフ構造を十分に重視した学習を行うことができず精度が低である．

下したと考えられる．

•

3. 1. 4 実 験 結 果

4 関連研究本実験の結果を表 1 に示す．表 1 から，3 つの提案手法全て
が既存手法と比較して高精度な予測を達成していることが確認

リンク予測では既知または観測されたリンクに基づいて，将できる．このことから，着目ノードのリンク予測において着目

来または未観測のリンクの存在を予測する．リンク予想に利用

ノード近傍のグラフ構造を重視してモデルを学習する提案手法

可能な手法は数多く提案されており，これらの手法は，（1）静の有効性が確認できる．また，3 つの提案手法の中ではロス関数的なグラフのみを用いるリンク予測手法と（2）時系列グラフ

Ld を用いた手法が最も高精度な予測結果となっている．Lrootを活用したリンク予測手法の二つのアプローチに分類すること

や Lnor では着目ノードからの距離による重みに対して平方根ができる．

をとる操作や正規化を行うことにより，距離による重み付けを和らげる処理になっているため，十分に着目ノード近傍のグラフ構造を重視して学習できておらず，Ld を用いた提案手法と比較して精度が低下しているものと考えられる．また，時系列
グラフのリンク予測手法である DySAT は他の静的グラフのリンク予測手法に比べて高精度な予測結果となっており，時系列
グラフを活用することの有効性が窺える．

4. 1 静的グラフのリンク予測
初期の静的グラフのリンク予測では common neighbor [16] やjaccard 係数 [14]， Adamic adar [15]，PageRank [17]，SimRank [18] など，既知のグラフ構造からノード間の類似度を示
すような指標を計算し，それに基づいてリンクの存在を判断するヒューリスティックな手法が用いられていた．これらの指Name

FormulaOrdercommon neighbors [16] |Γ(x) ∩ Γ(y)|Jaccard [14]Adamic-Adar [15]|Γ(x)∩Γ(y)||Γ(x)∪Γ(y)|∑1z∈Γ(x)∩Γ(y) log|Γ(z)|PageRank [17][πx ]y∑+ [πy ]x ∑SimRank [18]γ(x)b∈Γ(y) score(a,b)|Γ(x)|·|Γ(y)|a∈Γ(x)

構造的特徴と属性的特徴からリンクの存在を二値分類問題としﬁrstて解く手法である．これらの手法は，グラフ埋め込み手法を用

ﬁrst

いたリンク予測と比較してもより高精度な予測が可能であるこ

secondとが知られている．

high
high

表 3: ノード x, y 間の類似度を示す指標．Γ(x) はノード x の近傍ノードセットを表し，[πx ]y はノード x からランダムウォークを行っ

4. 2 時系列グラフのリンク予測
グラフの時系列変化を学習することによる精度向上を目的として，時系列グラフを活用したリンク予測手法の研究が進んでた際の y の定常分布確率を表す．SimRank のスコアは表中の式

いる [11–13]．これらの手法では，時系列グラフを活用するこを再起的に計算することにより算出される．Order は各指標がとで時系列的なグラフ構造の変化を捉えた上でリンク予測を行

ノード x, y から何ホップ先までの情報を考慮しているかを表しうことが可能である．そのため，静的グラフのみを用いたリンている．また，score(a, b) はノード a, b 間の SimRank の値をク予測手法と比較して高精度な予測を行うことが可能である．

表している．Order はそれぞれの指標が何ホップ先までの隣接

Dyn2AERNN [11] では，時系列グラフの隣接情報を LSTM で情報を考慮しているかを示している．

学習し，次の時刻のグラフを再現する学習を行う．これにより，標の詳細を表 3 に示す．common neighbor [16] や jaccard 係

各ノードの時系列変化の傾向を捉えた上でリンクを予測してい数 [14] は 2 ノード間の共通隣接ノードに着目した類似度指標でる．また DySAT [12] では，構造的な自己注意ネットワークとある．共通の隣接ノードが多いほどそのノード間でリンクを持

時間的な自己注意ネットワークを二次元的に組み合わせること

ちやすいという考えに基づき，common neighbor では 2 ノー

により，各時刻の構造的特徴と時系列的な構造変化の特徴の両ド間の共通隣接ノードの数を，jaccard 係数では共通隣接ノー方を考慮してリンク予測を行っている．Evolve GCN [13] はグ

ドの割合をリンクの存在確率のスコアとして用いる手法である．

ラフ畳み込みネットワークを時系列グラフへ拡張した手法であまた，Adamic-Adar [15] は上記の 2 つの共通隣接指標を改良る．この手法はグラフ埋め込み手法であり，このグラフ埋め込

した類似度指標である．共通隣接ノードの中でもその他のノーみを利用してリンク予測が可能である．しかし，これらの既存ドとあまり隣接していないノードを重く評価するよう重み付け手法は全てグラフ中の全リンクを予測することを目的とした手された指標である．さらに，PageRank と SimRank はグラフ法である．そのため，グラフ中のリンクを均等に学習しており，全体の構造を考慮した類似度指標である．PageRank [17] はグ

着目ノードのリンク予測に適用する場合には十分に精度が期待

ラフ中のノードをランダムに遷移するランダムウォークを行っできない．したがって，着目ノードのリンク予測においては，た場合に，ランダムウォークがあるノードに定常的に訪れる確着目ノードのリンク予測に特化したモデルの学習を行う必要が率を示す指標である．ノード x からランダムウォークを行ったある．

場合に，あるノード y に訪れる確率が高いほどノード x と y は類似していることを示す．SimRank [18] は類似度の高いノードの隣接ノードは類似したノードであるという考えに基づいた類似度指標である．あるノード x, y の隣接ノード間の類似度の高いほどノード x, y の類似度も高くなるように類似度が再帰的に計算される．
しかし近年では，深層学習を用いたグラフ埋め込み手法が数多く提案されており，これらの手法で得られたグラフ埋め込みがリンク予測に利用される [5, 9, 10]．node2vec [9] はランダムウォークによってグラフの隣接情報をサンプリングし，このランダムウォークを訓練データとしてノードの表現ベクトルを取得する．グラフ畳み込みネットワーク [5] は，画像処理分野で広く用いられている畳み込みネットワークをグラフに拡張した手法である．隣接ノードの属性を伝搬させることで構造的に類似するノードが類似する表現ベクトルを持つようにグラフ埋め込みを学習する．VGAE [10] はエンコーダにグラフ畳み込み
ネットワークを用いており，デコーダでは内積を用いて下のグラフを復元するような学習を行う．これらの手法はヒューリス
ティックなリンク予測手法に比べて高精度なリンク予測が可能である．これらの手法に加えて End-to-End でリンク予測を行う手法も提案されている [6, 19]．これらの手法では，任意の 2ノードから h ホップのサブグラフを抽出し，このサブグラフの5 終わりに本稿では，着目ノードに特化したリンク予測手法を提案した．
提案手法では，学習で利用できる情報量を増やすために，時系列グラフを活用した．また，着目ノードの構造変化が近傍のグ
ラフ構造から受ける影響を適切に学習するために，着目ノードのリンクとその近傍のリンクを距離に応じて重み付けしたロス関数を設計し，既存のモデルアーキテクチャに適用した．これにより，提案手法が着目ノードのリンク予測において最も高精度な予測が可能であることを確認した．今後の課題としては，異なる着目ノードを設定した場合のリンク予測精度の測定や複数のデータセットでの実験を行うことにより，提案手法の汎用性を確かめる必要がある．また，リンク予測対象を着目ノードに限定することを活かして効率的に学習を行うことのできるモ
デルアーキテクチャの設計が挙げられる．

謝辞

本研究は JSPS 科研費 JP20H00583 の助成を受けたものです.

文

献[1] Santo Fortunato. Community detection in graphs. The
Physics Reports, Vol. 486, No. 3, pp. 75 – 174, 2010.
[2] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.
Graph evolution: Densiﬁcation and shrinking diameters.
The TKDD, Vol. 1, No. 1, p. 2–es, 2007.
[3] Jia Li, Zhichao Han, Hong Cheng, Jiao Su, Pengyun Wang,
Jianfeng Zhang, and Lujia Pan. Predicting path failure intime-evolving graphs. In Proceedings of the SIGKDD, p.
1279–1289, 2019.
[4] Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J.
Schweiger. Scan: A structural clustering algorithm for networks. In Proceedings of the SIGKDD, p. 824–833, 2007.
[5] Thomas N. Kipf and Max Welling. Semi-supervised classiﬁcation with graph convolutional networks. In Proceedingsof the ICLR, 2017.
[6] Muhan Zhang and Yixin Chen. Link prediction based ongraph neural networks. In Proceedings of the NeurIPS, pp.
5165–5175, 2018.
[7] Xin Sun, Zenghui Song, Junyu Dong, Yongbo Yu, Claudia
Plant, and Christian Böhm. Network structure and transfer
behaviors embedding via deep prediction model. pp. 5041–
5048, 2019.
[8] Ashish Kumar, Ram Bezawada, Rishika Rishika, Ramkumar Janakiraman, and P.K. Kannan. From social to sale:
The eﬀects of ﬁrm-generated content in social media on customer behavior. The Journal of Marketing, Vol. 80, No. 1,
pp. 7–25, 2016.
[9] Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the SIGKDD,
p. 855–864, 2016.
[10] Thomas N. Kipf and Max Welling. Variational graph autoencoders. arXiv preprint arXiv:1611.07308, 2016.
[11] Palash Goyal, Sujit Rokka Chhetri, and Arquimedes
Canedo. dyngraph2vec: Capturing network dynamics using
dynamic graph representation learning. The KnowledgeBased Systems, Vol. 187, p. 104816, 2020.
[12] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, andHao Yang. Dysat: Deep neural representation learning on
dynamic graphs via self-attention networks. In Proceedingsof the WSDM, p. 519–527, 2020.
[13] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma,
Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B.
Schardl, and Charles E. Leiserson. EvolveGCN: Evolving
graph convolutional networks for dynamic graphs. In Proceedings of the AAAI, 2020.
[14] Jaccard Paul. The distribution of the ﬂora in the alpine
zone. The NEW PHYTOLOGIST, Vol. 11, pp. 37–50, 1912.
[15] Adamic Lada, A and Adar Eytan. Friends and neighborson the web. The Social Networks, Vol. 25, No. 3, pp. 211 –
230, 2003.
[16] M. E. J. Newman. Clustering and preferential attachment
in growing networks. The Physical Review E, Vol. 64, No. 2,
p. 025102, 2001.
[17] Sergey Brin and Lawrence Page. The anatomy of a largescale hypertextual web search engine. The Computer Networks, Vol. 30, No. 1, pp. 107–117, 1998.
[18] Glen Jeh and Jennifer Widom. Simrank: A measureof structural-context similarity.
In Proceedings of the
SIGKDD, p. 538–543. Association for Computing Machinery, 2002.
[19] Zheyi Liu, Darong Lai, Chuanyou Li, and Meng Wang. Feature fusion based subgraph classiﬁcation for link prediction.
In Proceedings of the CIKM, p. 985–994, 2020.