# A Framework for Large Scale Synthetic Graph Dataset Generation

Sajad Darabi
<EMAIL_ADDRESS>
&Piotr Bigaj 11footnotemark: 1
<EMAIL_ADDRESS>
Dawid Majchrowski
<EMAIL_ADDRESS>
&Pawel Morkisz
<EMAIL_ADDRESS>
&Alex Fit-Florea
<EMAIL_ADDRESS>
equal contribution

###### Abstract

Recently there has been increasing interest in developing and deploying deep
graph learning algorithms for many graph analysis tasks such as node and edge
classification, link prediction, and clustering with numerous practical
applications such as fraud detection, drug discovery, or recommender systems.
Allbeit there is a limited number of publicly available graph-structured
datasets, most of which are tiny compared to production-sized applications
with trillions of edges and billions of nodes. Further, new algorithms and
models are benchmarked across similar datasets with similar properties. In
this work, we tackle this shortcoming by proposing a scalable synthetic graph
generation tool that can mimic the original data distribution of real-world
graphs and scale them to arbitrary sizes. This tool can be used then to learn
a set of parametric models from proprietary datasets that can subsequently be
released to researchers to study various graph methods on the synthetic data
increasing prototype development and novel applications. Finally, the
performance of the graph learning algorithms depends not only on the size but
also on the dataset’s structure. We show how our framework generalizes across
a set of datasets, mimicking both structural and feature distributions as well
as its scalability across varying dataset sizes.

##  1 Introduction

For many machine learning tasks such as object detection, speech recognition,
and machine translation which once often heavily relied on handcrafted feature
engineered features, deep learning has enabled end-to-end paradigms that learn
effectively from these across a wide array of datasets [1]. The success of
deep learning in these domains is partially attributed to the rapid
development of computational resources and the availability of large amounts
of training data, and the effectiveness of deep learning in extracting useful
representations from such euclidean data (e.g., text, images, signals).
Recently, there has been increasing interest in extending this success to non-
euclidean data, where there is an increasing number of applications with data
being naturally represented as graphs.

Graphs are ubiquitous data structures that capture relational and structural
information between individual entities (nodes) via connections (edges) in
many domains. For example, in social networks, a graph-based learning system
leverages both structural and feature information to make accurate
recommendations to users. Similarly, in an e-commerce platform, a transaction
network can be used to detect fraudulent transactions. Real world graphs;
however, are much more complicated, e.g., for a simple recommendation scenario
user nodes would include information about age, gender, and income, item (e.g.
movie) nodes would be characterized by movie genre, length, and list of
actors, and edges features may contain information about rating the user gave
a movie. This means that the graph dataset’s structure is enriched by tabular
data describing features of the nodes and edges of the graph.

Motivated by similar developments in other domains, various methods have been
developed to learn from graph data such as Node2Vec [2], graph convolution
networks (GCN) [3] and graph attention networks (GAT) [4] focusing on various
tasks including node classification [3], link prediction [5], graph clustering
[6], the term geometric deep learning [7] is used to refer to such methods. A
central problem in geometric deep learning is the lack of real world datasets.
Most of the larger public datasets are similar to each other and are often
derived from academic citation networks [8] which are small for world-size
problems. This lack of diversity limits the development of graph neural
networks (GNN) and their evaluation. We believe generating realistic large
size graph datasets that simulate real-world datasets distributions enabling
data sharing and dataset curating will be a key component to advancing the
field both from the perspective of improving the accuracy of developed GNNs as
well as development new efficient and performance geometric deep learning
methods.

Graph generation entails modeling real-world graphs and generating such
graphs, which pose unique challenges. Owing to the many applications
surrounding graphs developing generative models for graphs has a rich history,
resulting in famous models such as random graphs, small world models and
stochastic block models, etc [9, 10, 11]. These traditional random graph
generation schemes are limited as they are only capable of generating simple
directed non-partite or maximum bi-partite graphs, where real world graphs are
generally n-partite heterogenous nodes and edges graphs. Further they lack
rich feature representatives contained in real-world graphs associated with
node features and edge features.

In this work we propose a framework for synthetic graph generation which can
systematically generate n-partite graphs with corresponding node or edge
features in a scalable manner. Our main contributions is as follows, 1) a
framework for synthetic graph dataset generation that can generate graph of
arbitrary size based on original (usually smaller) graph characteristics
containg both structure and tabular features. The framework also enables us to
generate graphs that when sampled produce subgraphs of similar properties to
subgraphs sampled from the original graphs. 2) simulate real-world graph
statistical properties. Lastly, 3) we show a set of case studies reflecting
the generality and effectiveness of our approach on real-world datasets.

##  2 Related Work

The development of generative models for graphs poses unique challenges. These
generative models are broadly categorized into two categories: traditional
model-based methods and deep learning based methods. Simple, elegant, and
general mathematical models are instrumental in graph generation. The two
simplest random graph models are to select a graph uniformly at random from
the set of graphs with $v$ vertices and $e$ edges or generating a graph
uniformly random from the set of graphs and $v$ vertices where each edge has
the same probability of existing, commonly referred as the Erdos-Renyi models
[12]. In biology, these models are accepted as a basic model to study
biological networks where similarity of typologies and biological regulatory
networks are studied or compared against [13]. Despite its usability and
scalability, it violates power laws commonly found in social networks. A class
of procedural generators tries to find simple mechanisms to generate graphs
that match this property of graphs commonly found in the real-world. A typical
representative here is the Barabasi-Albert Method [9, 14], which uses a
preferential attachment idea by adding nodes and new nodes prefer to connect
to existing nodes. R-MAT An example of such a random graph generation model is
the Gómez-Gardeñes and Moreno [15]. An alternative well-studied random graph
model is the Stochastic Block Model [16] which generates graphs based on the
communities within the graph and their degree distributions. Procedural
synthetic graph generation is a foundation of the Stochastic Kronecker Graph
method introduced in [17] which is a generalization of R-Mat for finding
power-law degree distribution with the base different than two. The above
methods are very attractive from a computational complexity standpoint, as
well as modeling real-world graph properties.

On the other hand, recent deep-graph generators (DGG) that generate graphs
sequentially either by generating node-by-node, edge-by-edge, or a block of
nodes have been proposed. These generators are commonly autoregressive [18,
19, 20] and are limited in generating small graphs with 100’s-1000’s nodes.
Further, very few deep graph generators work with single graph inputs,
commonly referred to as one-shot graph generators, which are auto-encoder
based [21, 22]. Additionally, very few DGG methods generate features in
addition to the structure, primarily because of the complexity of modeling
such a problem jointly in an end-to-end fashion. A good overview of DGG can be
found in [23].

Additionally, comparing two graphs’ datasets in both structure and feature
modality is challenging. Most methods [23, 24, 25, 26] use plots to compare
graphs in terms of connectivity, transitivity, path stats, and spectral
properties, which makes it difficult to assess the superiority of one method
over the other even if they use same original graph datasets. As a result,
there is a need to develop methods for generating and comparing large graphs
from single input models that constitute both the structure as well as
features, which is the focus of this work.

##  3 Proposed Method

Figure 1: Overview of our proposed synthetic data generation framework. The
module is composed of three parts: structural generator, which fits the graph
structure, feature generator which fits the feature distribution contained in
the graph, and finally an aligner, which aligns the generated features with
the generated graph structure.

###  3.1 Problem Formulation

We are interested in the problem of graph generation that aims to sample
similar graphs as the original graph via a probabilistic model. Formally, a
graph contains both structural information and features; as such we define the
graph as a quadruple
$G(\mathcal{V},\mathcal{E},F_{\mathcal{V}},F_{\mathcal{E}})$, where
$\mathcal{V}=\\{v_{0},v_{1},\cdots,v_{N}\\}$ is the set of $N$ nodes (or
vertices), $F_{\mathcal{V}}\in\Re^{N\times d}$ is the corresponding feature
matrix associated with node features, $E\in\mathcal{V}\times\mathcal{V}$ is
the set of $M$ edges, $e_{ij}$ is an edge that connects node $v_{i}$ and
$v_{j}\in\mathcal{V}$, and $F_{\mathcal{E}}\in\Re^{M\times k}$ is the
associated edge feature features assigning features to each edge $e_{i,j}$ and
$k$ is the dimensionality of each edge feature.

Given an observed graph $G$ with arbitrary number of nodes, edges, and feature
sets we aim to learn the probabilistic model that generated this graph $p(G)$.
New graphs are then sampled from this generative process $G\sim p_{model}(G)$.
In the general setting a graph with $N$ nodes can be represented by up to $N!$
adjacency matrices $A^{\pi}$, corresponding to arbitrary node ordering,
resulting a high representation complexity especially for large graphs.
Additionally, there are $2^{N(N-1)/2}$ such graphs in the undirected case. The
number of nodes and edges vary between different graphs and it is important
for generative models to scale to large-scale graphs for realistic graph
generation and to accommodate this complexity in the output space. Further, to
simultaneously generate node attributes $F_{\mathcal{V}}$ and edge attributes
$F_{\mathcal{E}}$ exacerbates the modeling complexity. To make the problem
tractable we decompose the generative process, making the structural
generation and feature generation independent

$P(\mathcal{V},\mathcal{E},F_{\mathcal{E}},F_{\mathcal{V}})=P(\mathcal{V},\mathcal{E})P(F_{\mathcal{E}})P(F_{\mathcal{V}})$
(1)

As a result, our proposed generative model consists of three components:
structural generation, feature generation, and alignment of these two
components as depicted in Figure 1. Consider a dataset
$\mathcal{D}=\\{(x_{i})\\}_{i=1}^{M}$, that contains entity features
corresponding to nodes, as well as features attributed to nodes, and edges. We
extract the corresponding structural information
$\mathcal{D}_{\text{struct}}$, and the data with feature sets
$\mathcal{D}_{\text{features}}$ to learn from generative models from
independently.

###  3.2 Structure Generation

####  3.2.1 General Information

As we are interested in scaling the generation tool to large graphs, we
leverage model-based graph generators, where our proposed method can be seen
as a generalized stochastic Kronecker matrix multiplication for structure
generation. The graph structure consists of the corresponding nodes and edges
without node or feature attributes, i.e.
$D_{structure}=G(\mathcal{V},\mathcal{E})$. The adjacency matrix $A$
corresponding to this graph is an $N\times M$ matrix with entries $a(i,j)=1$
if the edge $e_{ij}$ between node $i$ and node $j$ exists. We treat edges as
directional and if $e_{ij}$ exists then edge $e_{ji}$ does not necessarily
have to exist, i.e. $A$ does not have to be symmetrical. Matrix $A$ in general
is constructed in a way that $i$-th row and $i$-th column can represent
different nodes in the graph e.g. for bipartite user-item interaction graph
$i$-th user is a different entity than $i$-th item. We will first formalize
the problem of generating the structure for a simple graph $G$ that is non-
directed heterogeneous in nodes and homogeneous in edges. Later we will extend
this to general graph to show that our generator is a generalisation of R-MAT
[24].

####  3.2.2 Problem formulation

The task of the generator is to generate a graph $\hat{G}$ represented by
adjacency matrix $\hat{A}$ that is similar in selected graph’s structure
characteristics to original Graph $G$. We will create $\hat{A}$ by sampling
$E$ edges from a distribution $\theta$. $\theta$ is a discrete 2D probability
distribution, i.e. $\theta_{i,j}$ represents probability that there is
directed edge from node $i$ to node $j$ in graph $\hat{G}$. If we choose to
generate the graph of the same size as the input one, that is $\hat{A}$ is
$N\times M$ and graph $\hat{G}$ has $N+M$ nodes, then $\hat{A}\sim\theta$

$\theta=\theta_{S}^{\otimes min(m,n)}\otimes\theta_{H}^{\otimes
min(0,n-m)}\otimes\theta_{V}^{\otimes min(0,m-n)}$ (2)

where

$\theta_{S}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\theta_{H}=\begin{bmatrix}q&&1-q\end{bmatrix}\theta_{V}=\begin{bmatrix}p\\\
1-p\end{bmatrix},\linebreak$ (3)

$m=\lceil\log_{2}M\rceil,\quad n=\lceil\log_{2}N\rceil,$ (4)

$p=a+b,\quad q=a+c,$ (5)

$\otimes$ is a Kronecker matrix product, and $A^{\otimes
b}=\underbrace{A\otimes A\otimes...\otimes A}_{btimes}$ is a matrix Kronecker
power.

Also, $\theta_{H}$ and $\theta_{V}$ are marginals of $\theta_{S}$ which depend
only on the shape of matrix $\hat{A}$ and only one of them is effectively used
to form the probability distribution $\theta$. If matrix $\hat{A}$ is square
($N=M$) then

$\displaystyle\theta=\theta_{S}^{\otimes N}$

which effectively is an R-MAT algorithm. The proposed above approach is
different not only because $\hat{A}$ might be a non-square adjacency matrix,
but also because $\hat{A}$ in general is constructed in a way that the $i$-th
row and the $i$-th column can represent different node in the graph which
gives us possibility to construct graphs that are heterogeneous in nodes in
partite graphs. That reflects well the use case from recommender system
domains, where the matrix $\hat{A}$ is bipartite and we track connections
(edges) between the users and items. Then rows and columns can represent the
users and items, respectively.

For partite graph the obtained adjacency matrix is a block matrix with
connections only between the nodes only in corresponding connected partite. In
this framework in order to represent partite graphs with $\hat{A}$ where
matrix coordinates imply node ids then, it is sufficient to consider
$\hat{A_{P}}$ for each partite $P$ and create $\hat{A}$ out of $\hat{A_{P}}$
for each partite. Hence, each partite subgraph $\hat{G_{P}}$ represented by
$\hat{A_{P}}$ is created according to (2).

####  3.2.3 Fitting the generator

The purpose of the structure generator is to generate a graph $\hat{G}$ that
is similar in graph characteristics to original graph $G$. These
characteristics will depend on parameters of $\theta_{S}$ seeding matrix as
$\hat{A}\sim\theta$. We use the notion of (normalized) degree distributions of
the graphs $G$, $\hat{G}$ as a similarity measure therefore in order to find
parameters of $\theta_{S}$ we need to minimize the following error

$J(\theta_{S})\propto\sum_{k^{in}=0}^{k_{max}^{in}}(c_{k}^{in}-\hat{c_{k}^{in}})^{2}+\sum_{k^{out}=0}^{k_{max}^{out}}(c_{k}^{out}-\hat{c_{k}^{out}})^{2},$
(6)

where $k$ \- degree of node, $c_{k}^{in}$ \- number of nodes in graph $G$
having in-degree $k$, $c_{k}^{out}$ \- number of nodes in graph $G$ having
out-degree $k$, $\hat{c_{k}^{in}}$ \- estimated number of nodes in graph
$\hat{G}$ having in-degree k, and $\hat{c_{k}^{out}}$ \- estimated number of
nodes in graph $\hat{G}$ having out-degree k.

Note that this does not imply that $A$ and $\hat{A}$ are similar in sense
$A-\hat{A}\approx 0$, which would require appropriate node permutation in
$\hat{G}$. Simple degree distributions comparison allows us to effectively
compare graphs only when there is similar number of nodes, but in fact the
generator is to generate a graph $\hat{G}$ that is arbitrary bigger in number
of nodes than $G$. Therefore, we firstly need to find $\theta_{S}$ for the
graph of the same size and then generate

$\hat{c_{k}^{in}}$ and $\hat{c_{k}^{out}}$ depend on $\theta_{S}$ in a
following way

$\hat{c_{k}^{out}}={E\choose k}\sum_{i=0}^{m}{m\choose
i}[p^{m-i}(1-p)^{i}]^{k}[1-(p^{m-i}(1-p)^{i})]^{E-k}$ (7)

and

$\hat{c_{k}^{in}}={E\choose k}\sum_{i=0}^{n}{n\choose
i}[q^{n-i}(1-q)^{i}]^{k}[1-(q^{n-i}(1-q)^{i})]^{E-k},$ (8)

where $\hat{c_{k}^{in}}$ and $\hat{c_{k}^{out}}$ depend only on $p$ and $q$.
Solving (6) for $p=a+b$ and $q=a+c$ leads to underdetermined system
($a+b+d+c=1$) as we have 3 equations and 4 variables. [24] proposes to use
$\frac{a}{b}=\frac{a}{c}=\frac{3}{1}$, since this can be seen in many real
world scenarios. We have encountered graph datasets that did not follow this
ratio. Instead of this ratio we propose to estimate $\frac{a}{b}$ and
$\frac{a}{c}$ from adjacency matrix $A$ of the original graph $G$ by Maximum
Likelihood Estimation of these parameters as this yields better results.

Then, (6) together with (8), and (7) can be solved by iterative gradient
methods or nonlinear programming solver.

###  3.3 Feature Generation

Consider the feature sets associated with the graph
$\mathcal{D}_{\textrm{features}}=\\{(x_{i})\\}_{i=1}^{N}$, where $x_{i}$ are
observations sampled from a data-generating distribution
$P_{\mathcal{D}_{\textrm{features}}}(x)$. We treat this dataset as a tabular
dataset where each row corresponds to the corresponding edge features, source
node features, and destination nodes features. The objective is to learn a
generative model $G_{\textrm{features}}$ over this data generating process. To
this end, we consider the multi-modal setting where $x_{i}$ is a concatenation
of discrete $\mathcal{D}=[D_{1},\cdots,D_{|\mathcal{D}|}]$ and continuous
features $\mathcal{C}=[C_{1},\cdots,C_{|\mathcal{C}|}]$. Without loss of
generality our generator follows a GAN architecture, though any high-capacity
method that can model the underlying distribution can be used. To this end,
our input layer consists of a feature tokenizer where the corresponding
embedding for each feature is computed as follows:

$E_{j}=b_{j}+f_{j}(x_{j})\in\Re^{d_{j}}\quad
f_{j}:\mathbb{X}\rightarrow\Re^{d_{j}}$

where $b_{j}$ is a bias term for the $j\textrm{-th}$ feature and $f_{j}$ is
the corresponding feature tokenization function. Our model applies mode-
specific normalization to continuous columns which 1) fits a variational
mixture of Gaussian to continuous columns of $\mathcal{C}$ 2) converts the
continuous elements of $c\textrm{-th}$ into a one-hot vector denoting the
specific Gaussian that best matches the element and its scalar normalized
value within the selected Gaussian. For discrete columns we introduce
embedding layers $W_{D_{i}}\in\Re^{d_{D_{i}}}$. The input layer operation
could be summarized as follows

$\displaystyle E_{j}^{cont}$ $\displaystyle=f_{j}^{cont}$
$\displaystyle\in\Re^{d^{C_{j}}}$ $\displaystyle E_{j}^{cat}$
$\displaystyle=b_{j}^{cat}+e_{j}^{T}W_{j}^{cat}$
$\displaystyle\in\Re^{d^{D_{j}}}$ $\displaystyle X$
$\displaystyle=\textit{concat}[E_{1}^{cont},\cdots,E_{C_{\mathcal{C}}}^{cont},E_{1}^{cat},\cdots,E_{D_{\mathcal{D}}}^{cat}]$
$\displaystyle\in\Re^{d},$

where $f_{j}^{cont}$ is the
$d=\sum_{j}^{\mathcal{C}}d_{C_{j}}+\sum_{j}^{\mathcal{D}}d_{D_{j}}$. In GAN
training there are two separate models the generator $G$ and discriminator $D$
that estimates the probability of whether the sample came from the fake or
real distribution. The generator $G:\Re^{dim(z)}\rightarrow\Re^{dim(x)}$ takes
the input $z\sim p(z)\in\Re^{d_{z}}$ and recovers samples in the original data
space $\tilde{x}$. The discriminator then distinguishes between
$D(x,\tilde{x})\rightarrow[0,1]$. Both networks are high capacity deep neural
networks that follow a stack of
$f(x)=\theta(\texttt{ResNetBlock}(\cdots(\texttt{ResNetBlock(FC(x))))})$ where
$\texttt{ResNetBlock}(x)=x+\texttt{Dropout(ReLU(FC(BatchNorm(x))))}$, FC is a
fully-connected network which takes the $dim(x)$ size of its input. $G$ and
$D$ are both trained together using the GAN objective

$\displaystyle\min_{G}\max_{D}l(G,D)=\min_{G}\max_{D}\mathbb{E}_{x\sim
p_{data}(x)}[log(D(x)]+\mathbb{E}_{z\sim p(z)}[log(1-D(G(z)))].$

The trained feature generator is then used to sample from the learned feature
distribution $\tilde{x}\sim P_{\mathcal{D}_{features}}$.

###  3.4 Graph & Feature Aligner

Once the structural and feature generators are fitted they are overlaid via an
aligner. The aligner is a function that maps the generated set of features
onto the generated graph structure $A(S,F)\rightarrow
G(\mathcal{V},\mathcal{E},F_{\mathcal{V}},F_{\mathcal{E}})$. A trivial
aligner, could randomly assign features to the corresponding nodes and edges
of the generated graph. Instead, we propose to train a function $R$ that
matches the generated structure with the generated features, preserving some
properties of the input graph $G$, e.g. for the recommender system use case,
we may have an advertisement that is clicked by the majority of population and
we want to preserve its generated features properties.

Given real graph $G_{real}$ we extract a set of features from the
corresponding structural information $F:S_{real}\rightarrow\Re^{d}$. These
features correspond purely with the graph structure, such as node degree, node
centrality, clustering coefficient, page rank. Subsequently, a predictor $R$
is trained to capture the correlation between the real graph structural
features and the corresponding real feature set. For an edge $e_{(src,dst)}$
the predictor maps on to the features $x\in\Re^{d}$, that is,
$R:F(S_{src},S_{dst})\rightarrow\Re^{dim(x)}$, where $src$ is the source node
index, and $dst$ is the destination node index, and $S_{src},S_{dst}$ are the
corresponding structural features. We propose to choose XGBoost as our
predictor $R$, for each feature $x_{j}$. The proposed aligner can be
summarized as follows

$\displaystyle
R(S_{src},S_{dst})=\texttt{stack}[\texttt{XGBoost}_{1},\cdots,\texttt{XGBoost}_{d}]\in\Re^{d}$
$\displaystyle Rank=\max_{i\in M}(\texttt{sim}(R(S_{src},S_{dst}),X_{i}).$

The series of XGBoost models are trained to infer the features from structural
information, in the case of $e_{src,dst}$ both features of node $S_{src}$ and
$S_{dst}$ are used as input to the model. A similarity score between the
predicted vector and corresponding generated feature is used to rank the
corresponding features that are assigned to the edges of the graph. For
continuous values the mean squared-error is used

$-\sum_{j\in\\{\mathcal{C}\\}}(R(S_{src},S_{dst})^{(j)}-x^{(j)}_{i})^{2}$

and similarly for categorical columns the cosine similarity

$\frac{\sum_{j\in\mathcal{D}}(R(S_{src},S_{dst})^{(j)}X_{i}^{j}}{\sqrt{\sum_{jin\mathcal{D}}(R(S_{src},S_{dst})^{(j)}}\sqrt{\sum_{j\in\mathcal{D}x^{(j)}}}}.$

Once the generated set of features are ranked, they are overlayed on the
original graph structure where the node and edge information is appended to
the corresponding set of features.

##  4 Experiments

In this section, we introduce a set of experiments to show case the
effectiveness of the proposed framework for generating real-world graphs. We
describe a set of metrics to evaluate data quality across structural, feature,
and both. We also provide an extended set of results in supplementary
material.

###  4.1 Methods

Our method involves fitting a single large graph and learning a parametric
model that can be used to generate graphs on the same scale or larger. We
compare with the following baselines:

  * •

Random: We generate graph structures using Erdos-Renyi model, along with a
random feature generator with ranges fitted to the original feature dimension.
This model is integrated in our proposed framework.

  * •

GraphWorld [27]: Is a recent method for generating arbitrary graphs using the
degree corrected stochastic block model (SBM). We improve this method and add
a fitting step that fits the model onto the underlying dataset.

###  4.2 Dataset details

In this section we provide details on a real-world datasets encompassing
different graph sizes with varying number of features. More details are
provided in appendix.

ID | Dataset |  $\\#$ nodes |  $\\#$ edges |  $\\#$ features |
---|---|---|---|---|---
1 | Tabformer | 106482 | 978288 | 5 |
2 | IEEE-Fraud | 17289 | 52008 | 48 |
3 | Paysim | 9075669 | 6362620 | 8 |
4 | credit | 1666 | 476414 | 283 |

###  4.3 Metrics & Evaluation

We provide a set of metrics to assess the quality of the generated graph. We
detail a set of metrics across the different components of the generated graph

  * •

Degree Dist.: in networks the degree of a node is the number of connections it
has with other nodes, and its the degree-distribution of the network is the
distribution of these degrees over the whole network. For example, a graph has
a power-law if the number of nodes $N_{d}$ with degree $d$ is given by
$N_{d}\propto d^{-\alpha}$ where $\alpha$ is the power law exponent.

  * •

Hop-plot: The diameter of a graph is $D$ if every pair of nodes can be
connected by a path of length at most $D$ edges. As this metric is susceptible
to outliers often a alternative metric called effective diameter is used,
which is the minimum number of links in which a fraction of all pairs of nodes
can be reached each other. A hop-plot extends the notion of diameter by
plotting reachable pairs $d(h)$ within $h$ hops.

  * •

Feature Corr.: We consider correlation between columns of the features in the
dataset. For correlation between continuous columns we use the standard
Pearson correlation. Between continuous and categorical columns we consider
the correlation ratio [28], and between categorical columns we consider using
the Theil’s U [29] as a metric, which measures the conditional entropy between
two variables.

  * •

Degree-Feat Dist-Dist: We consider the joint degree distribution and feature
distribution as a measure of graph feature+structural similarity. This metric
computes the JS-divergence between the joint distribution over the generated
graph and real graph.

###  4.4 Results

Figure 2: Comparison of degree distribution (left) and hop plot (right) across
our proposed method (properly generated) and other baselines.

In Table 1 we summarize the comparison of the proposed framework across
different dataset sizes. From the table we can see that the synthetic data
quality generated using our method out performs the two baseline models. It is
worth noting that GraphWorld [27] was modified to fit the underlying data
structure. Additionally, this method falls under the same framework where the
structural generator is a SBM model, the feature generations are multi-variate
Gaussian’s and the aligner is a random aligner. We do not provide comparison
with methods such as [18, 19] as 1) these method require multiple graphs and
we are providing comparisons for single graph generation and 2) these methods
do not scale beyond 1000s of nodes as previously mentioned. Additionally, from
Figures 2, 3, 4, we show vizualization comparing across the original graph
distribution, ours and baseline models, demonstrating the effectiveness of
each component in the generation step.

Table 1:  Comparison across different datasets and baseline models. $\uparrow$
denotes higher is better and $\downarrow$ denotes lower is better.

|  | Metric
---|---|---
Dataset | Method |  Degree Dist. $\uparrow$ |  Feature Corr. $\uparrow$ |  Degree-Feat Dist-Dist $\downarrow$
Tabformer | random | 0.8099 | 0.3931 | 0.8213
graphworld | 0.2836 | 0.3609 | 0.8248
ours | 0.9833 | 0.4141 | 0.8101
ieee-fraud | random | 0.9620 | 0.2120 | 0.4335
graphworld | 0.0010 | 0.4179 | 0.8272
ours | 0.9865 | 0.5724 | 0.2359
credit | random | 0.0434 | 0.8370 | 0.6520
graphworld | 0.3556 | 0.8352 | 0.7584
ours | 0.5178 | 0.8558 | 0.5516
paysim | random | 0.6711 | 0.4833 | 0.5155
graphworld | 0.6547 | 0.4115 | 0.3453
ours | 0.9602 | 0.7500 | 0.2630

Figure 3: Cumulative distribution comparison on feature column C11 of ieee-
fraud dataset. Figure 4: Histograms comparing degree distribution and feature
distribution for IEEE-Fraud dataset. a) original graph, b) ours generated, c)
randomly generated, d) GraphWorld generated.

##  5 Conclusion

The objective of this paper was to create a method of generating graph
datasets that consist of (1) structure describing how nodes are connected to
other nodes (2) along with tabular node and edge features contained in the
graph. Using our method, these two components (structural and tabular) are
aligned in the sense that the degree distributions of nodes match the
probability distributions of features connected with nodes.We have shown the
generality of such a framework that can more accurately replicate and scale
with respect to different graph sizes and structure. We hightlight that
generating large-scale graph datasets that consist of structure and tabular
portion serves many real-world use cases starting such as data anonymization,
as a tool to benchmark GNN models by profiling them on arbitrary-sized graph
datasets, as well as potentially using synthetic datasets increasing the
accuracy of GNN by using such data to pre-training the GNN model and fine-tune
it on the original dataset. Future directions can include modifying the
framework to these different ends.

## References

  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Kipf and Welling [2016a] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016a.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Liben-Nowell and Kleinberg [2007] David Liben-Nowell and Jon Kleinberg.  The link-prediction problem for social networks.  _Journal of the American society for information science and technology_ , 58(7):1019–1031, 2007.
  * Hamilton et al. [2017] William L Hamilton, Rex Ying, and Jure Leskovec.  Representation learning on graphs: Methods and applications.  _arXiv preprint arXiv:1709.05584_ , 2017.
  * Bronstein et al. [2017] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, 2017.
  * Hu et al. [2021] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec.  Ogb-lsc: A large-scale challenge for machine learning on graphs.  _arXiv preprint arXiv:2103.09430_ , 2021.
  * Albert and Barabási [2002] Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  _Reviews of modern physics_ , 74(1):47, 2002.
  * Leskovec et al. [2010] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani.  Kronecker graphs: an approach to modeling networks.  _Journal of Machine Learning Research_ , 11(2), 2010.
  * Robins et al. [2007] Garry Robins, Tom Snijders, Peng Wang, Mark Handcock, and Philippa Pattison.  Recent developments in exponential random graph (p*) models for social networks.  _Social networks_ , 29(2):192–215, 2007.
  * Erdös and Rényi [1959] P. Erdös and A. Rényi.  On random graphs i.  _Publicationes Mathematicae Debrecen_ , 6:290, 1959.
  * Ma’ayan et al. [2008] Avi Ma’ayan, Azi Lipshtat, Ravi Iyengar, and Eduardo D Sontag.  Proximity of intracellular regulatory networks to monotone systems.  _IET Systems Biology_ , 2(3):103–112, 2008.
  * Albert and Barabási [2000] Réka Albert and Albert-László Barabási.  Topology of evolving networks: Local events and universality.  _Phys. Rev. Lett._ , 85:5234–5237, Dec 2000.  doi: 10.1103/PhysRevLett.85.5234.  URL https://link.aps.org/doi/10.1103/PhysRevLett.85.5234.
  * Gómez-Gardeñes and Moreno [2006] Jesús Gómez-Gardeñes and Yamir Moreno.  From scale-free to erdos-rényi networks.  _Physical Review E_ , 73(5):056124, 2006.
  * Abbe [2017] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  _The Journal of Machine Learning Research_ , 18(1):6446–6531, 2017.
  * Leskovec et al. [2005] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos.  Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication.  In Alípio Mário Jorge, Luís Torgo, Pavel Brazdil, Rui Camacho, and João Gama, editors, _Knowledge Discovery in Databases: PKDD 2005_ , pages 133–145, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.  ISBN 978-3-540-31665-7.
  * You et al. [2018] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.  Graphrnn: Generating realistic graphs with deep auto-regressive models.  In _International conference on machine learning_ , pages 5708–5717. PMLR, 2018.
  * Liao et al. [2019] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel.  Efficient graph generation with graph recurrent attention networks.  In _NeurIPS_ , 2019.
  * Martinkus et al. [2022] Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer.  Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators.  _arXiv preprint arXiv:2204.01613_ , 2022.
  * Kipf and Welling [2016b] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016b.
  * Grover et al. [2019] Aditya Grover, Aaron Zweig, and Stefano Ermon.  Graphite: Iterative generative modeling of graphs.  In _International conference on machine learning_ , pages 2434–2444. PMLR, 2019.
  * Faez et al. [2020] Faezeh Faez, Yassaman Ommi, Mahdieh Soleymani Baghshah, and Hamid R. Rabiee.  Deep graph generators: A survey.  _CoRR_ , abs/2012.15544, 2020.  URL https://arxiv.org/abs/2012.15544.
  * Chakrabarti et al. [2004] Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos.  R-mat: A recursive model for graph mining.  volume 6, 04 2004.  doi: 10.1137/1.9781611972740.43.
  * Leskovec et al. [2008] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani.  Kronecker graphs: An approach to modeling networks.  _Journal of Machine Learning Research_ , 11, 12 2008.  doi: 10.1145/1756006.1756039.
  * Bojchevski et al. [2018] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann.  Netgan: Generating graphs via random walks.  2018\.  doi: 10.48550/ARXIV.1803.00816.  URL https://arxiv.org/abs/1803.00816.
  * Palowitch et al. [2022] John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi.  Graphworld: Fake graphs bring real insights for gnns.  _arXiv preprint arXiv:2203.00112_ , 2022.
  * Fisher [1992] Ronald Aylmer Fisher.  Statistical methods for research workers.  In _Breakthroughs in statistics_ , pages 66–70. Springer, 1992.
  * Shannon [1948] Claude E Shannon.  A mathematical theory of communication, bell systems technol.  _J_ , 27(3):379–423, 1948.
  * Seshadhri et al. [2011] C. Seshadhri, Ali Pinar, and Tamara Kolda.  A hitchhiker’s guide to choosing parameters of stochastic kronecker graphs.  _CoRR_ , abs/1102.5046, 01 2011.
  * Park and Kim [2017] Himchan Park and Min-Soo Kim.  Trilliong: A trillion-scale synthetic graph generator using a recursive vector model.  In _Proceedings of the 2017 ACM International Conference on Management of Data_ , pages 913–928. ACM, 2017.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.

##  Appendix A Adding noise to structure generator

Graph $\hat{G}$ generated by (2) will produce oscillations on the degree
distribution as described in [30]. To address oscillations we propose to add a
noise component on each $max(m,n)$ step of (2). This changes (2) to

$\theta=\underbrace{\theta_{S,0}\otimes...\otimes\theta_{S,min(n,m)}}_{min(m,n)times}\otimes\underbrace{\theta_{H,0}\otimes...\otimes\theta_{H,min(0,n-m)}}_{min(0,n-m)times}\otimes\underbrace{\theta_{V,0}\otimes...\otimes\theta_{V,min(0,m-n)}}_{min(0,m-n)times},$
(9)

where $\theta_{S,i}$, $\theta_{H,i}$, $\theta_{V,i}$ are noisy versions of
$\theta_{S}$, $\theta_{H}$, $\theta_{V}$ from (2), respectively. If noise is
not added then (9) and (2) are equivalent. $\theta_{S,i}$ (and analogically
$\theta_{H,i}$, $\theta_{V,i}$) are modifications of $\theta_{S}$ (and
$\theta_{H}$, $\theta_{V}$, respectively)

$\theta_{S,i}=\theta_{S}+N_{i}(\theta_{S}),$ (10)

analogically for $\theta_{H,i}$, $\theta_{V,i}$. Mean value of noise added to
cascade (2) has to be zero, but careful mathematical analysis shows that also
elements of noise matrix $N_{i}$ added to matrix $\theta_{S}$ (and
respectively $\theta_{H}$, $\theta_{V}$) have to be zero.

Noise added by $N_{i}$ depends on $\theta_{S}$ and in practice can be
controlled by a single parameter sampled from uniform distribution. An
exemplary noise for symmetric $\theta_{S}$ can be

$N_{i}=\begin{bmatrix}\frac{-2n_{f}*a}{a+d}&nf\\\
nf&\frac{2n_{f}*a}{a+d}\end{bmatrix}\linebreak n_{f}\sim
U[min(\frac{a+d}{2},b,c)],$ (11)

Where $U[x,y]$ denotes the uniform distribution …. Overall, adding noise on
each step of generator requires only $max(n,m)$ parameters.

##  Appendix B Additional Experiments

###  B.1 Comparing degree distribution

Our structure generator fits its parameters to degree distribution of original
graph according to (6). Estimating the quality of that fitting can be done
visually by comparing plots like in Figure 2. Still, in most cases, it isn’t
easy to assess whether the improvement of the fitting procedure makes a degree
distribution of the synthetic graph closer to the original. This holds
especially for comparing a different size synthetic graph in terms of $N$,$M$
and $E$ than the original graph. We propose a single scalar metric that
captures the alignment of degree distribution for two graphs. This metric is
calculated as follows:

$DCC=\frac{1}{K}\sum_{k\in
logspace(0,1)}{\frac{c_{k}^{norm}-\hat{c_{k}^{norm}}}{c_{k}^{norm}}}$ (12)

where $K$ is the number of distinct degree $k$ sampled logarithmically from
$[0,1]$ $c_{k}^{norm}$, $\hat{c_{k}^{norm}}$ are normalised degree
distributions i.e. degree is normalised by maximum degree in the graph and
number of nodes is normalised by maximum $c_{k}$ and $\hat{c_{k}}$
respectively.

Normalization of the degree distribution is needed as $G$ and $\hat{G}$ may
have different sizes both in terms of number of nodes and edges. For $G$ and
$\hat{G}$ of the same number of edges $E$ the $DCC$ in (12) simplifies to

$DCC=\frac{1}{K}\sum_{k\in
logspace(0,k_{max})}{\frac{c_{k}-\hat{c_{k}}}{c_{k}}}.$ (13)

For generating larger graphs, we need to ensure that graph density is
preserved i.e.:

$\frac{E}{N*M}=\frac{\hat{E}}{\hat{N}*\hat{M}},$ (14)

where $\hat{E},\hat{N},and\hat{M}$ are number of edges and nodes in partites
of $\hat{G}$.

For example, for homogeneous graph when increasing the number of nodes twice,
one needs to increase the number of edges four times to preserve the constant
density.

Our method consistently outperforms ER model not only for the same graph size
but across all scaling factors, see Figure 5. It also provides very high
values of CDD for large graphs which in fact means that when generating large
synthetic graphs, the degree distribution curve shape preserves its power-law
shape. This statement holds for generating smaller graphs that is equivalent
to subsampling larger graph in a stratified way where nodes’ degree proportion
are preserved - this can be primary seen in Tabformer dataset where partites
are imbalanced in size ($2^{17}$ user nodes and $2^{11}$ merchant nodes).

|
---|---
(a) | (b)
|
(c) |
Figure 5:  CDD coefficient calculated according to 12 for different datasets
(a) Tabformer, (b) ieee-fraud (c) paysim. Two generating models are compared:
our method marked as ’propper’ and random witch is ER [12]. X-axis of each
graph is an exponential scaling factor by which the number of nodes in each
partite is multiplied e.g. $0$ means graph of the same size, +3 means graph
for which $\hat{N}=2^{3}N$,$\hat{M}=2^{3}M$ and $\hat{E}=2^{6}E$, -3 means
graph for which $\hat{N}=2^{-3}N$,$\hat{M}=2^{-3}M$ and $\hat{E}=2^{-6}E$ etc

###  B.2 GNN Performance Analysis

In this section, we run additional experiments analyzing GNN’s throughput
using our generated and randomly generated datasets. We time the throughput of
the GNN network by sampling subgraphs on the original graph using a Multi-
Layer Neighborhood Sampler
111dgl.dataloading.neighbor.MultiLayerNeighborSampler and measuring the time
of every epoch. The results are summarized in Table. 2. As can be seen from
the results, generally, for datasets where there’s a higher discrepancy in the
metrics reported in Table 1 there is a larger gap in the timing between random
vs original and ours. The relative timing (Rel. Timing) is calculated by
subtracting the epoch times on the original dataset from the generated and
normalizing, i.e. (Rel. Timing =
$1.0-\frac{|t_{generated}-t_{original}|}{t_{original}}$

Table 2:  Comparison of throughput for GCN [3] across different datasets.
$\uparrow$ denotes higher is better and $\downarrow$ denotes lower is better.

|  | Metric
---|---|---
Dataset | Method |  Rel. Timing $\uparrow$ | Timing
Tabformer | original | 1.0 | 107.5836
random | 0.8611 $\pm 0.8611$ | 93.3228
ours | 0.9376 $\pm 0.0094$ | 100.1258
ieee-fraud | original | 1.0 | 1.9833
random | 0.7922 $\pm{0.1484}$ | 2.06162
ours | 0.8039 $\pm{0.1450}$ | 2.04135
credit | original | 1.0 | 28.6372
random | 0.9668 $\pm 0.0003$ | 26.9836
ours | 0.9822$\pm 0.0083$ | 28.1271
paysim | original | 1.0 | 153.4566
random | 0.9302 $\pm{0.0025}$ | 143.1298
ours | 0.9581 $\pm{0.0020}$ | 159.1917

Table 3:  Comparison of throughput for GAT[4] across different datasets.
$\uparrow$ denotes higher is better and $\downarrow$ denotes lower is better.

|  | Metric
---|---|---
Dataset | Method |  Rel. Timing $\uparrow$ | Timing
Tabformer | original | 1.0 | 191.6026
random | 0.6903 $\pm.0004$ | 132.2720
ours | 0.8710 $\pm 0.0038$ | 166.8899
ieee-fraud | original | 1.0 | 3.9867
random | 0.6975 $\pm{0.0795}$ | 3.41476
ours | 0.8003 $\pm{0.0940}$ | 3.5655
credit | original | 1.0 | 70.2702
random | 0.9370 $\pm 0.0011$ | 65.8476
ours | 0.9609$\pm 0.0034$ | 67.8039
paysim | original | 1.0 | 235.1643
random | 0.9248 $\pm{0.0016}$ | 217.4626
ours | 0.9657 $\pm{0.0046}$ | 243.2182

####  B.2.1 Scalability

To show the scalability of the proposed framework, we run experiments where
the original graph datasets are scaled $S\in[1\times-100\times]$ the original
size. Specifically the graph is scaled accordingly by scaling the number of
nodes $\sqrt{S}*|V|_{original}$ and the number of edges $S*|E|_{original}$.
The generation times for two datasets are presented in 6. The experiments are
run on a machine with a single v100 as described in section D.

Figure 6: Generation times for various scaling factors on IEEE & Tabformer
graph datasets.

###  B.3 Ablation Study

We conduct an ablation study by varying the components in our proposed
framework. Specifically, we substitute the feature generator with one of {GAN,
Kernel Density Estimator (KDE), Random}, the structural generator with one of
{Ours, TrillionG [31], Random} and the aligner with either {XGBoost, Random}
across our proposed components and evaluate the synthetic data quality. The
results are presented in 4.

Table 4:  Ablation study on IEEE Dataset

|  |  | Metric
---|---|---|---
Struct. Generator | Feature Generator | Aligner |  Degree Dist. $\uparrow$ |  Feature Corr. $\uparrow$ |  Degree-Feat Dist-Dist $\downarrow$
Ours | GAN | xgboost | 0.989123 $(\pm 0.0014)$ | 0.566755 $(\pm 0.0121)$ | 0.319410
random | 0.989123 $(\pm 0.0014)$ | 0.566755 $(\pm 0.0121)$ | 0.330570
KDE | xgboost | 0.989123 $(\pm 0.0014)$ | 0.810647 $(\pm 0.0277)$ | 0.198234
| random | 0.989123 $(\pm 0.0014)$ | 0.810647 $(\pm 0.0277)$ | 0.512846
| Random | xgboost | 0.989123 $(\pm 0.0014)$ | 0.220692 $(\pm 0.0090)$ | 0.355433
| random | 0.989123 $(\pm 0.0014)$ | 0.220692 $(\pm 0.0090)$ | 0.364814
TrillionG | GAN | xgboost | 0.848164 $(\pm 0.0012)$ | 0.566755 $(\pm 0.0121)$ | 0.316364
random | 0.848164 $(\pm 0.0012)$ | 0.566755 $(\pm 0.0121)$ | 0.423613
KDE | xgboost | 0.848164 $(\pm 0.0012)$ | 0.810647 $(\pm 0.0277)$ | 0.261013
| random | 0.848164 $(\pm 0.0012)$ | 0.810647 $(\pm 0.0277)$ | 0.360605
| Random | xgboost | 0.848164 $(\pm 0.0012)$ | 0.220692 $(\pm 0.0090)$ | 0.434184
| random | 0.848164 $(\pm 0.0012)$ | 0.220692 $(\pm 0.0090)$ | 0.484187
Random | GAN | xgboost | 0.962508 $(\pm 0.0011)$ | 0.566755 $(\pm 0.0121)$ | 0.420893
random | 0.962508 $(\pm 0.0011)$ | 0.566755 $(\pm 0.0121)$ | 0.480556
KDE | xgboost | 0.962508 $(\pm 0.0011)$ | 0.810647 $(\pm 0.0277)$ | 0.38334
| random | 0.962508 $(\pm 0.0011)$ | 0.810647 $(\pm 0.0277)$ | 0.400145
| Random | xgboost | 0.962508 $(\pm 0.0011)$ | 0.220692 $(\pm 0.009081)$ | 0.434184
| random | 0.962508 $(\pm 0.0011)$ | 0.220692 $(\pm 0.0090)$ | 0.613355

###  B.4 Downstream Tasks

Common downstream tasks in graphs are node classification and edge
classification. As the proposed framework can generate both node-level and
edge-level features, we can accommodate these various tasks using the proposed
generator. To this end, we train our synthetic data generator on both node
classification and edge classification datasets and subsequently generate a
graph of the same size for pre-training. Finally, we fine-tune the real
dataset. The results are presented in 5. For node-classification task we use
the Cora [32] as toy example which is a citation network dataset, with node
labels as topics and features as multi-hot vectors; and for edge-
classification task the ieee-fraud dataset contains edge features as well as
label denoting whether a particular transaction is fraudulent. For all
datasets, we train the models for a maximum of 200 epochs (fine-tuning epochs
+ pre-training epochs) and use Adam [33] with a starting learning rate of
0.01, with early stopping after ten epochs of no improvement on a held-out
validation set as defined by the original datasets. The networks are 2-layer
GCN [3], GAT[4] models with hidden dimension set to 128.0.

Table 5:  Comparison of Pre-training followed by fine-tuning for node
classification and edge classification tasks.

Dataset | Generator | Model |  Accuracy $\uparrow$
---|---|---|---
Cora | random | GCN |  $0.7470$ $(\pm 0.0025)$
GAT |  $0.7595$ $(\pm 0.0102)$
ours | GCN |  $0.7677$ $(\pm 0.0014)$
| GAT |  $0.7720$ $(\pm 0.0061)$
| no-pretraining | GCN |  $0.76275$ $(\pm 0.0008)$
| GAT |  $0.7650$ $(\pm 0.0077)$
ieee-fraud | random | GCN | 0.9788
GAT | 0.9793
ours | GCN | 0.9831
| GAT | 0.9840
| no-pretraining | GCN | 0.9823
| GAT | 0.9830

##  Appendix C Dataset Details

Constructing graphs from a tabular dataset requires capturing sample
relations. Unlike graph datasets that have the structure and features given
directly, sample relations are not immediately given in tabular settings. As a
result, these need to be extracted from the data. In practice, tabular
datasets are from very diverse domains ranging from fraud detection to
recommender systems and electronic health records; these relationships require
to be inferred from the features with domain knowledge. The feature columns
used for extracting the corresponding relationship and edges from the tabular
dataset are summarized in Table. 6.

Table 6:  Details on how to construct graph from tabular features. Node column
corresponds to the set of features used to construct node types, and the
condition column details the condition that must be satisfied for an edge to
exist between the nodes.

Dataset |  Nodes |  Condition
---|---|---
Tabformer |  concat(User, Card) Merchant ID |  same row
IEEE-Fraud |  concat($7$ features)222(addr1, addr2, card1, card2, card3, card4, card5, card6) concat($2$ features)333(ProductCD, R_emaildomain) |  same row
Paysim |  nameOrig nameDest |  same row
Credit |  concat(first, last) merchant |  same row

##  Appendix D Experiment Details

We provide details on hyperparameters used in our experiments. Our structural
generator has a fitting portion that fits the underlying dataset without
requiring the user to specify the parameters. The
XGBoost444https://rapids.ai/xgboost.html aligner learning rate is set to a
default value of 0.1, max depth of 5, and the number of estimators is set to
100, with an alpha value of 10., We set the hidden dimensions to be equal to
the input dimension. For all experiments for training to our proposed method,
we use Adam [33] optimizer with an initial learning rate of $1e-3$ decayed
every ten epochs by a factor of $0.1$ and trained for a maximum of $20$ epochs
with early stopping. Note that we train on the complete input data and do not
split the dataset into train, validation, and test splits as we aim to
generate a single graph while our input is also a single graph. For most
datasets, it suffices to train the feature generator for about $5$ epochs.
Note that for datasets that contain categorical columns, the embedding size
for these columns is set to $min(600,round(1.6*|D|^{0.56})$ where $|D|$ is the
number of unique values for the categorical column. Our code is available on
Github 555https://github.com/¡anon¿/¡anon¿

##  Appendix E Software & Hardware

To ensure reproducibility, all experiments were run using the same random
seed, and software versions. Experiments were run on a machine with 32GB
V100s, 504GB RAM, and 80 CPUs Intel XEON E5-2698 v4 using CUDA version 11.4.

Table 7: Python dependencies.

Dependency | Version
---|---
python | 3.8.12
pytorch | 1.11.0
dgl | 0.72
numpy | 1.22.3
cudf | 21.12
pandas | 0.24.1
scikit-learn | 0.24.2
scipy | 1.7.2
xgboost | 1.5.0