Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
Authors: Qi Zhu
Carl Yang
Yidan Xu
Haonan Wang
Chao Zhang
Jiawei Han
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
transfer learning
pre-training
domain adaptation
theoretical guarantee

Abstract: Graph neural networks (GNNs) have achieved superior performance in various applications, but training dedicated GNNs can be costly for large-scale graphs. Some recent work started to study the pre-training of GNNs. However, none of them provide theoretical insights into the design of their frameworks, or clear requirements and guarantees towards their transferability. In this work, we establish a theoretically grounded and practically useful framework for the transfer learning of GNNs. Firstly, we propose a novel view towards the essential graph information and advocate the capturing of it as the goal of transferable GNN training, which motivates the design of EGI (Ego-Graph Information maximization) to analytically achieve this goal. Secondly,
when node features are structure-relevant, we conduct an analysis of EGI transferability regarding the difference between the local graph Laplacians of the source and target graphs. We conduct controlled synthetic experiments to directly justify our theoretical conclusions. Comprehensive experiments on two real-world network datasets show consistent results in the analyzed setting of direct-transfering, while those on large-scale knowledge graphs show promising results in the more practical setting of transfering with fine-tuning.

Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
Qi Zhu'; ; Carl Yang"; Yidan Yidan Xu², Haonan Wang', Chao Zhang', Jiawei Han'
University of Illinois Urbana-Champaign. EEmory University, University of Washington, 'Georgia Institute of Technology h yyx25160uw. edu, "chaozhang@gatech edu
edu, "j carlyangdemory. edu,
Abstract
Graph neural networks (GNNs) have achieved superior performance in various applications, but training dedicated GNNs can be costly for large-scale graphs. Some recent work started to study the pre-training of GNNs. However, none of them provide theoretical insights into the design of their frameworks, or clear re- quirements and guarantees towards their transferability. In this work, we establish a theoretically grounded and practically useful framework for the transfer learning of GNNs. Firstly, we propose novel view towards the essential graph information and advocate the capturing of it as the goal of transferable GNN training, which motivates the design of EGI LEgo-Graph Information maximization) to analytically achieve this goal. Secondly, when node features are structure-relevant, we conduct an analysis of EGI transferability regarding the difference between the local graph Laplacians of the source and target graphs. We conduct controlled synthetic experi- ments to directly justify our theoretical conclusions. Comprehensive experiments two real-world network datasets show consistent results in the analyzed setting firncc-transfcring, while those on large-scale knowledge graphs show promising results in the more practical setting of transfering with fine-tuning
1 Introduction
26 39 68 due to their as well as close connections to spectral graph theory [12 9 16]. While most GNN architectures are not very complicated, the training of GNNs can still be costly regarding both memory and computation resources on world large-scale graphs [10 63 Moreover, it is intriguing transfer learned structural information across different graphs and even domains in settings like few-shot learning [56] 44 25]. Therefore, several 47)
Graph neural networks (GNNs) have been intensively studied recently 29
established performance towards various real-world tasks [5
69
53
very recent studies have been conducted
the transferability of GNNs 21
23
22
59
However, it is unclear in what situations the models will excel or fail especially when the pre-training and fine-tuning tasks are different. To provide rigorous analysis and guarantee the transferability of GNNs, we focus on the setting of direct-transfering between the source and target graphs, under an analogous setting of "domain adaptation" 7 (59
In this work, we establish a theoretically grounded framework for the transfer learning of GNNs, and leverage it to design practically transferable GNN model. Figure gives overview of our framework. It is based on a novel view a graph as samples from the joint distribution of its k-hop ego-graph structures and node features, which allows to define graph information and similarity,
'These two authors contribute equally.
Code and processed data are available aalctppss/ggihhhu...cm///etttttd
35th Conference on Neural Information Processing Systems (NcurIPS 2021), Online.

---

Source Go
Target
Target Ga
top ego-graphs
ego-graph distribution
d 0.748
1.054
node features
mode degree emooxiing spectral embeddinng
degree encoding spectral embedding
random or uniform variables graph-spocite node atriiuutes
EGI Training Transferable?
similar ego-graphs
dissimilar ego-graphs x non-transferable features
transforable features
Overview of our GNN transfer lcarning framework: (1) we represent the toy graph as a combination of its l-hop ego-graph and node feature distributions; (2) we design a transferable GNN regarding the capturing of such essential graph information; (3) establish rigorous guarantee of GNN transferability based on the node feature requirement and graph structure difference.
Figure 1:
so as to analyze GNN transferability ($3). This view motivates us to design EGI, a novel GNN training objective based ego-graph information maximization, which effective in capturing the graph information as we define ($3.1). I. Then we further specify the requirement on transferable node features and analyze the transferability of EGI that is dependent on the local graph Laplacians of source and target graphs ($3.2).
All of our theoretical conclusions have been directly validated through controlled synthetic experi- ments (Table where we use structural-equivalent role identification in an direct-transfering setting analyze the impacts of different model designs, node features and source-target structure similari- ties on GNN transferability. In $4 we conduct real-world experiments on multiple publicly available network datasets. On the Airport and Gene graphs ($4.1). we closely follow the settings of our synthetic experiments and observe consistent but more detailed results supporting the design of EGI and the utility of our theoretical analysis. On the YAGO graphs ($4.2). we further evaluate EGI on the more generalized and practical setting of transfer learning with task-specific fine-tuning. We find our theoretical insights still indicative in such scenarios, where EGI consistently outperforms state-of-the-ar GNN representation and transfer learning frameworks with significant margins.
2 Related Work
Representation learning on graphs has been studied for decades, with earlier spectral based methods
6 46. [2] theoretically grounded but hardly scaling up to graphs with over thousand of nodes.
With the emergence of neural networks, unsupervised network embedding methods based on the Skip-gram objective (37] have replenished the field [51] 14
42
45
66 62] 65). Equipped with
efficient structural sampling (random walk, neighborhood, etc.) and negative sampling schemes, these methods are easily parallelizable and scalable to graphs with thousands to millions of nodes. However, these models are essentially transductive as they compute fully parameterized embeddings only for nodes seen during training. which are impossible be transfered unseen graphs.
More recently, researchers introduce the family of graph neural networks (GNNs) that are capable of inductive learning and generalizing unseen nodes given meaningful node features (29 12 15] 67
Yet, most existing GNNs require task-specific labels for training in a semi-supervised fashion to
achieve satisfactory performance [29] [5 53 64] and their usage is limited to single graphs where the downstream task fixed. To this end, several unsupervised GNNs are presented, such as the auto-encoder-baat based ones like VGAE (28 and GNFs (35. well as the deep-infomax -basee ones like DGI [54] and InfoGraph [50]. Their potential in the transfer learning of GNN remains unclear when the node features and link structures vary across different graphs.
Although the architectures of popular GNNs such as GCN [29] may not very complicated compared with heavy vision and language models, training a dedicated GNN for each graph can still

---

be cumbersome 10, 63 Moreover, pre-training neural networks are proven to be successful in
other domains [33 18 the idea is intriguing to transfer well-trained GNNs from relevant source
graphs to improve the modeling of target graphs or enable few-shot learning [59
31
3 when
labeled data are scarce. light of this, pioneering works have studied both generative 22 and
discriminative 211231 GNN pre-training schemes. Though Graph Contrastive Coding 4 shares
the most similar view towards graph structures as us, it utilizes contrastive learning across all graphs instead of focusing on the transfer learning between any specific pairs. On the other hand, unsupervised domain adaptive GCNs [59] study the domain adaption problem only when the source and target tasks are homogeneous.
Most previous pre-training and self-supervised GNNs lack a rigorous analysis towards their trans- ferability and thus have unpredictable effecttivnesss. The only existing theoretical work on GNN transferability studies the performance of GNNs across different permutations of a single original graph 33 3 and the tradeoff between discriminability and transferability of GNNs [47.. We, instead, are the first to rigorously study the more practical setting of transferring GNNs across pairs of different source and target graphs.
Transferable Graph Neural Networks
In this paper, we design a more transferable training objective for GNN (EGI) based on our novel view of essential graph information (G..)) We then analyze its transferability as the gap between its abilities to model the source and target graphs, based on their local graph Laplacians ($3.2).
Based on the connection between GNN and spectral graph theory (29]. we describe the output of a GNN as combination of its input node features X, fixed graph Laplacian I. and learnable graph filters V. The goal of training GNN is then to improve its utility by learning the graph filters that are compatible with the other two components towards specific tasks.
In the graph transfer learning setting where downstream tasks are often unknown during pre-training, we argue that the general utility of GNN should be optimized and quantified w.zt. its ability of capturing the essential graph information in terms of the joint distribution of its topology structures and node features, which motivates to design a novel ego-graph information maximization model (EGI) ( I3..). The general transferability of a GNN is then quantified by the gap between its abilities to model the source and target graphs. Under reasonable requirements such using structure- respecting node features as the GNN input, we analyze this gap for EGI based on the structural difference between two graphs w.r.f. their local graph Laplacians ($3.2).
3.1 Transferable GNN via Ego-graph Information Maximization
In this work, we focus on the direct-transfering setting where GNN is pre-trained on a source graph Ga in an unsupervised fashion and applied on a target graph G, without fine-tuning graph G (V, EV, where the set of nodes V are associated with certain features X and the set of edges E form graph structures. Intuitively, the transfer learning will be successful only if both the features and structures of G2 and G2 are similar in some ways, so that the graph filters of a GNN learned on G. are compatible with the features and structures of Gg.
2 Consider a
Graph kernels 57
30 38
well-known for their capability of measuring similarity between pair
of graphs. Motivated by k-hop subgraph kernels A. we introduce a novel view of a graph as samples from the joint distribution of its k-hop ego-graph structures and node features. Since GNN essentially encodes such k-hop ego graph samples, this view allows us to give concrete definitions towards structural information of graphs in the transfer learning setting, which facilitates the measuring of similarity (difference) among graphs. Yet, none of the existing GNN training objectives are capable of recovering such distributional signals of ego graphs. To this end, we design Ego-Graph Information maximization (EGI), which alternatively reconstructs the k-hop ego- ggo-graph of each center node via mutual information maximization (20).
Definition 3.1 (K-hop ego- gro-gr.ph). We call a graph g; = (V..). E(g:) a k-hop ego-graph centered at node v; if it has a k-layer centroid expansion 4 such that the greatest distance between v; and
'In the experiments, we show our model to be generalizable to the more practical settings with task-specific pre-training and fine- fine-tuning, while the study of rigorous bound in such scenarios is left as future work.
3

---

any other nodes in the ego- ago-graph is k, i.e. Vey E V [d(e,, 2y)1 S k, where d(v,, U/) is the graph distance between V; and V..
In this paper, we use directed k-hop ego-graph and its direction decided by whether it is composed of incoming or outgoing edges to the center node, i.e., and 9:. The results apply trivially to undirected graphs with 9i gs.
Definition 3.2 (Structural information). Let 9 be a topological space of sub trabhgrrass we view graph G as samples of k-hop ego-graphs {9r1== drawn i..d. from G with probability μ4, ie., i.d. μ vi = -,... n. The structural information of G is then defined to be the set of k-hop ego-graphs of {gi)%-1 and their empirical distribution.
As shown in Figure [ three graphs Go. G1 and G2 are characterized by set of I-hop ego-graphs and their empirical distributions, which allows us to quantify the structural similarity among graphs shown in $3.2 (i.e., Go is more similar Gi than G2 under such characterization). In practice, the nodes in graph G are characterized not only by their k-hop ego-graph structures but also their associated node features. Therefore, G should be regarded as samples {(g. xz,} drawn from the joint distribution I' on the product space of G and a node feature space X.
Ego-graph xi)
Encoder
center node
Discriminator D
embedding
hop
hop
Zj
edge message passing
Edge-wise decision
Ego-graph x/'
X
x
Zi
edge message possing
Figure 2: The overall EGI training framework.
Ego-Graph Information Maximization. Given a set of ego-graphs {(g,, 24)}; drawn from an empirical joint distribution (g:, 22) ~ P. We aim to train an GNN encoder V to maximize the mutual informaion (MI (gt, (g;; zx))) between the defined structural information 9 (i.e. k-hop ego-graph) and node embedding 2; (g:, 2x). To maximize the MI, another discriminator D(gi, z;) F(g:)) 2, - I introduced to compute the probability an edge belongs to the given ego-graph 9:. We use the Consen-Shanme MI estimator (20) in the EGI objective,
L 01 (G, v)
N Σ Isp (D(gi, +0) + sp (-D(g,, =;)]],
(1)
where sp(x) = ee the softplus function and (gs: =[) is randomly drawn from the product of marginal distributions, i.e. z! (gr,, my), (gv,,y) ~ IP, of In general, we can also randomly draw negative of in the topological space, while enumerating all possible graphs gr leads to high computation cost.
In Eq. the computation D on E(g.) depends on the node orders. Following the common practice in graph generation [70), we characterize the decision process of DD with fixed graph ordering, i.e. the BFS-ordering over edges E(g.). D f + composed by another GNN encoder and scoring function f over an edge sequence Ex {el, 62, ..., en), which makes predictions on the BFS-ordered edges.
LLter in section 3.2 we will discuss the equivalence between MI(g., x)) and MI((g, Iz), 2.) when node
feature is structure- muneture-rsppectnng

---

More model details in Appendix B and source code in Recall our previous definition on the direction of k-hop ego- gro-graph, the center node encoder v receives pairs of Ig) while the neighbor node encoder in discriminator DD receives Zi). Both encoders are parameterized as GNNs,
V (gr, zz) = (A,, ((., x.)) = GNN, (4,,
where A., A is the adjacency matrix with self-loops of 9: and 9.. respectively. The self-loops are added following the common design of GNNs, which allows the convolutional node embeddings to always incorporate the influence of the center node. A, A! The output of v, i.e., 2, E R" is the center node embedding, while & outputs representation H E Blai for neighbor nodes in the ego-graph.
Once node representation H is computed, we now describe the scoring function f. For each of the node pair (p.g) v) E", hp is the source node representation from o, Fy is the destination node features. The scoring function is,
f(hp, Fgg 21) o (UT (WW"Ihpll= [1p]|=y||23)
(2)
where a and are Sigmoid and ReI.U activation functions. Thus, the discriminator 'D is asked to distinguish a positive ((p, q), zi) and negative pair ((p, q), 2()) for each edge in g:.
E
D(g:
Σ
log (h
pp: Fag zi), D(g z/)
Σ (p-4)
log f( Lgg 2f).
(P.4)EE*
There are two types of edges (p. q) in our consideration of node orders, rype-a the edges across different hops (from the center node), and type-b the edges within the same hop (from the center node). The aforementioned BFS-based node ordering guarantees that Eq. 1g sensitive to the ordering of type-a edges, and invariant to the ordering of type-b edges, which is consistent with the requirement of our theoretical analysis on AD. Due the fact that the output of k-layer GNN only depends on a k-hop ego-graph for both encoders V/ and 4, EGI can be trained in parallel by sampling batches of g ss Besides, the training objective of EGI is transferable as long as (g;, across source graph G. and G2 satisfies the conditions given in $3.2 the Supplementary Materials.
Connection with existing work. To provide more insights into the EGI objective, we also present it as dual problem of ego-graph reconstruction. Recall our definition -go-graph mutual information (I V (gi, a.)). It can be related to an ego-graph reconstruction loss R(gs V ((r. xx)) as
max (l.g. L (g., 24)) = (g:) - (g: M (g:, x:)) & H - R(g M Iz)).
(4)
When EGI is maximizing the mutual information, it simultancously minimizes the upper error bound of reconstructing an ego-graph 9i- In this view, the key difference between EGI and VGAE (8 is they assume each edge in graph to be observed independently during the reconstruction. While in EGI, edges in an ego-graph are observed jointly during the GNN decoding. Moreover, existing mutual information based GNNs such as DGI [54) and GMI 41 explicitly measure the mutual information between node features x and GNN output V. In this way, they tend to capture node features instead of graph structures, which we deem more essential in graph transfer learning as discussed in $.2
Use cases of EGI framework. In this paper, we focus on the classical domain adaption (direct- transferring) setting 77) where no target domain labels are available and transferability is measured by the performance discrepancy without fine-tuning. In this setting, the transferability of EGT is theoretically guaranteed by Theorem 3.1 In $ we validated this with the airport datasets. Beyond tireet-transferring EGI is also useful in the more generalized and practical setting of transfer learning with fine-tuning, which we introduced $4.2 and validated with the YAGO datasets. In this setting, the transferability of EGI is not rigorously studied yet, but is empirically shown promising.
Supportive observations. In the first three columns of our synthetic experimental results (Table I in both cases of transfering GNNs between similar graphs (F-F) and dissimilar graphs (B-F), EGI significantly outperforms all competitors when using node degree one-hot encoding as transferable node features. In particular, the performance gains over the untrained GIN show the effectiveness of training and transfering, and our gains are always larger than the two state-of-the-ar unsupervised GNNs. Such results clearly indicate advantageous structure preserving capability and transferability of EGL.
5

---

3.2 Transferability analysis based on local graph Laplacians
We now study the transferability of a GNN (in particular, with the training objective of LEG) between the source graph G. and target graph G3 based on their graph similarity. We firstly establish the requirement towards node features, under which we then focus on analyzing the transferability of EGI w.rl. the structural information of G. and Gb-
Recall view of the GNN output as combination of its input node features, fixed graph Laplacian and learnable graph filters. The utility of a GNN is determined by the compatibility among the three. In order to fulfill such compatibility, we require the node features be structure- respetttin-....:inn:: Definition 3.3 Structure-respectiing node features). Let be an ordered ego-graph centered on node vs with a set of node features { ppp.gp=00.q=1 (..)) where Vylg.) is the set of nodes in p-th hop of gi- Then we say the node features on gi are structurrerespecting if f = [f(g))lo I for any node "y Vg(g),, where G > [V is a function. In the strict case, J should be injective.
In its essence, Def 3.3 requires the node features to be a function of the graph structures, which is sensitive to changes in the graph structures, and in an ideal case, injective to the graph structures (i.e., mapping different graphs different features). In this way, when the learned graph filters of a transfered GNN is compatible to the structure of G. they are also compatible to the node features of G. As we will explain in Remark Of Theorem 3.1 this requirement also essential for the analysis of EGI transferability which eventually only depends on the structural difference between two graphs.
In practice, commonly used node features like node degrees, PageRank scores 40), . spectral em- beddings [1]] and many pre-computed unsupervised network embeddings 44] 51 [4] are all structure-respeccing in nature. However, other commonly used node features like random vectors (68) or uniform vectors (60) are not and thus non-transferable. When raw node attributes are available. they are transferable as long as the concept of homophily 36 applies, which also implies Def 3.3 but we do not have rigorous analysis on it yet.
Supportive observations. In the fifth and sixth columns in Table where we use same fixed vectors non-transferable node features contrast with the first three columns, there is almost no transfcrability (see ó ((ccc.)) for all compared methods when conttransferable features are used, as the performance of trained GNNs are similar to worse than their untrained baselines. More detailed experiments on different transferable and non-transferable features can be found in Appendix $C.I
With our view of graphs and requirement node features both established, following theorem by characterizing the performance difference of EGI on two graphs based on Eq, [I
derive the
) Theorem 3.1 (GNN transferability). Let G. { x and G2 (gr, I.) D== be two graphs, and assume node features are structure- releevat. Consider GCN Ve with k layers and a I h-hop polynomial filter db With reasonable assumptions on the local spectrum of Ga and Go, the empirical performance difference of V evaluated on Lyca satisfies
(L., L.e((Gr) S O (AD Ga) +C).
(5)
On the RHS, C is only dependent on the graph encoders and node features, while Ap(Ga, Gb) measures the structural difference between the source and target graphs as follows,
AD Gb) = =
Xmaox (Lg. -Lgg)
(6)
TETTL
where Amax (A) Amax(A² (AT A)1/2, and i.g, denotes the normalised graph Laplaciann of ÿ; by its in-degree. constant dependant on >max (Lgg) and D.
Proof. The full proof is detailed in Appendix
The analysis in Theorem 3.I naturally instantiates our insight about the correspondence between structural similarity and GNN transferability. It allows us to tell how well an EGI trained on G. can work on G, by only checking the local graph Laplacians of G. and G, without actually training any model. In particular, we define the EGI gap as Ap in Eq. 6 as other term C' is the same for different methods using same GNN encoder. can be computed to bound the transferability of EGI regarding its loss difference the source and target graphs.

---

Our view of graph G as samples of k-hop ego-graphs is important, as it allows us to obtain node-wise characterization of GNN similarty as in [55V. also allows us to set the depth of ego-graphs in the analysis to be the same as the number of GNN layers (k), since the GNN embedding of each node mostly depends on its k-hop ego-graph instead of the whole graph.
Remark 1.
Remark 2. For Eq. 7 Dej 3.3 ensures the sampling of GNN embedding at a node always corresponds to sampling an ego-graph from G, which reduces to uniformly sampling from G {9:) under the setting of Theorem 3.7 Therefore, the requirement of Def in the context of Theorem 3.1
guarantees the analysis to be only depending on the structural information of the graph.
Supportive observations. In Table 1 in the d columns, we compute the average structural difference between two Forest- fire graphs (Ap(F.F) and between Barabasi and Forest-fire graphs (A)( based on the RHS of Eq. 5) The results validate the topological difference between graphs generated by different random-graph graph models, while also verifying our view of graph as k-hop ego-graph samples and the way we propose based on it to characterize structural information of graphs. We further highlight in the ò(acc) columns the accuracy difference between the GNNs transfered from Forest-fire graphs and Barabasi graphs to Forest-fire graphs. Since Forest-fire graphs are more similar to Forest-fire fire graphs than Barabasi graphs (as verified in the Ad columns), we expect 8(acc.) to be positive and large, indicating more positive transfer between the more similar graphs. Indeed, the behaviors of EGI align well with the expectation, which indicates its well-understood transferability and the utility of our theoretical analysis.
Use cases of Theorem 3.1, Our Theorem 3.1 naturally allows for two practical use cases among many others: point-wise pre-judge and pair-wise pre-selection for EGI pre-training. Suppose we have a target graph G2 which does not have sufficient training labels. In the first setting, we have a single source graph Go which might be useful for pre-training GNN to be used Gg. The EGI gap Ap(G.. G.) in Eq. [ then be computed between G2 and G3 to pre-judge whether such transfer learning would be successful before any actual GNN training (i.e., yes if (D Gb) is empirically much smaller than 1.0; no otherwise). In the second setting, we have two or more source graphs {G,, Co Ca.... ... which might be useful for pre-training the GNN. The EGI gap then be computed between every pair of G and G5 to pre-select the best source graph (i.e., select the one with the least EGI gap).
In practice, the computation of eigenvalues on the small ego-graphs can be rather efficient (2) and we do not need to enumerate all pairs of ego-graph are really large (e.g., with more than a thousand nodes). Instead, we can randomly sample pairs of ego-graphs from the two graphs, update the average difference on-the-fly, and stop when it converges. Suppose we need to sample M pairs of k-hop ego- ego-graphs to compare two large graphs, and the average size of ego- ggo-graphs are L, then the overall complexity of computing Eq, is (ML where M is often less than 1K and L less than 50. In Appendix $C..4 we report the approximated Ap's 's w.r.f. different sampling frequencies, and they are indeed pretty close the actual value even with smaller sample frequencies, showing the feasible efficiency of computing Ap through sampling.
two compared graphs especially if the graphs
Limitations. EGI is designed to account for the structural diffcrence captured by GNNs (i.c., k- hop ego-graphs). The effectiveness of EGI could be limited if the tasks on target graphs depend on different structural signals. For example, as Eq. 6 is computing the average pairwise distances between the graph Laplacians of local ago-graphs, Ap is possibly less effective in explicitly capturing global graph properties such as numbers of connected components (CCs). In some specific tasks (such counting CCs community detection) where such properties become the key factors, Ap may fail to predict the transferability of GNNs.
Real Data Experiments
We compare the proposed model against existing self-supervised GNNs and pre-training GNN algorithms. To exclude the impact of different GNN encoders Vi on transferability, we always use the same encoder architecture for all compared methods (i.e., GIN [60] for direct-transfering experiments, GCN 29 for transfering with fine-tuning).
Baselines.
The self-supervised GNN baselines are GVAE 28), DGI (54 and two latest mutual information estimation methods GMI [1] and MVC 17] As for pre-training GNN algorithms, MaskGNN
7

---

Table I: Synthetic experiments of identifying structural equivalent nodes. We randomly generate 40 graphs
with the Forest-fire model (F) [22 and 40 graphs with the Barabasi model (B) M. The GNN model is GIN [60]
with random parameters (baseline with only the neighborhood aggregation function), VGAE[28). DGI [54]. and EGI with GIN encoder. We train VGAE, DGI and EGI on one graph from either set (F and B), and test them on
the rest of fire graphs (F). Transferable feature is node degree one-hot encoding and non- non-transferable feature is uniform vectors. More details about the results and dataset can be found in Appendix C.
transferable features
non-transferable feature 5(acc.)
structural difference Az(F.F)
Method
F-F
B-F
8(acc.)
F-F
B-F
Ap(B.F)
GIN (untrained)
0.572
0.572
/
0.358
0.358
VGAE (GIN)
0.498
0.432
+0.066
0.240
0.239
0.001
DGI (GIN)
0.578
0.591
-0.013
0.394
0.213
+0.181
0.752
0.883
EGI (GIN)
0.710
0.616
+0.094
0.376
0.346
+0.03
and ContextPredGNN are two node-level pre-training models proposed in [2] Besides, Structural Pre-train [23] also conducts unsupervised node-level pre-training with structural features like node degrees and clustering coefficients.
Experimental Settings. The main hyperparameter k is set 2 in EGI common practice. We use Adam (27] as optimizer and learning rate is 0.01. We provide the experimental result with varying k in the Appendix CC.4 All baselines are set with the default parameters. Our experiments were run on an AWS g4dn.2xlarge machine with Nvidia T4 GPU. By default, we use node degree one-hot encoding as the transferable feature across all different graphs. As stated before, other transferable features like spectral and other pre-computed node embeddings are also applicable. We focus on the setting where the downstream tasks target graphs are unspecified but assumed to be sruuctrr-relevant and thus pre-train the GNNs on source graphs in an unsupervised fashion Fl In terms of evaluation, we design two realistic experimental settings: (1) Firect-transfering on the more structure-relevant task of role identification without given node features to directly evaluate the utility and transferability of EGI. (2) Few-shot learning on relation prediction with tpsk-specific node features to evaluate the generalization ability of EGI.
4.1 Direcc-transfernng on role identification
First, we use the role identification without node features in a diieec-transferiin setting as a reliable proxy to evaluate transfer learning performance regarding different pre- pre-training objectives. Role in a network defined as nodes with similar structural behaviors, such as clique members, hub and bridge [19. Across graphs in the same domain, we assume the definition of role to be consistent, and the task of role identification is highly structure-relevant, which can directly reflect the transferability of different methods and allows us to conduct the analysis according to Theorem 33.] Upon convergence of pre-training each model on the source graphs, we directly apply them to the target graphs and further train a multi-layer perceptron (MLP) upon their outputs. The GNN parameters are frozen during the MLP training. We refer to this strategy as direct-transsering since there is no fine-tuning of the models after transfering to the target graphs
We use two real-world network datasets with role-based node labels: (1) Airport 45 contains three networks from different regions- Brazil, USA and Europe. Each node is an airport and each link the flight between airports. The airports are assigned with external labels based on their level of popularity. (2) Gene [68] contains the gene interactions regarding 50 different cancers. Each gene has binary label indicating whether it is transcription factor. More details about the results and dataset can be found in Appendix C.2
The experimental setup on the Airport dataset closely resembles that of our synthetic experiments in Table but with real data and more detailed comparisons. We train all models (except for the untrained ones) on the Europe network, and test them on all three networks. The results are presented in T We notice that the node degree features themselves (with MLP) show reasonable performance in all three networks, which is not surprising since the popularity-bart -base airport role labels are highly relevant to node degrees. The untrained GIN encoder yields a significant margin over just node features, as GNN encoder incorporates structural information to node representations.
'The downstream tasks are unspecified because we aim to study the general transferability of GNNs that is not bounded to specific tasks. Nevertheless, assume the tasks to be relevant graph structures.
8

---

While training of the DGI can further improve the performance on the source graph, EGI shows the best performance there with the cruuttre-rrlevam node degree features, corroborating the claimed effectiveness of EGI in capturing the essential graph information (i.e. recover the k-hop ego-graph
distributions) as we stress [
When transfering the models to USA and Brazil networks, EGI further achieves the best performance compared with all baselines when structure relevant features are used (64.55 and 73.15), which reflects the most significant positive transfer. Interestingly, direct application of GVAE, DGI and MVC that do not capture the input k-hop graph jointly, leads to rather limited and even negative transferrability (through comparison against the untrained GIN encoders). The recently proposed transfer learning frameworks for GNN like MaskGNN and Structural Pre-train are able mitigate negative transfer to some extent, but their performances are still inferior to EGL. We believe this is because their models are prone to learn the graph-specific information that is less transferable across different graphs. GMI is also known to capture the graph structure and node features, so it achieves second best result comparing with EGI.
Similarly as in Table we also compute the structural differences among three networks w.r. the EGI gap in Eq. The structural difference is 0.869 between the Europe and USA networks, and 0.851 between the Europe and Brazil datasets, which are pretty close. Consequently, the transferability of EGI regarding its performance gain over the untrained GIN baseline is 4.8% on the USA network and 4.4% on the Brazil network, which are also close. Such observations again align well with our conclusion in Theorem 3.T that the transferability of EG1 is closely related the structural differences between source and target graphs.
Table 2: Results of role identification with direct- theecttrrnnteriing on the Airport dataset. We report mean and standard deviation over 100 runs. The scores marked with passed (-test with p 0.01 over the second runners.
Airport 45
Method
Europe
USA
Brazil
features
0.528=+0.052
0.557-+0.028
0.671=00089
GIN (random-init)
0.558:100050
0.616:10.030
0.700=10.082
GVAE (GIN)
28
0.539110.053
0.555110.029
0.663-10.089
DGI (GIN)
S44
0.578-10.050
0.549-10.028
0.673-10.084
Mask-GIN 21
0.564110.053
0.608110.027
0.667-0.073
ContextPred GIN 21
0.527
0.50440.030
0.621
Structural Pre-train train 23
0.560
0.62210.030
0.688+10.082
MVC 17
0.532+100500
0.59710.030
0.661
GMI
+0.04
0.593++0.031
0.731+0.107
EGI (GIN)
0.046"
0.646=0.029 *
0.732++0.078
On the Gene dataset, with more graphs available, we focus on EGI to further validate the utility of Eq. 5lin Theorem 3.1] regarding the connection between the EGI gap (Eq. 66) and the performance gap (micro-Fl) of EGI on them. Due severe label imbalance that removes the performance gaps, we only use the seven brain cancer networks that have more consistent balance of labels. As shown in Figure 3 we train EGI on one graph and test it on the other graphs. The z-axis shows the EGI gap, and y-axis shows the improvement on micro-F1 compared with an untrained GIN. The negative correlation between two quantities is obvious. Specifically, when the structural difference is smaller than 1, positive transfer is observed (upper left area) as the performance of transferred EGI is better than untrained GIN, and when the structural difference becomes large (> 1), negative transfer is observed. We also notice a similar graph pattern, i.e. single dense cluster, between source graph and positive transferred target graph Gg.
4.2 Few-shot learning on relation prediction
Here we evaluate EGI in the more generalized and practical setting of few-shot learning on the less cruuture-relevann task of relation prediction, with task-specific node features and fine-tuning. The source graph contains a cleaned full dump of 579K entities from YAGO [49), and we investigate 20- shot relation prediction on a target graph with 24 relation types, which is a sub-graph of 115K entities sampled from the same dump. In post-fine-tuming the models are pre-trained with an unsupervised loss on the source graph and fine-tuned with the task-specific loss on the target graph. In joint-fine- tuning, the same pre-trained models are jointly optimized w.E.t the unsupervised pre-training loss

---

G.
0.05
.Gi
-0.05
Mirca
-0.10
.Gs
0.90
structrrll difference (proposec)
0.95
1.00
1.05
1.10
source graph
G4, 1.084
G2, d= 0.957
Figure Transfer learning performance of role identification on the Gene dataset. We visualize the source graph Go and two example target graphs that are relatively more different (Ga) or similar (G2) with Go.
and task-specific fine-tuning loss on the target graph. In Table 3 we observe most of the existing models fail to transfer across pre-training and fine-tuning tasks, especially in the joint-finettminng setting. In particular, both MIN and ContextPreed-e while EGI focuses the capturing of similar ego-graph structures that transferable across graphs. The mutual information based method GMI also demonstrates considerable transferability and we believe the ability capture the graph structure the key to the transferability. As consequence, EGr significantly outperforms all compared methods in both settings. More detailed statistics and running time are in Appendix
rely lot on task-specific fine-tuning,
Table 3: Performance of few-shot relation prediction on YAGO. The scores marked with ** passed I-test with
< 0.01 over the second best results.
post-fin-tuning AUROC
joint-fine-tuning
Method
MRR
AUROC
MRR
No pre-train
0.687+0.002
0.596+0.003
N.A.
N.A.
GVAE
0.701
0.601
0.679+0.004
0.568+0.008
DGI
0.68
0.586=+0.025
0.688
0.537=0.023
MaskGNN
0.71310.009
0..015
0.712.10.055
0.560-10.010
Contex(PredGNN
0.692-10.030
0.662.10.030
0.705
0.57510.0021
GMI
0.028
0.625
0.721100007
0.643
Structural Pre-train
OOM
OOM
OOM
OOM
MVC
OOM
OOM
OOM
OOM
EGI
0.739 0.009
0.670=0.014
0.787 0.011
0.729 + 0.016
5
Conclusion
To the best of our knowledge, this is the first research effort towards establishing theoretically grounded framework to analyze GNN transfcrability, which we also demonstrate to be practically useful for guiding the design and conduct of transfer learning with GNNs. For future work, it is intriguing to further strengthen the bound with relaxed assumptions, rigorously extend it to the more complicated and less restricted settings regarding node features and downstream tasks, well as analyze and improve the proposed framework over more transfer learning scenarios and datasets. is also important to protect the privacy of pre-training data avoid potential negative societal impacts.
Acknowledgments and Disclosure of Funding
Research was supported in part by US DARPA KAIROS Program No. FA8750-19-2-11 SocialSim Program No. 1991NNF17---0009 and INCAS Program No. HRO01 12IC0165, National Science Foundation IIS-19-56151, 115-17-4,317, and IIS 17-04532, and the Molecule Maker Lab Institute: An AI Research Institutes program supported by NSF under Award No. 2019897. Chao Zhang is supported NSF IIS 2008334, IIS-2106961, and ONR MURI N00014- 100014-1--1-2655- We would like to thank AWS Machine Learning Research Awards program for providing computational resources for experiments in this paper. This work is also partially supported by internal funding and GPU servers provided by the Computer Science Department of Emory University. Any opinions, findings, and conclusions or recommendations expressed herein are those the authors and do not necessarily represent the views, either expressed or implied, of DARPA the U.S. Government.
10

---

References
[1] Réka Albert and Alsert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[2] Sanjeev Arora, Elad Hazan, and Satyen Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In FOCS, pages 339-348, 2005.
[3] Jinheon Baek, Dong Bok Lee, and Sung Ju Hwang. Learning to extrapolate knowledge: Transductive few-shot out-of-graph link prediction. Advances in Neural Information Processing Systems, 33, 2020.
[4] Lu Bai and Edwin R Hancock. Fast depth-based subgraph kernels for unattributed graphs. Pattern Recognition, 50:233-2455 2016.
[5] Ólbert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509. 512, 1999.
[6] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, pages 585-591, 2002.
[7] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In NIPS, pages 137-144, 2007.
[8] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O' O'Bray, and Bastian Rieck. Graph kernels: State-of-the arrt and future challenges. arXiv preprint arXiv:201 1.03554 2020.
[9] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[10] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
[11] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[12] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NIPS, pages 3844-3852, 2016.
[13] Jacob Devlin, Ming-Wei deep bidircctional transformers for language understanding. In ACL, pages 4171-4186, 2019,
Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of
[14] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pages 855-864 2016.
[15] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1024-1034, 2017.
[16) David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. ACHA, 30(2): 2011.
[17] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 41 16-41126. PMLR, 2020.
[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[19] Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction mining in large graphs. In KDD, pages 1231-1239, 2012.
[20] Devon Hjelm, Alex Fedorov, Samuel Marchilnn,, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In /CLRR 2019.
[21] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zimik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICIR, 2019.
[22] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In KDD, pages 1857-1867, 2020.
[23] Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. arXiv preprint arXiv:
2019.
11

---

[24] Suk-Geun Hwang. Cauchy's interlace theorem for eigenvalues of hermitian matrices. The American Mathematical Monthly, 111(2):157-199, 2004.
[25] Xuan Kan, Hejie Cui, and Carl Yang. Zero-shot scene graph relation prediction through commonsense knowledge integration. In ECML-PKDD, 2021.
[26] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In NIPS, pages 7090-7099, 2019.
[27] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv:1412.6900 69800, 2014.
[28] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint
1rXiv.6611.07388, 2016.
[29] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional
networks. In ICLR, 2017.
[30] Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
[31] Lin Lan, Pinghui Wang, Xuefeng Du, Kaikai Song, Jing Tao, and Xiaohong Guan. Node classification on graphs with few-shot novel labels via meta transformed network embedding. Advances in Neural Information Processing Systems, 33, 2020.
[32] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery data mining, pages 177-187, 2005.
[33] Ron Levie, Wei Huang, Lorenzo Bucci, Michael M Bronstein, and Gitta Kutyniok. Trans- ferability of spectral graph convolutional neural networks. arXiv preprinl arXiv: 1rXiv:1907.12972 2019.
[34] Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. In 2019 13th International conference on Sampling Theory and Applications (Samp'TA), pages 1-5. IEEE, 2019.
[35] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems, pages 13556-13566, 2019.
[36] Miller McPherson, Lynn Smith-Lovin and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, (71))415-444, 2001.
[37] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations words and phrases and their compositionality. arXiv preprint arXiv: 13 131.4444 10.456, 2013.
[38] Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. arXiv preprint arXiv: 122 2019.
[39] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
[40] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[41] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW, pages 259 200,270,22 2020.
[42] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD, pages 701-710, 2014.
[43] 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 KDD, pages
2020. [44] Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. In ICLR, 2017.
[45] Leonardo Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In KDD, pages 385-394, 2017.
12

---

[46] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323 2326, 2000.
[47] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
[48] Yu Shi, Qi Zhu, Fang Guo, Chao Zhang, and Jiawei Han. Easing embedding learning by comprehensive transcription of heterogeneous information networks. Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2190-2199, 2018.
[49] Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: a core of semantic knowl- edge. In WWW, pages 697-706, 2007.
[50] Fan- Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICI.R 2019.
[51] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In WWW, pages 1067-1077, 2015.
[52] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319-2222 2000.
[53] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[54] Petar Velickovic, William Fedus, William L Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm, Deep graph infomax. In ICLR, 2019.
[55] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In KDD, 2019.
[56] Oriol Vinyals, Charles Blundell, Tim Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In NIPS, pages 3630-3638, 2016.
[57] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11: 11:1201-1242, 2010.
[58] Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to canonical form and an Informatsia, 2(9): 1968. [59] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu, Unsupervised domain adaptive graph convolutional networks. In WWW, pages 1457-1467, 2020.
algebra arising during this reduction.
[60] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[61] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: 2014.
[62] Carl Yang, Yichen Feng, Pan Li, Yu Shi, and Jiawei Han. Meta-graph based hin spectral embedding: Methods, analyses, and insights. In ICDM, 2018
[63] Carl Yang, Aditya Pal, Andrew Zhai, Nikil Pancha, Jiawei Han, Chuck Rosenberg, and Jure Leskovec. Multisage: Empowering graphsage with contextualized multi-embedding on web- scale multipartite networks. KDD, 2020.
[64] Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network representation learning: A unified framework with survey and benchmark. In TKDE, 2020.
[65] Carl Yang, Chao Zhang, Xuewen Chen, Jieping Ye, and Jiawei Han. Did you enjoy the ride? understanding passenger experience via heterogeneous network embedding. In ICDE, 2018.
[66] Carl Yang, Jieyu Zhang, and Jiawei Han. Co-embedding network nodes and hierarchical labels with taxonomy based generative adversarial nets. In ICDM, 2020.
[67] Carl Yang. Jieyu Zhang, Haonan Wang, Sha Li, Myungwan Kim, Matt Walker, Yiou Xiao, and Jiawei Han. Relation learning on social networks with multi-modal graph edge variational autoencoders. In WSDM, 2020.
[68] Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NIPS, pages 1338- 1349, 2019.
13

---

[69] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NIPS, 2018.
[70] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference Machine Learning, pages 5708-5717. PMLR, 2018
14


Reviews:
[{"review_id": "oezABBsYczU", "reviewer": "Reviewer_RQmo", "summary": "This work aims to provide fundamental understanding towards the mechanism and transferability of GNNs, and develops an unsupervised GNN training objective based on their understanding. Novel theoretical analysis has been done to support the design of EGI and establish its transferability bound, while the effectiveness of EGI and the utility of the transferability bound are verified by extensive experiments. The whole story looks new, comprehensive and convincing to me.", "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": "Most arguments made and techniques developed in this work are well-supported by solid and detailed theoretical analysis. However, I do find a few limitations of this work. For example, (1) its focus on “structure-respecting features” might lead to the exclusion of its usage in many real-world networks where node features are more noisy and even not “structure-respecting”; (2) its study of transferability under the “direct-transfer” setting might be less useful when in real-world, most transfer learning is done with fine-tuning. Nonetheless, I understand the necessarily existing gap between theory and practice in many machine learning problems, and I appreciate the authors in making their assumptions clear and also conducting empirical analysis to show the generalizability of their model and theory over the scenarios where the assumptions are less valid.\n\nThe paper is overall well-organized, and I like the intermediate “supportive observations” in the technical section which help the understanding and verification of the technical contributions. In terms of writing, the introduction is very clear, while some details in the technical section require some back-and-forth reading. Further polishing over that section would benefit the overall readability.\n\nTo the best of my knowledge, this paper is the first one that provides a well-balanced blend of theory and empirical studies aiming to demystify the transfer learning with GNNs. Although its current scope is a bit limited, I think it is a necessary and good start for future research in this important direction.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "ZVPae0xQuWU", "reviewer": "Reviewer_2Ymd", "summary": "This paper develops a novel measure for assessing the transferability of\ngraph neural network models to new data sets. The measure is based on\na decomposition of graphs into 'ego networks' (essentially,\na distribution of $k$-hop subgraph, extracted from a given larger\ngraph). Transferability is then assessed by means of a spectral\ncriterion using the graph Laplacian. Experiments demonstrate the utility\nin assessing transferability in such a manner, as the new measure\nappears to be aligned with improvements in predictive performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 Review\n\nThis paper discusses a timely and highly relevant topic. Understanding\n*a priori* how a graph neural network will be able to perform on unseen\ndata is an excellent research objective; addressing this problem is\nbound to lead to better models, and might even make 'pre-trained model\nmarkets' more attractive for GNNs.\n\nWhile I overall feel favourably about the paper, there are several\nissues that need to be addressed before endorsing it for publication.\nThese comprise:\n\n1. Unclear limitations or properties of the developed measure: \n\n  - The main text is currently not discussing how choices of $k$\n    affect the calculation. If I understood everything correctly, $k\n    = 2$ is set for all experiments; a more thorough analysis of\n    different values of $k$ is necessary. It is clear that higher values\n    of $k$ will not be beneficial with respect to computational\n    performance, but their impact still needs to be assessed. I would be\n    interested in learning to what extent transferability becomes more\n    'precise' or more 'predictive' by these changes.\n\n  - To what extent is the $\\Delta_{\\mathcal{D}}$ dependent on\n    the ordering of input nodes? The way I understand Equation 6 is that\n    two normalised graph Laplacians (which are of the same size because\n    the same value for $k$ is being used throughout the paper) are\n    subtracted from each other. However, this presupposes that the\n    ordering of nodes is known in advance, which I do not think is the\n    case here. This aspect needs to be discussed. (there is a brief\n    discussion on edge ordering, following Eq. 1; if this applies here\n    as well, I would suggest to mention it explicitly)\n\n  - How is EGI used in practice? Do I understand this correctly that\n    it is being employed as an additional loss term? Figure 2 seems to\n    suggest at first that the primary purpose is to assess how well\n    a model could be transferred, but the experiments later on seem to\n    indicate that EGI is used *during* training. Please clarify this!\n    (an alternative use case, discussed in l. 237-- could involve\n    picking the best graphs as a training data set; this would be a more\n    'static' use of the measure, so please comment on the exact details\n    here)\n\n2. Missing clarity, for instance when it comes to defining what the\n   method is supposed to capture. The paper uses the term 'graph\n   structures,' but seems to equate this with $k$-hop graphs. Upon\n   re-reading the paper, I find that a more appropriate description\n   would be that similarity of graph Laplacians is supposed to be\n   captured (with the caveat about the dependence on a fixed ordering\n   that I listed above).\n\n3. The experimental setup could be improved: please report mean accuracy\n   and standard deviations over multiple runs. This would help in\n   assessing the proposed method.\n\n## Comments on clarity\n\n- Why does Definition 3.1 make use of a *directed* distance formulation\n  between graph nodes? The remainder of the paper appears to discuss\n  only the undirected case.\n\n- Why is the second input to $\\mathrm{sp}(\\cdot)$ negated in Equation 1?\n  The function $\\mathcal{D}$ returns a probability, right?\n\n- Why are self-loops required or included here? (l. 143)\n\n- Please provide more details about the arguments $h_p$, $x_q$, and\n  $z_i$ shown in Eq. 2. I find the expression hard to read at present.\n\n- Definition 3.3 appears to state that structure-respecting node\n  features are those features that are function of the $k$-hop graphs.\n  Is this correct? If so, please provide this intuition in the\n  definition; I found it confusing at first.\n\n- What does it mean to be 'injective to the graph structures'? I can\n  guess at the intent, namely that $f$ should map different $k$-hop\n  graphs to different representations/features. Is this correct?\n\n- I would not use the term 'organic node attributes' but rather discuss\n  that certain graphs might already be equipped with node attributes.\n\n- In l. 226--, a brief depiction of such graphs in the main text would\n  be useful to make the paper more accessible to readers.\n\n- Please also discuss the stability of your measure and method with\n  respect to random samples. I found the section starting in l. 247\n  very interesting; the statements made in it should also be empirically\n  evaluated.\n\n- When displaying results, such as in Table 1, consider sorting columns\n  differently. I would find it more intuitive to *first* see the\n  'original' accuracy obtained on the 'source' data set, whereas the\n  *second* column could depict the 'target' data set.\n\n- For Table 2, is 'EGI' also using a GIN architecture or a GCN? Please\n  mention the architecture directly in the 'Method' column.\n\n- Please provide more details on data set features in Table 2.\n\n## Minor Comments\n\n- I disagree with the in the related work that 'GNNs are not very\n  complicated.' Maybe the convolutional layer can be seen as\n  a comparatively simple construction, but I would rephrase or tone down\n  this section slightly.\n\n- For the discussion of graph kernels, the author may want to consider\n  citing one of the recent surveys in this area, such as 'Graph Kernels:\n  State-of-the-Art and Future Challenges ' by Borgwardt et al., 'A\n  Survey on Graph Kernels' by Kriege et al., or 'Graph Kernels:\n  A Survey' by Nikolentzos et al.\n\n## Style & language\n\nThe language in this paper requires some improvements. I had trouble\nunderstanding certain constructions, and I would suggest to rewrite them\nin order to improve the accessibility of the paper. Here are some\nsuggestions:\n\n- As an overall suggestion, I would like to point out that bibliographic\n  citations can be sorted using the `sort` option of the `natbib`\n  package, for instance. I find that this makes parsing citations\n  a little bit easier.\n\n- 'on the' appears twice in the caption of Figure 1\n\n- 'its capability' --> 'their capability'\n\n- 'none of existing' --> 'none of the existing'\n\n- 'training objective is' --> 'training objectives are'\n\n- 'set of $k$-hop ego graph' --> 'set of $k$-hop ego graphs'\n\n- 'drawn with the joint distribution' --> 'drawn from the joint distribution'\n\n- 'from empirical joint' --> 'drawn from an empirical joint'\n\n- 'we now describes' --> 'we now describe'\n\n- 'distinguish positive' --> 'distinguish a positive'\n\n- 'make node-wise characterization' --> 'obtain node-wise characterizations'\n\n- 'while also verify' --> 'while also verifying'\n\n- 'hyper parameter' --> 'hyperparameter'\n\n- 'apply them on' --> 'apply them to'\n\n- 'parameters are freezing' --> 'parameters are frozen'\n\n- 'are prune' --> 'are prone'\n\n- 'structural different' --> 'structural differences'\n\n- 'that vanishes the performance gaps' --> 'that removes [...]'\n\n# Update after rebuttal\n\nThe authors provided numerous clarifications, which helped alleviate some of my initial concerns. I am therefore happy to raise my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Algorithmic limitations are partially discussed in this paper, but as\noutlined above, an ablation study of the effects of changing parameters\nand/or sampling frequency is crucial and needs to be included. In\naddition, 'failure cases' of the algorithm would also be interesting to\ndiscuss; are there specific graphs that turn out be easily transferable\nbut the framework is unable to assess this a priori?\n\nThere are no specific adverse societal impacts arising from this work.\nThe paper briefly mentions privacy aspects in pre-training data, but\nthis thought could be fleshed out more.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "X4A5OmFj7kh", "reviewer": "Reviewer_5DSQ", "summary": "This paper proposes a novel graph transfer learning framework with theoretical guarantees. Theoretical analysis is supported by both synthetic and real-world experiments.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The work is moderately original with ego-graph information maximization scheme. \n\nQuality: The transferability analysis seems theoretically sound and solid with improved transferability bounds. Experiments are carried out based on real-world datasets. I do not see any major issues with this work.\n\nClarity: The paper is well-organized overall. For clarity, I have some small concerns: In line 226, there is no reference to $\\bar d$ columns. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OhACuj6p5jL", "reviewer": "Reviewer_7fvg", "summary": "The paper establishes a theoretically grounded and practically useful framework for transfer learning of GNNs.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work seems complete, with both theoretical guidance and promising experimental results. The main drawback is that it is densely written (unclear in some parts) and difficult to follow. The authors are strongly encouraged to improve the readability of the paper, especially the methodology part. I have a few comments and questions.\n\n - Why does the computation of $\\mathcal{D}$ on $E(g_i)$ depend on the edge orders (line 139)? According to Eq.3, the summation over edges does not seem to depend on edge orders.\n - What is the exact definition of the discriminator $\\mathcal{D}$? It seems that both $f$ and $\\Phi$ are a part of $\\mathcal{D}$, but how are they combined together to form $\\mathcal{D}$?\n - The topic is about transfer learning, but I cannot figure out how the model transfers from the source graph $G_a$ to the target graph $G_b$. It should be presented between Line 154 and 155.\n - Calling $\\Phi$ decoder is confusing. The input of $\\Phi$ is not the output of the encoder $\\Psi$, so they are not a pair of encoder and decoder, but rather both are encoders.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies, in the context of transfer learning, the extent to which trained graph neural networks can transfer to new data. Concretely, the authors derive criteria to asses the transferability of a based on ego-graph information (EGI) maximization. In initial reviews, most reviewers marked the paper above acceptance threshold, and following rebuttal and discussion we have reached a unanimous decision to recommend its acceptance. 

Some remarks have been raised (especially by one reviewer) regarding the clarity and quality of presentation, but in discussion a consensus has been reached that the revisions required to address these concerned can viably be regarded as only minor revisions that should not prevent the paper from being accepted, especially given the author responses that indicated they will revise the manuscript appropriately.

Therefore, I recommend this paper be accepted and reiterate to the authors to carefully go over the reviewer comments and follow up on the indicated or planned revisions from their responses.
Decision: Accept (Poster)