修士論文 要旨

二次マルコフ過程を考慮した自己回帰型テンポラルグラフ生成モ
デルと送金データへの応用
数理情報学専攻 48216223
指導教員

長澤 達也
久野 遼平 講師

フを条件として用いることができ，p(Gt ) は p(Gt |G<t )1 はじめにと表すことができる．

送金データとは口座やユーザー間の送金履歴を記録したデータのことである．これらはネットワークとし3 提案モデルて捉えることができ，経済における資金の流れをリア

本モデルは静的自己回帰型グラフ生成モデルであるルタイムで追うことができる貴重なデータである．国GraphGen[1] をベースに時間拡張を行ったうえで，対内の都市銀行から提供された銀行送金データに対する象を無向グラフから有向グラフに拡張したものである．

実証分析 [3] では，送金ネットワークがスケール性やスモデルの全体の流れを図 1 に示す．

モールワールド性といった複雑なネットワークの特性を持つことや，経済環境の変化を色濃く反映したデー
タであること，着金元の情報が送金先に相関するという二次マルコフ過程の性質を持つことなどが明らかになった．
そこで本修士論文では送金データを対象にした動的・有向・中規模ネットワークのテンポラルグラフ生成を
図 1. 提案モデルの全体図

試みる．グラフ生成モデルとは訓練対象となるネットワークの集合を対象に，訓練対象と同じような統計的性質を持つネットワークを生成するアプローチのこと

まず，グラフに対し登場順によってノードの順番を定である．深層学習を用いたグラフ生成は既に分子グラめ，これを用いて辞書順で並び替えたエッジリスト S tフなどにおいて既に一定の成果を挙げているが，有向に変換する．ここでエッジリスト S t = (s1 , . . . , sm ) のネットワークを対象にしたものや時間変化を伴うネッ構成要素 si はトワークに対してはまだ研究が浅い．

si = (tu , tv , Lu , Le , Lv )ネットワークにおけるテンポラルグラフ生成問題を設

tu , tv : ノード u, v のノード番号
Lu , Lv : ノード u, v のラベル情報

定し，モデルを提案する．提案モデルは自己回帰型グラ

Le : エッジ euv のラベル情報

本修士論文では実証分析の結果を踏襲し [3]，送金フ生成モデルをベースに時間拡張を行ったうえで，実証分析の結果得られた一月前の着金元が当月の送金先と相関するという性質を加味したものである．

(2)と 5 つの成分からなるタプルとして定義する．
二次マルコフ過程の考慮として，このエッジリストに対して 1 時点前の隣接行列 At−1 を条件として用いる．
すなわち，本モデルの条件付き生成モデルは2 問題設定
時刻 t における有向グラフ Gt = (V t , E t ) をノード集合 V t = {v1 , . . . , vN t } およびエッジ集合 E t = {euv =(u, v)|u, v ∈ V t } によって定義する．各時刻における訓練グラフの集合列:

Dtrain = (G , . . . , G |G1Tt= {Gti })(1)

p(Gt |G<t ) = p(S t |At−1 )(3)と表せる. LSTM を用いてエッジを順に生成するので，

p(S t |At−1 ) ==m
∏
i=1m
∏

p(si |s<i , At−1 )(4)p((tu , tv , Lu , Le , Lv )|s<i , At−1 )i=1が与えられたもとで， p(Gt ) を予測し，GT +1 を生成す(5)ることが本モデルの目標である．さらに，本モデルは時t−1となる．隣接行列 At−1 の u に対応する列 Au
はuの系列データを対象としているからその時刻までのグラ1 時点前の着金元情報を表しており，これを送金先の予

二次マルコフ過程を考慮した自己回帰型テンポラルグラフ生成モデルと送金データへの応用 (長澤 達也)

測 (tv , Lv , Le ) に条件として用いる．さらに本モデルで表 1. 生成グラフに対するグラフ統計量の指標．各指はエッジの始点ノードを表す tu ，Lu も送金先の条件に標の値は分布に対する MMD[2]．数値が小さいほどテストグラフと生成グラフが類似してい与える．すなわち，

p(S |Atm∏t−1ることを表す．

)=

モデル

p((tu , Lu )|s<i )p((tv , Lv , Le )|s<i , (tu , Lu ), At−1u )i=1(6)

総次数

入次数

出次数

クラスタ係数

NSPDK

ノードラベル

エッジラベル

提案モデル

0.75

1.12

1.02

1.69610.16370.22470.0011GraphGen

1.00

1.22

1.24

1.81950.13960.13050.0018Erdös

0.33

0.64

0.67

1.59350.1021

--BA

0.90

1.10

1.121.7376

0.2755-

-

SBM

0.20

0.35

0.35

0.76960.1035--DCSBM

0.15

0.29

0.26

0.75090.1033--と表せる．(tu , Lu ) と (tv , Lv , Le ) の組はそれぞれ独立性を仮定し，それぞれの条件を LSTM の隠れ状態示しており，深層グラフ生成モデルである提案手法およh1i , h2i を用いて表すとび GraphGen は送金ネットワークのグラフ構造を学習

p(S t |At−1 ) =m∏

できていないと言える．提案手法と GraphGen の間でp(tu |h1i ) · p(Lu |h1i )i=1·p(tv |h2i ) · p(Lv |h2i ) · p(Le |h2i )は優位な差は見られない．

(7)

古典的ネットワークモデルではラベル推定を行わないため，ラベルの類似性は提案手法と GraphGen のみである．h1i , h2i は埋め込み関数 femb と LSTM の状態評価を行う．ノードラベルでは GraphGen の方が高精遷移関数 fh を用いて度を示した一方で，エッジラベルでは提案手法の方が優()

h1i = fh h1i−1 , femb (si−1 )()h2i = fh h2i−1 , femb (si−1 , (tu , Lu ), At−1u )(8)

れた結果を出している．エッジラベルの予測に対し，提(9)案モデルではそれまでのエッジ情報に加え，始点ノードで更新される．また，各成分 c ∈ {tu , tv , Lu , Le , Lv } は対応する hi と出力関数 fc を用いて

c ∼M θc = fc (hi )(10)によって得る. θc は多項分布のパラメータであり，∼Mは多項分布によるサンプリングを表す．
以上のエッジ si を生成する一連の過程を図 2 に示す．の情報 (tu , Lu ) および Atu を与えていることが精度の向上に繋がった可能性がある．

5 おわりに本修士論文では送金データを対象とした動的・有向・中規模ネットワークのテンポラルグラフ生成モデルの構築を試みた．結果としては提案モデルを目覚ましく改善する所まではもっていくことができなかった．しかし，送金ネットワークに対するテンポラルグラフ生成問題の有効性を示すことができた．また同時に送金ネットワークに対してテンポラルグラフ生成問題を設定する際に生じる諸問題を整理することができた．

参考文献

図 2. 提案モデルのネットワーク図

4 主結果
提案モデル，GraphGen および古典的ネットワークモデルについて，銀行送金データに対してグラフ生成した結果の一部を表 1 に示す．
いずれのデータにおいてもブロック構造を用いた古典的ネットワークモデルである DCSBM が優れた値を[1] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu.
Graphgen: A scalable approach to domain-agnostic
labeled graph generation. In Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen, editors, WWW ’20: The Web Conference 2020, Taipei,Taiwan, April 20-24, 2020, pp. 1253–1263. ACM /IW3C2, 2020.
[2] Arthur Gretton, Karsten M Borgwardt, Malte J
Rasch, Bernhard Schölkopf, and Alexander Smola.
A kernel two-sample test. The Journal of Machine
Learning Research, Vol. 13, No. 1, pp. 723–773, 2012.
[3] 久野遼平, 長澤達也, 高橋秀, 近藤亮磨, 大西立顕. 銀行
送金ネットワークの内在的構造と時間変化. 人工知能,Vol. 38, No. 2, 2023.