Better with Less: Data-Active Pre-training of Graph Neural Networks
Authors: Jiarong Xu
Renhong Huang
XIN JIANG
Yuxuan Cao
Carl Yang
Chunping Wang
Yang Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Pre-training
Graph Neural Networks

Abstract: Recently, pre-training on graph neural networks (GNNs) has become an active research area and is used to learn transferable knowledge for downstream tasks with unlabeled data. 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 samples and graph datasets do not necessarily lead to better performance. Motivated by this observation, we propose a better-with-less framework for graph pre-training: few, but carefully chosen data are fed into a GNN model to enhance pre-training. This novel 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 the predictive uncertainty. The proposed uncertainty, as feedback from the pre-training model, measures the confidence level of the model to 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 learnt from the previous data. Therefore, the integration and interaction between these two components form a unified framework, in which graph pre-training is performed in a progressive way. Experiment results show that the proposed APT framework is able to obtain an efficient pre-training model with fewer training data and better downstream performance.

Under review as a conference paper at ICLR 2023
BETTER WITH LESS: DATA-ACTIVE PRE-TRAINING OF GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, pre-training on graph neural networks (GNNs) has become an active re- search area and is used to learn transferable knowledge for downstream tasks with unlabeled data. The success of graph pre-training models is often attributed to the massive amount of input data. In this paper, however, identify the curse of big data phenomenon in graph pre-training: more training samples and graph datasets do not necessarily lead to better performance. Motivated by this observation, we propose a bether-with-less framework for graph pre-training: few, but carefully chosen data are fed into a GNN model to enhance pre-training This novel 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 se- lector chooses the most representative and instructive data points based on the inherent properties of graphs as well as the predictive uncertainty. The proposed predictive uncertainty, feedback from the pre-training model, measures the con- fidence level of the model to the data. When fed with the chosen data, on the other hand, the pre-training model grasps initial understanding of the new, unseen data, and at the same time attempts to remember the knowledge learnt from the previous data. Therefore, the integration and interaction between these two com- ponents form a unified framework, in which graph pre-training is performed in a progressive way. Experiment results show that the proposed APT framework is able to obtain an efficient pre-training model with fewer training data and better downstream performance.
INTRODUCTION
Pre- Pre-training Graph Neural Networks (GNNs) shows the potential to be an attractive and competitive strategy for learning graph representations without costly labels. However, its transferability is guar- anteed only if the pre-training datasets come from the same or similar domain as the downstream Hu
al.
22199 2020b); You et al.] (2020a b): Hu et al.) (2020c): [i al.] (202T): Lu et al. (2021); ; [Sun 2021 When we have no knowledge of the downstream, an encouraging yet largely unex-
al.
plored research direction pre-training GNNs on cross-domain data QQu et al. (2220); Hafdi et al.)
(020). Taking the graphs from multiple domains as the input, graph pre- pre-training is able to learn the transferable structural patterns in graphs (when some semantic meanings are present), or to obtain the capability of discriminating these patterns.
With diverse and various cross-domain data, the success of a graph pre-training model is often at- tributed the massive amount of unlabeled training data, well-established fact for pre-training in computer vision Girshick et al. 20:4); Donahue et al. (2014); He et al. (2020) and natural language processing Mikolov al. (2013): Devlin et al. (2019). In view of this, contemporary research al- most has no controversy on the Tollowing issue: Is massive amouni of imput data really necessary, or even beneficial, for pre- pre-training GNNs? However, two simple experiments regarding the num- ber of training samples and graph datasets seem to doubt the positive answer to this question. The first observation is that scaling pre-training samples does not result in a one-model-fis--ll increase in downstream performance (see the first row of Figure T. Second, we observe that adding input graphs (while fixing sample size) does not improve and sometimes even deteriorates the general- ization of the pre-trained model (see the second row in Figure [). Furthermore, even if the number of input graphs (the horizontal coordinate) is fixed, the performance of the model pre-trained on different combinations of inputs varies dramatically; see the standard deviation in blue. As the first contribution, we identify the curse of big data phenomenon in graph pre-training: more training samples and graph datasets do not necessarily lead to better downstream performance.

---

Under review as a conference paper at ICLR 2023
bruzil
Wisconsin
mste-g
undb-binary
modd config
micro F7
micro F1
layer
micro
micro
layers
layer
-oomvxx bull
10
10
12
13
12
13
12
12'
# of samples
# of sumples
of samples
# of samples
72
brazil
Wisconsin
mmsro-21 21
imdi imdi--inary
micro PI
micro Fl
Imion 17
12
std
std :1.3
std
std
10 (f)
# of graphs
# of graphs
# of graphs
# of graphs
(a) Node classification
(b) Graph classification
Figure 1: Top row: The effect of scaling up sample size (log scale) on the downstream performance based on a group of GCCs Qiu et al. (2020) under different configurations (the graphs used for pre- wre-triniin are kept all eleven pre-traie pre-training data Table and the samples are taken from the backbone pre- pre-training model according its sampling strategy). The results for different downstream graphs (and tasks) are presented in separate figures. To better show the changing trend, we fit a curve to the best performing models (ie.. the convex hull fit as AAbnr et al. (2022) does). Bottom row: The effect of scaling up the number of graph datasets on the downstream performance based on GCC. For fixed horizontal coordinate, we run 5 trials. For each trial, we randomly choose a combination of input graphs. The shaded area indicates the standard deviation over the trials. See Appendix Difor more observations on other graph pre-training models and detailed settings.
Therefore, instead of training on massive data, it is more appealing choose wisely some samples and graphs for pre-training. However, without the knowledge of downstream tasks, the difficulty is how to design new criteria for selecting input data to the pre-training model. To fill this gap, we propose a novel graph selector that is able to provide the most instructive data for the model. The criteria in the graph selector include predictive uncertainty and graph properties. Predictive uncer- tainty is introduced to measure the level of confidence (or certainty) in the data. On the other hand, some graphs are more informative and representative than others, due to their inherent structure. To this end, some fundamental properties of graphs also help in the selection process.
Given the selected input data, we take full advantage of the predictive uncertainty as a proxy for measuring the model capability during the training phase. Instead of swallowing data as a whole, the pre-training model is encouraged to learn from the data in a progressive way. After learning certain amount of training data, the predictive uncertainty gives feedback 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 propose a data-active graph pre-training (APT) framework, which integrates the graph selector and the pre-training model into a unified framework. 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 as follows. In S we review the existing works about basic graph pre-training framework commonly used for training cross-domain graph data. Then in $ we describe in detail the proposed data-active graph pre-training (APT) paradigm. $ contains numerical experiments, which demonstrate the superiority of APT in different downstream tasks, especially when the test and training graphs come from different domains. Lastly, we also include the applicable scope of our pre-trained model.
BASIC GRAPH PRE-TRAINING FRAMEWORK
This section reviews the basic framework of cross-domain graph pre-training commonly used in related literature. The backbone of our graph pre-training model also follows this framework, and uses GCC Qiu et al. (2020) as an instantiation. In principle, GCC can be substituted by any encoder suitable for training cross-domain graphs.
We start with a natural question: What does cross-domain graph pre-training actually leam? Pre- vious studies argue that the semantic meaning associated with structural patterns is transferable. For example, both in citation networks and social networks, the closed triangle structure (α)) is interpreted stable relationship, while the open triangle (7 indicates unstable relationship.
2

---

Under review as a conference paper at ICLR 2023
When data comes from other domains like molecular networks, the semantic meaning can be quite different. Nevertheless, we argue that the distinction between different structural patterns is still transferable. Taking the same example, the closed and open triangles might yield different inter- pretations in molecular networks (unstable vs. stable in terms of chemical property) from those in social networks (stable vs. unstable in terms of social relationship), but the distinction between these two structures remains the same because they indicate opposite (or contrastive) semantic meanings. Therefore, the cross-domain pre-training either learns representative structural patterns (when se- mantic meanings are present), or more importantly, obtains the capability of distinguishing these patterns. This observation in graph pre-training is not only very different from that in other areas (e.g,, computer vision and natural language processing). but may also explain why graph pre-training effective, especially when some downstream information absent.
With the hope to learn the transferable structural patterns or the ability to distinguish them, the cross- domain graph pre-training model is fed with a collection of input graphs (possibly from different domains), and the learnt model, denoted by fa (or simply f if the parameter 0 is clear from context), maps a node to low-dimensional representation. Unaware of the specific downstream task as well as task- labels, one should design self-supe task for the pre-training model. Such self- self-supervised information for a node is usually hidden in its neighborhood pattern, and thus the structure of its ego network is often used as the transferable pattern. Naturally, subgraph instances sampled from the same ego network T2 are considered similar while those sampled from different ego networks are rendered dissimilar. Therefore, the pre-training model attempts to capture the sim- ilarities (and dissimilarities) between subgraph instances, and such a self-supervised task is called the subgraph instance discrimination task. More specifically, given a subgraph instance Ç; from an ego network I; centered at node V; as well as its representation æ; f((i), the model f aims to encourage higher similarity between æ; and the representation of another subgraph instance C sampled from the same ego network. This can be done by minimizing, egg., the InfoNCE loss Oord ct al. (2018):
exp (m.. (((/)/7
C. = log exp (a) /(())/)+ + Σ exp (2. (MT S(C)//)) GEO,
where Q7 is a collection of subgraph instances sampled from different ego networks r (i * i), and r is temperature hyper-parameter. Here the inner product is used as similarity measure between two instances. One common strategy to sample these subgraph instances is via random walks on graphs, as used in GCC Qiu al. (2020), but other sampling methods as well as loss functions are also valid.
DATA-ACTIVE GRAPH PRE-TRAINING
In this section we present the proposed APT framework for cross pross-dommin graph pre- 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-training model learns from the carefully chosen data. The feedback of the pre-training model in turn helps select the needed data tailored to the model.
The rest of this section is organized as follows. We describe the graph selector in $ 3.] and the graph pre-training model
3.2 The overall pre- pre-training and fine-tuning strategy is presented in 3.3
3.1 GRAPH SELECTOR
In view of the curse of big data phenomenon, it is more appealing to carefully choose data well suited for graph pre-training rather than training massive amount of data. Conventionally, the criterion of suitable data, or the contribution of a data point to the model, is defined based on the output predictions on downstream tasks Goodfellow et al. (016)). In graph pre-training where downstream information is absent, new selection criteria or guidelines are needed to provide effective instructions for the model. Here introduce two kinds of selection criteria, originated from different points of view, to help select suitable data for pre-training. The predictive uncertainty measures the model's understanding 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 of graphs can also be used to assess the level of representativeness or informativeness of given graph.
Predictive uncertainty. The notion of predictive uncertainty can be explained via an illustrative example, shown in part (a) of the graph selector component in Figure Consider a query sub-
3

---

Under review as a conference paper at ICLR 2023
graph pre-training model
graph selector
provided to predictive uncertainty
drgg
decision boundary
instance uncertainty
Tegularization for dhea
Combined for gruph selector
diin
similandissimila instamee of
TrCS data
(a) Predictive uncertainty
loss new data
network catropy
input data
graph model
density
Newworlpoop
average degree
backkpop
degree variacc
scale exponent
other propertee
micro on
added to
select
comeil
Pearion
pro-training data
-1.00.0
cocrelation
The graph and samples friendly to pre-trainng
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- vre-training. while the graph pre-training model learns from the incoming data a progressive way and in turn better guides the selection process. the graph selector component, Part (a) provides an illustrating example on the predictive uncertainty, and Part (b) plots the Pearson correlation between the properties of the imput graph and the performance of the pre-trained model (using this graph) on different unseen test datasets (see Appendix E for other properties that exhibit litte/ccorelation with performance).
graph instance Ç (denote by ? in Figure 2 from the ego network I' in a graph G. If the pre-training model cannot tell its similar instance 4 (denoted by + from its dissimilar instance Ç E S2, (de- noted by @), we say that the current model is uncertain about the query instance G. Therefore, the contrastive loss function in Eq. ① comes handy as a natural measure for the predictive uncer- tainty of the instance Ç;: Ouncertain (C:) L.. Accordingly, the predictive uncertainty of a graph G (i.e., the graph-level predictive uncertainty) is defined ouneertain (G) (1/M) Σ Dis C,, where M is the number of subgraph instances queried in this graph.
The proposed selection process different from strategies used in curriculum learning Bengio al. (2099. Predictive uncertainty encourages the model to learn more difficult (uncertain) graphs and samples in the first place, while in curriculum learning, the easiest samples are fed first. The choice of difficult-fir first order is intuitive in our case; see also [epeendixGooorr empirical evidence.
Graph properties. As distinguish (or identify) a given graph (or subgraph instance). However, predictive uncertainty is sometimes misleading, especially when the chosen graph (or subgraph) happens be an outlier of the entire data collection. Hence learning solely from the most uncertain data might not improve the overall performance, or even worse, lead to overfitting. The inherent properties of the graph turn out to be equivalently important as selection criterion for graph pre-training. Intuitively, it preferable to choose those graphs that are good by themselves, those with better structure, or those containing more information. So here introduce five inherent properties of graphs (i.e., network entropy, density, average degree, degree variance and scale-free exponent) to help select better data points for pre-training, All these properties exhibit 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 discuss the intuition behind the network entropy as an example.
above, the predictive uncertainty measures the model's ability to
The of network entropy is inspired from the sampling methods used in most cross-domain graph pre-training models (see e.g., -iu et al. (2020); [aaidii et al. (2020)): Random walks started at a node are employed to construct subgraph instance the model input. Random walks can also be used to compute the amount of information contained in a graph. Especially, the amount of information contained in the move from node v; to node U log P.y Cover & Thomas (1999). where P is the transition matrix. Thus the network entropy of connected graph G (V. E) can be defined as expected information of individual transitions over the random walk process) [Burda et al. (2009):
4

---

Under review as a conference paper at ICLR 2023
infomalioence
Pcatropy (-log log P/r - Σ Piy log Pos,
13
pervon anthopy
where is the stationary distribution of random walk and (-)p denotes the expectation of a random variable according P. Network entropy (2) is in general difficult to calculate, but for connected unweighted graph. Pt 1/d,,
El)d
common strctumi properios
dogrez
(where d, is the degree of node E V and (d1, d2, ...) the degree vector). Then the network entropy reduces to
density
degree vasiance
scale free exponent
normalized value of structural propertics
average degres, density. degree vanance or negaiive scale free exponent)
Centropy
Σ de log di,
(3) Figure 3:
2|
The illustrative graphs (from bottom left to top right) with increasing network entropy and the other four graph properties.
where N = [V] is the total number of nodes in G. In this case, the network entropy of graph depends solely on its degree distribution, and is straightforward to compute.
Although the definition 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 walks. Here we provide another intuitive explanation of network entropy from the coding theory. Network entropy
be viewed as the entropy rate of random walk, and it is known that the tropy rate is the expected number bits per symbol required to describe a stochastic process Cover Thomas (1999). Similarly, the network entropy be interpreted the expected number of "words" needed to describe the graph. Thus intuitively, the larger the network entropy is, the more information the graph contains.
As a final remark on network entropy, 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 com- ponent contains most of the information [Easley & Kleinberg (2010). 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, i.e., density, average degree, degree variance and scale- free exponent, are closely related to the network entropy. Figure 3 presents clear correlation be- tween 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 Newman (2003), and Appendix B contains more results of real-world networks.) Intuitively, graphs with higher network entropy contain a larger amount of information, and so are graphs with larger density, higher average degree, higher degree variance, or a smaller scale-free exponent. The connections between all five graph properties can also theoretically justified and the motivations 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
Time-adaptive selection strategy. The proposed predictive uncertainty and the five graph proper- ties together act as a powerful indicator of graph's hh goodness. Thus the selection graph can be formulated the following optimization problem:
maximize J(G)= (1 - 11
11 Juncertain + Yt DEMMEENNNN (dentroyy Qdensity dang.dey ddeg -Q.). (4)
where the optimization variable the graph to be selected, Suncertann Pentropy Qsensity Saggadgs &aeegvee var and da are the z-score normalized value of graph-level predictive uncertainty, network en- tropy. density, average degree, degree variance and scale-free exponent of graph G respectively, Tt E [0, 1] is a parameter to trade off the predictive uncertainty and the graph properties, and / is the iteration counter. Note that the pre- pre-training model learns nothing at the beginming, so we initialize Yu = 0. The balance between the predictive uncertainty and the inherent graph properties ensures that the selected graph is good supplement to the current pre- pre-trreiittte teeiiiiinng model as well as an effective representative for the entire data distribution.
5

---

Under review as a conference paper at ICLR 2023
We shall also note that, at the beginning of the pre-training, the outputs of the model are not accurate enough to guide data selection, so the parameter "/ should be set smaller so that the graph properties play leading role. As the training phase proceeds, the graph selector gradually pays more attention to the feedback Puncertain from the model via a larger value of ? Therefore, the parameter " is called the time-adaptive parameter, and is set to be random variable depending on time t. In this work, we take "/e from a Beta distribution 7 ~ Beta(1, where Bg decreases over time (training iterations).
Finally, after a graph is selected, we can further choose subgraph instances with high predictive uncertainty for training, rather than feed the model with random subgraph samples.
Connections and differences with hard example mining. Hard example mining learns from the examples that contribute the most to model training, which has been widely applied in computer vision, natural language processing and recommender system Simo-Serra et al. (2014); Loshchilov & Hutter (2015); Shrivastava al. (2016): Krishnan et al. (2020). Our usage of predictive un- certainty for choosing graphs is conceptually similar to hard example mining. However, existing approaches for hard sample mining can not be directly applied to our setting with the following two requirements. (1) The chosen instances should follow a joint distribution that reflects the topologi- cal structures of real-world graphs. This is met by our use of graph-level predictive uncertainty and graph properties. (2) The chosen set of graphs should include informative and sufficiently diverse instances. This goal is achieved by the data-active graph pre-training framework, which enables the interaction between the graph selector and pre-training model. Another line of works in active learning introduce the measure of uncertainty by querying the labels of samples that current model is least certain w.r.t classification prediction Cai et al. (2017); Zhang et al. (2021);; Yang et al. 2015); Zhu et al. 2008), which cannot be adapted in pre-training with unlabeled data.
3.2 GRAPH PRE-TRAINING MODEL
The graph pre-training model takes the input graphs and samples one by one and enhances itself in a progressive manner. However, such a sequential training process does not guarantee the model to remember all the contributions of previous input data. As shown the orange curve in Fig- ure | the previously learnt graph exhibits larger predictive uncertainty as the training phase proceeds. The empirical result indicates that the knowledge or information contained in previ- ous input data will be forgotten or covered by newly incoming data. This phenomenon, called catastrophic forgetring Kirkpatrick et al.) (201)), was first noticed in continual learning and is also identified here. Intuitively, when the training data is taken in a one-by-one manner, the learnt parameters will cater to the newly incoming data compared with the old, previous data points. One remedy for this issue is adding proximal term the ob- jective. The additional proximal term (i.e,, the regularization)
predictive uncertainty
65
guarantees the proximity between the new parameters and the
model parameters learnt from previous graph. Therefore, the final loss function for our pre-training model in APT is
((0) = (()==C(10) (.)++
Σ
Σ
F 2
10...
112
(5)
without proximal term with peoximal temm (1.2)
j=k-1
56
10
where L, is given in Eq. ( the summation in the first term is taken over the subgraph instances sampled from the new in-
training epoch
put graph, A is the number of previously learnt graphs, 00) the model parameters learnt from the first j graphs, and Xy 's are the trade-off parameters between the knowledge learnt
Figure 4: Predictive uncertainty of a learnt graph ("michigan") versus train- ing epoch.
from new data and that from previous data. Typically, the trade-off parameters {}y} form a non-
decreasing sequence, ie., X < Xa < ... S >x. Inspired from the Elastic weight consolidation (EWC) algorithm Kirkpatrick et al. 2017), we take FOJ as the Fisher information matrix of (6)), Fli) is the diagonal element of p() and m labels each parameter. When F is set as an identity matrix, the second term degenerates to the L2 regularization (serves as one of our variants). Note that the proximal term in Eq. 5 is absent when the first input graph is introduced the model.
3.3 TRAINING AND FINE-TUNING
Integrating the graph selector and the pre- vre-training model forms the entire APT framework, and the overall algorithm is presented in Appendix B After the training phase, the APT framework returns
6

---

Under review as a conference paper at ICLR 2023
pre-trained GNN model, and then the pre-trainet model can be applied to various downstream tasks from a wide spectrum of domains. In the so-called freezing mode, the pre-trained model outputted from APT is directly applied to downstream tasks, without any changes in parameters. Alternatively, the fine-runing 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 our model on the incoming data provided by the graph selector, and then evaluate the transferability of our pre-trained model on multiple unseen graphs from different domains in the node classification and graph classification task. Lastly, we include the applicable scope of our pre-trained model. Additional experiments can be found in Appendix G including analysis on training time, sensitivity analysis of thyper-paammeee ablation study on various combi- nations of graph properties.
4.1 EXPERIMENTAL SETUP
Datasets. The datasets for pre-training and testing, and their detailed statistics are listed in Ap- pendix C The datasets for pre-training are collected from different domains, including social net- works, citation networks, and movie collaboration networks. We then evaluate the pre-trained mod- els 13 real-world graphs. including large-scale datasets with millions of edges from Open Graph Benchmark Hu et al. (0200).. Some of them are from the similar domain as pre-training (like citation networks), while most of them are from totally unseen domains (like web networks, transportation networks, protein networks and others).
Baselines. We comprehensively evaluate our model against the following baselines for node clas- sification and graph classification tasks, respectively. For node classification tasks, ProNE Zhang al. (2019), DeepWalk Perozzi et al. (2014), struc2vec struc2vec/Ribeiro Ribeiro et al. (2017), Veliekooi et al. (2019, y. GAE Kipf et al. (2016), and GraphS Hamilton et al. (2017) 7 are used as baselines, and then the learned representations are fed into the logistic regression for node classification (as most of baselines did). As for graph classification tasks, we take graph2vec Narayanan et al. (2017), In- foGraph Sun et al. (2020), DGCNN /Zhang et al.] (20T8) and GIN Xu et al. (2019) as baselines, and then feed the representations into SVM as the classifier (as most of baselines did). For both tasks, also compare our model with (1) Random, where random vectors are generated as representations; BouphhClYooeeee You et al. (2020a), GNN pre-training scheme based on contrastive learning with aug- mentations; (3) JOAO You et al. [2021) a GNN pre-training scheme that can automatically select data augmentations; (4) GiC et al. (020), the state-of-the-art cross-domain graph pre-training model (the version of our model without data selection scheme, which trains on all pre-training data). GCC, GraphCL. and JOAO are trained on the entire collected input data, and the suffix (rand, fine-tune) indicates that the model is trained from scratch. We also include 4 variants of our model: (1) APT-G, which removes the criteria of graph properties in the graph selector: (2) APT-P, which removes the criterion of predictive uncertainty in the graph selector; (3) APT-R, which removes the regularization w.r.t old knowledge in Eq. (5) (4) APT-L2, which degenerates the second term in Eq. 5 to the L2 regularization.
(2) GraphCL
Experimental settings. In the training phase, we iteratively select graphs for pre-training until the predictive uncertainty of any candidate graph is below 3.5. For each selected graph, we choose those samples with predictive uncertainty higher than 3. We include M = 500 query subgraph instances in graph when measuring the predictive uncertainty of this graph. The time-adaptive parameter Y in Eq. (4) is drawn from 7/2 ~ Beta 3.). where & = 3 - 0.995'. We set the trade-off parameter r5 = 10 for all j for APT-L22, and X; 500 for APT. The total iteration number is 100. We adopt GCC as the backbone pre-training model with their default
Note that we can also use other pre-training models like GraphCL the backbone, but we do not report them due the non-ideal performance of GraphCL. In the fine-tuning phase, we select logistic regression or SVM as the downstream classifier and adopt the same setting as GCC. See Appendix | for more details.
4.2 EXPERIMENTAL RESULTS
Node classification. Table D presents the micro Fl score of different methods over 10 unseen graphs from a wide spectrum of domain for node classification task. We can observe our model beats the graph pre-training competitor by an average of 9.94% and 17.83% under freezing and fine-tuning mode respectively. This suggests that instead of pre- veetraining on all the collected graphs (like GCC), it is better to choose a part of graphs better suited for pre-training (like our model APT). Moreover, compared with the traditional models without pre-train the performance gain of our
7

---

Under review as a conference paper at ICLR 2023
Table 1: Micro Fl scores of different models in the node classification task. The column "A.R." reports the average rank of each model. Asterisk (+) denotes the best result on each dataset, and bold numbers denote the best result among graph pre-training models in the freezing or fine-tuning tine-tuning setting. The notation "/" means out of memory or convergence for more than three days.
Method
Dataset
brazil
66242
dd68
dd687
Wisconsin
cocnell
COEL
pubmed
ogbarsiv
oghproteins A.K.
Rendom
12.66(3665)
6.71(2.44)
8.206435
5.9/22770
26 26.7918.35 59)
50
30.7777.26 26)
26
8D1 62)
58. (5,85/0766 76) 11 69)4 52.69K5 94)
13.2
ProNE
50,24(11 .6)
(0.04(2.56)
7.7343.11
3
(1.677
07.321 12. 14)
80, (0..7662.992 (2)
78.50e0 98)" 65 9660
76.2810.34y'
7.5
DeepWalk
43.16(16.75 78)
8.110145)
6.72(3.04)
6.17(2.18)
39.61 (1) 47.6788 30)
49.8519 26)
44 9% 10.89)
16.04 (2.98)
64.7440.4)
8.7
2truc2ves
25.54411.20 14)
13.71(2.661
10.30(323)
7.98(274)
45.2917.6)
38,3919.15
18)
36.01(2411
44 44.4500.78)
10.6
DXG
56.4447.79)
14.35/044
44,5700.4)
11.04(193)
40.4615.460
50.0210.44)
42. 94)9998))
12.93(7.67)
55.98/0.33)
GAB
57.88(10.65
14.0%
134430096)
(0.25226)
45.78(4.188
19.2615.20 24)
40 (0)
67.9399228
14,3300.33 371
13.550770)
10
47.0311 980
20-200144 46)
25.93(1.76)
39.9410.02))
7.1
CraphCT. (freeze)
50.71(5.00)
9.53.2.50 50)
0.36(366)
603(1.56)
88,85(10.8)
41
16.9512000 19) 070
12.2
JOWO (irecae)
71.22/7.211
7.98(2.90)
12.36(2.59)
53411443
42.
02.691833 15)
43.16(5.67)
18.13(2.22
41.05(0.87)
10.9
GOC (Treeze)
67.47(4.091
158340880
11,95(1133
(9)
46.701.73
55.4710.11)
26 4000 18)
14 14.56/7660)
59.15 111055005 35)
7.0
APT-G (fhocze)
68.69(3422)
17.21(1.3))
11.96:0.75)
9 554(199
54.45(1 90)
46
5N: 59)
34
24
46 49/0 22)
12. 32
60.38:0.41)
6.3
APTP (frozze)
66.55.2.55)
58.077
(2
10 (0.39
51
901 64)
47
122332211 11)
556300 56) 46 160 12)
12 86 54)
60 12.00/0333 32)
6.2
APTE (freeze)
68.12(3.0)
16.72(0.72)
12.42:120 24) (1)0510.8)
54. 18)
5011 06)
34.900366
46.0210.11)
18. 18.7915.3 87) 62.1800.06
5.0
APE-L2 (frecae)
(9.82/2.521
16.780.80
12,8(085))
10.341112)
55.1111.44
48.76(2.20)
43)
16.1(1015)
19.6416.46)
60.25500377
4.4
APT (frceve)
78.292.55)
15 (2
181
70)
22.04(0.20)
62.29(0.55)
CrapheT Teand, Inn-tume
638M 18) 45
40730000)
JOAO (rand, fine tume)
72.14(6.74)
20.932.855 85
1.08(2115)
7 1.003.00 18)
38.388...00 30 45 (0.3)
29.93/2
84)
62.0100.68)
9.6
GOC (rand, fine-tune)
58.51(3.07
15.95/1.15
13.16<
(6)
9.75(5
53
53.512230 58)
50.95 26)
43
41.700055)
49.7210.17)
18.01 880
59.12/0.35)
7.6
GraphCT. (fine-tune)
73.57(10335)
15.35.0.99 99)
13.5112.57)
10 (4))
63 635556442 42)
010022241
50 36) 42 12.91(0911
7.5
JOAD (lne tune
75.0015761
10.54(3.077
1.54)
50.0012.20 S.77(2.39)
28)
42.
(2.10()0.2)
29. (4)
42.2110.888
9.5
GOC (fhn--unn))
34.5663.05)
19,33(0.80) 90)
13.87(1.13) 13) 10.371 (6)
50. 4714 49)
48.33(2.423
(2)
38)
508870.199
18 62662.992 92) 60.0510.56)
6.4
APT-G (line-tnne)
77.601
25,4500.600 60) 17.78k 14)
11
370
66
02.0992.22 28)
508110 53,02 51) 636
(8)
27. 334
60.02:0.32)
32)
3.8
APLPP
78.9922441
25.1900.87)
(..991.19)
2412
39) 45.530030)
50.6610.18
27. 20.200 800
59.8600322)
4.8
APT-R (line-tune)
24.9600557
66
53.56(2.28)
83)
00/0001)
10/0 38)
3.4
APT-L2 (flac-nune)
78.75/ 631
24.62/0900
12.3660 787" 040 50)"
52.401
95) 4M0
25)0
27 40)4 60.8500.46)
2.6
APT (fine-tune)
79.67(2.30)
28.62(0.55)
20.30(1.13) 12.8K1.54) 1.78)
52, (5)2.2))
47.51(662)
51.30/0.16) 27.48)))7) 61.64(0355)
1.3
model is attributed to the transferable knowledge learned by pre-training strategies. We also find that some proximity- -based models like ProNE enforce neighboring nodes share similar representations, thus they perform well on graphs with strong homophily rather than weak homophily. Graph classification.
The micro Fl 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 find that the variants of APT per- form well under graph classification, indicating that we can apply a version with simpler archi- tecture in practice yet achieve good results.
Table 2: Micro Fl of different models in the graph classification.
Method
Dataset
indi-binary
dd
m1
A.R.
Random
32,30(433
52.7 32.724.34 34)
4.492 14)
11
graph2vec
56.20/5.33)
47.16(347)
8.22(3.67)
7.7
InfoCimph
66.5800633
58.6600.33
6.010599
7.7
GRAJAC (hiesie)
18
37.32277
"3344/7777)
9.3
IOAO (freeze)
63.90(3.48)
55,97(3.611
5.09(2.65)
9.3
GOC (frezze)
73.0%0.55)
75.1660.53
11.61(1.33)
APT-G (freese)
73.10/0.39)
75.24/0.42)
12.
APT-P (frezze)
72.83/0.11)
76.38(0.32)
(3.30/0.57)
3.0
APTER (freaze)
73.98(0.21)
75.
02.32/0.33 34)
12,9010.57 57)
3.0
APT-L2 (freeze)
73.54/0.40)
75.8160.30)
13.16/0.77
(freese)
73.00/0.50)
75.83/0.311
1381(1.0)
The data sequentially selected via our graph selector are uillinois, soc-sign0811, 1, msu, michigan, wiki-vote, soc-sign0902 and dblp. To further analyze why these graphs are chosen, we present their detailed struc- tural properties in Table | in the Appendix C We first observe that uillinois, michi- gan and msu have the largest value of (EAN(eeuuegy Qdensity: davg.deg: odeg.var -Qa), while dblp has the smallest. This shows that both criteria, the graph properties and the predictive uncertainty, play an important role in data selection. Moreover, is also interesting to see that wiki-vote 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.
Analysis of the selected graphs.
DGCUN
21.00400)
33.6114.66)
6010159)
11.3
GIN
72.00/2.11) 77.61(1.47)
10.54;5.085 08) 6.0
GANKT (rani, linetine
671606667 SKK1312
"875/13545"
12.7
JOAD trand. fine-tune)
67.70(3.35) 62.10(4.11)
11.10(3.06) 10.0
GCC (rand, line-tmne)
7..80(1.37) 74.26(0.59)
17.18(1443)
7.3
GrapeCt (line-time)
66 66.9044399)
65.55(5.14)
(.77(2600)
10.7
JOAD (fine tunc)
68.50(3.61)
62.61(4.99)
(0.18(1.72)
GCC (line-lane)
76.1900.90)
75.32(1.77)
64.90(6665)
4.7
APT-G (fine-tune)
76.2500899
75.46(0.77)
21 94(0.73)
4.7
APT-P (finc-tune'
76.70(1.01)
24.32(1 75.34(0.88)
22)
APT-R (line-tune)
76.601100
75.6400.70 70) 24.09/
APT-1.2 (fine-tune)
75.58(1 75.93(0884
(6)
25.58(
APT (Eie-tunc)
76.27(1.20)
75.69(142)
21.11(1.22 3.0
4.3 DISCUSSION: SCOPE OF APPLICATION
The transferability of the pre-trained model comes from the learnt representative structural patterns and the ability to distinguish these patterns (as discussed in $2). Therefore, our pre-trnining 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 ogbproteins) may not benefit too much from models. Similar observation can
8

---

Under review as a conference paper at ICLR 2023
also be made 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) Vishwanathan et al. (2010); Gardiner et al. (2000).
RELATED WORKS
Pre-training in CV and NLP. Initially, the CV community benefits from the models like Vi- sion Transformers Liu et al. (202I), MLP-mixers (Tolstikhin al.] (202T) and ResNets HHe et al. (216)) which are supervised pre-trained on large-scale image data. To take full advantage of mas- sive unlabeled data, NLP community adapts self self-vuuer learning models like Transformer-basee encoder Vaswani et al. (2017); Radford & Narasimhan| (2 (2018) Devlin et al. (2019) for language pre- training. When pre-training in CV and NL.,, researchers find that scaling up the pre-training data size would results in better or saturating performance in downstream Tan & Le (019); Kaplan (ct al.) (2020); El-Nouby et al.] (202T); [Abnar et al. (2022); Raffel et al. (2020). However, this is not true in graph pre-training. In this paper we argue that adding input graphs pre-training samples does not necessarily improve, but sometimes even deteriorates the downstream performance.
In view of the above phenomenon in CV and NLP pre-trat rre-training, data selection is not active search direction. The only related research we notice focus on domain-specifie pre- traininiig models, which select pre-training data that is most similar to the downstream domain Cui et al. (2018); Belt- agy et al. 2019): Dai et al.] (2019) 2020 Yan et al. (2000); : Lee et al.] (2020); : Chakraborty et al.
(2022). The assumption on the knowledge of downstream domain is different from the across-
domain graph pre-training in our paper, and thus data selection in CV/NLP pre-training is not that
relevant to the current work.
in CV and NLP, recent efforts have shed the light on pre-training GNNs. Initially, some unsupervised graph representation learning can be used for graph pre- pre-training Tang et al. (2015); He et al.] (l.](20)) (2016); Grover & Leskoved ()
Graph pre-training. Taking inspiration from the
Narayanan al. (2017); Ribeiro et al. (2017): 7): Donnat et al. (2018); Zhang et al. (2019): Hamilton et al. (2017). They are designed based on neighborhood similarity assumption, thus cannot general- ize to unseen nodes and graphs. Later, a line of graph sulf--upe learning can be also treated as graph pre-training which are categorized into two folds: graph generative models and contrastive models. Graph generative models capture the universal graph patterns by recovering certain parts of input graph (e.g., masked structure or attributes) Kipf et al. (2016); Wang et al. (2017); 7y: Hu et al. (2020c); Cui et al. (2020); (Hou et al.] (2022). These works rely on specific domain knowledge for example the nodeledge/attriute type should be the same, which makes them difficult to trans- fer across different types of graphs.f On the other hand, graph contrastive models maximize the agreement between positive pairs and minimize that between negative pairs Velickovic et al. (2019);
Hu et al. (2020b); You et al. (2020a); ; Zhu et al.] (2020): Hassani & Khasahmadi (2020); S Sun et al.
(2020) Li al. (2021 ; Lu al. (202)); b Sun et al. (202) ): Zhu al. (20215): Xu et al. (2021 Zhu ce al. (2021a) Lee et al. (022)) ; Zeng & Xie 2021 ): Zhang et al. (2021b); Han et al. (2022) One
design appropriate data augmentation like attribute masking, edge pertur- bation, node dropping, diffusion, etc., which either performed on node attributes or the whole graph structure. So they only achieve transferability in graphs from similar (or the same) domains, or the downstream task is restricted to graph classification. With the purpose of learning transferable pat- terns across different domains, some works take subgraph sampling as augmentation, such that the transferable (sampled) subgraph patterns can be captured during pre-training Qiu et al. (2020); You et al. (2020a) 202T). However, these existing works only focus on how to design the pre-training model. rather than how to select data for pre-training. Our paper first points out the necessity of selecting data, and fills the gap of the data selection strategy in graph pre-training.
of the technical cores
6 CONCLUSION
In this paper, we observe that big data is not a necessity for pre-training GNNs. This motivates us to wisely choose some suitable graphs and samples for pre-training rather than training on massive amount of data. Without any knowledge of the downstream tasks, we propose a novel graph selector to provide the most instructive data for the model. The pre-training model is then encouraged to learn from the data in progressive way and reinforce itself on newly selected data. We integrate the graph selector and the graph pre-training model in a unified framework, and form a data-active graph pre- trainngnn (APT) paradigm. The two components in APT are able to mutually boost the capability of each other. Extensive experimental results show that the proposed APT framework can enhance model capability with fewer number of input data.

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
We provide an open-source implementation of our model APT at htttps://githin comb.com/ anonymous APT ai/Anonymous APT- code Hyperparameters necessary for reproducing
the experiments can be found in $4.1 Appendix D and Appendix F Users can run APT on their own datasets.
ETHICS STATEMENT
This paper empirically identifies the curse of big data phenomenon in graph pre-training, and devel- ops novel data-active graph pre-training framework. All the experiments are conducted publicly available datasets for reproducibility purposes. Overall, this work inherits some of the risks of the existing works implementing these pre-existing datasets, and the risks are not amplified by the work. Therefore, this present paper likely does not introduce any new ethical or future social concerns.
REFERENCES
Samira Abnar, Mostafa Dehghani, Behnam Neyshabur, and Hanie Sedghi. Exploring the limits of large scale pre-training. In ICLR, 2022.
Iz Beltagy, Kyle Lo, and Arman Cohan. Scibert: A pretrained language model for scientific text. In EMNLP-IJCNLP, pp. 3615-3620, 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, pp. 41-48, 2009.
Zdzislaw Burda, Jarek Duda, Jean-Mare Luck, and Bartek Waclaw. Localization of the maximal entropy random walk. Physical review letters, 102(16):16000,, 2009.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embed- ding. arXiv preprint arXiv: 770.00508, 2017.
Shuvam Chakraborty, Burak Uzkent, Kumar Ayush, Kumar Tanmay, Evan Sheehan, and Stefano Ermon. Efficient conditional pre-training for transfer learning. In CVPR, pp. 4241-4250, 2022.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 1999.
Ganqu Cui, Jie Zhou, Cheng Yang, and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. KDD, 2020.
Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge J Belongie. Large scale fine-grained categorization and domain-specifh, transfer learning. In CVPR, pp. 4109-4118, 2018
Xiang Dai, Sarvnaz Karimi, Ben Hachey, and Cecile Paris. Using similarity measures to select pretraining data for ner. In Proceedings of NAACI-HIT,, pp. 1460-1470, 2019.
Xiang Dai, Sarvnaz Karimi, Ben Hachey, and Cecile Paris. Cost-effective selection of pretraining data: case study of pretraining bert on social media. In EMNLP (Findings), pp. 1675-1681, 2020.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLLT, pp. 4171-4186, 2019,
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: deep convolutional activation feature for generie visual recognition. In ICML, pp. 647-655, 2014.
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In SIGKDD, pp. 1320-1329, 2018.
David Easley and Jon Kleinberg. Networks, crowds, and markets: Reasoning about a highly con- nected world. Cambridge university press, 2010.
10

---

Under review as a conference paper at ICLR 2023
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 arXhv:2112.10740, 2021.
Eleanor J Gardiner, Peter Willett, and Peter Artymiuk. Graph theorette techniques for macro- molecular docking. Journal of Chemical Information and Computer Sciences, 40(2):273-279 2000.
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accu- rate object detection and semantic segmentation. In CVPR, pp. 580-587, 2014.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD, pp. 355-864, 2016.
Hakim Hafidi, Mounir Ghogho, Philippe Ciblat, and Ananthram Swami. Graphcl: Contrastive self- supervised learning of graph representations. arXiv preprint arXiv:2007.08025, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. NewrlPS, pp. 1025-1035, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In ICML, pp. 8230-8248, 2022.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. ICML, pp. 4116-4126, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pp. 9729-9738, 2020.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In SIGKDD, pp. 594 604. 2022.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0000 00687, 2020a.
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, 2020b.
Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. arXiv preprint 3rXiv:1905.13728,,00 2019.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In SIGKDD, pp. 1857-1867, 202cc.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Thomas N Kipf et al. Variational graph auto-encoders. NIPS Workshop Bayesian Deep Learning, 2016.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska Barwinska, al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):3521-322 2017.
Adit Krishnan, Mahashweta Das, Mangesh Bendre, Hao Yang, and Hari Sundaram. Transfer leamn ing via contextual invariants for one-to-mam momy cross-domain recommendation. In SIGIR, pp. 1081- 1090, 2020.
11

---

Under review as a conference paper at ICLR 2023
Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jae- woo Kang. Biobert: pre-trained biomedical language representation model for biomedical text mining. Bioinformatics, (6(44):234411 2020.
Namkyeong Lee, Junseok Lee. and Chanyoung Park. Augmentation-free self-supervised learning on graphs. In AAAI, pp. 7372-7380, 2022.
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, pp. 2694-2700, 2021.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In ICCV, pp. 10012- 10022, 2021.
lyya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint 15 1.06343 2015.
Yuanfu Lu, Xunqiang Jiang, Yuan Fang, and Chuan Shi. Learning to pre-train graph neural networks. In AAAI, pp. 4276-4284, 2021.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. NeurIPS, pp. 3111-3119, 2013.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05000 2017.
Mark E. J. Newman. The structure and function of complex networks. SIAM Rev., 45:167-256, 2003.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, pp. 701-710, 2014.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In SIGKDD, pp. 1150-1160, 2020.
Alec Radford and Karthik Narasimhan. Improving language understanding by generative pre- training. 2018
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 unified text-to-text transformer. J. Mach. Learn. Res., 21(140):1-67, 2020.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In SIGKDD, pp. 385 394, 2017.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region- based object detectors with online hard example mining. In CVPR, pp. 761-769, 2016.
Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, Iasonas Kokkinos, and Francese Moreno-Noguer. Fracking deep convolutional image descriptors. arXiv preprint arXiv:4412.6537, 2014.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph representation learning via mutual information maximization. In ICLR, 2020.
Mengying Sun, Jing Xing, Huijun Wang, Bin Chen, and Jiayu Zhou. Moel: fingerprint via knowledge-avee contrastive learning from molecular graph. In SIGKDD, pp- 3585-3594, 2021.
Data-driven molecular
12

---

Under review as a conference paper at ICLR 2023
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In ICML, pp. 6105-6114, 2019.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. WWW. pp. 1067-1077, 2015.
Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp-mixer: An all-mip architecture for vision. NeurlPS, pp. 24261-24272, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention all you need. NeurIPS, 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. 2019.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
C. Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. CIKM, 2017.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. pp. 30414-30425, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks. In ICLR, 2019.
Xi Yan, David Acuna, and Sanja Fidler. Neural data server: A large-scale search engine for transfer 2020.
learning data. In CVPR, pp.
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.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. NeurlPS, pp. 5812-5823, 2020a.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks. In ICMI., pp. 10871-10880, 2020b.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In ICML, pp. 12121-12132, 2021.
Jiaqi Zeng and Pengtao Xie. Contrastive self-supervised learning for graph classification. AAAI, pp. 10824-10832, 2021.
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. Prone: Fast and scalable network representation learning. In IJCAI, pp. 4278-4284, 2019.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. AAAI, pp. 4438-4445, 2018.
Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. Alg: fast and accurate active learning framework for graph convolutional networks. In SIGMOD, pp. 2366-2374, 202
Zaixin Zhang, Qi Liu, Hao Wang, Chenggiang Lu, and Chee-Kong Lee. Motef-based graph self- supervised learning for molecular property prediction. In NeurlPS, pp. 15870-15882, 202
Jingbo 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, pp. 1137-1144, 2008
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint 2006v:2006.0413/ 2020.
13

---

Under review as a conference paper at ICLR 2023
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In NeurlPS D&B, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, 2021b.
14

---

Under review as a conference paper at ICLR 2023
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 Lynn et al. (2020). We here theoretically show some connections between the proposed network entropy and typical structural properties.
To make theoretical amalysis, we consider connected, unweighted and undirected graph, whose net- work entropy depends solely its degree distribution (see Eq. (3) Considering random graph G with a fixed node set, we suppose that the degree of any node v independently follows distribution
p. which common setting in random graph theory GardenGa & Latora (008). Then the
expected network entropy of G is
(H(G)) = 2 Σ (d, log d.) (d d)
(6)
(d)
where every d, (and d) is an 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 o).
Average degree. Given that the function x: llog is convex in æ, we have
(H(G)) 2 (d) log(d)
log(d).
(d)
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 log d) in Eq. (6) at (d) gives
Var(d)
(M(G)) log(d) 2(d)² +o
where Var(d) the variance of d. We find that log(d) 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 implics a positive correlation between degree variance and the test performance of the model.
Scale-free exponent. Most real-world networks exhibit an interesting scale-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(x) ~ x where a called the scale-free exponent. For real-world network, the scale-free exponent is usually larger than Clauset et al.) (2009). Suppose the degrees of random graph G with N nodes follows power- law distribution p(x) Ca-a where C' normalization constant. When approximately have Gömez-Gardenes & Latora (0088
we could
(H(G)) a a-2' if oc.
Clearly, a smaller scale-free exponent a results in a higher network entropy.
Remark (Connection between network entropy and typical structural properties) 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-fre free exponent. (A smaller scale-free exponent indicates the length of the tail of degree distribution relatively longer, i.e., the degree distribution spreads wider. )
15

---

Under review as a conference paper at ICLR 2023
B ALGORITHM
The overall algorithm for APT is given in Algorithm [ Given a collection of graphs g = {Gi...., Gr} } from various domains, APT aims to pre-train better generalist GNN (i.e., pre- training model) on wisely chosen graphs and samples. Our APT pipeline involves the following three steps. (i) At the beginning. the graph selector chooses graph for pre-training according to the graph properties (line 1). (ii) Given the chosen graph, the graph selector chooses the subgraph samples whose predictive uncertainty is higher than T. in this graph (line 3). (iii) The selected samples are then fed into the model for pre-training until the predictíve uncertainty of the chosen graph below Tg or the number of training iterations on this chosen graph reaches F (line 4-5). (iv) The model's '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 are 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 Overall algorithm for APT.
Input: A collection of graphs 9 = [GI..... Gy }. maximal period F of training one graph,
trade-off parameter 7/2 = O, hyperparameter (3e), the learning rate μ4, the predictive uncertainty threshold Ty of moving to a new graph, the predictive uncertainty threshold T, of choosing training samples, and the maximum iteration number T.
Output: Model parameter 0 of the pre-trained graph model.
I: Choose a graph G from G via the graph selector, and g + gVG").
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 + - VV)
5: if @unscrtain (G*) < T. or the model has been trained on G by F "iterations then
6: Update the trade-off parameter 7/2 ~ Beta (1, B,).
7: Choose graph G* from G, and G <- 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 is [V), the batch size is B, and D is the representation dimension. (1) As for the data augmentation, the time complexity of random walk with restart is at least (BBV)S)) Xia et al. (2019). (2) The time complexity of GNN encoder propagation depends on the architectures of the backbone GNN. We denote as here. (3) The time complexity of the contrastive loss is D(2DD) Li et al. (2022). (4) Sample selection is conducted by choosing the samples with high contrastive loss (the loss computed before), which costs O OBB). (5) Graph selection costs uncertainty of graph, and [G] is the number of graphs that have not been selected). This step is executed only in 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[V + X + B² + B).
(where M the number of samples needed to compute the predictive
C DATASET DETAILS
The graph datasets for 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 as follows. When selecting pre-training data, we hope that the graph size is at least hundreds of thousands to 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, model's 's in and across-domait 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 millions.
so to comprehensively evaluate
16

---

Under review as a conference paper at ICLR 2023
Regarding the pre-training datasets, arxiv, dblp and patents- main citation networks collected from |onchi et al. )2012). Yang & Leskoved (2012) and Hall et al. (200T), respectively. Imdb is the collection of movie from Rossi & Ahmed (2015). As for the social networks, Soc-sign0902 and
soc-sign081 are collected from Leskovec et al. (2009), wiki-vote is from [eskovec et al. 2010),
academia is from Fire al. (2011), and michigan, Regarding the test datasets, we collect the protein network dd and ogbproteins from Dobson & Doig (2003) and Hu et al. (2020a). The image network msre-21 is from Neumann et al. (2016). The movie network imdb-binary is from Yanardag & Vishwanathan (0015). The citation networks, cora, pubmed and ogbarxiv, are from McCallum et al. (2000), Namata al. (2012) and Hu et al. (2020a).
and uillions
from [Taad al. 2012).
The web networks cornell and wisconsin are collected from Pei et al. (2019). The transportation
network brazil is form Ribeiro et al. (2017). , and dd242, dd68 and dd687 are from Rossi & Ahmed (2015).
The detailed graph properties of the pre-training data and test data are presented in Table and Table 5 respectively.
Table 3: Datasets for pre-training and testing, where denotes the average statistic of multiple graphs under graph classification setting. [V] and E| denote the number nodes and the number of edges in graph, respectively.
Type
Name
V
E
Description
citations
arxiv
86,376
517.563
citations between papers the arxiv
dblp
93,156
178,145
same as 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
soc-sign081
77,350
468,554
same as above (Nov. 2008)
wiki-vote
7.115
100,762
voting relationships between wikipedia users
ucademia
137.969
369,692
friendships between academics Academia.edh
michigan
30,147
1,176,516
friendships between Facehook users University of Michigan
32,375
1.118,774
above (Michigun State University)
uillinois
30,809
1,264,428
above (University of Uillinois)
movie
imdl
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
msrc-21
77.52"
198.32"
adjacency between superpixels of the image segmentations
test data
imdb-hinary
19.77*
96.53"
collahoration relationships between actors/actresses
citations
2.708
5,278
citations between Machine Learning papers
pubmed
19,717
88,648
citations between scientific papers
ogharxiv
169,343
I, 1,1,,,243
citation network between computer science arXiv papers
web
cornell
183
280
hyperlinks between webpages collected from Cornell Univer-
sity
wisconsin
466
same as above (Wisconsin University)
transportation others
brazil
2,077
commercial flights between airports Brazil
dd242
1,284
3,303
this network dataset in the category laheled networks
dd68
775
2,093
above
dd687
725
2,600
above
Table 4: Detailed structural properties of pre-training datasets, where avg properties equals to MEAN Wentrogy: ( davg_deg; Ødeg.var, -Q.) ) in Eq. 44). and neiz denotes the average number and standard deviation of hop neighbors, [V| and [E] denote the number nodes and the number of edges in graph, respectively.
Properties
Datusel
[V]
[F]
avg properties avg degree degree var density
entropy
0
meig (avg, std)
avg clustering
signf9922
81867
497671
40.32
13.16
1643.20
49
3.91
1.51
1192.33, 2315.99
0.06
soc sign08111
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.42e-06
3.07
1.53
316.16,
614.03
5c-05
pulent
240547
560943
.0.96
5.66
34.95
1.94-055
2.04
1.57
117.23,
172.40
0.08
academia
137969
369692
-0.89
6.36
102.14
3.88e-05
2.38
1.57
101.40,
225.96
0,14
wiki- Vote
7115
103689
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.11c-05
2.16
1.72
58.85, 90.46
0.27
arxiv
86376
517563
-0.43
12.98
382.12
1.39c-04
3.22
141
145.21, 309.12
0.68
michigan
30147
1176116
1.40
79.05
6369. 17
2. 3.59--03
4.78
1.23
4683.90.
3655.25
0.21
5087.53
2.133.03
4567.63,
3465.16
uillinois
30809
1264428
1.44
83.08
6306.02
2.66e-03
4.78
1.22
5267.10, 3831,37
0.21
17

---

Under review as a conference paper at ICLR 2023
Table 5: Detailed structural properties of test datasets, where neiz denotes the average number and standard deviation of 2 2-hop neighbors, and the numbers with denote the average statistics of multiple graphs under graph classification setting. [V], | and | denote he number of nodes in graph, the number of edges in graph and the number of graphs in graph classification datasets, respectively.
Properties
Dotnsel
[V]
[5]
[C]
avg degree
degree vur
density
entropy
Relg (avg. std)
avg clustering coef * of classes
imdil Binary
19.77
193.06
1000
9.89
116.01
1,14
1.07
24,89 11.91
0.95
marc-21
198.32
6.10"
6.81e-02
1.71
17,00",
D.51
dd
284.32"
715.66
1178
6.00"
27.60"
2.78c-02"
1.65"
14,30" 5.68"
0.48"
2
2708
5278
4,90
42.53
1.4e-03
1.71
34,98,47.70
0.24
puhmed
2.28e-04
2.23
57.10,82.72
brazil
131
1074
16.85
539. 18
1.26c-01
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
17,40.8.93
dd687
725
2600
8.17
55.78
9.91c488
2.01
25.45,9 4.4.999.0
0.48
20
wiscosin
251
466
4.65
76.26
1.49-002
1.84
68.04
0.23
oghanxiv
16343
1157199
14,67
489% 17
8.776-055
3.63
3483 671
0.23
40
oghproteins
132534
39561252
598.00
742637.58
4.50c-03
6.84
32265.17, 1,111141144
0.28
D ADDITIONAL OBSERVATIONS OF Curse of Big Data PHENOMENON
This section provides more comprehensive observations to support the curse of big data phe- nomenon cross-domain 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 Qiu et al. (2020) and GraphCL Hafidi et al. (2020) model with different model configurations (i.e., the number of GNN layers is set to be 3, 4 and 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. Note that GCC and GraphCL are the only two pre-training models that can be adopted for the cross-domain 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 and Figure 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 deviation among the results w.r.t different graph last is also marked by the blue arrow. The figures the last column illustrate the effect scaling up sample size (log scale) on the performance.
dotted line. The largest standard
Table 6: The value of parameters for fitting the curve according to the function f(x) d1 In 2n
4g (a1, 02 0g > 0), based on the points the last column in Figure and Figure
GCC
GraphCL
Parameter
Dataset
Q1
02
Q3
a1
Qa
03
cora
0.45
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
29.59
0.19
41.83
dd242
6.60
0.08
3.82
7.84
0.12
0
dd68
6.44
0.11
3.83
2.08c+177
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
imdh- mind-bbnarry
7.43
0.13
64.97
1.06
0
51.69
dd
0.81
0.31
75.53
13.76
0.10
36.33
msrc
5.56
0.11
4.85
4.71
0.13
18

---

Under review as a conference paper at ICLR 2023
The explanation of convex hull fit. In order to better show the changing trend, the blue curve in the last column Figure 5 and Figure i is fitted to the convex hull of the points. The convex hull is proposed to capture the performance of randomized classifier made by choosing pre-training models with different probabilities/ Abnar et al. (2022).
We first introduce the concept of randomized classifier. Given two classifiers with training sample size and downstream performance с₁ (ef .ft) and C2 (c d)), a randomized classifier can be made choose the first classifier with probability p and the second classifier with probability 1-p. p.
Then the output of the randomized classifier is pcl + (1 - p)c2, which is the convex combination of C1 and cg. All the points on this convex combination can be obtained by choosing different p. Extend the notion to the case of multiple classifiers, we can consider the output of such a random- ized classifier be convex combination of the outputs of its endpoints Abbnar et al. (2022). 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.
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 Abnar et al. (2022).
final remark that our observations on different downstream datasets do not result a one- model-fits-ll trend. So propose to fit complicated curve whose function has form f(x) a In 2/2222 + 0g (a1, 02 03 > 0) to the best performing models (i.e., the convex hull fit as discussed above). The fitted parameters 01, 02 and ag in this function of each curve given in Table 6
19

---

Under review as a conference paper at ICLR 2023
wisbonsin
wisconsin
nocd cadis,
muCCO F1
mase 17
SOUOO FT
micro F.1
leyess
:1.5
byyers
000
12 samples
of graphs
# of graphs
of graphs
brazzl
brazzil
bracil
brazal
mieer oF1
miteoo Fl
mmoo F1
milero S
19
3 sumples
graphs
A of graphes
of graphs
12 8d687
83687
dd687
mnteoo F1
mntero Fl
misro Fl
Lawees of graphs
10l samples
of graphs
of graphs
Node classifcction
micro F1
MF242
micro F1
G6242
micro Fl
6d242
micro Fl
dd242
0,6 laerg
O00 graphs
DOC boven
graphs
graphs
samples
iid68
120 Bol68
mico F7
sod: 1.0
micro F]
micro
miero
sdd 0.5
GUL byars
coco loca
000 loyns
graphs
graphs
graphs
of samples
15.1
miero F1
Coma
micro F1
micro
500 0.7
rid 0.8
losta
D3 Byyen
graphs
graphs
graphs
samples
Nehmed
pubmed
pubmed
pubmed
migo Fl
sad 0.3
mitoro Fl &
micro
80
sdd 0.3
bocad
10
graphs
of graphs
of graphs
#f samples
Cormell
cornell
cornell
curnel
micro F1
micro Fl
sid 22.0
micro
bul 1.3
mnieo +
of graphs
of graphs
of graphs
# of samples
mikooo
si
InloroF
0.6
kyyes
boyan of graphs
(b) Gruph classification
of graphs
of graphs
samples
limdb-binaa binarry
limbb Sinury
binary
imdo Sinary
micro F1
11
micm Fl
micro F]
stl 1.3
12 sumples
of graphs
of graphs
gruphs
fhsee-21
msre-21
msre
miloo F1
La mimn
micro F1
migrr F1
12
graphs
graphs
graphi
samples
Figure 5: The additional observations of curse of big data phenomenon, performed on different GCC pre-training models.
20

---

Under review as a conference paper at ICLR 2023
Waccotsin
Wisconsin
Wiscontinn
Wiscoopiin
micro Fl
&
Styees
nicro
micro
Lxpers
Hil $5.0
ald 2.0
laper
Croplet
Gradel Aiens graphs
of graphs
of graphs
of samples
brazil
Krazii
orazil
micro F1
micro F1
micro
miceo
3.
GrephCL (4 legert
Go loonne
graphs
graples
graphs
#f samples
12.8
3d687
10
miler F1
0.8
micro Tl
add:
micro Fl
micro
Au
12
graphs
grappss
graphs
samples
micro F1
18. 64242
tso 0d242
mide Fl
x2 <MZ42
micro Fl
Bd2422
micro g
AMd
Sid 200
Node clasiifcation
Gr Ieens
12
graphs
graphs
graphs
of samples
ddfx
ad68
micro F1
1:
micro F]
micro
Cropert 17 Iavens
graphs
graphis
graphs
samples
27. Do1a
corá
175
miero F1
mikeoo Fl
micro Fl
35.
micco
CopActt
Cropert laser
graphs
of graphs
graphs
# of samples
Tubmed
fubmed
nubmed
pubcnod
Aimie Fi
ad.
std 1.7
Sd.0. 0.3
micro
micro
CopACt
25
of graphs
of graphs
of graphs
# of samples
combel
Corbell
Suraell
micro
Sul
mirero
micro
sod 5.1
miceo F!
byend
425
of graphs
# of graphs
of graphs
of samples
micro Fl
micco Fl
6d
miceo
std:
Grae L10 Sazoa
DraphC graphs
Gruph dlssificatios
grappss
graphs
samples
indb-binary
mid--hibrry
mmdh-binary
milan SooooF Fl
micmo Il
micro
sid 1.7
micro
x
sid 3.4
Gredicl koynn
Gryae liyen
Grogle kiyens
graphs
graphs
graphs
of samples
Pmsrr-21 I
21
21sco-21
Insro
micro-Pi
Il
micro. F]
std
std
sill
0.7
GreeKCL beyend
Cranact loger
Ceppctt Boans
of graphes
of graphs
graphs
samples
Figure 6: The additional observations of curse of big data phenomenon, performed different GraphCL pre-training models.
21

---

Under review as a conference paper at ICLR 2023
E EMPIRICAL STUDY OF GRAPH PROPERTIES
In Figure 7 we plot the Pearson correlation between the graph properties of the graph used in pre-training (shown in the y-axis) and the per- formance of the pre-trained model using this graph 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 a clear positive correlation with the performance, while the scale-free exponent presents an 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 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.
Additional properties for part (b) in Figure 2
posntive
coreiition
comelation
Regative coprolation
pubmed
hrazil
002
dd242
000
dd68
wisconsin
cornell
Entropy
Demaity
Avetuge dagree
Degres varaneed
Trmurvity Clique numther
Oegres stscstativi wity
Clustering coefficiont
Scate- Sealo-frce expertnt
Figure 7: Pearson correlation between the structural features of the graph used in pre-training and the performance of the pre-trained model (using this graph) on different unseen test datasets.
Detailed illustrations of Figure 3 In Figure the illustrative graphs are generated by the con- figuration model with 15-18 nodes. The shaded area groups the illustrative graphs whose network entropy and graph propertics are similar. Each four points on the same horizontal coordinate repre- sent four graph properties of 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 we provide a real-world example of how network entropy correlates with four typical structural properties (in red), as well as the performance of the pre-trained model on test graphs (in blue). Numerical experiments again support our explanation (or intuition) of their strong correlation.
Network entropy
Network entropy
Network entropy
Network entropy Performance (%)
Performance (%)
Performance (%)
Performance (%))
52
52
52
52
50
50
50
50
1e:3
2e:3
3e-3
46
20
10
60
46
20
10
60
46
1.35
1.50
1.65
(a) Density
(b) Average degree
(c) Degree variance
(d) Scale-free exponent
Figure 8: The red plot shows the network entropy (left y-axis) versus typical structural properties in graph (i.e.. density, average degree, degree variance, and the parameter in scale-free free network), and the blue one shows the pre-training performances on wisconsin dataset (right y-axis) versus structural features.
22

---

Under review as a conference paper at ICLR 2023
F IMPLEMENTATION DETAILS
The number reported in 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 We conduct all experiments on a single machine of Linux system with an Intel Xeon Gold 5118 (128G memory) and a GeForce GTX Tesla P4 (8GB memory). Our codes are available at bttps://githus: com/ anonymous-naee ai Ana.nyoonmm APT-code)
Implementations of our model. The regularization for weights of the model in Eq. ( is applied to first 2 layers GIN. The maximal period of training one graph F is 6, the maximum iteration number I' is 100, and the predictive uncertainty thresholds T, and T. tively. The selected instances are sampled from 20,000 instances each epoch. Since the pre-training model is unable 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 the same GCC.
set to be 3 and 2 respec-
Our model is implemented under the following software settings: Pytorch version 1.4.0+cu 100, 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 Syper-parameters used in the baselines.
Method
Hyper-parameter
Code
DeepWalk
The dimension of output representations is
64, walk length 10, number of walks
80
struc2vec
The dimension of oulput representations
32, walk length 80, number of walks
10, window size
DGI
512 hidden units GNN layer, learning
rate 0.001
GAE
hidden per GNN layer, learning rate 0:01
graph2vec
The dimension of output representations
graph2vee
128
InfoGruph
32 hidden units per GNN layer, 5 layers
Nttpsr//o1t.bb.coo com.be/yyoom/m/mmiincaa
http:///g11u5..com sur/1arorran
DGCNN
hidden
per GNN layer. learning
rate 0.001, batch size = 50 hidden units per GNN layer. learning rate 0.01. pooling
gnns
GraphCL
300 hidden units per GNN layer, 5 layers,
ALtp8://git.UD. wtt.:/tttu..co.......oo..mo Shen Lab/GraphCL
learning 0.001
GCC
64 hidden units per GNN layer, 5 layers, learning rate 0.005, number of samples epoch 20000
REtps: /ttt:///1tuu... www. wwt.R/EE...CC/////COOOO HCDM//CC
23

---

Under review as a conference paper at ICLR 2023
G ADDITIONAL EXPERIMENTAL RESULTS
Effects of hyper-parameter { The hyper-parameter {Aý} is the trade-off parameters between the knowledge learnt from new data and that from previous data in Eq. (5) We simply À 22 = = AR- We use the dataset dd242 as an example to find the suitable values of the hyper- parameter under the L2 and EWC regularization setting respectively, and present here for reference (see Figure 2 Clearly, too small or too large À would deteriorate the performance. Thus, an appropriate value of preferred 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.
16.8
16.5
micro F1
16.7
micro F1
16.6
16.3
16.5
10
50
100
100
300
500
700
(a) Ablation study APT-L2 (freeze)
(b) Ablation study APT (freeze)
Figure 9: Performance our model on dd242 w.r.t varying {Az}.
Effects of hyper-parameter F, F. T.. Our model training involves three hyper-part parameter F, Tg. T., where controls the largest number of epochs training on each graph, T, is the pre- dictive uncertainty threshold of moving of choosing training samples.
new graph, T, is the predictive uncertainty threshold use grid search to show F E (4, 5, 6)'s Tg E 3.5, 4)'s and T, E (, role in the pre-training. F remains 5 while studying T3 and T,, T, remains 3.5 while studying F and T.. and T, remains at 2 while studying F and Tg. Figure [0 presents the effect of these parameters, We find that if the value of F is set too small or that of Tg is too large, the model cannot learn sufficient knowledge from each graph, leading to suboptimal results. Too large F' or small 7, also lead poor performance. This indicates that instead of training on graph for a large period, it would be better to switch to training on various graphs in different domains to gain diverse and comprehensive knowledge. Regarding the seper-parameter T,, we observe that large T, would make the model having too few training samples to learn knowledge, and small T, could select the most uncertain and representative samples, thus both cases achieve suboptimal performance.
17.9
17.0
17.0
16.0
36.0
16.0
(a) Ablation study F
(b) Ablation study Tg
(c) Ablation study T₃
Figure 10: Performance of our model on dd242 w.r. varying F, T.T.T...
Ts.
The choice of 3i, its alternatives, and ablation study. the beginning of the pre-training, the model is less accurate and needs more guidance from graph properties. We therefore set 7 larger at the beginning and gradually decrease it. To simplify this process, we follow Cai et al. (2017) to the exponential formula of B, C1 ca to set the expectation of to be strietly decreasing (where " ~ Beta(1,8)).
The parameters C₁ and 02 in the exponential formula of Br 0.995 in Cai et al. (2017). We simply perform grid search on c₁ in in {1.005, 3, 5); see the effect ci in the Figure
c/ are suggested as 1.005 and
24

---

Under review as a conference paper at ICLR 2023
Table 8: Micro Fl of APT-L2 (freeze) with the different decay functions in the node classification task.
Dataset
Method
brazil
dd242
dd68
dd687
wisconsin
curnell
pubmed
linear
72.30(1.37) 16. (0..2800.5)) 42.74() 10. 22.2.900 54, 20(1200(050 1,50) 47. 47.66(1 (7.6611.5) (0.55)) 16.49(0.19) 68.70 16. 74(0.45) 12.86( 10. (0.09(0.76) 52.55(2.39) 48. 288.88(1.88). (8) 35, (5.40( 46.58(0.21) 69.82(2.32) 16.79(0.88)) (2.68(0.81) 10.34(1.12) 55.11(1.74) 48.76/2.20) 34.27(0.43) (6.21(0.15)
step
exponential
Table 9: Micro Fl of APT-L2 (freeze) with the different decay functions in the graph classification task.
Dataset
Method
imdb-binary
dd
msre-21
linear
73.66(0.34) 75.47(0.26) 13.01(0.788 78)
step
72.99(0.40) 75.41(0.41) (4.13(0.56)
exponential
73.54(0.40) 70.81(0.30) 13. 13.16(0.77)
We then illustrate that the choice of the decay function of 3, is robust. Table 8 and Table 9 below show the effect of linear decay, step decay and exponential decay on 3r. (The function for linear decay and step decay are designed as 3 = 2.001 + 0.004/, 3r 2.005 + floor(1/20), respectively. The initial value 31 set the same as ours.) While there is no universally better decay function, the performance of our method is not significantly impacted by the choice of different decay functions, and our performance is better than the baselines in most cases regardless of the choices of specific decay functions.
55
74
F1
54
73
53
72
1.005
1.005
(a) Wisconsin on node classification
(b) Imdb-binary on graph classification
Figure 11: Performance of APT-L-2 (freeze) w.r. varying C1-
Impact of five graph properties combination. As further experimental analysis, we study the effect of the strategy of utilizing only one graph property Table I0 and Table We find that the five properties used in our model are all indispensable, and the most important one probably varies for different tasks and datasets. That's why we choose to combine all graph properties.
Moreover, these case studies may provide some clues of how to select pre- pre-training graphs when some knowledge of the downstream tasks known. For example, if the downstream dataset extremely dense (like imdb-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.
The justification of input graphs' learning order. Table 12 reveals the downstream performance can be affected by the learning order of input training graphs. With the guidance of graph selector, the pre-training model is encouraged first learn the graphs and samples with higher predictive
25

---

Under review as a conference paper at ICLR 2023
uncertainty and graph properties. Such learning order accomplishes better downstream performance compared to the reverse or random one.
The choice of the "difficult" data. Among all the data, "difficult" samples contribute the most the loss function, and thus they can yield gradients with large magnitude. Comparatively. training with easy samples may suffer from inefficiency and poor performance as these data points produce gradients with magnitudes close to zero Huang et al. (2166) Sohn (2016). In addition, learning from difficult samples has proven be able to accelerate convergence and enhance the expressive power of the learnt representations (Suh et al. (2019); |Schroff et al. (2015). For our model, the importance of learning from difficult samples also justified empirically, as shown Table 13
Training time. As empirically noted in Table 14 the total training time of APT-L2 and APT is 18321.39 seconds and 18592.01 seconds respectively (including the time consumed graph selec- tion 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) if and only if the condition in line 5 in Algorithm is satisfied.
The time cost of the L2 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 is 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 to 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 relatively small among models in open graph benchmark Hu al. (2020b).
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- pre-trrined model have already been put close to appropriate and reasonable values; thus the model converges faster during fine-tuning on data. As shown in Figure compared regular GNN model (e.g. GIN), our model yields speedup of 4.7x average (which is measured by the ratio of the training time of GIN the fine-tuning time of APT). Based on above analysis, we can draw conclusion that pre-training is beneficial both in effectiveness and efficiency.
600
GIN
APT
running time (sec)
400
3.9X
200
T
T 4.9
5.2x
imdb-binary
dd
msrc-21
Figure 12: The running time of our model and the basic GNN model graph classification task. Our model achieves a speedup of 4.7x on average compared with GIN.
26

---

Under review as a conference paper at ICLR 2023
Table 10: The effect of different graph properties on downstream performance (micro Fl is reported) under APT-L22 (fine-tune) in the node classification task, The last row is our strategy combining all the graph properties, and each of the first five rows is the strategy of only utilizing one graph property.
Dutaset
Method
brazil
dd242
dd68
dd687
wisconsin
cornell
cora
pubmed
Entropy
80.04(2.15) 255.9(0.94) 16.31(0.81) 11.08(0.82) 67.012.000 $2. 80(2.00024 45, (1.50.10...00 50. (0(005
Density
79.23(1.92) 20.29(0.62) 19.89(0.95) 12.22( 65 58( 1 87) 51. 15(1.599 46. 18(0.71) 50.7400 74(0. 15)
Average degree
79.22(1.65) 24.99(0.67) 16.56(1.01)
(7.66 (..) 51,43(4.16 46.38(0.48) 50. (0.39)
Degree variance
78.44(2.24) 24.94(0.61) (6.62(1.04) 11.51(1.17) 65.65(11.8 50.45(2.14)
45.76(0.65) 50.70(0.11)
Scale-free exponent
79.70(2.71) 24.94(0.68) 17.26(0.63) 12.03(1 (11) (4.77().31) ( 51.37(2.70) 45. 18.18())52) 50.84(0.26
Our combination
78.75(1.63) 24.62(0.90) 17.83(1.35) 12.26(0.78) 12.2666.
67.04(1.50)
52.94(1.95) (0.46)0.46) (12.04411...55994111.95555
(1.25)
Table 11: The effect of different graph properties on downstream performance (micro F1 is reported) under APT-L2 (fine-tune) in the graph classification task.
Dataset
Method
imdb-binary
msrc-21
Entropy
76.78(0.88) 75.56(0.84) (1.50)
Density
77.20(0.66) 75.29(0.54) 21.31)
Average degree
76.87(0.933 75.46(0.53) (5.14((.55)
Degree variance
76.39( 1.4) 75.47(0..7) 25.22(1.51)
Scale-free exponent
75.52(1.24) 23.19(1.3)) 75.24(0.62)
Our combination
75.93( 75.58(1.06) 25.58(1.57)
Table 12: The effect of input graphs' learning order on downstream performance (micro F1 is re- ported) under freezing mode in the node classification task. The first is 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
cornell
cora
pubmed
Our order
69.82(2.32) (6.79(0.88) 12.68(0.81) 10.34(1.12) (1.74) 48. 76(2.20) 34.27(0.43) (0.11(
Reverse order
69.60(2.71) 16.00K0.47) 11.4 (0.91) 10.65(0.65) 51.46(1 .64) 44.36(1 (1,3)))))))))) 35.66(0.62) 45.92(0.14)
Random order
67.25(2.40)1..11 (0.11) 12.57(1.77) 11.06(0.75) 53.06(2.41) 46.76(1.95 (1,95) 35..0)) 46.36(0.20)
Table 13: The comparison of learning from easy samples and learning from difficult sample in our pipeline (APT-L22 (freeze)) on node classification. Micro F1 reported in the table. (Under the setting of learning from easy samples, replace @uncertain with Quncertain in (4), and only sample instances with predictive uncertainty lower than T..)
Dataset
Method
brazil
dd242
dd68
dd687
wisconsin
coreell
cora
pubmed
Learning from samples
56.34(3.45) (4.38(0.53) 1. 9,90(0.64) 50.65(1 48 090 72) 35.74 46.0330 17)
Learning from difficult samples (ours)
(ours) 69.8212.332 12.68(0.81) 10.34().12) 51.1 24.2766..2203442.72.. (6.21
Training time (sec) comparison between our model and GCC. All the models are trained under the same number epochs, which set as 100 practice. (The difference time cost of inference on all graphs is due to different runs.)
Table 14:
GCC
APT-L2
APT
Time of the inference on all graphs
723.92
719.64
Time of the regularization term
15.98
83.58
Total time
40161.68
18321.39
18592.01
27

---

Under review as a conference paper at ICLR 2023
H DISCUSSION: THE DESIGN OF PREDICTIVE UNCERTAINTY.
We here discuss two advantages of using the model loss (i.e., InfoNCE loss) as predictive uncertainty select samples. First, InfoNCE loss is exactly the objective function of our model, so what we do is actually to select the samples with the greatest contributions to the objective function (i.e., select the samples with the greatest InfoNCE loss), Such strategy has been justified to accelerate convergence and enhance the discriminative power of the learned representations [1-4]. Second, as the loss function our model, InfoNCE is already computed during the training, and thus no additional computation expense is needed in the data selection phase.
REFERENCES
Samira Abnar, Mostafa Dehghani, Behnam Neyshabur, and Hanie Sedghi. Exploring the limits of large scale pre-training. In ICLR, 2022.
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 Math- ematics, 8(1-2):73-B 112, 2012.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embed- ding. arXiv preprint arXiv: 700.005055 2017.
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM review, 5144):661-733 2009.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. Link prediction in cial networks using computationally efficient topological features. In IEEE third international conference on social computing, pp. 73-80, 2011.
Jesús GódezeGa and Vito Latora. Entropy rate of diffusion processes on complex networks. Physical Review E, 78(6):065 102, 2008.
Hakim Hafidi, Mounir Ghogho, Philippe Ciblat, and Ananthram Swami, Graphcl: Contrastive self- supervised learning of graph representations, arXiv preprint arXiv:2007.08025, 2020.
Bronwyn H Hall, Adam B Jaffe, and Manuel Trajtenberg. The nber patent citations data file: lessons, insights and methodological tools. 2001.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint 1rXii:2005.0068/ 2020a.
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. NeurIPS, 33:221 18-18-111 22133, 2020b.
Chen Huang, Chen Change Loy, and Xiaoou Tang. Local similarity-aware deep feature embedding. In NeurlPS, pp. 1262-1270, 2016.
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- 120991113000011 2009.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In wwW, pp. 641-650, 2010.
Sihang Li. Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In ICMI., pp. 13052-13063 2022.
28

---

Under review as a conference paper at ICLR 2023
Christopher W Lynn. Lia Papadopoulos, Ari E Kahn, and Danielle S Bassett. Human information processing in complex networks. Nature Physics, 16(9):965 -933, 2020.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2(3):127-163,
2000.
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification, In MLG. pp. 2012.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation ker- nels: efficient graph kernels from propagated information. Machine Learning, 102(2):209-245 2016.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gce: Graph contrastive coding for graph neural network pre-training. In SIGKDD, pp. 1150-1160, 2020.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. strue2vec: Learning node representations from structural identity. In SIGKDD, pp. 585-394, 2017.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, pp. 4292-4293, 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. CVPR, pp. 815-823, 2015.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In NeurIPS, pp- 1849-1857, 2016.
Yumin Suh, Bohyung Han, Wonsik Kim, and Kyoung Mu Lee. Stochastic class-based hard example mining for deep metric learning. In CVPR, pp. 7244-7252, 2019.
Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications, 391(16):415--118) 2012.
Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random walks: A review of algorithms and applications. IEEE Transactions on Emerging Topics in Com- putational Intelligence, 4(2):95-107, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In SIGKDD, pp. 1365-1374, 2015.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground- truth. In SIGKDD, pp. 1-8, 2012.
29


Reviews:
[{"review_id": "wgy2durrQn", "reviewer": "Reviewer_z7Ev", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on pre-training graph neural networks (GNNs), aiming to identify a few most important examples for pre-training. For this purpose, a graph selector is designed, which uses the predictive uncertainty from a pre-trained GNN model as features for data selection. Extensive experiments on a few datasets prove the effectiveness of the proposed framework.", "summary_of_the_review": "See above comments.", "strength_and_weaknesses": "Strengths:\n1. The problem of GNN pre-training is drawing growing attention in the graph machine learning field. Most works for GNN pre-training aim to collect more data or design better pre-training objectives to boost the performance. By contrast, this paper proposes a new idea, i.e., using data in a more efficient way by picking up those informative examples for training. Overall, I think the idea is interesting and novel.\n2. The proposed approach is quite intuitive.\n3. The experiment is extensive, where 13 graphs are used for pre-training. The results show that the proposed approach APT outperforms many existing methods.\n\nWeaknesses:\n1. In Sec. 3.1, this paper defines the predictive uncertainty by using the InfoNCE loss. Although this definition is intuitive, I feel like the design is heuristic and is lack of theoretical guarantee. It would be helpful to further discuss the advantage of the InfoNCE loss for measuring the sample importance.\n2. In terms of graph properties, this paper considers a few features of graphs, including network entropy, density, average degree, and, degree variance. Although they are very important to describe a graph, I feel like these properties are insufficient to yield a comprehensive characterization of the graph. I wonder whether it is possible to automatically learn some features as the structural properties of graphs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uRyqp6ZoTI", "reviewer": "Reviewer_ajow", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies an interesting question in terms of which graph datasets should be selected for GNN pre-training tasks. The authors propose a novel graph selector that is able to provide the most instructive data for the model. The criteria in the graph selector include predictive uncertainty and graph properties (graph entropy, density, degree, etc). Besides, they propose a data-active graph pre-training (APT) framework, which integrates the graph selector and the pre-training model into a unified framework.\n", "summary_of_the_review": "Please refer to Strength And Weaknesses.", "strength_and_weaknesses": "**Strength**\n\n- Overall, the problem studied seems to be a novel angle in the context of GNN pre-training. Efficient pre-training is currently a new trend in other domains such as NLP and CVs with a focus on how to select informative training instances. It is important to shed some light in the context of how to better use the pre-training graphs data. \n\n- The core idea the author proposed intuitively makes sense. Indeed, graphs with certain characteristics such as higher network entropy, larger density, higher average degree, higher degree variance, or a smaller scale-free exponent will contain a larger amount of information. Even though the authors do not provide theoretical justification, empirically, this work does provide good insight into GNN pre-training. \n\n**Weaknesses**\n\n- The intuition figure 1 is a bit hard to fully understand. For the first row, when scaling up the sample size, does it mean we keep the same number of pre-train graphs but we vary the same portion of sample size from each pre-train graph dataset? For the bottom row, the total number of pre-train graphs in the paper is eleven and the number of graphs in the figure is only up to ten. The author should provide what is the benchmark results if we use all the possible pre-train datasets to properly compare \n\n- Directly using contrastive loss to define and measure predictive uncertainty is not questionable. \n\n- The notation of this paper is a bit messy. For example, both scaler and vector use non-bolded lowercase (degree vector and node degree) which is not conventional. \n\n- The selection mechanism is a bit complicated and heavily handcrafted. Currently, the graph selection policy uses a combination of 6 loss terms in total. Besides, loss terms work on a very different scale and are combined together with an additional time-adaptive parameter. I am not sure if this design is reasonable. Empirically, there is no proper ablation study on the choice of which graph property to be included in the pre-train graph selection criteria. \n\n- There is an additional proximal regularization term in the model design, which aims to better preserve the knowledge or information contained in previous input data when we train on new incoming data, a similar design component in the continue learning paradigm. I am not able to fully follow the rationale of this design. The pre-training problem is completely different from the catastrophic forgetting setting since we will normally shuffle the training order of the samples after each epoch. The claim of \"previous input data will be forgotten or covered by new incoming data\" is invalid if we shuffle the data training order. Besides, the $\\mathbf{\\theta}$ parameters learned from the first $j$ graphs, does it mean in terms of the memory complexity of the model will be $j$ times larger since we need to store the previous training iteration of the model?\n\n- Experimental results-wise, I have several concerns: 1) It seems the work is directly established on top of the GCC paper, but with completely different suits of pre-training datasets and downstream datasets. The choice of dataset section seems arbitrary and suspicious. Could the author directly work on the precious experiment setting in GCC? or what's the reason behind the complete switch of datasets? \n 2) The baseline uses are quite outdated, using baselines only coming before the year 2020. A lot of recent work in terms of GNN pre-training or graph data augmentation should be included [1] - [8].  3) One suggestion to the authors, since the paper uses a lot of downstream tasks and lots of numbers in the result table, a better way to present the results can be considered. For example, providing an average rank number across all the datasets for each method will be informative and helpful to deliver the message to readers.  3) I will suggest including the full pre-training dataset results in the experiment table to see the effectiveness of the pre-train graph selection scheme. Or should I interpret the GCC results as the full pre-training dataset results?  4) Can the author provide the training time comparison? It seems that to fully  \n\n- Can the author comment on the relationship of this work to some recent adaptive graph positive sample generation work? It seems they all achieve a similar end goal by finding the proper training samples [3] [5] [6] [7].\n\n\n[1] Hu, Ziniu, et al. \"GPT-GNN: Generative pre-training of graph neural networks.\" KDD 2020.\n\n[2] Xu, Dongkuan, et al. \"Infogcl: Information-aware graph contrastive learning.\" NeurIPS 2021.\n\n[3] Zhu, Yanqiao, et al. \"Graph contrastive learning with adaptive augmentation.\" Proceedings of the Web Conference 2021. 2021.\n\n[4] Zhu, Yanqiao, et al. \"An Empirical Study of Graph Contrastive Learning.\" NeurIPS 2021.\n\n[5] You, Yuning, et al. \"Graph contrastive learning automated.\" ICML 2021.\n\n[6] Lee N, Lee J, Park C. Augmentation-free self-supervised learning on graphs. In Proc. of the AAAI Conference on Artificial Intelligence 2022.\n\n[7] Han et al. \"G-Mixup: Graph Data Augmentation for Graph Classification.\" ICML 2022.\n\n[8] Hou, Zhenyu, et al. \"GraphMAE: Self-Supervised Masked Graph Autoencoders.\" KDD 2022.\n\n\n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PBJo84oCbfk", "reviewer": "Reviewer_xmXz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a novel framework for cross-domain graph pre-training using fewer training samples. The paper first demonstrates the phenomenon of the “curse of big data” - more training and graph datasets do not always lead to better performance in downstream node and graph classification tasks. Next, it presents a data-active graph pre-training (APT) framework that consists of two parts.  (1) The graph selector uses a loss that combines the predictive uncertainty of a data sample and its graph properties (entropy, density, etc.) to make an informed decision on the most instructive data samples for the model. (2) The pre-training model that learns from the graph selector and provides it guidance for better selection.  The paper implements the framework for different datasets and tasks to show that the proposed method improves performance for downstream tasks in different domains. The proposed method is compared with existing graph-based pre-trained models. The paper also includes results on the ablation of the different components of the graph selector, which is an important analysis for such a framework. ", "summary_of_the_review": "The studied problem in this paper is important, the idea is new, and the experimental results are comprehensive. Specifically, it is demonstrated that the APT framework can achieve SOTA performance on downstream tasks by using less pre-training cross-domain data. The paper also shows this framework reduces the time complexity for pre-training. It would be great if some of the experimental choices and results could be described more clearly. \n\n", "strength_and_weaknesses": "Strengths:\n\n- The paper is overall well presented, and the methods are well described\n- It aims to tackle an important problem in the field and proposes an interesting strategy to do so\n- The experiments and results are thorough and demonstrate better downstream performance on a variety of tasks with fewer training samples\n- The presentation of the phenomenon of large training samples not adding to the performance is useful \n\nWeakness:\n\nIt would  be helpful if the following points regarding experimental settings, results, and implementation could be clarified:\n\n- Why were different models used for node (logistic regression) versus graph classification (SVMs)?\n- The ProNE model seems to outperform the APT model significantly for certain datasets. It would be helpful to discuss this result.\n- How is F (the maximal period of training one graph) different from the training epochs, or is F measured in seconds? \n- How sensitive is the model to the predictive uncertainty thresholds Tg and Ts (set to 3 and 2, respectively)? The decision choices for F, Tg, and Ts could be better described. \n- Are the baseline methods being re-trained on new datasets? If so, does it make sense to use the default hyperparameters for the same? \n\nMinor Comments:\n- I may have missed this, but what was the selection strategy for pre-training versus test data? \n- In appendix C, Table 3, the description of the ‘msu’ datasets implies it belongs to the protein category instead of the social category. The authors should make corrections where necessary.\n- In appendix C, specifically in Tables 3,4, and 5, it would be helpful to define the abbreviations |V| , |E|, and |G| in the captions. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FOn0m3Tcld", "reviewer": "Reviewer_pEvr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to select some graph data to improve the pre-training of GNNs. Existing works use all data to conduct pre-training, and it is observed that more data does not necessarily leads to better accuracy. The authors propose to use prediction uncertainty and graph properties to select data for training. Empirical results show that the proposed methods improve the accuracy of downstream tasks.", "summary_of_the_review": "This paper proposes to select data to pre-train GNNs. The idea makes sense but there are significant problems in method design and experiment analysis. Novelty is also unclear from the presentation.", "strength_and_weaknesses": "Strength\n1. The observation that more data does not necessarily leads to better accuracy is neat.\n2. Using uncertainty and graph properties to select data makes sense.\n3. The empirical results are strong.\n\n\nWeakness\n1. Discussions of related works are shallow, which make the contributions unclear. For instance, in Section 5, the Pre-training in CV and NLP part is nothing more than saying that CV and NLP have used pre-training. However, the readers are interested in what methods they use for pre-training, especially for selecting data, and what are the differences from this work. The same applies to the Graph pre-training part. My suggestion is that when you discuss some closely related works, you should make the readers understand how these works on the methodology level, instead of only describing their targets. To my knowledge, uncertainty is widely used for sample selection is many areas. What are the differences from this work?\n\n2. Method design lacks explanation and does not make sense in some places. Eq. (4) calculates the mean of several graph property metrics (i.e., network entropy, density, degree). However, the appendix shows that these metrics differ in scale, which means that a metric may dominate the others when computing the mean. It also needs to be explained why we prefer larger values of these metrics (the network entropy part is clear). My guess that the intuition is that we prefer complex graphs that are likely to contain a diverse set of graph structures, and the proposed method tends to select graph with larger average degrees.\n\n3. Experiment and analysis need to be significantly improved. (1) What is the time used for data selection? Will it be a concern? (2) In Tables 1-2, different variants of APR perform the best on different datasets, what are the reasons? Is it related to the properties of the test graph? (3) Why not compare with some well-known GNN baselines, such as GraphSAGE, which can be trained in an unsupervised manner? (4) How does different graph properties affect accuracy? How does the weight of uncertainty and graph properties affect performance? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject