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

Evolution and Future Prospectsof Graph Generation Models
Graduate School of Engineering,
Nagaoka University of Technology
Associate Professor
Kohei Watabe
1Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Presentation Overview
uA graph consisting of nodes and edges is an extremely versatile datastructure.
Communication networks
5RXWH
6ZLWFK
3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU

Social networks

Molecular structures
H
H CH

5RXWH
6ZLWFK3URFHVVRU

5RXWH
6ZLWFK
3URFHVVRU/$1node (vertex)&ORXG,QWHUQHWHC HHedge (link)uThe main topic of this talk is artificial graph generation techniques.
uGenerating not present or future graph structures from a small
number of parameters or graph data.

uApplications of graph generation
uSimulation of communication protocols
uInformation dissemination and community prediction in socialnetworks
uCode suggestion in programminguDevelopment of drugs with novel molecular structures

2Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNetsComNetsLab.
Lab.

History of Graph Generation TechniquesuGraph generation techniques began with the ER model in 1959.
ER model(1959)
Randomgraphs

WS model(1998)
BA model(2002)

NetGan(2018)
GraphGan(2018)

Graphs withspecific features(small world,scale free, etc.)

Graphs that
reproduce featuresof real data

Random Graph Generation

CondGen(2019)

GraphTune(2023)

Graphs undera condition

Graphs that havespecific features
while reproducing
real data

Deep Graph Generators

uThere are various features of graphs:
uAverage shortest path length, diameteruClustering coefficient, modularity
uAverage degree, power-law exponent of degree distribution, edge
densityuEigenvalues, degree centrality, betweenness centrality, PageRank

uCommon objective: How to sample graphs with desiredfeatures from the huge space of graphs.

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

Random Generation Model – WS modeluWatts-Strogatz model is a graph generation model that reproduce
small-world properties.
uSmall-world properties: For a number of nodes 𝑛, the average path length
𝐿 increases at most logarithmically with 𝑛.
uInput parameters: Number of nodes 𝑛, average degree 2𝐾, edge rewiring
probability 𝑝
1.

Create 𝑛 nodes.

2. Construct a ring lattice with an average degree of 2𝐾.
3. Rewire each edge with a probability of 𝑝．

5

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

Random Generative Model – BA modeluBarabási–Albert model is a graph generation model that reproduce
scale-free properties.
uScale-free properties: The degree distribution 𝑓(𝑘) follows 𝑓(𝑘) ∝ 𝑘 !"(2 ≤ 𝛾 ≤ 3).
uInput parameters: Number of additional edges 𝑚 , number of nodes 𝑛
1. Create a complete graph consisting of 𝑚 nodes.
2. Add nodes with 𝑚 m edges. However, the probability of an edge from thenew node is proportional to the degree of the target node it connects to.
3. Repeat Step 2 until the number of nodes reaches 𝑛.

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

Deep Graph Generators – GraphGen
uContrary to random graphgeneration, Deep Graph
Generators reproduce every
features of real graphs.

Converting edge sequence datausing Depth-First Search (DFS).

uGenerated using Long ShortTerm Memory (LSTM) in deeplearning, capable of sequence
prediction.
1. Converting the training
graphs into a sequence ofedges.
2. Inputting sequence data
and training the model topredict the subsequentedge.
3. Using the trained modelrecursively to generate thesequence.

Previous Node ID
Next Node ID

011203ʀʀʀʀʀʀʀʀʀ0')61
VHTXHQFH

2ʀʀ
ʀ

3

Training data/670(VWLPDWHG')6LSTM
predict
VHTXHQFH

and outputthe subsequentedge.

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

ʀ
ʀʀ

0
1
2

3

7
Reconstructed data

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

Deep Graph Generators – GraphTune
uA generative model capable of specifying arbitrary features bycombining Variational AutoEncoder (VAE) and LSTM [1][2].
uLearning to encode sequence data of graphs into vectors andthen decode them back into their original sequences.
uBy inputting a specified value of features as a condition vector, it
can generate graphs with specified features.





/670EDVHGGHFRGHUFRQGLWLRQDOYHFWRU
Conditionvector/DWHQWYHFWRU
RIIHDWXUHV
6DPSOLQJ/670EDVHGHQFRGHU*UDSKGDWDVHW

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

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

FRQGLWLRQDOYHFWRU
Conditionvector



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

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

Objective of Graph Generation Techniques
uObjective of Graph Generation Techniques: How to sample
graphs with desired features from the huge space of graphs.
uWS Model: Aiming to reproduce small-world properties (averageshortest path length).
uBA Model: Aiming to reproduce scale-free properties (power-law
exponent of degree distribution).
uGraphGen: Aiming to reproduce the same features as training
graph data.
uGraphTune: Aiming to tune specific features while reproducing
the other features of training graph data.

Sampling
Huge spaceof graphs

Desired featuresfeature A: 0.3
feature B: 0.8
feature C: 0.2

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

Experimental Settings for GraphTune
uGraphTune was trained using the following dataset:uSubgraphs of “who-follows-whom” graph of Twitter (Twitterdataset)uTwitter dataset:uAttempted to tune only the average shortest path length byproviding it as the condition vector while reproducing the otherfeatures of the dataset graphs.
uSpecified average shortest path lengths as 3.0, 4.0, and 5.0 in
three patterns.

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

Graphs generated by GraphTune
uDistribution of generated graphs when trained on the Twitterdataset.
uThe overall distribution matches the training graph data (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.

Graphs generated by GraphTune
uThe distribution of average shortest path length.
uWe can confirm that the distribution of generated graphs isconcentrated around the specified value.

Probability density

Specified values
3.0 4.0 5.0

Average shortest path length

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

Experiments Regarding Sequence Conversion
uRecently, we have been investigating for converting method tosequences from graphs.
uWe investigated the impact of changing the deterministic DFS
conversion to a random walk.
2nd-order random walk

Deterministic DFS
00112

Previous Node ID
Next Node ID

30112203011201or320301or …
30
3

1
2

u2nd-order random walk have 2 parameters 𝑝 and 𝑞.
u𝑝 ≫ 𝑞 ⇒ DFS-like walk, 𝑝 ≪ 𝑞 ⇒ BFS-like walk17

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

Graphs generated by GraphTuneuRMSE between the feature of generated graphs and thespecified value are evaluated.
uGenerally, the randomness of training data leads to training
difficulty, but the accuracy improved with a random walk.
uThe impact of randomness is more pronounced when the training
data size is small.

±0.343
1.580
Deterministic
DFS : 1.580 ± 0.343

parameter 𝑞p＞

DFS code

Better accuracy with randomness.
0.25

1.329±0.436

1.339±0.482

1.162±0.318

1.153±0.338

0.831±0.128

0.50

1.461±0.381

1.425±0.488

1.257±0.358

1.106±0.247

0.961±0.187

1.00

1.274±0.191

1.403±0.380

1.178±0.256

1.084±0.272

0.945±0.314

2.00

1.300±0.163

1.269±0.268

1.318±0.235

1.038±0.214

1.027±0.321

4.00

1.267±0.172

1.266±0.226

1.243±0.196

1.219±0.204

1.128±0.2840.25

0.50

1.00

2.00

4.00

parameter𝑝q18

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

Future Prospects – Conditional GenerationuGraph generation techniques for reproducing training data
have matured.
uThe current focus is shifting towards the development ofconditional generation techniques.
uImproved precision in tunability
uDiversification of tuning targets
uExpansion of tunable regions

feature A

specified values

Frequencies

Training
Generated
datadata

Generating graphs inregions not present inthe training data
(future)Generating graphs thatare similar to a subsetof training data
(current state)
Frequencies

Frequencies

Generating graphs
similar to training data(conventional)

feature A

specified values

19

feature A

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

SummaryuCurrent Status
uThe graph generation problem involves sampling graphs withdesired features from the huge space of graphs.
uGeneration techniques have become active in research, shiftingfrom random generation to deep graph generators.
uER，WS，BA model ⇒ GraphGen，GraphTune

uFuture Prospects
uConditional generation techniques, in particular, are promising as
they are still in the early stages of development.
uOnce the technology for conditional graph generation matures, it
may bring benefits to classical graph theory research as well.

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

References[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.
[3] Takahiro Yokoyama, Yoshiki Sato, Sho Tsugawa, and Kohei
Watabe, ``An Accurate Graph Generative Model with TunableFeatures'', The 32nd International Conference on Computer
Communications and Networks (ICCCN 2023) Poster Session,
Honolulu, HI, USA , 2023.
22

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

Thank you for your kind attention.

23

NagaokaNagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Deep Graph Generators – F-GraphTune
uAn enhanced version of GraphTune, a generative model
incorporating a feature estimator feedback mechanism forhigher accuracy.
uFeature estimator estimates a conditional vector representing thegraph's characteristics from the reconstructed sequence.
uAlternating training between GraphTune and Feature estimator.
6HTXHQFH*UDSK
GDWDVHW*UDSK7XQHʀʀʀʀʀʀʀʀʀ

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

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

24

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

ハイパーパラメータ
u 平均経路長など複数の特徴量を指定して精度を評価

follow

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

follow
followeru学習
u最適化関数：Adamu学習率：0.001
uWeight decay：0.0
u勾配クリップの閾値：1.0
u交互学習の反復回数：2
uバッチサイズ：37
uエポック数：10,000
25

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

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

グラフを深さ優先探索

A t=0
aB
t=2

Cb c

Time

t=1
D

t=3

Time
Time
Nodestamp u stamp v label u

Nodelabel v

Edge
label

001

A

B

a112

B

C

b2

13

B

Dc26

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

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

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

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

54

2.5

提案法
GraphTune
指定値

2RMSE

平均最短経路⻑6

平均値による⽐較

3200５

GraphTune

10.5

４
指定値

提案法

1.5

1３

RMSEによる⽐較

３４
指定値

５

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

28

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNetsComNetsLab.
Lab.

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

29

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

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

提案法

5
平均最短経路⻑

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

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

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

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

NagaokaNagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

2nd order random walk

u遷移先のノードを決定する際、今いるノードの一つ前のノードからの距離に応じて選択確率にバイアスがかかるように設定する手法。
uパラメータをp > q とするとDFS
q < p とするとBFS に近い遷移となる
325