Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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:

1.	In 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.
2.	Since k is an important hyper-parameter, can authors provide some experiments to evaluate the impact of different k values.

review_title: Solid theoretical analysis and extensive experimental studies

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.
 
Clarity:
Overall, 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}(,)$ 
are not defined. The clarity of this manuscript needs to be improved.
 
Strengths/Quality/Significance (pros):
The 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.
 
The 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.
 
The proposed method achieved significant improvement against baseline approaches.
 
Weaknesses (cons) & Questions:
 
The 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.
 
The 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.
 
In 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. 
 
Even in the synthetic experiments, the performance gain is obtained only in the transferrable feature settings.

--- Post Rebuttal --- 
I read the author response and I keep the original rating due to the limited operating range of the proposed method.
review_title: interesting results but a limited coverage

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

The 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.
review_title: need some reorganization

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose ego-graph information maximization (EGI) to build more transferable GNN. They further theoretically study the transferability of EGI. 


The 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.

The 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).

Comments/concerns/questions:  

- 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. 

- What kind of functions over the graph is reasonable to construct the node features? How much noise is acceptable?

- 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.

- 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? 

- 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.

- Does $\psi$ is the same for all graphs? If not, the heterogeneous embedding spaces should be an issue.

- 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? 

- 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.

- 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. 

- 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. 

- Table 2 needs to have other columns similar to the first table to see how $\Delta$ will be. 

- 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.

- Comparison with the baselines on the Gene dataset would be helpful. 

- 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. 

- Including a simulation based on some specific perturbations on the target graph is also insightful.

------- UPDATE ---------

I 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.

R1: 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. 

R2: 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.

R4: You can somehow use their idea to show how much difference is reasonable to transfer information. 

R5: 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. 

R7: I believe the response is not sufficient. The authors need to add that to show they could positively transfer information.

review_title: Ego-graph information maximization (EGI) is more transferable GNN

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