Year: 2020

Abstract:
Graph convolutional networks (GCN) achieved superior performances in graphbased semi-supervised learning (SSL) tasks. Generative adversarial networks (GAN) also show the ability to increase the performance in SSL. However, there is still no good way to combine the GAN and GCN in graph-based SSL tasks. In this work, we present GraphCGAN, a novel framework to incorporate adversarial learning with convolution-based graph neural network, to operate on graphstructured data. In GraphCGAN, we show that generator can generate topology structure and attributes/features of fake nodes jointly and boost the performance of convolution-based graph neural network classifier. In a number of experiments on benchmark datasets, we show that the proposed GraphCGAN outperforms the reference methods by a significant margin.

heading: 1 INTRODUCTION
text: Graph-based semi-supervised learning (SSL) aims to classify nodes in graph, where only small amounts of nodes are labeled due to the expensive and time-consuming label collection process. To solve such task, various graph neural networks (GNNs) have been proposed using the idea of convolutional neural networks (CNN) to implicitly propagate the information of labeled nodes to unlabeled nodes through the linkage between nodes (Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017). These convolution-based graph neural networks have achieved superior performance on multiple benchmark datasets in graph-based SSL tasks (Wu et al., 2019).
Recently, generative adversarial networks (GANs) (Goodfellow et al., 2014) have been shown a power in improving the performance of image-based SSL problems (Odena, 2016; Salimans et al., 2016; Li et al., 2019b). In semi-GAN (Salimans et al., 2016), authors converted the M -class classification task into solving (M + 1)-class problem where the synthetic (M + 1)th class is generated by the GAN’s generator. Later on, Dai et al. provided a theoretical insight that the generated data are able to boost the performance of classifier under certain assumptions. Our work is motivated by the the semi-GAN.
GraphSGAN (Ding et al., 2018) first investigated the adversarial learning over graph, where the graph is embedding into an embedding space and synthetic data are generated in the corresponding space. The multi-layer perceptron (MLP) is trained as the classifier on the embedding vectors. However, to our knowledge, there is still no existed method to combine the adversarial learning to convolution-based GNNs on graph-based SSL task. In this work, we explore the potential of incorporating the convolution-based GNN and GAN. The challenges of constructing a general framework have three folds: first, the attributed graph data are non-Euclidean whose distribution contains information of graph topology structure as well as the attributes of nodes. Hence, it is not trivial to construct generator to model the distribution. Second, even the generator can model the graph’s distribution, the generator should be trained properly to boost the performance of the classifier. A poor-quality generator would introduce noise to the existed graph and affect the classifier. Third, many variants of GCN have been proposed continuously. The framework should be built with flexibility to adapt to different convolution-based GNNs.
We construct a novel approach called GraphCGAN to deal with above challenges. First, to model the distribution of graph, the generator is built sequentially from two sub-generators: one models
the attribute information (node’s attribute) and another one models the graph topology structure (adjacency relation of node). Details can be found in Section 3.1. Second, in GraphCGAN, the generator is trained based on the feature matching technique (Salimans et al., 2016) which minimizes the distance between generated nodes and real nodes in the constructed feature space. This technique showed a good performance in SSL tasks in practice. The details for construction of loss functions can be found in Section 3.3. For GCN, the attributes of nodes are aggregated convolutionally by multiple layers. The representation of the last layer is usually considered as the prediction for the labels. For variants of GCN, the main differences exist in the strategy of layer aggregation (Hamilton et al., 2017). In our framework, we choose the second to the last layer of convolution-based GNN as the feature matching functions. Therefore, our framework is easily extended to variants of GCN. More discussions can be found in Section 3.2.

heading: 2 PRELIMINARY
text: We first introduce the notation about graph. Let G = (V,E) denote a graph, where V is the set of nodes with |V | = n and E ⊂ V × V is a set of edges with |E| = m. The adjacency matrix A ∈ R|V |×|V | is defined as Aij = 1 if node vi and vj has edge, otherwise Aij = 0. Suppose each node vi has a d-dimensional feature xi ∈ Rd and a single value label yi ∈ {1, 2, ..,M}. In the semi-supervised learning setting, there is a disjoint partition for the nodes, V = V L ∪ V U , such that, for vi ∈ V L, the corresponding label is known and for vj ∈ V U the corresponding label is unknown. The distributions of node in labeled set V L and unlabeled set V U are denoted as pV L and pV U , respectively. The semi-supervised learning is to learn the label for unlabeled set {yj |vj ∈ V U} given adjacency matrix A, feature matrix X = [xi]vi∈V and labels for labeled sets {yi|vi ∈ V L}.

heading: 2.1 CONVOLUTION BASED GRAPH NEURAL NETWORK CLASSIFIER
text: Based on the Laplacian smoothing, the convolution-based GNN models propagate the information of nodes features across the nodes’ neighbors in each layer. Specifically, in GCN, the layer-wise propagation rule can be defined as follows:
H(l+1) = σ(D−1AH(l)W(l) + b(l)), l = 0, 1, 2.., L− 1 (1)
where W(l) and b(l) are layer-specific trainable weight matrix and bias, respectively. σ(·) is an activation function. D is the diagonal degree matrix with Dii = ∑ j Aij . Hence, D
−1A represents normalization of adjacency matrix A. The initial layer H(0) is the feature matrix X. The final layer H(L) followed by a softmax layer can be viewed as the prediction of one-hot representation for the true label y.
Recently, many variants of the GCN layer-wise propagation rule had been proposed, including graph attention network, cluster GCN (Veličković et al., 2017; Chiang et al., 2019), which achieved stateof-the-art performances in many benchmark datasets.

heading: 2.2 GENERATIVE ADVERSARIAL NETWORK BASED SEMI-SUPERVISED LEARNING
text: In semi-GAN, the classifier C and generator G play a non-cooperative game, where classifier aims to classify the unlabeled data as well as distinguish the generated data from real data; generator attempts to match feature of real data and that of generated data. Therefore, the objective function for classifier can be divided into two parts (Salimans et al., 2016). The first part is the supervised loss function Lsup = Ev,y∼pV L logPC(y|v, y ≤M) which is the log probability of the node label given the real nodes. The second part is the unsupervised loss function
Lun−sup = Ev∼pV U logPC(y ≤M |v) + Ev∼pV G logPC(y =M + 1|v) which is the sum of log probability of the first M classes for real nodes and the log probability of the (M + 1)th class for generated nodes V G. The classifier C can be trained by maximize the objective function
LC = Lsup + Lun−sup. (2)
For objective function of generator, Salimans et al. (2016) found minimizing feature matching loss in Equation 3 achieved superior performance in practice
LG = ||Ev∼pV U (f(v))− Ez∼pz(z)(f(G(z)))|| 2 2, (3)
where the feature matching function f(·) maps the input into a feature space and z ∼ pz(z) is drawn from a given distribution like uniform distribution. Furthermore, Dai et al. (2017) provided a theoretical justification that complementary generator G was able to boost the performance of classifier C in SSL task.

heading: 3 FRAMEWORK OF GRAPHCGAN
text: To combine the aforementioned Laplacian smoothing on graph and semi-GAN on SSL together, we develop GraphCGAN model, using generated nodes to boost the performance of convolution-based GNN models.

heading: 3.1 CONSTRUCTION OF GENERATOR FOR GRAPHCGAN
text: The generator G generates fake node v0 by generating feature vector x0 ∈ Rd and adjacency relation a0 ∈ Rn jointly, where a0,i = 1 if the fake node is connected to real node vi, otherwise a0,i = 0. Therefore, the distribution for generated node pG(v0) can be expressed by the joint distribution of the corresponding feature and adjacency relation pG(x0,a0). From the conditional distribution formula, the joint distribution can be written as pG(x0,a0) = pG1(x0)pG2(a0|x0). We use sub-generators G1 and G2 to generate fake feature x0 and a0|x0, respectively. In practice, a0|x0 can be modeled by G2(z;x0) = G2(z;G1(z)) where the adjacency relation a0 is constructed by sub-generator G2 given the input of x0. The distribution of generated node can be denoted by
pG(v0) = pG(x0,a0) = pG(x0)p(a0|x0) = p(G1(z))p(G2(z;G1(z))) =: p(G(z)). (4)
If B nodes (v0,1, v0,2, .., v0,B) are generated, the generated feature matrix is denoted as X0 = (xT0,1,x T 0,2, ..,x T 0,B) T and generated adjacency matrix has form A0 = (aT0,1,a T 0,2, ..,a T 0,B)
T . Hence, the combined adjacency matrix can be denoted as
Ã = [ A AT0 A0 IB ] ∈ R(n+B)×(n+B), (5)
The combined feature vector is
X̃ = [ X X0 ] ∈ R(n+B)×d. (6)
The diagonal degree matrix D̃ ∈ R(n+B)×(n+B) can be denoted as [ D∗ 0 0 DB ] where D∗ ∈ Rn×n
with D∗,ii = ∑ j Aij + ∑ bA0,bi and DB ∈ RB×B with DB,bb = ∑ j A0,bj + 1.

heading: 3.2 ANALYSIS OF CLASSIFIER FOR GRAPHCGAN
text: In GraphCGAN, we adopt the convolution-based GNN, such as GCN, GraphSage (Hamilton et al., 2017) or GAT (Veličković et al., 2017), as the the classifier. The classifier is applied to the enlarged graph G̃ = [X̃, Ã] to obtain the prediction ỹ of nodes V ∪ V G.
Specially, considering the layer-wise propagation of GCN (Equation 1) as the classifier in GraphCGAN, the propogation rule can be denoted as
H̃(l+1) = σ(D̃−1ÃH̃(l)W(l) + b̃(l))
= σ( [ D−1∗ 0 0 D−1B ] [ A AT0 A0 IB ] [ H (l) ∗ H (l) 0 ] W(l) + [ b(l) b (l) B ] )
= σ(
[ D−1∗ AH (l) ∗ +D −1 ∗ A T 0 H (l) 0
D−1B A0H (l) ∗ +D −1 B H (l) 0
] W(l) + [ b(l)
b (l) B
] )
= σ(
[ D−1∗ AH (l) ∗ W (l) + b (l) ∗
(D−1B A0H (l) ∗ +D −1 B W (l))W(l) + b (l) B
] )
=:
[ H (l+1) ∗
H (l+1) 0
] .
(7)
where the first layer is chosen as the enlarged feature matrix H̃(0) = X̃. Weight matrix W(l) has the same in Equation 1. Bias vector b̃(l) has dimension (n+B) which is denoted as [b(l)T ,b(l)TB ]
T . We denote b(l)∗ = D−1∗ A T 0 H (l) ∗ W
(l) + b(l) to make the format clear. From Equation 7, the layer propagation of real nodes (first n rows) follows the same format as the GCN layer propagation in Equation 1. As a special case, for the zero generator A0 = 0 or X0 = 0, the performance of classifier on V ∪ V G would be the same as that of original classifier on V .
For the last layer H̃(L) ∈ R(n+B)×M , we adopt the strategy in Salimans et al. (2016) to obtain the (M + 1) class label ỹ by
ỹ = softmax(H̃(L)||0(n+B)×1), (8)
where || denotes concatenation and 0(n+B)×1 ∈ R(n+B)×1 is a zero matrix. The loss function for classifier in GraphCGAN follows the same format in Equation 2.

heading: 3.3 LOSS FUNCTIONS
text: Let us denote g(·, ·; θC) as the map from feature vector and adjacency vector to the space of second to the last layer in convolution-based GNN with trainable parameter θC . Specially, in the case of GCN, for node vi with feature vector xi and adjacency vector ai,
g(xi,ai; θC) = H̃ (L−1) i , (9)
where H̃(L−1)i denotes the i-th row of H̃ (L−1) and θC = [W(l); b̃(l)]l=0,1,..,L−2.
According to Equation 4, the loss function of generatorG can be decomposed into two parts: the loss functions of sub-generators G1 and G2 separately. To construct G1, the feature matching function f in Equation 3 should solely depend on feature vector. Therefore, we mask the adjacency matrix Ã as identity matrix Ĩ ∈ R(n+B)×(n+B) in layer propagation. Formally, the feature matching loss function of G1 is constructed as
LG1 = ||Exi(g(xi, Ii; θC))− Ez∼pz(z)(g(G1(z),0; θC))|| 2 2,
where Ii denote the i-th row of identity matrix I ∈ Rn×n and 0 is the zero vector. After x0 = G1(z) is built, the feature matching loss function of G2 can be constructed similarly from
LG2 = ||Eai(g(xi,ai; θC))− Ez∼pz(z)(g(x0, G2(z); θC))|| 2 2.
Therefore, loss function for G can be written as
LG = LG1 + LG2 . (10)
Furthermore, when multiple fake nodes are generated, Salimans et al. (2016) showed that adding pull-away item to loss function can increase the entropy of generator which led to better performance
in practice. The pull-away loss for sub-generators G1, G2 can be denoted as
LptG1 = 1
B(B − 1) B∑ i ∑ j 6=i ( g(G1(zi),0; θC) Tg(G1(zj)),0; θC) ||g(G1(zi)),0; θC)||||g(G1(zj)),0; θC)|| )
and
LptG2 = 1
B(B − 1) B∑ i ∑ j 6=i ( g(x0,i, G2(zi); θC) Tg(x0,j , G2(zj); θC) ||g(x0,i, G2(zi); θC)||||g(x0,j , G2(zj); θC)|| ).
The loss function for G with pull-away item can be written as
L∗G = LG + L pt G1 + LptG2 . (11) Besides, Dai et al. (2017) constructed the complementary loss by
LcG1 = Ex∼pG1 log(p(x))I(p(x) > ε), L c G2 = Ea∼pG2 log(p(a))I(p(a) > ε),
which could also increase performance. Therefore, the loss function for G with complementary loss can be written as
L∗∗G = L∗G + LcG1 + L c G2 . (12)
The procedure is formally presented in Algorithm 1.
Algorithm 1: GraphCGAN Algorithm Input: Adjacency matrix A, Node feature X, initialized fake nodes V G = [A0,X0].
hyper-parameters including dimension of the noise vector dnoise, the number of steps KD, and the size of fake nodes B and early stop error.
Output: Prediction Ỹ 1 while not early stop do 2 Combine the fake nodes V G to the graph and obtain Ã and X̃ from Equation 5 and Equation 6; 3 Classifier: 4 iterD = 0 5 while iterD < KD do 6 Use convolution-based GNN as the classifier C, and extract the map to the intermediate layer g(., .) as Equation 9; 7 Train C by minimizing LC (Equation 2) on combined graph, obtain predicted result Ỹ; iterD = iterD + 1; 8 Generator: 9 Generate a random noise vector Z ∼ U(0, I) ∈ RB×dnoise ;
10 Train generator G = [G1;G2] by minimizing Equation 10 or Equation 11 or Equation 12; 11 Obtain X0 = G1(Z) and A0 = G2(Z;G1(Z)).

heading: 4 RELATED WORK

heading: 4.1 GRAPH-BASED SEMI-SUPERVISED LEARNING
text: The challenge for graph-based SSL is to leverage unlabeled data to improve performance in classification. There are three categories of the Graph-based semi-supervised learning. The first one is the Laplacian regularization-based methods (Xiaojin & Zoubin, 2002; Lu & Getoor, 2003; Belkin et al., 2006). The second type is the embedding-based methods, including DeepWalk (Perozzi et al., 2014), SemiEmb (Weston et al., 2012), and Planetoid (Yang et al., 2016). The third type is convolutional based graph neural networks such as GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), ClusterGCN (Chiang et al., 2019) and DeepGCN (Li et al., 2019a). Such methods address the semi-supervised learning in an end-to-end manner. Convolution-based methods perform the graph convolution by taking the weighted average of a node’s neighborhood information. In many graph semi-supervised learning tasks, the convolution-based methods achieved the state-of-the-art performance (Wu et al., 2019).

heading: 4.2 GNN LEARNING WITH GAN
text: GAN is wildly used in obtaining generative graph models. GraphGAN (Wang et al., 2018) proposed a framework for graph embedding task. Specifically, GraphGAN can generate the link relation for a center node. However, GraphGAN cannot be applied to attributed graph.
MolGAN (De Cao & Kipf, 2018) proposed a framework for generating the attributed graph of molecule by generating the adjacency matrix and feature matrix independently. After that, MolGAN used an the score for the generated molecule as reward function to choose the reasonable combination of attributes and topology structure by an auxiliary reinforcement learning model. In comparison, GraphCGAN can generate attributes and adjacency matrix of the attributed graph jointly, which can capture the correlation between the attributes and topology relation.
DGI (Veličković et al., 2018) proposed a general approach for learning node representations within graph-structured data in an unsupervised manner. For the generator, In DGI, the fake nodes are created from a pre-specified corruption function applied on the original nodes. In contrast, our GraphCGAN can generate the fake nodes from a dynamic generator during the training GAN process. For the classifier, the DGI uses GCN only, however, our GraphCGAN is flexible and adaptive to other convolution-based GNN models.

heading: 4.3 GAN WITH SEMI-SUPERVISED LEARNING
text: SGAN (Odena, 2016) first introduced the adversarial learning to the semi-supervised learning on image classification task. GAN-FM (Salimans et al., 2016) stabilized training process in SGAN by introducing feature-matching and minibatch techniques. In Kumar et al. (2017), authors discuss about the effects of adding fake samples and claimed that moderate fake samples could improve the performance in image classification task.
GraphSGAN Ding et al. (2018) proposed a framework for graph Laplacian regularization based classifier with GAN to solve graph-based semi-supervised learning tasks. In GraphSGAN, fake samples in the feature space of hidden layer are generated, hence it can not be applied to convolutional based classifiers. In constrast, our model generates fake nodes directly and is adaptive to convolutional based classifiers.

heading: 5 EXPERIMENTS
text: In this section, our primary goal is to show that the adversary learning can boost the performance of convolution-based GNNs in graph-based SSL under our framework. We evaluate GraphCGAN on established graph-based benchmark tasks against baseline convolution-based GNN models and some other related methods. We first introduce the dataset, experiment setup and results. Besides, we study the property of the generated nodes from our model during the training process. The ablation study is also provided in this section. The code GraphCGAN-ICLR.zip is provided as the supplementary file.

heading: 5.1 DATASETS
text: Three standard citation network benchmark datasets - Cora, Citeseer and Pubmed (Sen et al., 2008) are analyzed. We closely follow the setting in Kipf & Welling (2016) and Veličković et al. (2017) which allows for only 20 nodes per class to be used for training. The predictive power of the trained models is evaluated on 1000 test nodes, and 500 additional nodes are used for validation purposes.

heading: 5.2 EXPERIMENT SETUP AND RESULT
text: Two widely used of convolution-based GNNs, GCN and GAT, are considered as classifiers in GraphCGAN. In order to show the generated nodes can help improve the performance of the methods. We adopt the same model setting in the original papers (Kipf & Welling, 2016; Veličković et al., 2017). Specially, for classifier in GraphCGAN-GCN, the number of layers L is 2, the dimension of the hidden layer is 16, the dropout rate is 0.5, activation function in the hidden layer is Relu. For GraphCGAN-GAT, the number of layers L is 2, the dimension of the hidden layer is 8, and number
of attention heads is 8, the dropout rate is 0.6, activation function in the hidden layer is Sigmoid. The hyper-parameter for the weight of L2 regularization is 5e-4. For the generator, we use the loss function in Equation 12 (Ablation study for loss function of generator can be found in Table 2 Appendix A). In Cora and Citeseer, we generate B = 64 fake nodes. In Pubmed, the number of fake nodes is B = 256. The ablation study of size of fake nodes are provided in Figure 1.
The results is presented in Table 1, the best and the second best results are masked in bold font. We particularly note that both GraphCGAN-GCN and GraphCGAN-GAT outperform GCN and GAT in a significant margin, respectively. More specifically, we are able to improve upon GCN by a margin of 0.9%, 2.3% and 0.9% on Cora, Citeseer and Pubmed, respectively. Besides, GraphCGAN-GAT can improve upon GAT by a margin of 1.0%, 0.7% and 1.7%, suggesting that the adding fake nodes strategy in our GraphCGAN model can boost the performance for reference convolution-based GNN model. To be noticed that GraphCGAN can be easily extended to other convolution-based GNN models.

heading: 5.3 VISUALIZATION OF GAN PROCESS
text: In this subsection, we investigate about the distribution of the generated nodes during the training process. We consider three datasets to illustrate generated nodes in different perspectives. For Karate club graph (Zachary, 1977), it contains 34 nodes without features. The feature matrix X̃ is set as identity matrix during the training process. Therefore, the plot (first row in Figure 2) of fake nodes shows the distribution of G2(z; I). It can be found, after training, fake nodes mainly connect to the boundary nodes1 which is preferred as discussed in GraphSGAN (Ding et al., 2018). MNIST datasets (LeCun et al., 1998) contain the images of handwritten digit. We can consider it as a graph
1Boundary nodes are nodes connected to different clusters
with image feature by constructing an identity adjacency matrix Ã = Ĩ. Therefore, the plot (second row in Figure 2) of fake feature shows the distribution of G1(z) which has the shape around to digit eight. Last, we generated B = 256 nodes for Cora dataset which are plotted in two-dimension by T-SHN (Van Der Maaten, 2014) techniques on the feature space of g(·, ·; θC) shown in the third row in Figure 2, which can be considered as the distribution for G(z). We can find the generated nodes present as a complementary part for the existed nodes

heading: 6 CONCLUSION
text: We propose GraphCGAN, a novel framework to improve the convolution-based GNN using GAN. In GraphCGAN, we design a generator to generate attributed graph, which is able to generate adjacency matrix and feature jointly. We also provide a new insight for the semi-supervised learning with convoluntional graph neural network under GAN structure. A flexible algorithm is proposed, which can be easily extended to other sophisticated architecture of GraphC, such as GAAN (Zhang et al., 2018) and GIN (Xu et al., 2018).
One potential future direction is to extend the GraphCGAN in other relevant tasks including community detection, co-embedding of attributed network (Meng et al., 2019) and even graph classification. Extending the model to incorporate edge features by generating the fake edge will allow us to tackle a larger amount of problems. Finally, in GAN, the stability of training process can be studied.

heading: A ABLATION STUDY FOR LOSS FUNCTION OF GENERATOR

Review summaries:
The paper presents a method to combine graph convolutional neural networks (GCNs) with generative adversarial networks (GANs). The authors focus on the problem of semi-supervised learning on graphs and propose an end-to-end framework in which the generative model is followed by direct convolutions on the graph nodes. Experiments are conducted on standard benchmark datasets and the proposed method, GraphCGAN is compared against several state-of-the-art approaches.