This is the post-print version of the following article: Kohei Watabe, Shohei Nakazawa, Yoshiki Sato, Sho Tsugawa, and Kenji Nakagawa, ``GraphTune: A Learning-Based Graph Generative Model With Tunable Structural Features,'' in IEEE
Transactions on Network Science and Engineering, 2023. The original publication is available at https://doi.org/10.1109/TNSE.2023.3244590 (DOI: 10.1109/TNSE.2023.3244590). (c) 2023 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 or redistribution to servers or lists, or reuse of any
copyrighted components of this work in other works.

1

GraphTune: A Learning-based Graph Generative
Model with Tunable Structural Features
Kohei Watabe, Member, IEEE, Shohei Nakazawa, Yoshiki Sato, Sho Tsugawa, Member, IEEE,
and Kenji Nakagawa

Abstract—Generative models for graphs have been actively
studied for decades, and they have a wide range of applications.
Recently, learning-based graph generation that reproduces realworld graphs has been attracting the attention of many researchers. Although several generative models that utilize modern
machine learning technologies have been proposed, conditional
generation of general graphs has been less explored in the ﬁeld.
In this paper, we propose a generative model that allows us totune the value of a global-level structural feature as a condition.
Our model, called GraphTune, makes it possible to tune thevalue of any structural feature of generated graphs using Long
Short Term Memory (LSTM) and a Conditional Variational
AutoEncoder (CVAE). We performed comparative evaluationsof GraphTune and conventional models on a real graph dataset.
The evaluations show that GraphTune makes it possible to moreclearly tune the value of a global-level structural feature better
than conventional models.
Index Terms—Graph generation, Conditional VAE, LSTM,
Graph feature, Generative model.

I. I NTRODUCTION
Generative models for graphs have a wide range of applications, including communication networks, social networks,transportation systems, databases, cheminformatics, and epidemics. Repeated simulation on graphs is a basic approach todiscovering information in the above ﬁelds of study. However,researchers and practitioners do not always have access toenough real graph data. Generative models of graphs can
supplement a graph dataset that does not include a sufﬁcientnumber of real graphs. Moreover, generating graphs that are
not included in a dataset or future graphs can be used to
discover novel synthesizable molecules [2]–[4] or to predictthe growth of a network [5].
Classically, stochastic models that generate graphs with apre-deﬁned probability of edges and nodes have been studied,and they focus on only a single-aspect feature of graphs.
Various models [6] have been proposed in the literature,
K. Watabe, Y. Sato, and K. Nakagawa are with the Graduate School ofEngineering Nagaoka University of Technology, Nagaoka, Niigata, Japan(e-mail: k watabe@vos.nagaokaut.ac.jp; s171039@stn.nagaokaut.ac.jp; nakagawa@nagaokaut.ac.jp).
S. Nakazawa was with the Graduate School of Engineering Nagaoka
University of Technology, Nagaoka, Niigata, Japan.
S. Tsugawa is with the Faculty of Engineering, Information and
Systems University of Tsukuba, Tsukuba, Ibaraki, Japan (e-mail: stugawa@cs.tsukuba.ac.jp).
This work was partly supported by JSPS KAKENHI Grant Number
JP20H04172.
An earlier and short version of this paper was presented at the 41st IEEE
International Conference on Distributed Computing Systems (ICDCS 2021)
Poster Track [1].

including the Erdős-Rényi (ER) model [7], Watts-Strogatz(WS) model [8], and Barabási-Albert (BA) model [9]. These
stochastic models accurately reproduce a speciﬁc target structural feature (e.g., randomness [7], small worldness [8], scalefree features [9], and clustered nodes [10]). In other words,
they cannot be adapted to the real data of graphs withnumerous features, and cannot guarantee that generated graphs
completely reproduce all features of the graphs excluding thetarget feature.
Generative models for graphs using machine learning technology learn features from graph data and try to reproduce
those features according to the data in every single aspect [5],[6], [11]–[20]. For the last several years, learning-basedgraph generation has been attracting the attention of many
researchers, and several approaches have been tried in recent
studies. Although a lot of models have been proposed togenerate small graphs with the aim of designing molecules [3],[4], [14], [16], [18], some recent studies [5], [17] enable thegeneration of relatively large graphs that also include citationgraphs and social networks. In particular, the sequence databased approach, which converts a graph into sequential data
and learns the sequential data by recurrent neural networks, hasbeen successful in the ﬁeld [5], [11], [12], [17]. These studies
reproduce various features that reﬂect the global structures ofgraphs, including average shortest path length, clustering coefﬁcient, and the power-law exponent of the degree distribution.
Although the existing generative models for graphs using
machine learning technology can generate similar graphs toreal-world graphs, most of them cannot generate graphs thathave user-speciﬁed structural features. Although demand for
conditional generation of graphs with speciﬁc features iscommon, it has been less explored [19], [20].
Despite the fact that some works aim for conditional generation of graphs with a speciﬁc feature, their applicability andperformance are not sufﬁcient to generate general graphs witha speciﬁc value of a structural feature. Several models [14],[16], [18] that enable conditional generation utilize domainspeciﬁc knowledge of molecule chemistry and are not suitablefor graphs of other domains. DeepGMG [12], one of thepioneering studies of conditional graph generation, does notassume domain-speciﬁc knowledge explicitly, and can generate graphs according to a speciﬁc condition. However, thework just evaluates generation conditioned by the number ofatoms (nodes), bonds (edges), or aromatic rings (hexagons)
in a molecule. DeepGMG does not have an ability to tune
global-level structural features (e.g., average shortest path
length, clustering coefﬁcient, and the power-law exponent of

2

the degree distribution) which are difﬁcult to tune by adding
or removing a local structure of a graph such as a node,edge, or hexagon. Although attempts have been made to train
DeepGMG by graphs generated by the BA model, they havesucceeded in unconditional generation of only very small
graphs with 15 nodes [12]. CondGen [15], whose applicabledomain is not limited to molecule chemistry, has achieved
conditional generation of general graphs including citationgraphs. CondGen can reproduce global-level structural features(average shortest path length and Gini index are evaluated in
the paper [15]). CondGen succeeds in improving generationby using datasets grouped by label by inputting labels asa condition. Unfortunately, it does not provide a model tocontinuously tune a feature since it requires training datasets
grouped by labels. It does not have sufﬁcient performance
to tune the features ﬂexibly based on conditions given as acontinuous value of a global-level feature (we discuss theperformance of CondGen in Section VI).
In this paper, we propose GraphTune, a graph generativemodel that makes it possible to tune the value of any structuralfeature of a generated graph using Long Short Term Memory(LSTM) [21] and a Conditional AutoEncoder (CVAE) [22].
GraphTune adopts a sequence data-based approach for learning graph structures, and graphs are converted to sequence data
by using Depth-First Search (DFS) code that achieves successin GraphGen [17]. Unlike GraphGen, GraphTune is a CVAEbased model and the CVAE in the model is composed of an
LSTM-based encoder and decoder. GraphTune uses CVAE togenerate a graph with some speciﬁc feature, including globallevel structural features, and the feature can be continuously
tuned. Meanwhile, features other than the speciﬁed feature are
accurately reproduced in every single aspect according to thedataset that is learned.
In summary, the main contributions of this paper are as
follows:• We propose a novel learning-based graph generativemodel called GraphTune with tunable structural features.
In GraphTune, ﬂexible generation of graphs with any
feature including global-level structural features (e.g.,
average shortest path length and clustering coefﬁcient)can be achieved by giving the value of a feature as acondition vector to the CVAE-based architecture.
• We achieve elaborate reproduction of a graph dataset inevery single aspect by adopting a sequence data-based
approach for learning. GraphTune tunes the value of a
speciﬁc feature to a speciﬁed value while keeping valuesof other features within the range of values that exist in
the dataset.
• We perform empirical evaluations of GraphTune on areal graph dataset. The evaluation results establish thatthe tunability and reproducibility of graphs in GraphTune
outperforms those in conventional conditional and unconditional graph generative models. The code and dataset
used for empirical evaluations are available on GitHub1 .
The rest of this paper is structured as follows. In Section II,
we summarize related works in the ﬁeld of graph generative
1 https://github.com/wkouw1082/GraphTunemodels. Section III formulates the generation problem of agraph with a speciﬁed feature. In Section IV, we introduce the
DFS code that we adopt as a method for converting graphs intosequence data in our model. We explain the model architecture
and the training and generation algorithms of GraphTune in
Section V. Section VI shows the empirical evaluations ofGraphTune and conventional models. Section VII discusses thelimitations of the paper and future research directions. Finally,
Section VIII concludes the paper.
II. R ELATED W ORKS
Graph generation has a long history and the literature isrich with the results of many researchers. One of the mostrudimentary models, Erdős-Rényi model, generates simple
random graphs and was proposed in 1959. Around 2000, twomodels [8], [9] that reproduce structural features of graphs
called small-world networks and power-law degree distribution
attracted the attention of researchers. Since these studies werereported, various statistical graph generation methods inspiredby them have been proposed [6], [23]–[25]. A lot of thestructural features of graphs have also been quantiﬁed in thisresearch. What can be said in common with these traditional
statistical generation models is that a model focuses on one (ora few) of the many features and aims to reproduce the features(e.g., small worldness, power-law degree distribution, and local
clustering). These models cannot be adapted to real graphdatasets that have numerous features, and cannot guaranteethat the generated graphs completely reproduce every single
aspect according to the real data.
A recent trend in the ﬁeld of graph generation is learningbased models that reproduce real-world graphs. Learningbased models have evolved rapidly over the last few years,
and have attracted the attention of researchers. Learning-basedmodels have been proposed for a wide range of domains ranging from discovering new molecular structures to modelingsocial networks, and most recently, survey papers have been
published [6], [19], [20]. Various learning-based models havebeen proposed, including adjacency-based and edge-list-based
approaches. The sequence data-based approach that converts
a graph into sequential data has been particuarly successful inthis ﬁeld [5], [11], [12], [17].
Although several learning-based models for graphs havebeen proposed, conditional generation of graphs is less explored [19], [20]. The few models that achieve conditional
generation of graphs include domain-speciﬁc models in theﬁeld of molecule chemistry [3], [4], evolutionary developmental biology [26], and natural language processing [27],[28]. Unfortunately, these models cannot easily be applied
to general graphs due to the utilization of domain-speciﬁcknowledge. DeepGMG [12] and CondGen [15] have been
proposed as models applicable to general graphs. DeepGMG
adds a condition into the latent vector during the decoding
process of the graph to tune the local structure in the graphsuch as the number of nodes, edges, or hexagons. CondGen
allows tuning of global-level structural features (including
average shortest path length and Gini index at least) withgraph variational generative adversarial nets. TSGG-GAN also

3

Node

Universal setof graphs

Edge

Forward edge

Backward edge

Generatedgraph set
Replaceelement

Featurevector (of)
Original graphFig. 1. Problem formulation. A graph 𝐺𝑖 ∈ Ω is mapped to a feature vector
1 𝛼2 · · · ] 𝑇 . Elements of a𝐴𝐺𝑖 ∈ 𝑨 by a mapping 𝐹 (𝐺𝑖 ) = 𝐴𝐺𝑖 = [ 𝛼𝐺𝑖 𝐺𝑖feature vector 𝐴𝐺𝑖 for graph 𝐺𝑖 represent values of all sorts of features thatare calculated from 𝐺𝑖 . This paper tackles the inference problem of ﬁnding𝐹ˆ −1 (·) that approximates 𝐹 −1 (·), using a subset G of the universal set Ωof graphs. 𝐹ˆ −1 (·) can generate 𝐺𝑖′ by inputting the feature vector 𝐴𝐺 ′ in𝑖which any element of the vector 𝐴𝐺𝑖 is replaced by an arbitrary value.

provides conditional generation of graphs, but it focuses ontime series conditioned generation and the challenges aredifferent from ours. In TSGG-GAN, multivariate time series
data are input as node expression values to the model, andgraphs conditioned by the time series are generated.
III. P ROBLEM F ORMULATION
The graphs treated in this paper are undirected connected
graphs without self-loop. As a notational convention, a graphis represented by 𝐺 = (𝑉, 𝐸), where 𝑉 and 𝐸 denote a subset
of nodes 𝑉 ⊆ {𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑛 } and a subset of edges 𝐸 ⊆{(𝑥, 𝑦) | 𝑥, 𝑦 ∈ 𝑉 }, respectively. We let Ω = {𝐺 1 , 𝐺 2 , . . . }denote the universal set of graphs 𝐺 = (𝑉, 𝐸).
We consider a mapping 𝐹 : Ω → 𝑨, and a graph𝐺 𝑖 ∈ Ω that is mapped to a feature vector 𝐴𝐺𝑖 ∈ 𝑨 by
1 𝛼 2 · · · ] 𝑇 as shown in Fig. 1. The 𝑗th
𝐹 (𝐺 𝑖 ) = 𝐴𝐺𝑖 = [𝛼𝐺𝑖 𝐺𝑖𝑗element 𝛼𝐺𝑖 of the vector 𝐴𝐺𝑖 expresses a feature of graph𝑘 ∈ R.
𝐺 𝑖 . Every feature is represented by a real number 𝛼𝐺𝑖
For example, elements of 𝐴𝐺𝑖 represent values of features
such as the number of nodes and edges, average shortest path
length, average degree, edge density, modularity, clustering
coefﬁcient, power-law exponent of the degree distribution, andlargest component size.
In this paper, we formulate the problem of generating agraph with speciﬁed features as inferencing the inverse image
from feature vectors of graphs to graphs (see Fig.1). We deﬁne
the inverse image 𝐹 −1 (·) of the mapping 𝐹 (·), and graph 𝐺 𝑖
can be obtained by calculating 𝐹 −1 ( 𝐴𝐺𝑖 ) = {𝐺 𝑖 , . . . } with theinverse image. We tackle the inferencing problem of ﬁnding𝐹ˆ −1 (·) that approximates 𝐹 −1 (·) by using a subset G of Ω.
By solving this problem, it is possible to generate 𝐺 𝑖′ with thefeature vector 𝐴𝐺𝑖′ in which any element of the vector 𝐴𝐺𝑖
is replaced by an arbitrary value. Since we cannot use theuniversal set Ω of graphs, the inference needs to be achievedby a subset G of Ω that is contained in an accessible dataset.
IV. DFS C ODE
GraphGen [17] is a successful model for unconditional
generation in learning-based graph generation that utilizes
the DFS code. The key idea is to use the DFS code to

DFS traversal

Sequence that
contains all edges

Fig. 2. Sequence converted from an example graph. All nodes 𝑣𝑖 (𝑖 =0, 1, . . . ) are assigned timestamps 𝑡𝑣𝑖 in order of depth-ﬁrst search, thereby
obtaining a DFS traversal. The edges contained in the DFS traversal are called
forward edges, and other edges are called backward edges. A backward edge(𝑢, 𝑢′ ) is placed between forward edges (𝑤, 𝑢) and (𝑢, 𝑣), thereby obtaining
a sequence that contains all edges.

convert graphs into sequence data. The converted sequence
data are learned by LSTM in a training process. The compact
expression of a graph by sequence data with DFS code allows
GraphGen to accurately generate graphs that are similar tographs in a dataset. While we propose a novel CVAE-based
generative model for graphs different from GraphGen, ourmodel follows the sequence data-based approach by using
DFS code in the preprocess for training. In this section,
we summarize the conversion process by DFS code that iscommon to GraphGen and our model.
DFS code converts a graph to a unique sequence of edges
that retains the structural features of the graph. It is well known
that a trajectory (i.e., a sequence) of a walk on a graph reﬂects
features of the graph, including the degree distribution [29].
DFS code converts a graph to a compact sequence of length|𝐸 | by using the depth-ﬁrst search preventing revisit of edges.
In the conversion algorithm of DFS code, timestamps are
ﬁrst added to all nodes from 0 by performing the depth-ﬁrst
search. That is, all nodes 𝑣 𝑖 (𝑖 = 0, 1, . . . ) are discovered
and assigned timestamps 𝑡 𝑣𝑖 in order of depth-ﬁrst search.
The traversal of the search is represented as a sequence ofedges called a DFS traversal. In the example graph shownin Fig. 2, a DFS traversal is (𝑣 0 , 𝑣 1 ), (𝑣 1 , 𝑣 2 ), (𝑣 1 , 𝑣 3 ), andtimestamps of nodes are assigned as 𝑡 𝑣0 = 0, 𝑡 𝑣1 = 1, 𝑡 𝑣2 = 2,
and 𝑡 𝑣3 = 3. Edges contained in a DFS traversal are called
forward edges, and other edges are called backward edges.
By adding a timestamp to all nodes, edge 𝑒 = (𝑢, 𝑣) can be
annotated as a 5-tuple (𝑡 𝑢 , 𝑡 𝑣 , 𝐿 (𝑢), 𝐿 (𝑒), 𝐿 (𝑣)), where 𝑡 𝑢 and𝐿(·) denote the timestamp of node 𝑢 and the label of the edge
or node, respectively. Although the graphs treated in this paper
are graphs with unlabeled nodes and edges, the original DFS
code is designed for labeled graphs. A detailed treatment of
𝐿(𝑢), 𝐿 (𝑒) in our model is explained in Section V-A.
Based on the order of node timestamps, DFS code constructs a sequence that contains all edges in a graph. Although
the forward edges are already constructed as a sequence (i.e.,a DFS traversal), the backward edges are not included in thesequence. To construct a sequence that contains all edges ina graph, a backward edge (𝑢, 𝑢 ′ ) is placed between forward
edges (𝑤, 𝑢) and (𝑢, 𝑣). If there are multiple backward edges(𝑢, 𝑢 ′ ) and (𝑢, 𝑢 ′′ ), the timestamps of 𝑢 ′ and 𝑢 ′′ are compared,
and the smaller one is placed in front. By performing this

4

...

Sequence

...

...

...

...

...

...

Condition vector

...

...
...

Along with the sequential data fed by the DFS code, we
input condition vectors C expressing structural features of...

B. Condition Vectors Corresponding to Graphs

Generatedgraphs...

Like GraphGen, GraphTune learns a sequence dataset S ={𝐹DFS (𝐺 𝑖 )|𝐺 𝑖 ∈ G} that is converted from a graph datasetG ⊂ Ω using a conversion 𝐹DFS (·) based on DFS code.
Although the conversion 𝐹DFS (·) is basically the same as theconversion by DFS code described in Section IV, it is modiﬁed
as follows to adapt it for our problem. As mentioned above,
although the original DFS code is designed for labeled graphs,
we assume unlabeled graphs in Section III. In the sequence
dataset that is learned by GraphTune, node labels 𝐿 (𝑣) (𝑣 ∈ 𝑉)
and edge labels 𝐿(𝑒) (𝑒 ∈ 𝐸) in a 5-tuple are set as the degreeof node 𝑣 and 0, respectively. According to the DFS code
procedure described in Section IV, a graph is converted to asequence of 5-tuples. At the end of the sequences, an End
Of Sequence (EOS) token (EOS𝑡 , EOS𝑡 , EOS 𝐿 , 1, EOS 𝐿 ) is
added, where EOS𝑡 and EOS 𝐿 represent 1 + max𝑣 ∈𝑽 𝑡 𝑣 and1 + max𝑣 ∈𝑽 𝐿(𝑣) for a set 𝑽 of all nodes in the graph dataset
G. Sequences with EOS allow us to learn graphs of any size.
We can obtain a sequence 𝑺𝑖 ∈ S by further converting thesequence of 5-tuples by component-wise one-hot encoding. A
sequence 𝑺𝑖 with element 𝒔 𝑗 ∈ {0, 1} 𝑘 is input into the modelof GraphTune (see below for the model architecture).

...

Graph
dataset...

A. Sequence Data Converted from Graphs

Sampling...

We propose GraphTune – a generative model for graphsthat is able to tune a speciﬁc structural feature using DFS
code and CVAE. GraphTune is composed of CVAE with an
LSTM-based encoder and decoder. Graphs are converted tosequence data by the DFS code, and the sequence data are
input to LSTM. This section provides a detailed review ofgenerative approaches of graphs in GraphTune.

LSTM-based decoder

...

...

V. G RAPH T UNE : A G RAPH G ENERATIVE M ODEL WITH
T UNABLE S TRUCTURAL F EATURES

Latent vectorof features

LSTM-based encoder...

procedure, all backward edges are placed between forward
edges, and a sequence that contains all edges is obtained.
In the example shown in Fig. 2, the obtained sequence is(0, 1, 𝐴, 𝑎, 𝐵), (1, 2, 𝐵, 𝑎, 𝐶), (2, 0, 𝐶, 𝑏, 𝐴), (1, 3, 𝐵, 𝑐, 𝐴). Although sequences that are constructed by the above procedure
are not necessarily unique, the lexicographically smallest sequence based upon lexicographical ordering [30] is chosen as
the unique one. As a result, the graph is represented as uniquesequence of 5-tuple (𝑡𝑢 , 𝑡 𝑣 , 𝐿 (𝑢), 𝐿 (𝑒), 𝐿 (𝑣)) by DFS code.
It is not difﬁcult to reconvert a DFS code into a graph if
the DFS code exactly represents the graph. By constructing
the edges and the nodes on either side of these edges in theorder listed in the DFS code, we can reconstruct the graph.
In the case of the example shown in Fig 2, the graph can bereconstructed by the following procedure. 1) Create Node 0,
Node 1, and Edge 0-1 with labels 𝐴, 𝐵, and 𝑎 respectively;
2) Create new Node 2 and Edge 1-2 with labels 𝐶 and 𝑎,
respectively; 3) Create new Edge 2-0 with label 𝑏. 4) Create
new Node 3 and Edge 1-3 with labels 𝐴 and 𝑐, respectively.

Condition vector

Fig. 3. Proposed model composed of CVAE with a LSTM-based encoder anddecoder. A graph in the graph dataset G is converted to a sequence 𝑆𝑖 ∈ S
by using DFS code. The sequence is processed by an LSTM-based encoder.
The decoder generates a sequence of 5-tuples, and the sequence is converted
to a generated graph. The condition vector is input to both the encoder anddecoder. See the equations in Section V-C for the detailed process of themodel.

the graph dataset G to the GraphTune model for learning.
Elements 𝑐 𝑖 of vector 𝑪 𝑖 = [𝑐 𝑖 , 𝑐 𝑖 , . . . , 𝑐 𝑖 ] 𝑇 ∈ C represent
the value of the structural feature of graph 𝐺 𝑖 in graphdataset G, and 𝑐 𝑖 corresponds to the ﬁrst element of a feature
vector 𝐴𝐺𝑖 in Fig.1. Elements 𝑐 𝑖 of condition vector 𝑪 𝑖
are calculated from graph 𝐺 𝑖 by a statistical process. The
condition vector speciﬁes the structural features we focus on,
and we can choose any structural feature as the elements ofa condition vector. Structural features that can be speciﬁed ina condition vector are not limited to features regarding the
local structures of graphs such as the number of nodes andedges, but global-level structural features (including averageof shortest path length, clustering coefﬁcient and the powerlaw exponent of the degree distribution) can also be speciﬁed.
For example, if we want to tune the model by focusing on
the clustering coefﬁcient of the graphs, then we calculate aclustering coefﬁcient 𝛼cls (𝐺 𝑖 ) for each graph 𝐺 𝑖 ∈ G andconstruct a vector [𝛼cls (𝐺 𝑖 ), 𝛼cls (𝐺 𝑖 ), . . . , 𝛼cls (𝐺 𝑖 )] for each𝐺 𝑖 ∈ G.
C. Model Architecture
The proposed model is composed of CVAE with an LSTMbased encoder and decoder (see Fig. 3). A graph dataset G
is converted to a sequence dataset S in the manner explainedin Section IV. By doing this, set of condition vectors C iscalculated from the graph dataset G. The proposed model istrained with a sequence dataset S and a condition vector set
C. Sequence data 𝑺𝑖 ∈ S and the condition vector 𝑪 𝑖 ∈ C are
input into the LSTM-based encoder, and the encoder ﬁnds alatent state distribution Z of latent vectors. A latent vector 𝒛
is randomly sampled from the distribution Z, and the latentvector 𝒛 concatenated with a condition vector 𝑪 𝑖 ∈ C is input
into the LSTM-based decoder. The decoder tries to reproduce
the sequence 𝑺𝑖 . The details of the encoder and the decoder
are described below.
Encoder: Encoder 𝑞𝝓 (𝒛|𝑺𝑖 ) with parameter 𝝓 learns sequences 𝑺𝑖 and maps them to a latent vector 𝒛 according to5features of graphs. To treat sequence data, we employ a stacked
LSTM as an encoder. To encode a graph into a latent space, the𝑗th element 𝒔 𝑗 of the sequence 𝑺𝑖 and a condition vector 𝑪 𝑖
are vertically concatenated in a single vector and the vector
is embedded with a single fully connected layer 𝑓eemb . The
embedded vector is then fed into each LSTM block 𝑓enc . The
initial hidden state vector 𝒉0 is initialized as a zero vector 0.
The stacked LSTM with the embedding layer 𝑓eemb processes
a sequence 𝑺𝑖 of length 𝑘 = |𝑺𝑖 | by recursively applying the
LSTM block 𝑓enc to hidden state vector 𝒉 𝑗 . The output 𝒉 𝑘of the last LSTM block is fed to two functions 𝑓 𝝁 and 𝑓𝝈 2
implemented by single fully connected layers. As usual in
VAE, the latent state distribution is enforced as a multivariate
Gaussian distribution with dimension 𝐿. A latent vector 𝒛 isthen sampled from the latent state distribution N ( 𝝁, 𝝈 2 ) where𝝁 = 𝑓 𝝁 (𝒉 𝑘 ) and 𝝈 2 = 𝑓𝝈 2 (𝒉 𝑘 ). Summarizing the above, theprocess of the encoder part of our model is as follows:
𝒉0 = 0,(1)

𝒉 𝑗+1 = 𝑓enc (𝒉 𝑗 , 𝑓eemb ( [𝒔𝑇𝑗 , 𝑪 𝑇𝑖 ] 𝑇 ))( 𝑗 = 0, 1, . . . , 𝑘 − 1), (2)𝝁 = 𝑓 𝝁 (𝒉 𝑘 )(3)

𝝈 2 = 𝑓𝝈 2 (𝒉 𝑘 )(4)𝒛 ∼ N ( 𝝁, 𝝈 2 ).

(5)

Decoder: Decoder 𝑝𝜽 (𝑺𝑖 |𝒛) with parameter 𝜽 learns to map
a subsequence {𝒔 𝑚 |𝑚 ≤ 𝑗 } of a sequence 𝑺𝑖 , a condition vector 𝑪 𝑖 , and latent vector 𝒛 to a next element 𝒔 𝑗+1 . The decoderis also modeled by a stacked LSTM. Like the encoder, the 𝑗thelement 𝒔 𝑗 of the sequence 𝑺𝑖 is embedded into a vector bya single fully connected layer 𝑓demb , and is processed by astacked LSTM. Unlike the encoder, however, the embedded
vector is concatenated with a sampled latent vector 𝒛 and acondition vector 𝑪 𝑖 before inputting into a stacked LSTM.
The concatenated vector is fed into the LSTM block 𝑓dec ,and a sequence 𝑺𝑖 is processed by recursively applying the
LSTM block 𝑓dec . The initial hidden state 𝒉0 is calculated
by replacing 𝒔 𝑗 and 𝒉 𝑗 with a Start Of Sequence (SOS) and𝑓dinit (𝑪 𝑖 ). SOS is converted by 𝑓dsos from a vector into whicha latent vector 𝒛 and a condition vector 𝑪 𝑖 are concatenated
together, where the conversion 𝑓dsos is implemented by a fully
connected layer. The function 𝑓dinit is also implemented by afully connected layer. The output vector of each LSTM blockis fed to 5 functions 𝑓𝑡𝑢 , 𝑓𝑡𝑣 , 𝑓 𝐿𝑢 , 𝑓 𝐿𝑒 , and 𝑓 𝐿𝑣 implemented
by a fully connected layer. The 5 vectors output from these 5functions are respectively converted to probability distributions
𝝃 𝑡𝑢 , 𝝃 𝑡𝑣 , 𝝃 𝐿𝑢 , 𝝃 𝐿𝑒 , and 𝝃 𝐿𝑣 through a softmax function, andthese distributions predict one-hot vectors of 5-tuples in 𝒔 𝑗 .
In the learning process, the stacked LSTM and the fully
connected layers are trained to predict 𝒔 𝑗+1 by a concatenatedvector 𝒔˜ 𝑖 = [𝝃 𝑡𝑢 , 𝝃 𝑡𝑣 , 𝝃 𝐿𝑢 , 𝝃 𝐿𝑒 , 𝝃 𝐿𝑣 ] (See Section V-D for
detailes). Summarizing the above, the process of the decoder
part of our model is as follows:
SOS = 𝑓dsos ( [𝒛𝑇 , 𝑪 𝑇𝑖 ] 𝑇 ),(6)𝒉0 = 𝑓dec ( 𝑓dinit (𝑪 𝑖 ), [ 𝑓demb (SOS) 𝑇 , 𝒛𝑇 , 𝑪 𝑇𝑖 ] 𝑇 ),𝑇

𝒉 𝑗+1 = 𝑓dec (𝒉 𝑗 , [ 𝑓demb (𝒔 𝑗 ) , 𝒛𝝃 𝑡𝑢 = Softmax( 𝑓𝑡𝑢 (𝒉 𝑗 )),𝑇, 𝑪 𝑇𝑖 ] 𝑇 ),

(7)
(8)
(9)

𝝃 𝑡𝑣 = Softmax( 𝑓𝑡𝑣 (𝒉 𝑗 )),(10)

𝝃 𝐿𝑢 = Softmax( 𝑓 𝐿𝑢 (𝒉 𝑗 )),(11)

𝝃 𝐿𝑒 = Softmax( 𝑓 𝐿𝑒 (𝒉 𝑗 )),(12)

𝝃 𝑡𝑣 = Softmax( 𝑓 𝐿𝑣 (𝒉 𝑗 )),(13)𝒔˜ 𝑗 = [𝝃 𝑇𝑡𝑢 , 𝝃 𝑇𝑡𝑣 , 𝝃 𝑇𝐿𝑢 , 𝝃 𝑇𝐿𝑒 , 𝝃 𝑇𝐿𝑣 ] 𝑇 .

(14)

D. Training
Using sequence data fed by DFS code and structural feature
vectors calculated by a statistical process, GraphTune infers
the functions mentioned in Section V-C. In the training process, we input sequence data 𝑺𝑖 ∈ S and a condition vector
𝑪 𝑖 ∈ C into the proposed model, and obtain a latent vector 𝒛
and a predicted sequence 𝑺˜ 𝑖 = {˜𝒔 𝑗 | 𝑗 = 0, 1, · · · , 𝑘 }.
Following the optimization manner of VAE [22], our modelwith encoder 𝑞𝝓 (𝒛|𝑺𝑖 ) and decoder 𝑝𝜽 (𝑺𝑖 |𝒛) considers the twocomponents−DKL (𝑞𝝓 (𝒛|𝑺𝑖 )|| 𝑝(𝒛))

and

(15)

E𝑞𝝓 (𝒛 |𝑺 𝑖 ) [ 𝑝𝜽 (𝑺𝑖 |𝒛)]

(16)of the variational lower-bound, where DKL (·) and 𝑝(𝒛) denote
the Kullback-Leibler divergence and the multidimensional
standard normal distribution N (0, 𝑰) with dimension 𝐿, respectively. Like the normal VAE [22], the ﬁrst component
Eq. (15) regularizes the latent state distribution to be thestandard normal distribution, and can be written as
1∑(1 + log((𝜎𝑙 ) 2 ) − (𝜇𝑙 ) 2 − (𝜎𝑙 ) 2 ). (17)2 𝑙=1𝐿

Lossenc ( 𝝁, 𝝈) =The second component Eq. (16) is a reconstruction loss that
ensures the predicted sequence is similar to the input sequence
from the dataset. For our model, the reconstruction loss isdeﬁned for a sequence data 𝑺𝑖 and a predicted sequence 𝑺˜ 𝑖by1 ∑∑𝒔 𝑗 (𝑐) log( 𝒔˜ 𝑗 (𝑐)),|𝑺| 𝑖=0 𝑐|𝑺 |Lossdec ( 𝑺˜ 𝑗 , 𝑺 𝑗 ) = −(18)

where 𝒔(𝑐) and 𝒔˜ (𝑐) represent component 𝑐∈{𝑡𝑢 , 𝑡 𝑣 , 𝐿 𝑢 , 𝐿 𝑒 , 𝐿 𝑣 } of 𝑠𝑖 and 𝒔˜ 𝑖 , respectively.
By uniting the two losses with the idea of 𝛽-VAE [31],the proposed model is optimized by gradient descent on thefollowing loss with weight 𝛽.
Loss( 𝝁, 𝝈, 𝒔˜ 𝑗 , 𝒔 𝑗 ) = 𝛽 · Lossenc ( 𝝁, 𝝈) + Lossdec ( 𝒔˜ 𝑗 , 𝒔 𝑗 ). (19)The loss is backpropagated to the model, and we use thereparameterization trick [22] for backpropagation through theGaussian latent variable.
The detailed algorithm of the training is shown in Algorithm 1. For a given sequence dataset S = {𝑺1 , 𝑺2 , . . . } andthe condition vector set C = {𝑪 1 , 𝑪 2 , . . . } corresponding to thedataset, Algorithm 1 returns learned encoder functions ( 𝑓eemb ,𝑓enc , 𝑓 𝝁 , and 𝑓𝝈 2 ) and decoder functions ( 𝑓dinit , 𝑓demb , 𝑓dec ,𝑓𝑡𝑣 , 𝑓𝑡𝑣 , 𝑓 𝐿𝑢 , 𝑓 𝐿𝑒 , and 𝑓 𝐿𝑣 ). First, the total loss is initialized(Line 2). The algorithm then iterates over all sequences 𝑺𝑖(Lines 3-23). An encoder recursively calculates 𝒉 𝑗 and a latentvector 𝒛 is sampled (Lines 4-9). The loss for regularization of

6

Algorithm 1 Training of GraphTune
Input: Graph dataset S = {𝑺1 , 𝑺2 , . . . },Condition vector set C = {𝑪 1 , 𝑪 2 , . . . }Output: Learned functions 𝑓eemb , 𝑓enc , 𝑓 𝝁 , 𝑓𝝈 2 , 𝑓dinit , 𝑓demb ,𝑓dec , 𝑓𝑡𝑢 , 𝑓𝑡𝑣 , 𝑓 𝐿𝑢 , 𝑓 𝐿𝑒 , and 𝑓 𝐿𝑣
1: repeat2:
Loss ← 0
3:
for 𝑖 from 1 to |S| do
4:𝒉0 ← 05:
for 𝑗 from 0 to 𝑘 − 1 do
6:
𝒉 𝑗+1 ← 𝑓enc (𝒉 𝑗 , 𝑓eemb ( [𝒔𝑇𝑗 , 𝑪 𝑇𝑖 ] 𝑇 ))7:
end for8:𝝁 ← 𝑓 𝝁 (𝒉 𝑘 ); 𝝈 2 ← 𝑓𝝈 2 (𝒉 𝑘 )9:𝒛 ∼ N ( 𝝁, 𝝈 2 )10:Loss ← Loss + 𝛽 · Lossenc ( 𝝁, 𝝈)
11:𝑺˜ 𝑖 ← []12:
SOS ← 𝑓dsos ( [𝒛𝑇 , 𝑪 𝑇𝑖 ] 𝑇 )13:𝒉0 ← 𝑓dec ( 𝑓dinit (𝑪 𝑖 ), [ 𝑓demb (SOS) 𝑇 , 𝒛𝑇 , 𝑪 𝑇𝑖 ] 𝑇 )14:for 𝑗 from 0 to 𝑘 − 1 do
15:
for 𝑐 ∈ (𝑡𝑢 , 𝑡 𝑣 , 𝐿 𝑢 , 𝐿 𝑒 , 𝐿 𝑣 ) do16:
𝝃 𝑐 ← Softmax( 𝑓𝑐 (𝒉 𝑗 ))17:
end for18:𝒔˜ 𝑗 ← [𝝃 𝑇𝑡𝑢 , 𝝃 𝑇𝑡𝑣 , 𝝃 𝑇𝐿𝑢 , 𝝃 𝑇𝐿𝑒 , 𝝃 𝑇𝐿𝑣 ] 𝑇
19:
𝑺˜ 𝑖 ← [ 𝑺˜ 𝑖 , 𝒔˜ 𝑗 ]20:
𝒉 𝑗+1 ← 𝑓dec (𝒉 𝑗 , [ 𝑓demb (𝒔 𝑗 ) 𝑇 , 𝒛𝑇 , 𝑪 𝑇𝑖 ] 𝑇 )21:
end for
22:
Loss ← Loss + Lossdec ( 𝑺˜ 𝑖 , 𝑺𝑖 )23:
end for24:
Back-propagate Loss and upate weights
25: until stopping criteria

the latent state distribution is added to the total loss (Line 10).
A predicted sequence 𝑺˜ 𝑖 , SOS and 𝒉0 , are initialized by an
empty vector, 𝑓dsos , and 𝑓dinit , respectively (Line 11-13). 𝒉 𝑗
is converted to probability distributions of one-hot vectorsof 5-tuples through the function 𝑓𝑡𝑣 , 𝑓𝑡𝑣 , 𝑓 𝐿𝑢 , 𝑓 𝐿𝑒 , and 𝑓 𝐿𝑣
(Lines 15-17). Next, the distribution is vertically concatenatedinto a single vector 𝒔˜ 𝑗 , and these vectors {˜𝒔 𝑗 | 𝑗 = 1, 2, . . . , |𝑺𝑖 |}are horizontally concatenated into a predicted sequence 𝑺˜ 𝑖(Lines 18-19). A decoder also recursively calculates 𝒉 𝑗 forthe prediction of the next 5-tuple (Line 20). The reconstruction
loss calculated from the concatenated probability distributions
is added to the total loss (Line 22). Lastly, the weights ofall functions are updated by back-propagating the total loss
(Line 24). The above procedures are iterated until the total
loss converges (Line 25).

E. Generation
When we generate graphs with speciﬁc structural features,
GraphTune recursively generates sequential data in the DFS
code format using learned functions. We give a sampled latentvector and a condition vector whose elements are tuned to
speciﬁc values to the decoder. By giving a condition vector, thedecoder recursively generates a sequence of 5-tuples according
to the condition vector. Finally, we get a graph with speciﬁc

structural features by inverse converting from sequence data
to a graph.
The entire procedure for the generation of a graph witha speciﬁc condition is summarized in Algorithm 2. The
input and output of the algorithm are a condition vector 𝑪with speciﬁc values and sequence data of a graph with thecondition, respectively. Firstly, a generated sequence data 𝑺
and an iterator variable 𝑗 are initialized (Lines 1-2). For thegeneration, a latent vector 𝒛 is sampled from the standard
normal distribution N (0, 𝑰 2 ) (Line 3). 𝒉0 is calculated fromthe sampled latent vector 𝒛 and the given condition 𝑪 (Lines 45). To obtain the next 5-tuple in a predicted sequence, theelement-wise distributions 𝜉𝑡𝑢 , 𝜉𝑡𝑣 , 𝜉 𝐿𝑢 , 𝜉 𝐿𝑒 , and 𝜉 𝐿𝑣 of 5-tuple
are calculated, and predicted values 𝒔ˆ (𝑡𝑢 ), 𝒔ˆ (𝑡 𝑣 ), 𝒔ˆ (𝐿 𝑢 ), 𝒔ˆ (𝐿 𝑒 ),and 𝒔ˆ (𝐿 𝑣 ) are sampled from these distributions, respectively(Lines 7-10). The predicted values 𝒔ˆ (𝑡𝑢 ), 𝒔ˆ (𝑡 𝑣 ), 𝒔ˆ (𝐿 𝑢 ), 𝒔ˆ (𝐿 𝑒 ),and 𝒔ˆ (𝐿 𝑣 ) of each element of 5-tuple are vertically concatenated into a single vector 𝒔ˆ 𝑗 , and the concatenated vector𝒔ˆ 𝑗 is horizontally concatenated to the predicted sequence 𝑺(Lines 11-12). 𝒉 𝑗 is recursively calculated for the predictionof the next 5-tuple, and the iterator variable 𝑗 is updated(Lines 13-14). To stop the generation of the sequence inﬁnite size, the iteration ﬁnishes if at least one element of theprediction 𝒔ˆ 𝑗 of 5-tuple is EOS (Line 15). A graph with a
speciﬁc condition 𝑪 is easily constructed from the sequence
𝑺 at the end of the algorithm.
Most parts of the algorithm of GraphTune are deterministic, but the latent vector 𝒛 and the 5-tuple in DFS codeare randomly sampled from estimated distributions. By the
sampling process, GraphTune is possible to generate a wide
variety of graphs under a single condition. Based on the basic
concept of VAE, the ﬁnal output of the encoder of GraphTune
is not the latent vector 𝒛, but the parameters 𝝁 and 𝝈 of thenormal distribution over the latent space. The latent vector𝒛 is sampled from the normal distribution speciﬁed by theparameters. Similarly, the decoder output in GraphTune is a
distribution from which 5-tuples in DFS code will be sampled.
In the generating process of a graph from a DFS code, weconstruct the graph by creating nodes and edges based on thetimestamps of the nodes in the DFS code that is output by the
decoder. Since this research focuses on generating unlabeledgraphs, we ignore label information in the DFS code. Although
GraphTune attempts to faithfully reproduce the DFS code in
the graphs of the dataset, GraphTune can not guarantee fullcompliance with the rules of DFS code. Therefore, 5-tuples
that violate the rule of DFS code may be output. A typicalcase is that a 5-tuple contained in the DFS code reappears in
subsequent DFS code. To solve these problems, we ignore any
5-tuple that conﬂicts with the 5-tuples that appear in the DFS
code before that.
F. Necessity of CVAE Architecture
The most distinctive point of GraphTune is that it allows
continuous tuning of a structural feature of generated graphs
by giving condition vectors to the decoder and the encoder
in VAE, respectively. Although the architecture of GraphTune is similar to that of GraphGen, GraphTune differs from

7

Algorithm 2 Generation of a graph with a speciﬁc condition
Input: Condition vector 𝑪 with speciﬁc values
Output: Sequence data 𝑺 of a graph 𝐺 with a speciﬁc
condition 𝑪
1: 𝑺 ← []2: 𝑗 ← 0
3: 𝒛 ∼ N (0, 𝑰 2 )𝑇
4: SOS ← 𝑓dsos ([𝒛𝑇 , 𝑪 ] 𝑇 )𝑇
5: 𝒉0 ← 𝑓dec ( 𝑓dinit (𝑪), [ 𝑓demb (SOS) 𝑇 , 𝒛𝑇 , 𝑪 ] 𝑇 )6: repeat7:
for 𝑐 ∈ (𝑡 𝑢 , 𝑡 𝑣 , 𝐿 𝑢 , 𝐿 𝑒 , 𝐿 𝑣 ) do8:
𝝃 𝑐 ← Softmax( 𝑓𝑐 (𝒉 𝑗 ))9:𝒔ˆ (𝑐) ∼ 𝝃 𝑐
10:
end for𝒔ˆ 𝑗 ← [ˆ𝒔 (𝑡𝑢 ) 𝑇 , 𝒔ˆ (𝑡 𝑣 ) 𝑇 , 𝒔ˆ (𝐿 𝑢 ) 𝑇 , 𝒔ˆ (𝐿 𝑒 ) 𝑇 , 𝒔ˆ (𝐿 𝑣 ) 𝑇 ] 𝑇
11:12:𝑺 ← [𝑺, 𝑠ˆ 𝑗 ]13:
𝒉 𝑗+1 ← 𝑓dec (𝒉 𝑗 , [ 𝑓demb ( 𝒔ˆ 𝑗 ) 𝑇 , 𝒛𝑇 , 𝑪 𝑇 ] 𝑇 )14:𝑗 ← 𝑗 +1
15: until ∃𝑐 : 𝒔ˆ (𝑐) = EOSGraphGen in that it is divided into an encoder and a decoder.
Our goal is to tune only the feature that is speciﬁed in thecondition vector while maintaining the values of the otherfeatures. In order to achieve this goal, it is important not only
to simply learn graph features, but also to separate the features
into the feature speciﬁed in the condition vector (conditioned
features) and the other features (unconditioned features). Since
the decoder of GraphTune is given a condition vector alongwith a latent vector, it can proceed with learning to reduce thereconstruction loss based on accurate information regarding
conditioned features. Therefore, the latent vector does nothave to contain information about conditioned features. On
the contrary, it is desirable that the latent vector contains only
information about unconditioned features. In GraphTune, by
explicitly giving the encoder a condition vector as well as
the decoder, the encoder can remove information about theconditioned features from the latent vector.
The architecture of GraphTune, which provides condition
vectors to both the encoder and the decoder in VAE, is a reasonable architecture for accurately tuning features of generated
graphs. An architecture that inputs a condition vector to either
the encoder or the decoder does not have signiﬁcant tunability.
The detailed experimental results that support the necessity of
the CVAE-based architecture of GraphTune are presented in
Section VI-E.
VI. E XPERIMENTS
We verify that GraphTune can learn structural featuresfrom graph data and generate a graph with speciﬁc structural features. In this section, we ﬁrst present performance
evaluations of GraphTune on a graph dataset generated with
WS model [8], which is representative of statistical graphgeneration models. In addition, we also present a performance
evaluation of GraphTune on a real graph dataset extracted froma who-follows-whom network of Twitter. Through the evaluations, we show that GraphTune yields better performance

than the conventional generative models, namely, GraphGen
and CondGen.
A. Baselines
To conﬁrm the basic characteristics of GraphTune in a conditional graph generation task, we compare the performanceof GraphTune with two baseline models: GraphGen [17] andCondGen [15].
GraphGen: GraphGen employs a scalable approach todomain-agnostic labeled graph generation and is a representative model that adopts a sequence data-based approach. As
we mentioned in the introduction, the sequence data-based
approach is one of the most successful approaches in the ﬁeldof learning-based graph generation. GraphGen was comparedwith DeepGMG [12] and GraphRNN [11] in [17]. It wasreported that GraphGen is superior to these methods in termsof the reproduction accuracy of graph structural features.
Although GraphGen is an outstanding model, it unfortunately
does not provide conditional generation of graphs. Hence,
GraphGen is a baseline in terms of the reproduction accuracyof graph structural features, and it does not provide a baseline
regarding the ability of conditional generation. In the evaluations in Section VI, we use the parameters recommendedin [17].
CondGen: CondGen employs conditional structure generation through graph variational generative adversarial nets andis one of the few models that achieves a conditional generation
for general graphs that is not limited to a speciﬁc domain.
To the best of our knowledge, CondGen is almost the only
model that is oriented towards the reproduction of globallevel structural features in human relationship graphs including
social networks and citation networks. GraphGen was compared with GraphVAE [13], NetGAN [5], and GraphRNN [11]in [15]. The study [15] reports that CondGen records thebest performance in most cases. Since CondGen supports aconditional generation of graphs, CondGen provides a baseline
regarding the ability of conditional generation. Unlike GraphTune specifying a value of a feature after a training process,
CondGen requires training datasets grouped by labels. Hence,
when we specify another condition, CondGen needs to relearn
another dataset grouped by the conditions. In the evaluationsin Section VI, we use the parameters recommended in thepaper [15]. Since the number of nodes and edges are required
as input parameters in the generation, the number of nodes
and edges of sampled graphs with a speciﬁc label from thedataset are used.
B. Parameters and Training Dataset
The parameters of a model in GraphTune are set as follows.
For the encoder part of our model, we use 2-layer LSTM
blocks for 𝑓enc , which has a hidden state vector of dimension
223. The dimension of 𝑓eemb is set to 227. The dimensions ofvectors 𝝁 and 𝝈 2 , that is, the dimension of the latent vector 𝒛,
are set to 10. Three-layer LSTM blocks for 𝑓dec which havea hidden state vector of dimension 250, is adopted for the
decoder part. The dimensions of 𝑓dsos and 𝑓demb are set to250. We use Adam optimizer to train the neural networks for810000 epochs with a batch size of 37 and an initial learning
rate of 0.001 for training. The weight 𝛽 for the calculation ofloss is set to 3.0.
To investigate the basic performance of GraphTune, weconstructed a graph dataset (WS dataset) generated by WS
model. As the parameters of WS model, we set average degree
𝐾 to 3, and randomly change rewiring probability 𝑝 within
the range [0.1, 0.6]. As we mentioned in the introduction,
since stochastic graph generation models generate graphswith simple algorithms, they focus on only a single-aspectfeature. Therefore, in graph datasets that are generated bythese models, a part of the features that are not focused on
are almost invariable. In the case of WS model, since it isa model that aims to reproduce small worldness, the average
shortest path length changes greatly, but the other features arealmost invariable. Our WS dataset contains average shortest
path lengths ranging from 5.32 to 17.0.
To evaluate the performance of GraphTune on real graphdataset, we sampled data from the Twitter who-follows-whomgraph in the Higgs Twitter Dataset [32]. To prepare a humanrelationship graph dataset with sufﬁcient size for training andevaluation, we sampled 2000 graphs from a single huge graphincluded in the Higgs Twitter Dataset with 456,626 nodes and
14,855,842 edges. A graph in the dataset for the evaluations
is sampled by performing a random walk that starts from arandomly selected node. An initial node of a random walkis selected following a uniform distribution. The edge forthe next hop is randomly selected from all edges with equal
probability. The random walk ends up after 50 nodes arefound, and a graph in the evaluation dataset is an induced
subgraph that is composed of the nodes included in the random
walk. Note that an edge can be included in the evaluation
dataset if both nodes are included in the random walk, even
if the edge is not included in the random walk. Although
the original Higgs Twitter Dataset is a directed graph, we
ignore the directions of all edges in this study since ourmodel is designed for undirected graphs. This dataset withsmall and uniform size graphs is suitable for evaluating thebasic tunability of global-level features without being affectedby the difﬁculty of reproducing heterogeneous or very large
graphs. We split the dataset into two parts: the training set andvalidation set. The size ratio of the training set and validation
set are 90% and 10%, respectively.
C. Structural Features
As structural features of graphs, we focus on the following
5 features: average of shortest path length, average degree,
modularity [33], clustering coefﬁcient, and a power-law exponent of a degree distribution [34]. The value of modularity is
calculated for modules consisting of nodes divided by the Louvain algorithm [35]. We calculate the power-law exponent of
the degree distribution by the powerlaw Python package [34].
These global-level structural features are selected from survey
papers [36], [37] on the measurement of complex network
structures, and they have been widely used as graph featuresof human relationship graphs [38], [39]. Compared with local
structures such as the number of nodes and edges, these globallevel structural features are difﬁcult to tune by adding or

removing local structure to or from a graph, such as a node,edge, or hexagon. Needless to say, adding or removing local
structures to or from a graph can change the value of globallevel structural features. However, if we control a value of afeature to a speciﬁc value on a graph, we must understandthe structure of the whole graph and consider the effect of thelocal structure on the value of the feature. For the creation of
the dataset, the value of features is rounded to one decimal
place.
D. Performance Evaluations
In this section, we show that GraphTune can generate graphswith speciﬁc structural features. Performance comparison
among three methods (GraphTune, CondGen, and GraphGen)and detailed analysis of generated graphs are provided.
We trained GraphTune, CondGen, and GraphGen using thetraining set described in Section VI-B, and generated graphswith speciﬁc conditions. For GraphGen, a single model istrained with the training set, since GraphGen does not provide
conditional generation of graphs. For GraphTune and CondGen, the models were trained individually for each featurethat is focused on; that is, we trained 5 different models foreach single feature. After the training process, we generated
300 graphs for each model. For each feature, we picked up
3 typical values of a feature from the range of values of
the training set as the values of the condition vectors. In thegeneration process, we give the condition vectors to models ofGraphTune. Since CondGen requires training sets grouped bylabels, the training sets are divided into 3 groups at the middleof the typical values. Note that we cannot give a condition toGraphGen since it is designed for unconditional generation.
The summary of the results of generation for WS dataset
and Twitter dataset are listed in TABLE I and II, respectively.
The values of features other than average shortest path lengthof graphs in WS dataset are almost invariant, we list only
results regarding average shortest path length in TABLE I. In
TABLE II regarding the results for Twitter dataset, we list
the results for all 5 features shown in Section VI-C. The
values in the columns of GraphTune, CondGen, GraphGen
represents average values of features in graphs generated byeach model. Since GraphGen does not provide conditional
generation, the same value is listed for different conditions.
We can consider that a method has better performance if theaverage value is closer to the values of the condition in thetunability of a condition. The best performance achieved undereach condition for a particular feature is emphasized in boldfont.
As shown in TABLE I, GraphTune well reproduces the shiftof the average shortest path length with the change in rewiring
probability on WS dataset. The value of the average shortest
path length of the graphs generated by GraphTune is close
to the value speciﬁed by the condition vector. The average
shortest path length for CondGen cannot be calculated sincemost of generated graphs are unconnected. Then, we depict “–” for unconnected graphs. For reference, the average shortest
path length of the largest component is given in parenthesis
for unconnected graphs. In contrast, all graphs generated by9GraphTune were connected graphs. This is an advantage ofthe sequence data-based approach taken by GraphTune (andGraphGen). Even comparing the values of the average shortest
path length of the largest components, it can be conﬁrmed thatthe tunability of GraphTune is higher than that of CondGen.
According to the results in TABLE II, we can conﬁrm thatthe graphs generated by GraphTune have high reproduction
accuracy and clearly change depending on the conditions.
GraphGen generally reproduces real data well, but GraphTune,
which adopts sequence-based generation like GraphTune, hassimilar performance. A similar conclusion can be drawn fromthe visualized graphs of each model shown in Fig. 5. In the
results of average degree and clustering coefﬁcient, information of condition vector works effectively, and GraphTune has
better reproduction accuracy than GraphGen. In tunability offeature, GraphTune achieves the best performance in most of
the features. While GraphTune can accurately tune the averageof shortest path length, the value for CondGen cannot becalculated since all generated graphs are unconnected. Since
we explicitly give information on the number of nodes andedges in the graph of the training dataset, CondGen canaccurately tune the value of average degree. GraphTune is alsoquite accurate even though such information is not given. With
regard to modularity and clustering coefﬁcients, GraphTune
outperforms CondGen in terms of both reproduction accuracyof real data and tunability. For highly complex statistics
such as the power-law exponent, the value of the feature issomewhat tunable but the result is a little unstable.
To investigate the detailed performance of GraphTune, we
depict the distributions of the values of the global-level structural features. In Fig. 4, we plot pairwise relationships of thevalues of the features on generated graphs by GraphTune.
While maintaining the value of the other features of thegenerated graphs are in the range of real data, the distributionsof values of an average shortest path length on GraphTune
results are clearly distinguishable. According to the scatterplots in Fig. 4, we can conﬁrm that the distribution of points
in the real graph data and that of the generated graph dataalmost overlap. As a result, the relationships between any two
features are accurately reproduced, and it was achieved thatthe reproduction of a graph dataset in every single aspect.
E. Ablation Study
We performed an ablation study to demonstrate the validityof the architecture of GraphTune. When giving a condition
to the LSTM-based VAE in GraphTune, a condition vector is
input to 3 spots: the input sequence of the encoder (Eq. (2)),
the input sequence of the decoder (Eq. (8)), and the hidden
layer of the decoder (Eq. (7)). To evaluate the impact of thecondition vector on the tunability, we prepared 3 versionsof GraphTune by removing one of the 3 spots at which a
condition vector is input. We trained each model with Twitter
dataset and generated 300 graphs. Each model is trained withthe same parameters as the experiment regarding the average
shortest path length shown in Section VI-D. We calculated
the average shortest path length for all generated graphs, andcalculated the Root Mean Squared Error (RMSE) with thevalue speciﬁed in the condition vector as the true value. The
results of RMSE for each model are listed in TABLE III.
As shown in TABLE III, RMSE of the original GraphTuneis the lowest value among all models. According to theresults, although 3 spots of input of a condition vector in theGraphTune architecture seem redundant, we can understandthat all condition inputs contribute to improving its tunability.
The most signiﬁcant contributor to the tunability is the condition vector that is concatenated to the input sequence of theencoder. This suggests that removing the information related
to the speciﬁed feature from the latent vector is important for
the graph generation. Meanwhile, the condition vector thatis concatenated to the input sequence of the decoder also
contributes signiﬁcantly to the tunability.
F. Latent Space Analysis
Together with the above evaluations regarding tunability,
we analyzed the structure of the latent state distribution Z in
GraphTune. The reference [40] focuses to enforce disentangled
representations of model parameters in a graph generation
based on the idea of 𝛽-VAE [31]. Although the proposedmodel in the reference [40] cannot provide conditional generation of graphs, the authours reported that it is possible
to construct a generative model that correlates the numberof nodes 𝑛 and edge density 𝑝 with the elements of thelatent vector 𝑧 in a simple ER model. We performed anexperiment with the graph dataset (ER dataset) generated
by the same conditions as ER model in reference [40], andveriﬁed the structure of the latent space and generation results.
All parameters in GraphTune are the same as those evaluatedin Section VI-D, except the dimension of the latent space is
set to 4 which is the same as the experimental conditions inreference [40]. In the learning process, we used connected
graphs in ER dataset, and gave edge density 𝑝 as a condition
vector.
Fig. 6 shows the relationship between each element 𝑧𝑖 ofthe latent vector 𝒛 and edge density 𝑝, and it is conﬁrmed thatthe latent space of GraphTune is not disentangled according tothe ﬁgure. This analysis that visualizes the correlation between𝒛 and 𝑝 is adopted in the evaluation in reference [40]. On theother hand, from the pairwise relationship of 𝑛 and 𝑝 shownin Fig. 7, we can clearly conﬁrm the correlation between
values of condition vectors and edge density 𝑝 of the generated
graphs. In this result, the correlation coefﬁcient between valuesof the condition vector and 𝑝 is 0.95, and it is higher thanthe correlation coefﬁcient of 0.35 between the element oflatent vector 𝑧 𝑖 and 𝑝 reported in the reference [40]. It should
be noted that 𝑝 depends on a condition, whereas 𝑛 can be
determined independently of a condition. The above resultsmean that GraphTune achieves to generate graphs depending
only on the value of the condition given to the decoder, noton the information of the latent space.
VII. L IMITATIONS AND F UTURE D IRECTIONS
We recognize that there are some limitations of generation
by GraphTune, which suggest that GraphTune has potential
for future expansion.

10

TABLE IT HE AVERAGE SHORTEST PATH LENGTH IN GRAPHS GENERATED BY G RAPH T UNE , C OND G EN , AND G RAPH G EN FOR WS DATASET. W E PRESENT THE
SAME VALUE FOR ALL RESULTS OF G RAPH G EN FOR EACH FEATURE SINCE G RAPH G EN DOES NOT PROVIDE CONDITIONAL GENERATION OF GRAPHS .
T HE BEST PERFORMANCE BETWEEN G RAPH T UNE AND C OND G EN ACHIEVED UNDER EACH CONDITION IS HIGHLIGHTED IN BOLD FONT.
Global-level structural feature

Condition

GraphTune
average

CondGenaverage

GraphGenaverage

WS dataaverage(25-percentile / median / 75-percentile)

Average of shortest path length

7.5
10.0
12.5

10.8
14.5
16.8

– ( 2.28 )– ( 2.27 )– ( 2.30 )

9.51

9.10
(7.67 / 8.74 / 10.2)

TABLE IIAVERAGE VALUES OF 5 GLOBAL - LEVEL STRUCTURAL FEATURES IN GRAPHS GENERATED BY G RAPH T UNE , C OND G EN , AND G RAPH G EN FOR T WITTERDATASET. W E PRESENT THE SAME VALUE FOR ALL RESULTS OF G RAPH G EN FOR EACH FEATURE SINCE G RAPH G EN DOES NOT PROVIDE CONDITIONAL
GENERATION OF GRAPHS . T HE BEST PERFORMANCE BETWEEN G RAPH T UNE AND C OND G EN ACHIEVED UNDER EACH CONDITION FOR A PARTICULARFEATURE IS HIGHLIGHTED IN BOLD FONT.
Global-level structural feature

Average of shortest path length

Average degree

Modularity

Clustering coefﬁcientPower-law exponent of a degree distribution

Condition

GraphTune
average

CondGenaverage

3.0
4.0
5.0
3.0
3.5
4.0
0.40
0.55
0.70
0.1
0.2
0.3
2.6
3.0
3.4

3.05
4.02
5.43
3.26
3.60
3.90
0.389
0.430
0.507
0.177
0.181
0.217
2.91
2.98
3.50

– ( 2.18 )– ( 2.24 )– ( 2.27 )
2.93
3.48
4.51
0.299
0.325
0.336
0.344
0.366
0.409
4.10
3.90
3.80

GraphGenaverageReal data
average(25-percentile / median / 75-percentile)

4.59

4.26
(3.40 / 4.09 / 4.84)

2.96

3.59
(2.96 / 3.44 / 3.92)

0.567

0.550
(0.509 / 0.563 / 0.617)

0.08460.203(0.152 / 0.196 / 0.251)

5.48

4.28
(2.91 / 3.48 / 4.23)

TABLE IIIRSME FOR EACH G RAPH T UNE VERSION . W E VERIFY 3 VERSIONS BY REMOVING ONE OF THE 3 SPOTS AT WHICH A CONDITION VECTOR IS INPUT. T HE
SMALLEST VALUES OF RMSE AMONG ALL MODELS ACHIEVED UNDER EACH CONDITION ARE HIGHLIGHTED IN BOLD FONT.
Global-level structural feature

Condition

Average of shortest path length

3.0
4.0
5.0

GraphTune
Original
RMSE
0.70
1.15
1.92

GraphTune without
condition on encoder
RMSE
3.06
3.22
4.17

Generation of Large Graphs: Although the number ofnodes on graphs in our dataset is relatively large comparedwith the datasets that have been evaluated in studies regarding
learning-based conditional generations of graphs, it is smallin terms of social networks. In the results [17] of unconditional generation with GraphGen, which adopts sequencebased generation like GraphTune, the average number of nodesof graphs generated by GraphGen is at most 54.01 nodes.
While GraphTune generates graphs of almost the same sizeas the graphs that GraphGen generates, it was unfortunately
not able to generate graphs with over 100 nodes. Moreinnovation is needed to overcome this limitation. Hierarchicalgeneration [18] is relatively easy to implement but is expected
to be effective and is a promising option. Another promising
option is a combination of deep learning and traditional statistical graph generation. We consider that the sequence-based
generation in GraphTune has a high afﬁnity and extensibility
for both approaches.

GraphTune without
condition on decoder
RMSE
2.63
2.82
3.47

GraphTune without
condition on hidden layer
RMSE
1.12
1.38
1.92

Pinpoint Speciﬁcation of Features: The tunability of graphfeatures in GraphTune is not perfect. While a distribution offeature values of graphs generated by GraphTune has distinctly
different peaks, these values are somewhat varied. Accuracy
improvements of the speciﬁcation remain as a future issue. In
addition, GraphTune can specify at most one feature, and currently, it has not succeeded in specifying multiple features atthe same time. In order to achieve the speciﬁcation of multiple
features, it is necessary to understand the independency and/or
dependency between each feature. However, the independency
and/or dependency of global-level structural features is very
complex, and understanding it is a challenging issue. It goes
without saying that analytical results based on graph theory
are important for this issue. However, observing the featuresof graphs generated by GraphTune may reinforce the resultsof graph theory by a data-driven approach.
Generation of Extrapolation: Although GraphTune generates graphs with a speciﬁc feature ﬂexibly, the tunable range ofa feature is limited to the range of the feature within the graphs

11Fig. 4. Pairwise relationships of the values of the features on generated graphs by GraphTune when we give values 3.0, 4.0, and 5.0 of an average shortest
path length as conditions. The ﬁgure is a grid of multiple plots, and the grid is such that each feature will be shared across the y-axes across a single row andthe x-axes across a single column. The diagonal plots are the distributions of the features, and the others are scatter plots of two features. The distributionsof values of an average shortest path length are clearly distinguishable.

of the learned dataset. In the tasks of generation or prediction,
it is generally hard to extrapolate values that are not includedin the range of the dataset. This difﬁculty is the same forthe graph generation task, and the current GraphTune cannot
generate extrapolated graphs that are outside the range ofgraphs included in the training set. However, the speciﬁcation
technique of graph features provided by GraphTune could bea key technology to overcome the difﬁculty of extrapolation
output in the graph generation task. By specifying the valueof a feature on the edge of the range of the training dataset,
we can generate graphs inside and outside the border. The
generated graphs enhance the original training set, and theenhanced training set covers ranges that are not included in
the original training set by repeatedly generating graphs on
the edges. The generation of extrapolated graphs is one of our
future directions.
VIII. C ONCLUSION
In this work, we proposed GraphTune, which is a learningbased graph generative model with tunable structural features.

GraphTune is composed of a CVAE with an LSTM-based
encoder and decoder. By specifying the value of a particular
structural feature as a condition vector that is input into CVAE,
we can generate graphs with a speciﬁc structural feature. We
performed comparative evaluations of GraphTune, CondGen,and GraphGen through a real graph dataset sourced fromthe who-follows-whom graph on Twitter. The result of theevaluation show that GraphTune makes it possible to tune thevalue of a global-level structural feature, and that conventionalmodels are unable to tune global-level structural features.
Although GraphTune provides a rich variety of graphs
ﬂexibly, it does not solve all problems related to graphmodeling. One improvement needed in future works is toprovide rich functionality for the speciﬁcation of structuralfeatures. In addition to improving the accuracy of feature
values of generated graphs, it is also necessary to be able
to specify multiple features at the same time. Allowing thegeneration of extrapolated graphs that are not included in
the training dataset is also an important function. On theother hand, the tunability of GraphTune has the potential to12Fig. 5. Real data on the Twitter dataset and generated graphs by each generative model. For all generative models except GraphGen, three samples ofgenerative graphs when we specify the shortest path length to 3, 4, and 5 are depicted. For real data, three samples whose average shortest path lengths areclose to 3.0, 4.0, and 5.0 in the dataset are depicted. In Real data and GraphTune, the graphs with “length 3” clearly have a hub node, while the graphs with
“Length 5” forms a long loop.

R EFERENCES

Fig. 6. Relationship between elements 𝑧𝑖 of a latent vector 𝒛 and edge density
𝑝 of ER model. It is conﬁrmed that the latent space of GraphTune is notdisentangled.

Fig. 7. Pairwise relationships of the values of the features on generated graphs
by GraphTune when we give values 0.0, 0.25, 0.5, 0.75, and 1.0 of an edge
density 𝑝 as conditions. The distributions of 𝑝 are clearly changed depending
on a value of a condition vector while the distribution is not signiﬁcantly
dependent on a value of the number 𝑛 of nodes.

empower traditional graph theory by a data-driven approach.
When combined with traditional graph theory, unravelingcomplex global-level features relationships is a challenging
but interesting issue.

[1] S. Nakazawa, Y. Sato, K. Nakagawa, S. Tsugawa, and K. Watabe, “A
Tunable Model for Graph Generation Using LSTM and Conditional
VAE,” in Proc. of the 41st IEEE International Conference on Distributed
Computing Systems (ICDCS 2021) Poster Track, 2021.
[2] N. D. Cao and T. Kipf, “MolGAN: An Implicit Generative Model for
Small Molecular Graphs,” in Proc. of the 35th International Conference
on Machine Learning (ICML 2018) Workshop, 2018.
[3] Y. Li, L. Zhang, and Z. Liu, “Multi-Objective De Novo Drug Design
with Conditional Graph Generative Model,” Journal of Cheminformatics,
vol. 10, no. 33, 2018.
[4] E. Jonas, “Deep Imitation Learning for Molecular Inverse Problems,” inProc. of the 33rd Conference on Neural Information Processing Systems(NeurIPS 2019), 2019.
[5] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann, “NetGAN:
Generating Graphs via Random Walks,” in Proc. of the 35th International Conference on Machine Learning (ICML 2018), 2018, pp. 609–
618.
[6] A. Bonifati, I. Holubová, A. Prat-Pérez, and S. Sakr, “Graph Generators:
State of the Art and Open Challenges,” ACM Computing Surveys,
vol. 53, no. 2, 2021.
[7] P. Erdös and A. Rényi, “On Random Graphs I,” Publicationes Mathematicae, vol. 6, no. 26, pp. 290–297, 1959.
[8] D. J. Watts and S. H. Strogatz, “Collective Dynamics of Small-World
Networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.
[9] R. Albert and A.-L. Barabási, “Statistical Mechanics of Complex Networks,” Reviews of Modern Physics, vol. 74, no. 1, pp. 47–97, 2002.
[10] P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic Blockmodels:First Steps,” Social Networks, vol. 5, no. 2, pp. 109–137, 1983.
[11] J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec, “GraphRNN:
Generating Realistic Graphs with Deep Auto-regressive Models,” inProc. of the 35th International Conference on Machine Learning (ICML2018), 2018.
[12] Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. Battaglia, “Learning Deep
Generative Model of Graphs,” in Proc. of 6th International Conference
on Learning Representations (ICLR 2018) Workshop, 2018.
[13] M. Simonovsky and N. Komodakis, “GraphVAE: Towards Generationof Small Graphs Using Variational Autoencoders,” in Proc. of the 27th
International Conference on Artiﬁcial Neural Networks (ICANN 2018),
2018.
[14] R. Assouel, M. Ahmed, M. H. Segler, A. Saffari, and Y. Bengio,“DEFactor: Differentiable Edge Factorization-Based Probabilistic Graph
Generation,” arXiv, 2018.
[15] C. Yang, P. Zhuang, W. Shi, A. Luu, and P. Li, “Conditional Structure
Generation through Graph Variational Generative Adversarial Nets,” inProc. of the 33rd Conference on Neural Information Processing Systems(NeurIPS 2019), 2019, pp. 1338–1349.
[16] J. Lim, S.-Y. Hwang, S. Moon, S. Kim, and W. Y. Kim, “Scaffold-Based
Molecular Design with a Graph Generative Model,” Chemical Science,
vol. 2020, no. 4, pp. 1153–1164, 2020.

13[17] N. Goyal, H. V. Jain, and S. Ranu, “GraphGen: A Scalable Approach
to Domain-agnostic Labeled Graph Generation,” in Proc. of the Web
Conference 2020 (WWW 2020), 2020, pp. 1253–1263.
[18] W. Jin, R. Barzilay, and T. Jaakkola, “Hierarchical Generation of Molecular Graphs using Structural Motifs,” in Proc. of the 37th International
Conference on Machine Learning (ICML 2020), 2020.
[19] X. Guo and L. Zhao, “A Systematic Survey on Deep Generative Models
for Graph Generation,” arXiv, 2020.
[20] F. Faez, Y. Ommi, M. S. Baghshah, and H. R. Rabiee, “Deep Graph
Generators: A Survey,” IEEE Access, vol. 9, pp. 106 675–106 702, 2021.
[21] S. Hochreiter and J. Schmidhuber, “Long Short-Term Memory,” NeuralComputation, vol. 9, no. 8, pp. 1735–1780, 1997.
[22] D. P. Kingma and M. Welling, “Auto-Encoding Variational Bayes,” inProc. of the 2nd International Conference on Learning Representations(ICLR 2014), 2014.
[23] A. Vázquez, “Growing Network with Local Rules: Preferential Attachment, Clustering Hierarchy, and Degree Correlations,” Physical Review
E, vol. 67, no. 5, 2003.
[24] D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-MAT: A Recursive Modelfor Graph Mining,” in Proc. of the 2004 SIAM International Conferenceon Data Mining (SDM 2004), 2004.
[25] T. G. Kolda, A. Pinar, T. Plantenga, and C. Seshadhri, “A Scalable
Generative Graph Model with Community Structure,” SIAM Journal on
Scientiﬁc Computing, vol. 36, no. 5, 2014.
[26] J. Liu, Y. Chi, and C. Zhu, “A Dynamic Multiagent Genetic Algorithm
for Gene Regulatory Network Reconstruction Based on Fuzzy Cognitive
Maps,” IEEE Transactions on Fuzzy Systems, vol. 24, no. 2, pp. 419–
431, 2016.
[27] Y. Wang, W. Che, J. Guo, and T. Liu, “A Neural Transition-BasedApproach for Semantic Dependency Graph Parsing,” in Proc. of the
32nd AAAI Conference on Artiﬁcial Intelligence (AAAI 2018), 2018.
[28] B. Chen, L. Sun, and X. Han, “Sequence-to-Action: End-to-End Semantic Graph Generation for Semantic Parsing,” in Proc. of the 56th Annual
Meeting of the Association for Computational Linguistics (ACL 2018),
2018, pp. 766–777.
[29] D. Spielman, “Spectral graph theory,” in Combinatorial Scientiﬁc Computing, U. Naumann and O. Schenk, Eds. Taylor & Francis, 2011,
ch. 9.
[30] X. Yan and J. Han, “gSpan: graph-based substructure pattern mining,”
in Proc. of 2002 IEEE International Conference on Data Mining (ICDM
2002), 2002.
[31] I. Higgins, L. Matthey, A. Pal, C. P. Burgess, X. Glorot, M. Botvinick,
S. Mohamed, and A. Lerchner, “beta-VAE: Learning Basic Visual
Concepts with a Constrained Variational Framework,” in Proc. of 5thInternational Conference on Learning Representations (ICLR 2017),
2017.
[32] M. D. Domenico, A. Lima, P. Mougel, and M. Musolesi, “The Anatomy
of a Scientiﬁc Rumor,” Scientiﬁc Reports, vol. 3, no. 2980, 2013.
[33] M. E. J. Newman and M. Girvan, “Finding and Evaluating Community
Structure in Networks,” Physical Review E, vol. E, no. 69, 2004.
[34] A. Jeff, B. Ed, and P. Dietmar, “powerlaw: A Python Package forAnalysis of Heavy-Tailed Distributions,” PLOS ONE, vol. 9, no. 1, 2014.
[35] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “FastUnfolding of Communities in Large Networks,” Journal of Statistical
Mechanics: Theory and Experiment, vol. 2008, no. 10, 2008.
[36] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwanga,“Complex Networks: Structure and Dynamics,” Physics Reports, vol.
424, no. 4-5, pp. 175–308, 2006.
[37] L. da F. Costa, F. A. Rodrigues, G. Travieso, and P. R. V. Boas,“Characterization of Complex Networks: A Survey of Measurements,”
Advances in Physics, vol. 56, no. 1, pp. 167–242, 2007.
[38] H. Kwak, C. Lee, H. Park, and S. Moon, “What is Twitter, a Social Network or a News Media?” in Proc. of the 19th International Conferenceon World Wide Web (WWW 2010), 2010, pp. 591–600.
[39] B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, “On the
Evolution of User Interaction in Facebook,” in Proc. of the 2nd ACM
Workshop on Online Social Networks (WOSN 2009), 2009, pp. 37–42.
[40] N. Stoehr, M. Brockschmidt, J. Stuehmer, and E. Yilmaz, “Disentangling Interpretable Generative Parameters of Random and RealWorld Graphs,” in Proc. of the 33rd Conference on Neural Information
Processing Systems (NeurIPS 2019) Workshop, 2019.

Kohei Watabe received his B.E. and M.E. degrees
in Engineering from Tokyo Metropolitan University,
Tokyo, Japan, in 2009 and 2011, respectively. He
also received the Ph.D. degree from Osaka University, Japan, in 2014. He was a JSPS research
fellow (DC2) from April 2012 to March 2014. He
was an Assistant Professor of the Graduate Schoolof Engineering, Nagaoka University of Technology,
from April 2014 to October 2019. He has been an
Associate Professor of the Graduate School of Engineering, Nagaoka University of Technology, sinceNovember 2019. He is a member of the IEEE and the IEICE.

Shohei Nakazawa received his B.E. and M.E. degrees in Engineeringfrom Nagaoka University of Technology, Niigata, Japan, in 2019 and 2021,
respectively.

Yoshiki Sato received his B.E. degree in Engineering from Nagaoka University of Technology, Niigata, Japan, in 2021. He is currently a student at
Graduate School of Engineering, Nagaoka University of Technology.

Sho Tsugawa received the M.E. and Ph.D. degrees
from Osaka University, Japan, in 2009 and 2012,
respectively. He is currently an Assistant Professor
with the Faculty of Engineering, Information and
Systems, University of Tsukuba, Japan. His researchinterests include network science, social network
analysis, and computational social science. He is amember of IEEE, ACM, IEICE, and IPSJ.

Kenji Nakagawa received the B.S., M.S., and D.S.
degrees from Tokyo Institute of Technology, Tokyo,
Japan, 1980, 1982, and 1986, respectively. In 1985,
he joined Nippon Telegraph and Telephone Corporation (NTT). Since 1992, he has been an Associate
Professor with Nagaoka University of Technology,
where he has been a Professor since 2012. In 2022,
he retired from the Nagaoka University of technology and now he is a Professor Emeritus. His researchinterests include information theory, performance
evaluation of networks, and queueing theory.