Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

LSTMと条件付きVAEを用いた構造的特徴を高精度に指定可能なグラフ生成モデル†長岡技術科学大学††筑波大学横山昂大†

大学院工学研究科

システム情報系

佐藤良紀†

津川翔††

渡部康平†

1

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

目次
１. 目的・背景
２. 先行研究３. 提案法
４. 実験
５. まとめ・今後の展望

2

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

目的・背景

3

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

目的・背景
u近年、グラフを用いるアプリケーションの需要は増加している
uグラフとして表現できる例
uソーシャルネットワーク：アカウントの繋がり
u通信ネットワーク：通信機器の接続関係

uグラフを用いたアプリケーションの例
u通信プロトコルのシミュレーション
uコミュニティ予測

Route
SwitchProcessor

Route
SwitchProcessor

Route
SwitchProcessor

Route
SwitchProcessor

Route
SwitchProcessor

LAN

Cloud

Internetuグラフ上でのシミュレーションでは、現実の環境の特徴を備えたグラフが必要となる
uプライバシーなどの観点から、これを用意するのは難しい
4

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

目的・背景
uグラフ生成モデルは実世界のグラフデータを補完するアプローチ
u既存のグラフ生成モデルにおける問題
u統計的手法を用いたグラフ生成モデル
Ø 特定の実在するグラフの特徴すべてを捉えた生成は難しい

u機械学習を用いたグラフ生成モデル
Ø 特徴の指定に関する生成手法の研究は非常に少ない
Ø 特徴を指定した生成の精度には課題がある

u目的
実在するデータを学習し、任意の特徴量をより⾼精度に指定することが可能なグラフ⽣成モデルの構築
5

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

目的・背景uアプローチ
u先行研究であるGraphTuneモデルを拡張し、グラフからその特徴値を推定するFeature estimatorを追加して、交互学習アルゴリズムを適用することによって特徴の指定を高精度に行う
uFeature estimatoruグラフから特定の特徴値を推定する
u特徴値の再現に関するフィードバックをGraphTuneに与えられる
u交互学習アルゴリズム
uGraphTuneとFeature estimatorを一方の重みを凍結させて他方を学習する作業を交互に繰り返す
u特徴値を含む条件ベクトルの情報がリークすることを防ぐ

6

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

ネットワークの代表的な特徴

7

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

ネットワークの代表的な特徴
u現実のネットワークが持つ特徴は多く存在し、ネットワーク毎にさまざまな特徴を有している
uスケールフリー性
uごく少数のノードが持つリンクの数(次数)が大きく、大多数のノードの次数は小さいという性質
u特徴量：次数分布のべき指数

uクラスタ性uある人の知人同士が知り合いというように、ネットワークが三角形を取る割合が高いという性質
u特徴量：平均クラスタ係数

uスモールワールド性
uネットワークの平均ノード間距離が小さいという性質
u特徴量：平均最短経路長8

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

先行研究

9

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

GraphTune [3][4]uConditional VAE(CVAE)とLong Short Term Memory(LSTM)を組み合わせた任意の特徴量を指定可能な生成モデル
u前処理
uグラフをDFSコードによってシーケンスへ変換し、グラフから計算される特徴量を条件ベクトルとして連結させる
uこの条件ベクトルを与えることにより、特徴の学習が可能となる
Latent vectorof features

LSTM based encoder

LSTM based decoder

Sampling
...

...

...

Graphdataset

Generatedgraphs...

Sequence

...

...

...

...

conditional vector

...

...

...

...

...

...

conditional vector

...

...

...

...

10

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

DFSコード(Depth First Search Code)uグラフをシーケンスにする手法
1. グラフに深さ優先探索を行い探索順に各ノードにタイムスタンプを付与する
2. タイムスタンプ情報とノードラベル、ノード間のエッジラベルを基に5要素のベクトルに変換する
3. 各ノードを探索順毎にベクトルに変換することでグラフをシーケンスなデータに変換する
シーケンスデータへ

グラフを深さ優先探索

A t=0aB
t=2

Cb cTime

t=1
D

t=3

Time
Time
Nodestamp u stamp v label u

Nodelabel v

Edge
label

001A

B

a1

12

BC

b21

3

B

D

c11

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Conditional VAE[1]uEncoderとDecoderの2つのニューラルネットワークからなる
条件付き生成モデル
uEncoderu学習データとlabelから潜在変数が正規分布に従うように学習

uDecoderu潜在変数とlabelの情報を基に学習データを復元するように学習

label
学習
データ

labelsampling

潜在変数

Encoder

Decoder

出力𝑁(𝜇, σ!)
12Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Long Short Term Memory [2]u長期的な依存関係を学習することが可能なモデルで、シーケンスデータの学習に用いられる
uシーケンスデータを固定サイズのベクトルにすることができる
u前の時系列の出力を再帰的に入力することで生成に利用できる
出力層

ht

中間層
(LSTM block)

A

入力層

xt=

h0h1h2A

AAx0x1x2・・・

ht
A・・・

xt
13

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

GraphTune [3][4]u学習uEncoderはシーケンスから潜在変数を正規分布となるように学習する
uDecoderは条件ベクトルとサンプリングした潜在変数から入力シーケンスを復元するように学習する

u生成u指定したい特徴値の条件ベクトルと正規分布からサンプリングされた潜在変数をDecoderに入力することで生成される
Latent vectorof features

LSTM based encoder

LSTM based decoder

Sampling
...

...

...

Graph
datasetGeneratedgraphs...

Sequence

...

...

...

...

conditional vector

...

...

...

...

...

...

conditional vector

...

...

...

...

14

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

提案法

15

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

提案モデルの構造
uGraphTuneにFeature estimatorモデルを追加した生成モデル
uFeature estimatorは再構築されたシーケンスからグラフの特徴値を表す条件ベクトルを推定する
Sequence
Graphdataset

GraphTune・・・・・・・・・...

Reconstructed sequence

・・・

Encoder

Decoder

・・・・・・・・・...

・・・Condition vector

LSTM-basedfeature estimator

Estimated featurevector

16Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

提案モデルの構造
u提案モデルの学習を通して、GraphTuneがFeature estimatorによる特徴値の推定誤差のフィードバックを受けることが可能となるSequence
Graphdataset

GraphTune
・・・・・・・・・...

Reconstructed sequence

・・・Encoder

Decoder

・・・・・・・・・...

・・・

Condition vector

Estimated featurevector
LSTM-basedfeature estimator

17

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

提案モデルの学習
u提案モデルは、交互学習アルゴリズムによって学習される
u交互学習アルゴリズム
uGraphTuneとFeature estimatorの一方の重みを凍結させ、他方の重みを更新することを繰り返す
u同時に学習した場合、GraphTuneに入力される条件ベクトルの情報がFeature estimatorへリークする可能性がある
u具体的な手順（１）GraphTuneのみを学習させる（２）GraphTuneによって生成されたグラフを学習データセットに追加する（３）Feature estimatorのみを学習させる（４）（１）〜（３）を繰り返す
18

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

実験

19

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

データセットuTwitter上のアカウントのフォロー・フォロワー関係を表すグラフ
uTwitterの実グラフからノード数が50となるように、ランダムに探索することで得られた2,000個の部分グラフ
u簡易化のため、無向グラフとして扱う

follow

follow
follower

20

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

実験内容
uTwitterの部分グラフのデータセットを使用してGraphTuneと提案モデルを学習する
u条件ベクトルとして、平均最短経路長を用いる
uデータセットを訓練用と検証用に分割
u訓練データ数：1,800
u検証データ数：200u生成u平均最短経路長を3, 4, 5 と3パターン指定する
u生成するグラフ数：300

21

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

ハイパーパラメータ
u提案モデルu最初の全結合層のサイズ：256
uLSTMの隠れ層のサイズ：512
u最後の全結合層のサイズ：1
uGraphTune：提案論文で評価されたものを使用

u学習
u最適化関数：Adamu学習率：0.001
uWeight decay：0.0
u勾配クリップの閾値：1.0
u交互学習の反復回数：2
uバッチサイズ：37
uエポック数：10,000
22Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

生成結果の評価
u定性的な評価
u生成されたグラフの特徴量の分布を確認する

u定量的な評価
u生成されたグラフの特徴量の平均値＝＞指定値との差異を評価
u生成されたグラフの特徴量のRMSE＝＞平均値と指定値との差異および分散を同時に評価

RMSE =

E 𝑐"! − 𝑐$#+ Var[𝑐"! ] #𝟏𝟑𝑐"! ︓⽣成されたグラフの特徴量の値
𝑐 ︓指定した値
23

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

生成結果：分布３５３５u各手法による生成結果のカーネル密度推定プロットで分布を表示
u平均最短経路長を5と指定した場合の分布は、GraphTuneよりも提案法の方がより指定値の近くに集中して分布している24

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

生成結果：評価指標
u評価指標による比較

54

GraphTune
指定値

32
102.5

提案法

平均最短経路⻑

平均最短経路⻑6

平均値による⽐較

３４
指定値

５2

RMSEによる⽐較
提案法
GraphTune

1.5
10.5
0

３４
指定値

５

u平均値では2つの手法は指定値通りに平均値が推移
uRMSEでは提案法がGraphTuneと同等かそれ以上の性能を示す
Ø提案法は生成精度を高めることができたといえる

25

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

まとめ・今後の展望

26

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

まとめ・今後の展望
uまとめ
u先行研究のGraphTuneをFeature estimatorを追加することで拡張し、交互学習アルゴリズムを適用する手法を提案した
u生成結果の分布の確認による定性的な評価、平均値とRMSEによる定量的な評価を通して、提案法がGraphTuneよりも高精度な条件付き生成が可能であることを実験的に示した

u今後の展望u他の特徴を指定した場合の評価
u交互学習アルゴリズムの反復回数の増加

27

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

参考文献
u[1] D.P. Kingma and M. Welling, “Auto-Encoding VariationalBayes,” Proc. of the 2nd International Conference on Learning
Representations (ICLR 2014), 2014.
u[2] S. Hochreiter and J. Schmidhuber, “Long Short-TermMemory,” Neural Computation, vol.9, no.8, pp.1735–1780, 1997.
u[3] S. Nakazawa, Y. Sato, K. Nakagawa, S. Tsugawa, and K.
Watabe, “A Tunable Model for Graph Generation Using LSTM
and Conditional VAE,” Proc. of the 41st IEEE International
Conference on Distributed Computing Systems (ICDCS 2021)
Poster Track, 2021.
28

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

参考文献
u[4] S. Nakazawa, Y. Sato, S. Tsugawa, K. Nakagawa, and K.
Watabe, “Graphtune: A learning-based graph generative modelwith tunable structural features,” CoRR, vol.abs/2201.11494, ,2022. https://arxiv.org/abs/2201.11494

29

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

30

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

補足：生成されたグラフ
u指定値ごとに生成されたグラフの一部を抜粋
uReal dataはデータセットから指定値に最も近い3つのグラフを抜粋

31

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

補足：生成結果の分布の全体
GraphTune

提案法

5
平均最短経路⻑

平均最短経路⻑u各手法による生成結果のカーネル密度推定プロットで分布を表示
u平均最短経路長を5と指定した場合の分布は、GraphTuneよりも提案法の方がより指定値の近くに集中して分布している32

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

補足：生成結果の定量的評価
u評価指標による比較

u多くの場合で提案法はGraphTuneよりも優れたスコアである
uGraphTuneが優れている場合でも、提案法との差は小さい
Ø提案法は生成精度を高めることができたといえる
33