Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work aims to provide fundamental understanding towards the mechanism and transferability of GNNs, and develops an unsupervised GNN training objective based on their understanding. Novel theoretical analysis has been done to support the design of EGI and establish its transferability bound, while the effectiveness of EGI and the utility of the transferability bound are verified by extensive experiments. The whole story looks new, comprehensive and convincing to me.
main_review: Most arguments made and techniques developed in this work are well-supported by solid and detailed theoretical analysis. However, I do find a few limitations of this work. For example, (1) its focus on “structure-respecting features” might lead to the exclusion of its usage in many real-world networks where node features are more noisy and even not “structure-respecting”; (2) its study of transferability under the “direct-transfer” setting might be less useful when in real-world, most transfer learning is done with fine-tuning. Nonetheless, I understand the necessarily existing gap between theory and practice in many machine learning problems, and I appreciate the authors in making their assumptions clear and also conducting empirical analysis to show the generalizability of their model and theory over the scenarios where the assumptions are less valid.

The paper is overall well-organized, and I like the intermediate “supportive observations” in the technical section which help the understanding and verification of the technical contributions. In terms of writing, the introduction is very clear, while some details in the technical section require some back-and-forth reading. Further polishing over that section would benefit the overall readability.

To the best of my knowledge, this paper is the first one that provides a well-balanced blend of theory and empirical studies aiming to demystify the transfer learning with GNNs. Although its current scope is a bit limited, I think it is a necessary and good start for future research in this important direction.

limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper establishes a theoretically grounded and practically useful framework for transfer learning of GNNs.
main_review: The work seems complete, with both theoretical guidance and promising experimental results. The main drawback is that it is densely written (unclear in some parts) and difficult to follow. The authors are strongly encouraged to improve the readability of the paper, especially the methodology part. I have a few comments and questions.

 - Why does the computation of $\mathcal{D}$ on $E(g_i)$ depend on the edge orders (line 139)? According to Eq.3, the summation over edges does not seem to depend on edge orders.
 - What is the exact definition of the discriminator $\mathcal{D}$? It seems that both $f$ and $\Phi$ are a part of $\mathcal{D}$, but how are they combined together to form $\mathcal{D}$?
 - The topic is about transfer learning, but I cannot figure out how the model transfers from the source graph $G_a$ to the target graph $G_b$. It should be presented between Line 154 and 155.
 - Calling $\Phi$ decoder is confusing. The input of $\Phi$ is not the output of the encoder $\Psi$, so they are not a pair of encoder and decoder, but rather both are encoders.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel graph transfer learning framework with theoretical guarantees. Theoretical analysis is supported by both synthetic and real-world experiments.
main_review: Originality: The work is moderately original with ego-graph information maximization scheme. 

Quality: The transferability analysis seems theoretically sound and solid with improved transferability bounds. Experiments are carried out based on real-world datasets. I do not see any major issues with this work.

Clarity: The paper is well-organized overall. For clarity, I have some small concerns: In line 226, there is no reference to $\bar d$ columns. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops a novel measure for assessing the transferability of
graph neural network models to new data sets. The measure is based on
a decomposition of graphs into 'ego networks' (essentially,
a distribution of $k$-hop subgraph, extracted from a given larger
graph). Transferability is then assessed by means of a spectral
criterion using the graph Laplacian. Experiments demonstrate the utility
in assessing transferability in such a manner, as the new measure
appears to be aligned with improvements in predictive performance.
main_review: ## Summary of the Review

This paper discusses a timely and highly relevant topic. Understanding
*a priori* how a graph neural network will be able to perform on unseen
data is an excellent research objective; addressing this problem is
bound to lead to better models, and might even make 'pre-trained model
markets' more attractive for GNNs.

While I overall feel favourably about the paper, there are several
issues that need to be addressed before endorsing it for publication.
These comprise:

1. Unclear limitations or properties of the developed measure: 

  - The main text is currently not discussing how choices of $k$
    affect the calculation. If I understood everything correctly, $k
    = 2$ is set for all experiments; a more thorough analysis of
    different values of $k$ is necessary. It is clear that higher values
    of $k$ will not be beneficial with respect to computational
    performance, but their impact still needs to be assessed. I would be
    interested in learning to what extent transferability becomes more
    'precise' or more 'predictive' by these changes.

  - To what extent is the $\Delta_{\mathcal{D}}$ dependent on
    the ordering of input nodes? The way I understand Equation 6 is that
    two normalised graph Laplacians (which are of the same size because
    the same value for $k$ is being used throughout the paper) are
    subtracted from each other. However, this presupposes that the
    ordering of nodes is known in advance, which I do not think is the
    case here. This aspect needs to be discussed. (there is a brief
    discussion on edge ordering, following Eq. 1; if this applies here
    as well, I would suggest to mention it explicitly)

  - How is EGI used in practice? Do I understand this correctly that
    it is being employed as an additional loss term? Figure 2 seems to
    suggest at first that the primary purpose is to assess how well
    a model could be transferred, but the experiments later on seem to
    indicate that EGI is used *during* training. Please clarify this!
    (an alternative use case, discussed in l. 237-- could involve
    picking the best graphs as a training data set; this would be a more
    'static' use of the measure, so please comment on the exact details
    here)

2. Missing clarity, for instance when it comes to defining what the
   method is supposed to capture. The paper uses the term 'graph
   structures,' but seems to equate this with $k$-hop graphs. Upon
   re-reading the paper, I find that a more appropriate description
   would be that similarity of graph Laplacians is supposed to be
   captured (with the caveat about the dependence on a fixed ordering
   that I listed above).

3. The experimental setup could be improved: please report mean accuracy
   and standard deviations over multiple runs. This would help in
   assessing the proposed method.

## Comments on clarity

- Why does Definition 3.1 make use of a *directed* distance formulation
  between graph nodes? The remainder of the paper appears to discuss
  only the undirected case.

- Why is the second input to $\mathrm{sp}(\cdot)$ negated in Equation 1?
  The function $\mathcal{D}$ returns a probability, right?

- Why are self-loops required or included here? (l. 143)

- Please provide more details about the arguments $h_p$, $x_q$, and
  $z_i$ shown in Eq. 2. I find the expression hard to read at present.

- Definition 3.3 appears to state that structure-respecting node
  features are those features that are function of the $k$-hop graphs.
  Is this correct? If so, please provide this intuition in the
  definition; I found it confusing at first.

- What does it mean to be 'injective to the graph structures'? I can
  guess at the intent, namely that $f$ should map different $k$-hop
  graphs to different representations/features. Is this correct?

- I would not use the term 'organic node attributes' but rather discuss
  that certain graphs might already be equipped with node attributes.

- In l. 226--, a brief depiction of such graphs in the main text would
  be useful to make the paper more accessible to readers.

- Please also discuss the stability of your measure and method with
  respect to random samples. I found the section starting in l. 247
  very interesting; the statements made in it should also be empirically
  evaluated.

- When displaying results, such as in Table 1, consider sorting columns
  differently. I would find it more intuitive to *first* see the
  'original' accuracy obtained on the 'source' data set, whereas the
  *second* column could depict the 'target' data set.

- For Table 2, is 'EGI' also using a GIN architecture or a GCN? Please
  mention the architecture directly in the 'Method' column.

- Please provide more details on data set features in Table 2.

## Minor Comments

- I disagree with the in the related work that 'GNNs are not very
  complicated.' Maybe the convolutional layer can be seen as
  a comparatively simple construction, but I would rephrase or tone down
  this section slightly.

- For the discussion of graph kernels, the author may want to consider
  citing one of the recent surveys in this area, such as 'Graph Kernels:
  State-of-the-Art and Future Challenges ' by Borgwardt et al., 'A
  Survey on Graph Kernels' by Kriege et al., or 'Graph Kernels:
  A Survey' by Nikolentzos et al.

## Style & language

The language in this paper requires some improvements. I had trouble
understanding certain constructions, and I would suggest to rewrite them
in order to improve the accessibility of the paper. Here are some
suggestions:

- As an overall suggestion, I would like to point out that bibliographic
  citations can be sorted using the `sort` option of the `natbib`
  package, for instance. I find that this makes parsing citations
  a little bit easier.

- 'on the' appears twice in the caption of Figure 1

- 'its capability' --> 'their capability'

- 'none of existing' --> 'none of the existing'

- 'training objective is' --> 'training objectives are'

- 'set of $k$-hop ego graph' --> 'set of $k$-hop ego graphs'

- 'drawn with the joint distribution' --> 'drawn from the joint distribution'

- 'from empirical joint' --> 'drawn from an empirical joint'

- 'we now describes' --> 'we now describe'

- 'distinguish positive' --> 'distinguish a positive'

- 'make node-wise characterization' --> 'obtain node-wise characterizations'

- 'while also verify' --> 'while also verifying'

- 'hyper parameter' --> 'hyperparameter'

- 'apply them on' --> 'apply them to'

- 'parameters are freezing' --> 'parameters are frozen'

- 'are prune' --> 'are prone'

- 'structural different' --> 'structural differences'

- 'that vanishes the performance gaps' --> 'that removes [...]'

# Update after rebuttal

The authors provided numerous clarifications, which helped alleviate some of my initial concerns. I am therefore happy to raise my score accordingly.
limitations_and_societal_impact: Algorithmic limitations are partially discussed in this paper, but as
outlined above, an ablation study of the effects of changing parameters
and/or sampling frequency is crucial and needs to be included. In
addition, 'failure cases' of the algorithm would also be interesting to
discuss; are there specific graphs that turn out be easily transferable
but the framework is unable to assess this a priori?

There are no specific adverse societal impacts arising from this work.
The paper briefly mentions privacy aspects in pre-training data, but
this thought could be fleshed out more.
review_title: null

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

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

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