This is the post-print version of the following article: Shohei Nakazawa, Yoshiki Sato, Kenji Nakagawa, Sho Tsugawa, and Kohei Watabe, ``A Tunable Model for Graph Generation Using LSTM and Conditional VAE,'' in Proceedings of the 41stIEEE International Conference on Distributed Computing Systems (ICDCS 2021) Poster Track, 2021. The original publication is available at https://doi.org/10.1109/ICDCS51616.2021.00119 (DOI: 10.1109/ICDCS51616.2021.00119). (c) 2021
IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works for resale orredistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

Poster: A Tunable Model for Graph Generation
Using LSTM and Conditional VAE
1st Shohei Nakazawa

2nd Yoshiki Sato

3rd Kenji Nakagawa

Graduate School of Engineering
Nagaoka University of Technology
Nagaoka, Niigata, Japans173160@stn.nagaokaut.ac.jp

Graduate School of Engineering
Nagaoka University of Technology
Nagaoka, Niigata, Japans171039@stn.nagaokaut.ac.jp

Graduate School of EngineeringNagaoka University of Technology
Nagaoka, Niigata, Japannakagawa@nagaokaut.ac.jp

4th Sho Tsugawa

5th Kohei Watabe

Faculty of Engineering, Information and Systems
University of Tsukuba
Tsukuba, Ibaraki, Japans-tugawa@cs.tsukuba.ac.jp

Graduate School of Engineering
Nagaoka University of Technology
Nagaoka, Niigata, Japank watabe@vos.nagaokaut.ac.jp

Abstract—With the development of graph applications, generative models for graphs have been more crucial. Classically,stochastic models that generate graphs with a pre-defined probability of edges and nodes have been studied. Recently, somemodels that reproduce the structural features of graphs bylearning from actual graph data using machine learning havebeen studied. However, in these conventional studies based onmachine learning, structural features of graphs can be learned
from data, but it is not possible to tune features and generategraphs with specific features. In this paper, we propose agenerative model that can tune specific features, while learning
structural features of a graph from data. With a dataset of graphswith various features generated by a stochastic model, we confirm
that our model can generate a graph with specific features.
Index Terms—Graph generation, Conditional VAE, LSTM

I. I NTRODUCTION
Graph generation has a wide range of applications, such ascommunication networks, transportation systems, databases,molecules chemistry, etc. The generative models for graphs
can be categorized into two types: statistical models andmachine-learning-based models. The traditional statisticalmodels are possible to generate a graph that reproduces asingle-aspect feature (e.g. scale-free) focused by the designerof the model. The generative models for graphs using machinelearning technology learn features from graph data and try to
reproduce features according to the data in every single aspect.
However, to our best knowledge, the existing models based onmachine learning cannot tune a specific feature while learning
multi-aspect features from graph data.
In this paper, we propose a generative model for graphsthat enables to tune specific structural features using DepthFirst Search (DFS) code and Conditional Variational Auto
Encoder (CVAE). Unlike the traditional statistical models, theproposed model learns multi-aspect features from graph data.
Though the conventional machine-learning-based models try
This work was partly supported by JSPS KAKENHI Grant Number
JP20H04172.

Universal setof graphs

Generatedgraph set
ReplaceelementFeature
vector (of)Fig. 1. Problem formulation

to reproduce similar structural features of the given graphs, theproposed model can generate a graph with specified features.
II. P ROBLEM F ORMULATIONIn this paper, we formulate the problem to generate agraph with specified features as the estimation of the mappingfrom graphs to feature vectors of graphs (see Fig.1). Let us
denote the universal set of all graphs by Ω = {G1 , G2 , . . . }.
We denote a mapping by F (·), and a graph Gi ∈ Ωis mapped to a feature vector AGi ∈ Rk by F (Gi ) =jk T1AGi = [αGα2 · · · αG] . The jth element αGof thei Giiivector AGi expresses a feature of graph Gi (i.e. the numberof nodes/edges, scaling exponent of the degree distribution,clustering coefficient, etc.). We tackle the estimation problem
to find F̂ −1 (·) that approximates F −1 (·), using a subset of Ω.
By solving this problem, it is possible to generate G′i with thefeature vector AG′i in which any element of the vector AGi isreplaced by an arbitrary value.
III. DFS C ODE
GraphGen [1] is a kind of conventional generative modelfor graphs using machine learning, and it learns sequence
data to which converted from a graph using DFS code.
DFS code, a kind of encoding method for graphs, encodesa graph into a sequence of edges using a depth-first searchon the graph. In DFS code, first of all, timestamps areadded to all nodes from 0 in order of the depth-first search.

conditional vector

実データThe vector that represents features of a graphex.
value of scaling exponent of degree distribution
value of clustering coefficient

Sequence
generativemodel A
generativemodel Bgenerativemodel Crandomvariables
Encoder(LSTM)

Decoder(LSTM)

Generated graph withspecific features

Latent vectorof features

Fig. 2. The proposed model

By adding timestamp for all nodes, edge e = (u, v) canbe annotated as 5-tuple (tu , tv , L(u), L(e), L(v)), where tuand L(·) denote a timestamp of node u and a label of aedge/node, respectively. DFS code encodes the graph so thatthe sequence composed of consecutive neighboring edges asmuch as possible while maintaining the order of timestampsof the nodes. Finally, the graph is represented as sequence of
5-tuple (tu , tv , L(u), L(e), L(v)) by DFS code.
IV. P ROPOSED M ODELWe propose a generative model for graphs that can tune
specific features using DFS code and CVAE. The proposedmodel learns a sequence dataset S = {S1 , S2 , . . . } =FminDFS (G) that is encoded from a graph dataset G withDFS code. An end element of a sequence is a vector that
represents EOS. Nodes are labeled reciprocal of their degree and edges are not labeled. We define functions that
calculate a scaling exponent of a degree distribution and aclustering coefficient by Fdeg (·) and Fcluster (·), respectively.
We construct a conditional vector set C = {c1 , . . . , cm } ={[Fdeg (G1 ) Fcluster (G1 )]T , . . . , [Fdeg (Gm ) Fcluster (Gm )]T }by using these functions for the graph dataset.
The proposed model is composed of CVAE with Long
Short Term Memory (LSTM) based encoder and decoder (seeFig. 2). The proposed model is trained with the sequence
dataset S and conditional vector set C.
Encoder: Encoder learns sequences Si and maps them
to a multivariate normal distribution according to features ofgraphs. A latent vector z is sampled from the distribution. Tolearn a condition of a graph, we input a condition vector ciwith 5-tuple of the sequence into each LSTM block.
Decoder: Decoder learns to map jth 5-tuples sj ∈ Si anda conditional vector ci to next 5-tuples sj+1 . A conditional
vector ci is concatenated with the 5-tuples and input into all
LSTM blocks. We input a latent vector z into LSTM blocks
concatenating with a hidden state.
When we generate a graph using the proposed model,
we give a sampled latent vector and a conditional vector
whose elements are tuned to specific values to the encoder
and the decoder. By giving a conditional vector, the decoder
recursively generates a sequence of 5-tuples according to theconditional vector.
V. E XPERIMENTS
We verified that the proposed model can learn structuralfeatures from graph data and generate a graph with specificfeatures. As an initial study of the tunable model, we utilize

Scaling exponent

realdata
実データ

0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2

Training data
Generated data[-1.1 0.2][-0.8 0.4]
Conditional vector[-0.5 0.6]

Fig. 3. Scaling exponent of degree distributions

a dataset generated by a kind of statistical models called
Connecting Nearest Neighbor model [2], for training, though
our ultimate goal is to generate a graph with arbitrary featuresfrom real graph data. The statistical models easily supply
massive homogeneous data with well-known features (scalefree, clustering, etc.), thereby making analysis of the behaviorof the model easier. We gather 400 graphs, each consisting of
25 nodes. The features of the graphs are shown in Table I. In
Table I, a conditional vector of a scaling exponent Fdeg (Gi ) ofa degree distribution and a clustering coefficient Fcluster (Gi )as [Fdeg (Gi ) Fcluster (Gi )].
TABLE IT RAINING DATASET
conditional vector[−1.1 0.2][−0.8 0.4][−0.5 0.6]

scaling exponent-1.1-0.8-0.5

clustering coefficient
0.2
0.4
0.6

# of data
400
400
400

The parameters in the model are set as follows. The dimension of the hidden layer of LSTM, the embedded layer, andthe linear layer to convert the output to the parameters of thenormal distribution are set to 256, 128, and 20, respectively.
The initial learning rate, the weight decay, and the threshold ofgradient clipping are set to 0.001, 0.01, and 0.015, respectively.
The number of mini-batch is 60 and the number of epochs is400.
Fig. 3 shows the distribution of the scaling exponents ofthe training data and the generated data. The vertical axis
represents the value of the scaling exponents. We can confirm
that the scaling exponents are distributed around each value(i.e., -1.1, -0.8, and -0.5) specified by the conditional vectors.
VI. C ONCLUSIONSWe proposed a tunable model that can generate a graph withfeatures specified by a conditional vector, using CVAE. It wasconfirmed that the proposed model can generate a graph withspecified features through the experiments. We have a plan
to verify the applicability of our model in a real dataset. The
verification includes additional experiments for a wide variety
of multi-aspect features, graph scale, and so on.
R EFERENCES[1] N. Goyal, H. V. Jain, and S. Ranu, “GraphGen: A Scalable Approach toDomain-agnostic Labeled Graph Generation,” in Proceedings of the Web
Conference 2020 (WWW 2020), Taipei, Taiwan, 2020, pp. 1253–1263.
[2] A. Vázquez, “Growing Network with Local Rules: Preferential Attachment, Clustering Hierarchy, and Degree Correlations,” Physical Review
E, vol. 67, no. 5, 2003.