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

グラフ生成モデルの発展と今後の展望〜統計的生成モデルからDeep Graph Generatorsまで〜
長岡技術科学大学 大学院工学研究科
渡部康平

1本講演の概要

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

uノードとエッジからなるグラフは極めて汎用性の高いデータ構造．
通信ネットワーク
5RXWH
6ZLWFK
3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU

ソーシャルネットワーク

H
H C
H

5RXWH
6ZLWFK
3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU/$1

ノード (頂点，vertex)&ORXG

分子構造,QWHUQHW

H
C H
H

エッジ (辺，リンク)

u本講演の主テーマは，グラフ構造を人工的に作るグラフ生成技術．
u少数のパラメータやグラフデータから存在しない構造や未来の構造を作り出す．

uグラフ生成のアプリケーション
u通信プロトコルのシミュレーション
uソーシャルネットワークの情報伝播やコミュニティ予測
uプログラムコードのサジェスト
u新しい分子構造の生成による新薬開発

2

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

グラフ生成技術の歴史

uグラフ生成技術は1959年のERモデルに始まり，現代に至る．
u広大なグラフの空間から所望の特徴を有したグラフを如何にサンプリングするか．
ER model(1959)

WS model(1998)
BA model(2002)

small world性
統計的グラフ生
scale free性
成の始まりなどの特定特徴を持つグラフ生成

統計的生成

NetGan(2018)
GraphGan(2018)

CondGen(2019)

実データの特徴を 実データを再現したグラフ グループ分けして生成生成

GraphTune(2023)

実データの特徴を再現し，かつ，特定の特徴を調整

Deep Graph Generators

u同時に様々な特徴を定量化した特徴量が開発される．
u平均最短経路長，直径uクラスタリング係数，モジュラリティ
u平均次数，次数分布のべき指数，エッジ密度
u固有値，次数中心性，媒介中心性，PageRank

3

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

統計的な生成モデル – ERモデル
uErdős–Rényiモデルは最も原始的なグラフ生成モデル．
u入力パラメータ: ノード数 ! ，エッジ密度 "1. ! 個のノードを作成する．
2. すべての2ノード間について確率 " でエッジを張る．

4

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

統計的な生成モデル – WSモデル

uWatts-Strogatzモデルはスモールワールド性を再現するグラフ生成モデル．

uスモールワールド性: ノード数 ! に対して平均経路長 # がlog !でしか増えない．
u入力パラメータ: ノード数 ! ，平均次数 2( ，エッジ張替え確率 "1. ! 個のノードを作成する．
2. 平均次数が2$であるリング格子を構成する．
3. すべてのエッジについて確率 " でエッジを張り替える．

5

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

統計的な生成モデル – BAモデル

uBarabási–Albertモデルはスケールフリー性を再現するグラフ生成モデル．
uスケールフリー性: 次数分布 )(+) が )(+) ∝ + !" (2 ≤ / ≤ 3) となる．
u入力パラメータ: 追加エッジ数 1 ，ノード数 !

% 個のノードから成る完全グラフを作る．
% 本のエッジを持つノードを追加する．ただし，新規ノードからのエッジが張られる確率は，つながる相手先のノードの次数に比例させる．
3. ノード数が!になるまでステップ2を繰り返す．
1.
2.

6

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

Deep Graph Generators – GraphGenu統計的なグラフ生成とは対象的に，Deep Learning を使って実グラフを模倣したグラフを生成．
uシーケンス予測が可能な深層学習のLong Short Term Memory (LSTM)を使って生成．

深さ優先探索でエッジのシーケンスデータに変換

n元ノードID
先ノードID00
111221301 ')6

1. 学習用グラフをエッジのシーケ
VHTXHQFHンスに変換する．
2
3
2. シーケンスデータを入力して，次のエッジを出力(予測)するよ 学習用データ
う学習を進める．
/670
3. 学習済みモデルを使って再帰的に出力させて，シーケンスを生成．
(VWLPDWHG')6
4. シーケンスをグラフに逆変換す シーケンスの続き
VHTXHQFHることで，生成グラフを得る． を予測して出力ʀʀʀʀʀʀʀʀʀʀ
ʀʀʀʀʀʀʀ
ʀʀʀʀʀʀʀ7

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

Deep Graph Generators – GraphTune
uConditional Variational AutoEncoder (CVAE)とLSTMを組み合わせた任意の特徴量を指定可能な生成モデル[1][2]．
uグラフを一度ベクトル空間にマッピングして特徴量の情報を付加することで連続的な調整を実現．
1. シーケンス化したグラフをベクトルに圧縮して，再びもとのシーケンスに解凍するよう学習．
2. 学習済みモデルの解凍パートに乱数ベクトルを与えて生成．
/670EDVHGHQFRGHU/670EDVHGGHFRGHU
FRQGLWLRQDOYHFWRU/DWHQWYHFWRU
RIIHDWXUHV
6DPSOLQJ*UDSKGDWDVHW

6HTXHQFH

*HQHUDWHGJUDSKV

FRQGLWLRQDOYHFWRUFRQGLWLRQDOYHFWRU*UDSK)HDWXUH

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

Deep Graph Generators – GraphTune-FE
uGraphTuneをさらに高精度化するために，Feature estimator 特徴
量のフィードバック機構を加えた生成モデル．

uFeature estimatorは再構築されたシーケンスからグラフの特徴値を表す条件ベクトルを推定する
uGrapTuneとFeature estimatorを交互学習6HTXHQFH*UDSK
GDWDVHW*UDSK7XQHʀʀʀʀʀʀʀʀʀ

5HFRQVWUXFWHGVHTXHQFHʀʀʀ(QFRGHU'HFRGHU

ʀʀʀʀʀʀʀʀʀʀʀʀ

&RQGLWLRQYHFWRU(VWLPDWHGIHDWXUHYHFWRU/670EDVHG
IHDWXUHHVWLPDWRU

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

グラフ生成モデルによる生成グラフの検証

uグラフ生成問題の目標は，広大なグラフの空間から所望の特徴を有したグラフを如何にサンプリングするか．
uWSモデル: スモールワールド性(平均最短経路長)を再現したい．
uBAモデル: スケールフリー性(次数分布のべき指数)を再現したい．
uGraphGen: 入力グラフと同じ特徴を再現したい．
uGraphTune: 入力グラフの特徴を保持しつつ特定の特徴量だけ調整したい．

uグラフを生成して，各種特徴量の分布がどの様になるか．
u再現したいグラフがある場合，ある特徴量を調整しても別の特徴量が連動して再現対象から離れたりする．
uつまり，多面的な視点で見て再現対象に近いことが重要．

10

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

WSモデルが生成するグラフの空間的特徴
uWSモデルでエッジ張替え確率 ! を変更した場合の特徴量の分布

u平均最短経路長は調整されている一方で，次数分布のべき指数は調整不能．
Average Path
Length (APL)
Averagedegree(AD)Modularity(MDL)
Clustering
coefficient(CC)
Power-law
exponent(PLE)
APLADMDLCCPLE

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

WSモデルが生成するグラフの空間的特徴
u平均経路長と次数分布のべき指数の分布の拡大図．

12

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

GraphTune-FEでの実験条件
u以下の2つのデータセットを使用して GraphTune-FE を訓練．
uERモデルで生成したグラフ (ER dataset)uTwitterの部分グラフ (Twitter dataset)uER dataset
u条件ベクトルとしてエッジ密度を与えて，ノード数と独立に調整可能か検証．
uエッジ密度を 0.0，0.25，0.5，0.75，1.0 の5パターンで指定．

uTwitter dataset
u条件ベクトルとして平均最短経路長を与えて，学習グラフの基本的な特徴を保持しつつ，平均最短経路長のみ調整することを試みる．
u平均最短経路長を 3.0, 4.0, 5.0 と3パターンで指定する

13

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

GraphTune-FEが生成するグラフの空間的特徴
uER datasetで学習した場合の生成グラフの分布．

u独立に調整可能な特徴量であるノード数 ! とエッジ密度 " が独立に調整可能であることが確認できる．

14

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

GraphTune-FEが生成するグラフの空間的特徴
uTwitter dataset で学習した場合の生成グラフの分布．

u全体的な分布が学習データ(Real data)と一致している．

Average Path
Length (APL)
Averagedegree(AD)Length = 3.0
Length = 4.0

Modularity(MDL)

Length = 5.0
Real data

Clustering
coefficient(CC)Power-law
exponent
(PLE)
APL

AD

MDL

CC

PLE

15

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

GraphTune-FEが生成するグラフの空間的特徴
u平均最短経路長の分布の拡大図．

Length = 3.0
Length = 4.0
Length = 5.0
Real data

16

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

今後の展望 – 条件付き生成技術

uグラフ生成技術は，学習データを模倣した生成は成熟してきている．
u今後は条件付き生成技術の開発が中心になると考えている．
u調整精度の高精度化
u調整対象の多角化
u調整領域の拡張

uアプリケーションの多様さを考えても条件付き生成は有望．

実データ

指定値

学習データに存在しない領域のグラフを生成 (今後)頻度

学習データの一部に類似したグラフを指定して生成 (現状)
頻度

頻度

学習データに類似したグラフを生成
(従来)

指定値

生成データ
特徴量1

特徴量1

特徴量1
17

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

今後の展望 – Data driven なグラフ理論

u条件付きグラフ生成技術の成熟すると，任意の特徴量を持つグラフを得ることが可能になる．

特徴量2(例: 平均最短経路長)uグラフが存在し得る空間の全体像を把握可能．
uグラフの特徴量間の関係性を解析・検証することが可能．
uグラフの空間を均質にサンプリングしたデータセットを作れる．
グラフが存在し得る限界のライン

特徴量1 (例: 次数分布のべき指数)18

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

まとめ・今後の展望
uまとめuグラフ生成問題は，広大なグラフの空間から所望の特徴を有したグラフをサンプリングする問題．
u生成技術は統計的生成から入力グラフの特徴を学習的に再現する研究が活発になってきた．
uER，WS，BAモデル ⇒ GraphGen，GraphTune

u今後の展望u特に条件付き生成技術がまだまだ未成熟であるがゆえに有望．
u条件付きグラフ生成の技術が成熟すると，古典的なグラフ理論の研究にも恩恵があるかも．

19

関連文献

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

[1] 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.
[2] K. Watabe, S. Nakazawa, Y. Sato, S. Tsugawa , and K.
Nakagawa, “ GraphTune: A Learning-based Graph Generative
Model with Tunable Structural Features,” IEEE Transactions
on Network Science and Engineering, 2023.

20

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

ご清聴ありがとうございました

21