Knowledge Distillation Improves Graph Structure Augmentation for Graph Neural Networks
Authors: Lirong Wu
Haitao Lin
Yufei Huang
Stan Z. Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Structure Augmentation
Graph Neural Networks
Graph Knowledge Distillation

Abstract: Graph (structure) augmentation aims to perturb the graph structure through heuristic or probabilistic rules, enabling the nodes to capture richer contextual information and thus improving generalization performance. While there have been a few graph structure augmentation methods proposed recently, none of them are aware of a potential negative augmentation problem, which may be caused by overly severe distribution shifts between the original and augmented graphs. In this paper, we take an important graph property, namely graph homophily, to analyze the distribution shifts between the two graphs and thus measure the severity of an augmentation algorithm suffering from negative augmentation. To tackle this problem, we propose a novel Knowledge Distillation for Graph Augmentation (KDGA) framework, which helps to reduce the potential negative effects of distribution shifts, i.e., negative augmentation problem. Specifically, KDGA extracts the knowledge of any GNN teacher model trained on the augmented graphs and injects it into a partially parameter-shared student model that is tested on the original graph. As a simple but efficient framework, KDGA is applicable to a variety of existing graph augmentation methods and can significantly improve the performance of various GNN architectures. For three popular graph augmentation methods, namely GAUG, MH-Aug, and GraphAug, the experimental results show that the learned student models outperform their vanilla implementations by an average accuracy of 4.6% (GAUG), 4.2% (MH-Aug), and 4.6% (GraphAug) on eight graph datasets.

Knowledge Distillation Improves Graph Structure Augmentation for Graph Neural Networks
Lirong Wu 1.2 Haitao Lin 1.2 Yufei Huang 1.2 and Stan Z. Li If
AI Lab, School of Engineering, Westlake University 2 College of Computer Science and Technology, Zhejiang University (wulirong, 1 innaitao, huangyufei, stan. zq. @west la ke. edu
Abstract
Graph (structure) augmentation aims to perturb the graph structure through heuristic probabilistic rules, enabling the nodes to capture richer contextual information and thus improving generalization performance. While there have been a few graph structure augmentation methods proposed recently, none of them are aware potential negative augmentation problem, which may be caused by overly severe distribution shifts between the original and augmented graphs. In this paper, we take an important graph property, namely graph homophily, to analyze the distribution shifts between the two graphs and thus measure the severity of an augmentation algorithm suffering from negative augmentation. To tackle this prob- lem, we propose novel Knowledge Distillation for Graph Augmentation (KDGA) framework, which helps to reduce the potential negative effects of distribution shifts, i.., negative augmentation problem. Specifically. KDGA extracts the knowl- edge of any GNN teacher model trained on the augmented graphs and injects it into partially parameter-sharees student model that is tested the original graph. As a simple but efficient framework, KDGA applicable to a variety of existing graph augmentation methods and significantly improve the performance of various GNN architectures. For three popular graph augmentation methods, namely GAUG, MH-Aug, and GraphAug, the experimental results show that the learned student models outperform their vanilla implementations by an average accuracy of 4.6% (GAUG), 4.2% (MH-Aug), and 4.6% (GraphAug) on eight graph datasets. Codes are available at: https: /ttp://ittttt highhb....... com/ wttp:/iionnna/aa/a/ /KGGA.
Introduction
In many real-world applications, including social networks, chemical molecules, and citation net- works, data can be naturally modeled as graphs. Recently, the emerging Graph Neural Networks (GNNs) [4, 13, 48, 47, 22, 24, 28, 29] have demonstrated their powerful capability due to their supe- rior performance in various graph-related tasks, including link prediction [59], node classification [21,50], and graph classification [7]. Despite their great success, GNNs usually suffer from weak generalization due its heavy reliance the quantity of annotated labels and the quality of the graph structure. To boost generalization capabilities, natural solution is to increase the amount of training data by creating plausible variations of existing data, which have been widely adopted in fields such as computer vision [33, 30, 9, 39, 25, 31, 26, 27] and natural language processing [46, 1, 36, 5, 34].
The data augmentation graphs can be mainly divided into two branches: node feature augmentation and graph structure augmentation. While the former has been well studied by directly extending existing approaches for image and text data to graph data [56, 19, 15]. comparatively little work has been done to study graph structure augmentation [35, 2, 62, 32). Following the nomenclature of existing works [62, 32], we directly abbreviate graph (structure) augmentation to graph augmentation
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for the sake of brevity in this paper. The purpose of graph augmentation is to reasonably perturb the graph structure through heuristic or probabilistic rules, enabling the nodes to capture richer contextual information and thus improving generalization performance. For example, DropEdge [35] randomly removes a fraction of edges before each training epoch, in an approach reminiscent of dropout [40]. Besides, AdaEdge [2] iteratively adds (removes) edges between nodes predicted to have the same (different) labels with high confidence. In contrast to these heuristic methods, GAUG [62] proposes to optimize the graph augmentation and GNN parameters in an end-to-end manner. Similarly, MIl-Aug [32] proposes novel framework that draws a sequence of augmented graphs from an explicit target distribution, which enables flexible control of the strength and diversity of augmentation.
In this paper, we identify a potential negative augmentation problem for existing graph augmentation methods, i.c., the augmentation may cause overly severe distribution shift between the augmented graphs used for training and the original graph used for testing, which leads to suboptimal general- ization. Moreover, we conduct extensive experiments to demonstrate the existence and hazard of distribution shifts and find that the direction of distribution shifts may be opposed on homophily and heterophily graphs. We propose solution to the identified problem by adopting Knowledge Distillation for Graph Augmentation (KDGA) framework, which helps to reduce the potential nega- tive effects of distribution shifts. Specifically, it extracts the knowledge of any GNN teacher model trained on the augmented graphs and injects it into a partially parameter- shared student model that is tested the original graph. As a general framework, KDGA can significantly improve the vanilla implementations of various popular graph augmentation methods and GNN architectures.
Our contributions are summarized as follows: (1) We are the first to identify potential negative augmentation problem for graph augmentation, and more importantly, we have described in detail what it represents, how it arises, what impact it has, and how to deal with it. (2) We proposes a novel Knowledge Distillation for Graph Augmentation (KDGA) framework for the identified problem by directly distilling contextual information from augmented graphs. (3) We provide comprehensive experimental results showing that KDGA is applicable to a variety of graph augmentation methods and GNN models; it substantially outperforms the vanilla implementations across various datasets.
2 Background and Related Work
Structure Augmentation for Graphs. Data augmentation is an effective technique to improve generalization. Despite the great progress on node feature augmentation [56, 19, 15], comparatively little work study graph (structure) augmentation [35, 2, 62,32, 6] due to the non- non-Euclidean property of structures. For graph data, the mainstream algorithms for structure augmentation are divided into two categories: heuristic and learning- based. As typical heuristic algorithm, DropEdge [35] randomly remove edges according to the hand-crafted probability. In a similar way, AdaEdge [2] iteratively adds (removes) edges between nodes predicted to have the same (different) labels. Different from the above heuristic methods, GAUG [62] propose to optimize the graph augmentation and learnable GNN parameters in an end-to-end manner. Instead, MH-Aug [32] proposes sampling- based augmentation, where a sequence of augmented graphs are directly drawn from an explicit target distribution.
Graph Structure Learning and Graph Contrastive Learning. Two closely related topics to graph augmentation are Graph Structure Learning [18, 23, 58, 20, 3] and Graph Contrastive Learning [19, 15, 57, 51, 63, 52], but they are quite different in terms of learning objectives and evaluation protocols. The learning goal of structure learning is to estimate a new structure with high quality [10,8) 8]. Instead, graph augmentation aims to reasonably perturb the graph structure during training to produce a set of augmented graphs, enabling nodes to receive richer contextual information; such augmentations allow the model to generalize better across those variations. As for the evaluation protocol, the augmented graphs are only used during training and are not available during testing. In contrast, for graph structure learning, the learned structure is used during both training and testing.
There are also some recent works [41, 65, 55] exploring how to perform data augmentation for graph contrastive learning, but they focus on automatically selecting the most appropriate transformations from given pool to improve contrastive learning, rather than learning customized augmentation strategies for GNNs. More importantly, graph contrastive learning aims to learn transferable knowl- edge from abundant unlabeled data an unsupervised setting and then generalize the learned knowledge to downstream tasks. Instead, graph augmentation usually works in semi-supervised

---

setting, i.e., the label information is available during training. The graph structure learning and contrastive learning are not newly born topics, and we refer readers to the recent surveys [49, 64].
3 Preliminaries
Notions. Given a graph G = (V,E), E), where V is the set of N = |V] nodes with features X [x1, xg...., E R xd and & denotes the edge set. Each node v E V is associated with a d d-dimensional features vector x,, and each edge ei E denotes connection between node v, and Uy. The graph structure can also be denoted by an adjacency matrix A E [0, 1] with Ai, = 1 ei, E and Aij = if Ei.j & E. Consider a sumi-supervised node classification task where only a subset of node VL with corresponding labels 3/2 are known, we denote the labeled set as DL= = (VL, and unlabeled set as Du = (Vy.Ju where Vy = VL The node classification task aims to learn mapping + V + y labeled data Dr, so that it can be used to infer labels Ve-
Background on Graph Homophily Ratio. The homophily ratio is an important graph property that reflect the extent to which the graph structure adheres to the "label smoothness" criterion. The graph homophily ratio r can be defined as the fraction of intra-class edges the graph, as follows
(((,,)) (1,5) E A yi = ツ3} [1]
where ys and Vy the ground-truth labels of node es and Vy- In practice, the distribution space size of a discrete graph structure A E [0, 10.1 is 22², making it tractable to directly estimate the distribution differences between two discrete graph structures. In this paper, we take the graph homophily as a desirable option to analyze the distribution shifts between the original and augmented graphs, thus measuring the severity of an algorithm suffering from the negative augmentation problem.
Methodology
In this section, first make problem statements for graph augmentation in Sec. 4.1, highlight our motivations by analyzing the distribution shift between the original and augmented graphs in Sec. 4.2, then present a novel teacher-student Knowledge Distillation for Graph Augmentation (KDGA) framework in Sec. 4.3, and finally provide one of its specific instantiations in Sec. 4.4.
4.1 Problem Statement
Graph Representation Learning. From the perspective of statistical learning, the key of node classification to learn a mapping p(Y | X, A) based on node features X and graph structure A. The learned mapping can be used to infer labels Yo the graph structure A as shown in Fig. ((a).
Graph Structure Learning. The goal of graph structure learning is estimate a more accurate structure A by another mapping p( A X, A) and then feed into the mapping p(Y X, A) along with node features X. Finally, the learned mapping p(Y X, A) can be used to infer labels Vhu on the estimated (high-quality) structure Å instead of the original strucute A shown in Fig. 1(b).
Graph Augmentation. Instead of directly working with the original graph, we would like to leverage graph augmentation to reasonably perturb the graph structure and learn more generalizable representations. In other words, we are interested in the following variant, as follows
P X,A)
Σ
P(Y X,Â)p(A X.A)
A
where À E [0, NJNN is the augmented graph (structure). In practice, the distribution space size of À is 222 and it is intractable to enumerate all possible A as well as estimate the exact values of the mappings p( X, A) and p( X, A). Therefore, we approximate them by tractable functions as A)
P A) = Σ go X
Acjo.I]NxN
where (-)-) and (-(+) are approximation functions for p(Y X, A) and p(A X, A) parameterized by 0 and o. respectively. In practice, the function QY X. A) can be generally implemented by
3

---

Original Strudture
Loss Function
Original Structure
Estimated Structure Á
Function
+
GNN
Structure Leariing
GNN Classifier
+
Classifirr
Ranl
P
A(
(a) Graph Representation Learning
(b) Graph Structure Learning
Original Structure A
Original Structure A
Student
Loes
Loss Fundion
1
Graph Augmentation
GNN Classifier
Graph Augmentation
KL-divergence
Training Flow
p'A X. A)
p X, A)
Testing Flow
AYX,A)
Teacher Modal
Lose
Augmented Structure Á
Augmented Structure
(c) Graph Augmentation
(d) Knowledge Distillation for Graph Augmentation (KDGA)
Figure I: Illustrations of graph representation learning, graph structure learning, graph augmentation, and the proposed KDGA framework. For the sake of chart brevity, we omitted the node features X.
GNNs, and the function 4e (À X, A) can be implemented by graph augmentation methods model the distributions of augmented graph structures. Once the model training is finished, the mapping qe (Y X, A) can be used to infer labels Vu on the original structure A as shown in Fig. I(c).
In summary, unlike graph representation and graph structure learning that leverage the same struc- ture (A or Á) for both training and testing, the graph structures for training and testing graph augmentation are completely different, which may lead to potential negative augmentation problem.
4.2 Motivation: Potential Negative Augmentation Problem
One may create a model by specifying specific implementations for functions (Y X, A) and g A X, A) and then optimize it by maximizing the posterior p(Y X, A) defined in Eq. (3). As will explain here, however, this model may suffer from potential negative augmentation problem caused by overly severe distribution shifts between the original and augmented graphs.
Class Co Cj
C2 Cluss
Class C2
Closs C2 Class
Distriuzion
Ci
Cj
Class Cz
Chass C2
Class C1
Class
Cil Wascinnn
Cl
2amn
Original
Distribution Shift
Augmested
0.0
1.
flarepnlly Criph
(a) Distribution shift the real-world Wisconsin dataset
(b) Statistics of homophily ratios
Figure Illustrations of how distribution shift is arising and how it behaves on different datasets.
The distribution shift itself necessarily harmful: it is actually neutral phenomenon. A proper distribution shift helps the model "see" more different graphs, enabling the nodes to receive more contextual information, thus improving generalization; however, an overly severe distribution shift can lead to potential negative augmentation problem. To illustrate it, we consider node (id 129) of class C1 from the real-world Wisconsin dataset in Fig. 2(a), it initially connected to node with the same class C and three nodes from another class C2 in the original structure A. During the training process, the original structure A and node features X are fed together into 9 X, A) to generate an augmented structure A. Under the downstream supervision, disconnects from three nodes from class C2 and reconnects with three nodes from the same class C1 resulting in an

---

augmented structure A with much higher homophily ratio, that is, an overly severe distribution shift between the original and augmented graphs from the perspective graph homophily property. As a result, a model trained on the augmented structure A can successfully predict node as class C₁ but make wrong prediction C2 for node i when tested on the original structure A, which is termed as "negative augmentation". ". Furthermore, we plot the homophily ratios of the original structure A and augmented structure A on eight datasets in Fig. 2(b). from which we can observe significant distribution shifts between the two graphs. Moreover, while the above analysis developed on heterophily (Wisconsin) graph, we find that the identified distributional shift also exists in homophily graphs, only in a different direction. Please see Sec. 5.3 for detailed experimental settings and results.
4.3 Knowledge Distillation for Graph Augmentation (KDGA)
The distribution shift is essentially a trade-off between better generalizability and higher risks of negative augmentation. However, the optimal distribution shift may vary from dataset to dataset, or even from node to node, making it challenging to directly control the levels of distribution shifts. In this paper, we have not attempted to control or prevent distribution shifts. Instead, we allow for the existence of any level of distribution shifts, but we reduce their negative impact, i.e., the potential negative augmentation problem, by the proposed KDGA framework, which gradually distills the contextual information from the augmented graphs into a student model tested on the original graph. The idea of KDGA is straightforward, yet as we will see, extremely effective. In our case, we first generate soft distributions z and z for node U, with the teacher and student models, respectively. The knowledge distillation is first introduced in [14]. where knowledge was transferred from a cumbersome teacher to a simpler student by optimizing the following objective function, as follows
LKD = VI
Σ DKI. (softmax (z?) softmax (z,) 1EV
In this paper, not to get a simpler student model, we adopt the knowledge distillation framework to address the identified negative augmentation problem caused by overly severe distribution shifts between the two graphs. In short, we extract the knowledge of any teacher model trained on the augmented graphs and inject it into student model tested on the original graph as in Fig. 1(d).
Teacher Model. The teacher model can be implemented by any GNN, which takes node features X and augmented structure Å as input and learn latent node representations via neighborhood feature aggregation. Considering L-layer GNN fo VX, A), the formulation of the I-th layer is as follows
(0 h (1+1) UPDATE()) (h AGGREGATE (fnfi:: E {)a))) T,T
where 0 S 1, h x; the input feature, and N² is the neighborhood of node 8, in the augmented structure A. After pesssage-passing layers, the final node embedding h is passed to a linear prediction head gf to obtain logits x! = 9 (h())) ) and the model is trained by cross- entropy loss H((-) with ground-truth labels V/z, given by C Σtev, H (y:: softmax (z.)).
(0)
Student Model. The student model fo(X, A) shares the parameters 0 with the teacher model, but differs in that the it takes the original structure A as input, shown in Fig. 3(c). Besides, additional linear prediction head g (-) is used to map the node embedding h to logits z = g (h(43). ). As already explained earlier, the augmented graphs enable the teacher model to receive richer contextual information, which helps to improve model generalization. To allow the student model tested on the original structure to also benefit from it, we consider the contextual neighborhood information from both original and augmented structures and distill them into the student model, defined as
-? M
LOKD
Σ Σ LEV
DEL (softmax (z,, mm] sootmmax (2 (m)/
(6)
JE(NAANAJUU
where 7i is the distillation temperature, and of is used to keep the gradient stability of this loss [14]. Discussions. While a large number of methods on graph knowledge distillation [61, 53, 60] have been proposed, most of them adopt the standard teacher-student knowledge distillation framework
5

---

as shown in Fig. 3(a), where the imputs to both teacher and student models are the same (structure). Despite many progresses, their contributions have mostly focused on the special design of the teacher or student models. For example, CPF [54] proposes to distill knowledge from teacher GNN to student MI.P, but specifically incorporates lahel propagation [16] into the student model to improve performance. In contrast, GDK [11] utilizes label propagation in the teacher model to fully exploit both feature and topological information. our proposed KDGA framework, the graph structures fed to the teacher and student models are completely different. Moreover, unlike the scheme in Fig. 3(b) where two aarameter-indepedder teacher and student models are used, we adopt the architecture shown in Fig. 3(c) where the GNN parameters shared but with two independent prediction heads to increase discriminability. The behind motivation that parameter- parameter-independenn independent student model has the risk of quickly fitting with the original structure under the optimization of downstream supervision, while failing to take full advantage of rich contextual information from the augmented graphs. A detailed comparison of parameter-independee and parameter-shared schemes is reported in Table. 2.
KL-chvergaree
KL-chvargence
vergeeeee
Modal
Teachier Mudio
Stadent Model
Teacher Model
Student Model
Teacher Model
Partonaliee Stramed
t
t
Uoimyssllng udoi
Orignal Graph A
Original Graph A
Origiaal Graph A
Augmented Graph
Á
Original Grach A
Augmented Graph
(a) Standard Scheme
(b) Parameter- Teddeeter-ndeeendentt (Param-I)
(c) Parameter-Share (Param-S)
Figure 3: (a) standard teacher-student distillation; (b) distillation with parameter-independdnt teacher and student models; (c) distillation with parameter-shared teacher and student models.
4.4 Instantiating KDGA with GraphAug
In practice, any existing graph augmentation method can be used to instantiate the proposed KDGA framework and achieve consistent improvements over the vanilla implementations, as shown in Table. 1. In this subsection, we adopt probabilistic generative-based graph augmentation method to model the function qa À X, A), termed GraphAug, and use it instantiate KDGA framework. Specifically, we introduce a set of discrete variables A {Xi,) i.j to model the distribution of the augmented graph, where As {0, 1} denotes the augmentation probability between node and Uy- Moreover, we avoid estimating the probability p (Ai.) (4.j) using independent local parameter jiij and instead fits shared neural network estimate it. Specifically, we first transform the input to low-dimensional hidden space, done by multiplying the node features with a parameter matrix W E Fxd, that e; = Wa,, Then, we directly parameterize the probability Ài.j as
((us A) = (e.e,)
where (-) is an element-wise sigmoid function. Next, sample discrete augmented graphs from the learned augmentation distribution and make the sampling process differentiable, we adopt Gumbel- Softmax sampling [17]. Specifically, the sampling process can be formulated as
Arj=
1 2 where M.,, = axp (Mi.s X, A) + - (1)))))))) Aij
(8)
+ exp exp MG,
where E [0. is the fusion factor to control the intensity of the graph augmentation, Ta is the augmentation temperature, and G (0, 1) is a gumbel random variate.
To warm-up the proposed GraphAug module, we first pre-train it with loss L NY H(A,, Aig). where H(-) denotes the cross-entropy loss. Besides, we use classification loss Lote M. Eter, (H (y,, softmax(z?)) 7. (y,, softmax(z))) ) to pre-train the teacher and student mod- els until converges. Finally, the total loss train the whole framework detined as follows
Liotal Lete + AL + KLGKD
(9)
where À and k are the weights balance the influence of the two losses Lang and LOKD.

---

Table 1: Accuracy + std (%) eight datasets (as well their homophily ratios), with three GNN
architectures and five graph augmentation methods considered. The best metrics are marked by bold.
BaseGNN
Method
Cora
Citeseer
Cornell
Chameleon
Squirrel
Actor
Wisconsin
Texas
0.81
0.74
0.30
0.23
0.23
0.22
0.21
0.11
Vanilla
81.5=as
71,6403
57.0=47
59.8+26
36.9
30.3+05
59,8=70
59.5=53
DrapEdge [35]
82.2=07
71,9403
59.3=39
61.2+18
38.1
30.9+1.0
61.8:54
62.3:46
AdaEidge [2]
82.3ga8
69.7109
57.8
59.5123
37.6114
31,4111
60,4
58.8140
SSL. [63]
83.8aa7
72.9
58.8232
60.4g31
39.5
30.5a12
62.8
63.3
GraphMix [44]
83,920
74.7:14
60.5a37
61.2111
41.1
31,4109
62.4250
62.3148
GCN
GAUG [62]
83.6:05
73.3
$5.8240
19.3
36.3
29.7a:.
$7.5:51
58.0s42
GAUG (w/ KDGA)
85.4
73.6106
63.2,86
63.0
46.2gn9
33.3
65.0g24
67.4
1.8
0.3
7.4
3,7
9.9
3.6
7.5
9.4
MH-Aug [32]
83.62n3
73.0ans
58.4
59.2a30
35.9
31.2207
18.1
58.9239
MH-Aug (W/ KDGA)
85.0=a5
73.8+00
63.5-27
63.3+17 4.1
45.4
34,8+1
65,7=27
67.2+26
A Ane
1.4
0.8
5.1
9.5
3.6
7.6
8.3
GraphAug
83.2=n9
73.2+0a
56.6=24
58.8+18
37.2+12
28.8 28.8+09
59.3=26
59.4233
GraphAug (w/ KDGA)
85,2=a7
73,9
63.8 7.2
62.7 3.9
46,92as 9.7
32.5+as 3.7
66.3 6.9
68.0:13
AA
2.0
0.7
8.6
Vanilla
79.8
71.1
76.0250
58.7
41 6.n7
34.2+10
81.2:
82.4
DropEdge [35]
8044ass
71.5+06
77.4=36
60.2+22
42.5+13
36.4+113
82.7=44
83.0a4s
AdaEdge [2]
80.2=1.2
69.4404
76.5544
59.5
40.3
34.9208
82.0=53
81.6s53
SSL]
82.5.n8
71.2
76.8234
59.1
42.0g15
35.2111
82.4
82.6244
GraphMix [44]
82.3206
69.6104
78.0247
59.9130
42.6216
35.8110
83.1241
83.5239
SAGE
GAUG [62]
82.0ans
72.7
74.8
58.2113
40.5
34.4111
80.7.44
82.0g45
GAUG (w/ KDGA)
84.5ans
73.4207
80.6g35
61.8216
46.4:11
36,4107
85.5.33
84.5
A
2.5
0.7
5.8
3.6
5.9
2,0
4.8
2.5
MH MHg-Agg [32]
82.6ga7
72.1
75.3g39
59.4215
41.0anK
33.810s
80.5
81.2
MH-Aug (w/ KDGA)
84.3ga7
73.7
80.3g32
62.1
45.9
35.9107 2.1
84.9.4
83.8
A Ace
1.7
1.6
5.0
2.7
4,9
4.4
2.6
GraphAug
82.4110
72.4
75. 75.8
58 8:14
40.2a13
33.2407
79.9a42
81.9246
GraphAug (w/ KDGA)
84,8=as
73,5+03
81.4=28
61.0=1s 2,2
45 45.6ea> 5.4
36,9114 3.7
84,5=33
84,8=38
AM
2.4
1.1
5.6
2.9
Vanilla
82.2gn5
71.4
58.9233
$4.7110
30.6121
26.3111
$5.3.87
58.4245
DropEdge [35]
83.0.n4
72.2a08
60.2a58
55.6115
34.1
28.2415
57.8
60.5
DropEdge [35]
77.9=20
69.1
57.7=45
54.0+12
32.8=2b
27.5+14
56,4=6.
57.8242
SSL [63]
83,7=a6
72.7+0.
60.6#32
55.8+22
35.0a1.
27.6+11.
57.2+51
60.5233
GraphMix [44]
83,3g02
73.1
61.0241
$6.4117
35.6119
28.7100
58.5
61.1
GAT
GAUG [62]
82,2=as
71.6
$7.6238
$3.4114
30.1
25.8
$4,8
56.9236
GAUG (w/ KDGA)
84.2.11
73.0uod
62.2
58.2111
39.1
31,3111
60.9.s
63.1
A
2.0
1.4
4.6
4,8
9.0
5.5
6.1
6.2
AH- [32]
83.5gn7
72.8210
58.0240
55.3g18
29.5g11
25.7a1a
55.8
57.8 47.8
MH-Aug (w/ KDGA)
84.5=n9
73.4+44
62.7=28 4.7
89,5=:16 4,2
37.3aus 7.8
30.8s09 5.1
61,450
64,4=18
Ase
1.0
0.6
5.6
6.6
GraphAng
83.2.n8
72.5
58.6234
54.0111
29.8118
24.8113
54.4
57.1
GraphAng (w/ KDGA)
84,7=a7
73.2a0a
63.1
58. 58.8
38.9214 9.1
30.0a10 5.2
61.8-47
62.7g20
Are
0.7
4.8
7.4
5.6
Experiments
Datasets. The effectiveness of the proposed KDGA framework is evaluated on eight datasets. We use two commonly used homophily graph datasets, namely Cora [38] and Citeseer [12] as well as six heterophily graph datasets: Cornell, Texas, Wisconsin, Aactor [42], Chameleon and Squirrel [37]. A statistical overview of these datasets is available in Appendix We defer the implementation details and the best hyperparameter settings for each dataset to Appendix B and supplementary material.
Baselines. As a general framework, KDGA can be combined with any GNN architecture and existing graph augmentation methods. In this paper, we consider three GNN architectures, GCN [21], GraphSAGE [13], and GAT [43]. Besides, to demonstrate the applicability of KDGA various graph augmentation methods in addition to the proposed GraphAug, we also consider two state- of-the-art learning-basse based baselines, GAUG [62] and MH-Aug [32]. In particular, two heuristics methods, DropEdge and AdaEdge, are also included in the comparison as baselines. Moreover, we also compare KDGA with two semi-supervised methods: (1) GraphMix [44], regularization method that performs linear interpolation between two data on graphs, and (2) SSL [63], that proposes two supersupe tasks to fully exploit available information embedded in the graph structure. Each set of experiments is run five times with different random seeds, and the average performance is reported.
7

---

5.1 Comparative Results
To evaluate the powerful capabilities of the proposed KDGA framework, we instantiate it with three learning-based graph augmentation methods, GAUG, MH-Aug, and GraphAug. The experiments conducted on eight datasets with three different GNN architectures. From the experimental results shown in Table. I, we can make the following observations: (1) Two heuristic graph augmentation methods, DropEdge and AdaEdge, can improve the performance of the vanilla GNNs overall. However, such improvements are usually very limited and do not work for all datasets and GNN architectures. For example, on the Citeseer dataset, the performance of AdaEdge drops over the vanilla GNNs by 1.9% (GCN), 1.7% (GraphSAGE), and 2.3% (GAT), respectively. (2) There are huge gaps in the effectiveness of three learning- based augmentation methods on homophily and heterophily graphs. While these methods can significantly improve performance on homophily graphs, their performance gains on heterophily graphs are greatly reduced and even detrimental. For example, with GCN as the GNN architecture, the performance of GAUG improves by 1% on Cora, but drops by 1.5% and 1.2% on Texas and Cornell. Such negative augmentation is mainly caused by the overly severe distribution shift between the original and augmented graphs as analyzed in Sec. 4.2. (3) The proposed KDGA framework can consistently improve the performance of vanilla graph augmentation methods across three GNN architectures on all eight datasets, especially for those heterophily graphs. For example, with GCN as the GNN architecture, the performance of GraphAug can be improved by 9.7% and 8.6% on the Squirrel and Texas datasets. (4) Two eemi-supervised approaches, SSL and GraphMix, can achieve comparable even better performance than learning- based graph augmentation, especially on heterophily graphs. However, by combining with KDGA, GAUG, MH-Aug, and GraphAug outperform both SSL and GraphMix by a large margin overall.
Original
Graph
Augmented
Graph
Cors (il 1617)
Citesoer 1945)
Wiscomsin 129)
Actor 2554)
Chamoleon (id 1088)
Squiree 1516)
Figure 4: Case studies for each dataset, where we pick node with the most drastic neighborhood variations and visualize its neighborhood on the original graph structure (top) and augmented graph structure (bottom), where each node is colored according to its ground-truth label.
5.2 Analysis on the Distribution Shift and Negative Augmentation
Next, we qualitatively and quantitatively analyze the distribution shift between the original and augmented graphs and explain how it can cause a potential negative augmentation. Without loss of generality, we consider GCN as the GNN architecture and GraphAug as the augmentation method.
Visualizations of Neighborhood Variations. First, we pick a node with the most drastic neighbor- hood variations and visualize its neighborhood of the original and augmented graphs in Fig. 4, where each node is colored according to ground-truie label. The visualizations show that there would be a huge gap between the neighborhoods of the original and augmented graphs, which causes model that well trained on the augmented graph to predict poorly on the original graph during testing. Taking the Wisconsin dataset an example, the selected node is connected to four nodes from the same class in the augmented graph, so it can be well trained to make correct predictions. However, its neighborhood context is completely changed in the original graph, where the node is connected to three nodes from different classes, so it will be predicted with high confidence to an incorrect class.
We plot in Fig. 5 the training curves (w/o GKD Loss) of the homophily ratios of the original and augmented graphs during training. It can be seen that their gaps are enlarged as training proceeds, which indicates that the distribution of the augmented graphs is gradually shifting from the original graph. This shift may even reach 0.5 for some datasets (e.g., Texas), in which case the graph homophily property is completely reversed. More importantly, we find that the direction of distribution shifts may be completely opposite for homophily and heterophily graphs, which makes it more challenging to solve the negative augmentation problem.
Training Curves of Homophily Ratios.
8

---

2.3
Cora
5.5
Comeel
0.
Wisconsin
7073
Exprass bnd
0.62
Augar
Sporn
Spocha
Spocts
Actor
Chame
0.20
Squiirrl
mumstar
0.5
Nug serded umic
Augina lin visse
1.0 Dpsics
100
105
200
300
40c
465
Spachs
Specrs
Spachh
Figure 5: Training curves (w/ GKD Loss) of homophily ratios in the original and augmented graphs.
5.3 Ablation Study and Parameter Sensitivity
Ablation on Student Model Designs. The parameter-shared GNN shown in Fig. 3(c) is adopted as the student model by default
Table 2: Ablation study student model designs.
Method
Cora
Citeseer
Chameloon
Squirrel
Actor
Vanilla GCN
81.5
71.6.43
59.8116
36.9113
30.3
in this paper for fair comparison. In this subsection, we delve into the applicability of the proposed KDGA framework to dif- ferent student model designs. Specifically, with the vanilla GCN as the base architecture and GraphAug as the graph augmentation method, we compare the performance of the parameter-shared model (w/ Param-S) in Fig, 3(c) and the parameter-inneeeedder model (w/ Param-I) in Fig. 3(b) on five datasets. It can be seen from Table. 2 that although the Param-I model can also improve the performance of GraphAug overall, it may fail on few datasets, such as 0.5% accuracy drop on Citeseer; more importantly, its performance gain falls far behind the Param-S model on all five datasets. The reason behind this may be that parameter-inddeeedeer model may be quickly fitted with the original graph structure while failing to take full advantage of the rich contextual information embedded in the augmented graphs. Moreover, model by directly taking a parameter-independen. MIP (w/ MLP) as the student mode. We find from Table. 2 that even with a simple MLP, it can still benefit from the augmented graphs and achieves performance beyond that of its vanilla implementations.
GraphAng
83.2sse
73.2
58.8a1a
37.2
28.8
KDGA Param-S
85.2as7
73,9
62.7a18
46.9.ns
32.5
A
2.0
0.7
3.9
9.7
3.7
KDGA w/ Param-I
84,0=aa
72.7 -0.5
60.6 1.8
40.5a1a 3.3
30.7
Adt
0.8
1.9
Vinilla MLP KIXIA w/ MLP
55.2dss
46.5
46.4:1
29.7
35.8
83.221
73.5
18.1
88
38 1an
Ade
28.0
27.0
11.7
2,3
also consider variant of the Param-I
Sensitivity Analysis on Hyperparaaeetes. We have evaluated the parameter sensitivity w.r.t two key hyperparameters: fusion factor a and loss weight k. However, due to space limitations, we have placed the corresponding results of sensitivity analysis in Appendix C.
6 Conclusion
In this paper, we identified a potential negative augmentation problem for graph augmentation, which is caused by overly severe distribution shifts between the original and augmented graphs. To address this problem, we propose a novel Knowledge Distillation for Graph Augmentation (KDGA) framework by directly distilling contextual information from teacher model trained on the augmented graphs into a partially parameter-share student model. Extensive experiments show that KDGA outperforms the vanilla implementations of existing augmentation methods and GNN architectures. Limitations still exist, such as KDGA requires an initial raw graph structure for augmentation and cannot be applied to those structure-ung unnttor scenarios, which will be left for future work.
7
Acknowledgement
This work is supported in part by Ministry of Science and Technology of the People's Republic of China (No. 2021 1 YFA 1301603) and National Natural Science Foundation of China (No. U21A20427).

---

References
[1] Markus Bayer. Madr- Kaufhold, and Christian Reuter. A survey data augmentation for text classification. arXiv preprint arXiv:2107.03/58 2021.
[2] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3438-3445 3445, 2020.
[3] Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in Neural Information Processing Systems, 33:19314-19328 2020.
[4] Michaäl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv preprint arXiv: (eo::00077777 2016.
[5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirec- tional transformers for language understanding. arXiv preprint arXiv: 1810.0400 2018.
[6] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. arXiv preprint ar arXiv:2202.008: 08235, 2022.
[7] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.0998 0991199999.999,..... 2019.
[8] Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. arXiv preprint arXiv:2102.05034 000000 2021.
[9] Alhussein Fawzi, Horst Samulowitz, Deepak Turaga, and Pascal Frossard. Adaptive data augmentation for image classification. In 2016 IEEE international conference on image processing (ICIP), pages 3688-3692. Ieee, 2016.
[10] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. International conference on machine learning, pages 1972-1982, PMLR, 2019.
[11] Mahsa Ghorbani, Mojtaba Bahrami, Anees Kazi, Mahdich Soleymani Baghshah, Hamid R Rabice, and Nassir Navab. Gkd: supi-supervised graph knowledge distillation for graph-independent inference. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 709-718. Springer, 2021.
[12] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[13] Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs In Advances in neural information processing systems, pages 1024- 1034, 2017.
[14] Geoffrey Hinton, Oriol Vinyals. Jeff Dean, et al. Distilling the knowledge in neural network. arXiv preprint arXiv: 503.00331.. 2(7), 2015.
[15] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint 19Xi:1905.11266 2019.
[16] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi- supervised learning. In Proceedings of the ILEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5070-5079, 2019.
[17] Fric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax, arXiv preprint 161 1.01 144, 2016.
[18] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. supervupe learning with graph learning- convolutional networks. In Proceedings of the IEEE/CVF conference on computer vision and paterr recognition, pages 1 11313-11 1320, 2019.
[19] Wei Jin, Tyler Dem,, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised lcarning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10144,,,,,011, 2020.
[20] Wei Jin, Yao Ma. Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 66-74. 2020.
10

---

[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks arXiv preprint w0Xv:1100.002007, 2016.
[22] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann, Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018
[23] Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in Neural Information Processing Systems, 32, 2019.
[24] Meng Liu, Hongyang Gao, and Shuiwang. Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 338-348. 2020.
[25] Xiaofeng Liu, Yang Zou, Lingsheng Kong, Zhihui Diao, Junliang Yan, Jun Wang. Site Li, Ping Jia, and Jane You. Data augmentation via latent space interpolation for image classification. In 2018 24th International Conference on Pattern Recognition (ICPR). pages 728 -33.. IEEE, 2018.
[26] Zicheng Liu, Siyuan Li, Ge Wang, Cheng Tan, Lirong Wu, and Stan Z Li. Decoupled mixup for data- efficient learning. arXiv preprint vrXiv:2203.00766 2022.
[27] Zicheng Liu, Siyuan Li, Wu, Zhiyuan Chen, Lirong Wu, Jianzhu Guo, and Stan Li, Unveiling the power of mixup for stronger classifiers. arXiv preprint 3rXiv:2103.13022 2021.
[28] Zihan Liu, Yun Luo, Lirong Wu, Siyuan Li, Zicheng Liu, and Stan Z. Li. Are gradients on graph structure reliable in gray-box attacks? arXiv preprint 2rXiv:2208.055144 2022.
[29] Zihan Liu, Yun Luo, Zelin Zang, and Stan Li. Surrogate representation learning with isometric mapping for gray-box graph adversarial attacks. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 591-598, 2022.
[30] Agnieszka Mikotajezyk k and Michal Grochowski. Data augmentation for improving deep learning in image classification problem. In 2018 international inten aateldiiciplinary Phl) workshop (IPPDDW), pages 117-122. IEEE, 2018.
[31] Sarah G'Gara and Kevin McGuinness. Comparing data augmentation strategies for deep image classifica- tion. 2019.
[32] Hyconjin Park, Scunghun Lee, Sihycon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung- Woo Ha, and Hyunwoo J Kim. Metropolis- data augmentation for graph neural networks, Advances Neural Information Processing Systems, 34, 2021.
[33] Lais Perez and Jason Wang. The effectiveness of data augmentation image classification using deep learning. arXiv preprint 171..0471 2017.
[34] Alce Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[35] Yu Rong, Wenhing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolu- tional networks on node classification. arXiv preprint 1907. 10903, 2019.
[36] Ryan Robert Rosario. data augmentation approach short text classification. University of California, Los Angeles, 2017.
[37] Benedek Rozemberczki, Carl Allen, and Rik Sarkar Multi-scale attributed node embedding. arXiv preprint arXiv: 13021, 2019.
[38] Prithviraj Sen. Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- -Rdd Collective classification in network data. Al magazine, 29(3):93-3) -9.,993.2222 2008
[39] Jia Shijic, Wang Ping, Jia Peiyi, and Hu Siping. Research on data augmentation for image classification based on convolution neural networks. In 2017 Chinese automation congress (CAC), pages 4165 4170. IEEE, 2017.
[40] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-199 1958, 2014.
[41] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 34, 2021.
11

---

[42] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pages 807-816, 2009.
[43] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17XX:v:1110.00003, 2017.
[44] Vikas Verma, Meng Qu, Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for cemi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10024-10032, 2021.
[45] Minjie Wang, Da Zheng. Zihao Ye, Quan Gan, Mufei Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Gai, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: graph-centric, highly-performant package for graph neural networks. arXiv preprint
2019.
[46] Jason Wei and Kai Zou, Eda: Easy data augmentation techniques for boosting performance on text classification tasks, arXiv preprint arXiv: arXiv: 1w..1/1916...6.. 2019.
[47] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. International conference on machine learning, pages 6861 6871. PMLR, 2019.
[48] Lirong Wu, Haitao Lin, Zhangyang Gao, Cheng Tan, Stan Li, et al. Graphmixup: Improving class-imbalanced node classification on graphs by self-supervised context prediction. arXiv preprint a0Xiv:2 / 11133, 2021.
[49] Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Li. Self-supervised learning on graphs: Contrastive, generative, or predictive. IEEE Transactions on Knowledge and Data Engineering, 2021.
[50] Lirong Wu, Haitao Lin, Jun Xia, Cheng Tan, and Stan ZLi. Multi-level disentanglement graph neural network. Neural Computing and Applications, 34(11))9087-910, 2022.
[51] Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, pages 1070-1079, 2022.
[52] Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan 7. Li. Progel: Rethinking hard negative mining in graph contrastive learning. In International Conference on Machine Learning, pages 24332-24346. PMLR, 2022.
[53] Beneheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygun: Learning efficient graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1848-1856, 2020.
[54] Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework. In Proceedings of the Web Conference 2021, pages 1227-1237, 2021.
[55] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pages 12121-12132. PMLR, 2021.
[56] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33, 2020.
[57] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? In International Conference on Machine Learning, pages 10871-10880. PMLR, 2020.
[58] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 378-393. Springer, 2020.
[59] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. arXiv preprint 1xXiv.180.0069)) 2018.
[60] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph less neural networks: Teaching old mlps new tricks via distillation. arXiv preprint 100.022110.00877, 2021.
12

---

[61] Wentao Zhang, Xupeng Miao. Yingxia Shao, Jiawei Jiang. Lei Chen, Olivier Ruas, and Bin Cui. Reliable data distillation graph convolutional network. Proceedings the 2020 ACM SIGMOD International Conference on Management of Data, pages 1399-1414, 2020.
[62] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. arXiv preprint 01XXi::20060068300 2020.
[63] Qikui Zhu, Bo Du, and Pingkun Yan. Self-supervised training of graph convolutional networks. arXiv preprini arXiv:2006. 023380 2020.
[64] Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure 2021.
learning for robust representations: A survey. arXiv preprint arXiv:2103.038830
[65] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and I Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Weh Conference 2021, I, pages 2069-2080, 2021.
13


Reviews:
[{"review_id": "ecibSc2BV9i", "reviewer": "Reviewer_J4nz", "summary": "The authors of the paper identify and demonstrate a negative augmentation problem in graph augmentation methods. They propose to use a knowledge distillation method to solve this problem by training a teacher model on the augmented graphs and a student model on the original graphs. Experiments are conducted on two homogeneous graph datasets and six heterogeneous graph datasets. Improved performance are observed when the knowledge distillation method is applied to three learning-based graph augmentation methods and three different GNNs.", "questions": "1. Can other techniques achieve the same effect, such as increasing regularization, increasing the diversity of the sampled augmented graphs? Could you provide a comparison with these methods?\n2. Has anyone proposed using knowledge distillation (in any way) to solve the negative augmentation problem?\n3. Can KGDA be easily applied to graph contrastive learning or any other graph application?", "limitations": "1. Evaluations are only conducted on the node classification task. Would like to see experiments on more tasks, such as edge classification, graph contrastive learning.\n2. The proposed method does not seem to address the problem that graph augmentation methods tend to increase the homophily ratio of the graphs. It is more of a regularization that guides the student model on downstream tasks.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. The authors demonstrated sound statistics and analysis of the negative augmentation problem.\n2. Extensive experimental results are presented on the node classification task, using three representative GNNs and three learning-based graph augmentation methods.\n3. The paper is well written.\n\nWeakness\n1. In Figure 3, are the inputs of the teacher model and the student model swapped?\n2. Evaluations are only conducted on the node classification task. Would like to see experiments on more tasks, such as edge classification, graph contrastive learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b5Z6xL06QV8", "reviewer": "Reviewer_SAR2", "summary": "This paper claims that they are the first in considering the distributional shift between an original and augmented graph. They propose Knowledge Distillation for Graph Augmentation (KDGA) to address the potentially negative impact of this distributional shift. The model consists of a teacher and a student model. The teacher is a GNN model that extracts information from the augmented graph and injects the knowledge into the student model which has only seen the original graph by minimizing the KL divergence of the output logits of these models. ", "questions": "-- Have the authors studied the sensitivity of the final performance on the GKD loss weight in equation 9?\n\n-- Figure 5 is showing homophily ratios in the original and augmented graphs during training w/o the GKD loss, right? If that's true, what would the trajectory look like with the GKD loss?", "limitations": "there is not social impact section in the manuscript.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n-- The paper is well-written and the authors are trying to tackle an important aspect of graph contrastive learning. \n\n-- The approach is simple and can be easily implemented in an efficient way.\n\n**Weaknesses**\n\n-- The authors should make it clear from the begining of the manuscript that by 'distribution' they mean the homophily ratios of the graph structures.\n\n-- The claim in line 63 that little work studies structure augmentation is not accurate just by considering the already cited literature. \n\n-- The claim in lines 130 and 131 that graph structures for training and testing in graph augmentations are completely different isn't necessarily true. This is a property you can control in a few graph contrastive methods and automated GCL methods might limit this issue automatically. \n\n-- typo: Figure 5 caption, \"homopgily\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YOrWOE8Fjwd", "reviewer": "Reviewer_o5A2", "summary": "This paper claims that the existing graph structure augmentation methods may cause the distribution shift issue. In this paper, the authors design a knowledge distillation based method to improve the generalization capability for graph structure augmentation.", "questions": "See the weaknesses.", "limitations": "N.A.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Authors find that the existing graph augmentation method will lead to the distribution shift problem.\n2. This paper is well-written and easy to follow\n3. The idea behind is straightforward.\n\nWeaknesses:\n1. The authors claim that Negative Augmentation will lead to poor generalization. While It does not make sense based on your experiments.  The experiments show that the existing methods do perform well than baselines. This means that if those baselines are negative augmentation, they should perform worse. Or authors may need to conduct the experiment specifically to test the generalization. \n2. While the existing methods have a big gap in homopgily ratio from the augmented to original data, but no experiments show that the proposed method does not have it. Moreover, why big gap in homopgily atio represents worse generalization capability? intuitively, a big gap in homopogily ratio can help model to ''see'' more different graphs and increase the generalization.\n3 . Typos in Table 2: GKDA -> KDGA? \n4. The novelty is limited. As the proposed KDGA is just a simple knowledge Distillation method. The authors just apply it to existing augmentation methods to achieve better performance. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "0z10qn5gJkl", "reviewer": "Reviewer_LrXs", "summary": "The authors investigate on an interesting problem for graph augmentation: distribution shift between the original and the augmented graphs. The authors leveraged knowledge distillation to narrow the distribution gaps between the original and the augmented graphs. Experiment results show that the proposed framework (KDGA) based on the existing graph augmentation algorithms achieve superior results. ", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The authors pointed out the observation that there is a distribution shift between the original graph and the augmented graph. They also proposed to use the graph homophily ratio as the metric to quantify the distribution shift. \n2. The authors illustrated the concepts and methods clearly with well presented figures. The overall presentation is good and easy to follow\n\nWeakness:\nThe proposed the KDGA framework is based on the existing graph augmentation algorithms, and the student-teacher distillation framework. Would like to see more novelty in this work.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept