Metropolis-Hastings Data Augmentation for Graph Neural Networks
Authors: Hyeonjin Park
Seunghun Lee
Sihyeon Kim
Jinyoung Park
Jisu Jeong
Kyung-Min Kim
Jung-Woo Ha
Hyunwoo J. Kim
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Augmentation
Metropolis-Hastings

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.

Metropoli--Hastnng Data Augmentation for Graph Neural Networks
Hyeonjin Park Seunghun Lee'; SShyeon Kim Jinyoung Park' Jisu Jeong?.. Kyung-Min Kim Jung- Woo Ha?:3 Hyunwoo J. Kim Korea University', NAVER CLOVA?, NAVER AI LAB (hyeonjin96100 11sshh319, sh_bs15, 1pmn678, hyunwoojkim)ekorre ac (jisu.jeong kyungmin. kim.ml, jungwoo ha] ha)
Abstract
Graph Neural Networks (GNNs) often suffer from weak-generalization due sparsely labeled data despite their promising results on various graph-base based tasks. Data augmentation is prevalent remedy improve the generalization ability of models in many domains. However, due to the non- -un-Euclidean nature data space and the dependencies between samples, designing effective augmentation on graphs is challenging. In this paper, we propose a novel framework Cetropolis-Hasttine Data Augmentation (MH-Aug) that draws augmented graphs from explieit target distribution for semi-supervised learning. MH-Aug produces sequence of aug- mented graphs from the target distribution enables flexible control of the strength and diversity of augmentation. Since the direct sampling from the complex target algorithm obtain
adopt the Metropolis-Hastingg the augmented samples. We also propose a simple and effective remi-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.
distribution is challenging,
Introduction
Graph Neural Networks (GNNs) have been widely used for representation learning on graph- structured data due to their superior performance in various applications such as node classification 2
(4, link prediction 7 and graph classification [9. They have been proven effective by achieving impressive performance for diverse datasets such as social networks [10] citation networks [].
physics [1]], molecules 122 and knowledge graphs 10]. However, GNNs often suffer from weak- generalization 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 widely used to enhance the generalization ability of models in many domains. For instance, in image recognition, advanced methods like 1345 as well as simple transformations such 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 challenging due to their non- -on-Euciddean 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 authors have equal contribution
is the corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 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 control the degree of augmentation for individual samples. For instance, simple operation on graph, e.g., dropping node, may result in completely different degree of augmentation depending on the graph structure. If hub node is removed, the single perturbation affects substantial amount of other nodes, which are data samples in node classification. To address these challenges, learning- -ased 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 proper strength and diversity.
In this paper, we proposed a novel framework called Metropolis- Heatopolis-Hastingss Data Augmentation (MH- Aug) 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-HHee Mastiigs algorithm to obtain the augmented samples. Re- cently, the importance of leveraging unlabeled data well 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 sequence of samples according to the desired distribution and be combined with the consistency training and significantly improves the performance of graph neural networks.
Our contributions are summarized as follows:
We proposed a novel framework Metropolis-Hastinng Data Augmentation that draws aug- mented samples from an 'explicit' target distribution. To the best of our knowledge, this is the first work that studies data augmentation for graph 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 augmen- tation. 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 supe-supe learning strategy leveraging sequentially generated samples from our method.
2 Related Works
Semi-Supervised Learning on Graphs. GNNs have been widely adopted in representation learning on graphs 224) 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 semi- supervised frameworks in other domains (0). GraphMix (18) is regularization method based on supi-supe learning by linear interpolation between two data on graphs, and SSL. (1 proposes self 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 general- ization 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- Euclliddn nature and dependencies between data samples. Simple approaches exist such as DropEdge (33 to randomly remove a certain number of edges and AdaEdge [16] to adaptively edges. Similarly, method to propagate the perturbed node features
control the caaarrlllsss/itaaallaaa 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-hase augmentation, where a sequence of augmented samples are drawn from the explicitly designed target distribution for augmentation.

---

(1) Change Ratio Sampling
(2) Graph Modification
(3) Candidate
g(++1)
accepted
Aal"" &.2
(
rejected
P PQ
P(g") Pig QQ01gg
39,
30%
A min
Figure I: Sampling process MHH-Aug. MH--Au produces augmented samples in two steps. First, it draws a candidate graph G" from a proposal distribution Q (green). Then, it decides whether to accept or reject the candidate by the acceptance ratio A calculated by P (bluc) and Q. The left box shows the details of sampling candidate graph G'
the proposal distribution Q('' ((()) given current sample (()); (1) Change Ratio Sampling draws the change ratios Agg and AGy of a candidate graph w.r.t. edges and nodes from the Gaussian
distributions truncated to the range [0. 1]. (2) Graph Modification generates G/ and Fy by applying the change ratio the original graph G, and (3) Candidate augmented graph G is constructed by merging two augmented graphs Ge and Gyy.
3 Method
We present a novel data augmentation framework for graph-structured data via Cetropolis-Hastting algorithm. MH-Aug is sampling-ban augmentation, where sequence of augmented samples are drawn from the explicit target distribution that enables flexible control strength and diversity of augmentation. The overall sampling process of MH-Aug is described in Figure T In this section, 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 sumii-upereised learning. Lastly, we theoretically prove the distribution of augmented samples by MH-Aug converges to the desired target distribution.
3.1 Preliminaries
Ego-graph, G.. graph is denoted as G = E), where V and are the sets nodes and edges. A k-hop ego-graph Gi (26) is subgraph of G centered at node i, E V. consisting of neighbors within & hops from node i and all edges between the neighbors including 14. other words, the k-hop ego-graph of node e; is defined as G. (V,,E,) V, {u|S(u, v.) < k V}. & = {(u, (u, v) E E and u, u E V:), where S(u, u) is the length of the shortest path between nodes and In this paper, we do not explicitly specify & for ego-graphs since 2-hop ego-graphs used all experiments.
Change ratio of graph, Ag'. 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., and AG' (IV' - V')//>>. Since, in this work, we consider
AG'- = only subgraphs of the original input graph as augmented samples, which similar to DropEdge [23]
and DropNode (24). the change ratio can be cquivalently written Aç and AG, are always ranged [0, 1].
[ and
Ag = | Thereby
AG' Thereby
Metropolis-Hasting (MH) algorithm. MH algorithm is Markov chain Monte Carlo method draw random samples from target distribution when direct sampling is difficult [27]. The algorithm comprises three components: the target distribution P, the proposal distribution Q, and acceptance ratio A. The MH algorithm iteratively draws samples from the target distribution being only dependent on the current sample. The MH algorithm uses proposal distribution Q to draw candidate sample and evaluates the acceptance ratio decide whether accept or reject the candidate sample. The accepted samples by the MH algorithm follow the target distribution P.

---

(a) Message Propagation of u, G.
(b) AC 1- i5 (c) AG. 1
Calculation of (e) (a) displays the message propagation i on ego-graph G; in order. The received message of t; is 15 in the original 2-hop G.. In case of dropping distant (2-hop) edges (b), the received message of is 13 and AC becomes 0.13. In case of dropping same number near (1-hop) edges (c), the received message of e is 6 and AG becomes 0.6.
Figure 2:
3.2 Metropolis- -asptinnsss Data Augmentation
Our objective is to sample the augmented graph G' from the target distribution P given the original graph and can be written
g' ~ P))
(1)
Since direct sampling from the target distribution P is challenging, we propose novel data augmen- tation method based on Metropolis-Hastingg 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: full graph and ego-graphs. In our framework, the strength of augmentation measured by the change ratio of ego-graphs, i.e., Ag since most existing GNNs with k-layers learn node representations based on their k-hop ego-graphs. On the other hand, the diversity augmentation controlled by Ag' and Aç: from both full graph and ego-graph perspectives. The diversity of augmentation is adaptively adjusted for each ego-graph by the standard deviation (eg)) that a simple linear function of the entropy e, of the prediction at node e; Given the expected strength μ E RR and ego-graph level diversity og (ex) E R, the target distribution w.r.t. edges is given as follows:
IIV II exp
(AG - ME)
2((x(E:)3² )
A
1
PE(G")
where A9, the change ratio of 9; w.r.t. & and \s are hyperparamters for controlling the influence of the two components. To have various full graph change ratios A the normalization by the number of possible augmented graphs corresponding to the same change ratio, Ag ). necessary. As the size of graph increases, without the normalization, it becomes extremely difficult to generate augmented samples with 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:
(APLM)) - mV)?
)
As
A
1
Po(g")
II exp
2(ov(E:)]2
V
(1)
where (v) is the change ratio of 9 w.r.t. the nodes, V. With combining the two distributions, the overall target distribution is defined as:
P(g") - = Pv(g))
(4)
In our experiment, unlike the change ratio of the full graph AG (and AG',), we define the egu-graph change ratio A9', (and ) with the change of the number received messages from k-hop
ego-graphs. Figure illustrates the calculation of Ag 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 larger AG(,()) than the case of distant nodes (0.6 > 0313), which can be regarded as 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
(A**)); A = 1 (A*1); and A = =1 (A m)mm
(5)
(A*1),
where À and Á' are adjacency matrices of the original graph 9 and the current graph g', where both graphs include self-connection for every node, 1 E R is a vector of ones, and m E RM is mask vector for DropNode.
Proposal Distribution. For efficient sampling and theoretical guarantee of convergence to the target distribution, a proposal distribution crucial. A proposal distribution Qg' ((()) suggests candidate augmented sample G', given the current sample g(t), To draw diversely augmented graphs with various edge/node change ratios Ag' and Ag', 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 Ag for edges and nodes from Gaussian distributions truncated to the range
[0, given mean Ag (t) (-) and standard deviation oA.))- Then, modify the original graph G to generate augmented samples I/- and Kys which can be viewed as a uniform sampling from all possible augmented graphs with AG' and AG respectively. Finally, the two graphs 96 and Gj are merged to
construct the candidate augmented sample g'. Formally, the proposal distribution is given by:
(
Q(()(
((Bg) ((gg
((Bv) - -b(ay)
181
(p/AAE)
(6)
a-40 B6) b- 6) -0% ((x)
where ((-))
exp( f0²²) the V2n
as
0s
probability density function of the standard normal distribution and ((x) {1 + fr { )) as its cumulative distribution function. and 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 Ag'. and Ag given (t The third and fourth terms are for the probability of sample with Ag and AGK.
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:
Acceptance Ratio.
{ P
P( ) P(
A =
m=min| min
The computation of A with target distribution in 4 and proposal distribution in (6 is described in the supplement. MH-Aug generates sequence of augmented graphs (g(() JoSEST, where T is the number of accepted samples.
3.3 Consistency Training with MH-Aug
Inspired by recent works 19 28 20 that show the importance of advanced augmentation methods in leveraging unlabeled data, demonstrate the effectiveness of augmentation method in both supervised and cumi-super settings. Similar to consistency regularization [20,,
we propose a
simple training strategy with the following regularizers:
M Σ DKL [(g :) ((g(tt) :0]] and C. = [V]
M
C,
Σ -
I
where DRL( (: || .) the Kullback-Leible divergence, f(:) the GNNs parameterized by and G, is the kohop ego-graph. for node i. L. encourages the consistency of predictions two consecutive
5

---

augmented samples q and g( La 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- cross-entropy loss Cg for supervised samples, the overall loss for semi-supervised learning is given as
C C. + T2l C2Ch.
Our framework is outlined in Algorithm | Starting from original graph & with 0 change Ag', MH-Aug generates new augmented graph data G" with the change of Ag'. 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 MetsopoliisHastings Data Augmentation (MH-Aug) Framework
Input: target distribution P, proposal distribution Q, original graph G
Output: network parameter 8
Initialize + 0, g + g
while not convergence do
Draw G' from (()
Q Eq
Draw u from
if u I A then
b A in Bq
g(++1) Update 0 with L(G, , g((+));0) t ++
+ g'
b L Eq
end if end while
3.4 Theoretical Analysis
The goal of the Hattopolis-Hastingg algorithm is to generate a sequence of samples according to a desired target distribution P. To accomplish this, the Metropolis-Hasting algorithm uses a Markov process, which asymptotically reaches a unique stationary distribution x (xx 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 losisT 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 supple- ment. By Lemma we theoretically show augmented samples of MH-Aug converges to our desired target distribution. Our toy examples show sequence of augmented graphs actually converges well to the target distribution (see Section 4.2 for details).
Experiments
In this section, we demonstrate the effectiveness of MH-Aug 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.] 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 P.
Datasets. We evaluate our method on five benchmark datasets in three categories: (1) Citation networks: CORA and CITESEER (1.. (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., for CORA and CITESEER and (32 for the rest.
Baselines. backbone models to validate MH-Aug, we adopt three standard graph neural networks: GCN (4. GraphSAGE []] and GAT (3] We compare our method with vanilla models (without

---

Table 1: Node classification results. Mean aceuracy and standard deviation from 10 repetitions reported. We compare our methods with baselines of two categories: 1) supervised learning with A augmentation (e.g., DropEdge and AdaEdge), which comparable 2) semi-supervised learning (e.g,, GAug, SSL, B VAT, UDA* and GraphMix) that are comparable to MH-AAg (w/ Reg). For each dataset and baseGNN the highest score is marked in bold.
MH-Aug (w/ Reg) and
DATASET
BaseGNNs
Method
CORA
CITESEER
Compu.
Photo
CS
Vanilla
21.54
71.642031
79.682216
89.02
91.45=0.28
DropEdge
1077
71.9340.1
80,59
89 19.33
91.69=0.43
AdaEdge
16
82. 20000
69.70 69.70+0.0
80.66
89,941004
90.30=0.400
MH-Aug (w/o Reg)
83.55
72.96::048
80.95
89.65
91.81=0.33
GCN
GAug-M
17
83.50
72.30++0.0
18.9
88.46
OOM
GAug-O 17
$3.60
13.30=+1.of
OOM
89.04
OOM
SSL 21
83. 70:777
:2.95:t0.22
BVAT 22
83.60
74.00
80.07=241
28.46
92.27
UDA 119
83.59:1061
73.56:10.41
81.68:2295
89.95
92.26=0037
GraphMix 08
83.90
74.70=t..9f
80.72:21.16
89 89.05
91.83=0051f
MH-Aug (w/ Reg)
85.16:1035
75.49:0.29
82.80
90.87:1149
92.60=0043
Vanilla
79.78
71.09
79.59=1.84
89.10:1100
91.355=1.00
DropEdge
80.36:0080
71.46+0.57
79.87=1887
89.86::1.8
91 01.84
AdaEdge 16
80.20
69.40:1..0l
80.43:21.30
90.57
90.30=0010f
MH-Aug (w/o Reg)
82.61 10.66
72.12+a.99
81.74=22.2
90.37 1
92,27 00.49
GraphSAGE
GAug-M 17
83.20
71.20:1..0f
1..84=11.99
88.72:10.97
OOM
GAug-O 17
82.00
72.70=t070f
OOM
88.16422.70
OOM
BVT 22
83.12
4..23
78.72#a273
89.40..1.79
92.63
UDA
19
83
16:10:1.16
82.1622.00
90.61 +0.01
92.83=0039
GraphMixx
18
82,28
69.6224.36
81.33=11446
88.46+11.4
89.29
MH-Aug (w/ Reg)
84.70
75.55
83.62::2.00
92.19
93.61
Vanilla
82,23
71.374093
78.47=1.86
87.80+1.36
90.90=a.31
DropEdge
83.04.1037
72.164091
81.04=1..6
88.73
91.10=a0.37
AdaEdge
16
77. 77.90+200f
69.10
77.52:
88,92+t087
86.60=a.16
MH-Aug (w/o Reg)
83.49
72.81
81.72::166
90.23
91.40
GAT
GAug-M
17
82.10:1.00
71.50
77.70=2.10
87.08+11000
OOM
GAug-O 17
s2.
71.60+1.10f
OOM
16.45
OOM
SSL
21
83.70.2011
72.73
UDA
83.71 40.48
43.24:10.4
82.42+295
89.79
91.78
GraphMix
18
83.32
73.08
MH-Aug (w/ Reg)
84.95:10.00
75.53
83.25
90.61
92.08
UDA" denotes extension of UDA the graph domain. denotes the results reported in the original paper.
augmentation), augmentation- supervised learning (DropEdge 233 AdaEdge [66]. and semi- supervised learning framework (GAug [17]. SSL (2T), BVAT [22].
UDA * [9] GraphMix [8]). In
the case of DropEdge [23] and AdaEdge [16]. they use only cross cross-entropy loss (supervised setting)
while the rest of models employs extra loss functions regularization semi-supervised setting).
4.1 Results on Node Classification
Table I 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 t) is available in the original papers [16] 17 21 22 [8]
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 L. 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
7

---

g
Me 0,0g = 0.05
00 0.05
Re = 0, 0, = 1000
Ag% 100 B|
.12 Ag% -10, EAAG..:: A0% -10, E|AG,
0.0
0.2
0.4
0.6
0.8
1.0
Edge-Drop Probability
Figure 3: Diverse G' sampled by MH-Aug. The first cell is the original graph G extracted from CÓRA. With the fixed full graph change ratio Ag's augmented graphs with different μıg and og are generated by MH-Aug. All graphs above are 3-hop ego- ago-graphs with a center node marked as yellow. Nodes and edges which are not in the ego-graph after augmentation are blurred. Mini-maps at the upper right corner is the edge-drop probability, where blue means higher probability and red means low probability to drop the edge. By explicitly controlling the strength and diversity from an ego-graph perspective, MH-Aug generates diverse augmentations.
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) an ablation study, conduct experiments with MH-Aug (w/o Reg), our framework trained in the supervised setting. Table [ shows that MH-Aug (w/o Reg) achieves 1.47% improvement 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 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. 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 33):5%); GraphSAGE on CITESEER (72. 12%);; and GAT on CORA (83 (3.4 and Photo (90.23% This demonstrates the effectiveness of our sampling- based augmentation. More discussion on ablation study is in the supplement.
4.2 Analysis
Effectiveness of Ego-graph Perspective. To validate the effectiveness of ego- pro-graph perspective augmentation, we qualitatively analyze augmented samples by MH-Aug on real data with various settings as shown in Figure An original sample (first column) is a 3-hop ego-graph from CORA. Augmented samples are generated from in three settings: (Mg, Øg) ) (0,0.05), (Ug, σe) (1.0.05) and (us ag) = (0, (0,1000). The mini maps at the upper right corner shows the edge-drop probability,
calculated from II!" exp
(eli,ee)-e) of (2). To evaluate the effect of jr and og w.r.t. ego- 2(
graph, we fix the full- bull-graph change ratio Ag'. and observe the expected value of AC over all possible nodes in the ego-graph, E
[A 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 Me and ag. When Mg, which controls the expected augmentation strength, is large, e.g., Me = =1, og = 0.05, more important edges (e.g., edges acting as bridges between hub nodes) tend 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 if ag 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.
8

---

A=
6.2
Hy = 0.1
Percentage
8.23
H: 0.9
Me = 0.9
024
008
(a) With Normalization, A2
(b) Without Normalization, d 0
Figure 4: The effect of normalization term. The two plots above show the distribution of aug- mented graphs w.r.t. ([A)) We conduct the toy example with the target distribution (a) with normalization (blue) and (b) without normalization (red).
6002
0.10
0:25
Drop Probablitt
0003
8.66
0.03
8:64
52
100
125
150
375
Edge Index
(a) Drop probability each edges
(h) Visualization drop probability on grid graphs
Figure Convergence the target distribution. To verify the convergence of MH-Aug, we simulate the sampling procedure of MH-Aug grid graph. (a) is the result of target distribution P given ci O. We highlight the edges according to drop probability. drawn from MH-Aug (blue) follow the target distribution P (red) that we calculate with (2)
(b) shows that the samples
Necessity of Normalization Term. As mentioned in Section 3.2 the normalization the target distribution P by the number of possible augmented graphs corresponding to the same change ratio, [8] ). crucial to generating ego-graphs with the desired ego-graph change ratio μig when (gg)
the number of edges is huge. We demonstrate with a small but fully connected graph to apply MH-Aug. Figure 4 displays the distribution of the empirical mean of AG from the augmented graph sampled from P with two different μ4 0.1 and μr = 0.9. With normalization (Figure 4(a)). the sample mean of Ag' of both sampling results are near to the μe values. However, without normalization (Figure (())). the empirical mean of AC remains the same due overwhelmingly
many possible subgraphs with certain full graph change ratio AG'e e.g., (100x100) for 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.
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 simple toy example, i.e., grid graph with 100 nodes. For simplicity, we only consider the change of edges and the target distribution Pe (2). In (bb) 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 ((a) visualize drop probability graph. Since we set μr small, drop probability center edges is higher than others.
Convergence Target Distribution. In Section. 3.4
Conclusion
We present a novel remi-supervisse strategy with Metropolis- algorithm based augmentation method. This is the first work to impose data augmentation graph-structured data from perspective

---

of 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.
This work was partly supported by NAVER Corp., National Supercomputing Center with supercomputing resources including technical support DSSC-202-CCRE-O11 and ICT Creative Consilience program LITP-202) -0001000--0-11199 supervised by the IIT..
Acknowledgments.
References
[1] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017.
[2] William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs. In NeurlPS, 2017.
[3] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2017.
[4] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[5] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurIPS, 2018.
[6] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In ESWC, 2018.
[7] Thomas N Kipf and Max Welling, Variational graph auto-encoders. In NeurIPS W, 2016.
[8] Rex Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurlPS, 2018
[9] David Duvenaud, Dougal Maclaurin, Jorge Aguilera- Iparraguire,, Rafael Bommaz-Bomaarell, Timothy Hirzel, Alán Aspuru-Guzir and Ryan P. Adams. Convolutional networks graphs for learning molecular fingerprints. In NeurIPS, 2015.
[10] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In KDD, 2016
[11] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
[12] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513-530) 2018.
[13] Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In ICCV, 2019.
[14] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe Le. Autoaugment: Learning augmentation strategies from data. In CVPR, 2019.
[15] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In CVPR W, 2020.
[16] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over-smoothing problem for graph neural networks from the topological view. In AAAI, 2020.
[17] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In AAAI, 2021.
10

---

[18] Vikas Verma, Meng Qu Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for semi-supervised learning. In AAAI, 2021.
[19] Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoc Le. Unsupervised data augmen- tation for consistency training. In NeurIPS, 2020.
[20] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervised learning with consistency and confidence. In NeurIPS, volume 33, 2020.
[21] Qikui Zhu, Bo Du, and Pingkun Yan. Self-supervised training of graph convolutional networks. Arxiv, 2020.
[22] Zhijie Deng, Yinpeng Dong, and Jun Zhu. Batch virtual adversarial training for graph convolu- tional networks. ICML. W, 2019.
[23] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In ICLR, 2020.
[24] Wenzheng Feng. Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang. Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In NeurIPS, 2020.
[25] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In ICML, 2020.
[26] Qi Zhu, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han, and Carl Yang. Transfer learning of graph neural networks with ego-graph information maximization. In NeurIPS, 2021.
[27] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109, 1970.
[28] Jihoon Tack, Sangwoo Mo, Jongheon Jeong, and Jinwoo Shin. Csi: Novelty detection via contrastive learning on distributionally shifted instances. In NeurIPS, 2020.
[29] Christian Robert and George Casella. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
[30] Ari Freedman. Convergence theorem for finite markov chains. Proc. REU, 2017.
[31] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
[32] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. NeurIPS W, 2018.


Reviews:
[{"review_id": "rpyz5EQQIY9", "reviewer": "Reviewer_1YEx", "summary": "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.", "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": "The paper proposes an interesting idea for data augmentation for graph structured data. To the best of my knowledge, this is the first time that the Metropolis-Hastings algorithm is used for sampling variations of an input graph, whose strength can be controlled via hyper-parameters for improving performance of graph neural networks. The experimental section of the paper shows good results for the proposed method, which outperforms the selected baselines in all the considered prediction tasks. \n\nWhile I believe the idea presented in the paper is intriguing (and the task for sure of relevance to the community), the paper itself is not particularly well written. The introduction on the Metropolis-Hastings algorithm is rather short and high level and assumes that the reader is already familiar with the details of the method (e.g. the acceptance score of equation 7 is not explained in the paper and it’s given for granted that the reader is knowledgeable of the algorithm). Throughout the paper I personally found confusing the continuous jumps between changes of measures defined at an ego-network and graph level (e.g. equations 2 and 3 are defined for the whole graph G in terms of variations of the ego networks of the nodes of G which are presented after the equations themselves; the sampling function Q of equation 6 is instead defined resorting to the variations of the number of edges / nodes of whole G, which are presented before equation 2 and 3 - reading this section personally felt like reading spaghetti code, where I had to continuously go back and forth to clarify the intent of the authors). Additionally, there are a number of missing definitions that make the understanding of the whole paper rather difficult, in particular:\n\n1) Lines 128/130, this is very unclear, the entropy of the prediction is a scalar at node i, what do the authors mean with standard deviation of the entropy of a target node here?\n\n2) In equation 2 the expected variation is defined wrt the entropy \\epsilon_i of the predictions of node i, but this is not defined in the text, what do the authors mean here?\n\n3) Line 164, a and b I believe represent the extremes of the truncated gaussian, however this is not defined at all in the main paper (there are details of this in the supplementary material, but I believe the authors should not rely on that for these sort of fundamental definitions that build the main message of the paper).\n\n4) Lines 177/178, the whole framework is targeted towards semi-supervised learning as the whole graph is modified by equation 6 instead of the single independent ego networks (unless I’m mistaken). Referring to two different training settings, one of which is named “supervised” in the paper is confusing and I would encourage the authors to refactor those lines accordingly.\n\n5) In Figure 3 it’s unclear the meaning of E(\\Delta G_i), I believe the authors might intend with this the expected value of \\Delta G_i over all possible nodes of the ego network, however this is not detailed in the paper (and if this is correct, I would encourage them to use the classic notation E[.]).\n\n6) Line 237, the meaning of MH-Aug (w/o Reg) is unclear from the paper. Are the authors training on the augmented samples as if they were the original graph here? Please clarify.\n\n7) Lines 253/254, the authors mention the edge drop probabilities are computed from equation 2, however equation 2 determines the similarity of the ego networks w.r.t. the desired variation rather than the probability of an edge being dropped. I would ask the authors to provide more details on this and clarify the computation of those probabilities in the rebuttal.\n\n8) Lines 275/282, the references to Figure 5a and 5b should be swapped.\n\nIn light of this, I’m weakly in favor of the acceptance of the paper and I would ask the authors to clarify all the doubts addressed above and refactor the paper accordingly to improve readability.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "7gamoN3Aitl", "reviewer": "Reviewer_kMJz", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strength:\n1. The paper is easy to follow and proposed methods are both theoretically and empirical sound from the results.\n\nWeakness & Questions:\n1. What's the difference of w/o and w/ Reg? Is the only difference on whether have two terms in equation 9? For the DropEdge and AdaEdge baseline, why do you call them \"supervision\"?\n2. What's the main intuition behind the given target distribution at Equation (2)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "3vV4CEJTwQ", "reviewer": "Reviewer_S7LY", "summary": "This paper proposes a data augmentation method for GNNs based on Metropolis-Hastings (MH) sampling  algorithm. The technical method is novel and shown to be effective empirically.", "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": "\nBased on MH algorithm, this paper provides a data augmentation method for training GNNs under semi-supervised setting. Overall, the technical contribution is clear and the empirical study can demonstrate the effectiveness of the proposal.\n\n\n#######\n\nPros:\n\n(1) This work forms the data augmentation for graphs as a MCMC sampling process, which is new and potentially insightful to the community.\n\n(2) To utilize MH algorithm for sampling, this work defines reasonable target distribution and proposal distribution, which are the key points that make the proposal work.\n\n(3) The experimental results can show the effectiveness of the proposed data augmentation method. The ablation studies and the visualizations are pretty good for understanding.\n\n########\n\nCons:\n\n(1) The proposed method is a MCMC-based method, which is assumed to be time-consuming. However, there is no theoretical or/and empirical analysis of the efficiency of the proposed method.\n\n(2) The proposed regularizer terms, especially the term $L_u$, are quite interesting. But the description for this is very limited. For example, since $L_u$ includes model output from both $t$ and $t+1$ steps, more explanation on how to do optimization/back-propagation is necessary.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed to do graph data augmentation with a carefully designed target distribution and the corresponding proposal distribution. The experiments show that the proposed augmentation method can be more effective than existing baselines. During the rebuttal period, all the reviewers found that the authors have effectively resolved their concerns, and are generally positive about the paper. Personally I also like the design of the target distribution which is the key insight of the paper. However none of us are super excited about the outcome, partially due to the significance of the contribution and the potential implication for more general settings. Nevertheless, this paper is a sound contribution in the current scope. No matter of the outcome, we highly encourage the authors to incorporate the additional experiments and clarifications in to the revision of the paper to make it more solid.
Decision: Accept (Poster)