Year: 2021

Abstract:
Data augmentation has been widely used in image data and linguistic data but remains under-explored for Graph Neural Networks (GNNs). Existing methods focus on augmenting the graph data from a global perspective and largely fall into two genres: structural manipulation and adversarial training with feature noise injection. However, recent graph data augmentation methods ignore the importance of local information for the GNNs’ message passing mechanism. In this work, we introduce the local augmentation, which enhances the locality of node representations by their subgraph structures. Specifically, we model the data augmentation as a feature generation process. Given a node’s features, our local augmentation approach learns the conditional distribution of its neighbors’ features and generates more neighbors’ features to boost the performance of downstream tasks. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner. Extensive experiments and analyses show that local augmentation consistently yields performance improvement for various GNN architectures across a diverse set of benchmarks.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs) and their variants (Abu-El-Haija et al., 2019; Kipf & Welling, 2017; Veličković et al., 2018) have achieved state-of-the-art performance for many tasks on graphs such as recommendation system (Ying et al., 2018) and traffic prediction (Guo et al., 2019). However, most of the GNN models, such as GCN (Kipf & Welling, 2017) and GAT (Veličković et al., 2018), learn the node representations by aggregating information over only the 2-hop neighborhood. Such shallow architectures limit their ability to extract information from higher-layer neighborhoods (Wang & Derr, 2021). But deep GNNs are prone to over-smoothing (Li et al., 2018), which suggests the node representations tend to converge to a certain vector and thus become indistinguishable. One solution to address this problem is to preserve the locality of node representations when increasing the number of layers. For example, JKNet (Xu et al., 2018) densely connects (Huang et al., 2017) each hidden layer to the final layer. GCNII (Chen et al., 2020) employs an initial residual to construct a skip connection from the input layer. Besides, Zeng et al. (2021) pointed out that the key for GNN is to smooth the local neighborhood into informative representation, no matter how deep it is. And they decouple the depth and scope of GNNs to help capture local graph structure. Prior works have emphasized the importance of local information, but one property of the graph is that the number of nodes in the local neighborhood is far fewer than higher-order neighbors. And this property limits the expressive power of GNNs due to the limited neighbors in the local structure. A very intuitive idea is to use data augmentation to increase the number of nodes in the local substructure.
However, existing graph data augmentation methods ignore the importance of local information and only perturb at the topology-level and feature-level from a global perspective, which can be divided into two categories: topology-level augmentation (Rong et al., 2020; Wang et al., 2020b; Zhao et al., 2021) and feature-level augmentation (Deng et al., 2019; Feng et al., 2019; Kong et al., 2020). Topology-level augmentation perturbs the adjacency matrix, yielding different graph structures. On the other hand, existing feature-level augmentation mainly exploits perturbation of node attributes guided by adversarial training (Deng et al., 2019; Feng et al., 2019; Kong et al., 2020). These augmentation techniques have two drawbacks. 1) Some of they employ full-batch training for augmentation, which is computationally expensive, and introduce some additional side effects such
as over-smoothing. 2) The type of feature-level augmentation is coarse-grained, which focuses on global augmentation and overlooks the local information of the neighborhood. Moreover, to our best knowledge, none of the existing approaches combines both the feature representations and the graph topology, especially the local subgraph structures, for graph-level data augmentation.
In this work, we propose a framework: Local Augmentation for Graph Neural Networks (LA-GNNs), to further enhance the locality of node representations based on both the topology-level and featurelevel information in the substructure. The term "local augmentation" refers to the generation of neighborhood features via a generative model conditioned on local structures and node features. Specifically, our proposed framework learns the conditional distribution of the connected neighbors’ representations given the representation of the central node, bearing some similarities with the Skipgram (Mikolov et al., 2013) and Deepwalk Perozzi et al. (2014), with the difference that our method does not base on word or graph embedding.
The motivation behind this work concludes three-fold. 1) Existing feature-level augmentation works primarily pay attention to global augmentation without considering the informative neighborhood. 2) The distributions of the representations of the neighbors are closely connected to the central node, making ample room for feature augmentation. 3) Preserving the locality of node representations is key to avoiding over-smoothing (Xu et al., 2018; Klicpera et al., 2019; Chen et al., 2020). And there are several benefits in applying local augmentation for the GNN training. First, local augmentation is essentially a data augmentation technique that can improve the generalization of the GNN models and prevent over-fitting. Second, we can recover some missing contextual information of the local neighborhood in an attributed graph via the generative model (Jia & Benson, 2020). Third, our proposed framework is flexible and can be applied to various popular backbone networks such as GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), GCNII (Chen et al., 2020), and GRAND (Feng et al., 2020) to enhance their performance. Extensive experimental results demonstrate that our proposed framework could improve the performance of GNN variants on 7 benchmark datasets.

heading: 2 BACKGROUND
text: Notations. Let G = (V,E) represent the graph, where V is the set of vertices {v1, · · · , vN} with |V | = N and E is the set of edges. The adjacency matrix is defined as A ∈ {0, 1}N×N , and Aij = 1 if and only if (vi, vj) ∈ E. Let Ni = {vj |Aij = 1} denotes the neighborhood of node vi and D denote the diagonal degree matrix, where Dii = ∑n j=1 Aij . The feature matrix is denoted as X ∈ RN×F where each node v is associated with a F -dimensional feature vector Xv. Y ∈ {0, 1}N×C denote the one-hot label matrix, where Yi ∈ {0, 1}C is a one-hot vector and∑C
j=1 Yij = 1 for any vi ∈ V .
GNN. Graph Neural Network (GNN) is a type of neural network that directly operates on the graph structure, such as GCN and GAT (Kipf & Welling, 2017; Veličković et al., 2018), that capture the dependence of graphs via message passing between the nodes of a graph as
H(`) = f(A,H(`−1)), (1)
where f denotes the specific GNN layer for different models, H(`) are the hidden vectors of the `-th layer and H(0) = X. For example, f(A,H) = σ(ÂHW) for GCN, where Â = D̃− 1 2 ÃD̃− 1 2 , D̃ is
the degree matrix of Ã, i.e., D̃ii = ∑ j Ãij , and Ã = A+ I.
Topology-level Augmentation. Topology-level augmentation usually perturbs A to generate different graph structures, which can be formulated as A′ = F(A,X), where F(·) is a structure perturbation function. For example, DropEdge (Rong et al., 2020) considers F(A,X) = A−As which is independent of X, where As is a sparse matrix consists of a subset of the original edges E. GAUG-O (Zhao et al., 2021) leverages their proposed neural edge predictors to produce a different structure A′ where A′ij = ⌊ 1
1+e−(log Pij+G)/τ + 12
⌋ , Pij = αMij + (1 − α)Aij , M = σ ( ZZT ) ,
Z = f (A, f(A,X)), τ is the temperature of Gumbel-Softmax distribution, G ∼ Gumbel(0, 1) is a Gumbel random variate, and α is a hyperparameter mediating the influence of edge predictor on the original graph.
Feature-level Augmentation. Besides, feature-level augmentation function can be defines as X′ = H(A,X), where H(·) is a feature perturbation function. FLAG (Kong et al., 2020) defines the perturbation function as H(A,X) = X + δ where
perturbation δ is updated iteratively during the adversarial training phase. G-GCN (plain) (Zhu et al., 2020) obtains the global attribute feature matrix X(a) ∈ RN×da through minimizing the objective ∏ v∈V ∏ a∈CA(v)
exp(X(a)v ·Va)∑ k∈U exp ( X (a) v ·Vk ) where U is the set of all attributes, CA(v) is the sampled context attributes of v, and V ∈ Rda×F denotes the parameters. Obviously, the perturbation function of G-GCN has no close-form solution. In this work, we propose a novel feature-level augmentation method, named local augmentation. And the comparison of the details of various graph data augmentation techniques can be found in Table 1.

heading: 3 LOCAL AUGMENTATION
text: In this section, we describe details of the proposed method. The local augmentation framework consists of three modules: learning the conditional distribution via a generative model, the active learning trick, and the downstream GNN models, as illustrated in Figure 1. Note that the proposed algorithm enhances the locality of node representations through augmenting 1-hop neighbors in a generative way. Specifically, we exploit a generative model to learn the conditional distribution of the connected neighbors’ representations given the representation of a node. We describe the details of learning the conditional distribution and the motivation for why local augmentation is able to improve the performance in a probabilistic view in Sec. 3.1, detail the architecture of downstream GNN models in Sec. 3.2. We finally elaborate the training procedure of both the generative model and the downstream GNN models with the active learning trick in Sec. 3.3.

heading: 3.1 LEARNING THE CONDITIONAL DISTRIBUTION
text: We start by reviewing the semi-supervised learning of GNNs in a probabilistic view. Most existing GNN models (Kipf & Welling, 2017; Veličković et al., 2018) are viewed as a classification function to predict the class labels of the graph nodes. In this work, we use a GNN classification estimator Pθ(Y|A,X) (θ is the parameter) to model the conditional distribution of label Y with respect to the graph structure A and feature matrix X. Given training samples {A,X,Y}, the parameter θ can be estimated using Maximum Likelihood Estimation (MLE), by optimizing the following likelihood function:
max ∏ k∈K Pθ (Yk|A,X) , (2)
where K is the set of node indices of the training dataset whose labels are visible during the semi-supervised training. To further boost the performance of GNN, we introduce a new model Pθ(Y,X|A,X), where X is generated features by feature-level augmentation. For this model, the MLE method needs to optimize a marginalized probability Pθ over the generated feature matrix X:
max ∏ k∈K ∫ X Pθ ( Yk,X|A,X ) . (3)
For Bayesian tractability, we decompose Pθ in Eq.(3) as a product of two posterior probabilities:
Pθ,φ(Yk,X|A,X) := Pθ(Yk|A,X,X)Qφ(X|A,X), (4)
where Pθ(Yk|A,X,X) and Qφ(X|A,X) denote the probabilistic distributions approximated by the downstream GNN and the (feature-level augmentation) generator respectively, parameterized by θ and φ. There are two benefits in the decomposition above. First, it allows us to decouple the training of the downstream predictor Pθ and the generator Qφ, enabling the generator to easily generalize to other downstream tasks. Moreover, inspired by the successes of data augmentation via deep-learning-based generative modeling (Antoniou et al., 2017), the representation power of Eq.(4) is superior than that of a single predictor Pθ (Yk|A,X) without data augmentation. Consequently, once a generator Qφ is trained very well, our training procedure can optimize Pθ(Yk|A,X,X) with samples X drawn from the fixed conditional distribution Qφ. Now, we show how to train the generator as follows.
Generator To learn a feature augmentation generator, a naive solution is to learn one single distribution for all the neighbors using the MLE method, i.e., solving the following optimization problem
max ψ ∑ j∈Ni log pψ (Xj |Xi) = max ψ log ∏ j∈Ni pψ (Xj |Xi) , (5)
where {Xj|j∈Ni ,Xi}. Then pψ can be used to augment features for all the neighbors. However, this method ignores the differences between all the neighbors, which may induce severe noise.
To overcome the limitation, we assume that each neighbor satisfies a different conditional distribution. Specifically, there exists a conditional distribution p(·|Xi, zj) with latent random variable zj , such that we have Xj ∼ p(X|Xi, zj) for Xj|j∈Ni . Once we obtain p(·|Xi, zj) in some way, we can generate augmented features X, and then we can train Pθ(Yk|A,X,X) instead of Pθ(Yk|A,X) to improve the final performance of Pθ. Below, we will present how to find p(·|Xi, zj), which will produce the generator Qφ.
To achieve our purpose, a suitable method is the conditional variational auto-encoder (CVAE) (Kingma & Welling, 2013; Sohn et al., 2015), which can help learn the distribution of the latent variable zj , and the conditional distribution p(·|Xi, zj). So, a CVAE model Qφ ( X|A,X ) is adopted as our generator, where φ = {ϕ,ψ}, ϕ denotes the variational parameters and ψ represents the generative parameters. To derive the optimization problem for CVAE, log pψ (Xj |Xi) can be written with latent variables z as follows, following previous work (Pandey & Dukkipati, 2017; Sohn et al., 2015):
log pψ (Xj |Xi) = ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) dz+KL(qϕ(z|Xj ,Xi)‖pψ(z|Xj ,Xi))
≥ ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) dz,
and the evidence lower bound (ELBO) can be written as: L(Xj ,Xi;ψ,ϕ) = −KL(qϕ(z|Xj ,Xi)‖pψ(z|Xi)) + ∫ qϕ(z|Xj ,Xi) log pψ(Xj |Xi, z)dz, (6)
where the encoder qϕ(z|Xj ,Xi) = N (f(Xj ,Xi), g(Xj ,Xi)) and decoder pψ(Xj |Xi, z) = N (h(Xi, z), cI). The encoder is a two-layer MLP. f and g share the first layer, and their second layers employ different parameters. The decoder h is two-layer MLP. For simplicity and tractability, the implemented generator Q ( X|A,X ) uses the same parameters across all nodes vi ∈ V .
Optimization of the MLE Now, we present how to optimize the MLE Eq.(4) using the feature matrix produced from the generator. Once the augmented feature matrix can be sampled from the generator, we can optimize the parameters of Eq.(4) in the following way. Firstly, the parameter φ = {ψ,ϕ} can be optimized by maximizing the ELBO of the generator (6), i.e., we train the generator. Secondly, the parameter θ is optimized by maximizing the MLE Eq.(4) with φ fixed, which is the conditional distribution of Yk given A, X, and X, i.e., we train the downstream GNN model.
In this paper, the MLE is formulated by a downstream GNN model as follows: Pθ ( Yk | A,X,X ) ∝ −L(θ|A,X,X, φ), (7) where L(θ|A,X,X, φ) = − ∑ k∈T ∑C f=1 Ykf ln ( softmax ( GNN(A,X,X) ) kf ) .

heading: 3.2 THE ARCHITECTURE OF LA-GNN
text: We discuss the details of downstream GNN models. And we use GCN, GAT, GCNII, and GRAND as the backbones and test them on semi-supervised node classification tasks. We name the modified GNN architecture as LA-GNN, where LA means local augmentation.
LA-GCN A 2-layer LA-GCN is defined as follows:
H(2) = σ ( Â ( σ ( ÂXW
(1) 1 )∥∥∥∥σ (ÂX1W(1)2 )∥∥∥∥ · · · ∥∥∥∥σ (ÂXnW(1)n+1))W(2)) , (8) where Xi (i = 1, 2, · · · , n) is the augmented feature matrix produced by the generator, ‖ denotes an operator of column-wise concatenation, W(1)i (i = 1, 2, · · · , n) denotes the parameters of the first LA-GCN layer, and W(2) denotes the parameters of the second LA-GCN layer.
LA-GCNII Since GCNII (Chen et al., 2020) applies a fully-connected neural network on X to obtain a lower-dimensional initial representation H(0) before the forward propagation, we apply a fully-connected neural network on X and X to obtain H(0) for LA-GCNII as follows:
H(0) = σ ( XW
(0) 1 )∥∥σ (X1W(0)2 )∥∥ · · · ∥∥σ (XnW(0)n+1) . (9) H(0) is fed into the next forward propagation layer. Besides, we do not modify the architecture of GAT and GRAND, and just add our generated feature matrix to the input.

heading: 3.3 ACTIVE LEARNING
text: In this section, we introduce a trick for the overall training framework. After the training of the generator finishes, it contains an issue of using Qφ(X|A,X) of Eq.(4) for inference because Q may generate some samples from the side part of the distribution. This critical question makes the inferences inefficient. Inspired by Nielsen & Okoniewski (2019), we introduce active learning to capture the suitable generated feature matrix and the corresponding generator, which improves the inference efficiency and helps the optimization of the MLE. During active learning, the probability of each feature is proportional to its uncertainty evaluated by an acquisition function. We adopt the Bayesian Active Learning by Disagreement (BALD) acquisition function (Houlsby et al., 2011) to sample the most important inferences with the approximation from the Monte Carlo (MC) dropout samples as
U(X) ≈ H
[ 1
N N∑ n=1 P ( Yk|X,ωn )] − 1 N N∑ n=1 H [ P ( Yk|X,ωn )] , (10)
where N is the number of MC samples and ωn are the parameters of the network sampled for the n-th MC dropout sample. A high BLAD score indicates a network with high uncertainty about the generated feature matrix. So it tends to be selected to improve the GNN model. Finally, the overall algorithm framework is summarized in Algorithm 1, which shows the optimization of Eq.(4).
Algorithm 1 The framework to train the Generator Qφ and the downstream GNN Pθ using the initial feature matrix X and the generated feature matrix X selected by the acquisition function Input: Adjacency matrix A, feature matrix X 1: Initialize U=-inf, X, Qφ, X ′ , and Q′φ
2: for i = 1 to the number of generator iterations do 3: Train the generator Qφ using A and X 4: Generate feature matrix X using Qφ 5: Compute U(X) using Eq.(10). 6: if U(X) > U then 7: U = U(X) 8: if i > Nwarmup then 9: Train GNN Pθ using A and X for the number of continued GNN training iterations
10: X ′ = X, Q′φ = Qφ 11: X = X ′ , Qφ = Q′φ 12: Train the downstream GNN Pθ with the generated feature matrix X, and generator Qφ

heading: 4 DISCUSSION
text: In this section, we discuss the motivation of this work and provide some analysis.
Connection to EP-B and GraphSAGE We discuss how our proposed model distinguishes from the classical representation learning models on graphs. Previous methods such as EP-B (GarcíaDurán & Niepert, 2017) and GraphSAGE (Hamilton et al., 2017) rely on reconstruction loss function between the central node and its neighbors’ embeddings. EP-B aims to minimize the reconstruction error by optimizing the objective min ∑ u∈V \{v} [ γ + d(X̃v,Xv)− d(X̃v,Xu) ] where Xv repre-
sents the target node; Xu denotes the neighbor nodes; X̃v = AGG(Xl|l ∈ N (v)) indicates the reconstruction from neighbors; and γ refers to the bias. Besides, GraphSAGE exploits the negative sampling to differentiate the representations of remote node-pairs. GraphSAGE enforce nearby nodes to have similar representations and to enforce disparate nodes to be distinct by minimizing the objective min−Eu∼N (v) log ( (σ(XTuXv)) ) −λEvn∼Pn(v) log ( (σ(−XTvnXv)) ) where Xv denotes target node; Xu represents the neighbor node; Xvn is disparate node; and Pn(v) is the negative sampling. These approaches build upon the assumption that adjacent nodes share similar attributes. In contrast, our model does not rely on such assumption and instead generates the neighboring node features from the conditional distribution of central node representations. Given the target node, Xv , our aim is to learn the conditional distribution of the neighbor nodes, Xu. A comparison between the reconstruction-based representation learning on graphs and our proposed framework is illustrated in Figure 2. And our local augmentation method is the third paradigm to exploit neighbors in a generative way.
Local Augmentation vs. General Augmentation General image augmentation algorithms include geometric transformations, feature space augmentation, adversarial training, and generative adversarial networks (Shorten & Khoshgoftaar, 2019). It is impossible to apply geometric transformations directly to graph data augmentation since graphs are sensitive to node permutation. General
adversarial training, feature space augmentation, and generative adversarial networks don’t take the graph structure into account. Graphs consist of a set of identities with certain pairs of these identities connected by edges. We need to consider node features and the graph structure when designing the graph data augmentation framework. Our proposed method of local augmentation fully considers these two points. By extracting the neighbors’ feature vectors, we have enough data points to learn the distribution. There are two benefits to designing local augmentation. First, by taking the sub-graph structure and feature representation associated with this sub-graph structure as input for the generative model, we can learn the information of the sub-graph structure. Second, the number of data points to learn the distribution depends on the node degree. This assures that we have enough data points compared with the general feature augmentation and we can learn a better distribution.
Complementing missing information Jia & Benson (2020) points out that some attribute information might be missing on a subset of vertices. By learning the distribution of node representations from the observed data, we can utilize the produced node representations from the generative model to complement the information missing in the nodes’ attributes, which boosts the robustness of downstream tasks. And we show that our model still works in the scenario that nodes lose a certain percentage of attributes. In other words, we can exploit the well-learned distribution to complement the contextual information of the local neighborhood to enhance the locality of the node representations.
5 EXPERIMENTS
In this section, we evaluate the performance of our proposed model on semisupervised node classification tasks on a variety of public graph datasets and compare our model with the state-of-the-art graph neural networks. We also carry out additional experiments to showcase the necessity of our design and its robustness to missing information.

heading: 5.1 DATASETS
text: We utilize seven public graph datasets (Cora, Citeseer, Pubmed, Squirrel, Actor, Chameleon, and Cornell) for semisupervised node classification tasks. The details of these datasets can be found in the appendix.

heading: 5.2 SEMI-SUPERVISED NODE CLASSIFICATION
text: Baselines and Experimental Setup. We apply the standard fixed splits (Yang et al., 2016) on three datasets Cora, Citeseer, and Pubmed, with 20 nodes per class for training, 500 nodes for validation, and 1,000 nodes for testing. And we consider four backbones: GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), GCNII (Chen et al., 2020), and GRAND (Feng et al., 2020) to evaluate our proposed framework and compare our model against state-of-the-art models including 1) backbone models: Chebyshev (Defferrard et al., 2016), GCN, GAT,
APPNP (Klicpera et al., 2019), Graph U-net (Gao & Ji, 2019), MixHop (Abu-El-Haija et al., 2019), GCNII, GSNN-M (Wang et al., 2020a), S2GC (Zhu & Koniusz, 2021), and GRAND and 2) featurelevel and topology-level augmentation models: G-GNNs (Zhu et al., 2020), DropEdge (Rong et al.,
2020) and GAUG-O (Zhao et al., 2021). For four datasets Squirrel, Actor, Chameleon, and Cornell, we take 10 random splits (Shchur et al., 2018) where 10%, 30%, and 60% of the date for training, validation, testing; measure the performance of GCN, GAT, GCNII, and corresponding modified models.
Results For three datasets Cora, Citeseer, and Pubmed, we report the mean classification accuracy on the test nodes of all our models after 100 runs and report the values after running the experiments of their models with our server under their setting hyperparameters in their original papers. The results of the evaluation experiments are summarized in Tables 2, 3, and in the appendix, which demonstrate that the backbone models equipped with our method achieve the best performance across all the datasets except the Cornell dataset. More specifically, we can improve upon GCN by a margin of 2.5%, 2.2%, and 2.4% on Cora, Citeseer, and Pubmed respectively. Moreover, LA-GNN outperforms other backbone models including GAT and GCNII as well as data augmentation models (Zhu et al., 2020; Rong et al., 2020; Zhao et al., 2021) on these citation network datasets. Besids, we also provide the analysis of the distribution of our generated feature matrix. And Figure 3 shows the distribution of the attributes of the original
and inference neighbors, which can demonstrate our inference feature matrix follow the distribution of the initial feature matrix.
5.3 ABLATION STUDY
In this section, to demonstrate the effectiveness of our proposed generative framework, we conduct experiments that compare LA-GNN to several of its ablated variants without generative modeling. The results are shown in Table 4. "GCN + width" only increases the first network layer width for GCN and GCNII to match LAGNN without giving generated samples as input. "+ concatenation" only replaces the generated feature matrix of LA-GNN with the original feature matrix of the central node. "+ plain neighborhood" replaces the generated feature matrix of LA-GNN with a neighborhood feature matrix where each row corresponds to the feature vector of the randomly sampled neighbor. The
results show that the first two variants provide no notable improvement for the backbone models, and the third variant even results in degradation. By eliminating the possibility that these confounding factors irrelevant to our core approach may contribute to the final performance, it’s evident that the performance gain in Table 2 and 3 are due to our proposed generative local augmentation framework.

heading: 5.4 ROBUSTNESS TO MISSING INFORMATION
text: In this section, we conduct experiments to verify that our proposed framework can robustify downstream tasks against missing information in the feature attributes. Specifically, we mask a certain percentage of the attributes of each feature vector and use the same pipeline to do augmentation for the masked feature matrix. As shown in Table 5, we can see that as the mask ratio increases,
the gap of the performance between the GCN and LA-GCN enlarges in most cases in Cora and Citeseer, which corroborates our insight discussed in Section 4. Since there exists large redundancy in the features of the Pubmed dataset, the performance of GCN and LA-GCN decreases little as the mask ratio increases and the gap of the performance does not enlarge. To conclude, our model can complement the contextual information of the local neighborhood to enhance the locality of the node representations.

heading: 6 RELATED WORK
text: Graph Neural Networks In general, convolution in the graph domain involves non-spectral (spatial) and spectral approaches. Non-spectral methods generalize convolutions operating on spatially close neighbors to the graph domain, such as Duvenaud et al. (2015); Atwood & Towsley (2016); Niepert et al. (2016); Monti et al. (2017). Spectral approaches define the convolution operations based on the spectral formulation, such as Bruna et al. (2014); Defferrard et al. (2016); Kipf & Welling (2017). Recently, several methods (Abu-El-Haija et al., 2019; Liao et al., 2019) based on GCN have been proposed to obtain the higher-order filters. Besides, GAT (Veličković et al., 2018), Graph U-Nets (Gao & Ji, 2019) combine attention networks and pooling operation with GNN separately, which achieve state-of-the-art performance on node and link classification tasks. In this work, local augmentation can be applied on various backbone models to improve performance.
Graph Generative Models Generative models (Goodfellow et al., 2014; Kingma & Welling, 2013) are powerful tools of learning data distribution through unsupervised learning, and they have achieved tremendous success in various applications. Recently, researchers have proposed several interesting generative models for graph data generation. Variational graph auto-encoder (VGAE) (Kipf & Welling, 2016) makes use of latent variables and learns interpretable latent representations for undirected graphs. Salha et al. (2019) replace the GCN encoder in VGAE with a simple linear model and emphasize the effectiveness of a simple node encoding scheme. Xu et al. (2019) propose a generative model framework to learn node representations, by sampling graph generation sequences constructed from observed graph data. ConDgen (Yang et al., 2019) exploits the GCN encoder to handle the inherent challenges of flexible context-structure conditioning and permutation-invariant generation. Besides, some methods have been proposed to apply the graph generative models in various applications such as graph matching (Simonovsky & Komodakis, 2018), molecule design (Liu et al., 2018), retrosynthesis prediction (Shi et al., 2020) and chemical design (Samanta et al., 2018). Compared with these approaches mainly focusing on structure generation, our model takes full use of the power of the generative model for feature representation generation, which can serve as an enhanced technique for the downstream backbone models.

heading: 7 CONCLUSION
text: We propose local augmentation, a brand-new technique that exploits the generative model to learn the conditional distribution of the central node’s neighbors’ feature representations given its representation. We can augment more 1-hop neighbors from a well-trained generative model to enhance the performance of backbone GNN models. Experiments show that our model can improve performance across various GNN architectures and benchmark datasets by enriching local information. Besides, our model achieves new state-of-the-art results on various semi-supervised node classification tasks. One limitation of our proposed framework is that we do not exploit the 2-hop neighbors or use the random walk to find more related neighbors for the central node. And one future work is that we can extract more 2/3-hop neighbors if the central node’s degree is small and learn the conditional distribution for random sampling nodes if the graph is large.

heading: A PROOF OF EQ.(6)
text: We give more details of the derivation of the generator ELBO as follows: log pψ(Xj |Xi) = ∫ qϕ(z|Xj ,Xi) log pψ(Xi|Xi)dz
= ∫ qϕ(z|Xj ,Xi) log pψ(Xj ,Xi)
pψ(Xi) dz
= ∫ qϕ(z|Xj ,Xi) log pψ(Xj ,Xi)pψ(Xi,Xi, z)
pψ(Xi)pψ(Xi,Xi, z) dz
= ∫ qϕ(z|Xi,Xi) log pψ(Xj ,Xi, z)
pψ(Xi)
1 pψ(Xj ,Xi,z) pψ(Xj ,Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) pψ(z|Xj ,Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) pψ(z|Xj ,Xi) qϕ(z|Xj ,Xi) qϕ(z|Xj ,Xi) dz
= ∫ qϕ(z|Xj ,Xi) ( log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) + log qϕ(z|Xj ,Xi) pψ(z|Xj ,Xi)
) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) dz+KL(qϕ(z|Xj ,Xi)||pψ(z|Xj ,Xi))
≥ ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) dz
LELBO = ∫ qϕ(z|Xj ,Xi) log
pψ(Xj , z|Xi) qϕ(z|Xj ,Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj ,Xi, z)
qϕ(z|Xj ,Xi)pψ(Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj |Xi, z)pψ(Xi, z) qϕ(z|Xj ,Xi)pψ(Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(Xj |Xi, z)pψ(z|Xi) qϕ(z|Xj ,Xi) dz
= ∫ qϕ(z|Xj ,Xi) log
pψ(z|Xi) qϕ(z|Xj ,Xi) dz+
∫ qϕ(z|Xj ,Xi) log pψ(Xj |Xi, z)dz
= −KL(qϕ(z|Xj ,Xi)||pψ(z|Xi)) + ∫ qϕ(z|Xj ,Xi) log pψ(Xj |Xi, z)dz

heading: B REPRODUCIBILITY
text: B.1 DATASETS DETAILS
Cora, Citeseer, and Pubmed are standard citation network benchmark datasets Sen et al. (2008). In these datasets, nodes represent documents, and edges denote citations; node feature corresponds to elements of a bag-of-words representation of a document, and node label corresponds to one of the academic topics. Besides, we utilize four datasets used in Pei et al. (2020) for evaluation. Chameleon and squirrel are two page-page networks on specific topics in Wikipedia Rozemberczki et al. (2021). In these datasets, nodes represent web pages, and edges denote mutual links between pages; node features correspond to several informative nouns in the Wikipedia pages and labels correspond to the number of the average monthly traffic of the web page. WebKB1 is a webpage dataset collected from various universities. We use the one subdataset of it, Cornell. In this dataset, nodes represent web pages, and edges are hyperlinks between them; node features correspond to the bag-of-words representation of web pages and labels correspond to five categories, student, project, course, staff, and faculty. Film dataset is the actor-only induced subgraph of the film-directoractor-writer network Tang et al. (2009). In this dataset, Nodes represent actors, and edges denote co-occurrence on the same Wikipedia page; node features correspond to some keywords in the Wikipedia pages and labels correspond to five categories in terms of words of actor’s Wikipedia. All the dataset statistics are summarized in Table 6.
Table 6: Datasets statistics
Dataset Cora Cite. Pubm. Cham. Squi. Actor Corn. # Nodes 2708 3327 19717 2277 5201 7600 183 # Edges 5429 4732 44338 36101 217073 33544 295 # Features 1433 3703 500 2325 2089 931 1703 # Classes 7 6 3 5 5 5 5
B.2 IMPLEMENTATION DETAILS
We use Pytorch (Paszke et al., 2019) to implement LA-GNNs. The codes of S2GC (Zhu & Koniusz, 2021), LA-GCN, LA-GAT, LA-GCNII, LA-GRAND, and DropEdge-GCN are implemented referring to Pytorch implementation of S2GC2, GCN3 (Kipf & Welling, 2017), GAT4 (Veličković et al., 2018), GCNII5 (Chen et al., 2020) GRAND6 (Feng et al., 2020), and DropEdge-GCN7 (Rong et al., 2020). Besides, we implement APPNP (Klicpera et al., 2019) with DGL (Wang et al., 2019) version of APPNP8. The datasets Cora, Citeseer, Pubmed are downloaded from TensorFlow (Abadi et al., 2016) implementation of GCN9, and the datasets Chameleon, Squirrel, Actor, and Cornell are downloaded from the implementation of Geom-GCN10(Pei et al., 2020). All the experiments in this work are conducted on a single NVIDIA Tesla V100 with 32GB memory size. The operating system behind the Docker where the experiments are running is Red Hat 4.8.2-16. And the software that we use for experiments are Python 3.6.8, numpy 1.19.2, sklearn 0.0, scipy 1.5.4, networkx 2.5.1, torch 1.6.0, torchvision 0.7.0, CUDA 10.2.89, and CUDNN 8.0.2.
1http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb 2https://github.com/allenhaozhu/SSGC 3https://github.com/tkipf/pygcn 4https://github.com/Diego999/pyGAT 5https://github.com/chennnM/GCNII 6https://github.com/THUDM/GRAND 7https://github.com/DropEdge/DropEdge 8https://github.com/dmlc/dgl/tree/master/examples/pytorch/appnp 9https://github.com/tkipf/gcn/tree/master/gcn/data
10https://github.com/graphdml-uiuc-jlu/geom-gcn/tree/master/new_data
B.3 HYPERPARAMETER DETAILS
LA-GNNs introduce an additional parameter, that is the hidden layer for generated feature matrix X before concatenation. The difference of architectures between GCN and LA-GCN can be found in Figure 4, and the LA-GCNII architecture can be found in Figure 5.
The difference of hyperparameters between the GCN and LA-GCN is only the hidden layer size before concatenation. For the LA-GCNII, LA-GAT, LA-GRAND, we tune the hyperparameters in the same way as described in their original papers with validation set.

Review summaries:
This paper presents a data augmentation methods for training graph neural networks in general. They firstly fit a generative model that learns the conditional probability of input node features. The training data are then augmented using the generative model using the proposed importance sampling method and used for training GNNs. The proposed methods were evaluated on 7 public graph benchmark datasets. Authors attempted to show that the proposed augmentation methods could improve the benchmark classification accuracy over the baseline methods.

This paper studies the problem of feature augmentation for training the graph neural networks. Specifically, given the central nodes features and local structure, the proposed approach estimates the distribution of the node features of neighbors. Experimental results show that the proposed approach can further improve the baseline backbones.

Data augmentation remains under-explored on graph-structured data. In this work, the authors introduce local augmentation that enhances the feature of each node by its local subgraph structure. Specifically, they model the data augmentation as a feature generation process: given a node’s feature, they learn the conditional distribution of its neighbors’ features to make a generative augmentation model. Experiments show that the proposed local augmentation makes performance improvement on real-world data.