Scalable and Privacy-enhanced Graph Generative Model for Graph Neural Networks
Authors: Minji Yoon
Yue Wu
John Palowitch
Bryan Perozzi
Russ Salakhutdinov
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph generative model
graph neural networks
graph convolutional networks
benchmark graph generation

Abstract: As the field of Graph Neural Networks (GNN) continues to grow, it experiences a corresponding increase in the need for large, real-world datasets to train and test new GNN models on challenging, realistic problems. Unfortunately, such graph datasets are often generated from online, highly privacy-restricted ecosystems, which makes research and development on these datasets hard, if not impossible. This greatly reduces the amount of benchmark graphs available to researchers, causing the field to rely only on a handful of publicly-available datasets. To address this dilemma, we introduce a novel graph generative model, Computation Graph Transformer (CGT) that can learn and reproduce the distribution of real-world graphs in a privacy-enhanced way. Our proposed model (1) generates effective benchmark graphs on which GNNs show similar task performance as on the source graphs, (2) scales to process large-scale real-world graphs, (3) guarantees privacy for end-users. Extensive experiments across a vast body of graph generative models show that only our model can successfully generate privacy-controlled, synthetic substitutes of large-scale real-world graphs that can be effectively used to evaluate GNN models.

SCALABLE AND PRIVACY-ENHANCED GRAPH GENERA- TIVE MODEL FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
As the field of Graph Neural Networks (GNN) continues to grow, it experiences a corresponding increase in the need for large, real-world datasets to train and test new GNN models on challenging, realistic problems. Unfortunately, such graph datasets are often generated from online, highly privacy-restricte ecosystems, which makes research and development on these datasets hard, if not impossible. This greatly reduces the amount of benchmark graphs available to researchers, causing the field to rely only on a handful of publicly-available datasets. To address this dilemma, we introduce a novel graph generative model, Computation Graph Transformer (CGT) that can learn and reproduce the distribution of real-world graphs in a privacy-enhanced way. Our proposed model (1) generates effective benchmark graphs which GNNs show similar task performance as the source graphs, (2) scales to process large-scale real-world graphs, (3) guarantees privacy for end-users. Extensive experiments across vast body of graph generative models show that only our model can successfully generate privacy-controlled, synthetic substitutes of large-scale real-world graphs that can be effectively used evaluate GNN models.
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf & Welling 2016a; Chami et al. 2022) are machine learning models that learn the dependences graphs via message passing between nodes. Various GNN models have been widely applied on variety of industrial domains such as misinformation detec- tion (Benamira et al., 2019). financial fraud detection (Wang et al.) 2019a), traffic prediction (Zhao) al., 2019), and social recommendation (Ying et al. 2018). However, datasets from these industrial tasks are overwhelmingly proprietary and rrivacy-restricted and thus almost always unavailable for researchers to study or evaluate new GNN architectures. This state-of offie-of-fffrrss means that in many cases, GNN models cannot be trained or evaluated on graphs that are appropriate for the actual tasks that they need to execute. This scarcity of real-world benchmark graphs also leaves GNN researchers with only a handful of public datasets, which could potentially cause new GNN architectures to optimize performance only on these public datasets rather than generalizing (Palowitch et al., (002)).
In this paper, we introduce a novel graph generative model to overcome the unavailability of critical real-world graph datasets. While there is already vast body of work on graph generation (You et al. 20188 Liao et al., 2019 Simonovsky & Komodakis 2018) Grover et al., 2019). including infferentialll-priveee
generation (Qin et al. al.] [2017] Proserpoo et al. 20022), we found that no one study has addressed all aspects of the modern GNN problem setting, such as handling large-scale graphs and node attributes/labels. We thus propose a novel, modern graph generation problem definition:
Problem Definition 1. Let A, X, and y denote adjacency, node attribute, and node label matrices; given an original graph G = (A, generate a synthetic graph G' (A', X',"""") .Y") satisfying:
Benchmark effectiveness: performance rankings among GNN models on G should be similar to the rankings among the same m GNN models on G.
Scalability: computation complexity of graph generation should be linearly proportional to the size of the original graph O(IG)) (e.g., number of nodes or edges).
Privacy guarantee: any syntactic privacy notions are given end users (e.g., k-anonymity).

---

To address this problem statement, introduce the Computation Graph Transformer (CGT) the core of a graph generation approach with two novel components. First, CGT operates on minibatches rather than the whole graph, avoiding scalability issues encountered with nearly all existing graph generative models. Note that each minibatch is in fact a GNN computation graph (Hamilton et al. 2017) having its own adjacency and feature submatrices, and the set of all minibatches comprises graph minibatch distribution that can be learned by an appropriate generative model.
Second, instead of attempting learn the joint distribution of adjacency matrices and feature matrices, we derive a novel duplicale encoding scheme that transforms a (A, X) adjacency and feature matrix pair into a single, dense feature matrix that is isomorphic to the original pair. In this way we are able to reduce the task of learning graph distributions to learning feature vector sequence distributions, which we approach with a novel Transformer architecture (Vaswani et al., 2017). This reduction the key innovation allowing CGT to be an effective generator of realistic datasets for GNN research. In addition, after the reduction process, our model can be easily extended to provide k-anonymity or differential privacy guarantees on node attributes and edge distributions.
To show the effectiveness of CGT, we design three experiments that examine its scalability, its benchmark effectiveness as substitute generator of source graphs, and its privacy-pefforancee trade-off. Specifically, to examine this benchmark aspect, we perturb various aspects of the GNN models and datasets, and check that these perturbations bring the same empirical effect GNN performance on both the original and generated graphs. In total, our contributions are: 1) we propose novel graph generation problem featuring three requirements in state-of-the-art graph learning settings; 2) we reframe the problem of learning a distribution of a whole graph into learning the distribution of minibatches that are consumed by GNN models; 3) we propose the Computation Graph Transformer, an architecture that casts the problem of computation graph generation as conditional sequence modeling; and finally 4) we show that the test performance of GNN models in 14 different task scenarios is consistent across real-world graphs and their corresponding synthetic graphs.
RELATED WORK
Traditional graph generative models extract common patterns among real-world graphs (e.g. nodes/edge/triangle counts, degree distribution, graph diameter, clustering coefficient) (Chakrabarti & Faloutsos, 2006) and generate synthetic graphs following few heuristic rules (Erdös et al.] 1960 Leskovec al. 2010 Leskovee & Faloutsos 2007 Albert & Barabási (002). However, they cannot generate unseen patterns synthetic graphs (You et al.) 2018). More importantly, most of them generate only graph structures, sometimes with low-dimensional boolean node attributes (Eswaran)
et al.
2018). General-purpose deep graph generative models exploit GAN (Goodfellow et al.
2014).
VAE (Kingma & Welling 2013), and RNN (Zaremba et al. 2014) to learn graph distribu-
tions
Guo & 2020). Most of them focus on learning graph structures You al. 2018 Liao
et al.
2019] Simonovsky & Komodakis 2018 Grover et al. 2019), thus their evaluation metrics graph statistics such orbit counts, degree coefficients, and clustering coefficients which do not consider quality of generated node attributes and labels. Molecule graph generative models actively studied for generating promising candidate molecules using VAE (Jin et al., (008))
GAN (De Cao & Kipf 2018). RNN (Popova et al., 2019). and recently invertible flow models (Shi al., 2020 Luo et 2021). D.. However, most of their architectures are specialized to small-scaled molecule graphs (c.g., 38 nodes per graph in the ZINC datasets) with low-dimensional attribute space (e.g., boolean node attributes indicating atom types) and distinct molecule-related information (e.g..
SMILES representation or chemical structures such as bonds and rings) (Suhail et al. (021).
FROM GRAPH GENERATION TO SEQUENCE GENERATION
To develop a scalable and
benchmark graph generative model for GNNs, we first look into how GNNs process given graph G. With n nodes and d-dimensional node attribute vectors, g is commonly given as a triad of adjacency matrix A E Raax,, node attribute matrix X' E Rnnd and node label matrix ) IR.. In this section, we illustrate how convert the whole-graph generation problem into iiscrete-valuee sequence generation problem.
2

---

AREEOFF PN
ABEEDFT
11:1
BCDGH
1.1
DGR
11:2
[a] Input graph
(b) Computation graphs of node A, B, and sampled from input graph
[c] Computation graphs encoded by duplicate scheme
Figure 2-layered computation graphs with s neighhor samples: (a) input graph; (b) original encoding scheme results in differently-shaped adjacency (hlue) and attribute (yellow) matrices per computation graph; (c) duplicate encoding seheme outputs the same adjacency matrix and shaticaalll-shpped attribute matrices.
3.1
COMPUTATION GRAPHS MINIBATCH- BASEDD GNN TRAINING
To compute embeddings of node v, L-layered GNNs extract the node's L-hop egonet Go. namely the computation graph. Specifically, as with the global graph, Go is composed of a sub-adjacency matrix A. R "R, sub-feature matrix X, R" and node v's label E R. where each of n, rows correspond to nodes sampled into the computation graph. Minibatch-based GNN training samples computation graph per each node in minibatch and GNN models those computation graphs which are much smaller than the whole graph. Based on this observation, our problem reduces to: given a set of computation graphs {G, (A,, N.)
G} sampled from an original graph, we generate set of computation graphs [g' = (A',. A. )%)) This reframing shares intuition with mini-batch stochastic gradient descent that the distribution of randomly chosen subsets approximates the distribution of the original set (Bottou 2010).
3.2 ENCODING SCHEME FOR COMPUTATION GRAPHS
In this work, sample fixed-size set of neighbors to generate computation graphs instead of using the full neighborhood, as proposed by GraphSage (Hamilton et al.] (017), technique also widely adopted in popular GNN libraries (Fey & Lenssen 2019 Ferludin et al. 20022 Wang al. 2019b) to fix the minibatch computational footprint. To train L-layered GNN model with sperispee neighbor sampling number s. computation graph is generated for each node top-down manner (1: - 1): A target node is located at the I-tth layer; the target node samples neighbors, and the sampled nodes are located at the (I. 1) 1)-th layer; each node samples s neighbors, and the sampled s² nodes are located at the (L 2)-th layer; repeat until the 1-st layer. When the neighborhood is smaller than 8, we sample all existing neighbors the node.
Generating computation graph is similar to generating balanced s-nary tree structure. For example, a balanced binary tree-shaped computation graph is generated for node A in Figure with neighbor sampling number 2. However, in practice, computation graphs are almost always unbalanced s-nary trees due to one of two cases: (1) lack of neighbors, and (2) neighbor sharing. In Figure [(b), B's computation graph is unbalanced tree because node C has neighbors (case 1). In D computation graph, nodes D and G share node H as neighbors, creating a cycle in the computation graph (case 2). These two cases result in variably-shaped of adjacency and node attribute matrices of computation graphs shown as blue and yellow boxes in Figure (b).
3.3 DUPLICATE ENCODING SCHEME FOR COMPUTATION GRAPHS
We introduce duplicate encoding scheme for computation graphs that is conceptually simple but brings a significant consequence: it fixes the adjacency matrix for all computation graphs, allowing us to model it constant. To circumvent scheme defines a null node with zero attribute vector (node in Figure T(c) and samples it as padding neighbor for any node with less than neighbors. To eircumvent case 2, the duplicate
1 from the previous paragraph. the duplicate encoding
3

---

Variable-shape computation graphs
Fixed
Original graph
computation
Normal GHN flow
Computaion grahicampling
In (Ar)
Gi (lulls
Dupiccation encoding
Ace E3
Benchmark graph
g (A.X.V)
GNN
generation for GNNS
S Age [goss
Acs-
Quantization
(5,35)
Camputation Graph
De-quantization
Aes
Aep- yo''s
GNN
(5:3)
Original
Fised-shape
cluster id sequences
cluster id sequeincss
computation
Figure 2: Overview of our benchmark graph generation framework: (1) We sample a set computation graphs of variable shapes from the original graph, then (2) duplicate-encode them to fix adjacency matrices to a constant. (3) coplicate-nncodyy feature matrices are quantized into cluster id sequences and fed into our Computation Graph Transformer. (4) Generated cluster id sequences de-quantized back into duplicate- encoded feature matrices and fed into GNN models with constant adjacency matrix.
encoding scheme copies shared neighbors and provides each copy to parent nodes (node H in node D's computation graph is copied in Figure [c)). Each node attribute vector is also copied and added to the feature matrix. As shown in Figure [c). the duplicate encoding scheme ensures that computation graphs have identical adjacency matrix (presenting balanced s-nary tree) and an identical shape of feature matrices. Note that in order to fix the adjacency matrix, we need to fix the order of nodes in adjacency and attribute matrices (e.g., breadth-firg ordering in Figure [c)).
Because our duplicate encoding scheme fixes the adjacency structure over all computation graphs, our problem reduces to learning the distribution of (duplicate-encodes feature matrices of computation graphs, formalized as: given a set of feature matrix-labe pairs {(Kg, Vo) g} of duplicate- encoded computation graphs, we generate set of feature matrix-label pairs (2,,)))
3.4 QUANTIZATION
To learn distributions of feature matrices of computation graphs, we first quantize feature vectors into discrete bins; specifically, we cluster feature vectors in the original graph using k-means and map each feature vector its (discrete) cluster id. Quantization is motivated by 1) privacy benefits and 2) ease of modeling. By mapping different feature vectors (which are clustered together) into the same cluster id, we can guarantee k-anonymity among them (more details Section 4.2). Ultimately, quantization further reduces our problem to learning distributions over sequences of discrete values, namely the sequences of cluster ids of feature vectors each computation graph. Such a problem is naturally addressed by Transformers, state-of-the-as sequence generative models (Vaswani et al.) 2017). In Section 4 we introduce the Computational Graph Transformer (CGT), a novel architecture which (at inference time) generates mean feature vector of the cluster.
sequence of cluster ids, which are then de-quantized the
3.5 END-TO-END FRAMEWORK FOR BENCHMARK GRAPH GENERATION PROBLEM
Figure 2 summarizes the entire process of mapping a graph generation problem into a discrete sequence generation problem. In the training phase, we 1) sample a set of computation graphs from the input graph. 2) encode each computation graph using the duplicate encoding scheme to fix adjacency matrices, 3) quantize feature vectors to cluster ids they belong to, and finally 4) hand over set of (sequence of cluster ids, node label) pairs to our new Transformer architecture to learn their distribution. In the generation phase, we follow the same process in the opposite direction: 1) the trained Transformer outputs set of (sequence of cluster ids, node label) pairs, 2) we de-quantize cluster ids back into the feature vector space by replacing them with the mean feature vector of the cluster, 3) we regenerate computation graph from each sequence of feature vectors with the adjacency matrix fixed by the duplicate encoding scheme, and finally 4) we feed the set of generated computation graphs into the GNN model want train evaluate.
4

---

Input computation graph
Computation Transformerr (CGT)
Cost efffefffnnntt version
R
AF
PC
A
AG
Node C's ancestors
Suery
A
AG
Contoct
Divide into shorter
Requences comp uoed
R2
A
AT
Pg
Label
Poeilion
anbedddigg
Iepet
sequeence
Figure 3: Computation Graph Transformer (CGT): (a.b) Given a sequence flattened from the imput computa- tion graph, CGT generates context the forward direction. e(se). ( and h,") denote the token, query, and context embedding of (-th token at I-th layer; Pi(e) and yos denote the position embeddings label embedding of the whole sequence, respectively. (c) The cost-efficient version of CGT divides the input sequence into shorter ones composed only of direct ancestor nodes.
token and
4 MODEL
We present the Computation Graph Transformer (CGT) that casts computation graph generation as conditional sequence modeling with minimal modification to the Transformer architecture. Then we check our model satisfies the privacy and scalability requirements from Problem Definition [
4.1 COMPUTATION GRAPH TRANSFORMER
In this work, we extend a two-stream self-attention mechanism, XI.Net Yang et al. 2019). which modifies the Transformer architecture (Vaswani et al./ 2017) with a causal self-attention mask to enable auto-regressive generation. Given a sequence s = [11.-.. , ST.. the M M-layered Transformer maximizes the likelihood under the forward auto-regressive factorization as follows:
T Σ (s.(5())))
= Σ log exp(g) (L) (51.-1) t=1 Es exp(4) (s==-1)Te(s'))
T
max
where token embedding e(st) maps discrete input id 8t randomly initialized trainable vector, and query embedding % ($1=-1) encodes information until (t- 1)-th token in the sequence. More details on the Transformer architecture can be found in the Appendix A.8 Here describe how modify XLNet to model our computation graph effectively.
Position embeddings: In the original architecture, each token receives position embedding to let the Transformer recognize the token's position in the sequence. In our model, however, sequences are flattened computation graphs (e.g., input computation graph in Figure 3[a) a) is flattened into input sequence in Figure B b)). To encode the original computation graph structure, we provide different position embeddings to different layers in the computation graph, while nodes at the same layer share the same position embedding. When I(l) denotes the layer number where (-th token (node) is located at the original computation graph, position embedding Pi(e) indexed by the layer number assigned to t-th token. In ( node C, D. F and H located the 1-st layer in the computation graph have the same position embedding
the original architecture, query and context embeddings, q.") and h attend to all context embeddings b before t. In the computation graph, each node is sampled based on its parent node (which sampled based on its own parent nodes) and not directly affected by its sibling nodes. To encode this relationship more effectively, we mask all nodes except direct ancestor nodes in the computation graph, i.c., the root node and any nodes between the root node and the leaf node. In Figure bb) node C's context/query embeddings attend only to direct ancestors, nodes A and B. Note that the number of unmasked tokens are fixed to L in our architecture because there always L - 1 direct ancestors in L-layered computation graphs. Based this observation, we provide cost-efficient version of CGT that has shorter sequence length and preserves XLNet's ruto-segressive masking shown in Figure cc).
Attention Masks:
5

---

Label conditioning: Distributions of neighboring nodes not only affected by each node's " feature information but also by its label. It is well-known that GNNs improve over MLP performance by adding convolutional operations that augment each node's features with neighboring node features. This improvement is commonly attributed to nodes whose feature vectors are noisy (outliers among nodes with the same label) but that connected with "good" neighbors (whose features well- aligned with the label). In this case, without label information, we cannot learn whether node has feature-wise homogeneous neighbors or feature-wise heterogeneous neighbors but with the same labels. In our Transformer model, query embeddings li are initialized with label embeddings ys: that encode the label of the root node 81.
4.2 THEORETICAL ANALYSIS
First, our framework can be easily extended to provide k-anonymity for node attributes and edge distributions by using k-means clustering with the minimum cluster size (Bradley et al. 2000) during the quantization phase. Note that we define edge distributions as neighboring node distributions of each node. The full proofs for the following claims can be found in Appendix
Claim 1 (k-anonymity for node attributes and edge distributions). In the generated computation graphs, each node attribute and edge distribution appear at least k times, respectively.
Next, we can provide differential privacy (DP) for node attributes and edge distributions by exploiting DP k-means clustering (Chang al. (021]) during the quantization phase and DP stochastic gradient descent (DP-SGD) (Song et al. 2013) to train the Transformer. Unfortunately, however, DP-SGD for transformer is not well developed yet practically. So
not guarantee the rigid DP for edge distributions in practice (experimental results in Section [.44 and more analysis in Appendix A.1) Thus, here, claim DP only for node attributes.
Claim 2 ((c, 8)- Diffferrentia Privacy for node attributes). With probability at least 1- 5, our generative model gives e-differential privacy for any graph G, any neighboring graph G-v without any node E G, and any computation graph Gog generated from our model as follows:
Pr[A(g)= =eag ce
e
Pr[A(G_.) Gogl
Finally, we show that CGT satisfies the scalability requirement in Problem Definition
Claim 3 (Scalability). When aim generate T.-layered computation graphs with neighbor sampling number s on a graph with n nodes, computational complexity of CGT training is ((s and the cost-efficient version is 2
EXPERIMENTS
We aim to show that (1) CGT scales to learn distributions of large-scale real-world graphs; (2) CGT generates synthetic graphs on which GNNs perform similarly to the original graphs; (3) synthetic graphs generated by CGT sufficiently private; and (4) CGT preserves distributions of graph statistics defined on the original set of computation graphs.
5.1 EXPERIMENTAL SETTING
We evaluate on seven public datasets three citation networks (Cora, Citeseer, and Pubmed) (Sen al. 2008), two co-purchase graphs (Amazon Computer and Amazon Photo) (Shchur et al. 2018), and two co-authorship graph (MS CS and MS Physic) (Shchur et al. 2018). To measure GNN performance similarity, we popular GNN architectures on pair of original and synthetic graphs, then measure Pearson and Spearman correlations (Myers et al. 2013) between the resultant performance metrics on each type of graph.
5.2 SCALABILITY
To the best of our knowledge, other generic graph generative model was designed output triad of the adjacency matrix, node attribute matrix, and node labels. We extend two VAE-based graph generative models, GVAE (Kipf & Welling 20166) and Graphite (Grover et al. 2019) to generate

---

Table 1: GNN performance original and generated graphs in three different scenarios with three variations, # NE denotes number noise edges and denotes the PPR coefficient used for distribution shift.
Aggregation with moise (Citeseer)
Sampling with noise (Amazon Photo) model
Distrihution shift (MS Phayie)
#NE
model
Original
Generaled
ANE
Original
Generaled
model
Original
Generated
GCN
0,73+0,004
0.5940.024
GSage
0,75+0.099
0,53+0,028
GSage
0,92-0.002
0.84+0,008
SGC
GIN
0.7310.902
0.71+0.009
0.5840.029
0,5940002
AS-GUN
FastGCN
0.14:0.016
0.92200004
0.12+0.020
0.87+0.002
iid
GAT
0.92-0.01
0.93+0.002
08440/8077
0.22000111
GAT
0.71+0.003
0,57+0.029
PASS
0.85+0.001
0.54+0.049
PENP
0.92+0.005
0.84+2,007
GCN
0,5740,005
0,4640.013
GSage
0,4000013
0.36+0.009
GSage
0,3300033
0.76:0.019
2
GIN
SGC
0.57+0.805
0,54+0.020
0,68+0.015
04740.0019
AS-GUN
FastGCN
0,57+0.005
0.1240014
0.81+0.010
0.11+0.027
0.01
GAT
SGC
0.84-0.004
0,87+00077
0.74+0.015
0.78+0.009
GAT
0,57+0,014
0,64+0.010
PASS
0.73+0.088
0.59-0.011
PPNP
0,84-0.007
0,74+0,009
GCN
0.31+0,027
0,4100,001
GSage
0.20+0009
0,2040014
GSage
0,24-00112
0.08+0:225
SGC
GIN
0.48
0.5240.0009
4.4140.005
0.41+00007
AS-GCC
FastGCN
0.677600003
0.1040:025
0.62+00006
0.13+0.054
0.3
GAT 0.85-00011
SGC
0.8140.009
0.72+0.019
0,7040.009
GAT
0,4940.012
0,4040.009
0.64:0017
0.50-0.017
PPNP
0.1-00012
0.7040.019
Pearsun/ /Spearman
059977
099870996
0,22700155
Table 2: Benchmark effectiveness on node classification. Pearson and Spearman scores measure the correlation in ranking of GNN models on original and generated graphs; a score of denotes perfect correlation.
Aggregation with nobsc
Sompling with nodse
Sampling number
Distribution shift
Dataset
Peurson
Spcurman
Peorson
Spearman
Pearson
Spearman
Pearson
Spearman
0:934
0.950
0.943
0.894
0.967
0.514
0.867
0.833
CHeseer
0.964
0.977
0.975
0,504
0.812
0.759
Pubmed
0.818
0,791
0.900
0.867
0.989
0.824
0.830
0.794
Amazon Computer
0.825
0.778
0.885
0.916
0,975
01.800
019006
0.366
Photo
0,893
0.916
0.5311
0.847
MS CS
0.922
0.956
0.986
0.901
0.793
MS Physic
0.661
0.685
0.956
0.951
0.947
0.901
0.925
0.815
node attributes and labels in addition to adjacency matrices from their latent variables. We also choose three molecule graph generative models, GraphAF (Shi et al.) (020), GraphDF (Luo et al.) 202I), and GraphEBM (Suhail et al.. [02I), that do not rely on any molecule-specific traits (e.g.. SMILES representation). GraphAF, GraphDF, and Graphite meet out-of-memory errors even the smallest dataset, Cora (Table Appendix A.2). This is not surprising, given they were originally designed for small-size molecule graphs. The remaining baselines (GVAE and GraphEBM), however, fail to learn any meaningful node attribute/label distributions from the original graphs. For instance, the predicted distribution sometimes collapses to generating the the same node feature/labels across all nodes, which is obviously not the most effective benchmark (100% accuracy for all GNN models). We show their results and our analysis in the Appendix [A.2] Only our method can successfully generate benchmark graphs across all datasets with meaningful node attribute/label distributions (Tables and 2)
5.3
BENCHMARK EFFECTIVENESS
To examine the benchmark effectiveness of our generative model, we design different scenarios where the performance of different GNN architectures varies widely. In each scenario, we provide 3 variations to graphs and run 4 GNN models on each variation. For each scenario-variation, we report Pearson and Spearman correlations of the GNN performance metrics on the original graph against those on the generated graph. Due to the space limitation, we present detailed GNN accuracies only on a few datasets/scenarios in Table ! Results on other datasets can be found in Appendix [A.3 Note that Table presents the correlation coefficients across all datasets and scenarios. Descriptions of each GNN model can be found in the Appendix AA..1
A...1
SCENARIO 1: noisy edges on aggregation strategies. We choose four different GNN models with different aggregation strategies: GCN (Kipf & Welling 2016a) with mean aggregator, GIN (Xu eet al. 2018) with sum aggregator, SGC (Wu et al.] (0099) with linear aggregator, and GAT (Veličković 2017) with attention aggregator. Then we modify the graph by adding different numbers of
et al. noisy edges (randomly connected with any node in the graph) to each node and check how the GNN performance changes. In Table 1 first three columns show the result in the Citeseer dataset. When more noisy edges are added, the accuracy across all GNN models drops in the original graphs. These trends can be nearly exactly captured in GNN performance on the generated graphs (both Pearson and Spearman correlation rates are up to 0.964). This shows that the synthetic graphs generated by method successfully capture the noisy edge distributions introduced in the original graphs.
7

---

SCENARIO 2: noisy edges on neighbor sampling. We choose four different GNN models with different neighbor sampling strategies: GraphSage (abbreviated as GSage in Table 1 (Hamilton et al. 2017) with random sampling, FastGCN (Chen et al.] 2018) with heuristic layer-wise sampling AS-GCN (Huang et al. 2018) with trainable layer-wise sampling, and PASS (Yoon et al. 2021 with trainable node-wise sampling. We then add noisy edges described in the ENV and check how the different sampling policies deal with noisy neighbors. In Table[] FastGCN shows highest accuracies across different number of nosiy edges, followed by PASS, GraphSage, and AS-GCN on the original graphs on the Amazon Photo dataset; and this trend is well well-preserved on the generated graphs, showing 0.958 Pearson correlation.
Table 3: Benchmark effectiveness and GNN per- formance on link prediction.
SCENARIO 3: different sampling numbers neighbor sampling. We choose the same four GNN models with different neighbor sampling strategies as in EV2. Then we change the num- ber of sampled neighbor nodes and check how the
Datasct
Spearman
Pcarson
Spearman
Cura
0.781
0.71l
Gitsserr
0.808
0.824
Pubmed
0.742
0.754
GNN performance is affected. As shown in Table trends among original graphs - more neighbors are sampled, GNN performance generally increases - -rre successfully captured in the generated graphs with 0.991 and 0.931 Pearson and Spearman cor- relations, respectively, across all datasets. You can find the detailed GNN accuracies in Appendix A.3
Amazaa
0,822
0.599
Amazoal
0,887
0.443
Dataset
Predictor
Model
Original
Generuted
0.6940..07
0.65+0:026
Dot
SGC
GIN
0.8340.008
0.70+0.003
0.69-0.010
0.67+0.022
Citesser
GAT
0.5840.005
0.75+0.005
0.68+0.021
0.59+0:010
MLP
GIN
SGC
0,5740.011
0.5840.008
0.61+0.024
0.59+0:023
GAT
0.61+0.005
0.62+6.009
SCENARIO 4: distribution shift. Zhu et al.
202T) proposed biased training set sampler to examine each GNN model's robustness to distribution shift between the training/test time. The biased sampler picks few seed nodes and finds nearby
nodes using the Personalized PageRank vectors (Page et al. 1999) Tppr = (T (1 ax) A) with decaying coefficient at then uses them to compose biased training set. We choose the same GNN models, GCN (Kipf & Welling, 2016a), SGC (Wu et al. 2019). GAT (Veličković et al. (017)) and PPNP (Klicpera et al.) 2018). as the original paper (Zhu et al. 2021) chose for their baselines. We vary and check how each GNN models deal with the biased training set. In the last three columns in T [ the performance of GNN models drops as a increases, and the generated graphs successfully capture these trends.
Link prediction. As nodes are the minimum unit in graphs that compose edges or subgraphs, we can generate subgraphs for edges by merging computation graphs of their component nodes. Here we show link prediction results on original graphs are also preserved successfully on our generated graphs. We run GCN, SGC, GIN, and GAT on graphs, followed by Dot product or MLP to predict link probabilities. Table Ihoows Pearson and Spearman correlations across 8 different combinations of link prediction models (4 GNN models x 2 predictors) on each dataset and across the whole datasets. The lower table shows the detailed link prediction accuracies on the Citeseer dataset. Our model generates graphs that substitute original graphs successfully, preserving the ranking of GNN link prediction performance with 0.754 Spearman correlation across the datasets.
Table 4: Privacy- performance trade-off in graph generation on the Cora dataset
Original
No privacy
à 100
K K-amonymity
k 500
1000
DP kmmsn (5 0.01)
10
25
10
SGD = 0.1)
10
Pearson
1,000
0.934 0.935
0.916
0.862 0.812
0.030 00018
03774 0309
0.844
0.04
0,112 0.116
0,800
Spearman
1,000
0.947
0.805
0.807
0.599
5.4 PRIVACY
We examine the performaace-privaacy trade-off across different privacy guarantees. For k-anonymity, we use the k-means clustering algorithm |Bradley et al. (0000) varying the minimum cluster size k. For Differential Privacy (DP) for node attributes, privacy cost while setting d = 0.01. As expected, in Table [ higher and smaller e (L.c., stronger privacy) hinder the generative model's ability to learn the exact distributions of the original graphs,
use DP k- k-maans (Chang al. (222]) varying the
8

---

Computer
Mosppacee greatts
Original vactore
Conerated
26
origiral eduplicate vectors
Gonerated eduplicate
(a) # zero vectors on each computation graph
(b) # redundant vectors on each computation graph
Figure 4: CGT preserves distributions of graph statistics in generated graphs for each dataset: Duplicate encoding infuses graph structure into feature matrices of computation graphs. In cach computation graph, # zero vectors inversely proportional edge density, while # redundant vectors is proportional # cycles.
and the GNN performance gaps between original and generated graphs increase (lower Pearson and Spearman coefficients). Detailed GNN accuracies could be found in Table [2 in Appendix A.4 To provide DP for edge distributions, we use DP stochastic gradient descent (Song et al. 2013) train the transformer, varying the privacy cost while setting 8 = 0.1. In Table even with astronomically low privacy cost (c = 10%), the performance of our generative model degrades significantly. When set 10 (which is impractical), we can finally see reasonable performance. This shows the limited performance of DP SGD on the transformer architecture.
5.5
GRAPH STATISTICS
Given a source graph, our method generates a set of computation graphs without any node ids. In other words, attackers cannot merge the generated computation graphs to restore the original graph and re-identify node information. Thus, instead of traditional graph statistics such as orbit counts clustering coefficients that rely on the global view of graphs, define graph statistics for computation graphs that are encoded by the duplicate scheme. Duplicate scheme fixes adjacency matrices across all computation graphs by infusing structural information (originally encoded in adjacency matrices) into feature matrices. Number of zero vectors (corresponding to null nodes that padded when node has fewer neighbors than sampling neighbor number) is inversely proportional to edge density in a computation graph. Number of duplicate feature vectors (which are duplicated when nodes share neighbors) is proportional to number (#) of cycles computation graph, indicating how densely nodes are connected in the computation graph. In Figure 4 we present distributions of number of zero vectors and number of redundant vectors each computation graph has on each dataset. Five different datasets show distinct distributions on these two statistics, and distributions both statistics are well preserved generated graphs. For instance, in Figure [a) green lines (Pubmed) are lower than purple and red lines (Amazon Computer and Amazon Photo) at the beginning and become higher in both plots. In Figure (bb) purple lines (Amazon Computer) are slightly higher than red lines (Amazon Photo) until 300, then become lower in both plots. In the same figure, blue, yellow, and green lines (Cora, Citeseer, and Pubmed) decrease sharply compared to purple and red lines (Amazon Computer and Amazon Photo) in both plots. This shows generative model preserves graph structures encoded in feature matrices successfully.
6 CONCLUSION
We propose a new graph generation problem to enable generating benchmark graphs for GNNs that follow distributions of (possibly proprictary) source graphs with three requirements: 1) benchmark effectiveness, 2) privacy guarantee, and 3) scalability. With novel graph encoding scheme, we reframe a large-scale graph generation problem into a medium-length sequence generation problem and apply the strong generation power of the Transformer architecture to the graph domain.
Limitation of the study: This paper shows that clustering solutions can achieve k-anonymity privacy guarantees. We stress, however, that implementing a real-world system with strong privacy guarantees will need to consider many other aspects beyond the scope of this paper. We leave future work the study of whether we can combine stronger privacy guarantees with those of k-anonymity to enhance privacy protection.

---

REFERENCES
Réka Alhert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Adrien Benamira, Benjamin Devillers, Etienne Lesot, Ayush K Ray, Manal Saadi, and Fragkiskos D Malliaros. Semi-supervised learning and graph neural networks for fake news detection. In 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 568-569 IEFF, 2019.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pp. 177-186. Springer, 2010.
Paul S Bradley, Kristin P Bennett, and Ayhan Demiriz. Constrained k-means clustering. Microsoft Research, Redmond, 20(0):0, 2000.
Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1) 28(1):2-es, 2006.
Ines Chami, Sami Abu- Mae--E-HHaae -aija Bryan Perozzi, Christopher RAO, and Kevin Murphy, Machine
learning on graphs: A model and comprehensive taxonomy. Jourmal of Machine Learning Research, 13(89):1-64, 2022. URL
Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In International Conference Machine Learning, pp. 1441-1451. PMLR, 2021.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv:1801.1000 2018.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs.
arXiv preprint arXiv: /805. 1973, 2018
Paul Erdōs, Alfréd Rényi, et On the evolution of random graphs. Publ. Math. Inst. Hung, Acad. Sci, 5(1):17-60, 1960.
Dhivya Eswaran, Reihaneh Rabbany, Artur W Dubrawski, and Christos Faloutsos. Social-affiliation networks: Patterns and the soar model. In Joint European conference on machine learning and knowledge discovery in databases, pp. 105-121. Springer, 2018.
Oleksandr Ferludin, Arn Eigenwillig, Martin Blais, Dustin Zelle, Jan Pfeifer, Alvaro Sanchez- Gonzalez, Sibon Li, Sami Abu-El-Haija, Peter Battaglia, Neslihan Bulut, et al. Tf-gnn: Graph neural networks in tensorflow. arXiv preprint arXiv:2207.03522. 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903:02290002228888 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pp. 2434-2444. PMIR, 2019.
Xiaojie Guo and Liang Zhao. systematic survey on deep generative models for graph generation. arXiv preprini arXiv:2007.06686. 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems, 31, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2332. PMLR, 2018.
10

---

Diederik P Kingma and Max Welling. arXiv:1312.6114, 2013.
Auto-encoding variational bayes.
arXiv preprint
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
arXiv preprint arXiv: 1609: 0290002907 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:661..07308. 2016b.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05999, 2018.
Jure Leskovec and Christos Faloutsos. Scalable modeling of real graphs using kronecker multipli- cation. In Proceedings of the 24th international conference on Machine learning, pp. 497-504, 2007.
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.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in Neural Information Processing Systems, 32, 2019.
Meng Liu. Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, et al. Dig: a turnkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240))1--9, 2021.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. In International Conference on Machine Learning, pp. 7192-72001 PMLR, 2021.
Jerome L Myers, Arnold D Well, and Robert F Lorch Jr. Research design and statistical analysis. Routledge, 2013.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. arXiv preprint arXiv:2203.00112 2022.
Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. Molecularrnn: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:1905. 2019.
Davide Proserpio, Sharon Goldberg, and Frank McSherry. workflow for iiteerenttialy-privvae graph synthesis. In Proceedings of the 2012 ACM workshop Workshop online social networks, pp. 13-18, 2012.
Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 425 438, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.
Collective classification in network data. Al magazine, 29(3):93-95 93, 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: flowd autoregressive model for molecular graph generation. arXiv preprint arXiv:2001.09382. 2020.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International conference on artificial neural networks, pp. 122-422. Springer, 2018
11

---

Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248, IEEE, 2013.
Mohammed Suhail, Abhay Mittal, Behjat Siddiquie, Chris Broaddus, Jayan Eledath, Gerard Medioni, and Leonid Sigal. Energy-based learning for scene graph generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13936- 13945, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 17Xiv:1710.109000 2017.
Daixin Wang. Jianbin Lin, Peng Cui, Quanhui Jía, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 598-5998 IEEE, 2019a.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.0133 2019b.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00 1810.8810022.0 2018.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ Salakhutdinov, and Quoc Le. Xlnet: Generalized autoregressive pretraining for language understanding, Advances in neural information processing systems, 32, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974-983, 2018.
Minji Yoon, Théophile Gervet, Baoxu Shi, Sufeng Niu, Qi He, and Jaewon Yang. Performance- adaptive sampling strategy towards fast and accurate graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2046-200600 2056, 2021.
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, pp. 5708-5717. PMLR, 2018.
Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint 1409: 2229,, 2014.
Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-gen: A temporal graph convolutional network for traffic prediction. IEEE Transactions Intelligent Transportation Systems, 21(9):3848-388 -3588, 2019.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems,
34, 2021.
12

---

A APPENDIX
A.1 PROOF OF PRIVACY CLAIMS
Claim (k-Anonymity for node attributes and edge distributions). In the generated computation graphs each node attribute and edge distribution appear at least k times, respectively.
Proof. In the quantization phase, we use the k-means clustering algorithm (Bradley et al. 2000 with a minimum cluster size k. Then each node id is replaced with the id of the cluster belongs to, reducing the original (n x n)) graph into (m X m) hypergraph where m = n2/k is the number of clusters. Then Computation Graph Transformer learns edge distributions among m hyper nodes (i.e., clusters) and generates a new (m x m) hypergraph. In the hypergraph, there are at most different node attributes and m different edge distributions. During the de- de-quantization phase, a (m x m) hypergraph is mapped back to (n n2) graph by letting k nodes in each cluster follow their cluster's 's node attributes/edge distributions as follows: & nodes in the same cluster will have the same feature vector that is the average feature vector of original nodes belonging the cluster. When 8 denotes the number of sampled neighbor nodes, each node samples clusters (with replacement) following its cluster's ss edge distributions among m clusters. When node samples cluster i, will be connected to one of nodes in the cluster randomly. At the end, each node will have s neighbor nodes randomly sampled from clusters the node samples with the cluster's edge distribution, respectively. Likewise, all k nodes belonging to the same cluster will sample neighbors following the same edge distributions. Thus each node attribute and edge distribution appear at least l times a generated graph.
Claim 2 ((e, DDDiiffereettal Privacy for node attributes). With probability at least 1-ô, our generative model A gives e-differential privacy for any graph G. any neighboring graph G_v without any node v E G, and any new computation graph Geg generated from our model as follows:
Pr[A(G)) = =Gel] Pr[A(g-.) Gog. Se
Proof. G-v denotes neighboring graphs to the original one G, but without a specific node v. During the quantization phase, we use (e, dddfffferettaa private k-means clustering algorithm on node features (Chang et al., 2021). Then clustering results are differentially private with regard to each node features. In the generated graphs, each node feature decided by the clustering results (i.e.. the average feature vector of nodes belonging to the same cluster). Then, by looking at the generated node features, one cannot tell whether any individual node feature was included in the original dataset or not.
Remark 1 ((e,8)-Differeen) Diffferenntl Privacy for edge distributions). In our model, individual nodes' edge distributions are learned and generated by the transformer. When we use (c, ddfffferrentt private stochastic gradient descent (DP-SGD) (Song et al. 2013) to train the transformer, the transformer becomes differentially private in the sense that by looking at the output (generated edge distributions), one cannot tell whether any individual node's 's edge distribution (input to the transformer) in the original dataset or not. If we have DP-SGD that can train transformers successfully with reasonably small and 8, we can guarantee (e, 8) diffferretia privacy for edge distribution of any graph generated by our generative model. However, as we show in Section 5.4] current DP-SGD is not stable yet for transformer training, leading to very coarse or impractical privacy guarantees.
included
Claim 3 (Scalability). When aim to generate L-layered computation graphs with neighbor sampling number s on a graph with n nodes, computational complexity of CGT training is (z and that of the cost-efficient version is (
Proof. During k-means, we randomly sample ng node features compute the cluster centers. Then we map each feature vector to the closest cluster center. By sampling nı nodes, we limit the k-mean computation cost to O(n)). The sequence flattened from each computation graph is O(1 + + ... + s²) and the number of sequences (computation graphs) is Onn). Then the training time of the transformer is proportional to O(s²4n). In total, the complexity is O(s"In - nī). As 2 >> nž. the final computation complexity becomes "n) In the cost cost-efficient version, the length of sequences (composed only of direct ancestor nodes) is reduced to L.. However, the
13

---

Table 5: GNN performance graphs generated baseline generative models. Except method, no existing graph generative models can generate of adjacency matrix, node feature matrix, and node label matrix that reproduce reasonable GNN performance.
Datose
Model
Original
GraphAF
GraphDF
GraphEBM
Graphitt
GVAF
Ours
GCN
0,860
1,000
0.200
0.760
SGC
0.850
1,000
0:200
0.750
GIN
0.850
0.0.0
0.0m
0.300
0.750
GAT
0.830
0.0m
0.0m
1,000
00.
0.380
0,750
GCN
0.730
1,000
0.190
0.590
GIN
0.710
0.0mm
0.001
1,000
0.0.m
0.190
0,570
GAT
0,710
0.0.m
0.0.8
1,000
0.0.m
0.390
0,570
0.993
Spearman
0.195
0.975
number of sequences increases to sn because each nodes has computation graph composed of - shortened sequences. Then the final computation complexity become O s mm).
A.2 SCALABILITY ISSUES ON BASELINE GENERATIVE MODELS
In Table 5 GraphAF (Shi et al. 2020), GraphDF (Luo et al. 2021), and Graphite (Grover et al. 2019) meet out-of-memor errors on both the Cora and Citeseer datasets. This is because they were originally designed for small-sid size molecule graphs. The remaining baselines, GVAE (Kipf & Welling 2016b) and GraphEBM (Suhail et al.) 2021 successfully generate graphs, however, fail to learn any meaningful node attribute/label distributions from the original graphs. Especially, GraphEBM generates graphs whose distribution collapses to generating the the same node feature/labels across all nodes, showing 100% accuracy for all GNN models, which is obviously not the most effective benchmark. Note that none of existing graph generative models is designed for GNN benchmarking simultaneous generation of adjacency, node feature, and node label matrices, rather they all focus only on the generation of adjacency matrices. This result shows the tricky aspects of graph generation and relations among graph structure, node attributes and labels, and large room for improvement in the graph generation field.
A.3 DETAILED GNN PERFORMANCE IN THE BENCHMARK EFFECTIVE EXPERIMENT IN
SECTION 5.3
Tables 6 and show GNN performance node classification tasks across the origi- nal/quantized/ weed///geeeeeeeee graphs. Quantized graphs are graphs after the quantization process: each feature vector replaced by the mean feature vector of cluster it belongs to, and adjacency matrices are a constant encoded by the duplicate encoding scheme. Quantized graphs are input to CGT, and generated graphs output from CGT presented in Figure Likewise, Table TO shows GNN performance on link prediction tasks across the gaggina/quannizzedgeeeettt graphs. As presented across all five Tables, our proposed generative model CGT successfully generates synthetic substi- tutes of large-scale real-works graphs that shows similar task performance as on the original graphs. Table IT shows benchmark effective across all GNN models we have used in the experiments on the original graphs without any variations.
A.4 DETAILED GNN PERFORMANCE IN THE PRIVACY EXPERIMENT IN SECTION
Table 12 shows detailed privacy-Gii GNNN performance trade-off on the Cora dataset. In K-anonymity, higher k (i.c.. more nodes in the same clusters, thus stronger privacy) hinders the generative model's ability to learn the exact distributions of the original graphs, and the GNN performance gaps between original and generated graphs increase, showing lower Pearson and Spearman coefficients. In DP kmeans, smaller (i.c., higher privacy cost) results in lower GNN performance, however, surprisingly, showing higher Pearson and Spearman coefficients. This is because DP kmeans could remove noises in graphs (while hiding outliers for privacy) and capture representative distributions on the original graph more easily. This results show our Claims and 2 privacy are holding real-world experiments. As we discussed in Section 4.2] DP SGD fails to train the transformer, showing low GNN performance even with astronomically low privacy cost 10%).
14

---

Table 6: GNN performance SCENARIO I: noisy edges on aggregation strategies.
mudel
Origiaal
Generated
prarsa
spearman
GCN
0.850
0,001
0.830
0.002
0.760
01005
SGC
0,850
0.311
0.520
0.004
0.750
01002
GIN
0,850
0.034
0.830
0.008
0,013
8.830
0.830
0.002
GCN
0.770
0.035
0.750
0.00
03600
0.014
Cura
SGC
0,770
0.008
0.740
0.003
0.680
0,015
0.934
0,930
0.750
0.730
0.003
0.680
0.740
0.012
GCN
0.720
0.011
0,660
0.008
0.610
0,015
SGC
0.730
0.005
0.600
0.004
0.600
01007
0.660
0.007
0.016
0,019
0,670
0.008
0,015
Datasel
#NE
model
Original
sld
Cluster
std
Generated
std
pearson
spearman
GCN
0.730
0.600
0.002
01024
8.730
0,670
0.002
0,029
GIN
0.710
0.009
0.670
0.004
0.570
0,028
GAT
0,710
0.001
0.670
0.004
0.570
0.029
GCN
0.370
0.50
Citeseer
GIN
0.570
0.540
0.020
0.560
0.570
0.017
0.003
00440
0.015
0.019
0.991
0.964
GAT
0,570
0.014
0.550
0.004
0.440
0.01
GCN
0.310
0.300
03001
01001
SGC
0.520
0.500
0.002
0-410
0.005
GIN
0.480
0.023
0.500
0.008
0.410
0.007
GAT
0,490
0,012
0.510
0.004
0,400
0.009
model
Original
std
pearson
spearman
GCN
0.850
0.001
0.820
0.001
0.780
0,007
SGC
0.860
0,000
0.810
0.001
0.780
0.003
0.002
GAT
0.860
0.002
0.830
0.003
0.780
0.005
GUN
0.760
0.004
0.760
0.004
M680
0.003
Pubmed
SGC
0.760
0.004
0.750
0.006
0.670
0.004
0.818
0.791
GAT
0.710
0.011
0.770
0.003
0.690
0.005
GUN
0.750
0.00
0.710
M640
0107
SGC
0.670
0.001
0,700
0.003
0.630
0.009
0.008
GAT
0,650
0,005
0.740
0,001
0.640
0.004
Datnset
#NE
model
Original
Cluster
std
Generated
std
pearson
spearman
0.840
SGC
0.860
0.005
0.810
0.009
0.830
0.007
GIN
0.850
0.002
0.810
0.015
0.800
0.013
GAT
0.840
0,008
0.840
0.011
0.830
GCN
0.760
Computer
Amazon
1
GIN
SGC
0.790
0.760
0.012
0.004
0.750
0.340
0.014
0.006
0.670
0.670
0,007
0.004
0.825
0.778
GAT
0,710
0,011
0.770
0.003
0.680
0.005
0:710
0.003
SGC
0.670
0.000
0.700
0.003
0.630
0.009
GIN
0.770
0.011
0.700
0.008
0.600
0.017
GAT
0,650
0,005
0.340
0.001
Datasct
model
Original
Cluster
<M
Generated
pearson
spearman
GCN
0.910
0.001
0,890
0.900
010K2
SGC
0.910
0,000
0.890
0.005
0,900
0,006
GAT
8,900
0.009
0.830
0.010
0,890
0,007
GCN
0,870
0.007
0,570
0.003
0.790
0.007
Amnzon
SGC
0.870
0.005
0.870
0.008
0.790
0.005
0.918
0.870
0.004
0,012
GAT
0,850
0.006
0,850
0,005
0.780
0,003
GCN
0.820
0.019
0.510
0.003
0.740
01002
SGC
0.830
0.810
0.022
0.012
0.830
0.024
GAT
0,800
0.010
8,820
0.029
0:720
0.01
Dataset
ANR
model
Original
Chuster
AM
Generated
stdl
pearson
0.830
0.800
0.003
SGC
0.830
0.003
0.880
0.002
0.830
0,008
GIN
0.870
0.001
0.570
0.004
0.820
0.013
GAT
0.880
0.850
0.004
0.006
0.870
0.005
MS CS
2
SGC
0.850
0.006
0.850
0.004
0,750
0,006
0.916
0.922
GIN
01850
0,010
0.840
0,005
0.720
01002
GAT
0.900
0.840
0.540
00004
SGC
0.840
0.002
0.540
0.002
0.700
0,005
GIN
0.820
0.009
0.700
0.010
0.670
0,011
0.004
0,005
Datasel
ANE
monel
Original
Chuster
sidl
Generated
sid
pearson
spearman
GCN
0.930
0.002
0.950
0.002
0.840
0.008
SGC
0.920
0.920
0.001
0.920
0.002
GAT
8.930
0.005
8.930
0.000
0.840
0,007
GCN
0.910
0.000
01910
03001
0.770
010034
MS Physic
0.661
8910
8,900
0.002
GAT
0.930
0.003
0,900
0.005
0.770
0,003
GCN
0.357
0.085
013000
TX0022
0.710
0.00%
0.002
0.005
8.500
0.880
0.005
0.007
GAT
8.930
0.002
0.800
0.001
0.720
0.004
15

---

Table 7: GNN performance SCENARIO 2: noisy edges on neighbor sampling.
model
Original
ald
Generaled
pearson
spearman
GruphSage
0,740
0.022
0.560
0,003
9.390
0.011
AS-GCN
0.130
0.14
0,110
0.013
0.130
0.013
FastGUN
0.390
0,005
0.006
PASS
0.790
0.200
0.008
0.029
GraphSage
0C360
0012
0.300
0.014
0.270
0004
Cura
AS-GCN
FastGUN
0.130
0.013
0.100
0.290
0,110
0.007
0,010
0.130
0.008
0.016
0.943
0.894
0.500
GraphSage
0.130
0.05
0.150
0.007
0.170
0.015
AS4GCN
0.80
0.057
0.130
0.008
0.130
0.008
FastGON
0.540
0.610
0,020
0.500
0.003
0.016
Dulaset
ANE
model
Original
sid
Cluster
sld
Generaled
sid
pearson
spearman
GraphSage
01660
0.110
0.014
0.007
AS-GCN
0.100
0.019
0.006
FastGCN
0.380
0.011
0.330
0.009
0.300
0.001
PASS
0.680
0.088
0.530
0.013
0.440
0.006
GraphSage
0.03
Citeseer
AS-GCN
FastGON
0.240
0.007
0.800
0,260
0.008
0.230
0.003
0.955
0.977
PASS
0.540
0.088
0.460
0,010
0,410
0.014
GraphSage
0240
0.088
0.250
0.012
AS-GCN
0012
0.100
0.004
FastGON
0210
0.004
02100
0.006
0.200
0.014
PASS
0,480
0.021
0.460
0.002
0,400
0.015
model
Original
Cluster
std
sed
pearson
spearman
GraphSage
0.780
0.055
0.680
0.002
0.630
0.004
AS-GCN
0,260
0.009
0.230
0.026
0,340
0.007
FastGUN
0.450
0.003
PASS
0.50
0.007
0.700
0.001
0.630
0.007
GraphSage
0.409
0102
0.467
0.013
0411
0104
Pabmed
AS-GCN
FasGGN
0.308
00022
0.419
0.053
0.287
0,051
0,8K5
PASS
0812
0.007
0.697
0.000
0.587
0.088
GraphSage
0110
6001
0.120
0.001
0.300
0181
AS-GCN
0,310
0.031
0.330
0.035
0.360
0.021
FastGON
0.660
0.600
0.002
0.012
PASS
0,790
0.001
0.690
0.006
0.430
0.005
Dataset
ANE
model
Original
std
Chuster
std
Generated
sed
pearson
spearman
GruphSage
AS-GCN
0.130
0.065
0.130
0.081
0.060
0.028
FastGNN
0.860
0.005
0.820
0.006
0.810
0.005
PASS
0.720
0014
0.590
0.001
0.540
0.009
GraphSage
Computer
Amaron
FastGCN
AS-GCN
0.250
0.190
0.005
0.633
0.710
0.000
0.001
0.002
0,540
0.004
0.012
0.958
0.916
PASS
0.600
0011
0.530
0.006
0.230
0.033
GraphSage
0.100
AS-GCN
0.080
0.015
0.060
0.018
0.100
0.037
FasGGNN
0.650
0.004
0.620
0.001
0,570
0.006
PASS
0,540
0.044
0.470
0.014
0.019
model
Original
Chaster
std
Generated
661
pearson
spearman
Graphšage
0.250
0108
0.670
0.017
01.30
0,025
AS-GCN
0,140
0.016
0.080
0.025
0.120
0.02
FastGCN
PASS
0.50
0011
0.780
0.006
0.540
0.049
GruphSage
0.400
0.012
0.370
0.007
0.360
0.09
Amazon
AS-GCN
FastGCN
0.120
0014
0.140
0.800
0.041
0.110
0.027
0.958
PASS
0.230
0.188
0.610
0.029
0.590
0.011
GraphSage
0.200
0109
0.200
0.016
0.200
0.14
AS-GCN
0.100
0.130
0.033
0.054
FastGNN
PASS
0.640
0.017
0.600
0.005
0,500
0.017
Dataset
ANF
model
Original
Cluster
sM
Generated
4Md
GraphSage
0.680
AS-GCN
0.050
0.027
0.070
0,033
9,070
0.016
FastGCN
0.920
0.001
0.100
0.001
0.820
0.001
PASS
0.015
GraphSage
0.50
0.080
MS CS
AS-GCN
FastGON
0.10
0.040
0.002
0.028
0910
0.050
01001
0.022
01830
0,050
0,022
0.036
0.974
0.956
PASS
0.044
GraphSage
AS-GCN
0.070
0.033
0.050
0.027
0,040
0.058
FastGUN
0.900
0.005
0.90
0.000
0,610
0.007
PASS
0.005
Datasel
model
Original
Cluster
sid
Generated
siel
pasrrson
spearman
GraphSage
0,500
0.005
0.790
0.003
0,500
0.009
AS-GCN
0.240
0.042
0.052
0.40
PASS
0.920
0.000
0.66
0.003
0,670
0.066
GraphSage
0.490
01001
0.500
01002
(1420
00005
Physic
A8-GCN
FastGNN
0.300
0.012
0.005
0.055
0.009
0.956
PASS
0.000
0.009
0.440
0.004
0,690
0.012
Graphiaage
0.300
01001
0.330
01003
07330
0102
A8-GCN
0,052
0.039
FastGCN
0.001
PASS
0,800
0.001
0.800
0.005
0.610
0.044
16

---

Table 8: GNN performance on SCENARIO 3: different sampling numbers neighbor sampling.
model
Original
Generaled
peanson
spearman
Graphiage
0,750
0.013
0,350
0.025
0.500
0.311
AS-GCN
8.120
0.001
0.120
0.011
0.110
0:005
FastGCN
0,450
0.008
0.390
0.006
0.003
8.800
6.007
0.600
0.088
0.003
Graphiaage
0.850
0.740
0008
01090
0X01
Cora
AS-GCN
CN
0,750
0.130
0.009
0.660
0.130
0.011
0.015
0.130
0:001
0,314
0.967
0,814
0.740
0.012
B:111
GraphSage
0.850
0.001
0.810
0.004
0.600
0,005
AS-GCN
0.130
0:022
0.140
0.029
0.150
D.346
FN
0,870
0.004
0.820
0.007
0.005
0.820
0.790
0.000
0,025
Dalaset
PSN
model
Original
std
Claster
std
Gemerated
std
pearson
spearmann
GraphiSage
0.080
0.014
0.500
0011
0,016
AS.GCN
8.110
8.013
0,090
0.00
0.100
0.005
FastGCN
0.570
0.011
0.550
0.085
0.330
0.015
PASS
6,200
0.005
0,550
0014
0.460
0,006
Graphiaage
0.700
Citeseer
AS-GCN
FasGGN
0.670
8.110
0.008
8.012
0,600
0.110
0010
0.08
0,580
0.001
0.004
0.973
0.904
PASS
8.710
0.005
0.610
0.077
0.560
0:007
Graphiaage
0.750
0300
0.650
0.09
AS-GCN
8.110
0.004
0.120
0.00
0.100
0.012
FasGCN
0.770
0.005
0.700
0.004
0,680
0.001
PASS
0,730
0,002
0,650
0.004
0,580
0,009
Datuset
model
Original
Claster
std
Gemerated
peurson
spearman
GraplaSage
0.780
B.005
0.680
0.005
0.600
0.0044
AS-GCN
0.250
0.002
0.260
0.009
0,260
0.011
FN
0.004
0.003
PASS
0,860
0.002
0.720
0.004
0.660
0,003
GraphSage
0.850
0.005
0.760
01055
0.710
0.001
Pubmed
FasGCN
AS-GCN
0,750
0.240
0.012
0.710
0,240
0.015
0,250
0,006
0.013
0.989
0,824
PASS
0.80
6.002
0.780
0.003
0.10
0.008
Graphiage
0.890
0.800
0101
01:40
D.002
AS-GCN
0,260
0.021
0.260
0.007
0,240
0.02
FasGUN
0.800
0.003
0.002
PASS
0.870
0.002
0,790
0.004
0.730
0,004
Datnset
#SN
moddl
Original
std
Cluster
std
Generated
std
pearson
spearman
GraphSage
0,550
0.088
AS-GCN
0.090
0.006
0,060
0.028
0.040
0,005
FasGCN
0.780
0.004
0,740
0.007
0.700
0,006
PASS
0.750
0.000
0.620
0.018
0.530
0.02
GraphSage
Computer
Amazon
AS-GCN
FastGCN
0.870
0.110
0.001
0.025
0.040
0,840
0.006
0014
0.800
0.120
0,011
0.06
0.975
0.890
PASS
0.810
0,015
0.760
0.023
0.640
0.009
GraphSage
0.770
0.008
0.720
0004
AS-GCN
0.120
0.085
0.100
0.057
0.030
0,007
FasGGN
0.850
0.003
0.850
0.000
0.790
0.01
PASS
0,830
0,012
0,730
0.011
0,022
Datnset
model
Original
Cluster
66d
Gonerated
std
pearson
spearman
Graphaaaee
0,740
6.016
0,660
0005
0.300
0,314
AS-GCN
0.110
0.037
0.090
0.030
0.090
0.04
FasGGNN
PASS
0.850
0.011
0,750
0.026
0.200
0.01
GraphSaage
0.800
0.006
0,610
0.007
0,740
0,007
Ammzon
FastGCN
AS-GCN
0,140
0.026
0.140
0.910
0.022
0.019
0.130
0.038
0.002
0.961
PASS
0.910
0.002
0,870
0.002
0,750
0,017
Graphaaage
0.10
0.010
0.890
0002
0.250
0,009
AS-GCN
0.860
0.850
0.021
0.031
FasGGCN
0.050
0.001
PASS
0.930
0.002
0.900
0.011
0.300
0:005
Datnset
88N
meddll
Original
Cluster
Generated
std
pearson
Graphiaae
0.740
0.008
0.650
0008
0.305
AS-
0.070
0,050
0,060
0.025
0.080
0,023
FastGCN
0.920
0.001
0.920
0.000
0.540
0,003
PASS
0.870
0.005
0.770
0.005
0.004
GraphSage
0.840
0.820
0.044
0.008
MS CS
AS-GCN
FastGNN
0:930
0.090
0.001
0.051
0.090
0.920
0.002
0.035
0310
0.070
0,018
0.011
0.986
0.901
PASS
0.900
0.014
0.870
0.005
0.013
GraphiNage
B.800
0.300
0000
0.50
AS-GCN
0.060
0.044
0.040
0.022
0.110
0.357
FastGCN
0.930
0.001
0.920
0.000
0310
0.01
PASS
0.890
0.001
0.014
Dataset
48N
model
Original
sid
Chaster
sid
Gemerated
sid
peorson
sperrmnn
GraphsSage
8880
6.001
0.780
0.004
0.590
0:003
AS-CCN
0.125
0.260
0.139
0.021
FastGCNN
0.940
0.001
0.002
PASS
0.920
0.005
0.850
0.004
0.688
0.004
GraphaSage
0.340
0.012
0.300
00001
0.220
Phy
AS-GUN
0.002
0.022
0.947
FastGNN
0.390
0.210
0.03%
0.014
PASS
0.950
0.005
0,940
0.002
08200
0.009
Graphiagge
0.9%0
0.010
01005
(1740
0.00
AS-GCN
0.930
0.900
0.001
0.001
Fast&NN
0.090
0.036
0.150
0.048
0.033
PASS
0.960
0.002
0.940
0.00%
0,30
0.020
17

---

Table 9: GNN performance SCENARIO 4: distribution shift.
model
Original
Clasler
sdd
Generatle
pearson
Graphiaae
0.830
0,010
0.520
0.003
0.760
0.024
iid
SGC
0.800
0.031
0.810
0.004
0.100
0.023
GAT
0.840
0.007
0.800
0.005
0,760
0.014
PPNP
0.840
0.007
0.800
0.008
0.066
GraphSage
0.250
0.007
0.750
0010
03630
0211
Cura
0,01
SGC
GAT
0.780
0.820
0,003
0.760
0.790
0.005
0.002
0.710
0:001
0:005
0.867
0.832
PPNP
0.750
0.760
0.004
0.730
0:001
GraphSage
0.730
0.010
0.730
0.005
0.660
0,012
0,3
SGC
GAT
0.750
0.003
0.003
0,700
0.720
0.019
0.002
0,700
0.016
0.01
0,770
0,008
0.730
0.006
0,017
Dalasel
model
Original
std
Cluster
std
Generated
std
pearsun
spearman
GraphiSage
0.000
0,0035
0.540
0.003
01021
8.710
0.600
0.001
0.590
0.017
GAT
0.680
0.016
0.650
0.005
0,580
0.011
PPNP
0.600
0.002
0.630
0.002
0.610
0:007
GraphiNage
0.500
0.50
0012
B101X
Citeseer
0.01
GAT
0.610
0.640
0.005
0.580
0.550
0.005
0.003
0.560
0.510
0.022
0.014
0.812
0.799
PPNP
0.610
0,010
0.550
0.010
0.540
0.02
GrapliSage
0.010
0.00%
0.500
0.002
0,22
SGC
0.680
0.003
0.560
0.002
0.530
0.012
GAT
0.650
0.007
0.560
0.005
0.510
0.003
PPNP
0,630
0,001
0,550
0.005
0,550
0,012
Datuset
model
Original
Claster
std
Gemerated
pearson
spearman
GraphiSage
0.840
0.002
0.810
0.002
0.720
0.009
SGC
0.860
0.001
0.820
0.000
0.730
0.005
GAT
0.810
0.002
0.014
PPNP
0.820
0.002
0,800
0.002
0.30
0.004
Graphiagg
0.810
0.007
0.750
0000
M660
0.01
Pubmed
0.01
SGC
0.800
0.0022
0,760
0.760
0.005
0.004
0,680
0:007
0,330
0.794
PPNP
0.770
0.034
0.760
0.006
0.600
0.008
GraphNage
0.270
0.007
0.7:50
0100
16620
BX014
SGC
0,770
0,003
0,750
0.000
0.660
0.003
0.750
0,700
0.002
0:008
PPNP
0,740
0.009
0,730
0,004
0.660
0,001
Datnset
model
Original
std
Cluster
std
Generated
std
pearson
spearman
GraphSage
0.850
0,800
0.012
SGC
0.870
0.004
0,790
0.004
0.800
0.003
GAT
0,840
0.003
0,700
0.008
0.800
0.012
PPNP
0.810
0,003
0,800
0.005
0.800
0.000
GraphSSgg
0.740
Computer
Amazon
0.01
SGC
GAT
0.770
0.800
0.028
0.003
0,750
0.750
0.005
0.006
0.750
0.700
0,006
0.003
0.906
0,860
PPNP
0,770
0,015
0.750
0.003
0.760
0.007
GraphiSage
0.750
0.710
0.013
0.01
0.3
GAT
SGC
0.360
0.760
0.003
0.004
0,720
0,710
0.010
0.005
0,700
0.710
0,006
0.006
PPNP
0,740
0,004
0.710
0.009
0.021
Datasct
medel
Original
Cluster
std
Generated
std
pearson
spearman
Graphiaage
0.800
0,001
0.890
00022
0.10
SGC
0.890
0,005
0.890
0.002
0.911
0.007
0.00K
PPNP
0.880
0.002
0,900
0.002
0.100
0,006
GraphiSage
0,590
0.014
0,850
0016
0.550
0,012
Amuson
SGC
0.650
0.008
0.860
0.006
0.840
0.015
0.771
0,860
0
0.850
0.002
0:007
PPNP
0.850
0.009
0,850
0,003
0,850
0.019
Graphiaage
0.830
0.011
0.860
2018
0,330
B,00)
SGC
0.850
0,013
0.820
0.002
0.017
0.850
0.027
0.006
PPNP
0,860
0.015
0.800
0.007
0.850
0.00
Datasct
medel
Original
Claster
4dd
Generated
pearson
Graphiaage
0.870
0.550
0.001
0350
iid
SGC
GAT
0.869
0,870
0.001
0.005
0.860
0.580
0.002
0.003
0.830
0.850
0,007
0,012
PENP
0.870
0.006
0.880
0.002
0:008
GraphSage
0,800
0.520
0012
0.90
0:006
MS CS
0.01
GAT
SGC
0.850
0.550
0.034
0.002
0.850
0.840
0,002
0.006
0300
0830
0,000
0.01
0.792
0.751
PPNP
0.800
0.001
0.003
Graphiaage
0.30
0.300
0000
0.3
SGC
GAT
0.850
0.870
0.008
0.0022
0.850
0.540
0.001
0.005
0.10
08400
0.006
0.003
PPNP
0.005
D:005
Datasel
model
Original
sid
Chadee
sdl
Generated
sid
pearson
spearman
GraphiSage
0.930
0.002
0.950
0.002
03400
D:00s
SGC
0.920
0.920
0.001
0:007
0.930
0.920
0.002
0.011
PPNP
8.930
0.005
0.950
0.000
0880
0:007
GraphiSage
0.830
0.033
B.850
0.004
0.760
BX019
MS Physic
SGC
0.820
0.005
0:15
0.925
GAT
0.870
0.840
0.11
0.780
0.009
PPNP
0.840
0.0077
0.830
0.006
0.740
0.009
GraphiSage
0.500
0.012
T.540
06600
B103
SGC
0.820
0.005
GAT
0.850
0.011
0.840
0.002
0.720
0.019
PPNP
0.810
0.012
0.830
0.004
0.700
0.009
18

---

Table 10: GNN performance link prediction.
predictur
model
Original
Generated
pearson
SONCAT
GCN
0.70
0010
0.770
0.009
0.680
0.012
Dot
SGC
0.710
0830
0.25
0.760
0,005
0.660
0.016
Cora
GCN
0.54
0003
01200
0.012
1310
0.01
0.781
0.741
MLP
SGC
0.530
0.16
0.590
0,042
0.510
0.006
0.500
0.50
Dutaset
predictor
moode
Original
sdd
Cluster
std
Generated
std
pearson
spearman
0.600
0.700
0.730
0.013
0.670
0.022
GIN
0330
0.088
0.720
0.003
0.650
0.01
Cieeseer
GAT
0750
0.055
0.780
0.012
0.680
0.021
0.808
MLP
GIN
0.570
00111
0.720
0.012
0.60
0.024
GAT
0.60
0.005
0.680
0.001
0.620
0.009
predictor
pearson
spear EILLER
GCN
0300
0018
0310
0.005
0.670
0.019
SGC
0.790
0.002
0.780
0.006
0.660
0.004
Pahmed
GUN
0.60
0860
0101
0.770
0.850
0.012
0.007
0.50
0.720
0011
0.008
0.725
0.421
MLP
SGC
0.770
0.066
0.770
0.006
0.610
0.008
0750
0.019
Dataset
prodictor
meddi
Original
sld
Cluster
std
Generated
std
pearson
spearmaa
0.700
0.006
Dot
GIN
SGC
0.500
0.760
0.133
0.055
0.580
0.770
0.004
0.000
0.730
0.830
0.005
0.025
Amazon Computer
GAT
0.500
0.340
0.652
MILP
GIN
0.000
0.800
0.003
0.800
0.850
0.000
0,010
0.810
0,730
0.01
GAT
0.600
0.005
0.910
0.005
0,800
0.005
Dattset
prodictur
model
Original
Choster
x1d
Generated
pearson
spaaarmam
GCN
0.90
0.11
0.920
0,003
0.500
0.016
SGC
0.10
0.144
0.840
0.015
0.750
0.011
Amazon
Photo
GCN
GAT
0.700
0.500
0.006
0.023
0.300
0.740
0.006
0.151
0,660
0.500
01001
0.134
0.887
0.443
SGC
03400
0.012
GAT
0910
0.007
0.930
0.004
01850
0.007
19

---

Table 11: Benchmark effectiveness GNN models without any graph variations
Original
Genernted
Pearson
Spearman
0.760
SGC
0.850
0.750
GIN
0.850
0.750
Cora
GruphSage
0.750
0.500
0.929
0,868
AS-GCN
0.120
0.110
FadGCN
0.450
0,380
PPNP
0.840
0.810
Datase
GNN model
Original
Generated
Pearson
Sprarman
GCN
0,730
0.590
GAT
0,710
0,570
Giteseer
GraphSage
0,680
0.440
0.948
0.743
A8-GON
FadGCN
0.370
0.330
PASS
0.700
0.460
PPNP
0,690
0.610
Original
Pearson
Spearman
SGC
0.860
0.750
GIN
0,830
0,770
GraphSage
AS-GCN
0.250
0.260
FasGCNN
0.480
0.440
PPNP
0.820
Dalasel
GNN model
Original
Generated
Peurson
Spearman
GCN
0.860
0,840
Computer
Amuzon
A8-GCN
GraphSage
GAT
0.670
0,800
0.450
0.850
0.952
0,920
FasGCN
0.780
PASS
0.750
0,550
PPNP
0.840
0,810
Original
Spearman
SGC
0.100
0.900
GIN
0.900
0,900
GruphSage
AS-GCN
0.110
0.090
FastGNN
0.830
0.750
PASS
Dalasel
GNN model
Original
Generaleed
Peurson
Spearman
GCN
0.880
0,830
SGC
0,880
0.830
GAT
0,880
0.830
MS CS
GraphSage
0,740
0,550
0.964
0.784
AS-GCN
FasGCN
PASS
0.870
0.690
PPNP
0.870
0,840
Spearman
SGC
0,920
0.840
GIN
0.930
0.820
GAT
GruphSage
AS-GCN
0,240
0.160
FastGUNN
0.950
0.840
PASS
0.920
PINP
A.5 ADDITIONAL. GRAPH STATISTICS
Figure 5 shows distributions of graph statistics on computation graphs sampled from the origi- mal/quantized/geeeraaee graphs. Quantized graphs are graphs after the quantization process: each feature vector is replaced by the mean feature vector cluster it belongs to, and adjacency matrices constant encoded by the duplicate encoding scheme. Quantized graphs input to CGT, and generated graphs are output from CGT as presented in Figure 2 While converting from original graphs to quantized graphs, CGT trades off some of the graph statistics information for k-anonymity
20

---

Table 12: Privacy-Performancc trade-off in graph generation the Cora dataset
INE
model
Original
No privacy
100
K-mmooyyiity
500
1000
10
0.01)
25
10
SGD
10
GCN
0,860
0,760
0.750
0.520
0.120
0.530
0.570
0.650
0.130
0.640
SGC
0.740
0.490
0.620
0.150
0,620
GIN
0.830
0.750
0.760
0.110
0.110
0.520
0.570
0.050
0.140
0.640
GAT
0,830
0.750
0,740
0.520
0.060
0.440
0.500
0.610
0,140
0,610
GCN
0,570
0.380
0.500
0.450
0.110
01580
SGC
0.360
0.400
0.570
GIN
0.730
0.670
0,590
0.390
0.140
0.390
0.410
0.470
0.140
0,580
GAT
0.600
0.660
0,560
1.80
0.100
0.350
0.300
0.400
0,120
0.530
SGC
0.500
0,280
0.110
0,300
0.410
0.450
0.140
0.410
GIN
0.600
0.590
0.430
0.300
0.160
0.220
0,430
0.460
0,150
0,400
GAT
0,600
0.570
0,470
0.290
0.060
0.250
0.370
0.450
0,140
0.380
Pearson
0.166
0.862
0.874
0.804
0.112
0.850
Spearman
1.000
0.935
0.947
03112
0.018
0.869
0.803
0,807
0.116
0.059
privacy benefits. In Figure 5 we can see distributions of graphs statistics have changed slightly from original graphs quantized graphs. Then CGT learns distributions of graph statisties on the quantized graphs and generates synthetic graphs. The variations given by CGT are presented as differences in distributions between quantized and generated graphs in Figure
A.6 ABLATION STUDY
To show the importance of each component in our Computation Graph Transformer, we run three ablation studies on our model. Table 13 shows CGT without label conditioning (conditioning on the label of the root node of the computation graph), positional embedding trick (giving the same positional embedding to nodes at the same layers on the computation graph), and masked attention trick (attended only on direct ancestor nodes on the computation graph), respectively. When we remove the positional embedding trick, provide the different positional embeddings to all nodes in computation graph, following the original transformer architecture. When we remove attention masks from model, the transformer attends all other nodes in the computation graphs to compute the context embeddings. As shown in Table T3] removing any component negatively impacts model performance. This shows not only the importance of label conditioning and designed positional embeddings and attention masks, but also tricky aspects of graph generation and relations among graph structure, node attributes and labels.
A.7 GRAPH NEURAL NETWORKS
We briefly review graph neural networks (GNNs) then describe how neighbor sampling operations can be applied on GNNs.
Notations. Let G (V,E) denote graph with n nodes v E V and edges (y), E Denote an adjacency matrix A (a(v,, vy)) e _axx and a feature matrix guud where æ; denotes the d-dimensional feature vector of node Ug.
GCN (Kipf & Welling 2016a). GCN models stack layers of first-order spectral filters followed by nonlinear activation functions learn node embeddings. When 1o()) denotes the hidden embeddings of node Ui in the (-th layer, the simple and general form of GCNs is as follows:
R (+D al
a(n, My M W()), O.....,,
where a(v, Uj) is set to 1 when there is an edge from vs to ui, otherwise 0. nu(i) Σド= a(v,, 12) is the degree of node uy; a(-) nonlinear function; W!!) (1) ( xa(+1) is the learnable transformation matrix in the I-th layer with (! denoting the hidden dimension at the 1-th layer. h( is set with the input node attribute 2;
GraphSage (Hamilton et al., 2017). GCNs require the full expansion of neighborhoods across layers, leading to high computation and memory costs. To circumvent this issue, GraphSage adds sampling operations GCNs regulate the size of neighhorhood. We first recast Equation T as
21

---

Cora
Citeseer
Pubmed
Amazon Computer
Amazon Photo
graphss
-30
#computation graphs
100
10P
#computation
13
200
400
300
300
300
420
122
X0
40
Original #izero vectors
Quantized #zero
Generated #zero vectors
#computation grappss
107
@computation graphts
#computation
10
10'
107
10m1
Original eduplicate
#duplicate
#duplicate
Figure 5: CGT preserves distributions of graph statistics in generated graphs for each dataset: converting from original graphs to quantized graphs, CGT loses some of graph statistics information for k- anonymity privacy benefit. The variations given by CGT are presented as differences in distributions between quantized and generated graphs
While
Table 13: Ablation study. Label, Position, and Attention denote ablation of label conditioning, positional embeddings, and masked attention proposed in Section 4.1. respectively. Pearson measure the correlation ranking of GNN models on original and generated graphs; score of denotes perfect correlation.
Datasel
Model
Original
Label
Position
Alfemtion
Ours
GCN
0,860
0,510
0.710
0.590
0.760
Cora
SGC
0,850
0.520
0.700
0.580
0,750
GAT
0.830
0.520
0.450
0.350
0.750
GCN
0,730
0.450
0.670
0.550
0,390
0.640
GAT
0,710
0.460
0.100
0.590
0.570
GCN
0,880
0.680
0970
0.570
0,760
GIN
0.830
0.670
0.990
0.570
0.770
GAT
0.860
0.690
0.900
0.120
0.780
Pearson
1.000
0.718
0.647
-0.097
0.988
Spearman
follows:
((-)) wes (Bi-oGiol 11), 1 0,
where we combine the transformation matrix (()) into the activation function agr (-) for conci- sion; p(jli) a(vr,05) defines the probability of sampling ey given v,. Then approximate the
n(x)
expectation by Monte-Carlo sampling as follows:
((++)) ow
Σ 1=0,..., jeP(l1
where is the number of sampled neighbors for each node. Now, regulate the size of neighborhood using s, in other words, the computational footprint for each minibatch.
A.7.1 GNN MODELS USED IN THE BENCHMARK EFFECTIVENESS EXPERIMENT IN SECTION 5.3
We choose four different GNN models with different aggregation strategies to examine the effect of noisy edges on the aggregation strategies: GCN (Kipf & Welling 2016a) with mean aggregator, GIN (Xu et al.] (018)) with aggregator, SGC (Wu et al. 2019) with linear aggregator, and GAT (Veličković et al. 2017) with attention aggregator. We choose four different GNN models with different neighbor sampling strategies examine the effect of noisy edges and number of
22

---

sampled neighbor numbers GNN performance: GraphSage (Hamilton et al. 2017) with random sampling, FastGCN (Chen et al. 2018) with heuristic layer-wise wise sampling, AS AS-GCN (Huang et al. 2018) with trainable layer-wise sampling, and PASS (Yoon et al., 202I) with trainable node-wise sampling. Finally, we choose four different GNN models to check their robustness to distribution shifts in training/test time, as the authors of the original paper (Zhu et al.] (02T) chose for their
baselines: GCN (Kipf & Welling 2016a), SGC (Wu et al. 2011)) GAT (Veličković et al.) 2017). and
PPNP Klicpera et al.) 2018).
We implement GCN, SGC, GIN, and GAT from scratch for the SCENARIO 1: noisy edges on aggregation strategies. For SCENARIOS and 3: noisy edges and different sampling numbers on neighbor sampling, we use open source implementations of each GNN model, ASGCN FastGCN and PASS 3] uploaded by the original authors. Finally, for SCENARIO 4: distribution shift, we use GCN, SGC, GAT, and PPNP implemented by (Zhu et al. 2021) using DGL library 3
A.8 ARCHITECTURE OF COMPUTATION GRAPH TRANSFORMER
Given a sequence = [s,, , the M M-layered transformer maximizes the likelihood under the forward auto-regressive factorization as follow:
T
T
erp(y (1) ($1n-1) e((s))
max max (og
logps (st (st(s<r))
Σ log Eg expla 1 (SL:t1)
where node embedding e(st) maps discrete input id to randomly initialized trainable vector, and query embedding ( ($1:--1 encodes information until (t 1)-th token in the sequence. Query embedding qi
(i) is computed with context embeddings h (1-1) of previous - tokens and query
(1-1), context embedding st 1) from the previous layer. Context embedding hi?)) is computed from h
embeddings of previous
tokens and f-th token from the previous layer. Note that, while the query embeddings have access only to the previous context embeddings h h the context embeddings
(i) The context embedding h, is initially encoded by node embeddings c(st) attend to all tokens
and position embedding Pi(+) that encodes the location of each token in the sequence. The query embedding is initialized with a trainable vector and label embeddings Ys, as shown in Figure B This two streams (query and context) of self-attention layers are stacked M time and predict the next tokens auto-regressively.
A.9 DIFFERENTIALLY PRIVATE K-MEANS AND SGD ALGORIHMM
Given set of data points, k-means clustering identifies k points, called cluster centers, by minimize the sum of distances of the data points from their closest cluster center. However, releasing the set of cluster centers could potentially leak information about particular users. For instance, if particular data point is significantly far from the rest of the points, so the k-means clustering algorithm returns this single point as cluster center. Then sensitive information about this single point could be revealed. To address this, DP k-means clustering algorithm (Chang al. 202 is designed within the framework of differential privacy. To generate the private core-set, DP k-means partitions the points into buckets of similar points then replaces each bucket by a single weighted point, while adding noise to both the counts and averages of points within a bucket.
Training model is done through access to its parameter gradients, i.c., the gradients of the loss with respect to each parameter of the model. If this access preserves differential privacy of the training data, so does the resulting model, per the post-processing property of differential privacy. To achieve this goal, DP stochastic gradient descent (DP-SGD) (Song et al." 2013) modifies the minibatch stochastic optimization process make it differentially private.
hittarr//gihhubbccm//maamr////
httess//tthabbccc////nnch//////s Robust-GNNG
23

---

Table 14: Dataset statistics.
Dalasel
Nodes
Edges
Peatures
Labels
2,435
Pubused
19.717
44,324
500
Amazon Computer
13,581
245,778
767
10
Amazon Photo
7,487
119,043
745
18,335
MS Physic
34,491
267.62
3.415
We use the open source implementation of DP k-means provided by Google's differential privacy libraries We extend implementations of DP SGD provided by public differential library Opacus
10 EXPERIMENTAL SETTINGS
All experiments were conducted on the same p3.2xlarge Amazon EC2 instance. We run each experiment three times and report the mean and standard deviation.
We evaluate on seven public datasets three citation networks (Cora, Citeseer, and Pubmed) (Sen et al. 2208)), two co- co-purchase graphs (Amazon Computer and Amazon Photo) (Shchur et al. 2018). and two co-authorship graph (MS CS and MS Physic) (Shchur al. 2018). We use all nodes when training CGT. For GNN training, we split 50%/10%/40% of each dataset into the train- ing/validation/test sets, respectively. We report their statistics in Table [4]
For the molecule graph generative models, GraphAF, GraphDF, and GraphEBM, extend imple- mentations in a public domain adaptation library DIG (Liu et al. (202)). We extend implementations of GVAE P
Graphite 8 from codes uploaded by the original authors.
For our Computation Graph Transformer model, we use 3-layered transformers for Cora, Citeseer, Pubmed, and Amazon Computer, 4-layered transformers for Amazon Photo and MS CS, and 5- layered transformers for MS Physic, considering each graph size. For all experiments to examine the benchmark effectiveness of our model in Section [.3] sample 5 neighbors per node. For graph statistics shown Section 5.5, we sample 20 neighbors per node. Our code is publicly
available (anonymized).
accounting
d1
24


Reviews:
[{"review_id": "tB8bMOsT6JR", "reviewer": "Reviewer_qqDr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper re-define the problem of graph generation with concerns from three aspects: scalability, benchmarking, and privacy-preservation. In response, the authors proposes an interesting minibatch-based problem formulation and accordingly apply transformer to encode the computation graphs. Many tailored details about modeling are discussed and addressed. The proposed method is extensively evaluated from those three aspects, showing superiority over existing methods.", "summary_of_the_review": "I have went through the whole main paper and found it is interesting and technically sound. According to my experience in federated graph learning, I think the problem re-defined and somewhat resolved in this paper is important. Thus, I tend to accept this paper.", "strength_and_weaknesses": "Strengths:\n1. The paper is well-written.\n2. The re-defined problem with the three aspects of concerns appropriately reflect the latest demands in practice, which must be a contribution to the community. I am willing to seeing more and more works solving this problem.\n3. The duplicate scheme is simple yet effective, in my opinion. It transforms the problem in a way that drastically reduces the search space.\n4. The empirical studies are comprehensive.\n\nWeaknesses:\n1. How to sample node features from the cluster id and how to sample computation graphs from the learned transformer should be elaborated.\n2. The privacy concern is addressed from only the attributive perspective. As for the structural perspective, there is a lack of discussion. In my opinion, the discretization of node features also helps this method reduce the risk of composing the original graph from a collection of sampled computation graphs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "m-sQEfQfYJ2", "reviewer": "Reviewer_Dpqx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a scalable and privacy-enhanced graph generative model to learn and reproduce the distribution of real-world graphs with node attributes/labels. The proposed model satisfies benchmark effectiveness, scalability and privacy guarantee.\n", "summary_of_the_review": "This work in general provides clear problem formulation and interesting ideas to transform the problem of graph generation into sequence generation. The design and evaluation would be more convincing if the following questions can be answered.\n\n**Method**\n\n1. What could be the advantages/disadvantages for using the computation graph, compared with a random walk based method to sample the graph? The reason for asking this question is that the cost-efficient version of CGT can be directly achieved by random walks. Meanwhile, I am curious about how sensitive this proposed method is to the sample size of neighbors $s$? \n\n2. The cluster assignments across different computation graphs or minibatches might be different as the quantization is not conducted over all the nodes. For example, two nodes with similar features might be assigned with different cluster ids (thus are different tokens) as they are quantized separately in two batches. How to handle such a misalignment of cluster assignment?\n\n3. The method section cuts off after introducing CGT. However, it is also important to explain how the de-quantization is conducted to finally generate computation graphs.\n\n4. With label conditioning, can this method handle heterophilic graphs? \n\n**Experiment**\n\n5. Is the size of original and generated graphs comparable in the evaluations?\n\n6. The goal of generated graphs is to train a useful GNN model that can be applied to real-world data. Therefore a more important setting should be tested: compare the performance of two GNNs on the same real-world test data, and these two GNNs are trained on the original or generated graphs respectively.\n\n7. To verify the effectiveness of the generated graphs, it would be better if the proposed method is compared with some existing graph generative models on small datasets, such as molecular datasets.\n", "strength_and_weaknesses": "**Strength** \n- The proposed graph generative model fills the gap in existing works to handle privacy and node attributes/labels on large graphs\n- The paper proposes a clear and novel formulation for such a graph generation problem\n- Designs (e.g. computation graph minibatches, duplicate encoding scheme, quantization) are well motivated and technically sound\n\n**Weaknesses**\n- Important details (e.g. how to align cluster assignments across batches, how to do de-quantization etc) are not introduced\n- More experiments are needed to further verify the usefulness of generated graphs\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lCEUNPCsFMU", "reviewer": "Reviewer_jEpM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to tackle the privacy issue when collecting datasets from online databases by introducing a novel graph generative model, which is called Computation Graph Transformer (CGT), that can learn the distribution of real-world graphs in a privacy-enhanced manner. The proposed algorithm can generate synthetic\nsubstitutes of large-scale real-world graphs, which can be used to benchmark GNN models. First, CGT operates on computational graphs of mini-batches rather than the whole graph, avoiding scalability issues. Second, a novel duplicate encoding learns a single, dense feature matrix instead of learning the adjacencies and features simultaneously\n", "summary_of_the_review": "Overall I recommend the rejection of the current manuscript. I agree with the novelty and the importance of the problem considered: to enhance the privacy of the real-world, large-scale graphs collected from online databases. But due to the current insufficient theoretical analysis and experiments that justify CGT solves the benchmark effectiveness and scalability goals as the paper claimed, I cannot recommend acceptance now. Either some theoretical guarantees on how the benchmark effectiveness is achieved, or a much larger GNN architecture pool to measure the rank correlation is needed.", "strength_and_weaknesses": "#### Strengths\n1. To the best of my knowledge, I think the computation graph transformation method proposed by this paper is a novel approach to enhance privacy (more specifically, to achieve the k-anonymity privacy guarantee) on the fly and efficiently.\n2. The authors considered using Pearson & Spearman ranking correlations to measure how the performance order of GNNs is preserved on the synthetic graph.\n\n#### Weaknesses\n1. One major issue is that the \"benchmark effectiveness,\" which concerns how the synthetic graph preserves the performance ranking of GNNs, is definitely the most important metric of the proposed methodology. However, how the proposed CGT method achieves this goal is still hard to understand given the following reasons (please correct me if I am wrong): (1) The descriptions in sections 3 and 4 are mostly focused on the design and implementation of the CGT algorithm. However, it is hard to find the intuition or theoretical guarantee that ensures the benchmark effectiveness of CGT. (2) Tables 1 and 2 measure the Spearman rank correlations on multiple datasets; however, the number of GNN architectures considered (which are only GCN, GIN, SGC, GAT according to appendix A.7.1) is too small to draw a meaningful and conclusive result. Many more architectures are needed to add to the pool. Another issue is that the authors should also consider simpler and more meaningful graph generative model baselines in Table 5 in appendix A.2 (I also suggest moving Table 5 to the main paper). Otherwise, it is hard to understand the correlation metrics of CGT.\n2. In terms of the scalability of the proposed CGT method, (1) the theoretical complexities claimed in Claim 3 still suffer from the exponential dependence on the number of layers, similar to a standard neighbor sampling scheme, and this hinders the application to deeper GNNs. (2) I only see a few experimental results on the scalability comparison (e.g., Table 5 in appendix A.2 only shows some methods out of memory). Some more measures like the computational time and memory usage of CGT and some simpler yet meaningful graph generative model baselines are encouraged to be added.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UVHeumvekR", "reviewer": "Reviewer_q2ks", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a computational graph-based method for graph generation, in which computational graphs for nodes, used in graph neural networks to compute node-level outputs, are the generation objective, rather than the graphs themselves. To this end, the paper first balances the node-level computational graphs, i.e., the k-ary trees (where k is the number of sampled node neighbors) defining the computation, by adding redundant neighbor nodes and creating duplicate nodes to break cycles. This scheme is called the duplicate encoding scheme in the paper. As the trees of this scheme are balanced and k is typically fixed, the size of these trees is therefore a constant. As such, the paper then proposes a modification of the XLNet transformer, which they term computational graph transformer (CGT), to apply to these sequences. In CGT, query and context attention masks are dictated by the computational graph structure for improved inductive bias, and positional encodings are introduced at every layer to distinguish the different layers. For privacy enhancement, a clustering scheme (such as k-means) is used to anonymize and group feature vector into a discrete set of features (the cluster centroids), and shown to yield improved privacy when used with CGT. Hence, the approach can be summarized as 1) A computation graph extraction, 2) duplicate encoding, 3) feature clustering and replacement, and 4) application of CGT to compute outputs. For generation, the reverse applies: CGT is used to infer a combination of discrete feature vectors, which can then be mapped back to a duplicate encoding computational graph.\n\nEmpirically, this method is verified on a variety of benchmarks through an experimental setup based on performance similarity. In particular, the protocol looks to generate analogous computational graphs to the original inputs using the approach, and seeks to compare the performance of a variety of models on the original and generated computational graphs. The generation is then perceived to be high-quality if the model performances are similar across both original and generated graphs. In the paper, the authors report that this is the case. Finally, the authors consider manipulations to the input graph, and apply the same protocol to these situations, showing correlations between performance changes as well as similar performance values.", "summary_of_the_review": "Overall, I understand the paper's motivation to flatten of the graph structure into a balanced tree, so as to produce a fixed-size structure and use more established and scalable generation procedures. This flattening makes the paper's approach very efficient, but in turn loses significant structural information, and practically discards several key complexities that are inherent to graph-based tasks. In fact, it is easy to come up with scenarios where this generation procedure will ambiguate clearly distinct use cases. Moreover, I am not convinced by the empirical evaluation protocol and results. Therefore, I lean towards rejecting the paper as it stands. However, I am happy to discuss my concerns with the authors, and am open to change my verdict should they offer compelling arguments addressing my concerns.", "strength_and_weaknesses": "# Strengths: \n- The approach is scalable and thus can apply to large graph structures, which is not common in the graph generation domain.\n- The use of label information during generation is a good inductive bias and a useful property.\n- The model is simple to understand.\n# Weaknesses: \n-  I have major concerns about the soundness of reducing graph structures to fixed sequences. In particular, the duplicate encoding scheme is problematic, as it can lead to otherwise structurally different nodes obtaining identical computational graphs! For example, the computation graph of a node A in a triangle A -> B -> C  and is identical to that of the latter A in a line graph with identical A-featured nodes at extremes, i.e., A -> B - > C -> A (both A nodes distinct). As a result, the model is losing information in the generation process by default, and this stands regardless of the dimensionality of features used. The authors argue that the features can encode the lost structure, and discuss this near the end of the paper. However, this is not plausible in the general case, i.e., some information can be saved, but not all. Therefore, this generation procedure is effectively flattening the graph structure, which itself means that it cannot respect key structural properties of the input graphs and instead can only recover feature information. As a result, I have strong concerns that this approach can yield structure-preserving generated samples. \n- The empirical protocol, though intuitive, does not fully prove the quality of the graph generation: Given the large space of potential target functions over computation graphs, it is possible to learn different tasks of similar difficulty, particularly as the generation itself 1) could make arbitrarily difficult features with enough randomness, and 2) the encoded structure of the computation graph loses information relative to the original graph, making it harder to learn the original function in some cases. Therefore, I recommend also using a similar experimental protocol to the literature, based on visualizing graphs and comparing structural properties. I understand that the baselines are small in this case, but this is essential to appraise the quality of the generated computational graphs (both label-agnostic and per label).\n- The empirical results are not convincing: The gaps between synthetic and generated dataset numbers are quite substantial in Table 1. Moreover, the correlation experiment results are not surprising: It is natural that adding noise reduces performance irrespective of model choices, so this correlation in my opinion is to be expected. I feel the same about sampling neighborhood and its effect on performance. \n- The discussion on privacy in this work is very limited and makes no meaningful contribution: It simply uses a clustering algorithm prior to applying the model. Therefore, I find that the privacy contribution in this paper is significantly oversold, not least in the title. I suggest that this be downplayed when revising the paper.\n- Minor: Citations should be surrounded by brackets throughout the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject