Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks
Authors: Jiarong Xu
Renhong Huang
XIN JIANG
Yuxuan Cao
Carl Yang
Chunping Wang
Yang Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
pre-training
TL;DR: We propose a better-with-less framework for graph pre-training: fewer, but carefully chosen data are fed into a Graph Neural Network to enhance pre-training.

Abstract: Pre-training on graph neural networks (GNNs) aims to learn transferable knowledge for downstream tasks with unlabeled data, and it has recently become an active research area. The success of graph pre-training models is often attributed to the massive amount of input data. In this paper, however, we identify the curse of big data phenomenon in graph pre-training: more training data do not necessarily lead to better downstream performance. Motivated by this observation, we propose a better-with-less framework for graph pre-training: fewer, but carefully chosen data are fed into a GNN model to enhance pre-training. The proposed pre-training pipeline is called the data-active graph pre-training (APT) framework, and is composed of a graph selector and a pre-training model. The graph selector chooses the most representative and instructive data points based on the inherent properties of graphs as well as predictive uncertainty. The proposed predictive uncertainty, as feedback from the pre-training model, measures the confidence level of the model in the data. When fed with the chosen data, on the other hand, the pre-training model grasps an initial understanding of the new, unseen data, and at the same time attempts to remember the knowledge learned from previous data. Therefore, the integration and interaction between these two components form a unified framework (APT), in which graph pre-training is performed in a progressive and iterative way. Experiment results show that the proposed APT is able to obtain an efficient pre-training model with fewer training data and better downstream performance.

Better with Less: A Data-Active Perspective on Pre- Pre-Training Graph Neural Networks
Jiarong Xu Renhong Huang", Xin Jiang Yuxuan Cao²
Carl Yang', Chunping Wang', Yang Yang"
Fudan University, *Zhejiang University, Lehigh University 'Emory University, FFinoolution Group
j firrongxu@uudan edu. cn, frenh2, caoyx, yangya) eeteeizuuuuuue... edu. xj xjiang@lehigh, edu, j carlyanggemory. edu, vangchunping020xxne.co
Abstract
Pre-training on graph neural networks (GNNs) aims to learn transferable knowledge for downstream tasks with unlabeled data, and it has recently become active research area. The success of graph pre-training models is often attributed to the massive amount of input data. In this paper, however, data phenomenon in graph pre-training: more training data do not necessarily lead better downstream performance. Motivated by this observation, a better-with-less framework for graph pre-training: fewer, but carefully chosen data are fed into GNN model enhance pre-training. The proposed pre-training pipeline is called the data-active graph pre-training (APT) framework, and is composed of graph selector and a pre-training model. The graph selector chooses the most representative and instructive data points based on the inherent properties of graphs well as predictive uncertainty. The proposed predictive uncertainty, feedback from the pre-training model, measures the confidence level of the model the data. When fed with the chosen data, on the other hand, the pre- training model grasps an initial understanding of the new, unseen data, and at the same time attempts to remember the knowledge learned from previous data. Therefore, the integration and interaction between these two components form a unified framework (APT), which graph pre-training performed a progressive and iterative way. Experiment results show that the proposed APT is able to obtain an efficient pre-training model with fewer training data and better downstream performance.
identify the curse of big
propose
Introduction
Pre-training Graph neural networks (GNNs) shows great potential to be attractive and competitive strategy for learning from graph data without costly labels [29, 50J. Recent advancements have been made in developing various graph pre-training strategies, which aim to capture transferable patterns from a diverse set of unlabeled graph data [22, 30, 31, 44, 60, 76, 77]. Very often, the success of a graph pre- ree-training model is attributed to the massive amount of unlabeled training data, a well-established consensus for pre-tras pee-raining in computer vision [12, 19, [6] and natural language processing [11 [11,45).
In view of this, contemporary research almost has no controversy on the following issue: Is a massive amount input data really necessary, even beneficial, for pre-training GNNs? Yet, two simple experiments regarding the number of training samples (and graph datasets) seem to doubt the positive
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

bruzil
Wisconsin
umdb-binia undd-bbnarr
model model
miem FI
micro F1
24
Layer
micro
micro
layers
-oonees bull
10
10
30
10
13
10
13
13
10
10
10'
10'
samples
# of samples
of samples
of samples
brizil
Wisconsin
Imsro-21
imdh- binary
micro Fl
34
Il mitroo
mic 17
micro
std
sid :1.5
sid
skd
10 11 (L)
10
11 (10)
# of graphs
graphs
# of graphs
(48)
# of graphs
(a) Node classification
(b) Graph classification
Top row: The effect of scaling up sample size (log scale) on the downstream performance based on a group of GCCs [50] under different configurations (the graphs used for pre-training are kept as all eleven pre-training data in Table 3, and the samples are taken from the backbone pre-training model according to its sampling strategy). The results for different downstream graphs (and tasks) are presented in separate figures. To better show the changing trend, we fit curve to the best performing models (f.e., the convex hull fit as [1] does). Bottom row: The effect of scaling up the number of graph datasets on the downstream performance based on GCC. For a fixed horizontal coordinate, we run 5 trials. For each trial, randomly choose combination of input graphs. The shaded area indicates the standard deviation over the 5 trials. See Appendix for more observations on other graph pre-training models and detailed settings.
Figure 1:
answer to this question. We observe that scaling pre-training samples does not result in one-model- fits-all increase in downstream performance (top row Figure 1), and that adding input graphs (while fixing sample size) does not improve and sometimes even deteriorates the generalization of the pre-trained model (bottom row Figure I). Moreover, even the number of input graphs (the horizontal coordinate) is fixed, the performance of the model pre-traie preitrained on different combinations of inputs varies dramatically; see the standard deviation in blue in Figure 1, As the first contribution of this work, identify the curse of big data phenomenon in graph pre- preitiainn more training samples (and graph datasets) do not necessarily lead to better downstream performance.
Therefore, instead of training on massive amount of data, it is more appealing to choose a few suitable samples and graphs for pre-training. However, without the knowledge of downstream tasks, it is difficult to design new data selection criteria for the pre-training model. To this end, we propose the graph selector which able to provide the most instructive data for the model by incorporating two criteria: predictive uncertainty and graph properties. On one hand, predictive uncertainty is introduced to measure the level of confidence (or certainty) in the data. On the other hand, some graphs are inheritantly more informative and representative than others, and thus the fundamental properties should help in the selection process.
Apart from the graph selector, the pre- vre-training model is also designed to co-evolve with the data. Instead of swallowing data as a whole, the pre-training model is encouraged learn from the data in a progressive way. After learning a certain amount of training data, the model receives feedback (from predictive uncertainty) on what kind of data the model has least knowledge of. Then the pre-training model is able to reinforce itself on highly uncertain data in next training iterations.
Putting together, we integrate the graph selector and the pre-training model into a unified paradigm and propose a data-active graph pre-training (APT) framework. The term "data-active is used to emphasize the co-evolution of data and model, rather than mere data selection before model training. The two components in the framework actively cooperate with each other. The graph selector recognizes the most instructive data for the model: equipped with this intelligent selector, the pre-training model is well-trained and in turn provides better guidance for the graph selector.
The rest of the paper is organized follows. In $2 we present the basic graph pre-training framework and review existing work on this topic. Then in $3 we describe in detail the proposed data-active graph pre-training (APT) paradigm. $4 contains numerical experiments, demonstrating the superiority of APT in different downstream tasks, and also includes the applicable scope of our pre-trained model.

---

2 Basic Graph Pre-training Framework
This section reviews the basic framework of graph pre-training commonly used in the literature. The backbone of our graph pre-training model also follows this framework.
We start with a natural question: What does graph pre- pre-training actually learn? On one hand, graph pre-training tries to learn transferable semantic meaning associated with structural patterns. For example, both in citation networks and social networks, the closed triangle structure (( is interpreted as stable relationship, while the open triangle (ZS) indicates an unstable relationship. In comparison, these semantic meanings can be quite different in other networks, e.g. molecular networks. On the other hand, however, the distinction (or relationship) between different structural patterns is still transferable. Taking the same example, the closed and open triangles might yield different interpretations in molecular networks (stability of certain chemical property) from those social networks (stability in social intimacy), but the distinction between these two structures remains the same: they indicate opposite (or contrastive) semantic meanings [32,41] 21,411,7, Therefore, the graph pre-training either learns representative structural patterns (when semantic meanings present), or more importantly, obtains the capability of distinguishing these patterns. This observation in graph pre- tre-training is not only different from that in other areas (e.g.. computer vision and natural language processing), but may also explain why graph pre-training is effective, especially when some downstream information is absent.
With the hope to learn the transferable structural patterns or the ability to distinguish them, the graph pre-training model is fed with a diverse collection of input graphs, and the learned model, denoted by fe (or simply f if the parameter 0 is clear from context), maps a node to a low-dimensional representation. Unaware of the specific downstream task well as task-specific labels, one typically designs self-supervised task for the pre- pre-training model. Such self-supervised information for a node is often hidden in its neighborhood pattern, and thus the structure of its ego network can be used as the transferable pattem.. Naturally, subgraph instances sampled from the same ego network I; considered similar while those sampled from different ego networks Therefore, the pre-training model attempts to capture the similarities (and dissimilarities) between subgraph instances, and such self-supervised task is called the subgraph instance discrimination task. More specifically, given a subgraph instance C. from an ego network H; centered at node v as well as its representation æ; = f(G:), the model aims encourage higher similarity between æ; and the representation of another subgraph instance Ç, sampled from the same ego network. This can be done by minimizing, egg., the InfoNCE loss [48].
rendered dissimilar.
exp [an ((())/T)
C, - log exp (x. S(Ct)/T) + Σ exp (a. S(S)/T) CERT
(I)
where S2," is collection of subgraph instances sampled from different ego networks I, Ūi A i), and r >> 0 is a temperature pepee-parammter. Here the inner product is used as a similarity measure between two instances. One common strategy to sample these subgraph instances is via random walks on graphs, as used in GCC [50], and other sampling methods as well as loss functions are also valid.
3 Data-Active Graph Pre-training
In this section, we present the proposed APT framework for graph pre-training, and the overall pipeline is illustrated in Figure 2. The APT framework consists of two major components: graph selector and a graph pre-training model. The technical core is the interaction between these two components: The graph selector feeds suitable data for pre-training, and the graph pre- pre-training model learns from the carefully chosen data. The feedback of the pre-training model in turn helps select the needed data tailored the model.
The rest of this section organized as follows. We describe the graph selector $3.1 and the graph pre-training model in $3.2. The overall pre-training and fine-tuning strategy is presented in $3.3.
3

---

graph pre-training model
graph selector
provided to predictive
din
decision boundary
uncortainty
Query instance
Fogularzation data
with most uncertainty
old data
Combined for graph selector
dimn
+
similandissimilar instunce of
ROW
(a) Predictive uncertainty
loss for new
network entropy
input data
graph model.
demsity
Gorwardprop
averuge degree
bockprop
degree variance
scale-free exponent
other properties
micro F1 on
pubmed Inselt dRE44 by Wikooain cornell
added to
select
Pearson
pre-training data
correlation
-1.00.0 1.0
The graph and samples friendly pre-training
(b) Graph properties
Figure 2: Overview of the proposed data-active graph pre-training paradigm. The graph selector provides the graph and samples suitable for pre-training, while the graph pre-training model learns from the incoming data progressive way and in better guides the selection process. In the graph selector component, Part (a) provides an illustrating example on the predictive uncertainty, and Parr (b) plots the Pearson correlation between the properties of the input graph and the performance of the pre-trained model on the training set (using this graph) when applied to different unseen test datasets (see Appendix F for other properties that exhibit litte/correlation with performance).
3.1 Graph selector
In view of the curse of big data phenomenon, is more appealing carefully choose data well suited for graph pre-training rather than training a massive amount of data. Conventionally. the criterion of suitable data, or the contribution of data point to the model, is defined based on the output predictions on downstream tasks [20]. In graph pre-training where downstream information is absent, new selection criteria or guidelines are needed to provide effective instructions for model. Here we introduce two kinds of selection criteria, originating from different points of view, to help select suitable data for pre-training. The predictive uncertainty measures of certain data, and thus helps select the least certain data points for the current model. In addition to the measure of model's ' ability, some inherent properties graphs can also be used to assess the level of representativeness informativeness of given graph
model's understanding
Predictive uncertainty. The notion of predictive uncertainty can be explained via an illustrative example, as shown in part (a) of the graph selector component in Figure 2. Consider query subgraph instance Ç. (denote by ? in Figure 2) from the ego network T; in a graph G. If the pre-training model cannot tell its similar instance G (denoted by + from its dissimilar instance GT Ω (denoted by ). we say that the current model uncertain about the query instance G. Therefore, the contrastive loss function in Eq. (1) comes in handy natural measure for the predictive uncertainty of the instance Ç5 Puncertain (G: = L. Accordingly, the predictive uncertainty of a graph G (i.e, the graph-level predictive uncertainty) is defined as Punceutain (1/M) Σ L., where M is the number subgraph instances queried this graph.
We further establish a provable connection between the proposed predictive uncertainty and the conventional definition of uncertainty. most existing work, model uncertainty is often defined in the label space, e.g., taking as the uncertainty the cross entropy loss LCE(C) of an instance on the downstream classifier [43. 54, 56, 58). Comparatively, our definition of uncertainty, Puncertai (C). is in the representation space. The theoretical connection between these two losses is given in the following theorem.
Theorem (Connection between uncertainties.). Let X, Z and y be the input space, representation space and label set of downstream classifier. Denote downstream classifier by h: Z - y and the

---

set of downstream classifiers by H. Assume that the distribution of labels is uniform distribution
over y. For any graph encoder f + Z, one has
log |
LCE(X) 2 log
log 2 - Ouncertain (x)
where Lce denotes the conventional uncertainty, defined as cross entropy loss and estimated from the composition of graph encoder and downstream classifier h o f, and Quncertain is the proposed uncertainty estimated from graph encoder f (independent of the downstream classifier).
While the proof and additional discussion on the advantage of Ouncertain are postponed to Appendix B, emphasize here that, by Theorem 1, a smaller Lee over all downstream classifiers cannot be achieved without a smaller Puncertain-
Although GCC is used as the backbone model in the presented framework, our data selection strategy can be easily adapted to other non non-contrastive learning tasks. In that case, the InfoNCE loss used in @uncertain should be replaced with another pre-training loss associated with the specific learning task. More details with the example of graph reconstruction is included in Appendix H.
Graph properties. As we see above, the predictive uncertainty measures the model's ability to distinguish (or identify) given graph (or subgraph instance). However, predictive uncertainty is sometimes misleading, especially when the chosen graph (or subgraph) happens to be an outlier of the entire data collection. Hence, learning solely from the most uncertain data is not enough to boost the overall performance, turn out to be equivalently important as a selection criterion for graph pre-training. Intuitively, is preferable to choose those graphs that are good by themselves, e.g., those with better structure, or those containing more information. To this end, we introduce five inherent properties of graphs, ie., network entropy, density, average degree, degree variance and scale-free exponent, to help select better data points for pre-training. All these properties exhibit a strong correlation with downstream performance, which is empirically verified and presented in part (b) of the graph selector component in Figure 2. The choice of these properties also has an intuitive explanation, and here we discuss the intuition behind the network entropy as an example.
worse still, might lead to overfitting. The inherent properties of the graph
The use of network entropy is inspired from the sam- pling methods used in many graph pre- pre-training models (see, e.g., [22, In those works, random walks are used to construct subgraph instances (used model input). Random walks can can also serve as a means to quantify the amount of information contained in a graph. In particular, the amount of information con- tained in random walk from node 12 to node vy is defined as log Psg [6], where P is the transition ma- trix. Thus, the network entropy of a connected graph can be defined as the expected information of indi- vidual transitions over the random walk process [3]:
network catcopy
strccrrsi properiox
deeatt
deggee VOEARCE
scale-rer
normalized value of structural properties
(ue. avange degree, deaats, degees va or regaline scile fize espoaa))
Dentropy log P
Σ ne Pig log Pejs (2)
Figure 3: Illustrative graphs with increasing net- work entropy (bottom left to top right), and the other four graph properties.
where is the stationary distribution of the random
walk and (+) denotes the expectation of a random variable according to P. Network entropy (2) is in general difficult to calculate, but is still tractable for special choices of the transition matrix P. For example, for connected unweighted graph G (V, E') with node degree vector d E RV if the transition matrix is defined by P.j = 1/d,, then the stationary distribution is π = (1/2 and the network entropy (2) reduces to
M
cnnrrop
Σ
d, log d,.
(3)
2
In this case, the network entropy of a graph depends solely on its degree distribution, which is straightforward and inexpensive to compute.
Although the definition of network entropy originates from random walks on graphs, is still useful in graph pre-training even when the sampling of subgraph instances does not depend on random
5

---

walks. Its usefulness can also be explained via the coding theory. Network entropy can be viewed as the entropy rate of a random walk, and it is known that the entropy rate the expected number of bits per symbol required to describe stochastic process [6]. Similarly, the network entropy can be interpreted as the expected number of "words" needed to describe the graph. Thus, intuitively, the larger the network entropy is, the more information the graph contains.
We also note that the connectivity assumption does not limit the usefulness of Eq. (3) in our case. For disconnected input graphs, we can simply compute the network entropy of the largest connected component, since for most real-world networks, the largest connected component contains most of the information [14]. Alternatively, we can also take some of the largest connected components from the graph and treat them separately as several connected graphs.
Furthermore, the other four graph properties, ie.. density, average degree, degree variance and scale- free exponent, are closely related to the network entropy. Figure 3 presents clear correlation between the network entropy and the other four graph properties, as well as provides some illustrative graphs. (These example graphs are generated by the configuration model proposed in [47], and Appendix F contains more results on real-world networks.) Intuitively, graphs with higher network entropy contain larger amount of information, and are graphs with larger density, higher average degree, higher degree variance, or smaller scale-free exponent. The connections between all five graph properties can also be theoretically justified and the motivations of choosing these properties can be found in Appendix A. The detailed empirical justification of these properties and the pre-training performance in included in Appendix F.
Time-adaptive selection strategy. together act as a powerful indicator of graph's 's suitability for pre-training model. Then, we aim to select the graph with the highest score, where the score is defined as
The proposed predictive uncertainty and the five graph properties
J(G) (1 % ) Puncertain + Y MEAN (dentropy, Qdensity Pwg degs Odey vary -Qa);
where the optimization variable is the graph G to be selected, " E [0, 1] is trade-off parameter to balance the weight between predictive uncertainty and graph properties, and is the iteration counter. The small hat on the terms Puncertains Oentropy Odensityy Pavg_ dog. Odee var and &a indicates that all the values are already z-normalized, the objective (especially the MEAN operator) is independent of their original scales.
Note that the pre-training model learns nothing at the beginning, so we initialize no = 1, and in later iterations, the balance between the predictive uncertainty and the inherent graph properties ensures that the selected graph is good supplement to the current pre-training model as well as an effective representative for the entire data distribution. In particular, at the beginning of the pre-training, the outputs of the model are not accurate enough to guide data selection, so the parameter Tyr should be set larger so that the graph properties play a leading role. As the training phase proceeds, the graph selector gradually pays more attention to the feedback Ouncertain via smaller value of %: Therefore, in our framework, the parameter "tt is called the time-adaptive parameter, and is set to be a random variable depending on time t. In this work, we take "tt from Beta distribution Y Beta(1, 3t). where Be decreases over time (training iterations).
3.2 Graph pre-training model
Instead of swallowing all the pre-training graphs as a whole, our graph pre-training model takes the input graphs and samples one by one in a sequential order and enhances itself in a pro-
prdicttvv uncertalaty
mmm
gressive manner. However, such straightforward sequential training does not guarantee that the model will remember all the contributions of previous input data. As shown in the orange
33
curve in Figure 4, the previously learned graph exhibits a larger predictive uncertainty the training phase proceeds.
without proximal temm
With prociiaal (2.2)
15
training epoch
The empirical result indicates that the knowledge or information contained in previous input data will be forgotten or covered by newly incoming data. This phenomenon, called catastrophic forgetting, was first noticed in continual learning [35] and also
Figure 4: Predictive uncertainty versus training epoch.

---

appears in our case. Intuitively, when the training data is taken in progressive or iterative manner, the learned parameters will cater to the newly incoming data and forget the old, previous data points.
One remedy for this issue is adding a proximal term to the objective. The additional proximal term (ie., the regularization) guarantees the proximity between the new parameters and the model parameters learned from previous graphs. Therefore, when the model is learning the k-th input graph, the loss function for our pre-training model in APT is
(()) - Σ c,(0)
+ 2 EE F ( (0, - - 102
(5)
where L; is given in Eq. (1), the first summation taken over the subgraph instances sampled from the latest input graph, 6(k-1) the model parameters after learning from the first k 1 graphs, and the parameter À describes the trade-off between the knowledge learnt from new data and that from
previous data. Here, (((-1) is the Fisher information matrix of g(k-1), and F(A) is its j-th diagonal element. When F is set an identity matrix, the second term degenerates to the L.2 regularization (which serves as one of our variants). The proximal term in Eq. (5) is absent when the first input graph is introduced the model, and the term is applied on the first three layers of the pre-training model. Finally, we note that the total number of parameters in the pre-training model is in the same order of magnitude classical GNNs, the memory cost would not be bottleneck.
3.3 Training and fine-tuning
Integrating the graph selector and the pre-training model forms the entire APT framework, and the overall algorithm is presented in Appendix C. After the training phase, the APT framework returns a pre-trained GNN model, and then the pre-trained model applied to various downstream tasks from wide spectrum of domains. In the so-called freezing mode, the pre-trained model returned by APT is directly applied to downstream tasks, without any changes in parameters. Alternatively, the fine-tuning mode uses the pre-trained graph encoder as initialization, and offers the flexibility of training the graph encoder and the downstream classifier together in an end-to-end manner.
4 Experiments
In the experiments, we pre-train graph representation model via the proposed APT framework, and then evaluate the transferability of our pre-trained model on multiple unseen graphs in the node classification and graph classification task. Lastly, include the applicable scope of our pre-trained model. Additional experiments can be found in Appendix H, including our adaptation to backbone pre-training models GraphCL, JOAO and Mole-BERT, training time, impact of different graph properties, analysis of the ablation studies and selected pre-training graphs, hyper-parameter sensitivity, explorations of various combinations of graph properties.
4.1 Experimental setup
Datasets. The datasets for pre-training and testing, along with their statistics, are listed in Ap- pendix D. Pre-training datasets collected from different domains, including social, citation, and movie networks. Testing datasets comprise both in-domain (e.g., citation, movie) and cross- domain (e.g., image, web, protein, transportation and others) datasets to evaluate transferability comprchensively, also including large-scale datasets with millions of edges sourced from [28].
Baselines. We evaluate our model against the following baselines for node and graph classification tasks. For node classification, ProNE [80], DeepWalk [49], struc2vec [53]. DGI [65]. GAE [34], and GraphSAGE [23] are used as baselines, and then the learned representations are fed into the logistic regression, as most of baselines did. As for graph classification, we take graph2vec [46], InfoGraph [59], DGCNN [81] and GIN [71] as baselines, using SVM as the classifier, which aligns with the methodology of most baselines. For both tasks, we also compare our model with (1) Random: random vectors are generated as representations; (2) GraphCL [76]: a GNN pre-training scheme GNN pre-training scheme that automatically selects data augmentations; (4) GCC [50]: the state-of-the-art cross-domain graph pre-training model (which is model's 's version without the data selector, trained on all pre-training
based on contrastive learning with augmentations; (3) JOAO [75]:
7

---

Table I: Micro F1 scores of different models in the node classification task. The column "A.R." reports the average rank of each model. Asterisk (*) denotes the hest result on each dataset, and bold numbers denote the best result among graph pre-training models in the freezing or line-tuning setting, The notation "f" means out of memory or no convergence for more than three days.
Metlond
Datnect
braril
dd68
dd687
puhmed
oghansiv
oghpooteins
Random
12.16615
6.71x2.44 443
8.2014
5-9822
26, 76/79/8.55
19.77(7.20
8500
(814.666
52 62,6915
15.2
PooNE
50.244
10.04(2.56)
7.79/3.111
5.88(1
44.6717.400
47.33212.144
50, 76.
65.0640 06)
7.5
DaepWalk Walk
4.10(145)
6.7213.06
6.17(2.15
39.6119.11
16.04 (2.95)
74(0.49)
13.71
7,98/2.76
(6.0112.41)
DGI
13.570.441
4615.46
09.5599.00
30.0010.44)
12.907.677
55 (8.00.0))
GAB
37,88010.05
5.22
13.4300.00
10.25/263)
45.79/4.181
49 2012.0224
30.1010.31)
40.1410.65)
GrahSAAG
307711
67,9019
1533522
14.3310.37)
13,5510,07 701
781
47.0311.0
071
16686122221
761
12:1"
(bioeae)
71 11.2217.211 21
7,98/2 900
122002-9-33
42-098--15)
43 09-1015-077
(170508777
10.9
GCC (Irzes))
APT-C (fsessee
67.4744.09
(9.89/3.42
17.3101113)
80)
139
15900351 25
221
52-5211-900
40:8231-200
220--22
2
35-4700031
36-0000
15)
12
50
32
59 1510,50
38/0-411
7.0
6.3
APT-P (frees)
66.5512.55
96.58(0977
10
42:3877
du 0000 170
12 26 (4)
6.2
APT-R (frecze)
68. 12x1 07)
7200 22)
22
241
2013 00
980000 02
20 00000
18 2965 87)
62 1R0:061
5.0
APT-I-2 (freeme)
69. k3x2 926
12080080
228000811
10
2019 11
19 606 46)
2200
4.4
APT (freene)
16.5700 78.39/2.55)
10000000 821
10
17:3711-22 221
49)
26-8800211
22.04/0.29)
62.29)0.55)
3.8
GrgaCL 1rand, Tine tane
83
202500
71 T1
007700000
8:3
J0A0 (rand, line-qunc)
72.1416.74)
10.93 851
8.0822 15
45.36610,31)
29 26.9912.841
42.000.66
9.6
GEC (rand, linc-cune)
58,5163.07 (77)
15,980 US)
13.1611
$119512.20 5385512.58
58)
261
43. S2.
46.7200117
(8.61(1.5)
59. 59.1210.35
7.6
GnghCT. (finetune)
73. 97.57 10.300.33 331
(5.35/0.99)
(2.5))
10466120
63
51 21)
30 $1,0 361
429010-91)
7.5
1OAO (finocanc)
75.005.766 76)
10.54(33.07)
7.561. 94)
2 285
42. 12.11(10.366 26)
29 54(3.04)
22.2000.8))
9.5
GEC (lne-4inn)
74.46/3.005 (15)
19,32(0.80)
1.877 (1
10:371 (061
59:4711
.P)
48 48.3222.422
50.8700 19)
18.62(1922)
60.0810.56)
6.4
APT-G-dine-une qune)
77 871 48)
25. 45: 60)
17.78(L 141
112270.76 761
66
0912 28)
(1)
45.6310.86)
50.8100118 18)
27. 03.33
60:0210:3 32)
3.8
APT-P (ine-tune)
78.99/2 44)
25. (7)
16,40() 22
11 191
64.
24(1 90)
50.0511 30)
45 53.5 30)
50 6600 18)
27.2004 80)
59 30.8600.33 37)
4.8
APT & tliee tune)
79.14(1.97)
24.96/0.57)
(7.53
11.29(1.94)
11.29
66.28(1.94)
53.5662.28'
46,0210 46.0210.83)
$1.0010.21)
18.41(1.84)
60 60.10/0.35)
3.4
APT L2 (hine tune)
78.7511.63) 633
24.62/0.90 90)
17.8361.355
12.26/0 75)
67.0
(2.9411.95)
47.4810.65)
$1.2510.21)
27. 47.47)4
60.8510:45)
2.6
APT (fine tune)
79.67(2.34))
28.62/0.555
20.301.13)""
1.544
67.08(1.75)
92.15(2.25)
47.5110.62)
31.30:0.16
27. 27.40)4.87)
61.440.35)
1.3
data). GCC, GraphCL and JOAO are trained on the entire collected input data, and the suffix (rand, fine-tune) indicates whether the model trained from scratch. We also include variants of our model: (1) APT-G: removes the criteria of graph properties in the graph selector; (7) APT-P: removes the criteria of predictive uncertainty in the graph selector; (8) APT-R: removes the regularization w.r.t old knowledge in Eq. (5); (8) APT-L2: degenerates the second term in Eq. (5) with L2 regularization.
Experimental settings. In the training phase, we aim to utilize data from different domains to pre-train one graph model. We iteratively select graphs for pre-training until the predictive uncertainty of any candidate graph below 3.5. For each selected graph, we choose samples with predictive uncertainty higher than 3. We set the number of subgraph instances queried in the graph for uncertainty estimation M as 500. The adne-adaetive parameter " in Eq. (4) follows a 7 ~ Beta( 11, B.). where 3, = 3 0.995'. We set the trade-off parameter X 10 for APT-L2, and À 500 for APT. The total iteration number is 100. We adopt GCC as the backbone pre-training model with its default hyper-parameters, including their subgraph instance definition. In the fine-tuning phase, we select logistic regression or SVM as the downstream classifier and adopt the same setting as GCC. Due to space limit, results of our adaption other backbones like GraphCL, JOAO and Mole-BERT, as well as details can be found in Appendices H and G. See Appendix G for details.
We provide an open-source implementation of our model APT at https://g tttp//tttub.ccooo
gal ial
4.2 Experimental results
Node classification. Table 1 presents the micro Fl score of different methods over 10 unseen graphs from a wide spectrum of domain for node classification task. We observe that our model beats the graph pre-training competitor by an average of 9.94% and 17. 17.83% under freezing and fine-tuning mode respectively. This suggests that instead of pre- trainirinng on all the collected graphs (like GCC), it is better to choose part of graphs better suited for pre-training (like model APT).
Moreover, compared with the traditional models without pre-training, the performance gain of our model is attributed to the transferable knowledge learned by pre-training strategies. We also models, like ProNE, enforce neighboring nodes to share similar
find that some proximity- representations, leading to superior performance on graphs with strong homophily rather than weak homophily. Nonetheless, when applied to different graphs, these models require re-training, which makes them non-transferable. In contrast, we target at general, transferable model free from specific assumptions on graph types, and thus applicable across wide scenarios (including both homophilic and heterophilic graphs). Ablation study reveals the necessity of all the components in APT (e.g..
8

---

the proximity regularization with respect to old knowledge, proximity term, graph properties and predictive uncertainty). We also explore the impacts of the five graph properties used in our model, and demonstrate their indispensability by experiments. Thus, combining all graph properties is essential to boost the performance of APT. Details in ablation study and more experimental results can be found in Appendix H.
Graph classification. The micro F1 score on unseen test data in the graph classification task is summarized in Table 2. Especially, our model is 7.2% and 1.3% on average better than the graph pre-training backbone model under freezing and fine-tuning mode, respectively. In- terestingly, we observe that all variants of APT perform quite well, and thus, a simpler yet well-performed version of APT could be used in practice. This phenomenon could happen since "graph pre-train and fine-tune" is extremely complicated non-convex optimization prob- lem. Another observation is that in specific cases, such as dd dataset, a decrease in down- stream performance after fine-tuning is observed, as compared to the freezing mode. This could happen since "graph pre-train and fine-tune" is an extremely complicated non-convex optimization problem. A similar observation has been made in previous work [37] well.
Finally, it is worth noting that our APT model achieves a training time 2.2x faster than the competitive model GCC, achieved through reduced number of carefully selected training graphs and samples. More specifically, we care- fully selected only 7 datasets out of the avail- able 11 and performed pre-training using at most 24.92% of the samples in each selected dataset. Moreover, for each newly added dataset, our model only needs a few more training iterations to convergence, rather than being trained from scratch.
Table 2: Micro Fl of different models in graph classifi- cation.
Methed
Dataset
indi-binary
dd
mete-21
A.R.
Random
39,30(4.82)
32.72
4.492.114)
graphi2ee
56.200,5.33)
19.1663.47)
8.22(3.67)
777
infoGrrphh
66.58(0.63)
58. 38.6600.23)
6.0110.59)
7.7
GripteL (irese)
18)
57.24711
5,4(2.777)
(Tiezze)
55.97(3 63.900(3.8)
5.0912.65)
GCC (freeze)
73.09(0.55)
75.1600.53)
11.51(1.33)
5.3
APT-G (Treeze)
73 19.1000330 39)
75.
75.24/0.43)
(2.8100.4)
4.3
APT-P (freere)
72.89(081)
76.38.0.32)
13. (3-3000.57)
APT-R (freeze)
75.32/0.34 73.98(0.21)
12.90(0.57)
APT-L2 (frecze)
73. 73.54(0.40)
75.81 30)
13.16/0.77)
2.3
APT (Erecze)
73.0010.50)
75.83/0.11)
1381(1.06)
DOCNN
71.0014.69)
48.63(4.6)
6.01(0.9)
GIN
72.00/2.41)
47.6
10.5415.08)
6.0
GraphCT. frand, tine tine)
63 (3.6015361)
58.
(5)
(.25(2
12.7
JOAD (rand, fine-tune)
67.70(3.35)
62.10(431)
11.40(3.06
10.0
4.3 Discussion: scope of application
GCC frand, fine-tune)
75.80(1.37)
74.26/0.59)
17.18(1.43)
GmaphC1. (fiee-uue))
66.90(4.39)
(4)
8.77(2.60)
10.7
10AD (fine tune)
68. (3.50(3.61)
62.61(4.99)
(0.18(1.72)
10.0
The transferability of the pre-trained model comes from the learned representative structural patterns and the ability to distinguish these pat- terns (as discussed in $2). Therefore, our pre- training model is more suitable for the datasets where the target (e.g., labels) is correlated with subgraph patterns or structural properties (e.g., motifs, triangles, betweenness, stars). For example, for node classification on heterophilous graphs (e.g.. winconsin, cornell), our model performs very well because in these graphs, nodes with the same label are not directly connected, but share similar structural properties and behavior (or role, position). On the contrary, graphs with strong homophily (like cora, pubmed, ogbarxiv and oghproteins) may not benefit too much from our models. Similar observation can also be made on graph classification: our model could also benefit the graphs whose label has strong relationship with their structure, like molecular, chemical, and protein networks (e.g., dd in our experiments) [17,66).
GOC (line-tnn)
76
75.32(1.77
24-90(1.65)
APT- tine-nine)
36.29(0.89)
75.47)..77)
21.94(0.73)
APT-P (line-tune)
75.34(0888) 76.70/1.011
24 24.32(1.22)
3.7
APTER (line-tine)
76.60(1.00 1.422
75 (4.6 70)
24 34.09(2.11)
3.3
APT-L2 (fin-cune)
75.58(1.00 75.93(0.84)
28.57)
APT (line-tune)
76.27(1.20)
75.691142)
24.41(1.23)
5 Related Work
Graph pre-training. Inspired by pre-training in CV/NLP, recent efforts have shed light on pre-training on GNNs. Initially, unsupervised graph representation learning is used for graph pre- training [13, 21, 23, 46, 53, 63, 80]. The design of unsupervised models is largely based on the neighborhood similarity assumption, and thus cannot generalize to unseen graphs. More recently, self-supervised graph learning emerges as another line of research, including graph generative and contrastive models. Graph generative models aim to capture the universal graph patterns by recovering certain parts of input graphs [7,27,30. 30,34, 34, 34,67J, but they rely heavily on domain-specific knowledge. In comparison, contrastive models maximize the agreement between positive pairs and minimize that between negative pairs [24.25,20 29,39,94499. 40, 44, 60, 65, 69, 70, 76, 78, 83, 85-87). Some work in

---

this direction takes subgraph sampling as augmentation, in the hope that the transferable subgraph patterns can be captured during pre-training. However, all the aforementioned studies only focus on the design of pre-training models, rather than suitable selection of data for pre-training.
Uncertainty-basee sample selection. The terminology uncertainty is widely used in machine learn- ing, without a universally-accepter definition. In general, this term refers to the lack of confidence of an MI. model in certain model parameters. The majority of existing works define uncertainty in the label space, such as taking the uncertainty as the confidence level about the prediction [16, 18, 42, 61). Only a few works define uncertainty in the representation space [52. 68]. In [52], uncertainty is measured based on the representations of an instance's nearest neighbors with the same label. However, this approach requires access to the label information of the neighbors, and thus cannot be adapted in pre-training with unlabeled data. [68] introduces a pretext task for training a model of uncertainty over the learned representations, but this method assumes a well-pre-traing already available. Such post processing manner is not applicable to our scenario, because need an uncertainty that can guide the selection of data during pre-trainn training rather than after pre- training.
model is
Some works on active learning and hard example mining (HSM) have also introduced concept similar to uncertainty. In active learning, uncertainty is measured via classification prediction, and the active learning model focuses on those samples which the model is least certain about [4, 74, 82, 84). However, these techniques all rely on the labels and cannot be adapted in pre-training with unlabeled data. As another line of work, HSM introduces similar strategies and works on those samples with 43, Nevertheless,
the greatest loss, which can also be regarded as a kind of uncertainty existing HSM approaches do not meet the following two requirements needed in our setting. (1) The chosen instances should follow a joint distribution that reflects the topologiaal structures of real-worll graphs. This is satisfied by our use of graph-level predictive uncertainty and graph properties, but is not met in HSM. (2) The chosen set of graphs should include informative and sufficiently diverse instances. This is only achieved by the proposed APT framework while existing HSM methods fail to consider this requirement.
Pre-training in CV and NLP. For pre-training in CV and NLP, scaling up the pre-training data size often results in a better or saturating performance in the downstream [1. 15,3,51 51,62 62). In view of this, data selection is not an active research direction for CV and NLP. Existing studies mainly focus on selecting pre-training data that closely matches the downstream domain [2, 5, 80, 38, 72). The assumption on downstream domain knowledge differs from our graph pre-training setting, making such data selection less relevant to our work.
Data-centric AI. This recently introduced concept emphasizes the enhancement of data quality and quantity, rather than model design [73, 79]. Following-up works in graph pre-training (24.64) exploits the data-centric idea to design data augmentation. For example, [24] introduces a graph data augmentation method by interpolating the generator of different classes of graphs. [64] mainly focuses on the theoretical analysis of data-centric properties of data augmentation. While many of these works advocate for shifting the focus to data, they do not consider the co-evolution of data and model, as the case in our work.
6 Conclusion
In this paper, we identify the curse big data phenomenon for pre-training graph neural networks (GNNs). This observation then motivates us to choose few suitable graphs and samples for GNN pre-training rather than training on a massive amount of unselected data. Without any knowledge of the downstream tasks, we propose a novel graph selector to provide the most instructive data for pre-training. The pre-training model is then encouraged to learn from the data in progressive and iterative way, reinforce itself on newly selected data, and provide instructive feedback to the graph selector for further data selection. The integration of the graph selector and the pre-training model into a unified framework forms a data-active graph pre-training (APT) paradigm, in which the two components are able to mutually boost the capability of each other. Extensive experimental results verify that the proposed APT framework indeed enhances model capability with fewer input data.
Acknowledgments
This work was partially supported by NSFC (62206056, 62322606). Xin Jiang and Carl Yang were not supported by any fund from China.
10

---

References
[1] Samira Abnar, Mostafa Dehghani, Behnam Neyshabur, and Hanie Sedghi. Exploring the limits of large scale pre-training. In ICLR, 2022.
[2] Iz Beltagy, Kyle Lo, and Arman Cohan. Scibert: A pretrained language model for scientific text. EMNLP-IJCNLE pages 3615-3620, 2019.
[3] Zdzislaw Burda, Jarek Duda, Jean-Mare Luck, and Bartek Waclaw. Localization of the maximal entropy random walk. Physical review letters, 102(16): 2009.
[4] Hongyun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint orXiv:/005. 1705.05085 2017.
[5] Shuvam Chakraborty, Burak Uzkent, Kumar Ayush, Kumar Tanmay, Evan Sheehan, and Stefano Ermon. Efficient conditional pre-training for transfer learning. In CVPR, pages 4241-4250, 2022.
[6] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, 1999.
[7] Ganqu Cui, Jie Zhou, Cheng Yang, and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. In SIGKDD, pages 976-985, 2020.
[8] Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge J. Belongie. Large scale fine- grained categorization and domain-specific transfer learning. In CVPR, pages 4109-4118, 18, 2018.
[9] Xiang Dai, Sarvnaz Karimi, Ben Hachey, and Cecile Paris. Using similarity measures to select pretraining data for ner. In Proceedings of NAACL-HLT, pages 1460-1470, 2019.
[10] Xiang Dai, Sarvnaz Karimi, Ben Hachey, and Cecile Paris. Cost-effectivve selection of pretraining data: A case study of pretraining bert social media. In EMNLP (Findings), pages 1675-1681, 2020.
[11] Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLLT, page 4171-4186, 2019.
[12] Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In ICML, pages 647-655, 2014.
[13] Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embeddings via diffusion wavelets. In SIGKDD, pages 1320-1329, 2018.
[14] David Easley and Jon Kleinberg. Networks, crowds, and markets: Reasoning about highly connected world. Cambridge university press, 2010.
[15] Alaaeldin El-Nouby, Gautier Izacard, Hugo Touvron, Ivan Laptev, Hervé Jegou, and Edouard Grave. Are large-scale datasets necessary for self-supervised pre-training? arXiv preprint arXiv:2112.10440 2021.
[16] Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In ICML, pages 1050-1059. PMLR, 2016.
[17] Eleanor J. Gardiner, Peter Willett, and Peter J. Artymiuk. Graph-theoretic techniques for macromolecular docking, Journal of Chemical Information and Computer Sciences, 40(2):273- 279, 2000.
[18] Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, et al. survey of uncertainty in deep neural networks. Artificial Intelligence Review, pages 1-77, 2023.
[19] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. In CVPR, pages 580-587, 2014.
[20] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[21] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In
SIGKDD, pages 855- 2016.

---

[22] Hakim Hafidi, Mounir Ghogho, Philippe Ciblat, and Ananthram Swami. Graphel: Contrastive self-super learning of graph representations. arXiv preprint arXiv:2007.08025 2020.
[23] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, pages 1025-1035, 2017.
[24] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In ICML, pages
2022.
[25] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In /CML,, pages 4116-4126, 2020.
[26] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pages 9729-9738, 2020.
[27] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjje Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In SIGKDD, page 594-604, 2022.
[28] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs arXiv preprint F=XXv:2005.00687 2020.
[29] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICI.R, 2020.
[30] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In SIGKDD, pages 1857-1867,
[31] Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. arXiv preprint ArXiv::905.111 2019.
[32] Hong Huang, Jie Tang, Sen Wu, Lu Liu, and Xiaoming Fu. Mining triadic closure patterns in social networks. In WWW, pages 499-504, 2014.
[33] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alee Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
[34] Thomas N Kipf et al. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning. 2016.
[35] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 1 11<(13):521--352, 2017.
[36] Adit Krishnan, Mahashweta Das, Mangesh Bendre, Hao Yang, and Hari Sundaram. Transfer learning via contextual invariants for one-to-many cross-domain recommendation. In SIGIR, pages 1081-1090, 2020.
[37] Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang. Fine- tuning can distort pretrained features and underperform out-of-distributtin. arXiv preprint 2rXiv:2202.10054 2022.
[38] Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. Biobert: pre-trained biomedical language representation model for biomedical text mining. Bioinformatics, 36(4):1234-13))) 1234-1200 2020.
[39] Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation self-supervised learning on graphs. In AAAI, pages 7372-7380, 2022.
[40] Pengyong Li, Jun Wang, Ziliang Li, Yixuan Qiao, Xianggen Liu, Fei Ma, Peng Gao, Seng Song, and Guotong Xie. Pairwise half-graph discrimination: A simple graph-level self-supervised strategy for pre-training graph neural networks. In IJCAI, pages 2694-2700, 2021.
[41] Bin Liu, Yulin Zhu, and Ke Yan. Pold-LTR-TCP. protein fold recognition based on triadic closure principle. Briefings in Bioinformatics, 2166):2185-299, 2020.
[42] Jeremiah Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax Weiss, and Balaji Lakshmi- narayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. NewrIPS, 33:7498-7512, 2020.
12

---

[43] Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv:1511.06344 2015.
[44] Yuanfu Lu, Xunqiang Jiang. Yuan Fang, and Chuan Shi. Learning to pre-train graph neural networks. In AAAI, pages 4276-4284 4284, 2021.
[45] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed rep- resentations of words and phrases and their compositionality. In NewrIPS, pages 311 1-31 2013.
[46] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint
707.05005, 2017.
[47] Mark E. J. Newman. The structure and function of complex networks. SIAM Reviews, 45:167- 256, 2003.
[48] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint orXiv:1807.03744 2018.
[49] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In SIGKDD, pages 701-710, 2014.
[50] Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Tang. GCC: Graph contrastive coding for graph neural network pre-training. In SIGKDD, pages 1150-1160, 2020.
[51] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020.
[52] Tiago Ramalho and Miguel Miranda. Density estimation in representation space to predict model uncertainty. In Engineering Dependable and Secure Machine Learning Systems: Third International Workshop, EDSMLS 2020, New York City, NY, USA, February 7, 2020, Revised Selected Papers 3, pages 84-96. Springer, 2020.
[53] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In SIGKDD, pages 385-394, 2017.
[54] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. CVPR, pages 815-823, 2015.
[55] Abhinay Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In CVPR, pages 761-769, 2016.
[56] Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, lasonas Kokkinos, and Francese Moreno- -oogue. Fracking deep convolutional image descriptors. arXiv preprint 4411v:/412.6537/ 2014.
[57] Stavros Sintos and Panayiotis Tsaparas. Using strong triadic closure to characterize ties in social networks. In SIGKDD, pages 1466-1475, 2014.
[58] Yumin Suh, Bohyung Han, Wonsik Kim, and Kyoung Mu Lee. Stochastic class-based hard example mining for deep metric learning. In CVPR. pages 7244-7252, 2019.
[59] Fan- Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
[60] Mengying Sun, Jing Xing, Huijun Wang, Bin Chen, and Jiayu Zhou. MoCL: Data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph. In SIGKDD, pages 3585-3594, 2021.
[61] Natasa Tagasovska and David Lopez-Paz. Single-model uncertainties for deep learning. NeurlPS, 32, 2019.
[62] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. ICML, pages 6105-6114, 2019.
[63] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In WWW, page 1067-1077, 2015.
13

---

[64] Puja Trivedi, Ekdeep S Lubana. Mark Heimann, Danai Koutra, and Jayaraman Thiagarajan. Analyzing data-centric properties for graph contrastive learning. NeurIPS, 35:14030-14043, 2022.
[65] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.
[66] S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 1 11:1201-2242, 2010.
[67] Chun Wang. Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. MGAE: Marginalized
graph autoencoder for graph clustering. In CIKM, pages 889-898, 2017.
[68] Mike Wu and Noah Goodman. A simple framework for uncertainty in contrastive learning. arXiv preprint arXiv:2010.02038, 2020.
[69] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel:
Information-awarc graph contrastive learning. In NeurlPS, pages 30414-30444 30425, 2021.
[70] Jiarong Xu, Yang Yang, Junru Chen, Xin Jiang, Chunping Wang, Jiangang Lu, and Yizhou Sun. Unsupervised adversarially robust representation learning on graphs. In AAAI, pages 4290-4298, 2022.
[71] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks. In ICLR, 2019.
[72] Xi Yan, David Acuna, and Sanja Fidler. Neural data server: A large-scale search engine for transfer learning data. In CVPR, pages 3893-39022 2020.
[73] Cheng Yang, Deyu Bo, Jixi Liu, Yufei Peng, Boyu Chen, Haoran Dai, Ao Sun, Yue Yu, Yixin Xiao, Qi Zhang, et al. Data-centric graph learning: A survey. arXiv preprint arXiv:2310.04987, 2023.
[74] Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. IJCV, 113:113-127, 2015.
[75] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML, pages 12121-12132, 2021.
[76] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, pages 1812-5823, 2020.
[77] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks. In ICML. pages 10871-10880, 2020.
[78] Jiaqi Zeng and Pengtao Xie. Contrastive self-supervised learning for graph classification. In AAAI, pages 10824-10832, 2021.
[79] Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang, and Xia Hu. Data-centric ai: Perspectives and challenges. In SDM, pages 945-948. SIAM, 2023.
[80] Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang. and Ming Ding. Prone: Fast and scalable network representation learning. In IJCAI, pages 4278 2019.
[81] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, page 1338-4445, 2018.
[82] Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. AL.G: fast and accurate active learning framework for graph convolutional networks. In SIGMOD, pages 2366-2374, 2021.
[83] Zaixin Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self-supervised learning for molecular property prediction. In NeurlPS, pages 15870-15882, 2021.
[84] Jingho Zhu, Huizhen Wang, Tianshun Yao, and Benjamin K. Tsou. Active learning with sampling by uncertainty and density for word sense disambiguation and text classification. In COLING, pages 1137-1144, 2008
[85] Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In NeurIPS D&B, 2021.
[86] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning, arXiv preprint arXiv:2006.04133 2020.
14

---

[87] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive
learning with adaptive augmentation. In WWW, pages 2069-200000000 2000000000200 2021.
15

---

A Theoretical Connection Between Network Entropy and Typical Graph Properties
Many interesting graph structural properties from basic graph theory give rise to graph with high network entropy [19]. We here theoretically show some connections between the proposed network entropy and typical structural properties.
To make theoretical analysis,
we consider connected, unweighted and undirected graph, whose network entropy depends solely on its degree distribution (see Eq. (3)). Considering a random graph G with a fixed node set, we suppose that the degree of any node v; independently follows distribution which is a common setting in random graph theory [8]. Then the expected network entropy of G is
(H())) = 2| ((d, (d, log d,) (dlog (d)
(6)
where every d; (and d) is independent random variable follows the distribution p.
Now ready to discuss the connection between network entropy (H(G)) and some typical graph properties (i.e., average degree (d), degree variance Var(d) and the scale-free exponent a).
Average degree. Given that the function x log. x convex in æ, we have
(M(G)) 2 (d) log(d)
log(d).
(d)
It is clear that average degree is the lower bound of network entropy. Based on our discussion on $3.1, we conclude that when used for pre-training, an input graph with higher average degree would in general result in better performance of the pre-trained model.
Degree variance.
The Taylor expansion of (d d) in Eq. (6) at (d) gives Var(d)
(H(G)) log(d) + 2(d)²
(d)
where Var(d) is the variance of d. We find that log(d) is exactly the zeroth-order term in the expansion. When average degree is fixed, the network entropy and the degree variance Var(d) are positively correlated. This in turn implies a positive correlation between degree variance and the test performance of the model.
Scale-free exponent. Most real-world networks exhibit an interesting scule-free property (i.e., only a few nodes have high degrees), and thus the degree distribution often follows a power-law distribution. That is, we can just write the degree distribution as p(z) ~ x z= where a is called the scale-free exponent. For real-world network, the scale-free exponent is usually larger than [4]. Suppose the degrees of a random graph G with nodes follows power-law distribution p(z) Ca-a where C is normalization constant. When 2, we could approximately have [8]
1 2'
(H)))
if oc.
Clearly, a smaller scale-free exponent a results in a higher network entropy.
Remark (Connection between network entropy and typical structural properties). A graph with high network entropy arises from graphs with typical structural characteristics like large average degree, large degree variance, and scale-free networks with low scale-free exponent.
Besides the above theoretical analysis. The motivation of choosing density, average degree, degree variance and scale-free exponent is similar to that of network entropy. Intuitively, graphs with larger average degree and higher density have more interactions among the nodes, thus providing more topological information to graph pre-training. Also, the larger the diversity of node degrees, the more diverse the subgraph samples. The diversity of node degrees can be measured by degree variance and scale-free exponent, (A smaller scale-free exponent indicates the length of the tail of degree distribution is relatively longer, i.e., the degree distribution spreads out wider.)
16

---

B Theoretical Analysis and Advantages of Predictive Uncertainty
In this section, we provide the proofs of Theorem and demonstrate the advantages of our proposed uncertainty,
Proofs of Theorem 1 Before start the proof for Theorem 1, introduce three useful lemmas that are adopted to prove the theorem as follows.
Lemma (Fano's Inequality.). Let be random variable uniformly distributed over a finite set of outcomes X. For any estimator X such that X + *xx forms a Markov chain, we have
Pr(x + x) I(X;X) log
(8)
log |2]
Lemma (Data-Processa Processing Inequality.). For any Markov chain X + Y + Z, we have
I(xY) 2 I(X; Z) and InY; (Y; 2 1(
The proof of lemma and lemma can found under Chapter in [5]. The above lemmas establish connection between mutual information and the accuracy of downstream task. Next, further establish the connection between mutual information and ours uncertainty measure.
Lemma (Connection between InfoNCE and mutual information). Assume that graph encoder g is scaling function, namely g(x) kx. Hence, the mutual information I(X; Z) can be expressed by the InfoNCE loss unccettain for node Eq.(1) as follows:
Pancertain 2 -(X);(()) =
(10)
Proof: We follow [20] to prove the theorem. The mutual information (X; Z) can be expressed as: (()):((m:))
log Puncertain sup (xx.g(r))) Pxxxxx 1=1 E e (m),)(a)))
(11)
S DKL. (Px Px T(X: ((x)((())) I(X;
where fx; y) is any similarity scoring function like f(z;y) cos (I) cos cos(y)/T.
Therefore, now prove that lower existing uncertainty LCE(S) (C) over all downstream classifiers cannot be achieved without lower uncertainty @umcertaiu
Theorem 1 (Theoretical connection between uncertainty.). Let X, Z and y be the input space, representation space and label set of downstream classifier. Assume that the distribution of labels is uniform distribution over y. Consider the set downstream classifiers H. = (h: : 2 y}. For
any graph encoder f X + Z.
log |
LCr(S) 2 log( log 2 Quncertain (C)
(12)
where LCE denotes the conventional uncertainty (which is the cross entropy loss here) estimated from the composition of graph encoder and downstream classifier o f, and Puncertain is our proposed uncertainty estimated from graph encoder f.
Proof. For la E H. we have the Markov chain
Y 4 (x)
where X, Y are random variables for input and label distributions respectively. The first Markov chain Y + X can be understood as generative model for generating inputs according to the conditional probability distribution PXlY. Therefore, applying Lemmas and 2, we obtain the inequality,
Pr (r # Y 21 T(Y: (h f) (x)) + log 2 1
T(X; (X)) + log 2
(13)
log |
log |
Pr lh (f (X)) # Yl represents the error rate. According to the definition of eross entropy, the cross entropy for node can be denoted as follows:
LCE log(1 Pr (h (X)) YI).
(14)
17

---

By combining Eq. (13), Eq. (10) with Eq. (14), we have
= e CoB(() 21 T(X; + log2 (f (X)) * ===1-
Puncertain (<)
- log
2
log |3]
log [J] ,
(15)
log |
LCE(S) 2 log(
log22 2 Quncertain (C)
Thus, completed the proof.
Advantages of our proposed uncertainty Except for the theoretical advantages, we further discuss two advantages of using the model loss (i.e, InfoNCE loss) as predictive uncertainty for data selection. First, InfoNCE loss is exactly the objective function of our model, so what we do is actually select the samples with the greatest contributions the objective function. Such strategy has been justified to accelerate convergence and enhance the discriminative power of the learned representations [18, 28, 29, Second, as the loss function of our model, InfoNCE is already computed during the training, and thus no additional computation expense is needed in the data selection phase.
C Algorithm
The overall algorithm for APT is given in Algorithm 1. Given a collection of graphs G (Gi,..., Gr} from various domains, APT aims to pre-train a better generalist GNN (i.e. pre- training model) wisely chosen graphs and samples. Our APT pipeline involves the following three steps. (i) At the beginning, the graph selector chooses a graph for pre- pre-training according to the graph properties (line 1). (ii) Given the chosen graph, the graph selector chooses the subgraph samples whose predictive uncertainty
higher than T, this graph (line 3). (iii) The selected samples are then fed into the model for pre-traie pre-training until the predictive uncertainty of the chosen graph below T, or the number of training iterations on this chosen graph reaches F (line 4-5). (iv) The model's feedback in turn helps select the most needed graph based on predictive uncertainty and graph properties until the predictive uncertainty of any candidate graph is low enough (line 6-7). The last three steps repeated until the iteration number reaches pre-set maximum value T (which can be considered as the total iteration number required to train on all selected graphs)
Algorithm 1 Overall algorithm for APT.
Input: A collection of graphs G = (G1, ........ Gr }. maximal period F of training one graph, trade-off parameter 7/2 = O, hyperparameter {3,), the learning rate μ, the predictive uncertainty new graph Tg. the predictive uncertainty threshold of choosing training
threshold of moving samples T., and the maximum iteration number T.
Output: Model parameter 0 of the pre-trained graph model.
1: Choose graph G* from & via the graph selector, and G + GV(G).
2: while The iteration number reaches do
3: Sample instances with predictive uncertainty higher than T. from G* via the graph selector.
4: Update model parameters 0 +- - ب (
5: if @unsertain (G*) < T. or the model has been trained on G* by F iiterations then
6: Update the trade-off parameter "/e ~ Beta (1, Bt).
7: Choose graph G* from G, and G <- ((G').
8: end if
9:
end while
The time complexity of our model mainly consists of five components: data augmentation, GNN encoder propagation, contrastive loss, sample selection and graph selection. Suppose the maximal number of nodes of subgraph instances [V], the batch size is B, and D the representation dimension. (1) As for the data augmentation, the time complexity of random walk with restart at least (())V [34]. (2) The time complexity of GNN encoder propagation depends on the architectures of the backbone GNN. We denote it as X here. (3) The time complexity of the contrastive loss (BB²D) D) [17]. (4) Sample selection is conducted by choosing the samples with
high contrastive loss (the loss is computed before), which costs O(B). (5) Graph selection costs
18

---

Table 3: Datasets for pre-training and testing, where denotes the average statistic of multiple graphs under graph classification setting. [V] and [|] denote the number nodes and the number of edges in graph, respectively.
Type
Name
VI
E]
Description
citations
arxiv
86,376
517.563
citations between papers the arxiv
dblp
93,156
178,145
above (dblp)
pre-training data
patents- main
240.547
560,943
citations between US patents
social
soc-sign0902
81,867
497.672
friend/foe links between the users of Slashdot in Feb. 2009
sne-sign08
77,350
468,554
same as above (Nov. 2008)
wiki-vote
7,115
100,762
voting relationships between wikipedia users
academia
137,969
369,692
friendships between academics Academia.cdu
michigan
30.147
1.176.516
friendships between Facebook users University of Michigan
msu
32,375
1,118,7744
same as above (Michigan State University)
uillinois
30,809
1,264,428
above (University Uillinois)
movie
imub
896,305
3,782,447
relationships between actors and movies
protein
dd
284.32"
715.66"
molecular interactions between amino acids
ogbproteins
132.534
39,561,252
biologically associations between proteins
image movie
msre-21
77.52"
198.32
adjacency between superpixels of image segmentations
test data
imdb-hinary
19.77
96.53"
collahoration relationships between actorv/actresses
citations
2,708
5,278
citations between Machine Learning pupers
pubmied
19,717
88,648
citations between scientific papers
ogbarxiv
169.343
1,166,243
citation network between computer science arxiv papers
web
cornell
183
280
hyperlinks between webpages collected from Comell University
wisconsin
251
466
same as above (Wisconsin University)
transportation others
brazil
131
2,077
commercial flights between airports in Brazil
dd242
1,284
3,303
this network dataset in the category of labeled networks
dd68
775
2,093
same as above
dd687
725
2,600
same as above
((G) D) (where M the number samples needed to compute the predictive uncertainty of a graph, and [9] is the number of graphs that have not been selected). This step is executed only in a few epochs (around 6% in our current model), so we ignore its time overhead in graph selection. Therefore, the overall time complexity of APT in each batch is O(B + X + B B).
D Dataset Details
The graph datasets for pre- pre-training and testing in this paper are collected from a wide spectrum of domains (see Table 3 for an overview). The consideration of the graphs for pre-training and test is as follows. When selecting pre-training data, we hope that the graph size is at least hundreds of thousands contain enough information for pre-training. When selecting test data, we hope that: (1) some test data is in the same domain as the pre-training data, and some is cross-domain, so as to comprehensively evaluate our model's in and across-domain transferability. Accordingly, the in-domain test data is selected from the type of movie and citations, and the others test data are across-domain; (2) the size of test graphs can scale from hundreds to millions, including large-scale datasets with millions of edges from Open Graph Benchmark [10].
Regarding the pre-training datasets, arxiv, dblp and patents- are citation networks collected from [2]. [37] and [9], respectively. Imdb is the collection of movie from [27]. As for the social networks, soC-sign0902 and soc-sign0811 are collected from [16], wiki-vote from [15], academia from [7], and michigan, msu and uillions are from [32]. Regarding the test datasets, we collect the protein network dd and ogbproteins from [6] and [10]. The image network msrc-21 is from [23]. The movie network andb-binary is from [36]. The citation networks, cora, pubmed and ogbarxiv, are from [21], [22] and [10]. The web networks cornell and wisconsin are collected from [24]. The transportation network brazil is form [26], and dd242, dd68 and dd687 are from [27].
The detailed graph properties of the pre-training data and test data are presented in Table 4 and Table 5, respectively.
19

---

Table 4: Detailed structural properties of pre-training datasets, where avg properties equals to MEAN( Centroyy: ( Oavg_eeg; deg; Odeg_var:--d var: -Ộ.) ) in Eq. (4), and neig denotes the average number and denote the number of nodes and the number of
MEAN standard deviation of hop neighbors, [V] and and [|]
edges in graph, respectively.
Dataset
Properties
[V]
[8]]
agg properties avg degree degree var density
entropy
a
meig (avg. sid)
avg clustering caef
soc signD9022
81867
497672
1643.20
1.49e004
1.51
1192.33
2305.99
0,06
sec-sigaU811
77350
468554
-0.32
13.12
1631.77
1.57e-04
3.93
1.52
1226.93,
2312.03
0.05
imdb
896305
3782447
-0.66
9,44
298.27
9.42o-06
3:07
1.53
316.16, 614.03
5c-05
patent
240547
560943
-0.96
5.66
34.95
1 194c-05
2.04
1.57
117.23, 172.40
0.08
acadamia
137969
369692
-0.89
102.14
3.88c-05
2.38
1.57
101.40, 225.96
0,14
Wori-Vore
7115
103689
0.74
29.32
3314,79
4.10c-03
4.46
1.40
972.03, 1045.13
0.14
dhip
93156
178145
-1.12
4.82
58.05
4.11e.05
2.16
1,72
58.85, 90.46
0.27
arxiy
86376
517563
-0.43
12.98
382.12
1.39--44
3.22
1.41
145.21, 309.12
0.68
michigan
30147
1176516
1.40
79.05
6369.17
2. 2.59c-03
4.78
1,23
4683.90, 3655.25
0.21
msu
32375
1118774
70.11
5087
13c-03
4.62
1.23
4567.63, 3465.
0.21
uillinois
30809
1264428
1.44
83.08
6306.02
2.56e-03
4.78
1.22
5267. 10, 3831,37
0.21
Table 5: Detailed structural properties of test datasets, where neiz denotes the average number and standard deviation of 2 hop neighbors, and the numbers with denote the average statisties of multiple graphs under graph classification setting. [V], [E] and |G' denote he number of nodes in a graph, the number of edges in graph and the number of graphs in graph classification datasets, respectively.
Properties
Datasct
[V]
[E]
avg degrec
degree
density
entropy
Wtii (avg, sld)
avg. clustering of classes
indb-binary
19.77"
193.06'
1000
9.89'
116.01
1.04"
1.07
24.89"115 15.91
D.95'
2
msre-21
77.52"
198.32'
563
6.10'
30.26'
6.81c-02'
1.71
17,00' 5.81
0
20
6.00"
2.78ee022
1.68*
0.48*
cora
2708
5278
4,90
42.53
1.4de-03
1.71
34,98,47.70
0.24
puhmed
19717
44327
5,50
75.44
2.28e-04
2.23
57,10,82.72
0.06
brazil
3.14
92.27.28.50
0.66
dd242
1284
3303
6.14
28.80
4.01e-03
1.68
14,57,4.30
0.47
20
dd68
775
2093
6.40
33.42
6.98e-03
1.76
17.40,8.93
0.44
20
ddf87
8.17
25.45,9.96
0.48
wiscosin
251
466
4.65
76.26
1.49c-02
1.84
68.04 55.02
0.23
cornell
183
280
4.04
58.48
1.68--02
1.74
54.09, 44.30
0.18
ogburxiv
16343
1157799
14.67
4898.17
8.07c-05
3.63
3483.08.6711
0.23
40
oghproteins
132534
39561252
598.00
742637.58
4.50e-03
6.84
32265.17,19401
E Additional Observations of Curse of Big Data Phenomenon
This section provides more comprehensive observations to support the curse of big data phenomenon in graph pre-training, i.e., more training samples and graph datasets do not necessarily lead to better downstream performance.
We investigate 3630 experiments with GCC [25] and GraphCL. [39] model with different model configurations (i.e., the number of GNN layers is set be 3, 4 and 5 respectively), when pre- trained on all training graphs listed in Table 3 and evaluated on different test graphs (annotated in the upper left corner of each figure) under freezing setting. For each experiment, we calculate the mean and standard deviation over 10 evaluation results of the downstream task with random training/testing splits.
The observations of GCC and GraphCL model can be found in Figure 6 and Figure 7 respectively. The downstream results of different test data are presented in separate rows. The figures in left three columns present the effect of scaling up the number of graphs on the downstream performance under different model configurations (i.e., the number of GNN layers) respectively. We first pre-train the model with only two input graphs, and the result is plotted in dotted line. The largest standard deviation among the results w.r. different graph last also marked by the blue arrow. The figures in the last column illustrate the effect of scaling up sample size (log scale) on the performance.
Curse of big data phenomenon in molecular pre-training. We also conduct observations of scaling up the number of graphs on the downstream performance in molecular pre-training. We take AutrMasking [13], ContextPred [13], and GraphCL [39] as backbone models. Following their settings, the pre-training data is sampled from the molecular dataset ZINC15 and we take the molecular dataset BBBP as downstream data. We directly adopt the default settings of these pre-train models except for the number of molecules for pre- pre-training The number of molecular graphs are selected as { (1,000,
20

---

5,000, 10,000, 50,000, 100,000). The results are shown in Figure 5, which suggest that "curse of big data" phenomenon still found even when pre-training and downstream data are all molecules.
Table 6: The value of parameters for fitting the curve according to the function f(z) = a1 In x //2 x==- ag (a1, ag, 03 0), based the points the last column in Figure and Figure 7.
GCC
GraphCL.
Parameter
Dataset
Q1
42
03
41
a2
43
cora
0.45
0
33.43
1038.19
1.24
17.15
pubmed
4.74
0.11
39.63
3.50
0.12
36.83
brazil
39.10
0.09
0
29.59
0.19
41.83
dd242
6.60
0.08
3.82
7.84
0.12
dd68
6.44
0.11
3.83
2.08e+17 17
6.55
10.37
dd687
968.01
1.37
10.31
5.21
0.12
1.35
wisconsin
26.78
0.11
16.59
11.42
0.21
38.24
cornell
15.46
0.41
45.45
7.84
4.83
51.79
imdb-binane
7.43
0.13
64.97
1.06
51.69
dd
0.81
0.31
75.53
13.76
0.10
36.33
msre
5.56
0.11
4.85
4.71
0.13
0
74
74
72
72
micro F1
72
micro
70
micro
70
70
68
68
68
66
66
66
10
10"
10
10
10
10
10"
10"
10"
# of graphs
# of graphs
# of graphs
(a) AttrMasking
(b) ContextPred
(c) GraphCI.
Figure 5: The effect of scaling up the number of graph datasets the downstream performance under molecular pre-training on different pre-training models.
The explanation of convex hull fit. In order to better show the changing trend, blue curve in the last column in Figure 6 and Figure is fitted to the convex hull of the points. The convex hull is proposed to capture the performance of a randomized classifier made by choosing pre-training models with different probabilities [1].
We first introduce the concept of randomized classifier. Given two classifiers with training sample size and downstream performance made choose the first classifier with probability p and the second classifier with probability p. Then the output of the randomized classifier is pc1 + (1 p)c2, which is the convex combination of ei and c2. All the points on this convex combination can obtained by choosing different p. Extend the notion to the case of multiple classifiers, classifier to be a convex combination of the outputs of its endpoints [1]. All the points on the convex hull are achievable. Therefore, the output of the randomized classifier is equivalent to the convex hull of our trained classifiers' performance.
(ef c.s) and C2 (c de), randomized classifier can be
can consider the output of such a randomized
In our experiments, we include the upper hull of the convex hull of the model performances, i.e., the highest downstream performance for every given sample size. Such convex hull fit is proved to be robust to the density of the points in each figure [1].
final remark is that observations on different downstream datasets do result in one- model-fits-all trend. So we propose to fit a complicated curve whose function has form f(x) aj 22 + 0g (01, 02, a3 0) to the best performing models (i.., the convex hull fit as discussed above). The fitted parameters 01 and ag in this function of each curve are given in Table 6.
21

---

Wisconsnn
miter FL
red redoerdy
Oyen
Mil
50X brrr
5XL 15 Irce
of grapha
P geaplis
aa graplis
of samples
heazil
micr oF1
miiznn F1
mijoo TT
of graphs
graphs
of
samples
64687
minn F1
MBl 0.8.
miln Fl E
micro Ft
minoo
sid 1.3
40
12 samples
graphs
6:1242
merr
F1
1
migoo
graphs
graphi
graphe
samples
micro F1
mico Fl
aad 1.0
Pl
micro Ft
12 of samples
10
of gmihs
of graphs
of grophs
Cora
koma
com
micro F1
Atd 0.6
mitro
mncco s
mico TI 1
101 of samples
of grapis
graphs
graphs
juhned
micoo 1
micro F1
micr Rl
14 graphs
graphsi
graphi
samples
kornell
komell
Eamoll
comee
micro F1
mine minmo Fl
mico FL 2
2
gity 1.
miooo
121 samplecs
12
graphs
of grophs
graphis
Ropor Fl
micr
118 0.3
5d 10
run
O0C leem
graphs
N of graphs
of grahhs
of samples
Jib-binary
mollb-boneey
se imdb Einary
inds binary
mino F1
Sawe 1000. Fl
microFi Fl
(0) Groph
std Oct Sover
GCC lavean
graphs
of graphs
of graphs
y of samples
B
21
imare221
1. 1000
g
$1.114
OCC STaunn
CCC Saunn
oct leven
of graphi
of graphi
of graphis
of samples
Figure 6: The additional observations of curse of big data phenomenon, performed on different GCC pre-training models. Lefi three columns present the effect of scaling up the number of graphs on the downstream performance under different model configurations (i.e., the number of GNN layers) respectively. Last column illustrates the effect of scaling up sample size (log scale) on the performance.
22

---

TeAd carta Slayes
mitooo Fl
P1
micro P1
std
Grar lear graphe
graphs
of graphs
of sumples
misco F1
Jrazil
micro Fl
micro Fll
HS
adi
graphs
grapts
graphs
samples
44 daog?
vol 0.8
mntero F1
03688
micro F1
03687
0.8...
micen Fl
mitro
of graphis
graphs
of graghs
of samples
dd242
C0242
Iy 20242
micz Fl
micro
SMd 1.
micro
(A) Node dlsssitcation
27 of asmples
of grophi
of graphs
of graphs
dd68
6366
3053
mieo Fl
mizo
Abl
micro
sid
of graphs
of grophs
graphs
of samples
Cora
and
micro F1
micro
graphs
graphs
samples
Jahmed
juhmed
jubmeed
pubmed
mizro Fl
mikro
micco
1.7
Drope'
of
samples
tao Eornell
micoo Fl
micm
GGgbCt lreen
Chrett
graphs
of graphs
graphs
samples
8d
makoo #7
micro Fl
moce Fl
mioo
std 6.1
Dogglt Surnnn
Degart of
of graphs
of graphs
graphs
of samples
Linds-
imdo birlry
imds hinary
mub binary
micro Fl
Fl
micem Fl
miceo
(0) Gruph
Coodet
graphss
of graphs
graphs
of sumples
21
Inero-21
mizzo 11
micrrn Fl
mikro
0.7
of graphs
of graphi
2 graphis
of samples
Figure 7: The additional observations of curse of big data phenomenon, performed different GraphCL pre-training models.
23

---

Empirical Study of Graph Properties
Additional properties for part (b) in Figure 2. In Figure 8, we plot the Pearson correlation between the graph properties of the graph used in pre-training (shown in the y-axis) and the performance of the pre-trained model using this graph on different unseen test datasets (shown in the x-axis). Note that the pre-training is performed on each of the input training graphs (in Table 3) via GCC. The results indicate that network entropy, density, average degree and degree variance exhibit clear positive correlation with the performance, while the scale-free exponent presents obviously negative relation with the performance. On the contrary, some other properties of graphs, including clique number, transitivity, degree assortativity and average clustering coefficient, do not seem to have connections with downstream performance, and also exhibit little or no correlation with the performance. Therefore, the favorable properties of network entropy, density, average degree, degree variance and the scale-free exponent of a real graph are able characterize the contribution of graph to pre-training.
posstivve
rerellation
rumelation
engrelation
8x
pubmed
brazil
dd242
d668
wisconsin
cornell
46
Eatropy
Deasity
Avetage degres
Degree vattanee
Tomoriity Cliqu number
Degree atscotativity
Scale froe expenent Clustering voe flicie
Figure 8: Pearson correlation between the structural features of the graph used in pre-training and the performance of the pre-true trained model (using this graph) different unseen test datasets.
Detailed illustrations of Figure 3. In Figure 3, the illustrative graphs are generated by the configuration model with 15-18 nodes. The shaded area groups the illustrative graphs whose network entropy and graph properties are similar. Each four points on same horizontal coordinate represent four graph properties of an illustrating graph. Each curve is fitted by least squares and represents the relation between entropy and other graph properties.
Additional real-world example for Figure 3. In Figure 9, we provide real-world example of how network entropy correlates with four typical structural properties (in red), as well as the performance of the pre-trate pre-trained model test graphs (in blue). Numerical experiments again support our explanation (or intuition) of their strong correlation.
Network entropy
Network entropy Performance (%)
Network entropy Performance (?5)
Network entropy Performance (%)
Performance (%)
52
52
52
52
50
50
50
50
1e:3
26:3
36-3
46
20
40
60
46
20
40
60
1.35
1,50
1.65
(a) Density
(b) Average degree
(c) Degree variance
(d) Scale-free exponent
Figure 9: The red plot shows the network entropy (left y-axis) versus typical structural properties in a graph (i.e,, density, average degree, degree variance, and the parameter in a scale-free network), and the blue one shows the pre-training performances on wisconsin dataset (right y-axis) versus structural features.
24

---

G
Implementation Details
The number reported in all the experiments are the mean and standard deviation over 10 evaluation results of the downstream task with random training/testing splits. When conducting the downstream task, For each dataset, we consistently use 90% of the data as the training set, and 10% as the testing set. We conduct all experiments on a single machine of Linux system with an Intel Xeon Gold 51 18 (128G memory) and a Geforce GTX Tesla P4 (8GB memory).
Implementations of our model. The regularization for weights of the model in Eq. (5) is applied to first 2 layers of GIN. The maximal period of training one graph T is 100, and the predictive uncertainty thresholds T, and T3 are set to be 3 and 2 respectively. The selected instances are sampled from 20,000 instances each epoch. Since the pre-training model unable to provide precise predictive uncertainty in the initial training stage, the model is warmed up over the first 20 iterations. Since we adopt GCC as the backbone pre-training model, the other settings are the same GCC.
the maximum iteration number
Our model is implemented under the following software settings: Pytorch version 1.4.0+cu100 CUDA version 10.0, networkx version 2.3, DGL version 0.4.3post2, sklearn version 0.20.3, numpy version 1.19.4, Python version 3.7.1.
Implementations of baselines. We compare against several graph representation learning meth- ods. For implementation, we directly adopt their public source codes and most of their default hyperparameters. The key parameter settings and code links can be found in Table 7.
Table 7: The source code and major hyper-parameters used in the baselines.
Method
Hyper-paramen
Code
DeepWalk
The dimension of output representations
64, walk length 10, number of walks
80
struc2vec
The dimension of output representations is
32, length 80, number of walks
10, window size
DGI
512 hidden units per GNN layer, learning
hctps://gittubb.cc//eeaaaa
rate = 0.001
GAE
hidden units per GNN layer, learning 0.01
graph2vec
The dimension of output representations
128
InfoGraph
hidden units per GNN layer, layers hidden units per GNN layer, learning
DGCNN
https: httg::///gttabbccc//fftttttooto
0.001, batch size 50 64 hidden units per GNN layer, layers, learning rate 0.01, sum pooling
GIN
GraphCL
300 hidden units per GNN layer. layers.
learning
0.001
GCC
64 hidden units per GNN layor, layers. leurning rate = 0.005, number of samples
httpe://gitthb..com//tti cot.suub..cco///DD///000
per epoch 20000
25

---

H
Additional Experimental Results and Analysis
Analysis of ablation studies of APT. Table presents the node classification results of APT and its variants, Le., APT-G, APT-P, APT-R, and APT-L.2 We here analyze the performance of these ablation studies from the following three points of view: (1) APT-L2 and APT, the variants with the proximity regularization w.r.f old knowledge, perform the best in most cases. This suggests that catastrophic forgetting of previous trained graphs could occur during pre-training, and is necessary to add the proximity regularization to prevent this; (2) Sometimes APT-R (the variant without proximity term) achieves the best performance on the test data dd687 and cornel.. One potential reason is that the last data to be selected for pre- pre-training is dblp, while the test data dd687 and cornell exhibit some properties similar to dblp. Therefore, even excluding the proximity term, the pre-training model can still remember knowledge from the last pre-trained data, and achieve good performance on the test data that is similar to the last pre-trained data; (3) APT-G and APT-P present suboptimal performance among all variants, which suggests the utility of graph properties and predictive uncertainty.
Impact of five graph properties combination. We study the effect of the strategy of utilizing only one graph property in Table 8. We find that the five properties used in our model are all indispensable, and the most important one probably varies for different datasets. That's why we choose to combine all graph properties.
Moreover, these case studies may provide some clues of how to select pre-training graphs when some knowledge of the downstream tasks is known. For example, if the downstream dataset is extremely dense (like imdb- maab-binary), the density property dominates among the selection criteria (such that the probability of encountering very dense out-of-distribution samples during testing can be reduced). If the entropy of downstream dataset is very high (like brazil), it is perhaps better to choose graphs with high entropy for pre-training. But still, when the downstream task is unknown, using the combination of five metrics often leads to the most satisfactory and robust results.
Table 8: The effect of different graph properties on downstream performance (micro F1 is reported) under APT-L2 (fine-tune). The last row is our strategy of combining all the graph properties, and each of the first five rows is the strategy of only utilizing one graph property.
node clessificatin
groph clossification
Method
Dinaset
brazil
dd242
dd68
dd68?
Wisconsin
cornll
Doca
puhmed
indh bisary
dd
mare-21
Entropy
80,04/2.15) 25, (:))) 16.3100.81) 11 (1.08/0.82) 67 (7.00)2.00 52.8002.46 45. 1..10.8885 50.85/0.19 19)
76.78x0.84)
75 (5.5600.84)
24 24.34(1.50)
Denoity
79.23<1
27.29.0.62
19.8%0.95 12:22X1.06
1.87) 51,15(1.59)
71) 50.74/0.15
25.2900.54) 77.200.66)
24.2011.11
Average degree
79.22/1.65)
24.9900.77)
16.56(101) 11.671118)
67.02(1.8) 51.4364.16)
46.28( 50.99(0.31)
26.5700.33)
75.4600.53) (5.54))54)
Degree vaniacce
78:44/2:20 (4) 24.9100661)
16.62(1.04) 11 (1.7)( 65.65(1.26 50 (4).2.144 45.76(0.65) 50.70(0.21)
76.39(1.04)
75.47(0.67)
25:22(1.51)
Scale-free exponent
79.70;2.71)
24.94(0.68)
17.2600.63) 12.00/1.411 (41) 64.77/2.311 $1, 37.377..70 45. 18/0.2))52) 50.8410.26)
75.240.62)
75.52(1.24) 23, 19(1.9))
Our combinnatic
78.75/1663 24.62(0.90) 17,831.35 12.26/0.78) 67.04c1.50) $2.94.195) 47.48:0.46) 51.25(0.21)
75.9300844)
75.58(1.06) 25.58(1.57)
Analysis of the selected graphs. The data sequentially selected via our graph selector are uillinois, soc-sign08 1, msu, michigan, wiki-vote, soc-sign0902 and dblp. To further analyze why these graphs are chosen, we present their detailed structural properties in Table 4 in the Appendix D. We first observe that uillinois, michigan and msu have the largest value of the term related to graph properties (i.e., MEAN MEAN( (enttmy, Odensity; &avg deg, ddeeg var: -Q,)), while dblp has the smallest. This indicates that the selection of data is influenced by a combination of factors, including graph properties and potentially other factors such as predictive uncertainty. Moreover, it is also interesting to see that the selected graph wiki-vote is the smallest graph among all the pre-training graphs, but it still contributes to the performance. This observation again verifies the curse of big data phenomenon in graph pre-training, which suggests that having more training samples does not necessarily result in improved downstream performance.
Results of APT under different backbone models. We here include GraphCL [39] and JOAO [38] as our backbone models. Table 9 shows our superiority under most cases. The datasets used for pre-training and testing are the same as those employed in the experiments where GCC was the backbone model (refer to Table 7). Since the downstream tasks of GraphCL and JOAO are limited to graph classification, we can directly adapt them to our setting with graph classification as downstream task. For the node classification task, we simply take the RWR subgraphs as the input of GraphCL and JOAO, and treat the learned subgraph representation as node representation. We directly adopt GraphCL. and JOAO with their default hyper-parameters. The backbone GNN model is GIN with layers.
26

---

Table Micro Fl scores of different models in the node classification task and graph classification task, with GraphCL and JOAO as our backbone model, respectively.
rode clasilicttion
classifiaion
Matial
Dranct
beasl
02242
JJ68
63647
wiscosiin
pubsaod
insib-iiaas
dd
mame-21
GrephCL
38.3100.6)
42.9109911
13.57:00355)
15.5500.99
(3.512257)
63.8514.40
51,512241
66,00:4399
(6.598.141
8.7712
CruptCL API (lae sunci
306300 49h
42.821.01
75.14)30.0)
L443
14.5112773 72)
10 1888/0.844
64.663222)
52.612663
67 67.58-.37)
67.334407
10,02/2.5))
1030 mual Traoua))
29:9312
45.0100000
72:1446
10994:266
K:092215
T.003-481
85:38113.30)
45.26610.311
07:70:3335
02.1004311
112213:000
I0AD (pne)
26-3405.001
41.210085
75.00.3.96)
(8.562307)
7-594
8.7022-00
42.1800.28)
08.50-441
10.1911-22)
Results of APT under molecular pre-training. We also evaluate APT under molecular pre- training setting. We adopt the state-of-art model, Mole-BERT [35] and commonly used strategy. EdgePred [12] as backbone molecular pre-training models.
The predictive uncertainty mentioned before is based on contrastive loss, however, the loss function of Mole- BERTT and EdgePred are different from that used in GCC. To adapt these two models, need to make corresponding changes to our predictive uncertainty. More specifically, for Mole-BERS BBRT, take triplet masked contrastive learning LTMCL, which is the combination of triplet loss Lii with commonly-used contrastive loss Lcon in the original paper, as the predictive uncertainty. For EdgePred, we take the loss function, iee, negative log likelihood in the original paper as the predictive uncertainty
Besides, adjust the data selection process in molecular pre-training. This is because each molecular graph is taken as a sample in molecular pre-training, so we can directly select graphs. The overall algorithm for APT under molecular setting is given in Algorithm 2.
Algorithm 2 Overall algorithm for APT (Mole).
Input: collection of graphs 9 = (GI,... GN }. the number of graphs the pre-training dataset (G%) the maximal period F of training set of graphs, trade-off parameter % = 0, ratio of the number selected graphs each time to the number graphs in the pre-training dataset 7 hyperparameter {,Be}, ). the learning rate μr, the predictive uncertainty threshold of moving of graphs Tg, and the maximum iteration number T.
set
Output: Model parameter 0 of the pre-trained graph model.
1: Choose a set of graphs G (( = () from G via the graph selector, and G < 9 M
2: while The iteration number reaches T do
3: Update model parameters 0 <- 0 vV (())
4: if @uncertuin (g*) < Tg or the model has been trained on g" by F iterations then
5: Update the trade-off parameter % ~ Beta (1, B:).
6: Choose set of graphs G* (99*) = r | from G, and 9 < 9\(9").
7: end if
8:
end while
For pre-training datsets, we use 2 million molecules sampled from the ZINCI5 database following [12, 35). For downstream datasets, we adopt the widely-used 8 binary classification datasets contained in MoleculeNet [33] following [12,35]. For implementation, T, is set as -2.5 for Mole-BERT and 0.5 for EdgePred. For both Mole-BERT and EdgePred, the ratio of the number of selected graphs each time to the number of the graphs in original pre-training dataset 77 is 0.2. Other parameters related APT are set the same those in APT with GCC pre-training backbone model. The other parameters related to molecular pre- pre-training are the same as those employed in Mole-BERT and EdgePred, respectively.
The results APT under molecular pre-training with Mole-BERT and EdgePred as backbone models are reported in Table 10. We can see that our APT adaptions show significant superiority compared to the backbones. Moreover, APT (Mole-BERT) achieves the best performance on out of 8 downstream datasets among all the baseline models, which shows the effectiveness of our pipeline.
Training time. As empirically noted in Table 11, the total training time of APT-L.2 and APT 18321.39 seconds and 18592.01 seconds respectively (including the time consumed in graph selection
27

---

Table 10: Results for molecular property classification. We report the mean (standard deviation) ROC-AUC of 10 random seeds with scaffold splitting. 'No pre-train' means training from scratch. The baseline results directly obtained from the reported results in Mole-BERY [35]..
Dataset
Method
Tox21
ToxCast
Sider
ClinTTx
MUV
HIV
Bace
Average
Molecules
7,831
8,575
1,427
1,478
93,087
41,127
2,039
1,513
No pretrain
74.600.4)
61.7(0.5) 58.2(1.)) 58.4(6.4)
70.7(1.8)
75.5(0.8)
65.7(3.3)
72.4(38)
67.15
IntoCraph
73.30.6) 61.8(0.4) 58.7(06)
75.4(4.3)
74.401.8)
74.2(0.9)
68.7(06))
74.3(2.6
70.10
GPT-GNN
74.9(0.3) 62.5(0.4) 58.1(0.3) 58.3(5.2)
75.9(2.3)
65.2(2.1) 64.5(1.4) 77.9(3.2)
68.45
ContextPred
73.6(0.3) 62.6(0.6) 59.7(1.) 74.0(3.4)
72.5(1.5)
75.6(1.0)
70.6(1.5) 78.8(1.2)
70.93
GraphLoG
75.0(0.6) 63.4(0.6) 59.6(1.9) 75.7(2.4)
75.5(1.6)
76.1(0.8)
68.7(1.6) 78.6(1.0)
71.56
G- G-Contextual
75.00..6 62.8(0.7) 58.7(1.)) 60.665.2)
72.1(0.7)
76.3(.55
69.9(2.1) 79.3(1.1)
69.34
G-Motif
73.6(0.7) 62.3(0.6) 61.0(1.) 77.7(27))
73.0(1.))
73.8(1.2) 66.9(3.1) 73.0(3.3)
10.16
AD-GCL
74.9(0.4) 63.4(0.7) 61.5(0.9) 77.2(2.7)
76.3(1.4)
76.7(1.2) 70.7(0.3) 76.6(1.5)
72.16
JOAO
74.80.6) 62.8(0.7) 60.4(1.5) 66.6(3.1)
76.6(177
76.9(0.7)
66.4(1.0) 73.2(1.6)
69.71
SimGRACE
74.4(0.3) 62.6(0.7) 60 75.5(2.0) 75.4(1.)
75.0(0.6)
71.((11) 74.9(2.0)
71.15
GraphCI.
75.1(0.7) 63.00.4) 59.((13) 77.5(3.8
76.4(0.4)
75.1
67.8(2.4) 74.6(2.1)
71.16
GraphMAE
75.2(0.9) 63.6(0.)) 60.5(1.2) 76.5(3.0) 76.4(.0))
76.8(0.6)
71.2(10) 78.2(1.5)
72.30
3D InfoMux
74.5(0.7) 63.5(0.8) 568((.1) 62.7(3.3) 76.2(1.)
76.1(1.3)
69.1(1.2) 78.6(1.9)
69.69
GraphMVP
74,9(0.8) (3. 60.2(1.1) 79.1(2.8) 77.7(0.6)
76.0
70.5 79.3(1.5)
72.64
MGSSL
75.2(0.6) 63.3(0.5) 61.6(1O) 77.1(4.5) 77.6(0.4)
75.8(0.4)
68.8(0.)) 78.8(0.9)
72.28
AttMask
75.1(0.9) 63.3(0.)) 60.5(0.9) 73.5(4.3) 75.8(L.)
75.3(L.)
65.2(1.4) 77.8(1.8
70.81
MAM (with vanilla VAEV
75.8(0.6) 63. ((.)) 60.7(L.5) 74.2(2.7) 76.5((L.)
76.210.9)
66.7 78.210.8)
71.39
TMCL( w/o Cam!
73.5(1.0) 61.(0.3) 58.7(1.) 61.1(4.)) 71.6(1))
73.5(1.3) 65.4 73.7(2.4)
67.41
TMCL ( w/o Cat)
74.101.4) 62.4(0.8) 58.7(30)) 75.6(2.2) 75.7(1.1)
74.6(1.)
66.8(1.4 74.2(1.3)
70.26
MAM TMCL
76.2(0.5) 63.9(0.3) 61.4(19) 75.1(3.0)
77.4(21))
77.5(1.0)
66.8(1.5) 78.9(1.1)
72.16
74.910.7) 63.2(0.7) 59.6(14) 77.0(4.) 77.2(0.3)
75.3(L.)
67.6(L3) 75.1(1.2)
71.24
EdgePred APT (EdgePred)
76.000.6) 64.100.6) 40.70 64.1(3.7) 75.1(1.2)
76.3(1.) 67.3(24) 77.3(3.5
70.08
76.5 (0.4) 64.3 (0.3) 614 (0.) 77.9 (1.7) 76.6 (0.9) 70.7 (2.0) 81.8 (1.4)
73.05
Mole-BERT
76.8(0.5) 64.3(0.2) 628((1)) 78.9(3.0) 78.6(1.8)
78.2(0.8) 71.(16) 80.8(1.4)
74.04
APT (Mole-BERT
77.0(0.4) 65.0(0.3) 60.800.4) 79.9(1.0) 75.9(1.))
78.9(0.6) 73.1(0.4) 82.3(1.)
74.11
and regularization term), while the competitive graph pre-training model GCC takes 40161.68 seconds for the same number of training epochs on the same datasets.
The time spent on the inference on all graphs during graph selection (which is the main time spent for graph selection) only accounts for 3.95% and 3.87% of the total time under APT-L2 and APT respectively. Note that this step is executed only in a few epochs (around 6% in our current model).
The time cost of the 1.2 regularization term only accounts for 0.08% of the total time and the EWC regularization term only accounts for 0.45% of the total time, which calculated by the runtime gap between the models with and without the regularization term. Note that the regularization term is imposed on the first two layers of the GNN encoder, which only accounts for 12.4% of the total number of parameters.
The efficiency of our model is due much smaller number of carefully selected training graphs and samples at each epoch. In addition, the number of parameters in our model is 190,544, which is the same order of magnitude as classical GNNs like GraphSAGE, GraphSAINT, etc. and is relatively small among models in open graph benchmark [11].
Table 11:
Training time (sec) comparison between our model and GCC. All the models are trained under the same number of epochs, which set as 100 in practice. (The difference in time cost of inference on all graphs is due different runs.)
Time
GCC
APT-L2
APT
inference on all graphs proximity term total
723.92
719.64
15.98
83.58
40161.68
18321.39
18592.01
Effects of hyper-parameters. Here we show that the effect of the hyper-parameter (X} in the proximity term, the maximal number of training iterations one graph F, the predictive uncertainty threshold of moving to a new graph Tg. and the predictive uncertainty threshold of choosing training samples T, on performance in Figure 10 and Figure 11.
28

---

The hhper--ppaee parameter À is the trade-off parameters between the knowledge learnt from new data and that from previous data in Eq. (5). We use the dataset dd242 as an example find the suitable values of the hyper-paramette under the 1.2 and EWC regularization setting respectively, and present here for reference (see Figure 10). Clearly, a too small too large À would deteriorate the performance. Thus, an appropriate value of À is preferred to ensure that the graph pre-training model can learn from new data as well as remember previous knowledge. We leave changing as the future work.
15.5
mi30 107
mico
15.4
12.3
100
(a) Ablation study on APT-
(b) Ablation study on APT (freeze)
1.2 (freeze)
Figure 10: Performance of our model dd242 w.r. varying {사}.
Our model training involves three hyper-parameter F, T. g: T., where F controls the largest number of epochs training on each graph, T3 is the predictive uncertainty threshold of moving to a new graph, T. is the predictive uncertainty threshold of choosing training samples. We grid search to show F (4,5, 6.' s, T3 E {3, 3.5, 43's and T. E { 312ss3)ss role in the pre-training. F' remains at while studying Ty and T,. T, remains 3.5 while studying F' and T. and T3 remains at 2 while studying I' and Tg. Figure 11 presents the effect of these parameters, We find that if the value of F is set too small that of T. is too large, the model cannot learn sufficient knowledge from each graph, leading to suboptimal results. Too large F or small Tg also lead to poor performance, This indicates that instead of training on various graphs in different domains to gain diverse and comprehensive knowledge. Regarding the hyper-parameter Ts, observe that large T, would make the model having few training samples to learn knowledger and small T5 could not select the most uncertain and representative samples, thus both cases achieve suboptimal performance.
graph for large period, it would be better to switch to training
17.0
37.0
17.0
nic
25.0
13.0
(a) Ablation study F
(b) Ablation study T
(c) Ablation study T₃
Figure 11: Performance of our model on dd242 w.r. varying F.Tg.Ta.
The choice of 3r, its alternatives, and ablation study. At the beginning of the pre-training, the model is less accurate and needs more guidance from graph properties. We therefore set % as larger at the beginning and gradually decrease it. To simplify this process, we follow [3] to use the exponential formula of 3e cı cg the expectation of n. to be strictly decreasing (where (1, ()).
Tt.
The parameters ei and C2 in the exponential formula of 3r C1 - -c are suggested as 1.005 and 0.995 in [3]. We simply perform grid search on 0j in {1.005, 3, 5): see the effect ci in the Figure 12.
We then illustrate that the choice of the decay function of 8, is robust. Table 12 and Table 13 below show the effect of linear decay, step decay and exponential decay on S.. (The function for linear decay and step decay are designed as Br 2.001 - 0.004t, B = 2.005 + floor(t/20) respectively. The initial value 31 is set the same as ours.) While there is no universally better decay function, performance of our method is not significantly impacted by the choice of different decay functions, and our performance better than the baselines in most cases regardless of the choices of specific decay functions.
29

---

15
-2
(a) Wisconsin on node clas- sification
(b) Imdb-binary on graph
classification
Figure 12: Performance of APT-L2 (freeze) w.r. varying C1.
Table 12: Micro F1 of APT-L2 (freeze) with the different decay functions the node classification
task.
Dataset
Method
brazil
dd242
dd68
dd687
wisconsin
cornell
cora
pubmed
linear
72.30 16.28(0.57) 12.44(0.72) 10.29(0.87) 54.20((150) 47.66(1.59 L.53) 35.74(0.52) 46.4900 19)
step
68.70(3.95) 16.74(0.45) 12.86(1.07) 10.09(0.76) 52.55(2.39) 48.088 (8.08((128) 35.5010.44 46.58(0.21)
exponential
69.82(2.32) 16.79(0.88) 12.68(0.81) 10.34(1.12) 55.11(1.74) 48.76(2.20) 34.27(0.43) 46.21(0.15)
Table 13: Micro Fl of APT-L2 (freeze) with the different decay functions in the graph classification task.
Dataset
imdb-binary
dd
msrc-21
Method
linear
73.66(0.34) 75.47(0.26) 13.01(0.78)
step
72.99(0.40) (0.41(0 14.13(0.56)
exponential
73.54(0.40)
75.81(0.30) 13.16(0.77)
Results under GCC's original experimental setting. For more comprehensive comparison, also adopt the same pretraining datasets and downstream datasets as GCC. Table 14 and table 15 shows the performance of our model and the strongest competitor GCC, under the experiment setting of GCC node classification and graph classification task, repectively. (The performance of GCC directly taken from its paper.) The results indicate that our model still outperforms GCC under the experimental setting of GCC. The results still suggest ours superiority most cases.
Table 14: Micro F1 scores of GCC and model in the node classification task, under the experi- mental setting of GCC.
Dataset
US-Airport
H-index
Method
GCC (freeze)
65.6
75.2
Ours (freeze)
66. 66.12(5.31) 75.9(3.01)
GCC (fine-tune)
67.2
80.6
Ours (finc-tunc)
70.50(6.08) 82.28(1.48)
Table 15: Micro Fl scores of GCC and our model in the graph classification task, under the experimental setting of GCC.
Dataset
IMDB-B
IMDB-M
COLLAB
RDT-B
RDT-M
Method
GCC (freeze)
72.0
49.4
78.9
89.8
53.7
Ours (freeze)
73.2(0.27)
49.6(1.17)
19.12(0.77)
89.6(2.51)
54.1(2.45)
GCC (fine-tune)
73.8
50.3
81.1
87.6
53.0
Ours (fine-tune)
76.27(1.20)
50.50(1.08)
81.23(0.86) 92.20(2.43) 53.28(2.33)
30

---

The justification of input graphs' learning order. Table 16 reveals the downstream performance can be affected by the learning order input training graphs. With the guidance of graph selector, the pre-training model is encouraged to first learn the graphs and samples with higher predictive uncertainty and graph properties. Such learning order accomplishes better downstream performance compared to the reverse or random one.
Table 16:
The effect of input graphs' learning order on downstream performance (micro Fl is reported) under freezing mode in the node classification task. The first row the order learnt from APT-L2, and the second and third rows are the reverse and random order of the first row, respectively.
Dataset
Method
brazil
dd242
dd68
dd687
wisconsin
comell
cora
puhmed
Our order
69.82(2.32) 16.79(0.88) 12.68(0.81) 10.34(1.12) 55.11((.74)) 48.76(2.20) 34.27(0.43) 46.21 15)
Reverse order
69.60(271) 16,00(0.47) 11,41(0911) 10.65(0.65) 51,46(1.66 16(18)))8 35, 66.6666))2) 45.92/0.14)
Rundom order
67.25(2.40) (6.11(0.79) 12.57(1.17) 11.06(.755) 53.06(2.41) 46.76 46.76(1.95) 35.90(0.72) 46.36(0.20)
The choice of the "difficult" data. Among all the data, "difficult" samples contribute the most to the loss function, and thus they can yield gradients with large magnitude. Comparatively. training with easy samples may suffer from inefficiency and poor performance these data points produce gradients with magnitudes close to zero 30J. In addition, learning from difficult samples has proven be able accelerate convergence and enhance the expressive power of the learnt representations [28, 31]. For our model, the importance of learning from difficult samples is also justified empirically, as shown Table 17.
Table 17: The comparison of learning from easy samples and learning from difficult sample in our pipeline (APT-L2 (freeze)) on node classification. Micro Fl is reported in the table. (Under the setting of learning from easy samples, we replace Ouncertan with Puncertain in (4,, and only sample instances with predictive uncertainty lower than T..)
Dataset
Method
brazil
dd242
dd68
dd687
wisconsin
cornell
pubmed
Learning from easy samples Learning from ditticult samples (ours)
56.34(3.45)
14.38(0.53) 11.76(1.44) 9.900 50,65(1 48 48.0911.72) 35.74(0.42) 46.03(0.17)
69.82(2.32) 16.79(0.88) 12.68(0.81) 10.34(1.12) 15.11(1.74) 48.7612.20) 34.27(0.443 46.21(0.15)
Time comparison: pre-training vs. training from scratch. Using a pre-trained model can significantly reduce the time required for training from scratch. The reason is that the weights of the pre-trained model have already been put close to appropriate and reasonable values; thus the model converges faster during fine-tuning model (e.g. GIN), our model yields a speedup of 4.7x on average (which measured by the ratio of the training time of GIN the fine-tuning time of APT). Based above analysis, conclusion that pre- treitrann is beneficial both in effectiveness and efficiency.
test data. As shown in Figure 13, compared to regular GNN
draw
GIN
running time (sec)
400
3.9x
200
T
82%
imdb-binary
msrc-21
Figure 13: The running time of our model and the basic GNN model on graph classification task. Our model achieves speedup of 4. 4.7x average compared with GIN.
31

---

References
[1] Samira Abnar, Mostafa Dehghani, Behnam Neyshabur, and Hanie Sedghi. Exploring the limits of large scale pre-training. In ICLR, 2022.
[2] Francesco Bonchi, Pooya Esfandiar, David F Gleich, Chen Greif, and Laks VS Lakshmanan. Fast matrix computations for pairwise and columnwise commute times and katz scores. Internet Mathematics, 8 8(1-2):73-11 112773--1,2222 2012.
[3] Hongyun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang, Active learning for graph embedding. arXiv preprint wixvv:705.000885 2017.
[4] Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data, SIAM review, 51(4):661-703, 2009.
[5] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, 1999.
[6] Paul Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-78,, 2003.
[7] M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. Link prediction in social networks using computationally efficient topological features. IEEE third international conference on social computing, pages 73-80, 2011.
[8] Jesús GórdzeGs and Vito Latora. Entropy rate of diffusion processes on complex networks. Physical Review E, 78(6):065102,, 2008.
[9] Bronwyn H Hall, Adam B Jaffe, and Manuel Trajtenberg. The nber patent citation data file: Lessons, insights and methodological tools, 2001.
[10] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00687 2020.
[11] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. NeurlPS, 33:221 112221882211 11-12133, 2020.
[12] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020.
[13] Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. arXiv preprint 190.51195..1311 2019.
[14] Chen Huang, Chen Change Loy, and Xiaoou Tang. Local similarity-awan deep feature embedding. In NewrlPS, page 1262-1270, 2016.
[15] Jure Leskovee, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In WWW, pages 641-650, 2010.
[16] Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123) 2009.
[17] Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In ICML, pages 13052-13065, 2022.
[18] Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint 1XXi::1511.0633 2015.
[19] Christopher Lynn, Lia Papadopoulos, Ari E Kahn, and Danielle Bassett. Human information processing in complex networks. Nature Physics, 16(9):965-973 2020.
32

---

[20] Martin Q Ma, Yao-Hung Hubert Tsai, Paul Pu Liang, Han Zhao, Kun Zhang, Ruslan Salakhut- dinov, and Louis-Philiipe Morency. Conditional contrastive learning for improving fairness in self-supervised learning. arXiv preprint 2eXiv:2/06.028600 2021.
[21] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 20)::177-633,
2000.
[22] Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In MLG. page 1, 2012.
[23] Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting, Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102(2):209- 245, 2016.
[24] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2019.
[25] Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: Graph contrastive coding for graph neural network pre-training, In SIGKDD, pages 1150-1160, 2020.
[26] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In SIGKDD, pages 385-394, 2017.
[27] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, page 4292-4293, 2015.
[28)
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. CVPR, pages 815-823, 2015.
[29] Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, lasonas Kokkinos, and Francesc Moreno-Noguer. Fracking deep convolutional image descriptors. arXiv preprint arXiv: 1412,657,, 2014.
[30] Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In NeurIPS, page 1849- 1857, 2016.
[31] Yumin Suh, Bohyung Han, Wonsik Kim, and Kyoung Mu Lee. Stochastic class-based hard example mining for deep metric learning. In CVPR, pages 7244-7252, 2019.
[32] Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications, (11616)4115-441800 2012.
[33] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9()):513-530, 2018.
[34] Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random walks: A review of algorithms and applications. IEEE Transactions Emerging Topics in Computational Intelligence, 4(2):95-107, 2019.
[35] Jun Xia, Chengshuai Zhao, Bozhen Hu, Zhangyang Gao, Cheng Tan, Yue Liu, Siyuan Li, and Stan Li. Mole-bert: Rethinking pre-training graph neural networks for molecules. In ICLR, 2023.
[36] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. SIGKDD, pages 1365-1374, 2015.
[37] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In SIGKDD, pages 1-8, 2012.
[38] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML, pages 12121-12132, 2021.
[39] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, pages 5812-5823, 2020.
33


Reviews:
[{"review_id": "bjQMzmLN1I", "reviewer": "Reviewer_16eq", "summary": "This paper proposes a novel approach to pre-training graph neural networks (GNNs) called the data-active graph pre-training (APT) framework. This framework introduces a unique method that involves a graph selector and a pre-training model. These two components work together in a progressive and iterative way to choose the most representative and instructive data points for pre-training.", "questions": "In line 67, section 2, the authors present an example of a triangle to show what kind of knowledge the pre-trained model can learn. However, the proposed subgraph instance discrimination task can break down that knowledge. For example, ego-graph sampling can break down the triangle. Can the authors provide some insights or justification for this issue?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The key insight of the paper is that using fewer, but carefully selected data can lead to better downstream performance compared to using a massive amount of input data. This approach challenges the common practice in machine learning of using large datasets for pre-training, a phenomenon the authors refer to as the \"curse of big data\" in graph pre-training.\n\n2. The paper is well-motivated, well-written and easy to understand.\n\n3. The experimental results demonstrate that the proposed method outperformed GCC, which is the previous SOTA and a direct ablation to the proposed APT framework.", "weaknesses": "1. The proposed method is incremental. The proposed “predictive uncertainty” is adapted from curriculum learning, and “graph properties” are common statistics. \n\n2. The proposed methods are not able to handle node features. It only provides structural information which does not align with most real-world scenarios. As a result, performance is not comparable with a supervised model trained on node features.\n\n3. The node classification performance on homophily graphs (which is an important family of graphs) are much lower than ProNE. The improvement in graph classification tasks seems limited.\n\n4. Selection based on graph properties might cause potential test data leakage because the graph properties are selected according to test performance (as shown in Figure 2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 16eq,\n\nWe really appreciate your insightful comments. We have followed closely the suggestions, and made clarifications and revisions accordingly. We hope the revised and newly provided content could help to further strengthen our work. Below is a point-by-point response.\n>W1: predictive uncertainty from curriculum learning\n\nWe appreciate the reviewer's careful evaluation of our proposed method. We elucidate three significant differences between curriculum learning and our uncertainty: (1) The uncertainty in most curriculum learning is built on label space for supervised learning [1-4], while we define the uncertainty in representation space and further establish its theoretical connection with the label space. (2) In curriculum learning, samples are individually selected based on uncertainty without considering their joint distribution [1,2]. However, in graph pre-training, it is crucial to ensure that the chosen samples conform to a joint distribution that reflects data diversity and topological structures of real-world graphs. This is achieved through the incorporation of graph properties that characterize the statistics of joint distribution of samples. (3) Most traditional curriculum learning determines the order of learning samples before model training [1,2,5,6]. In our model, however, the uncertainty changes during different stages of model training. Thus, the next training sample is not determined util the end of the previous iteration. Therefore, our method has substantial difference from curriculum learning. \n> W2: Transferability of node features\n\nWe appreciate the insightful point. Here we focus on the transferability of graph structures. It is also a common practice to transfer structure rather than node features in related research areas including graph pre-training [10], transfer learning [11] and graph domain adaptation [7-9]. This is because, in most cases, node features of different graphs do not overlap or have little overlap, making them not necessarily transferable across pre-training and downstream data. For instance, when nodes in different graphs represent different types of entities, it renders the node features completely irrelevant. Even when nodes are of the same entity type across graphs, the dimensions/meanings of node features can vary significantly, leading to misalignment. After all, the transferability of node features in graph pre-training is a largely unexplored area, and needs further research attention.\n>W3: Performance on homophily graphs and graph classification\n\nThank you for bringing up this point, and we here delve into the specific cases in detail. \n\nRegarding the performance on homophily graphs, the design of ProNE is based on the homophily assumption that neighboring nodes share the same class. What's more, ProNE requires re-training on different graphs, making it non-transferable. On the contrary, we target at a general, transferable model free from any specific assumptions on graphs, and thus applicable to various settings, including both homophily and heterophily graphs. This could explain the better performance of ProNE on homophily graphs, and the superiority of our model in most other cases (particularly in situations where ProNE fails).  We have included this discussion in the revised manuscript.\n\nRegarding graph classification performance. Admittedly, our model shows modest improvements in this aspect. Nevertheless, it is valid to emphasize the substantial efficiency gain: APT obtains comparable performance with training time 2.2 times shorter than the most competitive baseline GCC. This efficiency advantage holds practical significance and offers real-world application benefits.\n>W4: Potential data leakage\n\nSorry for the misunderstanding. To clarify, each downstream dataset is split into a training set and a test set. When selecting graph properties, we only refer to the performance on the **training set** of downstream dataset, including the results in Figure 2(b). We remark that the test set of downstream dataset is completely excluded during model training and graph property selection, preventing any form of data leakage. We have revised the manuscript to avoid any ambiguity.\n>Q1: Sampling in subgraph instance discrimination task\n\nThanks for the insightful comments. In the subgraph instance discrimination task, one subgraph is defined as the neighborhood of a node. Such neighborhood typically has complex structure, comprising of repeated occurrences of various simple structural patterns (e.g., open triangles, closed triangles). Therefore, although the ego-graph sampling may break some simple structural patterns, most information in the complex neighborhood is still preserved. We have provided the discussions in the revised version.\n\n[1] Curriculum learning: A survey. IJCV.\n\n[2] A survey on curriculum learning. TPAMI.\n\n[3] When do curricula work? ICLR.\n\n[4] Dynamically composing domain-data selection with clean-data selection by \"co-curricular learning\" for neural machine translation. ACL.\n\n[5] On the power of curriculum learning in training deep networks. ICML.\n\n[6] Curriculum learning by transfer learning: Theory and experiments with deep networks. ICML.\n\n[7] Graph domain adaptation: A generative view. ArXiv.\n\n[8] Graph adaptive knowledge transfer for unsupervised domain adaptation. ECCV.\n\n[9] Graph Domain Adaptation via Theory-Grounded Spectral Regularization. ICLR.\n\n[10] GCC: Graph contrastive coding for graph neural network pre-training. SIGKDD.\n\n[11] Transfer learning of graph neural networks with ego-graph information maximization. NeurIPS."}, {"review_id": "s8pq8eivyK", "reviewer": "Reviewer_i2Gc", "summary": "This paper presents a data-centric framework, abbreviated as APT, for cross-domain graph pre-training. APT is composed of a graph selector and a graph pre-training model. The core idea is to select the most representative and informative data points based on the inherent properties of graphs, as well as predictive uncertainty. For the pre-training stage, when fed with the carefully selected data points, a proximal term is added to prevent catastrophic forgetting and remember all the contributions of previous input data.", "questions": "Q1 Are all the Graph properties used in this paper useful when dealing with graph-inherent features? Also, what is the computational complexity since multiple properties need to be calculated?\nQ2 Why did the performance of the \"dd\" dataset decrease after fine-tuning compared to the frozen parameters of APT in table 2?\nQ3 I am slightly concerned that if all the five graph properties are useful for pre-training.\nQ4 In existing works, is there any works that define model uncertainty in the representation space? And what is the difference between theirs and this work?\n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper proposes that big data is not a necessity for pre-training GNNs. Instead of training on a massive amount of data, it is more reasonable to select a few suitable samples for pre-training. This approach can also reduce the amount of data and computational costs. Compared to pre-training on the entire dataset, selecting a more carefully selected subset of data for pre-training can indeed achieve better results.\n2.This paper provides theoretical justification for the connection between uncertainties by establishing a provable connection between the proposed predictive uncertainty and the conventional definition of uncertainty. The predictive uncertainty is defined in the representation space, which enables the identification of more challenging samples that can benefit the model training more significantly.\n3.The entire framework seems very reasonable, and the process is described clearly. From the experiments, it appears that good results have been achieved.\n", "weaknesses": "1.This paper mentions both \"data-active\" and \"data-centric\" concepts. It may be helpful to clarify the relationship between these two to avoid confusion. Maybe only using \"data-active\" in the paper.\n2.There is no individual ablation experiment about the graph selector to demonstrate the effectiveness for each of the ﬁve graph properties.\n3.There is a spelling error in the title, 'Prespective' should be corrected to 'Perspective'.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer i2Gc,\n\nWe really appreciate your valuable comments. We have followed closely the suggestions, and made clarifications and revisions accordingly. We hope the revised and newly provided content could help to further strengthen our work.\n>W1: This paper mentions both \"data-active\" and \"data-centric\" concepts. It may be helpful to clarify the relationship between these two to avoid confusion. Maybe only using \"data-active\" in the paper.\n\nThanks for your valuable suggestion. We here discuss the relation and difference of \"data-active\" and \"data-centric\" concepts. The term \"data-centric\" emphasizes the enhancement of data quality and quantity, rather than model improvement [1]. On the other hand, the term \"data-active\" in our manuscript is used to emphasize the co-evolution of data and model, rather than mere data selection before model training. Our unified pre-training framework, which co-designs both the graph selector and the pre-training model, fits in the scope of \"data-active\". To avoid confusion, we have consistently utilized the term \"data-active\" in the revised version as suggested.\n\n>W2, Q1 and Q3: W2: There is no individual ablation experiment about the graph selector to demonstrate the effectiveness for each of the ﬁve graph properties. Q1: Are all the graph properties used in this paper useful when dealing with graph-inherent features? Also, what is the computational complexity since multiple properties need to be calculated. Q3: I am slightly concerned that if all the five graph properties are useful for pre-training.\n\nThe ablation studies of utilizing one graph property have been presented in Table 8 in Appendix H. The results show utilizing one graph property can still beat the best baselines in most cases, which demonstrates the effectiveness of each of the five graph properties for graph pre-training. Moreover, putting five properties together often leads to the best performance. We have added a clear pointer of the important experimental findings in the main body of our paper, making it easier for readers to locate relevant content.\n\nRegarding the computational complexity of calculating graph properties, suppose the maximal number of nodes in subgraph instances is $|V|$. We calculate average degree, degree variance, density, network entropy and scale-free exponent of each graph, which cost $O(|V|)$, $O(|V|)$, $O(1)$, $O(|V|)$ and $O(|V|)$ respectively. The overall computational complexity is $O(|V|)$. More importantly, these graph properties are only needed to compute once before pre-training. Therefore, the computational overhead is relatively low.\n\n>W3: There is a spelling error in the title, 'Prespective' should be corrected to 'Perspective'.\n\nThank you for your meticulous attention in identifying the spelling error. We have now rectified the mistake, changing 'Prespective' to 'Perspective' in the title of the revised manuscript.\n\n>Q2: Why did the performance of the \"dd\" dataset decrease after fine-tuning compared to the frozen parameters of APT in table 2?\n\nThanks for your careful reading of our paper. This phenomenon could happen since \"graph pre-train and fine-tune\" is an extremely complicated non-convex optimization problem. Actually the observation that fine-tuning deteriorates the performance has been made in previous work; see, e.g., [2]. We have included this discussion in the revised manuscript.\n\n>Q4: In existing works, is there any work that defines model uncertainty in the representation space? And what is the difference between theirs and this work?\n\nThanks for your valuable insights to improve our work. After conducting a comprehensive literature review, we find that the majority of existing works define uncertainty in the label space, such as taking the uncertainty as the confidence level about the prediction [5-8]. Only a few works define uncertainty in the representation space [3,4]. In [3], uncertainty is measured based on the representations of an instance's nearest neighbors with the same label. However, this approach requires access to the label information of the neighbors, and thus cannot be adapted in pre-training with unlabeled data. [4] introduces a pretext task for training a model of uncertainty over the learned representations, but this method assumes a well-pre-trained model is already available. Such a post processing manner is not applicable to our scenario, because we need an uncertainty that can guide the selection of pre-training data during pre-training rather than after pre-training. We have included a detailed discussion of these related works in the revised manuscript.\n\n[1] Data-centric Artificial Intelligence: A Survey. Arxiv.\n\n[2] Fine-tuning can distort pre-trained features and underperform out-of-distribution. ICLR.\n\n[3] Density estimation in representation space to predict model uncertainty. EDSMLS.\n\n[4] A Simple Framework for Uncertainty in Contrastive Learning. Arxiv.\n\n[5] A Survey of Uncertainty in Deep Neural Networks. Arxiv.\n\n[6] Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness. NeurIPS.\n\n[7] Dropout as a bayesian approximation: Representing model uncertainty in deep learning. ICML.\n\n[8] Single-model uncertainties for deep learning. NeurIPS."}, {"review_id": "Bz7YR2MiWG", "reviewer": "Reviewer_KR8J", "summary": "The paper introduced an novel graph pre-training pipeline from a data-centric view by proposing a graph data selector. The proposed approach involved sequentially feeding representative data into the model for pre-training. These representative data were determined by a data selector, which utilized prediction uncertainty and graph statistics to suggest the most relevant examples. This novel methodology offers a fresh perspective on graph pre-training and demonstrates the importance of data selection in the process.", "questions": "First, there are several questions about the predictive uncertainty:\n\n1. The loss used for graph pre-training may not effectively align with the actual loss of the downstream task [1,2]. Consequently, the predictive uncertainty based on the current definition may lack meaningful interpretation. A more promising approach would be to ensure that the uncertainty of the pretraining loss accurately reflects the difference between the pre-training loss and the downstream task loss.\n\n2. Prediction uncertainty has been extensively explored in previous research [3,4]. While many existing methods have been proposed with ground-truth labels, it would be beneficial to have discussions (and even experiments) that shed light on the connection and distinctions between different approches of uncertainty modeling.\n\nFor experimentds\n\n3. The experimental setups lack clarity. It is unclear whether data from all domains are used to pre-train a single model or if separate models are pre-trained for different domains. \n\nOthers\n\n4. Please check descriptions in lines 215~217. Smaller gamma seems leading to important roles of the predictive uncertainty term.\n\n5. Choosing subgraphs seems to be a crucial component of the pre-training algorithm. However, the paper lacks a thorough explanation or detailed descriptions of this process, which would greatly improve the understanding of this important aspect.\n\n6. Recently, there are many related work focusing on the data-centric approaches [2,5,6], espeically for graph pre-training [2,5]. It would be great and helpful to readers if the authors could provide a brief discussion on the connections and differences between their work and these existing approaches.\n\nRef.\n\n[1] Does gnn pretraining help molecular representation? NeurIPS 2022.\n\n[2] Data-Centric Learning from Unlabeled Graphs with Diffusion Model. Arxiv.\n\n[3] Dropout as a bayesian approximation: Representing model uncertainty in deep learning. ICML 2016.\n\n[4] Single-model uncertainties for deep learning. NeurIPS 2019.\n\n[5] Analyzing data-centric properties for graph contrastive learning. NeurIPS 2022.\n\n[6] Data-centric ai: Perspectives and challenges. Arxiv.\n", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea is novel and interesting.\n2. The proposed training pipeline is tested on many tasks from different domains.", "weaknesses": "1. The utilization of predictive uncertainty based on pre-training loss lacks convincing evidence.\n\n2. The proposed training pipeline requires input graphs to be processed order-by-order, which may introduce unnecessary bias and is not scalable for large graph datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer KR8J,\n\nThanks for your constructive suggestions to improve our manuscript. We have followed closely the suggestions, and made clarifications and revisions accordingly. We hope the revised and newly provided content could help to further strengthen our work.\n>W1, Q1 and Q2:  Predictive uncertainty definition and its connection to existing uncertainty\n\nFirst, we would like to clarify that our uncertainty is introduced to enhance the graph pre-training model. Typically, graph pre-training does not consider any information from the downstream task or data, e.g., GCC, GraphCL. Therefore, the uncertainty is solely computed on pre-training data and based on the pre-training task, making the pre-training loss a natural measure for predictive uncertainty. We have added the detailed description in the revised manuscript. \n\nSecond, we have presented the discussion and theoretical connection between our proposed uncertainty and existing works on uncertainty. In most existing works, uncertainty is often deﬁned on the label space, including [3, 4]. [3] quantifies uncertainty based on Orthonormal Certificates, which needs to be trained with labels. [4] leverages Bayesian learning to approximate the posterior distribution and obtain the predictive performance distribution, where the variance serves as a representation of model uncertainty. In contrast, our uncertainty is defined in the representation space. Moreover, Theorem 1 has established a theoretical connection between our uncertainty and the most conventional uncertainty defined as the cross entropy loss of an instance on the downstream classiﬁer. The theorem suggests that a smaller conventional uncertainty over all downstream classiﬁers cannot be achieved without a smaller predictive uncertainty in our work. More details can be found in lines 127-142 of our manuscript. We have highlighted this discussion and theoretical connection with a subheading in the revised version.\n>W2: Bias and scalability of order-by-order training\n\nSorry for the confusion. We explain our order-by-order training approach and discuss the scalability as follows, which has been included in the revised version.\n\nThe ordering is indeed a fundamental feature of our model, making our approach perform better than unbiased random sampling. In different stages of training process, the graph selector (equipped with predictive uncertainty and graph property) chooses the samples most needed by the current model. The experimental results present evidence of the superiority of our selection compared with unbiased random sampling in other pre-training models. Additional results are in Table 17 in Appendix H. \n\nRegarding scalability, our model is trained on a reduced number of carefully selected training graphs and samples, and achieves a training time 2.2 times faster than the competitive model GCC. In our experiments in Section 4, we carefully selected only 7 datasets out of the available 11 and performed pre-training using at most 24.92% of the samples in each selected dataset. Moreover, for each newly added dataset, our model only needs a few more training iterations to convergence, rather than being trained from scratch.\n>Q3: Experiment setup\n\nSorry for the unclear description.  In the revised manuscript, we have highlighted the crucial setup of utilizing data from all domains to pre-train one model in Section 4.1.\n>Q4: Mistake of gamma description\n\nThanks for pointing out this mistake. We have corrected the description in lines 215-217 to \"the parameter $\\gamma_t$ should be set larger so that the graph properties play a leading role. As the training phase proceeds, the graph selector gradually pays more attention to the feedback ${\\phi}_{\\text{uncertain}}$ from the model via a smaller value of $\\gamma_t$\".\n>Q5: Explanation of choosing subgraphs\n\nThanks for pointing it out. We have included the subgraph selection process in the revised version as follows. When choosing subgraphs, we follow the practice in the existing work GCC. The process involves three sequential steps for sampling a subgraph of node $v$. (1) Random walk with restart: We start a random walk from node $v$, traversing iteratively to its neighboring nodes with the probability proportional to the edge weight. At each step, there is a positive probability for the walk to return back to the starting node $v$. (2) Subgraph induction: The random walk with restart accumulates a subset of nodes surrounding $v$. We then obtain the subgraph induced by this subset of nodes. (3) Anonymization. The induced subgraph is anonymized by relabeling its nodes in an arbitrary order.  \n>Q6: Discussion of data-centric related works\n\nThanks for reminding us of these related works. We have detailedly discussed them as follows, and included in the revised version. Data-centric AI, a recently introduced concept, emphasizes the enhancement of data quality and quantity, rather than model improvement [6]. Following-up works in graph pre-training [2, 5] exploits the data-centric idea to design data augmentation. [2] augments unlabeled graph data under the guidance of downstream, while our work focus on data selection in the pre-training phase without any information from downstream. [5] mainly focuses on the theoretical analysis of data-centric properties of data augmentation. Neither of them addresses the specific problem of data selection for pre-training, which is the objective of our proposed graph selector.\n\nThe reference list of our rebuttal is the same as that of the reviewer's comment."}, {"review_id": "lTPT2HwZNP", "reviewer": "Reviewer_gzMz", "summary": "This work found that more data does not necessarily improve the pre-training of GNNs and then propose a method to adaptively select data for pre-training GNNs. Experimental results show the proposed method is effective.", "questions": "See weakness above", "limitations": "The authors do not state limitations in either the appendix or the main body of the paper, please add them.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. this work is well motivated by the observation that more data does not necessarily lead to better pretrained graph encoder\n\n2. that the experiments seems to be convincing since APT generally outperforms other baselines", "weaknesses": "There are several weaknesses mainly about the method:\n\n1. The optimization problem in equation 5 is confusing, what is the variable you are optimizing, a series of binary variable indicating whether to select a graph or not? Based on description in subsequent part, you are basically selecting graphs with the highest score, in that case it is unnecessary to formulate an optimization problem, just state your scoring function.\n\n2. The description is confusing, eg, what is M in line 296? The number of subgraphs being selected?\n\n3. Efficiency is important in data selection, but the authors do not discuss it in the main body of the paper. I assume the method is slower than baseline pretraining method but how slow is it?\n\n4. The motivation of the other four property criteria is unclear, especially when they are highly correlated with the network entropy. Can we just drop the other four criteria?\n\n5. The authors claim in the conclusion that APT can enhance the model with a fewer number of input data, but I can't find evidence for that. Is APT only trained on fewer data than baselines?\n\nOverall, the description of the proposed method could be improved. In addition, the authors claimed they are not curriculum learning but I don't think so. Time-adaptive selection strategy is just curriculum learning in a broader sense, I think easy-first is just one type of curriculum.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer gzMz, \n\nWe really appreciate your valuable comments. We have followed closely the suggestions, and made clarifications and revisions accordingly. We hope the revised content could help to further strengthen our work.\n\n>W1: The optimization problem in equation 5 is confusing, what is the variable you are optimizing, a series of binary variable indicating whether to select a graph or not? Based on description in subsequent part, you are basically selecting graphs with the highest score, in that case it is unnecessary to formulate an optimization problem, just state your scoring function.\n\nSorry for the confusion. We here aim to select graphs with the highest score $\\mathcal J(G)$. As suggested, we have removed the optimization problem and modified the description to: \"Thus we can select the graph with the highest score, where the score is defined as $\\mathcal{J}(G) = \\gamma_t \\phi_\\mathrm{uncertain} +  (1 - \\gamma_t)\\mathrm{MEAN}(\\hat{ \\phi} _ \\mathrm{entropy}, \\hat{\\phi}_\\mathrm{density}, \\hat{\\phi} _\\mathrm{avg\\\\_deg}, \\hat{\\phi} _\\mathrm{deg\\\\_var},- \\hat{\\phi} _\\mathrm{\\alpha}) $.\n>W2: The description is confusing, eg, what is M in line 296? The number of subgraphs being selected?\n\nThanks for pointing it out. $M$ is a hyper-parameter used to compute the graph-level predictive uncertainty $\\phi_{\\text{uncertain}}(G) = (1/M) \\sum_{i=1}^M \\mathcal L_i$, where $M$ denotes the number of subgraph instances queried in the graph $G$ for uncertainty estimation (as mentioned in line 126). We have provided clear descriptions of the meaning of $M$ in line 296, and other ambiguous terms or concepts in our revised version.\n\n>W3: Efficiency is important in data selection, but the authors do not discuss it in the main body of the paper. I assume the method is slower than baseline pre-training method but how slow is it?\n\nThe training time comparison between our model and the most competitive pre-training baseline GCC have been provided in Table 10 in Appendix H. As empirically noted, the total training time of APT is 18592.01 seconds, while the competitive graph pre-training model GCC takes 40161.68 seconds. The efficiency of our model is mainly due to the use of a much smaller number of carefully selected training graphs and samples at each epoch. (Detailed analysis can be found in the subsection \"Training time\" in Appendix H.)\n\nThe time complexity of our model have been analyzed in Appendix C. The overall time complexity of APT in each batch is $O(B|V|^3 + X + B^2D + B)$, where $|V|$ is the maximal number of nodes in subgraph instances, $B$ is the batch size, $D$ is the representation dimension, and $X$ is the time complexity of backbone GNN. (Detailed analysis can be found in Appendix C.)\n\nTo improve the clarity, we have now moved some crucial results to the main body and included pointer to remaining details in the appendix for further reference.\n\n>W4: The motivation of the other four property criteria is unclear, especially when they are highly correlated with the network entropy. Can we just drop the other four criteria?\n\nWe appreciate the reviewer's observation. The five graph properties are provided to serve as comprehensive and informative data selection criteria. We agree that the four graph properties (i.e., density, average degree, degree variance and negative scale-free exponent) are somehow related to the network entropy, so we have conducted further empirical investigations to determine the necessity of using all five properties. The results, as reported in Table 8 of Appendix H, demonstrate the value of each individual property. Remarkably, when combining all five properties, we achieve the best performance in most cases. This emphasizes the significance of using all five properties collectively.\n\nIn addition, the computational overhead of computing all these five properties is relatively low ($O(|V|)$ where $|V|$ is the maximal number of nodes in subgraph instances), and the computation is only needed once before pre-training. Hence, using all five quantities does more good than harm in our model.\n\n>W5: The authors claim in the conclusion that APT can enhance the model with a fewer number of input data, but I can't find evidence for that. Is APT only trained on fewer data than baselines?\n\nSorry for the unclear description. APT is only trained on fewer data than baselines because of the careful selection of suitable input data. In our experiments, only 7 datasets are selected out of the available 11  (as mentioned in \"Analysis of the selected graphs\" in Appendix H). For each selected dataset, at most 24.92% of the samples are chosen for training. We have added detailed descriptions in the main body in the revised manuscript.\n\n>Overall weakness: Overall, the description of the proposed method could be improved. In addition, the authors claimed they are not curriculum learning but I don't think so. Time-adaptive selection strategy is just curriculum learning in a broader sense, I think easy-first is just one type of curriculum.\n\nThanks for your constructive suggestions to improve our manuscript. Regarding the curriculum learning, thanks for reminding us that \"easy-first\" and \"difficult-first\" approaches fall under the broader category of curriculum learning. We have adjusted our previous unclear statement and improved our description in the revised manuscript.\n\n\n"}]

Author rebuttal:

Meta-review: This submission offers a refreshing perspective on the realm of pre-training GNNs. The reviewers have arrived at a consensus appreciating multiple facets of the paper:

* The central proposition of the paper stands out — using fewer, strategically selected data can lead to enhanced downstream performance, challenging the standard "more is better" approach. Reviewers commend the clarity of the manuscript. The paper is well-articulated and coherent, making it accessible to readers.

* Experimentally, the paper showcases significant prowess. The results indicate that the proposed method surpasses the previous state-of-the-art. Another commendable aspect is the paper's theoretical justification. The work establishes a link between the introduced predictive uncertainty and traditional definitions of uncertainty, enhancing its credibility. By defining the predictive uncertainty in the representation space, the paper offers a novel mechanism to pinpoint samples that can benefit the training.

It is evident that the submission offers a novel, well-founded, and rigorously tested methodology that has the potential to reshape thinking and practices in pre-training GNNs. Given its strengths, both in theoretical grounding and empirical validation, the manuscript is considered fit for acceptance at NeurIPS.
Decision: Accept (poster)