Metropolis-Hastings Data Augmentation for Graph Neural Networks
Year: 2021

Abstract:
Graph Neural Networks (GNNs) often suffer from weak-generalization due to sparsely labeled data despite their promising results on various graph-based tasks. Data augmentation is a prevalent remedy to improve the generalization ability of models in many domains. However, due to the non-Euclidean nature of data space and the dependencies between samples, designing effective augmentation on graphs is challenging. In this paper, we propose a novel framework Metropolis-Hastings Data Augmentation (MH-Aug) that draws augmented graphs from an explicit target distribution for semi-supervised learning. MH-Aug produces a sequence of augmented graphs from the target distribution enables flexible control of the strength and diversity of augmentation. Since the direct sampling from the complex target distribution is challenging, we adopt the Metropolis-Hastings algorithm to obtain the augmented samples. We also propose a simple and effective semi-supervised learning strategy with generated samples from MH-Aug. Our extensive experiments demonstrate that MH-Aug can generate a sequence of samples according to the target distribution to significantly improve the performance of GNNs.

heading: 1 Introduction
text: Graph Neural Networks (GNNs) [1] have been widely used for representation learning on graphstructured data due to their superior performance in various applications such as node classification [2– 4], link prediction [5–7] and graph classification [8, 9]. They have been proven effective by achieving impressive performance for diverse datasets such as social networks [10], citation networks [4], physics [11], molecules [12], and knowledge graphs [10]. However, GNNs often suffer from weakgeneralization due to their small and sparsely labeled graph datasets. One prevalent remedy to address the problem is data augmentation. Data augmentation increases the diversity of data and improves the generalization power of machine learning models trained on randomly augmented samples. It is widely used to enhance the generalization ability of models in many domains. For instance, in image recognition, advanced methods like [13–15] as well as simple transformations such as random cropping, cutout, Gaussian noise, or blurring have been used to achieve competitive performance.
However, unlike image recognition, designing effective and label-preserving data augmentation for individual samples on graphs is challenging due to their non-Euclidean nature and the dependencies between data samples. In image recognition, it is straightforward to identify operations that preserve labels. For instance, human can verify that rotation, translation, and small color jittering do not change the labels in image classification. In contrast, graphs are less interpretable and it is non-trivial
∗First two authors have equal contribution †is the corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for even human to check whether the augmented samples belong to the original class or not. In addition, due to the dependencies between nodes and edges in a graph, it is hard to control the degree of augmentation for individual samples. For instance, a simple operation on a graph, e.g., dropping a node, may result in a completely different degree of augmentation depending on the graph structure. If a hub node is removed, the single perturbation affects a substantial amount of other nodes, which are data samples in node classification. To address these challenges, learning-based data augmentation methods for graphs have been proposed. AdaEdge [16] optimizes the graph topology based on the model prediction. [17] proposes GAug-M and GAug-O that generate augmented graphs via a differentiable edge predictor. GraphMix [18] presents interpolation-based regularization by jointly train a fully connected network and graph neural networks. However, they require additional models for augmentation and more importantly do not explicitly guarantee that augmentation has a proper strength and diversity.
In this paper, we proposed a novel framework called Metropolis-Hastings Data Augmentation (MHAug) that draws augmented graphs from an ‘explicit’ target distribution with the desired strength and diversity for semi-supervised learning. Since the direct sampling from the complex distribution is challenging, we adopt the Metropolis-Hastings algorithm to obtain the augmented samples. Recently, the importance of leveraging unlabeled data as well as adopting advanced augmentation has emerged [19, 20]. Inspired by that, we also adopt the consistency training by utilizing the regularizers for unlabeled data. Our extensive experiments demonstrate that MH-Aug can generate a sequence of samples according to the desired distribution and be combined with the consistency training and it significantly improves the performance of graph neural networks.
Our contributions are summarized as follows:
• We proposed a novel framework Metropolis-Hastings Data Augmentation that draws augmented samples from an ‘explicit’ target distribution. To the best of our knowledge, this is the first work that studies data augmentation for graph-structured data from a perspective of a Markov chain Monte Carlo sampling.
• We theoretically and experimentally prove that our MH-Aug generates the augmented samples according to the desired distribution with respect to the strength and diversity.
• We propose a target distribution that flexibly controls the strength and diversity of augmentation. This includes an efficient way to measure the strength of augmentation reflecting the structural changes of ego-graphs (or samples in node classification).
• Lastly, we propose a simple and effective semi-supervised learning strategy leveraging sequentially generated samples from our method.

heading: 2 Related Works
text: Semi-Supervised Learning on Graphs. GNNs have been widely adopted in representation learning on graphs [2–4]. However, existing works only utilize a small subset of nodes. To fully utilize a large amount of unlabeled data, recent studies for semi-supervised learning have emerged inspired by semisupervised frameworks in other domains [19, 20]. GraphMix [18] is a regularization method based on semi-supervised learning by linear interpolation between two data on graphs, and SSL [21] proposes self-supervised learning strategies to exploit available information from graph structure. BVAT [22] promotes the smoothness of GNNs by generating virtual adversarial perturbations. Likewise, we follow semi-supervised strategy to leverage unlabeled data while considering sequentially generated samples from our augmentation.
Data Augmentation on Graphs. Data augmentation is an effective technique to improve generalization by increasing the diversity of data. It is becoming the de facto necessity for model training to employ simple data augmentation (e.g., image rotation, flipping, translation, and so on). Despite the effectiveness of data augmentation, few approaches have been explored in graph domain due to its non-Euclidean nature and dependencies between data samples. Simple approaches exist such as DropEdge [23] to randomly remove a certain number of edges and AdaEdge [16] to adaptively control the inter-class/intra-class edges. Similarly, a method to propagate the perturbed node features by randomly dropping on a node-based was proposed in [24]. GAug [17] proposes the neural edge predictors as an augmentation module. Unlike existing methods employing simple perturbation [23] or extra augmentor model [17, 25], we propose the sampling-based augmentation, where a sequence of augmented samples are drawn from the explicitly designed target distribution for augmentation.

heading: 3 Method
text: We present a novel data augmentation framework for graph-structured data via Metropolis-Hastings algorithm. MH-Aug is a sampling-based augmentation, where a sequence of augmented samples are drawn from the explicit target distribution that enables flexible control of strength and diversity of augmentation. The overall sampling process of MH-Aug is described in Figure 1. In this section, we first summarize the basics for our framework and delineate the components of MH-Aug. Then, we outline the training procedure with proposed consistency regularizers for semi-supervised learning. Lastly, we theoretically prove the distribution of augmented samples by MH-Aug converges to the desired target distribution.

heading: 3.1 Preliminaries
text: Ego-graph, Gi. A graph is denoted as G = (V, E), where V and E are the sets of nodes and edges. A k-hop ego-graph Gi [26] is a subgraph of G centered at node vi ∈ V , consisting of neighbors within k hops from node vi and all edges between the neighbors including vi. In other words, the k-hop ego-graph of a node vi is defined as Gi = (Vi, Ei), Vi = {u|S(u, vi) ≤ k, u ∈ V}, Ei = {(u, v)|(u, v) ∈ E and u, v ∈ Vi}, where S(u, v) is the length of the shortest path between nodes u and v. In this paper, we do not explicitly specify k for ego-graphs since 2-hop ego-graphs are used in all experiments.
Change ratio of graph, ∆G′. The change ratio of graph G to G′ = (V ′, E ′) is measured by the number of added/deleted edges (or nodes) divided by the number of original edges (or nodes), i.e., ∆G′E = (|E ′−E|+|E−E ′|)/|E| and ∆G′V = (|V ′−V|+|V−V ′|)/|V|. Since, in this work, we consider only subgraphs of the original input graph as augmented samples, which is similar to DropEdge [23] and DropNode [24], the change ratio can be equivalently written as ∆G′E = 1 − |E ′|/|E| and ∆G′V = 1− |V ′|/|V|. Thereby ∆G′E and ∆G′V are always ranged in [0, 1]. Metropolis-Hastings (MH) algorithm. MH algorithm is a Markov chain Monte Carlo method to draw random samples from a target distribution when direct sampling is difficult [27]. The algorithm comprises three components: the target distribution P , the proposal distribution Q, and the acceptance ratio A. The MH algorithm iteratively draws samples from the target distribution P being only dependent on the current sample. The MH algorithm uses a proposal distribution Q to draw a candidate sample and evaluates the acceptance ratio A to decide whether to accept or reject the candidate sample. The accepted samples by the MH algorithm follow the target distribution P .

heading: 3.2 Metropolis-Hastings Data Augmentation
text: Our objective is to sample the augmented graph G′ from the target distribution P given the original graph G and can be written as G′ ∼ P (G′;G). (1) Since direct sampling from the target distribution P is challenging, we propose a novel data augmentation method based on Metropolis-Hastings algorithm.
Target Distribution. We design the target distribution P to control the strength and diversity of augmentation for effective learning. The strength and diversity can be discussed from two perspectives: a full graph and ego-graphs. In our framework, the strength of augmentation is measured by the change ratio of ego-graphs, i.e., ∆G′i, since most existing GNNs with k-layers learn node representations based on their k-hop ego-graphs. On the other hand, the diversity of augmentation is controlled by ∆G′ and ∆G′i from both full graph and ego-graph perspectives. The diversity of augmentation is adaptively adjusted for each ego-graph by the standard deviation σ( i) that is a simple linear function of the entropy i of the prediction at node vi. Given the expected strength µE ∈ R and ego-graph level diversity σE( i) ∈ R, the target distribution P w.r.t. edges is given as follows:
PE(G′) ∝  |V|∏ i exp ( − (∆G′i,(E) − µE) 2 2{σE( i)}2 )λ1 ·  1( |E| |E|·∆G′E ) λ2 , (2)
where ∆G′i,(E) is the change ratio of G ′ i w.r.t. E and λs are hyperparamters for controlling the influence of the two components. To have various full graph change ratios ∆G′E , the normalization by the number of possible augmented graphs corresponding to the same change ratio, ( |E| |E|·∆G′E ) , is necessary. As the size of graph increases, without the normalization, it becomes extremely difficult to generate augmented samples with a low (or high) full graph change ratio. For more details, see Section 4.2. Similarly, The target distribution P with respect to nodes can be written as follows:
PV(G′) ∝  |V|∏ i exp ( − (∆G′i,(V) − µV) 2 2{σV( i)}2 )λ3 ·  1( |V| |V|·∆G′V ) λ4 , (3)
where ∆G′i,(V) is the change ratio of G ′ i w.r.t. the nodes, V . With combining the two distributions, the overall target distribution is defined as:
P (G′) = PE(G′) · PV(G′). (4)
In our experiment, unlike the change ratio of the full graph ∆G′E (and ∆G′V ), we define the ego-graph change ratio ∆G′i,(E) (and ∆G ′ i,(V)) with the change of the number of received messages from k-hop ego-graphs. Figure 2 illustrates the calculation of ∆G′i,(E) regarding two different cases: (b) dropping distant (2-hop) edges and (c) dropping near (1-hop) edges. In this definition, even if the number of dropped edges is the same, dropping edges connecting nodes closer to the center node vi leads to a larger ∆G′i,(E) than the case of distant nodes (0.6 > 0.13), which can be regarded as a much stronger
augmentation. It indicates that the amount of received messages depends on not only the number of removed edges but also which edges are dropped. This structural property can only be properly handled from ego-graph perspective. In practice, this definition allows time and memory efficient implementation using matrix multiplications as
∆G′i,(E) = 1− (Ã′k1)i
(Ãk1)i , and ∆G′i,(V) = 1−
(Ãkm)i (Ãk1)i , (5)
where Ã and Ã′ are adjacency matrices of the original graph G and the current graph G′, where both graphs include a self-connection for every node, 1 ∈ R|V| is a vector of ones, and m ∈ R|V| is a mask vector for DropNode.
Proposal Distribution. For efficient sampling and a theoretical guarantee of convergence to the target distribution, a proposal distribution is crucial. A proposal distribution Q(G′|G(t)) suggests a candidate augmented sample G′, given the current sample G(t). To draw diversely augmented graphs with various edge/node change ratios ∆G′E and ∆G′V , a candidate augmented sample is generated by three steps: 1) change ratio sampling, 2) graph modification and 3) merging. We first independently sample change ratios ∆G′(·) for edges and nodes from Gaussian distributions truncated to the range [0, 1] given mean ∆G(t)(·) and standard deviation σ∆,(·). Then, we modify the original graph G to generate augmented samples G′E and G′V , which can be viewed as a uniform sampling from all possible augmented graphs with ∆G′E and ∆G′V respectively. Finally, the two graphs G′E and G′V are merged to construct the candidate augmented sample G′. Formally, the proposal distribution is given by:
Q(G′|G(t)) ∝ φ(ξ ′ E)
Φ(βE)− Φ(αE) · φ(ξ
′ V) Φ(βV)− Φ(αV) · 1( |E| |E|·∆G′E ) · 1( |V| |V|·∆G′V ) , (6) where α(·) = a−∆G(t) (·)
σ∆ , β(·) =
b−∆G(t) (·)
σ∆ , ξ′(·) =
∆G′(·)−∆G (t)
(·) σ∆ , φ(x) = 1√ 2π exp(− 12x 2) as the
probability density function of the standard normal distribution and Φ(x) = 12 (1 + erf( x√ 2 )) as its cumulative distribution function. a and b represent the extremes of Gaussian distribution. Since the change ratio should be ranged in [0, 1], a is 0 and b is 1. In (6), the first and second terms denote the likelihood of the change ratios ∆G′E and ∆G′V given ∆G(t). The third and fourth terms are for the probability of a sample with ∆G′E and ∆G′V .
Acceptance Ratio. Starting with the original graph G, MH-Aug draws the candidate graph G′ from the proposal distribution Q. Then, with an acceptance ratio A, MH-Aug decides whether to accept or reject the candidate G′. A is given as:
A = min {
1, P (G′)Q(G(t)|G′) P (G(t))Q(G′|G(t))
} . (7)
The computation of A with target distribution in (4) and proposal distribution in (6) is described in the supplement. MH-Aug generates a sequence of augmented graphs {G(t)}0≤t≤T , where T is the number of accepted samples.

heading: 3.3 Consistency Training with MH-Aug
text: Inspired by recent works [19, 28, 20] that show the importance of advanced augmentation methods in leveraging unlabeled data, we demonstrate the effectiveness of our augmentation method in both supervised and semi-supervised settings. Similar to consistency regularization [20], we propose a simple training strategy with the following regularizers:
Lu = 1
|V| |V|∑ i DKL [ f(G(t)i ; θ) || f(G (t+1) i ; θ) ] , and Lh = 1 |V| |V|∑ i [−f(Gi; θ) log(f(Gi; θ))] ,
(8)
where DKL(· || ·) is the Kullback–Leibler divergence, f(·) is the GNNs parameterized by θ and Gi is the k-hop ego-graph for node i. Lu encourages the consistency of predictions on two consecutive
augmented samples G(t)i , and G (t+1) i . Lh penalizes unconfident predictions and sharpens predictions. The two regularizers can be applied to both labeled and unlabeled nodes in the node classification task. With the two regularizers and the standard cross-entropy loss Ls for supervised samples, the overall loss for semi-supervised learning is given as
L = Ls + γ1Lu + γ2Lh. (9)
Our framework is outlined in Algorithm 1. Starting from original graph G with 0 change ∆G′, MH-Aug generates new augmented graph data G′ with the change of ∆G′. It decides whether to accept or reject the candidate G′ with acceptance score A. GNN models are trained with the accepted augmented data with our loss in (9). Then, the process is repeated until the model converges.
Algorithm 1 Metropolis-Hastings Data Augmentation (MH-Aug) Framework Input: target distribution P , proposal distribution Q, original graph G Output: network parameter θ
Initialize t← 0, G(0) ← G while not convergence do
Draw G′ from Q(G′|G(t)) . Q in Eq.(6) Draw u from Uniform(0, 1) if u ≤ A then . A in Eq.(7) G(t+1) ← G′
Update θ with L(G,G(t),G(t+1); θ) . L in Eq.(9) t← t+ 1
end if end while

heading: 3.4 Theoretical Analysis
text: The goal of the Metropolis-Hastings algorithm is to generate a sequence of samples according to a desired target distribution P . To accomplish this, the Metropolis-Hastings algorithm uses a Markov process, which asymptotically reaches a unique stationary distribution π(x) such that π(x) = P (x) [29]. Here, we show that Markov chain of MH-Aug, which has a sequence of augmented graph as states, converges to the unique and stationary target distribution P (G′) defined in (4). Lemma 3.1. Let the sequence of augmented graphs {G(t)}0≤t≤T be the Markov chain produced by MH-Aug. If we define the acceptance ratio A with target distribution P in (4) and proposal distribution Q in (6), the sequence converges to a unique stationary target distribution P .
This can be drawn from the Convergence theorem of Markov chain [30]. The proof is in the supplement. By Lemma 3.1, we theoretically show augmented samples of MH-Aug converges to our desired target distribution. Our toy examples show a sequence of augmented graphs actually converges well to the target distribution (see Section 4.2 for details).

heading: 4 Experiments
text: In this section, we demonstrate the effectiveness of MH-Aug on various benchmark datasets. We start with describing datasets, baselines, and implementation details for the experiments. Next, we evaluate our framework for node classification in Section 4.1 and we offer qualitative analyses in Section 4.2 on three parts: effectiveness of ego-graph perspective for desired target distribution P , necessity of normalization term in P , and whether generated samples from MH-Aug converge to P .
Datasets. We evaluate our method on five benchmark datasets in three categories: (1) Citation networks: CORA and CITESEER [31], (2) Amazon product networks: Computers and Photo [32], and (3) Coauthor Networks: CS [32]. We follow the standard data split protocol in the transductive settings for node classification, e.g., [4] for CORA and CITESEER and [32] for the rest.
Baselines. As backbone models to validate MH-Aug, we adopt three standard graph neural networks: GCN [4], GraphSAGE [1], and GAT [3]. We compare our method with vanilla models (without
augmentation), augmentation-based supervised learning (DropEdge [23], AdaEdge [16]), and semisupervised learning framework (GAug [17], SSL [21], BVAT [22], UDA* [19], GraphMix [18]). In the case of DropEdge [23] and AdaEdge [16], they use only cross-entropy loss (supervised setting) while the rest of models employs extra loss functions for regularization (semi-supervised setting).

heading: 4.1 Results on Node Classification
text: Table 1 shows the experimental results on node classification with five datasets compared to baseline models. We implemented all the baselines and conducted experiments for fair comparison except for the case where the performance (marked with †) is available in the original papers [16, 17, 21, 22, 18]. Also, we denote out-of-memory as OOM. MH-Aug (w/o Reg) means training the model only with the labeled data and cross-entropy loss Ls whereas MH-Aug (w/ Reg) means using extra regularization losses to explicitly utilize the unlabeled data. Our full framework MH-Aug (w/ Reg), which is trained in the semi-supervised setting, consistently achieves the best performance in all datasets and the
improvement against the vanilla models is 3.16% on average. In particular, we observe that MH-Aug improves the performance by 4.92% compared to the vanilla GraphSAGE on CORA. In addition, MH-Aug provides an 4.16% gain on CITESEER on average over all models (i.e., vanilla GCN, GraphSAGE and GAT).As an ablation study, we conduct experiments with MH-Aug (w/o Reg), our framework trained in the supervised setting. Table 1 shows that MH-Aug (w/o Reg) achieves 1.47% improvement on average compared to vanilla models. MH-Aug (w/o Reg) provides considerable gain over all dataset and model. More specifically, it provides 3.25% performance improvement compared to the vanilla GAT model on Computers. In addition, MH-Aug (w/o Reg) beats DropEdge for all settings and mostly beats AdaEdge that optimizes the graph topology based on the model predictions. It is worth noting that even though MH-Aug (w/o Reg) does not explicitly utilize unlabeled data during training, MH-Aug (w/o Reg) achieves competitive performance compared to other semi-supervised methods, especially in the following cases: GCN on CORA (83.55%); GraphSAGE on CITESEER (72.12%); and GAT on CORA (83.49%), and Photo (90.23%). This demonstrates the effectiveness of our sampling-based augmentation. More discussion on ablation study is in the supplement.

heading: 4.2 Analysis
text: Effectiveness of Ego-graph Perspective. To validate the effectiveness of ego-graph perspective augmentation, we qualitatively analyze augmented samples by MH-Aug on real data with various settings as shown in Figure 3. An original sample (first column) is a 3-hop ego-graph from CORA. Augmented samples are generated from G in three settings: (µE , σE ) = (0,0.05), (µE , σE ) = (1,0.05) and (µE , σE ) = (0,1000). The mini maps at the upper right corner shows the edge-drop probability,
calculated from ∏|V| i exp ( − (∆G ′ i,(E)−µE) 2
2{σE}2
) of (2). To evaluate the effect of µE and σE w.r.t. ego-
graph, we fix the full-graph change ratio ∆G′E and observe the expected value of ∆G′i,(E) over all possible nodes in the ego-graph, E[∆G′i,(E)]. Thus, the number of dropped edges is identical for all the augmented graphs in Figure 3. It demonstrates that even if the number of dropped edges is the same, one can generate diverse samples by controlling µE and σE . When µE , which controls the expected augmentation strength, is large, e.g., µE = 1, σE = 0.05, more important edges (e.g., edges acting as bridges between hub nodes) tend to be dropped. This observation exactly matches to our design in Section 3.2, which considers dropping edges near to the center as a strong augmentation. In addition, the mini map in the fourth cell of Figure 3 indicates if σE increases, the edge-drop probability of the all edges becomes uniform, i.e. MH-Aug subsumes DropEdge as a special case. In sum, the ego-graph perspective enables the explicit control of augmentation strength and diversity to make an advanced augmentation.
Necessity of Normalization Term. As mentioned in Section 3.2, the normalization in the target distribution P by the number of possible augmented graphs corresponding to the same change ratio,( |E| |E|·∆G′E ) , is crucial to generating ego-graphs with the desired ego-graph change ratio µE when the number of edges is huge. We demonstrate it with a small but fully connected graph to apply MH-Aug. Figure 4 displays the distribution of the empirical mean of ∆G′i,(E) from the augmented graph sampled from P with two different µE = 0.1 and µE = 0.9. With normalization (Figure 4(a)), the sample mean of ∆G′i,(E) of both sampling results are near to the µE values. However, without normalization (Figure 4(b)), the empirical mean of ∆G′i,(E) remains the same due to overwhelmingly many possible subgraphs with a certain full graph change ratio ∆G′E , e.g., ( 100×100 5000 ) for a fully connected graph with 100 nodes. But this does not mean that our MH-Aug fails to converges to the target distribution. It merely converges to the undesirable target distribution.
Convergence to Target Distribution. In Section. 3.4, we theoretically show that the distribution of samples generated by MH-Aug converges to our desired target distribution P . Now, we conduct the experiment to examine whether a sequence of augmented graphs experimentally follows the target distribution. We observe the behavior of MH-Aug with a simple toy example, i.e., a grid graph with 100 nodes. For simplicity, we only consider the change of edges and the target distribution PE in (2). In 5(b), red line denotes the probability of each edge obtained by calculating P with (2). Blue bars represent the distribution of augmented graphs generated by MH-Aug. It shows MH-Aug generates augmented graphs following the target distribution. In 5(a), we visualize drop probability on graph. Since we set µE small, drop probability of center edges is higher than others.

heading: 5 Conclusion
text: We present a novel semi-supervised strategy with Metropolis-Hastings algorithm based augmentation method. This is the first work to impose data augmentation on graph-structured data from a perspective
of a Markov chain Monte Carlo sampling. We theoretically and experimentally show the convergence of augmented samples to target distribution and demonstrate its consistent performance improvement over baselines across five benchmark datasets.
Acknowledgments. This work was partly supported by NAVER Corp., National Supercomputing Center with supercomputing resources including technical support (KSC-2021-CRE-0181) and ICT Creative Consilience program (IITP-2021-2020-0-01819) supervised by the IITP.

Review summaries:
This paper introduces a MH-style data augmentation to boost the generalization ability of the existing GNNs by generating sequence of augmented graphs. The generation is proven to be converging to the desired target distribution. The experimental results shows a promising result for applying augmented graph during the GNN training. 

The paper proposes a new data augmentation method for Graph Neural Networks based on Markov Chain Monte Carlo sampling and in particular the Metropolis-Hastings algorithm in the context of semi-supervised learning. The main intuition of the paper is to define a target distribution for the whole graph which is representative of the changes in the number of messages that are exchanged in the k-hop neighborhood of each node and then apply the Metropolis-Hastings algorithm for obtaining samples that are representative of this distribution. The experimental section compares the proposed method (MH-Aug) to other recent data augmentation methods showing favorable results w.r.t. the baselines.