When to Pre-Train Graph Neural Networks? From Data Generation
  Perspective!
In recent years, graph pre-training has gained significant attention,
focusing on acquiring transferable knowledge from unlabeled graph data to
improve downstream performance. Despite these recent endeavors, the problem of
negative transfer remains a major concern when utilizing graph pre-trained
models to downstream tasks. Previous studies made great efforts on the issue of
what to pre-train and how to pre-train by designing a variety of graph
pre-training and fine-tuning strategies. However, there are cases where even
the most advanced "pre-train and fine-tune" paradigms fail to yield distinct
benefits. This paper introduces a generic framework W2PGNN to answer the
crucial question of when to pre-train (i.e., in what situations could we take
advantage of graph pre-training) before performing effortful pre-training or
fine-tuning. We start from a new perspective to explore the complex generative
mechanisms from the pre-training data to downstream data. In particular, W2PGNN
first fits the pre-training data into graphon bases, each element of graphon
basis (i.e., a graphon) identifies a fundamental transferable pattern shared by
a collection of pre-training graphs. All convex combinations of graphon bases
give rise to a generator space, from which graphs generated form the solution
space for those downstream data that can benefit from pre-training. In this
manner, the feasibility of pre-training can be quantified as the generation
probability of the downstream data from any generator in the generator space.
W2PGNN offers three broad applications: providing the application scope of
graph pre-trained models, quantifying the feasibility of pre-training, and
assistance in selecting pre-training data to enhance downstream performance. We
provide a theoretically sound solution for the first application and extensive
empirical justifications for the latter two applications.
Yuxuan Cao, Jiarong Xu, Carl Yang, Jiaan Wang, Yunchao Zhang, Chunping Wang, Lei Chen, Yang Yang
# When to Pre-Train Graph Neural Networks?

###### Abstract.

In recent years, graph pre-training has gained significant attention, focusing on acquiring transferable knowledge from unlabeled graph data to improve downstream performance. Despite these recent endeavors, the problem of negative transfer remains a major concern when utilizing graph pre-trained models to downstream tasks. Previous studies made great efforts on the issue of _what to pre-train_ and _how to pre-train_ by designing a variety of graph pre-training and fine-tuning strategies. However, there are cases where even the most advanced "pre-train and fine-tune" paradigms fail to yield distinct benefits. This paper introduces a generic framework W2PGNN to answer the crucial question of _when to pre-train_ (_i.e._, in what situations could we take advantage of graph pre-training) before performing effortful pre-training or fine-tuning. We start from a new perspective to explore the complex generative mechanisms from the pre-training data to downstream data. In particular, W2PGNN first fits the pre-training data into graphon bases, each element of graphon basis (_i.e._, a graphon) identifies a fundamental transferable pattern shared by a collection of pre-training graphs. All convex combinations of graphon bases give rise to a generator space, from which graphs generated form the solution space for those downstream data that can benefit from pre-training. In this manner, the feasibility of pre-training can be quantified as the generation probability of the downstream data from any generator in the generator space. W2PGNN offers three broad applications: providing the application scope of graph pre-trained models, quantifying the feasibility of pre-training, and assistance in selecting pre-training data to enhance downstream performance. We provide a theoretically sound solution for the first application and extensive empirical justifications for the latter two applications.

graph neural networks, graph pre-training +
Footnote †: dagger}\)This work was done when the first author was a visiting student at Fudan University.Zhejiang, August 6-10, 2023, _Jong Beach, CA_

+
Footnote †: dagger}\)This work was done when the first author was a visiting student at Fudan University.
molecular networks (unstable vs. stable in terms of chemical property) from those in social networks (stable vs. unstable in terms of social relationship); such distinct or reversed semantics does not contribute to transferability, and even exacerbates the problem of negative transfer.

To avoid the negative transfer, recent efforts focus on _what to pre-train_ and _how to pre-train_, _i.e._, design/adopt graph pre-training models with a variety of self-supervised tasks to capture different patterns (Zhu et al., 2019; Zhang et al., 2020; Zhang et al., 2021) and fine-tuning strategies to enhance downstream performance (Zhu et al., 2019; Li et al., 2020; Zhang et al., 2021; Zhang et al., 2021). However, there do exist some cases that no matter how advanced the pre-training/fine-tuning method is, the transferability from pre-training data to downstream data still cannot be guaranteed. This is because the underlying assumption of deep learning models is that the test data should share a similar distribution as the training data. Therefore, it is a necessity to understand _when to pre-train_, _i.e._, under what situations the "graph pre-train and fine-tune" paradigm should be adopted.

Towards the answer of when to pre-train GNNs, one straightforward way illustrated in Figure 1(a) is to train and evaluate on all candidates of pre-training models and fine-tuning strategies, and then the resulting best downstream performance would tell us whether pre-training is a sensible choice. If there exist \(l_{1}\) pre-training models and \(l_{2}\) fine-tuning strategies, such a process would be very costly as you should make \(l_{1}\times l_{2}\) "pre-train and fine-tune" attempts. Another approach is to utilize graph metrics to measure the similarity between pre-training and downstream data, _e.g._, density, clustering coefficient and etc. However, it is a daunting task to enumerate all hand-engineered graph features or find the dominant features that influenced similarity. Moreover, the graph metrics only measure the pair-wise similarity between two graphs, which cannot be directly and accurately applied to the practical scenario where pre-training data contains multiple graphs.

In this paper, we propose a W2PGNN framework to answer _when to pre-train GNNs from a graph data generation perspective_. The high-level idea is that instead of performing effortful graph pre-training/fine-tuning or making comparisons between the pre-training and downstream data, we study the complex generative mechanism from the pre-training data to the downstream data (Figure 1(b)). We say that downstream data can benefit from pre-training data (_i.e._, has high feasibility of performing pre-training), if it can be generated with high probability by a graph generator that summarizes the topological characteristic of pre-training data.

The major challenge is how to obtain an appropriate graph generator, hoping that it not only inherits the transferable topological patterns of the pre-training data, but also is endowed with the ability to generate feasible downstream graphs. To tackle the challenge, we propose to design a graph generator based on graphons. We first fit the pre-training graphs into different graphons to construct a _graphon basis_, where each graphon (_i.e._, element of the graphon basis) identifies a collection of graphs that share common transferable patterns. We then define a _graph generator_ as a convex combination of elements in a graphon basis, which serves as a comprehensive and representative summary of pre-training data. All of these possible generators constitute the _generator space_, from which graphs generated form the solution space for the downstream data that can benefit from pre-training.

Accordingly, the feasibility of performing pre-training can be measured as the highest probability of downstream data being generated from any graph generator in the generator space, which can be formulated as an optimization problem. However, this problem is still difficult to solve due to the large search space of graphon basis. We propose to reduce the search space to three candidates of graphon basis, _i.e._, topological graphon basis, domain graphon basis, and integrated graphon basis, to mimic different generation mechanisms from pre-training to downstream data. Built upon the reduced search space, the feasibility can be approximated efficiently.

Our major contributions are concluded as follows:

* **Problem and method.** To the best of our knowledge, we are the first work to study the problem of when to pre-train GNNs. We propose a W2PGNN framework to answer the question from a data generation perspective, which tells us the feasibility of performing graph pre-training before conducting effortful pre-training and fine-tuning.
* **Broad applications.** W2PGNN provides several practical applications: (1) provide the application scope of a graph pre-trained model, (2) measure the feasibility of performing pre-training for a downstream data and (3) choose the pre-training data so as to maximize downstream performance with limited resources.
* **Theory and Experiment.** We theoretically and empirically justify the effectiveness of W2PGNN. Extensive experiments on real-world graph datasets from multiple domains show that the proposed method can provide an accurate estimation of pre-training feasibility and the selected pre-training data can benefit the downstream performance.

## 2. Problem Formulation

In this section, we first formally define the problem of when to pre-train GNNs. Then, we provide a brief theoretical analysis of the transferable patterns in the problem we study, and finally discuss some non-transferable patterns.

Definition 1 (When to pre-train GNNs).: _Given the pretraining graph data \(\mathcal{G}_{train}\) and the downstream graph data \(\mathcal{G}_{down}\), our main goal is to answer to what extent the "pre-train and fine-tune" paradigm can benefit the downstream data._

Figure 1. Comparison of existing methods and proposed W2PGNN to answer _when to pre-train_ GNNs.
Note that in addition to this main problem, our proposed framework can also serve other scenarios, such as providing the application scope of graph pre-trained models, and helping select pre-training data to benefit the downstream (please refer to the _application cases_ in Section 4.1 for details).

Transferable graph patterns.The success of "pre-train and fine-tune" paradigm is typically attributed to the commonplace between pre-training and downstream data. However, in real-world scenarios, there possibly exists a significant divergence between the pre-training data and the downstream data. To answer the problem of when to pre-train GNNs, the primary task is to define the transferable patterns across graphs.

We here theoretically explore which patterns are transferable between pre-training and downstream data under the performance guarantee of graph pre-training model (with GNN as the backbone).

Theorem 2.1 (Transferability of graph pre-training model).: _Let \(G_{\text{train}}\) and \(G_{\text{down}}\) be two (sub)graphs sampled from \(\mathcal{G}_{\text{train}}\) and \(\mathcal{G}_{\text{down}}\), and assume the attribute of each node as a scalar \(1\) without loss of generality. Given a graph pre-training model \(e\) (instantiated as a GNN) with \(K\) layers and \(1-\)hop graph filter \(\Phi(L)\) (which is a function of the normalized graph Laplacian matrix \(L\)), we have_

\[\left\|e(G_{\text{train}})-e(G_{\text{down}})\right\|_{2}\leq\kappa\Lambda_{ \text{loop}}\left(G_{\text{train}},G_{\text{down}}\right) \tag{1}\]

_where \(\Lambda_{\text{loop}}\left(G_{\text{train}},G_{\text{down}}\right)=\frac{1} {mn}\sum_{l=1}^{m}\sum_{f^{\prime}=1}^{n}\left\|L_{g_{l}}-L_{g_{j}}\right\|_{2}\) measures the topological divergence between \(G_{\text{train}}\) and \(G_{\text{down}}\), where \(g_{i}\) is the \(K\)-hop ego-network of node \(i\) from \(G_{\text{train}}\) and \(L_{g_{i}}\) is its corresponding normalized graph Laplacian matrix, \(m\) and \(n\) are the number of nodes of \(G_{\text{train}}\) and \(G_{\text{down}}\). \(e(G_{\text{train}})\) and \(e(G_{\text{down}})\) are the output representations of \(G_{\text{train}}\) and \(G_{\text{down}}\) from graph pre-training model, \(\kappa\) is a constant relevant to \(K\), graph filter \(\Phi\), learnable parameters of GNN and the activation function used in GNN._

Detailed proofs and descriptions can be found in Appendix A.1. Theorem 2.1 suggests that two (sub)graphs sampled from pre-training and downstream data with similar topology are transferable via graph pre-training model (_i.e._, sharing similar representations produced by the model).

Hence we consider the transferable graph pattern as the topology of a (sub)graph, either node-level or graph-level. Specifically, the node-level transferable pattern could be the topology of the ego-network of a node (or the structural role of a node), irrespective of the node's exact location in the graph. The graph-level transferable pattern is the topology of the entire graph itself (_e.g._, molecular network). Such transferable patterns constitute the input space introduced in Section 4.1.

Discussion of non-transferable graph patterns.As a remark, we show that two important pieces of information (_i.e._, attributes and proximity) commonly used in graph learning are not necessarily transferable across pre-training and downstream data in most real-world scenarios, thus we do not discuss them in this paper.

First, although the attributes carry important semantic meaning in one graph, it can be shown that the attribute space of different graphs typically has little or no overlap at all. For example, if the pre-training and downstream data come from different domains, their nodes would indicate different types of entities and the corresponding attributes may be completely irrelevant. Even for graphs from the similar/same domain, the dimensions/meaning of their node attributes can also be totally different and result in misalignment.

The proximity, on the other hand, assumes that closely connected nodes are similar, which also cannot be transferred across graphs. Obviously, this proximity assumption depends on the overlaps in neighborhoods and thus only works on graphs with the same or overlapped node set.

## 3. Preliminary and related works

Graphons.A Graphon (short for graph function) (Belleelle and G
fine-tuning strategies, and then the resulting best downstream performance as the transferability measure. However, as depicted in Figure 1(a), such approach would be very costly to perform effortful pre-training and fine-tuning. Another way is based on graph properties, which leverage the graph properties (_e.g.,_ degree (Bordes and Zisserman, 2017), density (Zisserman and Zisserman, 2017), assortativity (Kang et al., 2018) and etc.) to measure the similarities between pre-training and downstream graphs, potentially can be utilized to approximate the transferability. Some other works also focus on analyzing the transferability of GNNs theoritically (Kang et al., 2018; Li et al., 2019). Nevertheless, they are limited to measure the transferability of GNNs on a single graph or when training and testing data are from the same dataset (Kang et al., 2018; Li et al., 2019), which are inapplicable to our setting. A recent work, EGI (Kang et al., 2019) addresses the transferability measure problem of GNNs across graphs. However, EGI is a model-specific measure and depend on its own framework. For the first time, we study the transferability of graph pre-training from the data perspective, without performing any pre-training and fine-tuning.

## 4. Methodology

In this section, we first present our proposed framework W2PGNN to answer when to pre-train GNNs in Section 4.1. Based on the framework, we further introduce the measure of the feasibility of performing pre-training in Section 4.2. Then in Section 4.3, we discuss our approximation to the feasibility of pre-training. Finally, the complexity analysis of W2PGNN is provided in Section 4.4.

### Framework Overview

W2PGNN framework provides a guide for answering _when to pre-train GNNs from a graph data generation perspective_. The key insight is that if downstream data can be generated with high probability by a graph generator that summarizes the pre-training data, the downstream data would present high feasibility of performing pre-training.

The overall framework of W2PGNN can be found in Figure 2. Given the _input space_ consisting of pre-training graphs, we fit them into a graph generator in the _generator space_, from which the graphs generated constitute the _possible downstream space_. More specifically, an ideal graph generator should inherit different kinds of topological patterns, based on which new graphs can be induced. Therefore, we first construct a graphon basis \(\mathcal{B}=\{B_{1},B_{2},\cdots,B_{k}\}\), where each element \(B_{i}\) represents a graphon fitted from a set of (sub)graphs with similar patterns (_i.e.,_ the blue dots ). To access different combinations of generator basis, each \(B_{i}\) is assigned with a corresponding weight \(\alpha_{i}\) (_i.e.,_ the width of blue arrow ) and their combination gives rise to a graph generator (_i.e.,_ the blue star ). All weighted combinations compose the generator space \(\Omega\) (_i.e.,_ the gray surface ), from which graphs generated form the possible solution space of downstream data (shorted as possible downstream space). The generated graphs are those that could benefit from the pre-training data, we say that they exhibit _high feasibility_ of performing pre-training.

In the following, we introduce the workflow of W2PGNN in the input space, the generator space and the possible downstream space in detail. Then, the application cases of W2PGNN are given for different practical use.

**Input space.** The input space of W2PGNN is composed of nodes' ego-networks or graphs. For node-level pre-training, we take the nodes' ego-networks to constitute the input space; For graph-level pre-training, we take the graphs (_e.g.,_ small molecular graphs) as input space.

**Generator space.** As illustrated in Figure 2, each point (_i.e.,_ graph generator) in the generator space \(\Omega\) is a convex combination of generator basis \(\mathcal{B}=\{B_{1},B_{2},\cdots,B_{k}\}\). Formally, we define the graph generator as

\[f(\{\alpha_{i}\},\{B_{i}\})=\sum_{i=1}^{k}\alpha_{i}B_{i},\ \ \text{where}\ \sum_{i=1}^{k}\alpha_{i}=1,\alpha_{i}\geq 0. \tag{2}\]

Different choices of \(\{\alpha_{i}\},\{B_{i}\}\) comprise different graph generators. All possible generators constitute the _generator space_\(\Omega=\{f(\{\alpha_{i}\},\{B_{i}\})\mid\forall\ \{\alpha_{i}\},\{B_{i}\}\}\).

We shall also note that, the graph generator \(f(\{\alpha_{i}\},\{B_{i}\})\) is indeed a mixed graphon, (_i.e.,_ mixture of \(k\) graphons \(\{B_{1},B_{2},\cdots,B_{k}\}\)), where each element \(B_{i}\) represents a graphon estimated from a set of similar pre-training (sub)graphs. Furthermore, it can be theoretically justified that the mixed version still preserve the properties of graphons (c.f. Theorem 5.1) and the key transferable patterns inherited in \(B_{i}\) (c.f. Theorem 5.2). Thus the graph generator \(f(\{\alpha_{i}\},\{B_{i}\})\), _i.e.,_ mixed graphon, can be considered as a representative and comprehensive summary of pre-training data, from which unseen graphs with different combinations of transferable patterns can be induced.

**Possible downstream space.** All the graphs produced by the generators in the generator space \(\Omega\) could benefit from the pre-training, and finally form the possible downstream space.

Formally, for each generator in the generator space \(\Omega\) (we denote it as \(f\) for simplicity), we can generate a \(n\)-node graph as follows. First, we independently sample a random latent variable for each node. Then for each pair of nodes, we assign an edge between them with the probability equal to the value of the graphon at their randomly sampled points. The graph generation process can be formulated as

\[\begin{split}&\vspace{0.1cm}\cdots,\vspace{0.1cm}\text{Uniform}(\{0,1\}),\\ &\vspace{0.1cm}A_{ij}\sim\text{Bernoulli}(f(\vspace{0.1cm}v_{j}) ),\quad\forall i,j\in\{1,2,\ldots,n\},\end{split} \tag{3}\]

Figure 2. Illustration of our proposed framework W2PGNN to answer when to pre-train GNNs.
where \(f(\{a_{i},v_{j}\})\in[0,1]\) indicates the corresponding value of the graphon at point \((v_{i},v_{j})\)1, and \(A_{ij}\in\{0,1\}\) indicates the existence of edge between \(i\)-th node and \(j\)-th node. The adjacency matrix of the sampled graph \(G\) is denoted as \(A=[A_{ij}]\in\{0,1\}^{n\times n},\forall i,j\in[n]\). We summarize this generation process as \(G\gets f\).

Footnote 1: For simplicity, we slightly abuse the notations \(f(\cdot,\cdot)\). Note that \(f(\{a_{i}\},\{B_{i}\})\) is a function of \(\{a_{i}\}\) and \(\{B_{i}\}\), representing that the generator depends on \(\{a_{i}\}\), \(\{B_{i}\}\); while for each generator \(\{a_{i},\,\text{mixed graphon}\}\) given \(\{a_{i}\}\), \(\{B_{i}\}\), it can be represented as a continuous, bounded and symmetric function \(f:[0,1]^{2}\rightarrow[0,1]\).

Therefore, with all generators from the generator space \(\Omega\), the possible downstream space is defined as \(\mathcal{D}=\{G\gets f|f\in\Omega\}\). Note that for each \(\{a_{i}\},\{B_{i}\}\), we have a generator \(f\); and for each generator, we also have different generated graphs. Besides, we theoretically justify that the generated graphs in the possible downstream space can inherit key transferable graph patterns in our generator (c.f. Theorem 5.3).

**Application cases.** The proposed framework is flexible to be adopted in different application scenarios when discussing the problem of when to pre-train GNNs.

* _Use case 1: provide a user guide of a graph pre-trained model._ The possible downstream space \(\mathcal{D}\) serves as a user guide of a graph pre-trained model, telling the application scope of graph pre-trained models (_i.e._, the possible downstream graphs that can benefit from the pre-training data).
* _Use case 2: estimate the feasibility of performing pre-training from pre-training data to downstream data._ Given a collection of pre-training graphs and a downstream graph, one can directly measure the feasibility of performing pre-training on pre-training data, before conducting costly pre-training and fine-tuning attempts. By making such pre-judgement of a kind of transferability, some unnecessary and expensive parameter optimization steps during model training and evaluation can be avoided.
* _Use case 3: select pre-training data to benefit the downstream_. In some practical scenarios where the downstream data is provided (_e.g._, a company's need is to boost downstream performance of its business data), the feasibility of pre-training inferred by W2PGNN can be utilized to select data for pre-training, such that the downstream performance can be maximized with limited resources.

Use case 1 can be directly given by our produced possible downstream space \(\mathcal{D}\). However, how to measure the feasibility of pre-training in use case 2 and 3 still remains a key challenge. In the following sections, we introduce the formal definition of the feasibility of pre-training and its approximate solution.

### Feasibility of Pre-training

If a downstream graph can be generated with a higher probability from any generator in the generator space \(\Omega\), then the graph could benefit more from the pre-training data. We therefore define the feasibility of performing pre-training as the highest probability of the downstream data generated from a generator in \(\Omega\), which can be formulated as an optimization problem as follows.

Definition 2 (Feasibility of graph pre-training).: _Given the pre-training data \(\mathcal{G}_{train}\) and downstream data \(\mathcal{G}_{down}\), we have the feasibility of performing pre-training on \(\mathcal{G}_{train}\) to benefit \(\mathcal{G}_{down}\) as_

\[\zeta(\mathcal{G}_{train}\rightarrow\mathcal{G}_{down})=\sup_{\{a_{i}\},\{B_{i }\}}\Pr\left(\mathcal{G}_{down}\mid f(\{a_{i}\},\{B_{i}\})\right), \tag{4}\]

_where \(\Pr\left(\mathcal{G}_{down}\mid f(\{a_{i}\},\{B_{i}\})\right)\) denotes the probability of the graph sequence sampled from \(\mathcal{G}_{down}\) being generated by graph generator \(f(\{a_{i}\},\{B_{i}\})\); each (sub)graph represents an ego-network (for node-level task) or a graph (for graph-level task) sampled from the downstream data \(\mathcal{G}_{down}\)._

However, the probability \(\Pr\left(\mathcal{G}_{down}\mid f(\{a_{i}\},\{B_{i}\})\right)\) of generating the downstream graph from a generator is extremely hard to compute, we therefore turn to converting the optimization problem (4) to a tractable problem. Intuitively, if generator \(f(\{a_{i}\},\{B_{i}\})\) can generate the downstream data with higher probability, it potentially means that the underlying generative patterns of pre-training data (characterized by \(f(\{a_{i}\},\{B_{i}\})\)) and downstream data (characterized by the graphon \(\mathcal{B}_{down}\) fitted from \(\mathcal{G}_{down}\)) are more similar. Accordingly, we turn to figure out the infimum of the distance between \(f(\{a_{i}\},\{B_{i}\})\) and \(B_{down}\) as the feasibility, _i.e._,

\[\zeta(\mathcal{G}_{train}\rightarrow\mathcal{G}_{down})=-\inf_{\{a_{i}\},\{B_{ i}\}}\operatorname{dist}(f(\{a_{i}\},\{B_{i}\}),B_{down}). \tag{5}\]

Following (Zhou et al., 2018), we hire the 2-order Gromov-Wasserstein (GW) distance as our distance function \(\operatorname{dist}(\cdot,\cdot)\), as GW distance is commonly used to measure the difference between structured data.

Additionally, we establish a theoretical connection between the above-mentioned distance and the probability of generating the downstream data in extreme case, which further adds to the integrity and rationality of our solution.

Theorem 4.1 ().: _Given the graph sequence sampled from downstream data \(\mathcal{G}_{down}\), we estimate its corresponding graphon as \(\mathcal{B}_{down}\). If a generator \(f\) can generate the downstream graph sequence with probability 1, then \(\operatorname{dist}(f,\mathcal{B}_{down})=0\)._

### Choose Graphon Basis to Approximate Feasibility

Although the feasibility has been converted to the optimization problem (5), exhausting all possible \(\{a_{i}\},\{B_{i}\}\) to find the infimum is impractical. An intuitive idea is that we can choose some appropriate graphon basis \(\{B_{i}\}\), which can not only prune the search space but also accelerate the optimization process. Therefore, we aim to first reduce the search space of graphon basis \(\{B_{i}\}\) and then learn the optimal \(\{a_{i}\}\) in the reduced search space.

Considering that the downstream data may be formed via different generation mechanisms (implying various transferable patterns), a single graphon basis might have limited expressivity and completeness to cover all patterns. We therefore argue that a good reduced search space of graphon basis should cover a set of graphon bases. Here, we introduce three candidates of them as follows.

**Integrated graphon basis.** The first candidate of graphon basis is the integrated graphon basis \(\{B_{i}\}_{\text{integer}}\). This graphon basis is introduced based on the assumption that the pre-training and the downstream graphs share very similar patterns. For example, the pre-training and the downstream graphs might come from social networks of different time spans (Kipip et al., 2018). In the situation, almost all patterns involved in the pre-training data might be useful for the
downstream. To achieve this, we directly utilize all (sub)graphs sampled from the pre-training data to estimate one graphon as the graphon basis. This integrated graphon basis serves as a special case of the graphon basis introduced below.

**Domain graphon basis.** The second candidate of graphon basis is the domain graphon basis \(\{B_{i}\}_{\text{domain}}\). The domain information that pre-training data comes from is important prior knowledge to indicate the transferability from the pre-training to downstream data. For example, when the downstream data is molecular network, it is more likely to benefit from the pre-training data from specific domains like biochemistry. This is because the specificity of molecules makes it difficult to learn transferable patterns from other domains, _e.g._, closed triangle structure represents diametrically opposite meanings (stable vs unstable) in social network and molecular network. Therefore, we propose to split the (sub)graphs sampled from pre-training data according to their domains, and each split of (sub)graphs will be used to estimate a graphon as a basis element. In this way, each basis element reflects transferable patterns from a specific domain, and all basis elements construct the domain graphon basis \(\{B_{i}\}_{\text{domain}}\).

**Topological graphon basis.** The third candidate is the topological graphon basis \(\{B_{i}\}_{\text{topo}}\). The topological similarity between the pre-training and the downstream data serves as a crucial indicator of transferability. For example, a downstream social network might benefit from the similar topological patterns in academic or web networks (_e.g._, closed triangle structure indicates stable relationship in all these networks). Then, the problem of finding topological graphon basis can be converted to partition \(n\) (sub)graphs sampled from pre-training data into \(k\)-split according to their topology similarity, where each split contains (sub)graphs with similar topology. Each element of graphon basis (_i.e._, graphon) fitted from each split of (sub)graphs is expected to characterize a specific kind of topological transferable pattern.

However, the challenge is that for graph structured data that is irregular and complex, we cannot directly measure the topological similarity between graphs. To tackle this problem, we introduce a _graph feature extractor_ that maps arbitrary graph into a fixed-length vector representation. To approach a comprehensive and representative set of topological features, we here consider both node-level and graph-level properties.

For node-level topological features, we first apply a set of node-level property functions \([\phi_{1}(v),\cdots,\phi_{m_{1}}(v)]\) for each node \(v\) in graph \(G\) to capture the local topological features around it. Considering that the numbers of nodes of two graphs are possibly different, we introduce an aggregation function AGG to summarize the node-level property of all nodes over \(G\) to a real number AGG\((\{\phi_{i}(v),v\in G\})\). We can thus obtain the node-level topological vector representation as follows.

\[h_{\text{node}}(G)=[\text{AGG}(\{\phi_{1}(v),v\in G\}),\cdots,\text{AGG}(\{ \phi_{m_{1}}(v),v\in G\})].\]

In practice, we calculate degree (Belleelle and Solla, 2017), clustering coefficient (Kang et al., 2017) and closeness centrality (Kang et al., 2017) for each node and instantiate the aggregation function AGG as the mean aggregator.

For graph-level topological features, we also employ a set of graph-level property functions for each graph \(G\) to serve as the vector representation

\[h_{\text{graph}}(G)=[\{y_{1}(G),\cdots,y_{m_{2}}(G)\},\]

where density (Kang et al., 2017), assortativity (Kang et al., 2017), transitivity (Kang et al., 2017) are adopted as graph-level properties here 2.

Footnote 2: Other graph-level properties can also be utilized like _diameter and Wiener index_, but we do not include them due to their high computational complexity.

Finally, the final representation of \(G\) produced by the graph feature extractor is

\[h=[h_{\text{local}}(G)||h_{\text{global}}(G)]\in\mathbb{R}^{m_{1}+m_{2}},\]

where \(||\) is the concatenation function that combines both node-level and graph-level features. Given the topological vector representation, we leverage an efficient clustering algorithm K-Means (Kang et al., 2017) to obtain k-splits of (sub)graphs and finally fit each split into a graphon as one element of topological graphon basis.

**Optimization solution.** Given the above-mentioned three graphon bases, the choice of graphon basis \(\{B_{i}\}\) can be specified to one of them. In this way, the pre-training feasibility (simplified as \(\zeta\)) could be approximated in the reduced search space of graphon basis as

\[\zeta\leftarrow-\text{MIN}(\{\inf_{\{a_{i}\}}\text{dist}(f(\{a_{i}\},\{B_{i} \}),B_{\text{down}}),\forall\{B_{i}\}\in\mathcal{B}\}), \tag{6}\]

where \(\mathcal{B}\)=\(\{(B_{i}\}_{\text{topo}},\{B_{i}\}_{\text{domain}},\{B_{i}\}_{\text{interj}})\) is the reduced search space of \(\{B_{i}\}\). Thus, the problem can be naturally splitted into three sub-problems with objective of \(\text{dist}(f(\{a_{i}\},\{B_{i}\}_{\text{topo}}),B_{\text{down}})\), \(\text{dist}\) (\(f(\{a_{i}\},\{B_{i}\}_{\text{domain}}),B_{\text{down}})\)) and \(\text{dist}(f(\{a_{i}\},\{B_{i}\}_{\text{interj}}),B_{\text{down}})\)) respectively. Each sub-problem can be solved by updating the corresponding learnable parameters \(\{a_{i}\}\) with multiple gradient descent steps. Taking one step as an example, we have

\[\{a_{i}\}=\{a_{i}\}-\eta\nabla_{\{a_{i}\}}\text{dist}(f(\{a_{i}\},\{B_{i}\}),B _{\text{down}}) \tag{7}\]

where \(\eta\) is the learning rate. Finally, we achieve three infimum distances under different \(\{B_{i}\}\in\mathcal{B}\) respectively, the minimum value among them is the approximation of pre-training feasibility. In practice, we adopt an efficient and differential approximation of GW distance, _i.e._, entropic regularization GW distance (Kang et al., 2017), as the distance function. For graphon estimation, we use the "largest gap" method as to estimate graphon \(B_{i}\).

### Computation Complexity

We now show that the time complexity of W2PNN is much lower than traditional solution. Suppose that we have \(n_{1}\) and \(n_{2}\) (sub)graphs sampled from pre-training data and downstream data respectively, and denote \(|V|\) and \(|E|\) as the average number of nodes and edges per (sub)graph. The overall time complexity of W2PGNN is \(O((n_{1}+n_{2})|V|^{2})\). For comparison, traditional solution in Figure 1(a) to estimate the pre-training feasibility should make \(l_{1}\times l_{2}\) "pre-train and fine-tune" attempts, if there exist \(l_{1}\) pre-training models and \(l_{2}\) fine-tuning strategies. Suppose the batch size of pre-training as \(b\) and the representation dimension as \(d\). The overall time complexity of traditional solution is \(O\left(l_{1}b\zeta((n_{1}+n_{2})(|V|^{3}+|E|d)+n_{1}bd)\right)\). Detailed analysis can be found in Appendix D.

## 5. Theoretical Analysis

In this section, we theoretically analyze the rationality of the generator space and possible downstream space in W2PGNN. Detailed proofs of the following theorems can be found in Appendix A.
### Theoretical Justification of Generator Space

Our generator preserves the properties of graphons.We first theoretically prove that any generator in the generator space still preserve the properties of graphon (_i.e._, a bounded symmetric function \(\left[0,1\right]^{2}\rightarrow\left[0,1\right]\), summarized in the following theorem.

Theorem 5.1 ().: _For a set of graphon basis \(\{B_{i}\}\), the corresponding generator space \(\Omega=\{f(\{\alpha_{i}\},\{B_{i}\})\mid\forall\{\alpha_{i}\},\{B_{i}\}\}\) is the convex hull of \(\{B_{i}\}\)._

Our generator preserves the key transferable patterns in graphon basis.As a preliminary, we first introduce the concept of _graph motifs_ as a useful description of transferable graph patterns and leverage _homomorphism density_ as a measure to quantify the degree to which the patterns inherited in a graphon.

Definition 3 (Graph motifs(Graham, 1994)).: _Given a graph \(G=(V,E)\) (\(V\) and \(E\) are node set and edge set), graph motifs are substructure \(F=(V^{\prime},E^{\prime})\) that recur significantly in statistics, where \(V^{\prime}\subset V,E^{\prime}\subset E\) and \(|V^{\prime}|\ll|V|\)._

Graph motifs can be roughly taken as the key transferable graph patterns across graphs (Zhu et al., 2017). For example, the motif (X) has the same meaning of "feedforward loop" across networks of control system, gene systems or organisms.

Then, we introduce the measure of homomorphism density \(t(F,B)\) to quantify the relative frequency of the key transferable pattern, _i.e._, graph motifs \(F\), inherited in graphon \(B\).

Definition 4 (Homomorphism density(Graham, 1994)).: _Consider a graph motif \(F=(V^{\prime},E^{\prime})\), we define a homomorphisms of \(F\) into graph \(G=(V,E)\) as an adjacency-preserving map from \(V^{\prime}\) to \(V\), where \((i,j)\in E\) implies \((i,j)\in E\). There could be multiple maps from \(V^{\prime}\) to \(V\), but only some of them are homomorphisms. Therefore, the definition of homomorphism density \(t(F,G)\) is introduced to quantify the relative frequency with which the graph motif \(F\) appears in \(G\)._

_Analogously, the homomorphism density of graphs can be extended into the graphon \(B\). We denote \(t(F,B)\) as the homomorphism density of graph motif \(F\) into graphon \(B\), which represents the relative frequency of \(F\) occurring in a collection of graphs \(\{G_{i}\}\) that convergent to graphon \(B\), i.e., \(t(F,B)=\lim_{i\rightarrow\infty}t\) (\(F,\{G_{i}\}\))._

Now, we are ready to quantify how much the transferable patterns in graphon basis can be preserved in our generator by exploring the difference between the homomorphism density of graph motifs into the graphon basis and that into our generator.

Theorem 5.2 ().: _Assume a graphon basis \(\{B_{1},\cdots,B_{k}\}\) and their convex combination \(f(\{\alpha_{i}\},\{B_{i}\})=\sum_{i=1}^{k}a_{i}B_{i}\). The \(a\)-th element of graphon basis \(B_{a}\) corresponds to a motif set. For each motif \(F_{a}\) in the motif set, the difference between the homomorphism density of \(F_{a}\) in \(f(\{\alpha_{i}\},\{B_{i}\})\) and that in basis element \(B_{a}\) is upper bounded by_

\[|t(F_{a},f(\{\alpha_{i}\},\{B_{i}\}))-t(F_{a},B_{a})|\leq\sum_{b=1,b\neq a}^{ k}|F_{a}|\alpha_{b}||B_{b}-B_{a}||_{\Omega} \tag{8}\]

_where \(|F_{a}|\) represents the number of nodes in motif \(F_{a}\), and \(||\cdot||_{\Omega}\) denotes the cut norm._

Theorem 5.2 indicates the graph motifs (_i.e._, key transferable patterns) inherited in each basis element can be preserved in our generator, which justifies the rationality to take the generator as a representative and comprehensive summary of pre-training data.

### Theoretical Justification of Possible Downstream Space

The possible downstream space includes the graphs generated from generator \(f(\{\alpha_{i}\},\{B_{i}\})\). We here provide a theoretical justification that the generated graphs in possible downstream space can inherit key transferable graph patterns (_i.e._, graph motifs) in the generator.

Theorem 5.3 ().: _Given a graph generator \(f(\{\alpha_{i}\},\{B_{i}\})\), we can obtain sufficient number of random graphs \(\mathbb{G}=\mathbb{G}(n,f(\{\alpha_{i}\},\{B_{i}\}))\) with \(n\) nodes generated from \(f(\{\alpha_{i}\},\{B_{i}\})\). The homomorphism density of graph motif \(F\) in \(\mathbb{G}\) can be considered approximately equal to that in \(f(\{\alpha_{i}\},\{B_{i}\})\) with high probability, which can be represented as_

\[\mathrm{P}(|t(F,\mathbb{G})-t(F,f(\{\alpha_{i}\},\{B_{i}\}))|>\varepsilon) \leq 2\exp\left(-\frac{\varepsilon^{2}n}{8\nu(F)^{2}}\right), \tag{9}\]

_where \(\nu(F)\) denotes the number of nodes in \(F\), and \(0\leq\varepsilon\leq 1\)._

Theorem 5.3 indicates that the homomorphism density of graph motifs into the generated graphs in the possible downstream space can be inherited from our generator to a significant degree.

## 6. Experiments

In this section, we evaluate the effectiveness of W2PGNN with the goal of answering the following questions: (1) Given the pre-training and downstream data, is the feasibility of pre-training estimated by W2PGNN positively correlated with the downstream performance (Use case 2)? (2) When the downstream data is provided, does the pre-training data selected by W2PGNN actually help improve the downstream performance (Use case 3)?

Note that it is impractical to empirically evaluate the application scope of graph pre-trained models (Use case 1), as we cannot enumerate all graphs in the possible downstream space. Whereas, by answering question (1), it can be indirectly verified that a part of graphs in the possible downstream space, _i.e._, the downstream graphs with high feasibility, indeed benefit from the pre-training.

### Experimental Setup

We validate our proposed framework on both node classification and graph classification task.

**Datasets.** For node classification task, we directly adopt six datasets from (Zhu et al., 2017) as the candidates of pre-training data, which consists of Academia, DBLP(SNAP), DBLP(NetRep), IMDB, Facebook and LiveJournal (from academic, movie and social domains). Regarding the downstream datasets, we adopt US-Airport and H-Index from (Zhu et al., 2017) and additionally add two more datasets Chameleon and Europe-Airport for a more comprehensive results.

For graph classification task, we choose the large-scale datasets ZINC15(Zhu et al., 2017) containing \(2\) million unlabeled molecules. To enrich the follow-up experimental analysis, we use scaffold split to partition the ZINC15 into five datasets (ZINC15-0,ZINC15-1,ZINC15-2,ZINC15-3 and ZINC15-4) according to their scaffolds (Kong et al., 2017), such
that the scaffolds are different in each dataset. Regarding the downstream datasets, we use 5 classification benchmark datasets contained in MoleculeNet (Wang et al., 2017). For downstream datasets, we use BACE, BBBP, MUV, HIV and ClinTox provided in (Wang et al., 2017).

The dataset details are summarized in Appendix B.

**Baseline of graph pre-training measures.** The baselines can be divided into 3 categories: (1) EGI (Wang et al., 2017) computes the difference between the graph Laplacian of (sub)graphs from pre-training data and that from downstream data; (2) Graph Statistics,by which we merge average degree, degree variance, density, degree assortativity coefficient, transitivity and average clustering coefficient to construct a topological vector for each (sub)graph. (3) Clustering Coefficient, Spectrum of Graph Laplacian, and Betweenness Centrality, by which we adopt the distributions of graph properties as topological vectors. For the second and third category of baselines, we calculate the negative value of Maximum Mean Discrepancy (MMD) distance between the obtained topological vectors of the (sub)graph from pre-training data and that from downstream data.

Note that in all baselines, the distance/difference is computed between one ego-network (for node classification) or graph (for graph classification) from pre-training data and another one from downstream data. For efficiency, when conducting node classification, we randomly sample 10% nodes and extract their 2-hop ego-networks for each candidate pre-training dataset, and extract 2-hop ego-networks of all nodes for each downstream dataset. For graph classification, we randomly select 10% graphs for each candidate pre-training dataset and downstream dataset. Then we take the average of all distances/differences as the final measure.

**Implementation Details.** For node classification tasks, we randomly sample 1000 nodes for each pre-training dataset and extract 2-hops ego-networks of sampled nodes to compose our input space, and extract 2-hops ego-networks of all nodes in each downstream dataset to estimate the graphon. For graph classification tasks, we take all graphs in each pre-training dataset to compose our input space and we use all graphs in each downstream dataset to estimate its corresponding graphon. When constructing topological graphon basis, we set the the number of clusters \(k=5\). The maximum iterations number of K-Means is set as 300. When constructing domain graphon basis, we take each pre-training dataset as a domain. For graphon estimation, we use the largest gap (Beng et al., 2017) approach and let the block size of graphon as the average number of nodes in all graphs. When learning \(\alpha_{i}\), we adopt Adam as the optimizer and set the learning rate \(\eta\) as 0.05. When calculating the GW distance, we utilize its differential and efficient version entropic regularization GW distance with default hyperparameters (Krizhevsky et al., 2012).

### Results of Pre-training Feasibility

**Setup.** When evaluating the pre-training feasibility, since its ground truth is unavailable, we adopt the best downstream performance among a set of graph pre-training models as the ground truth.

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{\(N=2\)} & \multicolumn{6}{c}{\(N=3\)} \\ \cline{2-13}  & US-Airport & Europe-Airport & H-index & Chameleon & Rank & US-Airport & Europe-Airport & H-index & Chameleon & Rank \\ \hline Graph Statistics & -0.6068 & 0.3571 & -0.6220 & -0.2930 & 10 & -0.7096 & -0.5052 & -0.2930 & -0.8173 & 10 \\ EGI & 0.6672 & -0.6077 & -0.2152 & -0.2680 & 9 & -0.2358 & -0.5540 & -0.2822 & -0.6511 & 9 \\ Clustering Coefficient & -0.0273 & 0.1519 & 0.3622 & 0.3130 & 5 & -0.0039 & 0.2069 & 0.4829 & 0.2279 & 4 \\ Spectrum of Graph Laplacian & -0.2023 & 0.1467 & 0.0794 & 0.0095 & 8 & -0.7648 & -0.4311 & 0.2611 & -0.2300 & 8 \\ Betweenness Centrality & -0.2739 & -0.2554 & 0.2051 & 0.2241 & 7 & -0.3421 & -0.5903 & 0.1364 & 0.0849 & 7 \\ \hline W2PGNN (interject) & 0.3579 & 0.1224 & 0.3313 & 0.1072 & 6 & 0.0841 & 0.5310 & 0.4213 & -0.0916 & 6 \\ W2PGNN (domain) & **0.4774** & 0.4666 & 0.6775 & 0.3460 & 3 & **0.7132** & 0.5523 & **0.7381** & 0.1857 & 3 \\ W2PGNN (topo) & 0.2059 & 0.3908 & 0.3745 & 0.4464 & 4 & 0.4900 & 0.5061 & 0.4072 & 0.1497 & 5 \\ W2PGNN (\(x=1\)) & 0.4172 & 0.5206 & 0.6829 & 0.4391 & 2 & 0.5282 & 0.6663 & 0.7240 & **0.3246** & 1 \\ W2PGNN & 0.3941 & **0.5336** & **0.7162** & **0.4838** & 1 & 0.5089 & **0.6706** & 0.6754 & 0.3166 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Pearson correlation coefficient between the estimated pre-training feasibility and the best downstream performance on node classification. \(N\) denotes the number of candidate pre-training datasets that form the pre-training data. Bold indicates the highest coefficient. “Rank” represents the overall ranking on all downstream datasets.

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{\(N=2\)} & \multicolumn{6}{c}{\(N=3\)} \\ \cline{2-13}  & BACE & BBBP & MUV & HIV & ClinTox & Rank & BACE & BBBP & MUV & HIV & ClinTox & Rank \\ \hline Graph Statistics & -0.4118 & -0.1328 & 0.3858 & 0.0174 & -0.3577 & 9 & -0.3093 & -0.1430 & 0.1946 & 0.3545 & -0.1372 & 7 \\ EGI & 0.2912 & -0.6862 & 0.4488 & 0.0587 & 0.0452 & 7 & 0.4570 & 0.3230 & 0.3024 & 0.4144 & -0.0085 & 3 \\ Clustering Coefficient & -0.5098 & -0.5097 & 0.3754 & 0.4738 & 0.5154 & 8 & -0.4080 & 0.3217 & -0.1190 & -0.2483 & -0.4248 & 9 \\ Spectrum of Graph Laplacian & -0.0633 & -0.4878 & -0.3413 & -0.1125 & -0.2562 & 10 & -0.3563 & -0.1611 & -0.2294 & -0.2448 & 0.3001 & 8 \\ Betweenness Centrality & -0.0021 & -0.7755 & 0.4040 & 0.0339 & 0.3411 & 6 & -0.3695 & -0.4568 & -0.2752 & -0.3035 & -0.2129 & 10 \\ \hline W2PGNN (interject) & 0.7547 & **0.7790** & 0.2907 & 0.7033 & 0.5639 & 3 & 0.4081 & 0.4687 & -0.0567 & 0.3802 & 0.4354 & 5 \\ W2PGNN (domain) & 0.7334 & 0.7689 & 0.5395 & 0.6831 & 0.5431 & 5 & 0.0864 & 0.3680 & 0.0187 & 0.4784 & 0.3765 & 6 \\ W2PGNN (topo) & 0.6656 & 0.7164 & 0.8131 & **0.7391** & 0.5406 & 2 & 0.1109 & 0.5357 & 0.0514 & 0.3265 & 0.4724 & 4 \\ W2PGNN (\(a=1\)) & 0.6549 & 0.7690 & 0.6730 & 0.7033 & 0.5639 & 4 & 0.5287 & **0.7102** & 0.1925 & 0.5893 & 0.5430 & 2 \\ W2PGNN & **0.7549** & 0.7767 & **0.8131** & 0.7044 & **0.5784** & **1** & **0.6207** & 0.6696 & **0.5227** & **0.6529** & **0.5994** & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Pearson correlation coefficient between the feasibility and the best downstream optimization.
For node classification tasks, we use the following 4 graph pre-training models: GraphCL [52] and GCC models [32] with three different hyper-parameter (_i.e._, 128, 256 and 512 rw-hops). For graph classification tasks, we adopt 7 SOTA pre-training models: AttMarkMasing [15], ContextPred [15], EdgePred [15], Infomax [15], GraphCL [52], GraphMAE [14] and JOAO [51]. When pre-training, we directly use the default hyper-parameters of pre-training models except the rw-hops in GCC. During fine-tuning, we freeze the parameters of pre-trained models and utilize the logistic regression as classifier for node classification and SVM as classifier for graph classification, following [32] and its fine-tuning hyper-parameters. The downstream results are reported as the average of Micro F1 and ROC-AUC under 10 runs on node classification and graph classification respectively. For each downstream task, the best performance among all methods is regarded as the ground truth.

For a comprehensive evaluation on the correlation between the estimated pre-training feasibility and the above ground truth (_i.e._, best downstream performance), we need to construct multiple \(\langle\mathcal{G}_{\text{train}},\mathcal{G}_{\text{down}}\rangle\) sample pairs as our evaluation samples. When constructing the \(\langle\mathcal{G}_{\text{train}},\mathcal{G}_{\text{down}}\rangle\) sample pairs for each downstream data, multiple pre-training data are required to be paired with it. Hence we adopt the following two settings to augment the choice of pre-training data for more possibilities. Here we use \(N\) as the number of dataset candidates contained in pre-training data. (1) For \(N=2\) setting, we randomly select 2 pre-training dataset candidates as pre-training data and enumerate all possible cases. (2) For \(N=3\) setting, we randomly select 3 pre-training dataset candidates as pre-training data. We enumerate all possible cases for graph classification tasks and randomly select 40% of all cases for node classification tasks for efficiency.

**Results.** Table 1 (for node classification) and Table 2 (for graph classification) show the Pearson correlation coefficient between the best downstream performance and the estimated pre-training feasibility by W2PGNN and baselines for each downstream dataset. A higher coefficient indicates a better estimation of pre-training feasibility. We also include 4 variants of W2PGNN: W2PGNN (intergr), W2PGNN (domain) and W2PGNN (topo) only utilize the integrated graphon basis, domain graph basis and topological graphon basis to approximate feasibility respectively, and W2PGNN (\(\alpha=1\)) directly set the learnable combination weights \(\{\alpha_{i}\}\) as fixed constant 1. We have the following observations. (1) The results show that our model achieve the highest overall ranking in most cases, indicating the superiority of our proposed framework. (2) We find that the measures provided by other baselines sometimes show no correlation or negative correlation with the best downstream performance. (3) Comparing W2PGNN and its 4 variants, we find that although the variants sometimes achieve superior performance on some downstream datasets, they cannot consistently perform well on all datasets. In contrast, the top-ranked W2PGNN can provide a more comprehensive picture with various graph bases and learnable combination weights.

To provide a deeper understanding of the feasibility estimated by W2PGNN, Figure 3 shows our estimated pre-training feasibility (in x-axis) versus the best downstream performance on node classification (in y-axis) of all \(<\)pre-training data, downstream data- pairs (one point represents the result of one pair) when the selection budget is 2. The plots when the selection budget is 3 and the plots under graph classification can be found in Appendix C.1. We find that there exist a strong positive correlation between estimated pre-training feasibility and the best downstream performance on

Figure 3. Pre-training feasibility vs. the best downstream performance on node classification when the selection buget is 2.

\begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{\(N=2\)} & \multicolumn{6}{c}{\(N=3\)} \\ \cline{2-10}  & US-Airport & Europe-Airport & H-index & Chameleon & Rank & US-Airport & Europe-Airport & H-index & Chameleon & Rank \\ \hline All Datasets & 65.62 & 55.65 & 75.22 & 46.81 & - & 65.62 & 55.65 & 75.22 & 46.81 & - \\ \hline Graph Statistics & 64.20 & 53.36 & 74.30 & 44.31 & 4 & 62.27 & 54.58 & 72.88 & 43.87 & 5 \\ EGI & **64.96** & 57.37 & 74.30 & 43.21 & 2 & 62.27 & 57.36 & 72.28 & 45.93 & 3 \\ Clustering Coefficient & 62.61 & 52.87 & **77.74** & 43.21 & 3 & 62.94 & 54.58 & 75.18 & 44.66 & 4 \\ Spectrum of Graph Laplacian & 61.76 & **57.88** & 73.14 & 42.20 & 5 & **63.95** & 54.87 & 73.90 & 44.66 & 2 \\ Betweenness Centrality & **64.96** & 52.87 & 73.50 & 41.63 & 6 & 62.27 & 54.87 & 75.18 & 43.87 & 6 \\ \hline W2PGNN & **64.96** & **57.88** & 77.24 & **45.54** & 1 & **63.95** & **57.59** & **75.68** & **46.07** & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Node classification results when performing pre-training on different selected pre-training data. We also provide the results of using all pre-training data without selection for your reference (see “All Datasets” in the table).
all downstream datasets, which also suggests the significance of our feasibility.

### Results of Pre-Training Data Selection

Given the downstream data, a collection of pre-training dataset candidates and a selection budget (_i.e._, the number of datasets selected for pre-training) due to limited resources, we aim to select the pre-training data with the highest feasibility, so as to benefit the downstream performance.

**Setup.** We here adopt two settings, _i.e._, selection budget is set as 2 and 3 respectively. The datasets that are augmented for more pre-training data choices in Section 6.2 can be directly used as the candidates of pre-training datasets here. Then, the selected pre-training data serves as the input of graph pre-training model. For node classification tasks, we adopt GCC as the pre-training model as an example, because it is the pre-training model that can be generalized across domains and most of the datasets used for node classification are taken from it (Zhou et al., 2019). For graph classification tasks, we take GraphCL as the pre-training model as it provides multiple graph augmentation approaches and is more general (Zhou et al., 2019).

**Results.** Table 3 shows the results of pre-training data selection on node classification task. (The results on graph classification is included in Appendix C.2). We have the following observations. (1) We can see that the pre-training data selected by W2PGNN ranks first, which is the most suitable one for downstream. (2) We find that sometimes simple graph property like clustering coefficient serves as a good choice on a specific dataset (_i.e._, H-index), when the budget of pre-training data is 2. It is because that H-index exhibits the largest clustering coefficient compared to other downstream datasets (see Table 4), which facilitates the data selection via clustering coefficient. However, such simple graph property is only applicable when the downstream dataset shows a strong indicator of the property, and is not helpful when you need to select more datasets for pre-training (see results under _N=3_). (3) Moreover, it is also interesting to see that using all pre-training data for pre-training is not always a reliable choice. We find that carefully selecting pre-training data can not only benefit downstream performance but also reduce computation resources.

## 7. Conclusion

This paper proposes a W2PGNN framework to answer the question of _when to pre-train_ GNNs based on the generative mechanisms from pre-training to downstream data. W2PGNN designs a graph-based graph generator to summarize the knowledge in pre-training data, and the generator can in turn produce the solution space of downstream data that can benefit from the pre-training. W2PGNN is theoretically and empirically shown to have great potential to provide the application scope of graph pre-training models, estimate the feasibility of pre-training and help select pre-training data.
