Generated Graph Detection
Authors: Yihan Ma
Zhikun Zhang
Ning Yu
Xinlei He
Michael Backes
Yun Shen
Yang Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Generated Graph
Graph Neural Network
Contrastive Learning
Metric Learning

Abstract: Graph generative models become increasingly effective for data distribution approximation and data augmentation. Although still in sandboxes, they have aroused public concerns about their malicious misuses or misinformation broadcasts, just as what Deepfake visual and auditory media has been delivering to society. It is never too early to regulate the prevalence of generated graphs. As a preventive response, we pioneer to formulate the generated graph detection problem to distinguish generated graphs from real ones. We propose the first framework to systematically investigate a set of sophisticated models and their performance in four classification scenarios. Each scenario switches between seen and unseen datasets/generators during testing to get closer to real world settings and progressively challenge the classifiers. Extensive experiments evidence that all the models are qualified for generated graph detection, with specific models having advantages in specific scenarios. Resulting from the validated generality and oblivion of the classifiers to unseen datasets/generators, we draw a safe conclusion that our solution can sustain for a decent while to curb generated graph misuses.

Under review as a conference paper at ICLR 2023
GENERATED GRAPH DETECTION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph generative models become increasingly effective for data distribution ap- proximation and data augmentation. Although still in sandboxes, they have aroused public concerns about their malicious misuses or misinformation broadcasts, just as what Deepfake visual and auditory media has been delivering to society. It is never too early to regulate the prevalence of generated graphs. As a preventive response, we pioneer to formulate the generated graph detection problem to distinguish gen- erated graphs from real ones. We propose the first framework to systematically investigate a set of sophisticated models and their performance in four classification scenarios. Each scenario switches between seen and unseen during testing to get closer to real world settings and progressively challenge the classifiers. Extensive experiments evidence that all the models are qualified for generated graph detection, with specific models having advantages in specific scenarios. Resulting from the validated generality and oblivion of the classifiers to unseen datasets/generatoos. we draw safe conclusion that our solution can sustain for decent while to curb generated graph misuses.
INTRODUCTION
Graph generative models aim learn the distributions of real graphs and generate synthetic ones Xie
ctt al. 2022); Liu et al. () Wu et al. (2021b). Generated graphs have found applications numerous domains, such as social networks Qiu et al. (018)), e-commerce Li al. (2020).
chemoinformatics Kearnes et al. (2016). etc. In particular, with the development of deep learning,
graph generative models have witnessed significant advancement the past years SStoyanovich
et al. 2020); Liao et al. (2019); Kipf & Welling (2016); You et al. (2018a).
However, a coin has two sides, there concern that the synthetic graphs can be misused. For example, molecular graphs are used to design new drugs|Simonore Simonovsky & Komodakis (2018): You ct al. (0018)). The generated graphs can be misused in this process and it is important for the pharmaceutical factory to vet the authenticity of the molecular graphs. Also, synthetic graphs make deep graph learning models more vulnerable against well-designed attacks. Existing graph-level backdoor attacks Xi et al. (202T) and membership inference attacks Wu et al. (2021a) require the attackers to train their local models using the same or similar distribution data as those for the target models. Adversarial graph generation enables attackers generate graphs that are close to the real graphs. It facilitates the attackers to build better attack models locally hence keeping those attacks more stealthy (since the attackers can minimize the interaction with the target models). This advantage also applies to the latest graph attacks such as the property inference attack Zhang et al. (2022) and GNN model stealing attack [Shen al. (2022).
As result, it is essential to regulate the prevalence of generated graphs. In this paper, we propose to proactively target the generated graph detection problem, i.e., to study whether generated graphs can be differentiated from real graphs with machine learning classifiers.
To detect generated graphs, we train graph neural network (GNN)-based classifiers and show their effectiveness in encoding and classifying graphs/Zhang et al. (2020) Kipf & Welling (2017) (Hamilton ct al. (0077) Figure 2 illustrates the general pipeline of the generated graph detection. To evaluate their accuracy and generalizability, we test graphs from varying datasets and/or varying generators that are progressively extended towards the unseen during training. The seen concept in dataset or generator means that the graphs used in the training and testing stage are from the same dataset or generated by the same generator, respectively. That is to say, they share the same or similar distribution. And the unseen concept represents the opposite.

---

Under review as a conference paper at ICLR 2023
To sophisticate solution space, study three representative classification models. The first model is a direct application of GNN-based end-to-end classifiers Kipf & Welling (2017); Hamilton
ct al.
2017); Chen et al. (2018); x al. (2019b). The second model shares the spirit of contrastive
learning for images Chen et al. 2 Wu et al. (018); Hénaff (2020) and graphs /hhu et al. (2021a);
You et al. 2020); Hassani & Ahmadi 2020); Zhu al. (202Tb), which, as of the cutting-edge
self-supervised representation learning models, learns similar representations for the same data under different augmentations. We adapt graph contrastive learning learn similar representations of
graphs from the same source under different augmentations. The third model is based on deep metric learning Xing et al.] (2002); Schroff et al.] (2015); Song et al. (2016), which learns close/distant representations for the data from the same/different classes. We adopt metric learning to learn close/distant representations for graphs from the same/different sources.
We systematically conduct experiments under different settings for all the classification models to demonstrate the effectiveness of our framework. Moreover, we conduct the dataset-oblivious study which mixes various datasets in order to evaluate the influence along the dataset dimension. The evidenced dataset-oblivious property makes them independent specific dataset and practical in real-world situations.
2 PRELIMINARIES
Notations. We define an undirected and unweighted homogeneous graph as G (V, A), where {v1. .... Un represents the set of nodes, & S {(v, u) v,u V} is the set of edges and A E 10,1] denotes G's adjacency matrix. We denote the embedding of node E V as h, and the embedding of the whole graph G as hg-
Graph Neural Networks. Graph neural networks (GNNs) have shown great effectiveness in fusing information from both the graph topology and node features Zhang et al. (2020); Hamilton et al. (017)); Kipf & Welling (2017). In recent years, they become the start-of-the-art technique serving as essential building blocks in graph generators and graph classification algorithms. A GNN normally takes the graph structure as the input for message passing, during which the neighborhood information of each node u is aggregated to get a more comprchensive representation h, The detailed information of GNN is described in Appendix A.
Graph Generators. Graph generators aim to produce graph-structure structured data of observed graphs regardless of the domains, which is fundamental in graph generative models. The study of graph generators dated back at least to the work by Erdös-Rényi Erdös & Rényi (1959) in the 1960s. These traditional graph generators focus on various random models Erdös & Rényi (959)); Albert & Barabási (2002). which typically use simple stochastic generation methods such random or preferential attachment mechanism. However, the traditional models require prior knowledge to obtain/tune the parameters and tic them specifically to certain properties (c.g., probability of connecting to other nodes, etc.), hence their limited capacity of handling the complex dependencies of properties. Recently, graph generators using GNN the foundation have attracted huge attention Liao et al. 2 You et al. 8b); Grover et al. (019); Simonovsky & Komodakis (2018). The GNN- based graph generators can be further grouped into two categories: autoencoder-based generators generators. Autoencoder-based generator Kipt' & Welling (2016); Grover ctt al. (2019); Mehta et al. (2019); Simonovsky & Komodakis (2018) type of neural network which is used to learn the representations of unlabeled data and reconstruct the input graphs based on the representations. Autoregressive-basse sophisticated models to better capture the properties of observed graphs. By generating graphs sequentially, the models can leverage the complex dependencies between generated graphs. In this paper, we selectively focus eight graph generators that span the space of commonly used architectures, including ER Erdös & Rényi (1959), BA Albert & Barabásil (2002), GRAN Liao et al. (2019), VGAE Kipf & Welling (2016). Graphite Grover al. (2019), GraphRNN You et al. (2018b),
and autoregressive--assee
generator Liar et al. 2019); You al. (2018h) uses
SBMGNN et al. (2019), and CraphVAEESimonovsky & Komodakis (2088) (see more detailed information about graph generators in Appendix A.2)
2

---

[0m+1 1, ................................ @m+k) and a collection of generated graphs by seen and unseen generators GG = (GG,.... GG )- Here each GG; is set of graphs generated by a graph generator de. To be specific, let D ((01, V1), (22,82), .............................. (Fz, y2 )) where e; E RGGUG the total number of samples. A generated graph detector f(-) later trained on D. Once trained, classifies each testing graph as real or generated. However, it is normal to see the arrival of graphs from unknown generators that have never been seen in training, and the graphs may not bear with similar properties as of the training data in the real world. The existing solutions usually leverage model retraining to cope with the problem. Yet, is impractical to retrain a model from scratch every Under review as a conference paper at ICLR 2023
3 GENERATED GRAPH DETECTION
3.1 PROBLEM STATEMENT
The generated graph detection problem studied in this paper can be formulated as follows. Suppose we have a set of real graphs RG = {rg...... rgg/. h. m seen graph generators L Peeen = {Øi..... &m J
k unseen graph generators L Punseen
yj represents the label of each graph (i.e., real or generated) and = = -i=1
m [GG,
time new graph generator is added or unseen data is encountered. Ideally, f()) should be built in way that il can be generalized to previously unseen data/generator in the real world.
3.2 A GENERAL FRAMEWORK FOR GENERATED GRAPH DETECTION AND ANALYSIS
In this paper, we propose a general framework to detect generated graphs. Specifically, this framework consists of four scenarios depending on whether the dataset or graph generator has been used to train the model. These scenarios comprehensively cover from the simplest close world scenario to the most challenging full open world detection scenario. We discuss how we choose different ML models to implement this framework in /ecction 3.3
Closed World. In this scenario, the training and testing graphs sampled from seen datasets and generated by seen generators. The goal is to predict whether a graph is real or generated by seen generators. Under this setting, to train the generated graph detector f()). we sample real graphs from RG as positive samples and sample graphs generated by seen generators Dseen as negative samples. The graphs used to test f()) share the same distribution with the training set, i.e., they consist of real graphs sampled from RG and generated graphs generated by seen generators seenn
Open Generator. In this scenario, the negative samples of the testing graphs are generated by unseen generators but are in the same or similar distribution of training data (i.e., seen data). The training data of f-) does not contain any graphs generated by these unseen generators. Since only the graph generators used in the testing dataset are not seen at the time of training, we thus name it "Open Generator" scenario. Under this setting, the detector f(-) is trained with the graphs sampled from RG (positive samples) and graphs generated by seen generators 4 &seen (negative samples). The positive samples used to test f-)) are also from RG while the negative samples are generated by unseen generators 4 Punseen. The goal is to predict whether graph is real or generated by unseen generators.
Open Set. In this scenario, the testing graphs are from seen generators that are trained on an unseen dataset. Concretely, the graph generators that the system sees in training are what it will see in testing (i.e., seen generators). However, the testing graphs are of the different distribution of training data (i.e., unseen data). For instance, f(-) was trained using both real and generated graphs from chemical graphs, yet, the testing graphs (either real or generated) are social network graphs that are inherently different. As such, we name this scenario "Open Set" scenario. Similar to the "Open Generator" scenario, the detector f(-) is trained with the graphs sampled from RG (as positive samples) and the graphs generated by seen generators seeen (as negative samples). Unlike previous experiment, the graphs used to test (-) are from different datasets. The testing graphs of f()) consist of real graphs sampled from other datasets and graphs generated by seen generators T seee based on other datasets. The goal is to predict whether graph from unseen dataset is real generated.
Open World. In this scenario, the testing graphs are from unseen generators that are trained on an unseen dataset. This setting is the most challenging yet common in the real world. It is normal to see the arrival of graphs from unknown generators that have never been seen at the training time, and the graphs may not bear with similar properties of the training data. To be specific, certain generators that the system sees at the testing time are not included in its training stage (i.e., unseen generators), and the testing graphs are of the different distribution of training data (i.e., unseen data).
3

---

Under review as a conference paper at ICLR 2023
Similar to "Open Generator" and "Open Set" scenarios, the generated graph detector f(-) is trained with the graphs sampled from RG (as positive samples) and the graphs generated by seen generators Pseen (as negative samples). The testing graphs consist of real graphs sampled from other datasets and graphs generated by unseen generators unnseen based on other datasets. The goal is to predict whether graph from unseen dataset is real generated by unseen generators.
3.3 DETECTION METHODOLOGIES
As discussed in Section 3.2
need an ML model f(-) to cope with the four generated graph detection scenarios. In this section, we introduce three ML models - end-to-end classifier Kipp &
Welling 2017); Hamilton et al. (2117); Chen al. (2018); Xu et al. (20T9h), contrastive learning-
based model /Zhu et al. (2021a); aa;; You et al. (2020g Hassani & Ahmadi (2020); ; Zhu et al. (2021b),
and metrie carning-based based model Xing al. (2002 Schhroff |Schoof et al. (2015); Song al. (2016) to implement the aforementioned detection framework. All the models can work as the f()) to do the final detection in all scenarios. For each scenario, f(-) has the same structure, while trained or tested by different samples. The pros and cons of each model are evaluated and discussed in Secciion 4
End-to-end Classifier. The most straightforward approach to distinguishing between real and generated graphs is to train a binary classifier in an end-to-end manner. As aforementioned, among all the research, graph classification methods based on graph convolutional networks (GCNs) are commonly recognized as the state-of-the tte--artttttt technique in deep learning- based graph classification Kipf & Welling (017)); Hamilton et al. (2017); Chen et al. (2018); Xu et al. (2019b). Also, we can also see the results from Appendix A.5 also shows that GCN performs better in most of the times compared with other GNN networks. Therefore we choose the GCN model Kipf & Welling (2017) our end-to-end classifier. It consists of four GCN layers and fully connected layer. We use this four-layer GCN network to embed the graph data into a 128 28--dimnsiionl vector, and use fully connected layer compute the final classification result.
Contrastive L cearning-based Model. Previous studies have shown that contrastive learning helps to improve the graph encoding performance Zhuu et al. (202Ta); You et al. (2020): : Hassani & Ahmadi (2020); Zhu et al. 202 Different from the traditional binary classifier that trains the GNN model in an end-to-end manner, the contrastive learning- a self- suf-superviiion manner, then uses the graph encoder to transform the graphs into graph embeddings, and employs a binary classifier to predict the results. Figurre (in (in[Appendix A.3) illustrates the general workflow of our contrastive learning- based model. We use support vector machines (SVM) as the final classifier following the previous work (Sun et al. (2020a); You et al. (2020). The implementation details of the contrastive learning-based model are introduced in Appendiix A.3]
model first learns a powerful graph encoder in
Metric Learning-based based Model. In the past few years, deep metric learning has consistently achieved the state-of-the-art model performance Xing et al. al.. (2002); (Schroff et al. (2015); Song et al. (2016). As one of the cutting-edgs unsupervised representation learning models, deep metric learning aims to map imput data into metric space, where data from the same class get close while data from different classes fall apart from each other. However, unlike other tasks such as classification or face recognition in which only one training sample is needed to get the output, in metric learning, at least two training samples are needed at one time, as the output of metric learning is whether the two input samples are from the same category Guo et al. (2017): He et al.) (2018). Based on the core concept of metric learning, siamese network Guo et al. (017)): which takes paired samples as inputs and outputs whether the paired samples are from the same category. The implementation details of metric learning based model is introduced in Appendix A.4, Since the siamese network takes paired samples as input and only predicts whether the two input samples are from the same label, to evaluate the performance of the metric learning- based model in the perspective of getting prediction results of each graph, we still need to predict the exact label for each testing sample by querying the siamese network using paired samples consists of one testing sample and one known sample.
; He et al. (2018) 18 is proposed,
In order to get the final classification results, for each testing sample, we randomly select N₂ samples of each label from the training set and generate N₂ * Nelase paired samples. Here Netass equals to 2 (i.e., real and generated). After feeding the paired samples into the siamese network, we will get N₂ posteriors for each label. Each posterior represents the probability of the paired samples from the same label. After calculating the mean value of the N₂ posteriors for each label, we can find the
4

---

Under review as a conference paper at ICLR 2023
maximum mean value and take the corresponding label as the predicted result of the testing sample. For example, if the maximum mean value of the posteriors is from label real, then we consider using real as the final classification result.
EXPERIMENTS
We first introduce the datasets and implementation details of experiments. Then following the application scenarios described in Section 3, we conduct experiments based on each scenario.
4.1 EXPERIMENTAL SETUP
Datasets. We 7 benchmark datasets from TUDataset
Morris et al. (2020) to evalu-
ate the performance, including AIDS Riesen & Bunke (2008).
Alchemy Chen et al. (2019).
Deezer ego nets (abbreviated as Deezer) Rozemberezki
al.
(2020), DBLP DBL GitHub
StarGazer (abbreviated as GitHub) |Rozemberczki et al. (2020).
COLLAB Yanardag & Vish
wanathan (2015) and Twitch ego nets (abbreviated as Twitch)
Rozemberezki al. (2020).
Among them, Deezer, GitHub, and Twitch are so- cial networks with nodes representing users and edges indicating friendships. DBLP and COLLAB are collaboration networks with nodes represent- ing papers/rescarchers and edges indicating cita- tions/collaborations. AIDS and Alchemy are molec- ular graphs with nodes representing atoms of the compound and edges corresponding to chemical bonds. These graphs form real datasets for the rest of the evaluation. The statistics of all the datasets are summarized in Table I
Table I: Dataset statistics.
Dataset
# of graphs
Avg. Nodes
Avg. Edges
AIDS
2,000
15.69
16.20
Alchemy
202,579
10.10
10.44
Deezer
9,629
23.49
65.25
DBLP
19,456
10.48
19.65
GitHub
12,725
113.79
234.64
COLLAB
5,000
74.49
2,457.78
Twitch
127,094
29.67
86.59
Sampling High-qualit, Generated Graphs. Al- though the graph generators are capable to generate graphs with similar distribution as real graphs, some of the generated graphs may still contain obvious artifacts in some cases. There is a concern that the classification may be biased by such artifacts. Thus we compute the number of nodes, the number of edges, density, diameter, average clustering and transitivity as the statistical features of each graph and use Euclidean Distance measure the 1 i-nearest-neighel similarity between each generated graphs and real graph sets Yu et al. (201)). We select 20% generated graphs with the highest similarity for the following experiments.
To evaluate the quality of generated graphs, we use maximum mean discrepancy (MMD) over these graph features to measure the similarity between real graphs and graphs generated by different generators. The MMD results show that the graphs generated by different generators and real graphs are statistically indistinguishable. The MMD results are shown in Table 6 Apppeddix A.6)
Implementation Details. We the GCN embed the graphs in the end-to-end classifier and metric learning- -base model. The GCN is implemented in PyTorch [PyT] The optimizer we used Adam optimizer Kingma& & Ba (2015). Each model is trained for 200 epochs. The learning rate is set to 0.001 and we adopt Cross- Cross-Entropy Loss as the loss function. The ratio of the training set and testing set is 8:2. The contrastive learning-basee model is trained following the implementation details in GraphCL You et al. (220). As mentioned in Section 3.3] we generate Nps * 2 paired samples to train the stamese network in the metric learning- based model and use N& samples from each label to predict the final results. Nps 2 is the number of paired samples used to train the siamese network. Here we conduct experiments to fine-tune metric learning- model and find the best N,, 200, 000 and N₂ 10 which makes the model perform the best. The corresponding results are displayed in Appeeddix A.6 (Figure 5 and Figure 6).
Baseline. To better evaluate the performance of our proposed models, We incorporate new model named Feature Classification (FC) as the baseline. FC model leverages the graph statistical features as input and uses Multilayer perceptron (MLP) to do the final prediction. The statistical features we used are the number of nodes, the number of edges, density, diameter, average clustering and transitivity, which the same the features used to sample high-quality graphs.
5

---

Under review as a conference paper at ICLR 2023
4.2 EXPERIMENTS FOR THE "CLOSED WORLD" SCENARIO
In this scenario, we want to explore whether real graphs and generated graphs can be distinguished when the distribution of all testing graphs are known. As introduced before, we propose three methods to classify graphs. The evaluation metrics we used in this paper are accuracy and F1-score.
Overall Results. The accuracy of binary classification is summarized in Table 3] In general, our proposed models outperform FC model in all datasets, demonstrating that the GNN-based models can better capture the characteristies of graphs compared to using MLP with only statistical features. Also, observe that among the three methods, the metric learning-based model performs the best in most cases, while the contrastive learning-basse baaiid model performs least satisfying. Moreover, the results show that in general, the performance of Deezer. Github, and Twitch is better than other datasets. Compared to other datasets, the graphs in Twitch, Github, and Deezer are bigger and the three datasets also have a richer amount of graphs. This implies that the binary classifiers can distinguish between real graphs and generated graphs with higher accuracy for larger datasets with bigger graphs.
Although the contrastive learning- based model and metric learning- based model have similar goal, i.e. training an encoder that makes graphs with the same label get closer to each other and graphs with different labels fall apart, the metric learning-basn -aaedd-aadddda model performs better than the contrastive learning- based model in this scenario. Thus can draw the conclusion that the embeddings produced by the metric learning tend to be distinguished easily in graph datasets.
Dataset Oblivious Study. Besides the evaluation from the perspective of single dataset, we also conduct the dataset oblivious study. In this experiment, we first randomly sample 1,000 real graphs from each dataset. Then we randomly select 1,000 generated graphs which are evenly generated by all the generators from each dataset. Finally, we obtain a mixed dataset consisting of 7,000 real graphs and 7,000 generated graphs to train the binary classifier.
Surprisingly, a persuasive performance can also be noticed even when we don't take the dimension of the dataset into consideration. The performance indicates that the models can still distinguish real graphs from generated graphs even when the graphs used to train the model don't belong to any specific dataset. This is more meaningful in the real world scenario we may not know which dataset the graphs come from at the test time. In the mixed dataset, the end-to-end classifier performs the best, which means when the graphs which need to be classified do not belong one specific dataset, the end-to-end classifier can better capture the complex dependencies of graphs and detect generated graphs with higher accuracy.
Distinguish Graphs Generated by Unseen Gen- erators. Apart from classifying real graphs and graphs generated by unseen generators, we use met- ric learning to predict whether two graphs generated by unseen generators erator. To evaluate the performance of predicting whether any two graphs generated by unseen gen- erators are generated by the same generator, we randomly generate 50,000 positive graph pairs and 50,000 negative graph pairs and use metric learning take the graph pairs as input (the performance shown in Table 2). It can be noticed that the metric learning can predict whether two graphs generated by unseen generators are generated by the same gen- erator to some extent. Moreover, we can see that the performance of Deezer, Github and TWITCH are better than other datasets, which is consistent with the results of the "Open Generator" scenario.
Table 2: Distinguish Graphs Generated by Un- seen Generators.
generated by the same gen-
Accuracy
F1-score
AIDS
0.78
0.78
Alchemy
0.82
0.82
Deezer
0.93
0.93
DBLP
0.75
0.74
GitHub
0.95
0.95
COLLAB
0.83
0.83
TWITCH
0.89
0.89
MIXED
0.64
0.64
However, when we use the mixed dataset to train and test the metric learning-based model, the performance is much worse than in other datasets. It is reasonable since we can see from Table 3 that the metrie learning- based model with mixed dataset performs the worst among all the datasets. The visualization of graphs generated by the unseen generators shown in in(Figure aasso supports our results, the embeddings of the mixed dataset not be separated explicitly compared to other datasets.

---

Under review as a conference paper at ICLR 2023
Table The accuracy/FI-score of generated graph detection in "Closed World" scenario and "Open Generator" scenario.
Closed World
Open Generator
Dataset
FC
End-lo-end Contrastive
Metric
PC
End-to-end Contrastive
Metric
AIDS
0.75500.7
0.89/0.85
0.87/0.84 84
0.91/0.90
0.73/0.70
0.82/0.81
0.84/0.82
0.87/0.84
Alchemy
0.78/0.78
0.87/0.87
0.85/0.80
0.90/0.89
0.74/0.73
0.80/0.77
0.82/0.79
0.84/0.82
Deezer
0.78/0.78
0.97/0.95
0.95/0.94
0.98/0.97
0.74/0.74
0.90/0.88
0.92/0.92
0.91/0.91
DBLP
0.70/0.68
0.84/0.83
0.82/0.82
0.82/0.82
0.75/0.74
0.79/0.79
0.82/0.82
1980/0.79
Github
0.81/0.81
0.95/0.94
0.92/0.92
0.96/0.96
0,80/0.82
0.94/0,94
0.91/0.91
0.96/0.92
COLLAB
0.56/0.55
0.85/0.84
0.84/0.82
0.89/0.89
0.50/0.49
0.78/0.76
0.80/0.79
0.84/0.82
Twitch
0.56/0.55
0,92/0.89
0.90/0.88
0.95/0.93
0.51/0.49
0.85/0.85
0.90/0.89
0.86/0.86
Mixed
0.64/0.62
0.84/0.83
0.80/0.80
0.82/0.81
0.60/0.59
0.78/0.76
0.82/0.80
0.79/0.78
4.3 EXPERIMENTS FOR THE "OPEN GENERATOR" SCENARIO
The experiments above have proved that the real graphs and graphs generated by different generators can be distinguished in the close world scenario. In order to further evaluate if our models can still detect generated graphs when given unseen generators. we choose three different generators GraphRNN You et al. (2018b), SBMGNN Mehta et al.] (2019). and GraphVAS VAE Simonovsky & Komodakis 2018) generate fake graphs for each dataset. For all datasets, use real graphs the positive samples and graphs generated by unseen generators as the negative samples to test the models.
Overall Results. The final classification results shown in Table 3 from which
that the binary classification results of all the datasets are over 0.75, which indicates that even when the graphs are generated by unseen algorithms, the models can still have relatively good performance. This indicates that all the models can generalize to other generators. Also, we can see higher accuracy of the metric learning-based model, which exemplifies that can better generalize to other generators.
Dataset Oblivious Study. Moreover, we also train all models for the mixed dataset. It can be noticed that the performance of the mixed dataset in part with those of other datasets. The experimental results suggest that our models can still generalize to previously unseen generators even when we don't take the dimension of the dataset into consideration.
The accuracy of the contrastive learning- model for the mixed dataset is even better for COLLAB and is the best among the three models. This suggests that the contrastive learning based model can better generalize to other generators in datasets with wide range of node numbers and graph densities, i.e. mixed dataset.
4.4 EXPERIMENTS FOR THE "OPEN SET" SCENARIO
Apart from distinguishing between real graphs and graphs generated by unseen algorithms, we also conduct experiments to evaluate whether graphs generated by unseen datasets can still be distinguished from real graphs. In this experiment. we use graphs from AIDS, Alchemy, Deezer, DBLP, and Github as the seen datasets to train all the models, and use COLLAB and Twitch as unseen datasets test the models.
For each seen dataset, we randomly select 1,000 real graphs and 1,000 generated graphs which are evenly generated by the seen generators. In the end, we use the final dataset with 5,000 real graphs and 5,000 generated graphs to train all the models.
In this scenario, we want to evaluate whether the fake graphs generated by seen generators unseen datasets can be distinguished from the real graphs. To test the model, for each unseen dataset, randomly select real graphs and the same amount of generated graphs which are evenly generated by the seen generators. The final testing set contains 2,000 real graphs and 2,000 generated graphs. The performance of all the models is summarized in Table 4]
We from the table that, in general, the real graphs and generated graphs be distinguished with an accuracy higher than 0.78. This implies that our models have the ability to generalize to unseen datasets. Moreover, the accuracy of the contrastive learning-based model is higher than 0.85
7

---

Under review as a conference paper at ICLR 2023
Table 4: Generated graph detection in "Open Set" scenario and "Open World" scenario.
Open Set
Open World
Metric
Accuracy
Fl-score
Accuracy
Fl-score
Feature classification
0.57
0.54
0.64
0.62
End to end classifier
0.82
0.82
0.76
0.75
Contrastive learning- based model
0.85
0.84
0.83
0.83
Metric learning- baaningg-baeedd model
0.78
0.76
0.74
0.74
and the best among the three models, which suggests that the contrastive learning-basee model can generalize to the unseen datasets better.
After comparing the performance with the "Closed World" scenario in Section 4.2 we find that the performance drops. It is reasonable because the graphs used to test the models come from new datasets which are not seen in the training set, which makes the task harder than in the previous experiment.
4.5 EXPERIMENTS FOR THE "OPEN WORLD" SCENARIO
The fourth scenario is to evaluate whether the fake graphs generated by unseen algorithms in unseen datasets can be distinguished from the real graphs. To test the model, for each unseen dataset, we randomly select real graphs and the same amount of generated graphs which are evenly generated by the unseen generators. The final testing set contains 2,000 real graphs and 2,000 generated graphs. The performance of all the models is summarized in Table 4
The scenario is called the "Open World" scenario as described before since the datasets and generators both unseen in the training phase. It is the hardest task among the four scenarios. We can see from Table 4 that the performance, as expected, lower than those in Sectiion 4.4 and [Section 4.5)
Although the performance is not competent, the accuracies of all models still higher than 0.74. This suggests that the models can still distinguish real graphs and graphs generated by unseen generators in unseen datasets to some extent. Apart from that, the contrastive learning-basee based model performs the best among all the models, which is in line with the previous experiments.
Throughout all the experiments, to perform better in the "Closed World" scenario while the contrastive learning-haad based model shows advantages in "Open Generator". "Open Set" and "Open World" scenarios. The results give us an insight that metric learning can learn better representations of graphs with known graph distributions. On the contrary, as a representative celf-super method, the contrastive learning- based model can leamn representations that are more general and can be transferred to different graph distributions.
draw conclusion that the metric learning- bbaed model tends
4.6 VISUALIZATION ANALYSIS
Among the previous experiment, we can draw the conclusion that contrastive learning-based models tend perform better "Open Generator". "Open Set" and "Open World" scenarios with the mixed dataset, we further explore the reason behind it. To this end, we use t- t-Distributed Stochastic Neighbor Embedding (t-SNE) van der Maaten & Hinton (2008) visualize the graphs embedded by different models. Figure IJshows the t-SNE results of the testing samples used in the fourth scenario. can easily noticed that the embeddings produced by the contrastive encoder can be divided better, which may be the major reason why the contrastive learning- model outperforms other models in the "Open World" Scenario.
5 RELATED WORK
We have already covered several highly-related works (e.g., graph generative models and graph neural networks) in Section 2 We discuss additional related work in a broader scope below.
Generated Data Detection, Although remains an unexplored area in generated graph detection, there has been some research about generated image detection in the past few years. Rössler et al.
8

---

Under review as a conference paper at ICLR 2023
(a) End-to-end
(b) Contrastive
(c) Metric
Figure 1: The visualization results of different models in "Open World" scenario.
showed that simple classifiers can detect images created by a single category of networks Rössler et al. (2019) Wang et al. Wang et al. (2020) demonstrated that simple image classifier trained on one specific CNN generator ProGANNarran et al. (2018)) is able to generalize well to unseen architectures. Ning et al. Yu et al. (2019) learned the GAN fingerprints towards image attribution and showed that even a small difference in GAN training (e.g., the difference in initialization) can leave distinct fingerprint that be detected. Most of the previous studies focus on image data; as far as we know, we are the first to investigate the generated graph detection.
Privacy and Security Issues in GNN. Rising concerns about the privacy and security of GNNs have led to a surge of research on graph adversarial attacks. Broadly speaking, they can be grouped into two categories causative attacks and exploratory attacks. Causative attacks on GNNs add unnoticeable adversarial perturbations to node features and graph structures to reduce the accuracy of or intentionally change the outcome of node classification [Bojchevski Günnemann (201);
Caverlee et al. | (2020); Ma et al. (2020); : Sun et al. (2020b); Wu et al. (2019): [X et al. (2019a). link Günnemann (2019) Lin al. (2020), graph classification Dai et al. (2018);
prediction Bojchevski
Xi et al. (2021), etc. To conduct causative attacks, attackers must be able tamper with the training process of GNNs or influence the fine-tuning process of pre-trained GNNs. Exploratory attacks on GNNs send (carefully crafted) query data to the target GNNs and observe their decisions these input data. Attackers then leverage the responses to build shadow models to achieve different attack goals, such link re-identificatin [He et al. (2021), property inference Zhang et al. (2022), membership inference Wu et al. (2020), model stealing Duddu et (2020), etc. To launch exploratory attacks, attackers must be able to interact with the GNNs (e.g., via publicly accessible API) the runtime.
CONCLUSION AND FUTURE WORK
In this paper, we propose a general framework for generated graph detection. In this framework. we introduce four application scenarios based on different training data and testing data and design three kinds of models to accomplish experiments in each scenario. The experimental results show that all models can distinguish real graphs from generated graphs successfully in all scenarios, which means that although the generative models show great advantage and success in many domains, the generated graphs can still be detected by GNN-based models. Also, notice that the metric learning-based model tends to perform the best in the close world scenario while the contrastive learning-based model always shows the best performance in "Open Generator", "Open Set" and "Open World" scenarios, which suggests that the contrastive learning-based model can generalize to datasets and generators better. Our experiment about dataset oblivious study shows that our models can still work with a persuasive performance when we use the mixed dataset to train and test the models. This is an interesting finding since the graphs in different datasets vary a lot, hence the mixed dataset tends to have wide range of node numbers and densities. The results imply that our models can handle datasets with many disparate graphs. The finding also fits more to the real world situation, where the graphs that need to be detected may not be from specific dataset. Moreover, although we only discuss the detection of generated graphs in this paper, the framework can also be extended to other research areas, such images, text, or audio.

---

Under review as a conference paper at ICLR 2023
REFERENCES
b http:////hhhhb.cccm//////aaaaaa1 _atraph_datteetsssss
Sctps://pytorch.co
Réka Albert and Álsert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 2002.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial Attacks on Node Embeddings via Graph Poisoning. In International Conference on Machine Learning (ICML), pp. 695-704. PMLR, 2019.
James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang. All You Need Low (Rank): Defending Against Adversarial Attacks Graphs. In ACM International Conference on Web Search and Data Mining (WSDM), pp. 169-177. ACM, 2020.
Guangyong Chen, Pengfei Chen, Chang-Y Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, Richard S. Zemel, and Shengyu Zhang. Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models. CoRR hbbs/1906.09427, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In International Conference on Learning Representations (ICLR), 2018.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey E. Hinton. A Simple Framework for Contrastive Learning of Visual Representations. In International Conference on Machine Learning (ICML), pp. 1597-1607, PMLR, 2020.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial Attack on Graph Structured Data. In International Conference on Machine Learning (ICML), pp. 1123-1132. PMLR, 2018.
Vasisht Duddu, Antoine Boutet, and Virat Shejwalkar. Quantifying Privacy Leakage in Graph Embedding. CoRR abs/2010.009h0 2020.
Paul Erdös and Alfréd Rényi. On Random Graphs I. Publicationes Mathematicae Debrecen, 1959.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative Generative Modeling of Graphs. In International Conference on Machine Learning (ICML), pp. 2434-2444. PMLR, 2019.
Qing Guo, Wei Feng, Ce Zhou, Rui Huang, Liang Wan, and Song Wang. Learning Dynamic Siamese Network for Visual Object Tracking. In IEEE International Conference on Computer Vision (ICCV), pp. 1781-1789. IEEE Computer Society, 2017.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Annual Conference on Neural Information Processing Systems (NIPS), pp. 1025-1035. NIPS, 2017.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive Multi- View Representation Learning on Graphs. In International Conference on Machine Learning (ICML), pp. 4116 4126. PMLR, 2020.
Anfeng He, Chong Luo, Xinmei Tian, and Wenjun Zeng. Twofold Siamese Network for Real-Time Object Tracking. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4834 4843. IEÉE Computer Society, 2018
Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. Stealing Links from Graph Neural Networks. In USENIX Security Symposium (USENIX Security), pp. 2669-2686. USENIX, 2021.
Olivier J. Hénaff. Data-Efficient Image Recognition with Contrastive Predictive Coding, In Interna- tional Conference on Machine Learning (ICML), pp. 4182-4192. PMLR, 2020.
Tero Karras, Timo Aila. Samuli Laine, and Jaakko Lehtinen. Progressive Growing of GANs for Im- proved Quality, Stability, and Variation. In International Conference on Learning Representations (ICLR), 2018.
10

---

Under review as a conference paper at ICLR 2023
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular Graph Convolutions: Moving Beyond Fingerprints. Journal of Computer-Aided Molecular Design, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR), 2015.
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. International Conference on Learning Representations (ICLR), 2014.
Thomas N. Kipf and Max Welling. Variational Graph Auto-Encoders. In NeurlPS Workshop on Bayesian Deep Learning (NeurIPS-16 BDI.), 2016.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference Learning Representations (ICLR), 2017.
Xiaoxiao Li, João Saúde, Prashant Reddy, and Manuela Veloso. Classifying and Understanding Financial Data Using Graph Neural Network. In The AAAI Workshop on Knowledge Discovery from Unstructured Data in Financial Services (KDF). AAAI, 2020.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient Graph Generation with Graph Recurrent Attention Networks. In Conference on Neural Information Processing Systems (NeurIPS), pp. 4257 -267, 2019.
Wanyu Lin, Shengxiang Ji, and Baochun Li. Adversarial Attacks on Link Prediction Algorithms Based on Graph Neural Networks. In ACM Asia Conference on Computer and Communications Security (ASIACCS), pp. 370-380. ACM, 2020.
Yixin Liu, Shirui Pan, Ming Jin, Chuan Zhou, Feng Xia, and Philip S. Yu. Graph Sepf-Supervised Learning: A Survey. CoRR abs/2103.00111, 2021.
Jiqqi Ma. Shuangrui Ding, and Qiaozhu Mei. Towards More Practical Adversarial Attacks on Graph Neural Networks. Annual Conference on Neural Information Processing Systems (NeurIPS). NeurlPS, 2020.
Nikhil Mehta, Lawrence Carin, and Piyush Rai. Stochastic Blockmodels meet Graph Neural Networks. In International Conference on Machine Learning (ICML). pp. 1466644744 PMLR, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In The ICML Workshop on Graph Representation Learning and Beyond (GRL). ICML, 2020.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. DeepInf: Social Influence Prediction with Deep Learning. In ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 2110-2119 ACM, 2018
Kaspar Riesen and Horst Bunke. IAM Graph Database Repository for Graph Based Pattern Recogni- tion and Machine Learning. In Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshop (SSPR), pp. 287-297. Springer, 2008
Andreas Rössler, Davide Cozzolino, Luisa Verdoliva, Christian Riess, Justus Thies, and Matthias Nießner. FaceForensicst+:: Learning to Detect Manipulated Facial Images. In IEEE International Conference on Computer Vision (ICCV), pp. 1-11. IEBE, 2019.
Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-Source Python Framework for Unsupervised Learning on Graphs. In ACM International Conference on Information and Knowledge Management (CIKM), pp. 3125-3132. ACM, 2020.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. FaceNet: A Unified Embedding for Face Recognition and Clustering. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 815-823. JEEE, 2015.
Yun Shen, Xinlei He, Yufei Han, and Yang Zhang. Model stealing attacks against inductive graph neural networks. pp. 1175-1192. IEFE, 2022.
11

---

Under review as a conference paper at ICLR 2023
Martin Simonovsky and Nikos Komodakis. Dynamic Edge- Cigge-Conditooeed Filters in Convolutional Neural Networks on Graphs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 29-38. IEEE Computer Society, 2017.
Martin Simonovsky and Nikos Komodakis. GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders. In International Conference Artificial Neural Networks (ICANN), pp. 412-422. Springer, 2018.
Kihyuk Sohn. Improved Deep Metric Learning with Multi-class N-pair Loss Objective. In Annual Conference on Neural Information Processing Systems (NIPS), pp. 1849-1857, 2016.
Hyun Oh Song, Xiang. Stefanie Jegelka, and Silvio Savarese. Deep Metrie Learning via Lifted Structured Feature Embedding. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4004-4012 IEEE Computer Society, 2016.
Julia Stoyanovich, Bill Howe, and H. V. Jagadish. Responsible Data Management. Proceedings of the VLDB Endowment, 2020.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization. In International Conference on Learning Representations (ICLR), 2020a.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Son-tagget-ppecffic Node Injection Attacks on Graph Neural Networks: A Hierarchical Reinforcement Learning Approach. In The Web Conference (WWW), pp. 673-683. ACM, 2020b.
Laurens van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE, Journal of Machine Learning Research, 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018.
Sheng-Y Yu Wang, Oliver Wang. Richard Zhang, Andrew Owens, and Alexci A. Efros. CNN-Generated Images Are Surprisingly Easy to Spot... for Now. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1792-8701. Computer Vision Foundation IEEE, 2020.
Bang WU, Xiangwen Yang, Shirui Pan, and Xingliang Yuan. Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization. CoRR /2751, 2020.
Bang Wu, Xiangwen Yang, Shirui Pan, and Xingliang Yuan. Adapting membership inference attacks to GNN for graph classification: Approaches and implications. In IEEE International Conference on Data Mining, ICDM 2021, Auckland, New Zealand, December 7-10, 2021, pp. 1421-1426. IEEE, 2021a.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial Examples for Graph Data: Deep Insights into Attack and Defense. In International Joint Conferences on Artifical Intelligence (ICAA)) pp. 4816-4823. IJCAI, 2019.
Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan.7.Ii. Self-supervised Learning Graphs: Contrastive, Generative,or Predictive. IEEE Transactions on Knowledge and Data Engineering, 2021b.
Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised Feature Learning via Con-Parametric Instance Discrimination. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3733-3742 IEEE, 2018
Zhaohan Xi, Ren Pang, Shouling Ji, and Ting Wang. Graph Backdoor. In USENIX Security Symposium (USENIX Security). USENIX, 2021.
Yaochen Xie, Zhao Xu, Zhengyang Wang, and Shuiwang Ji. Self-Supervised Learning of Graph Neural Networks: A Unified Review. IEEE Transactions on Knowledge and Data Engineering. 2022.
12

---

Under review as a conference paper at ICLR 2023
Eric P. Xing, Andrew Y. Ng, Michael Jordan, and Stuart J. Russell. Distance Metric Learning with Application to Clustering with Side-Informatio. In Anmual Conference on Neural Information Processing Systems (NIPS), pp. 505-512. MIT Press, 2002.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective. In International Joint Conferences on Artifical Intelligence (IJCAI), pp. 3961-3967. IJCAI, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference Learning Representations (ICLR), 2019b.
Pinar Yanardag and S. V. N. Vishwanathan. Deep Graph Kernels. In ACM SIGKDD International Conference on Knowledge Discovery and Data (SIGKDD), pp. 1364-1374. ACM, 2015.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation. In Conference on Neural Information Processing Systems (NeurIPS), pp. 6412-6422, 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. In International Conference on Machine Learning (ICML), pp. 5694-5703. PMLR, 2018b.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph Contrastive Learning with Augmentations. In Annual Conference on Neural Information Processing Systems (NeurIPS). NeurIPS, 2020.
Ning Yu, Larry Davis, and Mario Fritz. Attributing Fake Images to GANs: Learning and Analyzing GAN Fingerprints, In IEEE International Conference on Computer Vision (ICCV), pp. 7555-7565. IEFE, 2019.
Zhikun Zhang, Min Chen, Michael Backes, Yun Shen, and Yang Zhang. Inference Attacks Against Graph Neural Networks. In USENIX Security Symposium (USENIX Security). USENIX, 2022.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep Learning Graphs: A Survey. JEEE Transactions on Knowledge and Data Engineering, 2020.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An Empirical Study of Graph Contrastive Learning. CoRR abs/2109, 01 16, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph Contrastive Learning with Adaptive Augmentation. In The Web Conference (WWW), pp. 2069-2080. ACM, 202
13

---

Under review as a conference paper at ICLR 2023
Generated Graphs
Real Graphs
Generator
GNN- based Classifier f(+)
Generated
Generator
Real
Figure 2: The pipeline of generated graph detection. The real graphs from real world datasets, the generated graphs are generated by different graph generators based on real graphs. The GNN- based classifier is built classify real graphs and generated graphs.
A APPENDIX
A.1 THE DETAILED INFORMATION OF GRAPH NEURAL NETWORKS
Graph Neural Networks (GNNs) have shown great effectiveness fusing information from both the graph topology and node features Zhang et al. (2020) Hamilton et al. (2017); Kipl' & Welling (2017) recent years, they become the start-of of-thh-art technique as essential building blocks in graph generators and graph classification algorithms.
General Definition. Most of the GNNs learn the node representations for graph-structured data by neighborhood aggregation strategy, where model iteratively updates the representation of node through message passing and aggregating representations of its neighbors. After iterations of aggregation, can get the node's representation h, which stores the structural information within its k-hop neighborhood. Typically, the GNN contains multiple graph convolutional layers. The definition of each layer is follows:
he & (ha-1 v (h k-1 hh- Yu EN()).
where (Vv)
is of nodes adjacent node h is the node embedding of node after k iterations, v (h--1 1..-",h-- -h-1)) represents the message received from the neighbours, and o(-) is an aggregation operation.
Aggregator. Recently, researchers have proposed different kinds of practical implementations of aggregation operations KKipf & Welling (2017); Hamilton et al. (201)); Chen et al. (2018); Xu et al. (2019b), among which the Graph Convolutional Networks (GCN) the most representative method which uses the symmetric normalization method to aggregate all the information from the neighbors and shows great success Kipf & Welling (2017). The aggregation process of GCN can be defined as follows:
h = & (h ())
Σ h /--1)//da dd,dg
(2)
aEN(e)UU
where d,, and dy are the node degrees node and v, respectively. Here o(-) is mean aggregation operator.
Graph Pooling. After obtaining embeddings of all nodes, we use a graph pooling operation to integrate the embeddings of all nodes in the graph to get the embedding of the whole graph. In our graph classification model, we use a straightforward but efficient approach called mean pooling that averages all the node embeddings to obtain the graph embedding, i.c.. hg M Euey h..
14

---

Under review as a conference paper at ICLR 2023
Grapph collection and generation
B. Contrastive encoder
Final prediction
Pretrained contrastive encoder
Encoder
Projection Hene
Encoder
ML- based Classifte
Generited
Augmentation
Shered Weights
Contrastive
Real
Encoder
Projection
Head
Figure 3: The workflow of the contrastive learning-based model. The model trains a contrastive encoder to embed the graphs and uses machine learning-band based classifier to do the final classification. The contrastive encoder is based GraphCL You et al. (2020), which uses the graph augmentation method to get two correlated augmented views as a positive pair and embed them with a GNN-based encoder f (-) and projection head g (-)- Then the contrastive loss function is used to maximize the agreement between the positive pairs. After embedding all the graphs, we use support vector machines (SVM) do the final prediction.
A.2 THE DETAILED INFORMATION OF GRAPH GENERATORS
Traditional Graph Generator. Frdös-Rényi (ER) model Erdös & Rényi (1959) and Barabási-Albert (BA) model Albert & Barabási (202)) are two commonly used traditional graph generators. Given a few parameters, these generators can be explicitly expressed by formulas. ER model generates random graphs with a fixed number of nodes and edges. BA model is often used to generate scale-free graphs using a preferential attachment mechanism. That is, new node will be added each time, and the edges will be randomly added to connect the new node and the existing nodes.
Autoencoder-based Generator. The autoencoder-based generator is type of neural network which used to learn the representations of unlabeled data and reconstruct the input graphs based on the representations. We consider VGAE Kipf & Welling (2016), Graphite Grover et al. (2019), SBMGNN Mehta et al. (2019), and Graph /
Komodakis (2018) in this paper. VGAE uses a graph convolutional network (GCN) as the encoder and the inner product as the decoder. The model can obtain the node features and capture the overall distribution of input graphs. Based on VGAE, Grover et al. proposed Graphite, latent variable generative model which also utilizes GCN as the encoder. Unlike VGAE, Graphite adds a multi-layer iterative neural network before the inner product to construct the decoder. SBMGNN produces graphs by modeling sparse latent variables, which makes it competitive in preserving the community structure. It uses a sparse variational autoencoder (VAE) Kingma & Welling (2014) to model graphs. The decoder consists of fast recognition model which models the probability of an edge between two nodes by a nonlinear function. Graph VAE is also an autoencoder based-model. It uses a feed-forward network with edge- conditioned graph convolutions (ECC) Simonovsky & Komodakis (2017) to encode the graphs into continuous representations. The main idea of the decoder is to output the probabilistic fully-connected graph and at last use standard graph matching algorithm to align it to the original graph.
Autoregressive-bazt Generator. To capture the complex dependencies of all nodes and edges, autoregressive-basee bassed generators are proposed. An autoregressive-buate based generator adds nodes and edges sequentially. In this paper, we include GRAN Liao al. (2019) and GraphRNN You al. (2018b) as the Autoregressive-basee model. GRAN generates a block of nodes and associated edges at each step. uses GNN with attention to utilizing the topology of the generated part of the graph, which makes GRAN model the dependencies between the already generated part and the newly generated part more effectively. GraphRNN uses two recurrent neural networks (RNN), which are called graph-level RNN and edge-level RNN. The graph-level RNN is used maintain the state of generated graph and generate new nodes. The edge-level RNN is used to generate the edges between new nodes and the already existing graph.
15

---

Under review as a conference paper at ICLR 2023
Graph
Encoder 6
sigmoid
L1 distancce hh)
Same class
Shared Weights
Different classes
Graph
Encoder f
Figure 4: The workflow of the siamese network. In siamese network, two graphs G; and G3 are fed into the encoder fo one by one get the embeddings h2 and hy. The L1 distance between h; and hy are calculated and used to do the final prediction.
A.3 THE IMPLEMENTATION DETAILS OF CONTRASTIVE BEARNING-BASED MODEL
Training Contrastive Encoder. As one of the cutting-edge unsupervised representation learning
models, contrastive learning aims at learning similar representations of the same data under different augmentations. is widely used in visual representation learning Chen et al. (2020); Wu et al. (2018)
Hénaff (2020) and graph embedding Zhu al. (021 You al. (2020); Hassani Ahmadi (2020
Zhu et al. 2021b In this paper, we use GraphCL You el al. 2020 as the graph contrastive encoder
In the graph contrastive encoder, first the graph augmentation method to get correlated augmented views Gr and Gj as positive pair. We use node dropping the first augmentation, and randomly select one augmentation from the augmentation pool as the second one. The augmentation pool consists of node dropping, edge perturbation, and subgraph. Then the G; and 93 will be embedded by a GNN-based encoder fo- After that, a projection head g(-) used to map the embeddings to different latent space to caleulate the contrastive loss. The projection head g(-) used in contrastive learning is a multi-layer perceptron (MLP). Then the contrastive loss function used maximize the agreement between the positive pairs. Here the loss function is the normalized lemperature-scaled
cross-entropy loss (NT-Xent) Sohn 2016); Wu et al. (2018).
When training the contrastive encoder, mini-batch of N graphs will be randomly sampled and processed, which means that 2 augmented graphs and the corresponding loss need to be optimized each time. We denote the augmented nith graph in the mini-batch as Σn,is Zn.j and them the positive pairs. The negative pairs are generated by Zn,is Zn,j and other augmented graphs within the same mini-batch except for 2n,6 Zn.j. Finally, the NT-Xent for the nih graph is defined follows:
2 Zn.j
sim (Zn,is kn.z) = Z Il |2n1j]]
(3)
Loss log exp (sim (Zn,i, Zn.)) /T)
(4)
En 2m exp (sim (Zn,ir 2n' /T)
where sim (Zn,i Zn.j) means the cosine similarity of En,is 2n,j- T denotes the temperature parameter. After generating the loss for each graph in the mini-batch, the overall loss computed across all the positive pairs in the mini-batch.
A.4 THE IMPLEMENTATION DETAILS OF METRIC LEARNING-BASER MODEL
Training Siamese Network. Figure 4 shows the workflow of the siamese network. Two graphs G and Gy are fed into the encoder fe one by one to get the embeddings h4 and hy. In the siamese
'The code of GraphCI. is http://ts////ttttb..m/////eeeeaa
16

---

Under review as a conference paper at ICLR 2023
Table The accuracy of different backbones in end-to-end model.
Dataset
GAT
GIN
GCN
AIDS
0.89
0.88
0.89
Alchemy
0.88
0.86
0.87
Deezer
0.96
0.96
0.97
DBLP
0.86
0.82
0.84
Github
0.93
0.94
0.95
COLLAB
0.84
0.82
0.85
Twitch
0.91
0.91
0.92
Mixed
0.82
0.83
0.84
network, the paired samples are fed into the same encoder and the weights of them are shared. Then the LI distance d between the two embeddings calculated by the following equation.
d abs abs( h
(5)
d is used to feed into the loss function and tune the network to get better embedding. The loss function we used in this paper is called binary cross-entropy loss, which is commonly used in classification tasks. The equation of binary cross equation loss is as follows:
Loss = - log(p) + (1 y) log(1 -p))
(6)
is used to feed into the loss function and tune the network to get a better emhedding. The loss function used in this paper is called binary cross-entropy loss, which is commonly used in classification tasks.
To train the siamese network, sample training set that consists of N ummps paired samples with the same label and Numps paired samples with different labels for each dataset.
A.5 ABLATION STUDY
Different GNN Networks. Our end-to-end model uses GCN as the backbone. We replace it with GIN[Xu et al. (2019b) and GAT Velickovic et al. (2018), and compare the performance of different backbones. We can see from Table 5 that most of the time, GCN performs better than the others, thus choose GCN as the final backbone of end-to-end model in our experiment.
Metric Learning-baate based Model.. To achieve the best classification results of the metric learning- based model, we evaluate the impact of different Nps and N& on model performance. Here Nys represents the number of paired samples used to train the siamese network. N₁ denotes the reference samples used obtain the final prediction results.
We can see from Figure 3 that if we use more paired samples to train the siamese network, the metric -based model tends perform better. Due the time and resource limitations, finally choose to use 20,000 paired samples to train the siamese network. Figure 6 shows that in general, the metric learning- -base model shows the best performance when N₂ 10. Thus N₂- 10 in the following experiments.
A.6 ADDITIONAL RESULTS
In the appendix, plots are illustrated for additional information and experimental results as mentioned throughout the paper.
MMD results. Table 6 shows the MMD results of real graphs and graphs generated by different
generators.
The visualization results of graphs generated by unseen generators.. Figure 7 shows the visual- ization results of three unseen generators (GraphRNN, GRAPHVAE and SBMGNN) produced by the metric learning- based model.
17

---

Under review as a conference paper at ICLR 2023
AuD EM
ALC-ENI
0.THR
TWIT04
TWETCH
2000
2000
30000
2X009
25048
50033
30900
200093
Samples
(a) Accuracy
(b) Fl Fc-se
Figure 5: Different Np. The impact different number of paired samples on metric learning-baa baasn model.
075
335
0The
1961
Reference Samples
Numbe Reference Samples
(a) Accuracy
(b) Fl-score
Figure 6: Different N₁. The impact different number of reference samples on metric learning- based model.
Table The MMD results of real graphs and graphs generated by different generators.
ER
BA
graphite
VGAE
GRAN
Gragh GraghRNN
sbmgnn
AIDS
0.0863
0.1070
0.0547
0.0324
0.0534
0.1016
0.0526
0.1884
Alchemy
0.0139
0.1167
0.0205
0.0088
0.0641
0.1493
0.0284
0.2844
Deezer
0.0356
0.1161
0.1869
0.2565
0.1168
0.0755
0.1167
0.1363
DBLP
0.0601
0.3117
0.0759
0.1168
0.4496
0.3835
0.1808
0.0238
Github
0.0249
0.2513
0.0398
0.0452
0.0315
0.1635
0.0314
0.0294
COLLAB
0.0270
0.0362
0.0092
0.0118
0.0024
0.0099
0.0021
0.0175
Twitch
0.0148 0.0336
0.0728
0.0589
0.0182
0.0663
0.0218
0.0681
18

---

Under review as a conference paper at ICLR 2023
CHAPHARE
CHAMPHANE
(a) AIDS
(b) Alchemy
(c) Deezer
SOUGNN BRAP-ANE Brik
GRAP doa
GRAPHIRK
GRAP AnE
GRAPPIIGG
DBLP
(c) Github
( COLLAB
(g) Twitch
(h) Mixed
Figure 7: The visualization results of graphs generated by unseen generators.
19


Reviews:
[{"review_id": "D4YUlLdPPV", "reviewer": "Reviewer_eg3n", "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": "The paper discusses the problem of detecting graphs that have been generated algorithmically. The paper discusses four different types of scenarios from the simplest (where the model knows all the possible details about the generation process) to the hardest (where nothing is known in advance).\n\nThe classifier used is an end-to-end trained GNN encoder with an MLP used to output the classification outcome.\n\nThe classifier has a decent performance, although not super high making the task challenging.", "summary_of_the_review": "Some questions to authors:\n\n1. When you write: \"... use Euclidean Distance to measure the 1-nearest-neighbor similarity between each generated graphs and real graph sets...\" ==> how can you make sure that euclidean in the embedding space is the right distance? Have a look at these two papers (https://www.sciencedirect.com/science/article/abs/pii/S002002551630696X ; https://arxiv.org/abs/1812.09095) is there anything that you could use to better compute the 1-nearest neightbor?\n\n2. If you have a good way to detect generated graphs, wouldn't this be useful to filter out generated graphs that are difficult to spot? How would you prevent this from happening?", "strength_and_weaknesses": "# Strengths\n\n1. Novel problem\n2. Method is simple enough to be easy to implement\n\n\n# Weaknesses\n\n1. The method itself could be used to detect generated graphs that cannot be detected easily and thus being used in an attack\n2. The classifiers that  authors tested on their datasets are pretty much \"standard\". I wonder wether there might be some better architecture that can be used to take specific care of this task", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "Aa2jMu7qWQ", "reviewer": "Reviewer_chCC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors present a new problem, how to detect real graphs and \"fake\" graphs. The authors then explore four scenarios where the detection algorithm applies, and propose three different machine-learning methods to detect fake graphs.", "summary_of_the_review": "I recommend a weak reject for this paper because of its limited novelty and the weak motivation.", "strength_and_weaknesses": "Strengths,\n\nS1: Authors explore four scenarios, which provide both ideal circumstances and realistic circumstances.\nS2: This paper proposes a new problem.\n\nWeaknesses,\n\nW1: The motivation is not strong and seems artificial. It is not clear how the generated graphs are used in malicious misuses or misinformation broadcasts.\n\nW2: The novelty is limited. The proposed methods are based on existing works.", "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": {}}, {"review_id": "6lN-XGwikD8", "reviewer": "Reviewer_4WuZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "DISCLAIMER: I reviewed this paper for NeurIPS 2022 earlier this year. As far as I can tell, not much (if anything) has changed in this manuscript. As such, I will reiterate the points in my original review.\n\nSummary:\n\nThe authors investigate the performance of existing graph neural network models to discern between real graphs and \"fake\" graphs generated synthetically, potentially for a nefarious purpose. The authors explore 4 scenarios of increasing complexity and real-world relevance, as well as 3 different approaches from the machine learning literature to learn to discern between real and fake graphs.", "summary_of_the_review": "See my comments above. My main concern with this paper is the lack of novelty. If the main contribution of the paper is a new ML task, I do not find compelling evidence in the paper to suggest that this task will have an application in the future. It may very well be the case that this task will become relevant for a certain domain at some point. But we simply do not know, and we can just \"extrapolate\" from other types of data, such as images.\n\nI am curious as to how the authors arrived to the generated graph detection problem? Was there a particular application in mind where fake graphs are indeed a concern? If so, please discuss in the paper, as it would *significantly* strengthen the contribution. Or was the thought more along the lines of \"if the task of detecting fake images is of interest to the community, why not detecting fake graphs instead\"?\n\nIf the idea of a new task is indeed the crux of the contribution, I would recommend this paper to be accepted as a short letter, an extended abstract, or a poster, not as a full research paper.", "strength_and_weaknesses": "Strengths:\n- Experimental results provide some practical insights on the performance of different ML approaches for the target task\n- Authors explore 4 scenarios of increasing complexity, which provides a valuable comparison on how the models perform under ideal circumstances vs. more realistic circumstances.\n\nWeaknesses:\n- Unclear significance and relevance of the addressed problem. The authors' argument is that they are preemptively studying a problem that may become relevant in the future. It is challenging to assess significance at this moment. It is also challenging to assess whether the performance obtained by the models would be good or not in practice for this hypothetical task. Having a case study would help justify the authors' claims of significance.\n- No novelty. The evaluation and data generation is performed using existing methods.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject