DEIM Forum 2023 1b-8-2

動的グラフを対象としたリンク予測手法の動向調査
中西

宏和†

前川

政司†

佐々木

勇和†

鬼塚

真†

† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{nakanishi.hirokazu,maekawa.seiji,sasaki,onizuka}@ist.osaka-u.ac.jp
あらまし

動的グラフは多くの実世界における動的なシステムを表現することができる．動的グラフにおいて，リンクの時間的かつ構造的な近傍構造を捉えることは，将来のリンクの発生を予測するために必要不可欠である．近年，動的グラフにおける近傍構造を捉えることを目的とした手法が数多く提案されている．本論文では，動的グラフを対象としたリンク予測手法の包括的な概観を提供する. 我々は，最先端のリンク予測手法を，代表的な Message Passing(MP) ベース, Walk Aggregation (WA) ベース， ハイブリッド （MP+WA） の 3 つのカテゴリに分類し，これらの手法の利点欠点を明らかにする. また，既存の研究では評価軸として表現力に注目しているものが多いが，より広い視野でこの分野の調査を行うために，本論文では効率性の評価軸を追加して評価する．最後に，この分野で今後解くべき課題と研究の方向性を示す．
キーワード 動的グラフ，グラフニューラルネットワーク，リンク予測
もしくは両方を捉えることで高いリンク予測精度を達成するこ

1 はじめに動的グラフは現実世界の様々な複雑なシステムを抽象化することができるため，幅広く活用されている．動的グラフは相互作用する実体としてのノード，相互作用自体としてのリンク，相互作用がいつ起こるかを示すタイムスタンプを持つ．この動的グラフを対象とした重要なタスクに，リンク予測がある．これは，動的グラフが時間の経過とともに変化する性質を考慮し，将来のイベントの発生を予測するタスクである．例えば，

SNS ネットワークにおける友人推薦 [1] や将来の消費者の購買予測 [2] などが応用事例として挙げられる．
近年，グラフデータを分析するためにグラフニューラルネッ
トワーク（GNN） [3–5] が登場している．GNN は，注目ノードの近傍情報を集約することで，さまざまな応用事例に適用可能な embedding を生成することができる．しかし，GNN は静的なグラフにおいて大きな成功を収めたが，動的なグラフにおいては未開拓な部分が多い．それは，既存の静的グラフを対象とした GNN の手法を動的なグラフにそのまま適用することが効果的でないためである [6]．
最近，動的なグラフに対して効果的な手法が提案され始めている．まず，動的グラフをある一定の時間間隔で表現されるグラフのスナップショットとして扱うもの [7–9] がある．このようなグラフは離散時間動的グラフ（DTDG：Discrete Time

Dynamic Graphs）と呼ばれ，このグラフを扱う手法では，動的グラフをある一定の時間間隔により表現するため，この時間間隔よりも細かい情報が欠落する．そのため，より先進的な方法に，相互作用する 2 ノードとそのタイムスタンプのシーケン
スを動的グラフとして表現する方法がある．このようなグラフ
は，連続時間動的グラフ（CTDG：Continuous Time Dynamic

Graphs）と呼ばれ，このグラフを扱う手法 [6, 10–17] では，属性情報のほか，時間的パターンと構造的パターンのどちらか，とができる．このように CTDG を用いた動的リンク予測手法が最近広く注目を集めている．しかし，我々の知る限り，これら手法を包括的にまとめた研究は存在しない．
本論文では，近年の研究の動向を踏まえた動的グラフを対象とするリンク予測手法の包括的な概観を提供する．我々は，最先端のリンク予測手法を，リンク予測へのアプローチの方法により， Message Passing （MP）ベース [6, 10–13], Walk

Aggregation(WA) ベース [14, 15]，ハイブリッド (MP+WA)[16, 17] ベースの３つのカテゴリに分類する．MP ベースは，リンクの発生毎に近傍ノードへノード情報とその相互作用の情報を伝搬することで動的グラフにおけるグラフの時間的な変化を捉えたノード embedding を生成し，これを用いてリンクの発生傾向を捉える．WA ベースは，リンク予測対象の 2 ノードを始点とする多数ウォークから相対位置情報を抽出することで構造的パターンを捉えたリンク embedding を生成し，リンクの予測を行う方法である．ハイブリッドは，MP ベースと WA
ベースの方法を組み合わせることにより，高精度化を達成している．これらカテゴリごとや各手法ごとに，それぞれの関係性や利点・欠点を明らかにする．MP ベースと WA ベースについて，それぞれ共通する基本アーキテクチャについてそれぞれ特定し，一般的な定式化を行う．さらに，表現力と効率性の２つの観点をベースに，複数の項目について分析することで，各手法が持つ特性を明らかにする．これらの分析を踏まえて，当該分野における現状の課題と今後の方向性について言及する．
本稿の構成は以下の通りである． 2 章で事前準備を行い， 3
章で各手法について詳細に述べた後， 4 章でそれら手法を２つの観点で分析する．また， 5 章では今後のこの分野における課
題と方向性について述べる．最後に， 6 章で結論を述べる．

属性情報

時間的パターン

ベース

手法名

MP ベースTGAT [6]✓✓TGN [10]✓✓✓APAN [11]

✓

✓

✓

△

TGL [12]

✓

✓

✓

○

TPGNN [13]

✓

✓

✓

✓

△

CAW-N [14]✓✓NeurTWs [15]✓✓PINT [16]✓

NAT [17]✓WA ベース
ハイブリッド

低次近傍

高次近傍

✓

周期

非周期

構造的パターン

処理速度

使用記憶領域

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

○

表 1: 各手法の分類と 2 つの観点による分析．表現力は属性情報と時間的パターン，構造的パターンの３つに分解し，効率性は処理速度と使用記
憶領域の２つに分解する．属性情報は低次近傍と高次近傍に，時間的パターンは周期と非周期にさらに分解し，それぞれ捉えられていれば✓ をつけている．処理速度については，各論文内において実験により，各ベース方法において最も基本的な手法である TGN [10] およびCAW [14] に比べて処理速度の改善が確認でき，かつ，そのうち SOTA であるものには ○ ，SOTA ではないが改善が確認できるものには△をつけている．使用記憶領域については，記憶機構を用いていないもの，もしくは CSR 行列ベースのデータ構造を用いているものは使用
記憶領域がローコストであると考えられるために ✓ をつけている．

2. 3 リンク予測に利用されるグラフ特徴

2 事前準備

リンク予測タスクにおいて高い精度を実現するために，属性

ここでは，動的グラフやリンク予測，リンク予測に利用され情報と時間的パターン，構造的パターンの３つの情報を CTDGから抽出し，embedding に反映する必要がある．

るグラフ特徴の定義を行う．

属性情報．Message Passing ベースの GNN は，注目ノー2. 1 動的グラフ

ドの近傍の属性情報を集約することにより，汎用的なノード

動的グラフ中でも本論文で扱う CTDG は，相互作用する２embedding を生成する．ただし，これらの手法では 3-hop 以上

ノードとそのタイムスタンプのシーケンスとして表現される．

離れた属性情報を集約しようとすると，多くの場合 embedding

ノード集合を V ，タイムスタンプ集合を T とすると，CTDGが似通ってしまう過剰平滑が生じる [18]．ここで，注目ノード

E は以下の式により定義される．

から 2-hop 以内の属性情報を低次近傍属性情報，3-hop 以上のE = {(u1 , v1 , t1 ), (u2 , v2 , t2 ), . . . }属性情報を高次近傍属性情報と定義する．この高次近傍属性情(1)報を活用するためには，過剰平滑の課題を解決する必要がある．

ただし，ui , vi ∈ V は相互作用する 2 ノードを表し, ti ∈ T は

時間的パターン．動的グラフにおけるリンクの発生を長期的各相互作用の発生時刻を表し, t1 <= . . . を満たす．また，= t2 <な視点で観察したときに見られる，さまざまな時間的特性を時

データセットによっては各相互作用に属性情報がリンク属性と間的パターンと定義する．本稿では，時間的パターンを周期的して付与されている場合がある．例えば，掲示板ネットワーク

パターンと非周期的パターンに分けて考える．周期的パターンの Reddit データセット などは，編集内容のテキストデータとは，ある２ノード間で周期的に相互作用が発生するパターン

が 512 次元のベクトルに変換され，リンク属性として各相互作のことであり，E-メールのネットワークなどに頻繁に見られる．

用に付与されている．この場合，リンク属性の集合を E とする

非周期的パターンについては，ブラックフライデーには瞬時的と，属性付き CTDG Ee は以下の式により定義される．

に相互作用の発生頻度が全体的に増加するという瞬時性やある

1

動画が投稿日から日数が経過したことでアクセス数が減衰する

Ee = {(u1 , v1 , t1 , e1 ), (u2 , v2 , t2 , e2 ), . . . }(2)

ただし，ei ∈ E である．

2. 2 問題定義（リンク予測）

減衰性といったパターンを指す．
構造的パターン．ある制限された時間内に現れるリンクにより構成される連結サブグラフの類似パターンを構造的パターンと定義する．Message Passing ベースの手法では，属性情報の動 的 リ ン ク 予 測 は ，あ る 時 刻 t よ り 前 の 動 的 グ ラ フ

集約時に平均の計算を行うために注目ノードに対する相対的{(u′ , v ′ , t′ ) ∈ E|t′ < t} から時刻 t に ２ ノード間にリンク

な位置情報が失われ，構造的パターンを抽出することができな(u, v, t) が発生するかどうかを予測するタスクである．このタい [16]．構造的パターンはリンク予測を行う上で重要な情報でスクを高精度かつ高効率で予測することが目的である．以降，あるとされており [14]，後述の WA ベースの手法はこの情報をリンク予測対象である 2 ノードのことを注目ノード，リンクの捉えることを目的に手法が提案されている．構造的パターンのことを注目リンクと表現する．

代表的な例として，友人の友人は友人になりやすいという仮定を裏付ける Triadic Closure というサブグラフパターンなどが1：http://snap.stanford.edu/jodie/reddit.csv

ある．

CTDG
CTDG
(u1,v1,t1,e1)(u2,v2,t2,e2)
・
・
・
・
・
・
・
・
・
・

リンクの有無(u,v,t,e)

エンコーダ(Attention)

zu,zv

デコーダ
(MLP)

puv

0 or 1s(u,v,t,e)

記憶機構(RNN系列)(u1,v1,t1,e1)(u2,v2,t2,e2)
・
・
・
・
・
・
・
・
・
・

リンクの有無(u,v,t,e)

エンコーダ
(RNN)

zuv

デコーダ
(MLP)

puv

0 or 1I(u,v,t,e)
相対情報抽出機構

図 2: WA ベースのモデルアーキテクチャの概要図．リンクの発生に伴図 1: MP ベースのモデルアーキテクチャの概要図．リンクの発生に伴い

い相対情報抽出機構により構造的パターンを捉えた相対情報が算記憶機構により状態が更新される，エンコーダでは，注目リンクの出される．エンコーダでは，注目リンクの情報と相対情報が入力

情報とその時刻における状態が入力され，リンク予測対象の２ノーされ，注目する 2 ノードのリンクの embedding が出力される．デドの embedding が出力される．デコーダでは，その embedding

コーダでは，その embedding が入力され，最終的なリンクの有無が入力され，最終的なリンクの有無が出力される．なお，s は記憶機が出力される．なお，I は相対情報，zuv はノード u，v からなる

構が保持する状態のベクトル，zu はノード u のノード embedding

リンクの embedding，puv はノード u，v 間のリンクの発生確率，puv はノード u，v 間のリンクの発生確率の予測値である．

の予測値である．

生した場合，u と v に関する次のメッセージ mu (t),mv (t) が生

3 手法の分類
本章では，CTDG を対象とする動的リンク予測手法を 3 つに分類し，それぞれのベースとなる考え方について述べた後，各手法について詳細な説明を行う．なお，Neural Networks を成される．

muv (t) = (su (t− )||sv (t− )||Φ(t − t− )||euvt )(3)

mvu (t) = (sv (t− )||su (t− )||Φ(t − t− )||euvt )(4)用いた手法が支配的な精度を示しているので，本章で紹介する

ここで, || は concatenate を表し, sv (t) はノード v の時刻 t に手法は，Neural Networks を用いた手法に絞っている．本稿でおける状態である．sv 1(t− ) は時刻 t の直前の状態であり，初紹介する手法についての分類と表現能力と効率性の分析を表 1

期値 sv (0) にはノード属性かランダム値を用いる 2 ．Φ(·) は過に示す．

去の相互作用と現在の相互作用の時間差を入力とする関数であ3. 1 Message Passing ベース
概要．Message Passing（MP）ベースは，リンク発生毎に近傍ノードへ発生したリンクに関する情報を伝搬することで動的グラフにおけるグラフの時間的変化を捉えたノード embeddingを生成する手法である．MP ベースは，静的グラフにおいて成功している GCN [3] の考え方を動的グラフにも適用すること

り，identity function もしくは，Xu ら [6] が提案したタイムエ
ンコーディング関数が用いられる．euvt は時刻 t においてノー
ド u, v 間で発生した相互作用のリンク属性を表す．
時刻 t に同時に発生したをリンクの集合のうち，リンクにノード v を含んでいるものを J (v, t) と表す．リンクの発生時に，そのリンクに関わるノードの状態を系列モデルにより更新するために，メッセージの集約が次の式により行われる．

で，ノード embedding を獲得することを目的としている．相互作用に関する情報の伝播履歴を記憶しておくために，RNNm̄v (t) = MESAGG (mvu (t))(5)(v,u,t)∈J (v,t)などの系列モデルで構成される記憶機構を持ち，これにより時間的に変化する傾向をノード embedding に反映することがで

MESAGG 関数は集約関数であり，平均が広く用いられる．ノー

きる．このノード embedding は，リンク予測タスクだけでな

ド v の状態は，直前の自身の状態と生成した集約後のメッセー

く，動的クラス分類などのさまざまなタスクに活用可能である．

ジを用いて次の式により更新される．

MP ベースは，主に，記憶機構，エンコーダ，デコーダの 3

sv (t) = UPDT(sv (t− ), m̄v (t))つの構成要素からなり，その構成の概要は図 1 のように表され(6)

る．記憶機構は，過去のリンク発生履歴を要約する各ノードの

UPDT 関数には RNN や GRU などの系列モデルが用いられる．

状態を保持する．エンコーダは，注目 2 ノードの近傍情報と記

エンコーダ．エンコーダは，注目する 2 ノードに対して，憶機構の情報を集約することでノード embedding を生成する．

その近傍ノードの情報を集約することで，各ノード embed-

デコーダはリンク予測対象の 2 ノードの embedding を MLP

ding を生成する．時刻 t におけるノード v の時間的近傍をに入力することで最終的なリンクの有無を予測する．

N (v, t) = {(u, euvt′ , t′ )|∃(u, v, t′ ) ∈ E, t′ < t} という近傍ノー記憶機構．記憶機構は，過去のリンク発生履歴を要約する各

ドと，そのノードとの相互作用に付与されているリンク属性，

ノードの状態を保持する．リンクが発生すると，そのリンクにその発生時刻の３つにより構成されるものの集合と定義する．

関わるノードの状態が系列モデル（RNN [19], GRU [20] など）
により更新される．ある時刻 t にノード u,v 間に相互作用が発2：ノード属性が与えられないデータセットの場合は，ランダム値をノード属性として利用する．

記憶機構

手法

メモリ

[6, 10, 16] 自身のノード状態

保持内容

更新方法

RNN

高次近傍の抽出

メールボックス[11]

自身のノード状態

FIFO

k-hop メモリ[13]

k-hop 毎の自身ノード状態

RNN✓

k-hop 辞書メモリ[17]

自身のノードと k-hop 近傍の状態

RNN と FIFO✓

近傍問い合わせの有無✓

表 2: 各記憶機構についての比較表．保持内容とは，各記憶機構が各ノードごとに保持する内容のことを指す．更新方法は保持内容をどのように更新するかを表し，そのうち FIFO は古い情報から優先的に削除する方法である．近傍問い合わせの有無はエンコーダにおいて近傍ノードの情報を集約するために，近傍問い合わせをするか否かを表す．

時刻 t におけるノード v の embedding zv (t) は次のように定式ことを提案した最初の手法である．この手法では，記憶機構は化される．

使われておらず，豊富な時間的パターンを捉えられない欠点が

zv (t) =AGGMP(i,eijt′ ,t′ )∈(v,euvt ,t)∪N (v,t)(si (t′ ), eijt′ , t − t′ )

ある．

(7)

TGN [10] は，過去の相互作用の履歴を考慮するために，各ノードの状態をメモリに保持することで，より豊富な時間パ

AGGMP は近傍ノードの情報を集約する学習可能なパラメータを持つ関数であり，Attention や MLP などで構成される．この近傍ノードの情報は 1-hop 先の属性情報と時間的情報を含む．手法によっては，集約時の近傍ノードの特定にかかる時間を削減するために，エンコーダにおける近傍集約を行わないものもある [11–13, 17]．代わりに自身の記憶機構に k-hop 先の状態も保持する．これにより自身の記憶を参照するだけで近傍集約を行い，処理速度の向上を達成している．
デコーダ．デコーダはリンク予測対象の ２ ノードの embed-

ding を MLP に入力することでリンクの有無を予測する．ノー
ド u, v の ２ ノードの間において時刻 t にリンクが発生する確率 puv は，以下のように定式化される．

puv (t) = MLP(zu (t), zv (t))

ターンを捉えた embedding を獲得することを可能にした．メ
モリとは，各ノードごとに過去の相互作用の履歴を要約する状
態をベクトルとして保持する，最も基本的な記憶機構である．
また，JODIE [21] や DyRep [22]，TGAT などの TGN 以前の CTDG を対象とした手法を一般化することができるフレー
ムワークとなっている．最近，PyTorch Geometric においてTGN の並列計算をより高速化した方法が公開されており，より大規模なグラフに対しても効率的に計算が行える．TGN の課題としては，層数を増やすと，過剰平滑の問題が生じ，高次情報を embedding に反映できないことや，エンコーダの集約
時に問い合わせるノードの数が指数関数的に増大することで計算効率が悪いという点が挙げられる．

(8)

APAN [11] は，CTDG による手法の実世界応用を目的に，実行速度の改善を行なった手法である．TGAT や TGN では，

MP ベースの利点としては，記憶機構やタイムエンコーディ

エンコーダでのノード embedding の生成の際に近傍ノードにング関数の活用により時間的パターンの抽出が可能であること

問い合わせをする必要があり，ここが計算時間のボトルネックが挙げられる．欠点としては，Message Passing だけでは，リとなっている．これを解決するために APAN では，各ノード

ンク予測において重要な構造的パターンを識別することが難し

ではメモリの代わりにメールボックスという固定長の k-hop 近

いことが挙げられる．この課題は，ハイブリッド (MP+WA)

傍のメッセージを保持する記憶機構を用いてノード embeddingの手法 [16, 17] において取り組まれている．また，複数 hop 先を生成する．これにより，ノード embedding の生成の際に近まで伝搬するために層数を増加させると，２つの問題が生じ傍ノードに問い合わせをする必要がなくなり，実行時間を大幅る．一つ目は，過剰平滑であり，グラフ内の全てのノードがマに短縮している．メールボックスでは，新しいメッセージを受

ルチホップ近傍を共有することにより、学習された全てのノー

け取ると，最も古いメッセージを消去する FIFO の方式がとらド embedding が類似してしまうという問題である．この課題れている．このため，リンク発生が頻繁なノードは，長期的なは， [13] において取り組まれている．２つ目は伝搬するノード

時間パターンを捉えられないことが課題として考えられる．

数が hop 数の増加とともに指数関数的に増加するため，計算

TGL [12] は，大規模グラフに適用可能かつ，TGN よりも多量的が大きくなるという課題である．この課題は， [17] におい

くの手法を一般化した汎用フレームワークである．近傍ノードて取り組まれている．また，大規模データセットの場合，そのへの高速な問い合わせを可能にする CSR 行列ベースのデータ

ノード数の多さから，メモリを保持するために莫大な記憶容量

構造と，様々な近傍探索アルゴリズムをサポートする並列実行を要求する．

可能なサンプラーにより，計算時間を大幅に削減することに成各手法．TGAT [6] は，学習時に未登場のノード表現を学習功している．また，記憶機構を有する手法においてバッチサイすることが難しいという従来の手法の課題を解決するために．

ズが大きい場合に生じるバッチ内の時間的な依存関係が失われ静的グラフにおいて成功を収めた Graph Attention(GAT) をる問題を解決するために，ランダムチャンクスケジューリング

動的グラフに対しても適用できるように拡張した手法である．

アルゴリズムを提案している．

また，古典的調和解析の Bochner の定理を活用したタイムエン

TPGNN [13] は，伝搬されるメッセージの hop 数ごとに記

コーディングを用いることで，時間的な情報を MP に組み込む

憶状態を分けて保持し，Transformer [23] を用いて重要な hop

数を特定することで，TGN における課題である高次情報の抽

g(w; Su )[i] = |{W |W ∈ Su0 : w = W [i][0]}|, i ∈ {0, 1, . . . , m}

出と過剰平滑の解決を達成している手法である．APAN と同様(10)に，エンコーダでの embedding の生成時には，自身のノード

g(w; Su0 )[i] はウォーク集合 Su0 の内，ノード w が i 番目の位が保持する記憶ベクトルのみ用いるため，近傍ノードに問い合置するウォークの数をカウントしたものとなっており，これにわせをする必要がなく，計算効率も向上している．ただし，各より動的グラフの構造的情報を捉えることができる．

ノードごとに記憶状態を伝搬する hop 数分の状態を保持する必こうして得られた ICAW をウォークのノード ID と置き換え要があるため，ノード数の多い大規模なグラフを対象とする場ることで CAW を獲得することができ，次のように定式化さ合には空間的計算量が課題となると考えられる．

れる．

3. 2 Walk Aggregation ベース

Ŵ = ((ICAW (w0 ), t0 ), (ICAW (w1 ), t1 ), ..., (ICAW (wm ), tm ))(11)

概要．Walk Aggregation(WA) ベースは，注目ノードを始点とする時間的な制限を設けた多数ウォークから相対位置情

ただし，表記の簡単のため，ICAW (w; {Su0 , Sv0 }) を ICAW (w)

報を抽出し，RNN に入力することで構造的パターンを捉えと表現している．こうして得られた CAW の集合をそれぞれたリンク embedding を生成し，リンクの予測を行う方法であŜu0 ,Ŝv0 とする．

る．このウォークは Wang ら [14] によって提案された Causal

Anonymoous Walks (CAW) と呼ばれるウォークをベースとしている．CAW は時間的因果関係の条件の下，最近のリンク発生を優先的にサンプリングすることで生成されるウォークであり，動的グラフにおける構造的パターンを捉えることができる．

MP ベースが CTDG における汎用的なノード embedding の生成を目的としている一方で，WA ベースではリンク予測タスク

エンコーダ．エンコーダは，生成した CAW を入力として注
目リンクの embedding を以下の式により生成する．

zu0 v0 (t0 ) = AGGWA (enc(Ŵ ))(12)

Ŵ ∈Ŝu0 ∪Ŝv0

ここで，enc は，CAW を系列処理する学習可能なパラメータを持つ関数であり，次のように定式化される．

の精度の向上を目的としている．そのため，リンク予測タスク

enc(Ŵ ) = RNN({f1 (ICAW (wi ))||f2 (ti−1 , ti )}i=0,1,...,m )を解く上で重要となる構造的パターンを捉えることに主眼を置(13)いている．WA ベースは，主に，相対情報抽出機構，エンコー

ただし，t−1 = t0 である．ここで，RNN 関数は系列モデルで

ダ，デコーダの 3 つの構成要素からなり，その構成は図 2 のよある RNN などに入力することを表し，f1 は CAW を処理する

うに表される．相対情報抽出機構は，注目ノードを始点とする

ための MLP，f2 はタイムエンコーディング関数である．この多数ウォークを用いて，注目ノードに対する各近傍ノードの相ようにして CAW を系列モデルにより処理することで，リンク

対位置情報を生成する．

予測タスクにおいて重要である構造的パターンを抽出すること

相対情報抽出機構．相対情報抽出機構は，注目ノードを始が可能となる．

点とする多数ウォークを用いて，注目ノードに対する各近傍デコーダ．デコーダは，予測対象のリンクの embedding をノードの相対位置情報を生成する．ここでは，代表的な手法

MLP に入力することで最終的なリンクの有無を予測する．ノーである CAW-N において提案されている CAW について定式

ド u0 , v0 の ２ ノードの間において時刻 t0 にリンクが発生する化する．まず，CTDG における長さ L の一般的なウォークを

確率 pu0 v0 は，以下のように定式化される．

W = ((w0 , t0 ), (w1 , t1 ), (w2 , t2 ), ..., (wL , tL ))，と定義する．ただし，t0 > t1 > ... > tL かつ (wi−1 , wi , ti ) ∈ E, 1 <=i<=Lと

pu0 v0 (t0 ) = MLP(zu0 v0 (t0 ))する．時刻 t0 においてノード u0 と v0 にリンクが発生したと(14)

WA ベースの利点としては，ICAW が相対位置情報を保持しき，u0 と v0 を始点とする長さ m のウォークをある時間的因果ているため，リンク予測タスクにおいて重要である構造的パ関係の条件の下，それぞれ M 個生成し，その集合を Su0 ,Sv0

ターンを抽出することが可能となる．また，生成した相対位置とする．この時間的制約とは，最近の相互作用ほど重要である

情報をウォークの各要素として RNN などの系列モデルに入力という特徴を捉えるため，exp(−α(t − tp )) に比例する確率でしているため，注目ノードからの hop 数を考慮可能であり，豊次の遷移先ノードを決定する．ただし，α は正の定数であり，富な構造的パターンを抽出できると考えられる．

t は現在注目しているリンクの発生時刻，tp は時刻 t 以前の遷移候補リンクの発生時刻を表す．このウォークの集合を用い欠点としては，WA ベースの手法はリンク予測タスクを解くことを目的として設計されており，動的クラス分類などの他のて， Su0 ∪ Sv0 に少なくとも一度は登場したノード w に対し

下流タスクを解くことを想定していないという点で，汎用的でて，ICAW (w; {Su0 , Sv0 }) を生成する．これは，匿名化されたはないということが挙げられる．また，各リンクの予測に対し相対位置情報を表すベクトルであり，注目 2 ノードのペアの形て莫大な数のウォークを生成し，またその数だけ系列モデルに式とすることにより，注目２ノードの相関を捉えることができる．以下にその定義式を示す．

ICAW (w; {Su0 , Sv0 }) = {g(w; Su0 ), g(w; Sv0 )}する必要があるため，莫大な計算時間がかかる．
各手法．CAW-N [14] は，上記の CAW を用いることで，(9)

CTDG における構造的パターンを明示的に捉えた最初の手法である．MP ベースが主流であった本分野において全く異なるアプローチにより最先端の精度を達成した手法であり，後の研をそれぞれ保持する．これにより，TPGNN と同様に高次情報究に大きな影響を与えている．CAW-N ではリンク embeddingの抽出が可能となり，最終的なノード embedding の表現力が向に埋め込む情報として，ICAW のほか，時間的情報として，タ上する．本稿にて登場した４つの記憶機構について表 2 にまとイムエンコーディングを用いることで時間的パターンを捉えるめる．また，静的グラフにおいて成功した Distance Encoding

ことを試みている．しかし、実際には時間的に近いイベントが(DE) を相対位置情報として用いることで，構造的パターンを優先的にサンプリングされるウォーク戦略をとっているため，捉えることも可能である．他にも，キャッシュとハッシュ関数

タイムエンコーディングと記憶機構の両方を活用している MPをうまく組み合わせることで，近傍ノードへの並列で高速なア

ベースと比較すると，時間的パターンの抽出は効果的に行わクセスを実現することができ，近傍情報を構築を高速化していれていない．また，一つのリンク予測を実行するために多くのる．処理速度は TGL と同等程度の現在最先端の実行速度を達

ウォークを生成し，それらを系列モデルにより処理する際にか成しており，大規模グラフへの適用性は高い．一方で，各ノー

かる時間は莫大なものとなる．

ドごとに自身含めた複数の近傍ノードの状態を保持する必要が

NeurTWs [15] は，複数ウォークの作成時に既出のウォークあるため，使用するメモリは莫大なものとなると考えられる．

のサンプリング確率を下げたり，高次ノードの影響を強調す
ることよって，CAW に比べてより豊富な近傍情報をリンク

embedding に埋め込むことができる手法である．また，タイム
エンコーディングの代わりに Ordinary Diﬀerential Equations(ODE) を用いることで，より豊富な時間的パターンを明示的に抽出することができる．通常のリンク予測タスクではネガティ
ブサンプルが単純にランダムな 2 ノードをサンプリングしたも4 分

析

この章では，ここまで紹介した手法を表現力と効率性の 2 つの観点で分析する．表 1 に各手法に対するこの２つの観点による分析をまとめる．

4. 1 表 現 力のであるという問題があり，それに対処するために，コンピューある手法の embedding がリンク予測を行う上で重要な情報

タビジョンの領域において成功した Contrastive Learning を活をどの程度表現可能であるかの程度を表現力と定義する．高い

用して embedding を生成する．しかし，WA ベースの手法の表現力を有する手法は様々なパターンの CTDG が識別可能で課題であるウォークの生成とそれらを RNN に入力して計算すあるため，リンク予測精度は向上する． 2 章で定義した 4 つのる際の時間的コストの課題は解消されていないため，本手法もグラフ特徴についてそれぞれ分析を行う．

大規模グラフへの適用性は低い．

3. 3 ハイブリッド
概要．ハイブリッド（MP+WA）は，文字通り MP ベースとWA ベースの方法を組み合わせた手法である．具体的には，MPベースを基本設計とし，Message Passing もしくはエンコーダ
における集約時に相対位置情報を付与することで，本来捉えられなかった構造的パターンを活用可能にしている．
各手法．PINT [16] は，MP ベースのエンコーダにおける集約関数に理論的裏付けのある工夫を施し，さらに相対位置情報を付与することでノード embedding の表現力を向上させている手法である．ノードエンべディング生成時に，CAW における遷移確率 exp(−α(t − tp )) を時間的制約として集約関数に乗じることで，最近発生したリンクに明示的に注目し，TGN や

CAW が捉えることのできなかった構造的パターンを抽出可能にしている．また，ウォークに基づく相対位置情報を使うことで，従来の MP ベースの手法が捉えることができなかった構造
的パターンを抽出可能にしている．この時作成するウォークは行列により計算されるため，処理速度も向上している．一方，集約時に近傍問い合わせを行うことや，ウォークに基づいて相対位置情報を用いることから処理速度が遅く，大規模グラフへの適用性は低い．

NAT [17] は，k-hop 辞書メモリと，シンプルな相対位置情報を活用することで，表現力と効率性の双方において最先端の性能を示す手法である．k-hop 辞書メモリは直近の相互作用の履歴からダウンサンプリングした k-hop 以内の近傍ノードの状態

属性情報．属性情報のうち，低次近傍属性情報については

MP ベース，WA ベース共に活用可能である．MP ベースでは 2-hop 近傍までであれば過剰平滑の課題が生じないため，低次近傍情報を問題なく捉えることができる．WA ベースでは，ウォークの長さを 2 以上とすることで低次近傍属性情報が獲得可能である．この情報はリンク予測において最も基本的な情報であり，全ての手法において獲得できていることがわかる．
一方，MP ベースでは大半の手法が過剰平滑のため高次近傍
属性情報を活用できない．しかし，TPGNN [13] と NAT [17]は記憶状態を hop 数ごとに分けて保持し，Tranformer を用いて重要な hop 数を特定することで， 過剰平滑を回避し，高次
近傍属性情報の抽出を可能にしている．WA ベースでは，ウォー
ク長を 3 以上に設定することで高次近傍情報が獲得可能である．
時間的パターン．MP ベースの手法は，Xu らにより提案された，三角関数の重ね合わせを用いたタイムエンコーディングを用いることで周期的パターンを捉えている [6]．記憶機構を持つ
手法 [10–13, 16, 17] では，系列モデルによる状態の更新により，状態ベクトルが過去のイベント発生の時間的傾向を要約して保持することができるため，非周期的も含めた時間的パターンも捉えている．このように MP ベースの手法では積極的に時間的パターンを捉えようとする試みが見られる．一方で，WA ベースの手法は記憶機構は使っておらず，またタイムエンコーディ
ングは活用しているものの，最近のイベントが優先的に選択されるウォークの戦略をとっているため，長期的な時間的パター
ンを捉えられないと考えられる．ただし，WA ベースの中でもNeurTWs [15] は，時系列処理において強力である OrdinaryDiﬀerential Equations(ODE) を用いることで，より豊富な時
間的パターンを抽出している．
構 造 的 パ タ ー ン ．CAW-N [14] で は ，CAW を 用 い て 系
列 モ デ ル に 入 力 す る こ と で 構 造 的 パ タ ー ン を 捉 え て お り，

NeurTWs [15] では，既出ウォークを再サンプリングする確

5 今後の課題と方向性
ここでは，今後のこの分野における課題と今後の方向性について述べる.

5. 1 効率性の向上のための方向性

率を下げ，高次ノードの影響を強調する工夫をウォークに施す

効率性に関しては，WA ベースの手法において全体的に処理ことで，より豊富な構造的パターンを効果的に捉えている．こ

速度の改善がなされていない．WA ベースで処理速度を高める

うした WA ベースの流れを受けて，PINT [16] や NAT [17] はためには，現状とは全く異なるアルゴリズムで最終的なリンMP ベースに対して相対位置情報を付与することで構造的パ

ク embedding を生成する必要があると考えられる．WA ベー

ターンを捉えている．PINT が WA ベースと同様にウォーク

スの処理速度のボトルネックは，ウォークの数に依存する処理

により相対位置情報を算出する一方で，NAT ではシンプルなである．具体的には，ウォークから相対位置情報を抽出する部

Distance Encoding を活用し，最先端の精度を達成している．

分と，相対位置情報で構成されたウォークをエンコーダにより

4. 2 効 率 性
実アプリケーションへの応用を目標としたときに，処理速度
や使用記憶領域の２つの観点において，各手法が効率的であるかどうかを評価する．処理速度が速ければ，大規模グラフに対しても適用可能となり，即時性の求められる実アプリケーションへの応用が現実的となる．使用記憶領域が少なくて済む手法
であれば，実アプリケーションとして実装がローコストで済んだり，大規模グラフを適用する際に記憶領域が不足することを回避したりすることができる．
処理速度．MP ベースにおいては，エンコーダでの近傍問い
合わせが処理速度のボトルネックとなっているが，APAN [11]や TGL [12]，TPGNN [13] では k-hop 近傍の情報を自身の集約する部分である．この部分の処理速度を改善する方法としては，ウォークを生成せずに，ウォーク生成の際に用いる確率exp(−α(t − tp )) を直接用いて相対位置情報を作成することが考えられる．エンコーダにより集約する部分については，RNNを用いずに，グラフ分類タスクに帰着する方法があると考えられる．これは静的グラフのリンク予測において成功を納めた SEAL [24] から着想を得ており，リンク予測２ノードの近傍ノードで構成されるサブグラフに相対位置情報を付与し，グラ
フ分類用の GNN に入力するというものである．こうすることで，既存の WA ベースの手法の課題である処理速度の課題を解決できると考えられる．

5. 2 新しい観点での評価

ノードのメモリに保持することで，近傍問い合わせをする必現状，精度に注目した手法が多く，効率性も考慮するものも要がなくなり，処理速度を向上させている．さらに，TGL で提案され始めている．一方で，識別可能性や公平性，説明可能

は，CSR 行列ベースのデータ構造を活用することで Message

性に関してはまだ未開拓である．識別可能性とは，各手法が構

Passing における近傍問い合わせを高速化し処理速度を向上さ

造的パターンをどの程度まで識別可能であるかを表す用語であせている．一方，WA ベースの手法は，一つのリンク予測を実る．PINT [16] の論文では，それ以前の手法である TGAT や行するために多くのウォークを生成し，それらを系列モデルに

TGN，CAW を含めて識別可能性の検証をしている一方で，そより処理するためにかかる時間が莫大なものとなるため，処理の他の論文では，こうした理論的な検証は取り組まれていない．

速度の観点で効率であるとは言えない．また，ハイブリッドの公平性とはある特定のグループに対して偏見を持たないように

NAT [17] は，キャッシュとハッシュ関数をうまく組み合わせるすることである．公平性を重視する場合，例えば，動的リンク

ことで，近傍ノードへの並列で高速なアクセスを実現している．

予測においては高次数ノードが低次数ノードに比べて推薦されこのように，最近多くの手法が処理速度の向上を目的に新しいやすい状況を取り除いたり，動的クラス分類では特定の属性を手法が提案されていることがわかる．

持つグループに対して評価が緩くなったりしないようにする必

使用記憶領域．MP ベースの手法は TGAT [6] 以外はノード要がある．このような特定のグループに対して偏見を持つかど数に比例する数の状態を保持する必要がある．そのため，ノーうかを検証する研究は，我々の知る限り見つからない．また，

ド数の多い大規模グラフを扱う場合，莫大な記憶領域が必要で

近年 AI の実用化に伴い，説明可能性を求められる場面が増加ある．しかし，TGL [12] では，CSR 行列ベースのデータ構造

しているが，そのような観点での研究も我々の知る限りでは見を活用することで CTDG の使用記憶領域を削減することがでつからない．このように，新しい観点で既存手法を見つめ直し，きる．一方，WA ベースの手法は状態を保持する必要がないた

今後の方向性を考えることが重要であると考えられる．

め，使用記憶領域の観点では効率的な手法であると言える．このように，使用記憶領域の観点では，最近提案された手法において改善点は TGL 以外は見受けられない．

5. 3 適切な評価方法
既存のデータセットは SOTA で性能評価をすると，AP や

AUC では 90 ％後半の精度を示すことが多く，新しい手法の精度改善の余地が小さい．これを解消するための方法が 2 つ考えられる．一つ目は，より複雑なデータセットを用いることである．予測の難しいパターンが含まれたデータセットを検証に用いることで，精度の改善が認識しやすくなると考えられる．二つ目は，評価指標の見直しである．AP や AUC は リンクの存在の有無，つまり，0, 1 を判定する指標である．一方で，Hits@10 や Mean Rank は，多数のリンクの候補に対する正解
リンクのランキングを評価値に用い，より細かい粒度での予測を行うため，詳細な分析が可能かつ，実応用上の評価に適切であると考えられる．そのため，これらの評価指標を用いることで手法を適切に評価できると考えられる．

5. 4 データセットの拡充
小規模なデータセットに加えて，大規模なものも公開され始めているが，属性を持つグラフは少ない．既存手法では，主にリンクの発生履歴をベースに embedding を生成し，属性情報
は embedding に連結するアプローチしかされていない．属性付きグラフが豊富に存在すれば，効果的にノード属性を活用するアプローチの重要性が増す．また，様々なカラムを含む属性付きグラフを用いることができれば，特定の属性によりノードをグルーピングすることで，公平性の検証も容易に可能になると考えられる．

6 終わりに
本論文では，近年の動向を踏まえ，CTDG を対象とするリンク予測手法の包括的な外観を提供した．最先端のリンク予測
手法を，MP ベース, WA ベース，ハイブリッドの 3 つのカテ
ゴリに分類し，手法間のつながりを整理した．また，表現力と効率性の２つの観点で各手法を比較し，利点欠点を明らかにした．今後の方向性として識別可能性や公平性といった新しい観点で研究をすることや，データセットや評価指標を見直すことが考えられる．

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

文

献[1] Mohammad Al Hasan and Mohammed J Zaki. A survey oflink prediction in social networks. In Social network data
analytics, pp. 243–275. 2011.
[2] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.
Graph evolution: Densification and shrinking diameters.
The TKDD, Vol. 1, No. 1, p. 2–es, 2007.
[3] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedingsof the ICLR, 2017.
[4] Petar Veličković, Guillem Cucurull, Arantxa Casanova,
Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph
Attention Networks. ICLR, 2018. accepted as poster.
[5] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedingsof the NeurIPS, 2017.
[6] da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, andkannan achan. Inductive representation learning on tempo-

ral graphs. In Proceedings of the ICLR, 2020.
[7] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst,
and Xavier Bresson. Structured sequence modeling withgraph convolutional recurrent networks. In Proceedings ofthe ICONIP, 2017.
[8] 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.
[9] 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.
[10] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide
Eynard, Federico Monti, and Michael Bronstein. Temporalgraph networks for deep learning on dynamic graphs. In
Proceedings of the ICML, 2020.
[11] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang,
Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang,
Bowen Sun, et al. Apan: Asynchronous propagation attention network for real-time temporal graph embedding.
In Proceedings of the SIGMOD, pp. 2628–2638, 2021.
[12] Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios Ioannidis,
Xiang Song, and George Karypis. Tgl: A general framework
for temporal gnn training on billion-scale graphs. arXiv
preprint arXiv:2203.14883, 2022.
[13] Zehong Wang, Qi Li, and Donghua Yu. Tpgnn: Learning high-order information in dynamic graphs via temporalpropagation. arXiv preprint arXiv:2210.01171, 2022.
[14] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec,
and Pan Li. Inductive representation learning in temporal
networks via causal anonymous walks. In Proceedings of the
ICLR, 2021.
[15] Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal
walks: Motif-aware representation learning on continuoustime dynamic graphs. In Proceedings of the NeurIPS, 2022.
[16] A. H. Souza, D. Mesquita, S. Kaski, and V. Garg. Provably
expressive temporal graph networks. In Proceedings of the
NeurIPS, 2022.
[17] Yuhong Luo and Pan Li. Neighborhood-aware scalable temporal network representation learning. Learning on Graphs
Conference, 2022.
[18] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights
into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI, 2018.
[19] Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence tosequence learning with neural networks. In Proceedings of
the NIPS, 2014.
[20] Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, andYoshua Bengio. Empirical evaluation of gated recurrent
neural networks on sequence modeling. In Proceedings of
the NIPS, 2014.
[21] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction
networks. In Proceedings of the 25th ACM SIGKDD, pp.
1269–1278, 2019.
[22] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal,and Hongyuan Zha. Dyrep: Learning representations overdynamic graphs. In Proceedings of the ICLR, 2019.
[23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia
Polosukhin. Attention is all you need. NIPS, Vol. 30, , 2017.
[24] Muhan Zhang and Yixin Chen. Link prediction based ongraph neural networks. In Proceedings of the NeurIPS, 2018.