Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
Authors: Qi Zhu
Yidan Xu
Haonan Wang
Chao Zhang
Jiawei Han
Carl Yang
Venue:  (2021)
Keywords: Transfer learning
graph neural networks

Abstract: Graph neural networks (GNNs) have been shown with 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 the transferability of GNNs. 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, we specify the requirement of structure-respecting node features as the GNN input, and conduct a rigorous analysis of GNN transferability based on the difference between the local graph Laplacians of the source and target graphs. Finally, we conduct controlled synthetic experiments to directly justify our theoretical conclusions. Extensive experiments on real-world networks towards role identification show consistent results in the rigorously analyzed setting of direct-transfering (freezing parameters), while those towards large-scale relation prediction show promising results in the more generalized and practical setting of transfering with fine-tuning.

Under review as a conference paper at ICLR 2021
TRANSFER LEARNING OF GRAPH NEURAL NETWORKS WITH EGO-GRAPH INFORMATION MAXIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have been shown with 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, clear requirements and guarantees towards the transferability of GNNs. In this work, we establish 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 tego-graph information maximization) to analytically achieve this goal. Secondly, we specify the requirement of structure- respecting node features as the GNN input, and conduct a rigorous analysis of GNN transferability based on the difference between the local graph Laplacians of the source and target graphs, Finally, we conduct controlled synthetic experiments directly justify our theoretical conclusions. Extensive experiments on real- world networks towards role identification show consistent results in the rigorously analyzed setting of firect-transfering (freezing parameters), while those towards large-scale relation prediction show promising results in the more generalized and practical setting of transfering with fine-tuning.
INTRODUCTION
Graph neural networks (GNNs) have been intensively studied recently (Kipf & Welling 2017 Keriven
Peyré 2019 Chen et al. 2019 Oono & Suzuki 2020 Huang al. 2018), due to their established performance towards various real wolld tasks (Hamilton et al. 2017 Ying et al.] 201 8b; Velickovic
al.
2018), as well as close connections to spectral graph theory (Defferrard et al. [016]] Bruna
ett al. 2014 Hammond et al. 2011). While most GNN architectures are not very complicated, the training of GNNs can still costly regarding both memory and computation resources on real-world large-scale graphs (Chen al.) 2018 Ying et al., [018a). Moreover, it is intriguing to transfer learned structural information across different graphs and even domains in settings like few-shot learning (Vinyals al. 2016 Finn et al. 2017 Ravi & Larochelle 2017). Therefore, several very recent studies have been conducted on the transterability of GNNs, which focus on the setting of pre-training plus fine-tuning (Hu et al. 2019a b 2020 Wu al. 2020). 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 on 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" (Ben-David David et al. 2007).
In this work, we establish a theoretically grounded framework for the transfer learning of GNNs, and leverage it to design a practically transferable GNN model. Figure [ gives an overview of our framework. It is based on a novel view of graph as samples from the joint distribution of its k-hop ego-graph structures and node features, which allows us to define graph information and similarity, so to analyze GNN transferability ($2). This view motivates us to design EGI, novel GNN model based on ego-graph information maximization, which is effective in capturing the graph information as we define (22.1). Then further specify the requirement analyze the transferability of EGI that is dependent on the local graph Laplacians of source and target graphs ($2.)
transferable node features and

---

Under review as a conference paper at ICLR 2021
Source Go
Target G1
Target G2
top ego-graphs
ego-graph distribution
025
0.05
1.28
2.96
node features
node degree encading spectral embedding
degree encoding spectral embedding
random uniform variables graph-apectfi node attributes
EGI Training Transferable?
similar ego-graphs
dissimilarr ego-graphs x non-transferable features
transferable features
Figure Overview of our GNN transfer learning framework: (1) represent graph as combination of its 1 --hop ego-graph and node feature distributions; (2) we design transferable GNN regarding the capturing of such essential graph information; (3) we establish a rigorous guarantee of GNN transferability based on the requirement nodes features and difference between graph structures.
All of our theoretical conclusions have been directly validated through controlled synthetic experi- ments (Table D.. where we use stretural-equivalle role identification in analyze the impacts of different model designs, node features and source- target structure similarities on GNN transferability. In [ we conduct real-works experiments on multiple publicly available network datasets. On the Airport and Gene graphs ($3.1), we closely follow the settings of our synthetic experiments and observe consistent but more detailed results supporting the design of EGr and the utility of our theoretical analysis. On the YAGO graphs ($3.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-as GNN models and transfer learning frameworks with significant margins.
setting to
2 TRANSFERABLE GRAPH NEURAL NETWORKS
Based on the connection between GNN and spectral graph theory (Kipf Welling 2017), we describe the output of GNN combination of its input node features, fixed graph Laplacian and learnable graph filters. The goal of training a 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. argue that the general utility of GNN should be optimized and quantified w.z.. its ability of capturing the essential graph information in terms the joint distribution of its link structures and node features, which motivates to design novel ego-graph information maximization model (EGI) T.. 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 as using cenccuur-rrepecttngg node features as the GNN input, we analyze this gap for EGI based on the structural difference between two graphs w.e.t. their local graph Laplacians
2.1 TRANSFERABLE GNN VIA EGO-GRAPII INFORMATION MAXIMIZATION
this work, we focus on the direct- treecttrrnnfering setting where GNN pre-trained on a source graph G2 in unsupervised fashion and applied graph G = (V, E), where the set of nodes V are associated with certain features and the set of links E form certain structures. Intuitively, the transfer learning will be successful only if both the features and structures G, and G, are similar in some ways, so that the graph filters of a GNN learned on G, compatible with the features and structures of Gb,-
target graph Go without fine-tuning! Consider
In the experiments, show our model to be generalizable to the more practical settings with task-specific pre-training and fine-tuning, while the study of rigorous bound in such scenarios is left future work.
2

---

Under review as a conference paper at ICLR 2021
introduce novel view of a graph as samples from the joint distribution of its h-p ego-graph structures and node features. This view allows us give concrete definitions towards structural information of graphs in the transfer learning setting, which facilitates the measuring of similarity (difference) among graphs.
Motivated by the concept of k-layer expansion sub-graph in (Bai & Hancock 2016).
Definition 2.1 (K-hop ego-graph). We call a graph 9; = (V(g) ). E(ge)} a k-hop ego- 180-graph centered at oe if it has a k-layer centroid expansion (Bai & Hancock 2016) such that the greatest shortest path rooted from U/ has length k, i.e., k = maX (5(1) b,)l. where S(v,, U2) is the shortest path between U, and Vj.
For an ordered k-hop ego-graph, we denote Up.g as the q-th node in the p-th layer of the ego-graph (i.e., (U, pp.4)l = p), where = 0, Q.....,, k, and eve as the edge between Up.g and Up+1. Definition 2.2 (Structural information). Let & be a topological space of sub-graphs (Verma & Zhang 2019 We view graph G samples of k-hop ego-graphs G {g drawn i..d. from 9 with probability i.e. 9s " μ y'ii = 1,... .... combination of the distribution μ and the set of spectrum of {g:)1=r
The structural information of G is then defined to be the
The structural information of a graph can be characterized by fgihn.y and its empirical distri- bution, where each 9: is a k-hop ego-graph of G centered at node U, with V(a.) = {u E V(G) S(u, v:) S k), and edges F(gg:) = {ewe F(GG) u, v E V(g.)). As shown Figure [ three graphs Go. G1 and G2 are characterized by set of 1 1-hop ego-graphs and their empirical distributions, which allows us to quantify the structural similarity among graphs as shown in 2.2 Go is more similar to G1 than G2 under such characterization).
In practice, the nodes a 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 {99, xx)]" E G X, drawn with the joint distribution p on the product space of G and a node feature space X. To capture such joint distributions of structural information and node features, we design ego-graph information maximization (EGI), which recursively reconstructs the k-hop ego-graph of each node based on their features in unsupervised fashion.
Ego-Graph Information Maximization. Assume we are given a of ego-graphs ((g,, 3..) )2 with empirical joint distribution I.. Similarly with the "local" version of DIM (Hjelm et al. 2019). we define Uwig..z) as the empirical distribution of the embedding produced by the GNN encoder W for the the center node eú of ego-graph 9t- Unlike DGI (Velickovic et al., 2019) that models the local-global mutual information (MI), EGI optimizes to maximize the MI of I(g., (g 2;)).
which is directly between the structural input and output of GNN, with a focus on the structural information gi- Specifically, we use the Jensen-Shanne MI estimator in (Hjelm al., 2019).
Lga: =- - (G, v) Exxt (sp (TD, (g., (g((. - (-spp--ppp (9t, (g) 27 ())) (1)
TD D (g:, (( ::)), where D is a discriminator D gi x (g;, + R+ In Eq. during the training of DD the input space of is at least as large as the number of graph permutations (V)))... Instead of enumerating all possible graphs g/c we fix 9i and sample GNN's output V/ (g x4)
from the marginal distribution U by uniformly sampling (g/, x/) P.P. P.. The correspondence between sampling (g/, x P and gf is discussed in Remark 2 when node features are strcuture-respecting (Def. 2.3
Formally, we characterize the decision process of D with a fixed graph ordering, i.e., BFS-ordering i over edges Egg)). D is GNN scoring function over an edge sequence E" fee, e2, ), which makes predictions on BFS-ordered edges. Let 2, = (g.. 2.). then we have,
k [V(a)ll
D(g;, 21) = ΣΣ Σ
log D(cau | p.g- p. 21),
(2)
p=0
q=1
where h is the hidden representation output by D, Cav E F((g)) is an edge between node i in layer p and in layer p- 1, following the notation defined below Def 2.1 More specifically, we have
D(eav
16 g 2i " 21) =a (UT T (W7 [hg or (z:1))
(3)
where a and are Sigmoid and ReLU activation functions, respectively. Thus, the discriminator is asked to distinguish positive (Ea., (g 2x)) and negative pair (env. V (g a()) that consists of an observed edge and positive/negative center node embeddings vi()).
3

---

Under review as a conference paper at ICLR 2021
Due to the fact that the output of k-layer GNN only depends k-hop ego-graphs, EGI can be trained in parallel by sampling batches of 9: 's. Besides, the training objective of EGI is transferable as long (g;, 2;) across source graph G, and G2 satisfies the conditions given in $2.2 More details about the model are in Appendix ş and source code in 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 of ego-graph mutual information [gg, (gg, x.)). It can be related to an ego-graph reconstruction loss R[gd L (gi, zr:) as
(4) When EGI is maximizing the mutual information, it simultaneously minimizes the upper error bound of reconstructing an ego-graph Js- In this view, the key difference between EGI and GVAE (Kipf & WWlling 2016) is they assume each edge in a graph to be observed independently during the reconstruction, while we assume the edges an ego-graph to be observed jointly. Moreover, existing mutual information based GNNs such as DGI (Velickovic et al.] 2019) and GMI (Peng et al. 2020) explicitly measure the mutual information between node features a 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 22.2
max L(g. L ((11.z)) = H (g:) H (g: (. x;)) I ( - [gg M ((g...:))
Supportive observations. In the first three columns of Table in both cases of transfering GNNs between similar graphs (F-F) and dissimilar graphs (B-F), EGI significantly outperforms all com- petitors when using node degree one-hot encoding as transferable node features. In particular, the performance gains over the untrained GIN and GCN show the effectiveness of training and transfering, and our gains are always larger than the two stateoof-the-ar unsupervised GNNs. Such results clearly indicate advantageous structure preserving capability and transferability of EGI.
2.2 TRANSFERABILIT ANALYSI BASED ON LOCAL GRAPHI LAPLACIANS
We now study the transferability of GNN (in particular, EGI) between the source graph G2 and target graph G, based on the graph similarity between G. and Gg. We firstly establish the requirement towards node features, under which we then focus on analyzing the transferability of EGI w.r.1. the structural information of G. and Gb-
Recall our view of the GNN output as a 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 to be structure- respecttnn: Definition 2.3 (Structure- respeectigg node features). Let g, be an ordered ego- centered on node with a set of node features {= [.VVV(99)) where Vp(gs) is the set of nodes in p-th hop of g-- Then we say the node features on gi are structure-respecting if spp.g = [f(g))l. Id for any node Vg E Vg(g)), where f: G > [X.) is a function. In the strict case, I should be injective.
In its essence, Def 2.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. 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 I this requirement also essential for the analysis of our GNN transferability which eventually only depends on the structural difference between two graphs.
In practice, commonly used node features like node degrees, PageRank scores (Page al., 1999). spectral embeddings (Chung & Graham, 1997). and many pre-computed unsupervised network embeddings (Perozzi et al., [ Tang et al., 2013) Grover & Leskovec 2016) are all structure- respecting in nature. However, other commonly used node features like random vectors (Yang et al.) 2019) or uniform vectors (Xu et al., (219) are not and thus non-transferable. When organic node attributes are available, they are transferable long the concept of homophily (McPherson et al., 2001) applies, which also implies Def 2.3 but we do not have a rigorous analysis on it yet.
Supportive observations. In the fifth and sixth columns in Table where we use uniform embedding non-trans con-transferable node features to contrast with the first three columns, there is almost negative transferability for all compared methods when non non-transferable features are used, as the performance of trained GNNs are similar or worse than their untrained baselines.
even
4

---

Under review as a conference paper at ICLR 2021
With our view of graphs and requirement node features both established, now derive the following theorem by characterizing the performance difference of EGI on two graphs based on Eq [
Theorem 2.1 (GNN transferabilityy. Let G. = [( x,) and Go = {(gr, Ie' ) be two graphs. Then denote Lg. the (normalised) graph Laplacian of g, vi =,=1... 1. features of gi be crructure-respectiee and normalized (similarly for ge). Consider GNN Vo with k layers and l-hop polynomial filter do- With reasonable assumptions on the local spectrum of Go and Go, the empirical performance difference of U with dg evaluated on LEGI satisfies
and let the node
T T DY TIm
[CEa (Caa)GGa) LGaI SO
M
ΣE
IM(L.)) - X(Egg))l2)
(5)
where M is a constant dependant on k, Φg. g. {hggh, b. {zih. J. {oe}. and finally M(Lg,) denotes the ordered eigenvalues of the graph Laplacian of g: E Ga (similarly for gv).
Proof. The full proof is detailed in Appendix A
Remark 1. Our view of a graph G as samples of k-hop ego- pro-graphs is important, as it allows us to make node-wise characterization of GNN similarly as in \Verma & Zhang] 2019). It also allows 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 2. For Eq. D Dejl 2.3 ensures the sampling of GNN embedding
node always corresponds
to sampling an ego-graph from G. which reduces to uniformly sampling from G = {9:) i= under the setting of Theorem 2.7 Therefore, the requirement of 2.f in the context of Theorem 2.1 guarantees the analysis to be only depending on the structural information of the graph.
The analysis in Theorem 2.1 naturally instantiates our insight about the correspondence between structural similarity and GNN transferability. It tells how well a GNN trained on G. can work on Go by only checking the local graph Laplacians of G. and G. without actually training the model.
In practice, the computation of eigenvalues the small ego-graphs be rather efficient (Arora iet al. 2005). and we do not need to enumerate all pairs of ego-graphs. Suppose we need to sample M pairs of k-hop ego-graphs compare two large graphs, and the average size of ego-graphs are L, then the overall complexity of computing Eq. 5 O(ML?), where M is often less than 1K and L. less than 50.
Supportive observations. Table 1 in the d columns, we compute the average structural difference between two Forest-fire graphs (d(F, F)) and between Barabasi and Forest-fire graphs (d((B, B, F)), based on the RHS of Eq. 5 The results validate our usage of the two graph models to generate structurally different graphs, while also verify our novel view of graphs and the way we propose based on it to characterize structural information of graphs. We further highlight in the Á columns the performance difference between the GNNs transfered from Forest fire graphs and Barabasi graphs to Forest-fire fire graphs. Since Forest-fire graphs are more similar to Forest-fire graphs than Barabasi graphs (as verified in the d columns), we expect A 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 eellesndertoo transferability and the utility of our theoretical analysis.
Table 1: Synthetic experiments of identifying structural equivalent nodes. We randomly generate 40 graphs with the forest-fire model (F) (Leskovec et al. 2005) and 40 graphs with the Barabasi model (B) (Albert & Barabási 2002). The GNN models we use include the untrained encoders of GCN (Kipf & Welling 2017) and
GIN (Xu et al. 2019) with random parameters (baselines with only the neighborhood aggregation function),
GVAE with GCN encoder (Kipf & Welling 2016). DGI with GIN encoder (Velickovic el al. 2019). and BGI
with GIN encoder. We train GVAE, DGI and EGI on one graph from either set (F and B), and test them on the
rest of Forest-fine fire graphs (F). More details about the results and dataset can be found in Appendix C
transferable features
non-transferable feature
structural difference d(F.F)
Method
F-F
B-F
A
F-F
B-F
A
d(B.F)
GCN (untrained)
0.478
0.478
/ 0.229
0.229
/
GIN (untrained)
0.572
0.572
/ 0.358
0.358
GVAE (GCN)
0.498
0.432
+0.066
0.240
0.239
0.001
1.78
2.17
DGI (GIN)
0.578
0,591
-0.013
0.394
0.213
+0.181
EGI (GIN)
0.710
0.616
+0.094
0.376
0.346
+0.03
5

---

Under review as a conference paper at ICLR 2021
3 REAL DATA EXPERIMENTS
We compare the proposed model with existing unsupervised GNNs and pre-training GNN frameworks. The unsupervised GNNs are the same used in our synthetic experiments, i.c. GVAE with GCN encoder (Kipf & Welling 2016) and DGI with GIN encoder (Velickovic et al. 2019). The pre-training GNN frameworks inc include Mask-GIN and Contex(Pred-GII two nove-level pre-training models proposed in (Hu et al. 2019a Besides, Structural Pre-train (Hu et al. 2019b) also conducts unsupervised node-level pre pre-tratne training with structural features like node degrees and clustering coefficients.
Baselines.
Protocols. 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 on target graphs are unspecified but assumed to be structurr-relevant, and thus pre-train the GNNs on source graphs in an unsupervised fashion." 3 In terms of evaluation, we design two realistic experimental settings: (1) Direct-tramm transfering on the more ceuuttre-relevasee 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 task-specific node features to evaluate the generalization ability of EGI.
3.1 TRANSFERRANN ON ROLE IDENTIFICATION
First, we use the role identification without node features in a dürect-transfering setting as a reliable proxy to evaluate transfer learning performance regarding different pre-training objectives. Role in a network is defined as nodes with similar structural behaviors, such as clique members, hub and bridge (Henderson al. 2012). 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 2. Upon convergence of pre-trainin training each model on the source graphs, we directly apply them on the target graphs and further train a multi-layer perceptron (MLP) upon their outputs. The GNN parameters are freezing during the MLP training. We refer to this strategy as direct-transfericn since there is no fine-tuning of the models after transfering to the target graphs.
We use two worl-world network datasets with role-based node labels: (1) Airport (Ribeiro et al. 2017) contains three networks from different regions- Brazil, USA and Europe. Each node is an airport and each link is the flight between airports. The airports are assigned with external labels based on their level of popularity. (2) Gene (Yang et al. 2019) contains the gene interactions regarding 50 different cancers. Each gene has a binary label indicating whether it is transcription factor.
The experimental sctup 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- airport role labels are highly relevant node degrees. The untrained GIN encoder yields a significant margin over both node degrees and the untrained vanilla GCN encoder, indicating the importance of proper aggregation mechanisms. While training of the GCN (through GVAE) and GIN (through DGI) can further improve the performance on the source graph, EGI shows the best performance there with the respectin node degree features (59.15), corroborating the claimed effectiveness of EGI in capturing the essential graph information we stress in $2
When transfering the models to USA and Brazil networks, EGI further achieves the best performance
compared with all baselines when node degree features are used (64.55 and 73. 15), which reflects the most significant positive transfer. Interestingly, direct application of GVAE and DGI without the consideration of essential graph information transferrability (through comparison against the untrained GCN and GIN encoders). The recently
stress leads to rather limited and even negative
We are exploring graph-level tasks and but focusing on transfer knowledge hetween two graphs. Thus, we drop the graph-level pre-training tasks the paper since is not applicable to our setting. "hhe downstream tasks are unspecified hecause we aim to study the general transferahility of GNNs that is not bounded specific tasks. Nevertheless, we assume the tasks to be relevant graph structures.
6

---

Under review as a conference paper at ICLR 2021
performance loss
G:
G:
G+
G1
G5
structural difference
5.0
6.2
source graph
Gs, d 4.788
Ge, d 6.114
Figure 2: Role identification on the Gene dataset. Due severe label imbalance that vanishes the performance gaps, we only use the 7 brain cancer networks that have more consistent balance labels. We visualize source graph Go and two example target graphs that are relatively more similar (Gş) and different (G&) with Go-
proposed transfer learning frameworks for GNN like Mask-GIN and Structural Pre-train are able to mitigate negative transfer to some extent, but their performances still inferior EGI. We believe this is because their models do not aim to capture the underlying ego-graph distributions as we deem important, so they are prune learn the graph-specific information that is less transferable across we also compute the structural difference among three networks w.t.f to RHS of Eq. 5 The structural difference is 12.03 between the Europe and USA networks, and 12.14 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 pretty close. Such observations once again align well with our conclusion in Theorem 2.1 that the transfcrability of EGI is closely related to the structural different between source and target graphs.
different graphs. Similarly as in Table [
Table 2: Results of role identification with direct-transferic transfeignn the Airport dataset. The performance reported
(%) are the average over 100 runs. The scores marked with passed t-test with p < 0.01 over the second best
results. More details about the results and dataset can found in Appendix CC.2
Europe (source) node degree
USA (target)
Brazil (target)
Method
uniform
node degrree
uniform
node degree
uniform
MLP
52.81
20.39
55.67
20.22
67.11
19.63
GCN (untrained)
52.96
20.11
55.30
22.07
68.30
17.63
GIN (untrained)
55.75
53.88
61.56
58.32
70.04
70.37
GVAE (GCN) (Kipf & Welling
2016
53.90
21.12
55.51
22.39
66.33
17.70
DGI (GIN) (eeickovic al. 2019
57.75
23.13
$4.90
21.76
67.93
18.78
Mask-GIN (Tu el
2019
56.37
55.53
60.82
54,64
66.71
74.54
ContextPred-GIN (Hu ct al
2019a
52.69
49.95
50.38
54.75
62.11
70.66
Structural Pre-train (uu et al
2019b
56.00
53.83
62.17
$7.49
68.78
72.41
EGI (GIN)
59.15**
54.98
64.55
57.40
73.15*
70.00
On the Gene dataset, with more graphs available, we focus on EGI to further analyze the utility of Eq. 5jin Theorem 2.1 regarding the connection between the structural difference of two graphs and the performance gap of EGI on them. As shown in Figure 2 we train EGI on one graph and test on six different graphs. The a-axis shows the structural difference measured w.r.f. the RHS of Eq. 5 and y-axis shows the performance loss compared with an untrained GIN. The positive correlation between two quantities is obvious. Specifically, when the structural difference is small, positive transfer is observed as the performance of transfered EGI is better than untrained GIN, and when the structural difference becomes large, negative transfer is observed. Note that, at its current stage, Eq. in Theorem 5 mainly gives a relative indication on the transferability of EGI, because the absolute values of structural difference may vary a lot across different datasets.
3.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 structure-relevant 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 (Suchanek et al., (007). and we investigate 20-shot relation prediction on target graph with 24 relation types, which is a sub-graph of 115K entities sampled from the same dump. In post-fine-tuning, the models are pre-trained with unsupervised loss on the source graph and fine-tuned with the task-specific loss the same pre- pre-trained models are jointly optimized w.r.t. the
on the target graph. In foint-fine-tunitn unsupervised pre- traiiiinn loss 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-fine-laning setting. In particular, both Mask-GIl and ContextPred-CG rely
7

---

Under review as a conference paper at ICLR 2021
lot task- fine-tuning, while EGI focuses on the capturing of similar ego-graph structures that are transferable across graphs. As a consequence, EGI significantly outperforms all compared methods in both settings.
Table 3: Performance of few-shot relation prediction on YAGO. Structural Pre-train (Hu et al. 2019b can not
scale to the YAGO graphs with 100K+ nodes. More details can be found in Appendix C.3
post-finettuning MRR
joint-fine-tuning
Method
AUROC
AUROC
MRR
No pre-train
0.6866
0.5962
N.A.
N.A
GVAE Kipf & Welling 2016
0.7009
0.6009
0.6786
0.5676
DGI Velickovic al. 2019
0.6885
0.5861
0.6880
0.5366
Mask-GIN (Hu ct al. 2019a
0. 0.7041
0.6242
0.6720
0.5603
ContextPred-GIIN (uu ct al. 2019a
0.6882
0.6589
0.5293
0.3367
EGI
0.7389
0.6695
0.7870
0.7289
RELATED WORK
Representation learning graphs has been studied for decades, with earlier spectral- -bssdd methods (Belkin & Niyogi 2002 Roweis & Saul (2000) Tenenbaum et al. 2000 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 (Mikolov et al. 2013)
have replenished the field (Tang et al. 2015 Grover & Leskovee 2016 Perozzi et 2014: Ribeiro et al. 2017). Equipped with efficient structural sampling (random walk, neighborhood, etc.) and negative sampling schemes, these methods are easily parallelizable and scalable 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 to be transfered to unseen graphs.
More recently, researchers introduce the family of graph neural networks (GNNs) that are capable of inductive learning and generalizing to unseen nodes given meaningful node features (Kipf &
Welling 2017 Defferrard et al.) 2016 Hamilton et al. 2017). Yet, most existing GNNs require lask-specific labels for training in -umi-supeee fasshion to achieve satisfactory performance (Kipl & Welling 2017: 2017,Hamilton Hamilton et al.) 2017: Velickovic et al. 2018: Chen et al. 2018),, , and their usage limited to single graphs where the downstream task is fixed. To this end, several unsupervised ones like GVAE (Kipf & Welling, 2016) and GNFs (Liu al. 2019), as well as the deep-infomax-basee ones like DGI (Velickovic al. 2019) and InfoCiraph (Sun et al. 2019). Their potential in the transfer learning of GNN remains unclear when the node features and link structures vary across different graphs
GNNs are presented, such as the auto-encoder-basse
Although the architectures of GNNs are not very complicated, training a dedicated model for each graph can still be cumbersome (Chen et al. 2018: Ying et al., 2018a). Moreover, pre-training neural networks are proven to be successful in other domains (Devlin et al. 2019: He et al. 2016). transfer well-trained GNNs from relevant source graphs to improve the modeling of target graphs or enable few-shot learning (Vinyals et al. 2016 Finn et al. 2017 Ravi & Larochelle 2017) when labeled data are scarce. In the light of this, pioneering works have studied both generative (Hu et al., (2020) and discriminative (Hu al. 2019a b) GNN pre-training schemes. Among these work, though Graph Contrastive Coding (Qiu et al. (2000) shares similar structural view as ours, it utilizes contrastive learning in the embedding space instead of structural space as EGI. Unsupervised domain adaptive GCNs (Wu et al.) 2020) study the domain adaption problem while source and target tasks are homogenous. Previous pre- mre-training and self- self-supervised GNNs lack a rigorous analysis towards their transferability and thus have unpredictable effectiveness.
the idea is intriguing
5 CONCLUSION
To the best our knowledge, this is the first research effort towards establishing a theoretically grounded framework to analyze GNN transferability, 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, as well as analyze and improve the proposed framework over more transfer learning scenarios and datasets.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Réka Alhert and Albert-Láázzo Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Sanjeev Arora, Elad Hazan, and Satyen Kale. Fast algorithms for approximate semidefinite program- ming using the multiplicative weights update method. In =FOCS, pp. 339-348, 2005.
Lu Bai and Edwin R Hancock. Fast depth-based subgraph kernels for unattributed graphs. Pattern Recognition, 50:233-245, 2016.
Albert-Láás7óó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):50--512, 1999.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, pp. 585-591, 2002.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In NIPS, pp. 137-144, 2007.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NIPS. pp. 15868-15876, 2019.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92, American Mathematical Soc., 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, pp. 3844-3852 2016.
Jacob Devlin, Ming- bidirectional transformers for language understanding. In ACL, pp. 4171-4186 2019.
Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- of deep
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICLR, 2017.
Rolf Dieter Grigorieff. A note neumann's 's trace inequalitv. Mathematische Nachrichten, 151 (1):327-328, 1991.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp. 855-864 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. ACHA, 30()) 2011.
Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, pp. 770-778, 2016.
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. KDD, pp. 1231-1239, 2012.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchilde Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR, 2019.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitik,, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICI.R 2019a.

---

Under review as a conference paper at ICLR 2021
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:190S.13778, 2019b.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In KDD, pp. 1857-1867, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. NIPS, 2018.
Suk-Geun Hwang. Cauchy's ' interlace theorem for eigenvalues of hermitian matrices. The American Mathematical Monthly, 111(2):157-159, 2004.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In NIPS, pp. 7090-7099, 2019.
Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.03300 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
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 in data mining, pp. 177-187, 2005.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems, pp. 13556-13566, 2019.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444 2001.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado. and Jeff Dean. Distributed representations of words and phrases and their compositionality. NIPS, pp. 3111-3119, 2013.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
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, pp. 259-270, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD, pp. 701-710, 2014.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding. Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In KDD, pp- 1150-1160, 2020.
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. In ICLR, 2017.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In KDD, pp. 385-394, 2017.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 29065500) 2000.
Yu Shi, Qi Zhu, Fang Guo, Chao Zhang, and Jiawei Han. Easing embedding learning by compre- hensive transcription of heterogeneous information networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1190-2199, 2018.
10

---

Under review as a conference paper at ICLR 2021
Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: core of semantic knowledge. In WwW, pp. 697-706, 2007.
Fan- Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. JCLR, 2019.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In WWW, pp. 1067-1077, 2015.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. Science, 29055500) 22233, 2000.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Saurabh Verma and Zh Zhang. Stability and generalization graph convolutional neural networks. In KDD, 2019.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Daan Wierstra, al. Matching networks for one shot learning. In NIPS, pp. 3630-3638, 2016.
Boris Weisfeiler and Andrei A Lehman. reduction of graph to canonical form and an algebra arising during this reduction.
Tenecmo-TTchhnihhsskkyy Informatsia, 2(9):12-16, 1968.
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In WWW. pp. 1457-1467, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
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: 1412.6575, 2014.
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NIPS, pp. 1338-1349, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovee. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NIPS, 2018b.
A THEORY DETAILS
From the Lie objective, have assumed gi Ltd we have access to the empirical distributions of the three. So the sampling reduces to bootstrapping in the procedure of evaluating the objective.
14, Hj Ltd
and (gi, xr,) Lid
p. Then with graph G,
Note that, in Eq. 2 of the main paper, we used a d dimensional hidden state hg ng. specified in Eq. 13 denote an edge encoding derived from the structure of the ego-graph and the associated source node feature from (p 1)-th layer. For simplicity, we consider the concatenated vector f(x*) |2, where f(x') ) = 1 and h².g. xhh.g are as defined in the EGr model and in 13 Additionally, since both of he and "h., are normalised, f is bounded.
considering GNN with layers, its computation only depends the k-hop ego- graphs of G. which is an important consideration when unfolding the embedding GNN at a centre node.
Finally,
11

---

Under review as a conference paper at ICLR 2021
A.1 PROOF FOR THEOREM 3.1
Lemma A.I. For any A Rmxx,, where n, and A is submatrix of B E Rm''xn, where m < m', we have
|| & ||||2
Proof. Note that, AAT is principle matrix of BB i.e., AA is obtained by removing the same set of rows and columns from BB", Then, by Eigenvalue Interlacing Theorem (Hwang (2004)) and the fact that A A and AA" have the same set of non-zero singular values, the matrix operator norm satisfies ||A||2
Amxxx (A' V Amax (AAT)= S v Vmaax (Amax(BBB) = |B
We restate Theorem 3.1 from the main paper as below.
Theorem A.2 (GNN transferability). Let G. (g),, and Gb [gv, be two graphs. Then denote Ly. as the (normalised) graph Laplacian of 9i Vi = 1,..., and let the node features of 9s be structure-reppectin and normalized (similarly for gv). Consider GNN Vo with k layers and I-hop polynomial filter Og the empirical performance difference of V with de evaluated on Leau satisfies
m
[Lga(Ga) (G,)l SO
Amax(Leg L/2))/12
where M is a constant dependant on k, Φe, {La. (har {rsh {xy). In addition, if 3U On V m s.t.
ULg. UT Diag( (MLgg))) ULg U Diag(A(Lgig
we have O (M + Jo Ex= EØ= [p)(g.))) - M(L M2.), values of the graph Laplacian of gr Ga (similarly for ge).
where A(Lg.) denotes the ordered eigen-
Proof. We denote (!) log(1 1 e²), the softplus activation function, which is 1-Lipschitz contin- uous. Now,
(G) L (G')l
(D(gi
(-(-D(g;, 2;)) -
Σ
(D(gr
(- D(gr, ))))
m²
v'='==
===1
Digr, 2z) - D(gv, 2z)
Digi, 2,) D(gu,
mm
nm
</=1
Σ
Σ
A+
ΣΣ B.
n'm
1=1=1
im
F==
First we consider B. Recall that, Vp(gi) the set of nodes layer p of gi
|V(a))
D(g 21)
Σ
log(asig (UT ((<
Q=1
where asig (t) - is the sigmoid function, is some 7, -ipLicitiitz activation function and [-Il-] denotes the concatenation of two vectors. Then we have
T (W (1))) U"r (W f(x') - W2'z2)
'O V m) is the orthogonal group of order m. So we have L.g, and Tog. admitting simultaneous ordered spectral decomposition.
12

---

Under review as a conference paper at ICLR 2021
WLOG, assume dp = Vg = |V Yu = 1..... kk. In addition, since log(Origgt))
- -log(1+ + e) = -0, which is I-Lipschitz, it gives
k dp
UT (WTf(x') + 222) - (Wf + W2 2x)
B -
(I WT + 11 2, 2x
S 7+
p=1 q=1
& dp
Σ p=1q=1
ΣΣON (l)((t))))) - 1(00-((())))))) )ll2 + || - 2x112); 1zz-zx112).
where sy is the largest singular value of U, and similarly sw = sw; V sw,- Since we assumed the node features normalised, then [f(=') f(x") 1ll2 S CD.
From Eq. 7 we only care about z;'s 's embedding obtained from a k-layer GNN with I-hop polynomial (linear in L) filter. Inspired by the characterization of GNN from a node-wise view in Veema & Zhang (2019) we similarly denote the embedding of node I; Vi = =i,1,... -,,.,, n in the final layer of the GNN as
= 2, = Vo(ox) of Σ e.j () ER. R.
JEN(())
where e.j = [L) E R. We may denote =f E Rd similarly for l = 1,... AA 1, and 2. x; E gd-1 the node feature of node rú. With the assumption of GNN stated in the statement, it is clear that only the k-hop ego-graph g, centered at æ; needed compute 2 for any 1.... n instead of the whole of G. With such observation in mind, let us denote the matrix of node embeddings of ((t) Ii at the 9th layer (zpla) E (o.)ll for l = 1, k; and let (=p.4
(1ppaa (84-1)IV(a.)
denote the matrix of node features in the h-hop ego-graph 9.. In addition, denote i(E) pss to be the submatrix that is obtained by selecting rows that corresponds to u E Vyr()) for 0, , S k. Similarly for gr-
Moreover, let us denote do (T.g.) = (L)(())) Ig.. ie., the filtered full graph Laplacian of G subsetted by the k-hop ego-graph 9i- Then, let ob Ipst denotes the submatrix that is obtained by selecting rows and columns that corresponds to v E Vp(gi for p-rp- = 0,-.. ... , S k. Similarly for gr.
Therefore, by Lemma A.I for any 8= 1,... k. the following holds
(1(2((0) jest - (2 (ps(l)psell S (1( (0))())))))) (10)) )
Assume (( ( S cs < x Vl. Now, at the final layer,
|| z ||(=((()) p= (=(((())p=ol )=lll2
<l|(<(b0( T.g, )os (=p10-
i(k - 1) )55) - <cho (1 )osi (=p(0
(1--11) (21)))
Stal100 L.g )ps1 (2 ((k--)) p25 6 (L )s1
(1(
))
(8)
(((6-1) 1)) p51
))) (2//1 (21'(x-1)) )sall2
+701(=0/44 ) ll /0 Lg 1ps1 م )os1ll ll2
St0l100 (102g,111222 11221111111 ((k-1)) 151 - (z )) Spsillz + Toc 7oczlloo(Lgg) -
p.q
In general, for E = 1,... ... k- - 1. the following holds with = k -., l. [1(=/(()) 1ps: - (2 )psell
Stall0b0 (gg (154))+++112) (=00 i(t- ) - cho (Lor Iose+ (= (((e-1)))a 1ss+ill2
(9)
STollcb0 (.g.)) [lal (((t-1)))))))) ppS+1 - (=/'( (e-1() |p + 7oczllobo (L..)) del (g)))
ll2
Then we equivalently write Eq. as Fg < bF + a, which gives
+1
Ee S b9 Et + b-1 a
13

---

Under review as a conference paper at ICLR 2021
Then, with (1)) [1(0)) see the following is only dependant the structure of gi and gr,
(1()1(0) (x - (olloo(L,))) (1121(1 p.g) - (x PM
16 g. 1112
To co g. 1l To (ocello((gg)) de (L )l
Since the features are normalised, and so are the graph Laplacians, we have 11 Ill S ey and [1( - (o S Cr. Then with Eq. 8 we have
|| zvl12 S c + rach +
Cr -1 N00 IT: T.g.112
(10)
S C + 114. - -gr
- + Amax (Teg )12)
Now, by Eq. 7 have
B S kdmax SCD + (y + Amax (L Lgg )2/2)) where dinax maxp dp- Similarly, the above holds for A, since from Eq. embedded features are bounded by separate terms. We therefore arrive at
8
the node features and
(G) - LEGI (G') < 2kd C, (M
(MM
Amaa (L.. Lgg)
nmm
(11)
m
2kdlmax Yr V
1 To l1F).
mm
Moreover, by Von Neumann's Trace Inequality Grigorieff [991]. p. if EU 0 Exz dps s.l.
where
UTg UT Diag (iag()A(T):)); U UTg U Diag(A(T.g))
have |g Lgy || | X(L 12, then
Eq. C. (M [|A(Lgg)) M12)
Therefore Eq. becomes
n
(G) LEGI(G")| (2k")l 7r Cs
(A(L))) - (Lgx)ll2)
Tu 1=1==1
Note that, our view structural information closely related to graph kernels Bai & Hancock 2016) and graph perturbation (Verma & Zhang] 2019). Specifically, our 2ef is motivated by the concept of k-layer expansion sub-graph in (Bai & Hancock] 2016). However, (Bai & Hancock 2016) used the Jensen-Shannon divergence between pairwise representations of sub-graphs define a depth-basse based sub-graph kernel, while we depict G as samples of its ego ago-graphs. In this sense, our view is related to the setup (Verma & Zhang (2019), which derived a uniform algorithmic stability bound of 1-layer GNN under 1-hop structure perturbation of G.
In the setting of domain adaptation, (Ben-David et al. 2007) draws connection between the difference in the distributions of source and target domains and the model transferability, and learns transferable model by minimizing such distribution differences. This coincides with our approach of connecting the structure difference of two graphs in terms of k-hop subgraph distributions and the transferability of GNNs in the above theory.
B MODEL DETAILS
Following the same notations used in the paper, EGI consists of a GNN encoder V and GNN discriminator D. In general, the GNN encoder v and decoder D can be any existing GNN models. For each ego-graph and its node features (gi, J.), the GNN encoder returns node embedding 2;
(())) is the orthogonal group of square matrix B. So we have Tig. and Tgg admits simultaneous ordered spectral decomposition.
14

---

Under review as a conference paper at ICLR 2021
for the center node u4 As mentioned in Eq. 2 in the main paper, the GNN discriminator D makes edge-level predictions as follows,
D(c 1h mag: "... 2,) (U² (W [1 -
(12)
where Cav E (gg)) and ha E IR is the representation for edge cæv between node up-1.. ş in hop
p - and pp. in hop p. Specifically, we denote the source node at p p- hop as ÿ E Qp.q. Qp.a = { 0p-11. L. p-1 (gi), f (..)))))) Elg)). Hence, the edge prediction relies the combination of center node embedding 2g, destination node feature x p.g and edge message h ".-""
center node embedding
Ego-graph xi)
Encoder "
Discriminator
hop
hop 2
edge message passing
Edge-wise decision
Ego-graph xg)(x/)
X
x
Z1
edge message passing
Figure 3: The overall EGI training framework.
In Figure 3 (gr, and (g/. a/) are the positive and negative training samples w.r.t ego-graph topology 9t. The discriminator D operates on reversed ego-graph ÿ comparing encoder's forward propagation gi. It starts from the center node v, and compute the hidden representation mp-1.4 for node 1,-1,0 representation 1,-1,5 and destination node features Zp.a
1,a at each hop. The edge message hg. is calculated between source node's hidden
R ReLU (WT (Mp-1.5 + +xpa)) mp-1.
Σ
R p-1.
(13)
1p-11gl g'EQpp14
When p 1, every edge origins from the center node v; and ma.g' is the center node feature Tes
In every batch, we sample a set of ego-graphs and their node features {gi, ..3. During the forward pass of encoder V, it aggregates from neighbor nodes the center node e.. Then, the discriminator calculates the edge embedding Eq. [2] from center node o, to its neighbors and make edge-level predictions- fake or true. The training framework of EGI is depicted Figure and Algorithm [
We implement our method and all of the baselines using the same encoders W: 2-layer GIN (Xu et al. 2019) for synthetic and role identification experiments, 2-layer GraphSAGE (Hamilton al.) (011)) for the relation prediction experiments. We set hidden dimension as 32 for both synthetic and role identification experiments. For relation prediction fine-tuning task, we hidden dimension as 256. We train EGT in mini-batch fashion since all the information for encoder and discriminators are within the k-hop ego-graph Ii and its features F;. Further, we conduct neighborhood sampling and set maximum neighbors as 10 to speed up the parrallel training. The space and time complexity of EGI is O(BN*) where is the batch size, is the number of the neighbors and is the number of hops of ego-graphs. Notice that both the encoder y and discriminator D propagate message on the k-hop ego- pro-graphs, so the extra computation cost of D compared with a common GNN module is a constant multiplier over the original one. The scalability of EGI million scale YAGO network is reported in section C.3
B. TRANSFER LEARNING SETTINGS
The goal of transfer learning is to train a model on a dataset or task, and use it on another. In our graph learning setting, focus training the model particular, we focus our study on the setting of direct-trand traeecttransfering. where the model learned on the source graph is directly applied the target graph without fine-tuning. We study this setting because
graph and using
another. In
15

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Pseudo code for training EGI
The GNN encoder Vi and the GNN discriminator DD k-hop ego graph and features {gi, m::: 1 EGI-training starts */
while Eo not converges do
Sample M ego-graphs {g11 æ1), ..., (gM, I)) from empirical distribution IP without replacement, and obtained their positive and negative node embeddings o through y
(gt, mz); z/ ((g4a4))
1* Initialize positive and negative expectation in Eq. in the main paper*/
Epos- = 0, Eneg-
for p to k do
1 Compute JSD on edges at each hop*/ for ((p-1.()(p-) E Eg.)) do
generate edge embedding hg in Eq. 133
10
Epos Epos + (UT (W2 [1g p.9
pig xx]]
Ling Enog to (UT T (W [1 p. =11
11
12
end
13
end
1 Compute batch loss*/
15
LEGI Eneg Epos 1 Update V D #/
16
V LEGI, 0D x DDLGGI
end
it allows us to directly measure the transferability of GNNs, which is not affected by the fine-tuning process on the target graph. In other words, the fine-tuning process introduces significant uncertainty to the analysis, because there is no guarantee on how much the fine-tuned GNN is different from the pre-trained one. Depending on specific tasks and labels distributions on the two graphs, the fine-tuned GNN might be quite similar to the pre-trained one, or it can be significantly different. It is then very hard to analyze how much the pre-trained GNN itself is able to help. Another reason is about efficiency. The fine-tuning of GNNs requires the same environment set-up and computation resource as training GNNs from scratch, although it may take less training time eventually if pre-training is effective. It is intriguing if this whole process be eliminated when we guarantee the performance with direct- transfrraan....ng..
In our experiments, we also study the setting of transfer learning with fine-tuning, particularly on the real-world large-scale YAGO graphs. Since we aim to study the general transferability of GNNs not bounded specific tasks, we always pre-train GNNs with the unsupervised pre-training objective on source graphs. Then we enable two types of fine-tuning. The first one is post-fine-tuning (C = L.). where the pre-trained GNNs are fine-tuned with the supervised task specific objective C, on the target graphs. The second on is point-finettuning (L = L, + Lu), where pre-training is the same, but fine-tuning done w.r.t. both the pre-training objective L. and task specific objective L, on target graphs in a semi- semi-supervised learning fashion. The unsupervised pre-training objective C., of EGI is Algorithm|| [ while those of the compared algorithms are as defined in their papers. The supervised fine-tuning objective L. is the same as in the DistMult paper (Yang et al., 2014) for all algorithms.
C EXPERIMENT DETAILS
C.1 SYNTHETIC EXPERIMENTS
Data. As mentioned in the main paper, we use two traditional graph generation models for syn- thetic data generation: (1) barabasi-albert graph (Barabási & Albert 1999) and (2) forest-fire graph (Leskovec et al. 2005). We generate 40 graphs each with 100 nodes with each model. We control the parameters two models to generate two graphs with different ego ego-graph distributions. Specifically, set the number of attached edges as 2 for barabasi-alba
model and set Preeward 0.4, Phackwand = 0.3 for forest-fire model. In Fagure/aaande and we show example graphs from two families in our datasets. They have the same size but different appearance which leads to our study the
16

---

Under review as a conference paper at ICLR 2021
transferability gap in Table I in the main paper. The accuracy of this task defined the percentage of nearest neighbors for target node in the embedding space that are dtructure-qqiivalee i.e. #correct k-nn neighbors #ground truth equivalent nodes.
(a) Forest-fire graph example
(b) Barabasi-allas graph example
(c) structural label example
Figure 4: Visualizations of the graphs and labels we use in the synthetic experiments.
Results. The structural equivalence label is obtained by 2-hop WL.test (Weisfeiler & Lehman 1968) on the ego-graphs. If two nodes have the same 2-hop ego-graphs, they will be assigned the same label. In the example of Figure 4c the nodes labeled with same number (e.g. 2, 4) have the isomorphic 2-hop ego-graphs. Note that this task is exactly solvable when node features and GNN architectures are powerful enough like GIN (Xu al. 2019). In order show the performance difference among different methods, we set the length of one-hot node degree encoding to (all nodes with degrees higher than have the same encoding). Here, we present performance comparison with different length of degree encodings (d) in Table When the capacity of initial node features is high (d=10), the transfer learning gap diminishes between different methods and different graphs because the structural equivalence problem can be exactly solved by neighborhood aggregations. However, when the information initial node features limited, the advantage of EGI in learning and transfering the graph structural information is obvious. In Table [5] we also show the performance of different transferable and non- non-transferable features, i.e. node embedding (Perozzi et al.) (004) and random feature vectors. The observation is similar with Table in the main paper: the transferable feature can reflect the performance gap between similar and dissimilar graphs while non-transferable features can not.
In both Table and There as well as Table in the main paper, we report the structural difference 1
among graphs the two sets (d) calculated w.r.. the term nm Σn Ex= [|A(L,,) XLL.y )ll on the RHS of Theorem 2.1 in the main paper. This indicates that the Forest fire graphs are structurally similar the other Forest fire graphs, while less similar to the Barabasi graphs, as can be verified from Figure 4a 4b) Our bound in Theorem 3. then tells us that the GNNs (in particular, EGI) should be more transferable the F-F case than B-F. This is verified Table and 5 when using the transferable node features of degree encoding with limited dimension (d=3) well Deep Walk embedding, as EGI trained on Forest fire graphs performs significantly better on Forest fire graphs than Barabasi graphs (with +0.094 and +0.057 differences, respectively).
Table Synthetic experiments of identifying stractural-equivalent nodes with different degree encoding dimensions.
#dim degree encoding =
dim degree encoding 10
structural difference d(F.F)
Method
F-F
B-F
A
F-F
B-F
d(B.F)
GCN (untrained)
0.478
0.478
0.940
0.940
GIN (untrained)
0.572
0.572
/
0.940
0.940
GVAE (GCN)
0.498
0.432
+0.066
0.939
0.937
0.002
1.78
2.17
DGI (GIN)
0.578
0.591
-0.013
0.939
0.941
-0.002
EGI (GIN)
0.710
0.616
+0.094
0.942
0.942
C.2 REAL-WORLE ROLE IDENTIFICATION EXPERIMENTS
Data. We report the number of nodes, edges and classes for both airport and gene dataset. The numbers for the Gene dataset the aggregations of the total 52 gene networks in the dataset. For
17

---

Under review as a conference paper at ICLR 2021
Table 5: Synthetic experiments of identifying structural nodes with different transferable and non-
transferable features.
WelpWalk Walk embedding
random vectors
structural difference d(F.F)
Method
F-F
B-F
A
F-F
B-F
A
d(B,F)
GCN (untrained)
0.658
0.658
/
0.246
0.246
/
GIN (untrained)
0.663
0.663
/
0.520
0.520
/
GVAE (GCN)
0.713
0.659
+0.054
0.266
0.264
0.002
1.78
2.17
DGI (GIN)
0.640
0.613
+0.027
0,512
0.576
-0.064
EGI (GIN)
0.772
0.715
+0.057
0,507
0.485
+0.022
Table 6: Overall Datasct Statistics
Dataset
# Nodes
# Edges
# Classes
Europe 399
5,995
USA
1,190
13,599
4
Brazil
131
1,074
Gene
9,228
57,029
the three airport networks, Figure shows the power-law degree distribution log-log scale. The class labels are between 0 to reflecting the level the airport activities (Ribeiro et al. 2017). For the Gene dataset, matched the gene names in the TCGA dataset (Yang et al. (2119) to the list of transcription factors on wikipedie 75% of the genes are marked as (transcription factors) and some gene graphs have extremely imbalanced class distributions. So conduct experiments the relatively balanced gene graphs of brain cancers (Figure in the main paper). Both datasets do not have organic node attributes. The role-based node labels are highly relevant to their local graph structures, but are not trivially computable such as from node degrees.
084
18
10
19
(a) Europe airport log-log plot
(b) USA airport log-log plot (c) Brazil airport log-log plot
Figure 5: Visualizations power-law degree distribution on three airport datasct.
Results. As we can observe from Figure 5 the three airport graphs have quite different sizes and structures (e.g., regarding edge density and connectivity pattern.. Thus, the absolute classification accuracy in both Table in in the main paper and Table [rble7Thrr here varies across different graphs. However, mention in the main paper, the structural difference compute based Eq. in Theorem 3.1 is close among the Europe-USA and Murope-Brazii graph pairs (12.03 and 12.14), which leads to close transferability of EGI from Europe to USA and Brazil. This indicates the effectiveness of our view over essential structural information.
Note that, the results present in Table 7 are the accuracy of GNNs directly trained and evaluated on each network without transfering. Therefore, only the Europe column has the same results as in Table in the main paper. while the USA and Brazil columns can be regarded as providing an upper-bound performance of GNN transfered from other graphs. As we can see, EGI gives the closest results from Table 2 in the main paper to Table here, demonstrating the its plausible transferability. The scores are so close, showing a possibility to skip fine-tuning when the source and target graphs are similar enough. Also note that, although the variances are pretty large (which also observed
18

---

Under review as a conference paper at ICLR 2021
in other works like (Ribeiro et al. 2017) since the networks small), t-tests have shown the improvements of EGI to be significant.
Table 7: Role identification that identifies structurally similar nodes on real-world networks. The performance reported are the average and standard deviation for 10 runs. Our classification accuracy on three datasets all passed the t-test (p<0.01) with the second best result in the table.
Airport (Ribeiro al.
2017
Method
Europe
USA
Brazil
node degree
52.81% + 5.81 %
55.67% + 3.63%
67.11% + 7.58%
GCN (random-init)
52.96% + 4.51%
56.18% + 3.82%
55.93% + 1.38%
GIN (random-init)
55.75% 1 5.84%
62.77% 2.35%
69.26% = 9.08%
GVAE (GIN) (Kipf& & Welling 2016
53.90% + 4.65%
58.99% = 2.44%
55.56% = 6.83%
DGI (GIN) Velickovic ct al. 2019
57.75% + 4.47%
62.44% 4.46%
68. 15% + 6.24%
Mask-GIN (Hu el al. 2019a
56.37% 1 5.07%
63.78% +: 2.79%
61.85% = 10.74%
ContextPred-GIN (Hu al. 2019a
52.69% 1 6.12%
56.22% + 4.05%
58.52% 10.18%
Structural Pre-train (Hu al.
2019b
56.00% + 4.58%
62.29% 3.51%
71.48% 9.38
EGI (GIN)
59.15% 4.44%
65.88 % 3.65%
74.07% % + 5.49%
C.3 REAL-WORLD LARGE-SCALE RELATION PREDICTION EXPERIMENTS
Data. As shown in Table 8 the source graph we use to pre-train GNNs is the full graph cleaned from the YAGO dump (Suchanek al. (007). where assume the relations among entities are unknown. The target graph we use is a subgraph uniformed sampled from the same YAGO dump (we sample the nodes and then include all edges among the sampled nodes). The similar ratio between number of nodes and edges can be observed in Table On the target graph, we also have the access to 24 different relations (Shi et al.) 2018) such as isAdvisedBy, isMarriedTo and so on. Such relation labels are still relevant to the graph structures, but the relevance is lower compared with the structural role labels. We use the 256-dim degree encoding as node features for pre-training on the source graph, then use the 128-dim positional embedding generated by LINE (Tang et al. 2015) for fine-tuning on the target graph, to explicitly make the features differ across source and target graphs.
Results. In Section B. we introduced two different types of fine-tuning, i.e., poot--fieetuning and joint-fine-tunin For both types of fine-tuning, we add one feature encoder & before feeding it into the GNNs for two purposes. First, the target graph fine-tuning feature usually has different dimensions with the pre-training features, such the node degree encoding we use. Second, the semantics and distributions of fine-tuning features can different from pre-training features. The feature encoder aims to bridge the gap between feature difference in practice. The supervised loss used in this experiment is the same as in DistMult YYngg et al. 2014). In particular, the bilinear score function is calculated as s(h. r, t) 2%, M1 where M, is diagonal matrix for each relation r, 24 and 2 the the embedding of GNN encoder & for head and tail entities. The experiments were run on CTX1088 with 12G memories. We report the average training time per epoch of our algorithm in pre-training and fine-tuning stage in TableBaa well. The pre-training and fine-tuning takes about 40 epochs and 10 epochs to converge, respectively. In Table we also present the per-epoch training time of EGI. EGI takes about 338 seconds per epoch for optimizing the ego ego-graph information maximization objective on YAGO-source. As we can see, fine-tuning also takes significant time compared pre-training, which strengthens our arguments about avoiding reducing fine-tuning through structural analysis. We implement all baselines within the same pipeline, and the runtimes all at the same scale.
Table 8: dataset statistics and running time of EGI
Dataset
# Nodes
# Edges
# Relations
# Train/Test
Training time per epoch
YAGO- Source
579,721
2.191,464 409,952
/
338 seconds
VAGO-Target
115,186
24
480/409,472
134 seconds
19


Reviews:
[{"review_id": "snCtKNlg-gx", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work considers the unsupervised learning for graph neural networks. The work has solid theoretical analysis and extensive experimental studies. To encode the structure information, the K-hop ego-graph is used to generate a k-hop ego-graph for each node. I don’t see any major issues in this work. Here are several small concerns:\n\n1.\tIn this work, the ordered k-hop ego-graph is used but didn’t discuss how this order is generated. Would the authors explain how the ordering works.\n2.\tSince k is an important hyper-parameter, can authors provide some experiments to evaluate the impact of different k values.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "qG05RqeoeCq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a transfer learning scheme for graph neural networks. The proposed method ego-graph information maximization allows learning transferable models. The authors studied structure-respecting node features and provided a theoretical analysis of the transferability of GNNs. The proposed method significantly outperforms state-of-the-art methods.\n \nClarity:\nOverall, this paper reads fine. There are some typos and missing definitions of symbols, e.g., `sp' in eq 1 and $U^T$ in eq 3. D function is defined by another D in eq 2. In definition 2.3, 'Ordered' ego-graph is not defined. 'Title 2.2. ANALYSI', 'structural equivalence', and 'structural different' are typos. The average structural difference denoted by $\\bar{d}(,)$ \nare not defined. The clarity of this manuscript needs to be improved.\n \nStrengths/Quality/Significance (pros):\nThe interesting observation that the functions learned by GNNs can be viewed as functions to map a subgraph centered at a node to a class label since most GNNs have a few layers and their receptive field of a node output is a k-hop ego-graph.\n \nThe authors studied structure-respecting node features, e.g., degrees, spectral embeddings, to show that graph filters of GNNs is transferable. Based on the structure-respecting node features, the authors provide the analysis of transferability solely depending on the graph structure. The analysis showed that the performance gap of transferred models is bounded by a function of the ordered eigenvalues of the graph Laplacian of ego-graphs.\n \nThe proposed method achieved significant improvement against baseline approaches.\n \nWeaknesses (cons) & Questions:\n \nThe writing should be improved. The manuscript should be self-contained. As mentioned above, there are functions, and variables that are introduced without definitions such as reconstruction loss, sp, $\\bar{d}(,)$ and so on.\n \nThe analysis is limited to graph structures. To benefit most GNNs in real-world applications, the transferability of GNNs needs to be analyzed with node features as well.\n \nIn this paper, the analysis of the transferability of GNNs is limited to node classification. It is not clear whether the proposed method is effective in other tasks on graphs such as link prediction, graph classification. \n \nEven in the synthetic experiments, the performance gain is obtained only in the transferrable feature settings.\n\n--- Post Rebuttal --- \nI read the author response and I keep the original rating due to the limited operating range of the proposed method.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cd83F0ZekwN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose ego-graph information maximization (EGI) to build more transferable GNN. They further theoretically study the transferability of EGI. \n\n\nThe article is fairly well structured, apart from the literature review, which is somewhat missing significant related works, such as Ron Levie's papers, which are the first theoretical studies regarding the transferability of GCNs. Concerning terminology, a reminder of what is called “node features” would be very useful for the reader, as this paper seems to construct features based on the graph structure instead of node attributes or signal over nodes as the node features. The article has the unfortunate tendency to contains a few unproven claims. For instance, \"we establish a theoretically grounded and practically useful framework for the transfer learning of GNNs\", which would deserve some empirical/theoretical evidence. Yet, the paper is only exploring the transferability of the proposed GIN.\n\nThe main argument is to establish a theoretically grounded framework for the transfer learning of GNNs and leverage it to propose a practically transferable GNN model, which I think is a very valid motivation for this paper and also is an important problem, but I think the authors could not achieve this goal properly. From my point of view, this paper proposes a new GNN model and further show theoretically and empirically that their new model is more transferable in some specific circumstances though, it’s quite hard to see some conclusions in my opinion based on both real and simulated experiments (but the transferability arguments of EGI holds to some degree nonetheless).\n\nComments/concerns/questions:  \n\n- In practice, the dataset consists of signals defined on many different graphs; the trained GNN should generalize to signals on graphs unseen in the training set. However, the experiments did not consider such a situation and only focused on some specific constructed features. Also, the authors claim the node features should be a function of the structure. The node attributes (signals over graph) can somehow be considered a noisy function of the graph structure. I would like to see the comparison performance in such situations too, where the graph has node attributes by itself. \n\n- What kind of functions over the graph is reasonable to construct the node features? How much noise is acceptable?\n\n- While the authors talk about the joint distribution of graph structure and node features, I think they are only using graph structure in two ways. Then, the main question is how one can use the graph structure as node attributes. Can one concatenate different constructed node features as node attributes? For example, assuming using both node degree and one-hub embedded graph based on VGAE.\n\n- It has been claimed \"[...] under an analogous setting of domain adaptation[..]\". How can one interpret it as domain adaptation? Can you show the embedded space? \n\n- Considering the graph convolutional neural network, either \"On the Transferability of Spectral Graph Filters\" or  \"Transferability of Spectral Graph Convolutional Neural Networks\" can be considered one important baseline.\n\n- Does $\\psi$ is the same for all graphs? If not, the heterogeneous embedding spaces should be an issue.\n\n- The similarity is not interpretable, and it is dependent on data. This is one of the main drawbacks of this paper. Specifically, for EGI on the Gene dataset, the structural difference higher than 5.4 causes a negative transfer effect; however, a structural difference larger than 12 can improve the airport dataset performance. In practice, we do not know the true answer. How can one know if the method is practical in a new dataset? \n\n- Besides that, $G_5$ has a higher distance than $G_4$ and $G_3$; however, it exploits the transferability of EGI more. A discussion on this phenomenon is needed.\n\n- The empirical results do not show the same relationship between DGI and the structural differences. If one considers the transferable feature column for DGI, please compare the performance improvement with the untrained GIN. \n\n- I believe the 3rd and 4th row of the second table is wrong. Please double check. Based on the first table, DGI outperforms EGI for non-transferable features. A comparison, based on another kind of features are needed. \n\n- Table 2 needs to have other columns similar to the first table to see how $\\Delta$ will be. \n\n- I also would like to see the target graph B performance in Table 1 (F-B and B-B). Also, the performance of considering two other airports as the source for the airport dataset.\n\n- Comparison with the baselines on the Gene dataset would be helpful. \n\n- Comparing EGI with SOTA GNN methods in some other analytical tasks, including node classification, link prediction, etc. can help validate this model's capability as a new GNN. \n\n- Including a simulation based on some specific perturbations on the target graph is also insightful.\n\n------- UPDATE ---------\n\nI thank the authors for their response to my concerns/comments. It seems like I have to defend my position for suggesting a rejection of the paper. While the response of the authors has clarified some aspects, some comments have not been adequately addressed.\n\nR1: However, the authors could not show how to measure the structural differences between the source and target graphs? Their measurement is not stable and is different between different datasets. How one can evaluate a new dataset is good for transferring or not (R5)? You could see how Ron Levie et al. showed this in their experiments. \n\nR2: But embedding using GCN is another definition for the function of the structure. However, it does not work well as node degree. Therefore, the author cannot point out that you only need to construct the features based on a function of the structure.\n\nR4: You can somehow use their idea to show how much difference is reasonable to transfer information. \n\nR5: So it seems this is one of the main drawbacks of considering \\delta. If that is the case, you need to discuss it in the paper. \n\nR7: I believe the response is not sufficient. The authors need to add that to show they could positively transfer information.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GpOZpfY-GF", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a theoretical framework for analyzing GNN transferability. The main idea is to view a graph as subgraph samples with the information of both the connections and the features. Based on this view, the authors define EGI score of a graph as a learnable function that needs to be optimized by maximizing the mutual information between the subgraph and the GNN output embedding of the center node.  Then, the authors give an upper bound for the difference of EGI scores of two graphs based on the difference of eigenvalues of the graph Laplacian of the subgraph samples from the two graphs. The implication is that if the difference of the eigenvalues is small, then the EGI scores are similar, which means the GNN has a similar ability to encode the structure of the two graphs. \n\nThe idea is new to me. One suggestion is that there are multiple forward references without precise pointers in the paper. Section 2.1 frequently refers to contents in Section 2.2. The authors may want to reorganize the paper to avoid any confusion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel framework from transfer learning over GNNs. Experiments ought to better substantiate how structural differences/similarities are measured, as well as relying on prior art to measure transferability success. A plan for incorporating (structural) features would also strengthen the present work.
Decision: Reject