Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Considering graph few-shot learning, the paper proposes a method called GLITTER to learn node representations across different meta-tasks. 
In particular, GLITTER selects nodes according to their overall node influence on support nodes, learns edge weights in the task-specific structure based on node influence within classes and mutual information between query nodes and labels. The authors believe that these make the learned structures tasks-specific and consequently improve the node representations. 


strengths_and_weaknesses: The paper considers broader graph few-shot learning applications following GMeta. 
The results show clear improvement. 

However, this paper is confusing due to unclear motivation and claim. 
Please see my detailed comments in questions. 

questions: The key problem is that the authors fails to convince the readers why existing methods cannot learn task-specific structures. The authors should provide a clear definition for their believed task-specific structure. 

Indeed, in meta-learning, after the inner loop fine-tuning, the model and the node embeddings naturally become task-specific. In this sense, existing meta-learning works can learn task-specific structures. 
On line 5-6, the authors write that "these methods generally rely on the original graph (i.e., the graph that the meta-task is sampled from) to learn node representations". On line 39, the authors write that "Here each meta-task is often sampled from one single graph". 
Then, why this problem exists in multiple-graph setting? If the problem is that one should adjust the provided graph adaptively, why not using GAT [1] or recent graph structure learning methods [2-5]? Any difference or relevance w.r.t them? 

[1] Graph attention networks, ICLR, 2018 

[2] Few-shot learning with graph neural networks, ICLR, 2018

[3] Learning to propagate labels: Transductive propagation network for few-shot learning, ICLR, 2018

[4] Property-Aware Relation Networks for Few-Shot Molecular Property Prediction, NeurIPS, 2021

[5] Deep graph structure learning for robust representations: A survey, 2021


limitations: The authors did not discuss any limitations nor potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a method to select relevant nodes and learn desirable edge weights for each few-shot node classification task, so that the input graph structure is tailored for each task individually. Specifically, the method has three stages: 1) selecting nodes based on proximity to the support set nodes; 2) optimizing edge weights function such that the resulting node influence between support nodes in the same class is maximized; 3) optimizing edge weights function such that the mutual information n between query nodes and all labels in the task is maximized. Over the produced graphs, the authors then use a meta-optimization method based on MAML to learn and perform the few-shot tasks. Experiment results over diverse settings demonstrate the effectiveness of the method over various baseline methods.
strengths_and_weaknesses: # Strengths
- The proposed method is novel and well-motivated from practical and theoretical perspectives. However, it is worth noting that similar ideas have been explored and somewhat standardized in the link prediction literature following SEAL (https://proceedings.neurips.cc/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf), where a specific subgraph is selected for predicting the existence of an edge even in the standard (non few-shot) setting. Yet to my knowledge, the most popular methods of this kind simply select an enclosing neighborhood of the two end nodes based on simple heuristics (e.g. intersection of k hop neighborhoods). Therefore, this work is still more novel and sophisticated in the specific methods.
- The method can serve as a simple drop-in preprocessing step for various other methods, and it can potentially benefit tasks even outside few-shot setting or node classification setting. 
- The experiment is comprehensive and demonstrates empirical gains.
- The paper is clearly written overall.

# Weaknesses
- The experiment results have significant variance, making it less clear how significant the results are. It would be beneficial to confirm the gains with statistical tests.
- It seems computationally intensive to precompute and extract subgraphs for each task. 
 
questions: - Is the training of edge weight function using the two objectives completed before the meta-optimization? Or how are they blended together?
- It would be beneficial to confirm the performance gains with statistical tests due to the high variance.
- What is computational overhead with this method over using MAML on the full graphs directly? 
limitations: The limitations are adequately addressed in the paper other than the ones mentioned above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes an improved MAML algorithm that tailors node representation to specific meta-tasks. The result is a significant performance improvement across meta-tasks.
strengths_and_weaknesses: [S] The problem is well-motivated and relevant to the research community. The proposed algorithm seems interesting and novel, while the approach intuitive.

[S] The performance improvements observed are significant compared to the baselines.

[W] The terminology is rather hard to follow in the beginning, especially before reading the introduction to the problem.

(comment) The attached code is extremely counterintuitive and messy, even for research code. I had a hard time trying to clarify some computational aspects of the paper for myself.
questions: How does the node influence in the paper relate to the field of graph influence maximilation? It seems that the definition, stripping the GNNs from it, is quite similar to the one of Kempe et al., 2003.

What is the computational complexity of the distance computations, during training and for a new task?
limitations: Limitations and societal impact are addressed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors have proposed a new mechanism to learn **task-specific** structure for each meta-task under the problem setup of few-shot node representation learning. The intuition behind the idea is clear in that the node representations should be learned in compliance with the structure of the meta-task being considered. As the authors mention, its evident that the entire graph is not necessarily useful since it may contain a substantial amount of redundant information, especially since each meta-task usually has a small number of nodes (this may not be the case when the graph at hand is small, nevertheless, most of the real world are much larger compared to the size considered in the experiments). Furthermore, the authors suggest that the edge weights over the task-specific structure should also be learned in a task-specific manner. The proposed methodology seeks to answer two questions in particular - (i) how to select relevant nodes for the task specific structure and (ii) how to compute the edge weights for the task specific structure. To answer the first question, the authors derive an approximation based on the “influence” of one node embedding to another and give a lower bound to the expected value of this influence across the nodes in a class in terms of the “shortest path distance” (SPD) amongst the nodes. Based on the SPD criterion, the authors have proposed two simple strategies to sample the nodes - local and common sampling. To answer the second question, the authors compute the edge weights as a combination of two different terms obtained using - node representations and SPD between the two given nodes. To further assist the learning process of the task-specific structures, the authors propose 2 loss functions based on the - (i) label information of the support set nodes and (ii) mutual information between the query nodes and their estimated / potential labels. For the first one, a loss function that enforces the maximization of the similarity within classes along with the minimization of the similarity between classes, is proposed (eq 4 of the main paper). For the second one, the maximization of mutual information is suggested. The optimization of the model is performed via MAML. Experiments on multiple popular benchmarks and comparison against state of the art baselines demonstrates that the proposed approach indeed performs very well. Although, there are several concerns regarding the theoretical analysis, as elaborated below.				
strengths_and_weaknesses: 1. The empirical evidence of the efficacy of the proposed method is strong. All the results in tables 2 and 3 indicate that the model outperforms the baselines by substantial margins on both - multi graph and single graph settings.
2. The result of the ablations in figure 2 also explicitly demonstrate the utility of each of the 3 main components of the proposed method. The explanations provided in lines 322-332 of the main paper are also inline with the demonstrated results. 
3. The authors haven’t provided sensitivity analyses for many important hyperparameters, such as - the value of $C$ in common sampling, value of $h$ in local sampling, value of $m$ in eq 6 etc. I believe such analyses are important to further interpret the proposed solution better.
4. I believe that the authors should also provide some qualitative results along with the quantitative evidence. For eg - constructing t-SNE (or any other) plots showing the class wise separation over the embeddings of the penultimate layer can be a useful analysis of the learned embeddings. This can be done for the proposed method and the best performing baseline. Similarly, some analysis of the “average size of the task-specific graph structure” will be useful. Additionally, some plots for the “performance-runtime” concerning the proposed method and the best performing baseline will provide an interesting tradeoff analysis.
5. Notational problems in eq 6 of the main paper - $j$ is the class label.
6. Definition 1 (in the main paper) as well as the proof of Lemma A.1 (appendix) have multiple notational problems: (i) The layer indexing for $h_i$ and $h_j$ are missing. From the proof, it's evident that the authors have considered layer recursion upto the shortest path length between $i$ and $j$; (ii) $d$ and $\bar{d}$ are the same. $\bar{d}$ is not defined in the statement of Lemma A.1
7. Eq 6 in the appendix hasn’t used Jensen's inequality properly in the first comparison. 
8. Multiple problems in proof of theorem 3.2, following the concerns above about the layer indexing and the entire proof sketch thereof. The assumption that the expected value of each $I_{ij} = \frac{1}{n-1}$ since the sum of probabilities of all paths starting from $v_{i}$ equals 1, is extremely loose.
9. It will be useful to compute the value of the constant $C$ in theorem 3.4, since it seems to follow the order of $t^{h}$ (computing its upper bound might be easier than the actual value)

questions: 1. The authors have explicitly focused on selecting nodes for learning task-specific structures, conditioned on the support set. While this is a perfectly sound method, why haven’t the authors considered the same for the query set nodes? Even if a single node is present in the query set, the same proposed mechanisms might help expand the subgraph around the query set node to tackle bottlenecks, particularly oversquashing, as well as densify the graph in certain cases (on average), to prevent under reaching from the nodes in the set $\mathcal{V_T}$ \ $\mathcal{Q}$. Moreover, the first limitation mentioned by the authors in appendix (lines 177-180) can potentially be addressed via a similar mechanism. It will be interesting to hear the authors’ opinion about this point. 
2. What specific GNN architecture has been used to obtain node representations in the proposed model?
3. Can the authors provide more details on how the hyperparameters are selected? Are these searched over some space or selected based on previous works?
4. The improvements suggested in section F.3 (appendix), although simple, can be utilized in cases where the scalability is not an issue. Although the statement - “Nevertheless, such a strategy is not suitable for the multiple-graph setting, since learning GNNs across different graphs can lead to suboptimal performance” - lines 204-206 in appendix, isn’t compelling. Why do the authors mention that learning one, or infact multiple GNNs can be suboptimal? These GNNs can learn the original graph structures and provide useful auxiliary information.

limitations: I commend the authors for explicitly stating some of the main limitations of the approach. A question regarding the first limitation (lines 177-180) has also been raised above. I strongly suggest the authors to explicitly elaborate the GNN architecture that has been used in the experiments, as there could be potential concerns regarding the architecture used. I have **serious** concerns regarding the theoretical analysis, as mentioned above. Lastly, I don’t see any serious negative societal impacts of the work.
review_title: null

Meta-review: metareview: The paper attempts to improve few shot learning over graphs. In this regards, the authors propose a multi-stage approach where first relevant nodes is identified and desirable edge weights is learnt for each few-shot node classification task, so that the input graph structure is tailored for each task individually. This proposed method is based on insights from theoretical analysis. Experiments are carried to show the proposed method is more effective over some baseline methods. We thank the authors and reviewers for actively engaging in discussion and taking steps towards improving the paper including for providing additional experiments. Some concerns about theoretical analysis remain on interaction of influence between nodes and layers and would be nice to discuss in the final version.

Other minor fixes:
- Line 23 in appendix typo: fix partial latex symbol
- Eq 6 below line 38: First equality should be inequality
confidence: Less certain
Decision: Accept