Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper introduces few-shot learning for graph classification. The authors propose a pre-training->fine-tuning approach to handle graph classes unseen at training time (and in only a few shots at test time).

At a high level, and to my understanding, their method a priori generates the ingredients for a graph of graphs, a "super-graph", in two steps: first, it discovers a prototype graph for each graph class in the dataset, then it clusters the prototype graphs into a set of super-classes by k-NN. Both of these operations rely on the spectral distance between graphs, defined in this work using the spectrum of a graph's normalized Laplacian matrix and the pth Wasserstein distance between probability measures. The intuition is that the super-graph built from these ingredients helps model latent relations between graph classes; these relations can be used at test time to improve classification of unseen graph classes.

During (pre-)training, the model builds super-graphs on each batch of data. It uses super-graph information in two ways: an auxiliary classification head (an MLP called C^sup) is trained to map graph embeddings to their corresponding super-class labels, and the super-graph itself, whose nodes are embeddings for individual graphs in the batch, passes through a graph attention network (GAT) that outputs a base class for each graph -- this is the classification head C^GAT. The graph embeddings themselves come from a feature extractor F_θ implemented as a graph isomorphism network (GIN).

During the fine-tuning stage the model adapts to and classifies graphs from classes unseen during training. Here the parameters of the feature extractor GIN and the C^sup MLP are frozen. C^sup outputs a set of super-class labels that are used to construct a super-graph, which in turn feeds into C^GAT, which in turn yields labels for the test graphs. C^GAT (but not the GIN or C^sup) fine-tunes on a small number q of labelled examples of each novel test class. The full model is evaluated on unlabelled examples from the novel test classes. This process assumes that the novel test graph classes belong to the same set of super classes as the training graph classes, a point that is, unfortunately, not discussed.

There's a lot to digest in this paper, on both the technical and architectural sides. There are graphs of graphs (super-graphs) and different GNN variants operating on both, with the output of one graph network, the feature extracting GIN, feeding into another, the GAT classifier. Understanding all of these pieces and how they fit together is challenging for the reader: I got lost somewhat in the Classifier description in Section 4, while Section 3 defines many things and gives some math that might be extraneous. It is also not immediately obvious that fine-tuning takes place on the set G_N and testing on the set G_U. Overall, though, the paper became clear to me with time and I found the overall presentation to be good. Some additional figures that depict the super-graph construction and clustering would be useful.

The construction and use of the super-graph structure to model relations between graph classes is interesting and novel to me, though it relies on well-established techniques (Wasserstein barycenters, Lloyd's algorithm for k-NN). The architecture itself, which combines GINs and GATs, is also novel to me; a downside is that it is highly complex.

Experiments were undertaken on two datasets and seem fairly thorough, with variance established on a high number of seeds (high in the deep learning literature). They demonstrate that the proposed method makes significant improvements over baselines. The baselines are somewhat limited because, as the authors state, "there do not exist any standard state-of-the-art methods for few-shot graph classification". However, I do not think the authors should be penalized for trying something new. On the other hand, given the novelty of the task, it would be nice to see an investigation/discussion of how few-shot graph learning differs from few-shot image learning (where there has been much more work).

I found the ablation and sensitivity studies illuminating, and I was pleased to see that the authors do support their claim that the super-graphs improve class separation over the feature extractor embeddings -- the GIN-k-NN baseline results provide evidence of this.

One place where I lack confidence in the results: I am not very familiar with the datasets used (TRIANGLES and Letter-High) nor how standard they are in the graph-learning literature. The authors do not even describe in the paper what the graph classes in these datasets actually are or represent, which would be good to know.

Overall, I think the paper is worth seeing and discussing at the conference, although it could be improved in various ways.

Minor errors:
- there appears to be bracket imbalance in eq.6
- "Lloyd's" is misspelled a few times

Reviewer's note: I have significant experience in few-shot learning but not in graph neural networks.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposed a few-shot graph classification algorithm based on graph neural networks. The learning is based on a large set of base class labeled graphs and a small set of novel class labeled graphs. The goal is to learn a classification algorithm over the novel class based on the sample from the base class and novel class. The learning process constitutes of the following steps. First, the base class is classified into K super classes based on the spectral embedding of the graph (onto distributions over the corresponding graph spectrum) and the k-means algorithm with the Wasserstein metric. Second, for each super class, the classification is done through a feature extractor and a classifier. In the training of the feature extractor and classifier, the author introduces a super-graph with each node representing a super class. Finally, in the fine-tuning stage, the feature extractor is fixed, and the classifier is trained based on the novel class.

This work seems to be the first attempt to adopt the few-shot learning in graph classification tasks. The architecture is novel, and the classification of graph based on spectral embedding together with the Wasserstein metric is novel to me.

I vote for rejecting this submission for the following concerns. 

1. The classification of base class into super classes seems questionable to me. In the meta-learning language, the author attempts to learn a good representation of graphs based on different graph classification tasks generated by a task distribution. In terms of graph classification, the task distribution is supported on the joint distributions (G, Y). Hence, to characterize different tasks, as far as I am concerned, the classification should take both the graph G and the label Y into consideration, instead of solely the graph.
 
2. Though seemingly very important to the architecture, the purpose of constructing the super-graph g^{sup} in the training of C^{CAT} seems to be unclear to me.  I would appreciate it if the author could provide more explanation on the introduction of the super-graph in training.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper introduces few-shot graph classification problem and proposes super-class based graph neural network (GNN) to solve it. Experiments on two datasets demonstrate that the proposed model outperforms a number of baseline methods. Some ablation study and analysis are also provided. Followings are my detail review. 

It is interesting for the authors to introduce few-shot graph classification problem which is meaningful. If I understood correctly, the authors use graph spectral distance to find prototype graph of each class, then employ prototype graph clustering to obtain super-classes, which are further fed to GNN as the joint optimization of super-class and regular class prediction. To me, the novelty is incremental. 

The authors use two new datasets for experiments due to the requirement of numerous class labels. I concerned about performances of different GNN baseline methods in Letter data due to small graph size (with 4.6 nodes in average). The context neighbor information is important for multi-layer GNN. Thus I could not fully judge the effectiveness of proposed model in this data. 

In Table 3, I found performance of proposed model with one super-class is still better than different GNN. I did get the point from this result. Why there is no performance decrease as all have the same super-class label? What is the model performance when removing super-class augmentation? I would like to see more discussion or experiment about this. 

Update: I am satisfied with author's response and raised my score. 
review_title: Official Blind Review #3

Meta-review: The authors propose a method for few-shot learning for graph classification. The majority of reviewers agree on the novelty of the proposed method and that the problem is interesting. The authors have addressed all major concerns.
Decision: Accept (Poster)