FEW-SHOT LEARNING ON GRAPHS VIA SUPER-CLASSES BASED ON GRAPH SPECTRAL MEASURES
Authors: Jatin Chauhan
Deepak Nathani
Manohar Kaul
Venue:  (2020)
Keywords: Few shot graph classification
graph spectral measures
super-classes

Abstract: We propose to study the problem of few-shot graph classification in graph neural networks (GNNs) to recognize unseen classes, given limited labeled graph examples. Despite several interesting GNN variants being proposed recently for node and graph classification tasks, when faced with scarce labeled examples in the few-shot setting, these GNNs exhibit significant loss in classification performance. Here, we present an approach where a probability measure is assigned to each graph based on the spectrum of the graph’s normalized Laplacian. This enables us to accordingly cluster the graph base-labels associated with each graph into super-classes, where the L^p Wasserstein distance serves as our underlying distance metric. Subsequently, a super-graph constructed based on the super-classes is then fed to our proposed GNN framework which exploits the latent inter-class relationships made explicit by the super-graph to achieve better class label separation among the graphs. We conduct exhaustive empirical evaluations of our proposed method and show that it outperforms both the adaptation of state-of-the-art graph classification methods to few-shot scenario and our naive baseline GNNs. Additionally, we also extend and study the behavior of our method to semi-supervised and active learning scenarios.

Published as a conference paper at ICLR 2020
FEW-SHOT LEARNING ON GRAPHS VIA SUPER- CLASSES BASED ON GRAPH SPECTRAL MEASURES
Jatin Chauhan, Deepak Nathani, Manohar Kaul Department of Computer Science Indian Institute of Technology Hyderahad {chauhanjate i n100, deepakn manohar. gmail 1 coom
ABSTRACT
We propose to study the problem of few-shot graph classification in graph neu- ral networks (GNNs) recognize unseen classes, given limited labeled graph examples. Despite several interesting GNN variants being proposed recently for node and graph classification tasks. when faced with scarce labeled examples the few-shot setting, these GNNs exhibit significant loss in classification perfor- mance. Here, we present an approach where probability measure assigned to each graph based on the spectrum of the graph's normalized Laplacian. This enables us to accordingly cluster the graph base-labels associated with each graph into super-classes, where the L" Wasserstein distance serves our underlying dis- tance metric. Subsequently, a super- super-graph constructed based on the super-classes is then fed to our proposed GNN framework which exploits the latent inter-class relationships made explicit by the super-graph to achieve better class label sep- aration among the graphs. We conduct exhaustive empirical evaluations of proposed method and show that it outperforms both the adaptation of state-of- the-art graph classification methods to few-shot scenario and our naive baseline GNNs. Additionally, we also extend and study the behavior of our method to semi-supervised and active learning scenarios.
INTRODUCTION
The need to analyze graph structured data coupled with the ubiquitous nature of graphs (Borgwardi (ct al. 2005 Duvenaud et al. 2015 Backstrom & Leskoved 2010 Chau et al. 2011). has given greater impetus research interest in developing graph neural networks (GNNs) (Defferrard et al. 2016 Kipf & Welling 2016 Hamilton et al. 2017] Velikovi et al. 2018) for learning tasks on such graphs. The overarching theme in GNNs is for each node's feature vector to be generated by passing, transforming, and recursively aggregating feature information from a given k-hop neighborhood surrounding the node. However, GNNs still fall short in the "few-shot" learning setting, where the classifier must generalize well after seeing abundant base-class samples (while training) and very few (or even zero) samples from a novel class (while testing). Given the scarcity and difficulty involved with generation of labeled graph samples, it becomes all the more important to solve the problem of graph classification in the few-shot setting.
Limitations and challenges: Recent work by Xu et. al. (Xu et al. 2019) indicated that most recently proposed GNNs were designed based on empirical intuition and heuristic approaches. They studied the representational power of these GNNs and identified that most neighborhood aggregation and graph-pooling schemes had diminished discriminative power. They rectified this problem with the introduction of novel injective neighborhood aggregation scheme, making it strong as the Weisfeiler-Lchman (WL) graph isomorphism test (Weisfeiler & Leman 1968).
Nevertheless, the problem posed by extremely scarce novel-class samples in the few-shot setting remains to persist as a formidable challenge, as it requires more rounds of aggregation to affect larger neighborhoods and hence necessitate greater depth in the GNN. However, when it comes to GNNs, experimental studies have shown that an increase in the number of layers results in dramatic performance drops in GNNs (Wu al. 2019 Li et al. 2018b).

---

Published as a conference paper at ICLR 2020
Our work: Motivated by the aforementioned observations and challenges, method does the following. We begin with a once-off preprocessing step. We assign a probability measure to each graph, which refer to graph spectral measure (similar to (Gu et al. 2015)), based on the spectrum of the graph's ' normalized Laplaciin matrix representation. Given this metric space of graph spectral measures and the underlying distance the T.² Wasserstein distance, compute Wasserstein barycenters (Agueh & Carlier (01I)) for each set of graphs specific to base class and term these barycenters as prototype graphs. With this set of prototype graphs for each base class label, we cluster the spectral measures associated with each prototype graph in Wasserstein space to create a super-class label.
Utilizing this super-class information, we then build a graph of graphs called syper-graph. The intuition behind this is to exploit the non-explicit and latent inter-class relationships between graphs via their spectral measures and use a GNN on this to also introduce relational inductive bias (Battaglia et al., 2018), which in turn affords us an improved sample complexity and hence better combinatorial generalization given such few samples to begin with.
Given, the super-classes and the super-graph, we train our proposed GNN model for few-shot learn- ing on graphs. Our GNN consists of graph isomorphism network (GIN) Xu et al. (2019) feature extractor (.).) to generate graph embeddings, on which subsequently acts our classifier C(.) comprising of two components: (i) Csup; MLP layer to learn and predict the super class as- sociated to a graph, and (ii) CGAT; a graph attention network (GAT) to predict the actual class label of graph. The overall loss function is sum of the cross-entropy losses associated with Csup and GGGAT We follow initialization based strategy (Chen et al. 2019), with a training and fine-tuning phase, so that in the fine-tuning phase, the pre-trained parameters associated with F.(.) and Csup are frozen, and the few novel labeled graph samples are used to update the weights and attention learned by CGAT.
To the best of our knowledge, we are the first to introduce few shot learning on graphs for graph classification. Next, we propose an architecture that makes use of the graph's spectral measures to generate set of super-classes and super-graph to better model the latent relations between classes, followed by our GNN trained using an initialization method. Finally, we conduct extensive experiments to gain insight into our method. For example, in the 20-shot setting on the TRIANGLES dataset, our method shows a substantial improvement of nearly 7% and 20% over DL-based and unsupervised baselines, respectively.
Our contributions:
2 RELATED WORK
Few-shot learning in the computer vision community was first introduced by (Fei-Fei et al. 2006) with the intuition that learning the underlying properties of the base classes given abundant samples can help generalize better to unseen classes with lawelebeled samples available. Various learning algorithms have been proposed in the image domain. among which a broad category of initializa- tion based methods aim to learn transferable knowledge from training classes, so that the model can be adapted to unseen classes with limited labeled examples (Finn et al., 2017]; (Rusu et al., 2018); (Nichol et al. 2018). Recently proposed and widely accepted Initialization based methods can broadly be classified into: (i) methods that learn good model parameters with limited labeled examples and small number of gradient update steps (Finn al. (017) and (ii) methods that learn an optimizer (Ravi & Larochelle, 2017). We refer the interested reader to Chen et. al. (Chen et al. 2019) for more examples of few-shot learning methods in vision.
Graph neural networks (GNNs) were first introduced in (Gori et al.. 2005): (Scarselli et al., 2009) as recurrent message passing algorithms. Subsequent work (Bruna et al.. 2014); (Henaff et al., 2013) proposed to learn smooth spectral multipliers of the graph Laplacian, but incurred higher computational cost. This computational bottleneck was later resolved (Defferrard et al.) 2016): (Kipf & WWlling 2016) by learning polynomials of the graph Laplacian. GNNs are natural extension to Convolutional neural networks (CNNs) on non- non-Euclidean data. Recent work (Velikovi et al.) 2018) introduced the concept of self-attention in GNNs, which allows each node provide attention to the enclosing neighborhood resulting in improved learning. We refer the reader to (Bronstein et al. 2016) for detailed information on GNNs.
2

---

Published as a conference paper at ICLR 2020
Despite all the success of recent attempts have focused on solving the few-shot learning on graph data where GNNs are either trained via co-training and self-training (Li et al. 2018a), extended by stacking transposed graph convolutional layers imputing a structural regularizer (Zhang et al., 2019) however, both these works foeus only on the node classification task.
classification remains under-addressed problem. Some
To the best of our knowledge, there does not exist any work pertaining few-shot learning on graphs focusing on the graph classification task, thus providing the motivation for this work.
Comparison to few-shot learning on images: Few shot learning (FSL) has gained wide-spread traction in the image domain in recent years. However the success of FSL in images is not eas- ily translated to the graph domain for the following reasons: (a) Images are typically represented in Euclidean space and thus can easily be manipulated and handled using well-known metrics like cosine similarity, Ip norms etc. However, graphs come from non- non-Euclidean domains and exhibit much more complex relationships and interdependency between objects. Furthermore, the notion of a distance between graphs is also not straightforward and requires construction of graph kernels or the use of standard metrics on graph embeddings (Kriege et al. 2019). Additionally, such graph kernels dont capture higher order relations very well. (b) In the FSL setting images, the number of training samples from various classes is also abundantly more than what is available for graph datasets. The image domain allows training generative models to learn the task distribution and can further be used to generate samples for data augmentation, which act as very good priors. In contrast, graph generative models are still in their infancy and work in very restricted settings. Furthermore, methods like cropping and rotation to improve the models can't be used for graphs given the per- mutation invariant nature of graphs. Additionally, removal of any component from the graph can adversely affect its structural properties, such as in biological datasets. (c) The image domain has very well-known regularization methods (e.g. Tikhonov, Lasso) that help generalize much better to novel datasets. Although, they dont bring any extra supervised information and hence cannot fully address the problem of FSL in the image domain. To the best of our knowledge, this is still an open research problem in the image domain. On the other hand, in the graph domain, our work would be a first step towards graph classification in an FSL setting, which would then hopefully pave the path for better FSL graph regularizers.
(d) Transfer learning has led to substantial improvements on various image related tasks due to the high degree of transferability of feature extractors. Thus, downstream tasks like few-shot learning can be performed well with high quality feature extractor models, such as Resnet variants trained on Imagenet. Transfer learning, or for that matter even good feature extractors, remains a daunting challenge in the graph domain. For graphs, there neither exists a dataset which can serve as a pivot for high quality feature learning, nor does there exist a Graph NN which can capture the higher order relations between various categories of graphs, thus making this a highly challenging problem.
PRELIMINARIES
In this section, we introduce our notation and provide the necessary background for our few-shot learning setup on graphs. We begin by describing the various data sample types, followed by our learning procedure, in order to formally define few-shot learning on graphs. Finally, we define the graph spectral distance between a pair of graphs.
Data sample sets: Let G denote a set of undirected unweighted graphs and ) be the set of associated class labels. We consider two disjoint populations of labeled graphs consisting of i.i.d. graph sam-
ples, the set of base class labeled graphs GB = ((g .y, ) and the set of novel class labeled
(B) (B)
E Y)N) Here, the set of base and novel class labels are denoted by ()B [l...., . K} and yyM) +K+ ..... K'), respectively, where K' > K. Both ()) and ((() are disjoint subsets of y, so, ( (M)) 0.
graphs GN = (( ..!
(())))= v= where g. Di (N)
&G. y (B)
E ((B), and y; (N)
Note that m < n. i.e., there are far fewer novel class labeled graphs compared to the base class labeled ones. Besides GB and GN we consider a set of t unlabeled unseen graphs Gu := (U) (U)
(01 (U) It 1 E (G =1 1....), l). for testing
We use the notation Tı (p) and (2) to denote the left and right projection of an ordered pair p. respec- tively.
3

---

Published as a conference paper at ICLR 2020
Learning procedure: Inspired by the initialization based methods, similarly follow two-stage approach of training followed by fine-tume fine-tuning.
During training, we train graph feature extractor F6 FG(BB) with network parameters 0 followed by a classifier C(GB) on graphs from GB. where the loss function is the standard cross-entropy loss Le. In order to better recognize and generalize well samples from novel classes, in the fine- tuning phase, the pre-trained feature extractor (- along with its trained parameters is fixed and the classifier C(Gx) is trained the novel class labeled graph samples from Gn. with the same loss Le.
Now, given the classification of data samples and the two-stage learning method, our problem of few-shot classification on graphs can be defined as follows.
Problem definition: Given n base-class labeled graphs from GB during the training phase and m novel-class labeled graphs from GN during the fine-tuning phase, where m < n, the objective of few-shot graph classification to classify unseen test graph samples from Gy. Moreover, m qT" where T = K' K, i.e. each novel class label appears exactly q times in GN, then this setting is referred to as the g-shot, T Twway learning.
Graph spectral distance: Let us consider the graphs in G. The normalized Laplacian of graph E G is defined as A, 1 AD1/22 where A and D are the adjacency and the degree matrices of graph 9: respectively. The set of eigenvalues of Ag given by {M is called the spectrum of Ag and is denoted by (g). It is well known that the spectrum (g)) of normalized Laplacian matrix contained interval [0, 2]. We assign Dirae mass 6x, concentrated on each X E (g), thus associating probability measure to (g) supported on [0, 2]. called the graph spectral measure Mo(g). Furthermore, let P([O, 2|) be the set of probability measures on interval [0, 2].
We now define the p-th Wasserstein distance between probability measures, which we later use to define the spectral distance between a pair of graphs.
Definition Let p E (o) and let e [0.2] x [0. 2| + [0, +oo be the cost function between the probability measures p.v P([O,2] 2)). Then the p-th Wasserstein distance between measures μ and u is given by
Wv(,,
inf
clx, (),,)) I(a,
[0,2)x
where U1(,, v) is the set of transport plans, i.e., the collection of all measures on [0, 2] x [0, 2] with marginals μ and v.
Given the general definition of the p-th Wasserstein distance between probability measures and the graph spectral measure, we can now define the spectral distance between pair of graphs in G.
Definition Given two graphs g.g6 E G. the spectral distance between them is defined as
WP(g.g') = Wp (Horg)) Po(a'))
In words, (P(g, (') is the optimal cost of moving mass from the graph spectral measure of graph g to that of graph g', where the cost of moving unit mass is proportional the p-th power of the difference of real-eigenvalues in interval [0, 2
4 OUR METHOD
We present our proposed approach here. First, given abundant base-class labels, we cluster them into super-classes by computing prototype graphs from each class, followed by clustering the prototype graphs based their spectral properties. This clustering of prototype graphs induces natural clustering on their corresponding class labels, resulting in super-classes (as outlined in Section 4.1
In practice, extremely fast computation of (P g') is achieved using regularized optimal transport (OT) Genevay al.] 2016), which makes use of the Sinkhorn algorithm.
4

---

Published as a conference paper at ICLR 2020
Training stage
Fine-tuning stage
Base class graphs
Novel class graphs
Fixed weights
Classifier
Super-class Classifier
Feature extractor
Csup
Festure extractor
Cuup
GB
Fe
tou Y
G
Fe
Y
(GAI
GAT 2
m <
Tpnennpppineer weights in
Figure 1: The training (left) and fine-tuning (right) stages of our GNN.
These super-classes are then used in the creation of super-graph used further down by GNN. Note that creation of super-classes, followed by building a super-graph are once-off process. The prototype graphs well the super-classes for the base classes can be stored in memory for further use.
Next, explain graph neural network's architecture which comprises of feature extractor Fo(.) and a classifier C(.), described Section 4.2 The classifier C(.) is further subdivided into a classifier Ceup that predicts the superclass of graph feature vector and graph attention network (GAT) CA to predict the graph's class label. Figure illustrates the training and fine-tuning phases of GNN.
4.1 COMPUTING SUPER CLASSES
In order to exploit inter-class relationships between base-class labels, cluster them in the follow- ing manner. First, partition the set Gn into class-specife, sets (1), for i = 1... K, where G the set of graphs with base-class label i. Thus, GB L G().
Then, we compute class prototype graphs for each dlass-specific set. The class prototype graph for class i represented by p; is given by
(G
p: argmin
W (g.
giEm (G3) G
Essentially, the class prototype graph p; for the i-th class is the graph with the least average spectral distance to the rest of the graphs in the same class. Given these K prototypes, cluster them using Lloyd's method (also known as k-means] [
Clustering prototype graphs: Given unlabeled prototypes Pi.....PP PK E wi (GB) and their associated spectral measures Ma(pi))... : Ma(pk) E P[[0, 2)). We rename the spectral measures as 8K to ease notation. Thus, our goal is associate these spectral measures to at most is user defined parameter.
$1 clusters, where
The k-means problem finds k- k-partition (Ci,..., C that minimizes the following objective that represents the overall distortion enror of the clustering
argmin C
Σ
Wp B(C,))
S.EC
where is prototype graph in cluster C₁ and B(C,) is the Wasserstein barycenter of the cluster Ct. The barycenter is computed
ICal
B(C,)
argmin peP((
s(.,)((i.)))
(3)
We used the seeding method suggested in k-means++ Arthur & Vassilvitskii 2007

---

Published as a conference paper at ICLR 2020
Wasserstein Prototype
Graph Spectra
Oass
Clsa
Prototppe
Vasseesteiin
Class
Protocype
Spectral Distance
K-Means SpectralClustaring
Super
Groph
Super Claca
Poteiam
Protsrye
Figure 2: illustration of our proposed Wasserstein super-class clustering algorithm.
where j) denotes the j-th spectral measure in the i-th cluster C..
Lloyd's algorithm: Given an initial set of Wasserstein barycenters B() (Cx) of spectral measures at step & 1, one uses the standard Lloyd's algorithm to find the solution by alternating between the assignment (Equation 4 and update (Equation [ steps
c²a) ={sp- Wp(sp. (C,) S Wppsp, (C,),
(4)
-(t+1)= = B(
(5)
Lloyd's algorithm known to converge to a local minimum (except in pathological cases, where can oscillate between equivalent solutions). The final output is a grouping the prototype graphs into k groups, which also induces grouping of the corresponding base classes. We denote these class groups as super-classes and denote the set of super-classes as ysup.
4.2 OUR GRAPH NEURAL NETWORK
Feature extractor: To apply standard neural network architectures for downstream tasks we must embed the graphs in finite dimensional vector space. We consider graph neural networks (GNNs) that employ the following cressage-passingg architecture
H ((A HU-1) ((d)
where HD) E V are the node embeddings (i.e., messages) computed after steps of the GNN and M is the message propagation function which depends on the adjacency matrix of the graph A, the trainable parameters of the jth layer g(1), and node embeddings Hú-11 generated from the previous step.
recently proposed GNN called the graph isomorphism network (GIN) by Xu et al. 2019 was shown to be stronger than several popular GNN variants like GCN Kipf & Welling (016) and GraphSAGE) Hamilton /aait/amitHaoono et al.) (2017). What makes GIN so powerful and sets apart from the other GNN variants is its injective neighborhood aggregation scheme which allows it to be powerful as the Weisfeiler-Lchman (WL) graph isomorphism test. Motivated by this finding, we chose GIN as graph feature extractor. The message propagation scheme in GIN is given by
H = MLP((1 + o Hú-1) + AT H(-0)
(6)
Here, c is layer-wise learnable scalar parameter and MLP represents multi-layer perceptron with layer-wise non-linearities for more expressive representations. The full GIN model run iterations of Equation to generate final node embeddings which we represent by (R), As features from earlier iterations can also be helpful in achieving higher diseriminative power, embeddings H()

---

Published as a conference paper at ICLR 2020
from all R. iterations concatenated as
R Hg
H
Here, H() = Evev HD), where H!) represents the i-th node's embedding in the j-th iteration and || denotes a concatenation operator. Hg now contains the graph embedding of a graph g and is passed to the classifier.
Classifier: Here, our objective to improve the class separation produced by the graph embeddings of the feature extractor (.) and we do this by building a "graph of graph embeddings", called super-graph gruP, where each node is graph feature vector. We then employ our classifier C(.) on this super-graphe to achieve better separation among the graph classes in the embedding space.
During training, we first build the super-graph gr"P on batch of base-labeled graphs as collection of k--N graphs, where each constituent k-NN graph is built on the graphs belonging the same super-class. gd is then passed through multi-layered graph attention network CGAT to learn the associated class probabilities. The features extracted from Fo(.) are passed into the MLP network Csup to learn the associated super-class labels. Csup and CGGAT combine to form our classifier C()). The cross-entropy losses associated with Croup and CGAT are added to give the overall loss for C()). The intuition behind the construction of goup to train CGAT on was to further improve the existing cluster separation based on graph spectral measures by introducing a relational inductive bias (Battaglia et al. 2018) that is inherent to the GNN CGAT
Recall that we adopt an initialization method (described in 3). In our fine-tuning stage, novel class labeled graphs from GN input to the network. The pre- traitedd parameters learned by the feature extractor (-) are fixed and Coup is used to infer the novel graph's 's super-class label, followed by creation of super-graph on the novel graph samples and finally updating the parameters in CGAT through the loss. Finally the evaluation is performed on the samples from the unseen test set Gu.
Discussion: We make the assumption that the novel test classes belong to the same set of super-classes from the training graphs. The reason being that the novel class labeled samples are so much fewer than the base class labeled samples, that the resulting super-graph ends up being ex- tremely sparse and deviates lot from the shape of the super-graph from the base classes; therefore it severely hinders CGAT's s ability to effectively aggregate information from the embeddings of the novel class labeled graphs. Instead, we pass the novel graph samples through our trained Crup and infer its super-class label and this works very effectively for us, as is evidenced by our empirical results.
5 EXPERIMENTAL RESULTS
5.1 BASELINES AND DATASETS
The standard graph classification datasets do not adequately satisfy the requirements for few-shot learning due to the dearth of unique class labels. Hence, we pick four new classification datasets, namely, Letter-High, TRIANGLES, Reddit-12K, and ENZYMES. The details and statistics for these datasets are given in Appendix A. As there do not exist any standard state-of-the-art methods for few-shot graph classification, we chose existing baselines for standard graph classification from both supervised and unsupervised methods.
For supervised deep learning baselines, we chose- GIN (Xu et al. (2019)), CapsGNN (Xinyi & Chen (2019), and Diffpool (Lee al. (2019).. We ran these methods with similar settings as ours, i.e., by partitioning the main model into feature extraction and classifier sub-models to compare them in a fair and informative manner. From the unsupervised category, we consider 4 powerful SOTA methods- AWE (Ivanov & Burnaev (2018)). Graph2 (Narayanan et al. (2017)). Weisfeiler- Lehman subtree Kernel (Shervashidze et al. (201T)), and Graphlet count kernel (Shervashidze et al. ). Since want to analyze the fho-shot classification abilities of these models, essentially want to find out how well these algorithms can achieve class separation. We use N-NN search on the output embeddings of these algorithms.
7

---

Published as a conference paper at ICLR 2020
Table 1: Results for various few-shot scenarios on Letter-High and TRIANGLES datasets. The best results are highlighted in bold while the second best results are underlined.
Method
Letter-High 10-shot
TRIANGLES
5-shot
20-sbot
5-sbot
10-shot
20-shot
WL.
65.27 = 7.67
68.39 19:39:24 4.09
72,69 + 3.02
51.25 = 4.02
53.26 + 2.95
57.74 = 2.88
Gruphiet
33.76 6.94
37.59
4.60
41.11 3.71
40.17 1: 3.18
43.76
3.09
45.90
1: 2.65
AWE
40.60 3,91
42.20
2.87
43.12 +: 1.00
39.36 3.85
42.58 +: 3.11
44.98
1.54
Groph2Vee
66.12 + 5.21
68.17 + 4.26
70.28 + 2.81
48.38 + 3.85
50.16
1.00-4411 4.15
$4,90
+ 3.01
Diffpoot
CapAGNN
56,60 1: 7.86
60.67 1. 5.24
63.97 1. 3.69
65.40 6.13
68.37 1. 3.67
73.06 1. 3.64
GIN
7.17
5.14
2.17
4.35
72.55
1.97
GIN-K-NN
63.52 7.27
4.45
3.94
61.55 3.19
63.45
2.76
OurMethod-GGN
68.69 + 6.50
72,80 + 4.12
75.17 + 3.11
69.37 + 4.92
73.11 + 3.94
77.86 + 2.84
OurMethod-GAT
5.90
1.58
71.40
Further configuration and implementation details for the baselines can be found in Appendix A.2 We also emphasize the benefit of using GNN as classifier by showing the adaptation of model to semi-supervised fine-tuning (in Appendix A.5) and active learning (in Appendix A.6 settings.
5.2 FEW-SHOT RESULTS
We consider two variants of our model as naive baselines. In the first variant, replace GAT classifier with GCN Kipf & Welling (2016). We call this model OurMethod-GCN, This variant is used justify the choice of GAT over GCN.
In the second variant, we replace the entire classifier with the k-NN algorithm over the features extracted from various layers of the feature extractor. We call this variant GIN-K-NN and this is introduced to emphasize the significance of building super- grper-graphhee and using a GAT on it as classifier to exploit the relational inductive bias.
The results for all the datasets in various s-shot scenarios, where E {5, 10, 20} are given in Table We run each model 50 times and report averaged results. every run, we select different novel labeled subset GN for fine-tuning the classifiers of the models. The evaluation for all models is done by randomly selecting subset of 500 samples from the testing set GD for Letter-High and TRIANGLESS whereas over 150 for ENZYMES and 300 for Reddit dataset and averaging over 10 such random selections.
Table 2: Results for various few-shot scenarios on Reddit-12K and ENZYMES datasets. The best results are highlighted in bold while the second best results are underlined.
Method
Reddit-128 12K
ENZYMES
5-shot
10=shot
20-shot
5-4bot
[0-shot
20-sho
WL
40.26 + 5.17
42.57 + 3.69
44.41 + 3.43
55.78 = 4.72
58.47 2 3.84
60.1 = 3.18
Gruphiet
3.79
AWE
30.24 2.34
33.44
+ 2.04
36.13 +: 1.89
43.75 4 1.85
45.58
+ 2.11
49.98
+ 1.54
Groph2Vee
27.85 4.21 4.21
29.97
3.17
32.75
55.88 - 4.86
58.22
+ 4.30
62.28
4.14
Difspoot
35.24 1: 5.66
37.43
1: 3.94
39.11
3.52
45.64 1: 4.56
49.64
4.23
54.27 1: 3.94
CapsGNN
36.58 2 4.28
39.16
3.73
41.27
3.12
52.67 + 5.51
55.31
+ 4.23
59.34
4.02
GIN
GIN-E-NN
41.31 1.1122880 2.84
43.58
+ 2.80
45.12
$7.24 =: 7.06
59.34 +: 5.24
60.49 = 3.48
OurMethod GCV
40.77
4.32
44.28
3.86
48.67
4.22
$4.34 1: 5.64
56.16
4.39
60.86 1: 3.74
OurMethod-GAT
41.59
4.12
45.67
3.68
50.34
2.71
55.42 5.74
60.64 +: 3.84
62.81 3.56
The results clearly show that our proposed method and its GCN variant (i.e., OurMethod-GCN outperform the baselines. GIN-K-NN shows significant degradation in results on nearly all the three paradigms for datasets with exceptions on 5-shot and 10-shot on ENZYMES dataset, thus strongly indicating that the improvements of our method can primarily be attributed to our GNN classifier fed with the super- graph constructed from our proposed method. The improvements in results are higher on TRIANGLES and Reddit datasets in contrast Letter-High and ENZYMES, which can be attributed to the smaller size of the graphs in Letter-High making it difficult to distinguish based on graph spectra alone, whereas the complex and highly inter-related structure of enzymes makes it dif-
8

---

Published as a conference paper at ICLR 2020
(a) Our Method-GAT
(b) GIN
(c) WL Kernel
Figure 3: Visualization: t-SNE plots of the computed embeddings of test graphs 20-shot scenario from OurMethod-GAT (left), GIN (middle) and WL Kernel (right) on TRIANGLES dataset. The embeddings for both our model and GIN taken from the final layers of the respective models.
ficult for the DL based feature extractors well as the graph kernel methods to segregate the classes in the feature and graph space respectively. GIN and WL show much better results as compared to other baselines for all the q-shot scenarios, whereas AWE and Graphlet Kernel show significantly low results, unable to capture the properties of the graphs well. The DL baselines apart from GIN on the other hand show improvements on the TRIANGLES dataset performing close to GIN, where the unsupervised methods fails to capture the local node properties, however still perform poorly on other datasets. For the 20-shot scenario on TRIANGLES, our GAT variant shows an improvement of around 7% over DL. baselines and more than 20% when compared to unsupervised methods. The substantial improvements of around 4% on Reddit dataset shows the superiority of our model for both the variants GAT and GCN. Furthermore, the t-SNE plots in Figure show substantial and interesting separation of class labels which strongly indicate that a good feature extractor in con- junction with GNN perform well as a combination. The t-SNE plots for ENZYMES, Reddit, and Letter-High are shown figures and rreepective..
5.3
ABLATION STUDY ON NUMBER OF SUPER-CLASSER CLASSES
Here, we study the behavior of our proposed network model without the super-class classifier Ceup, In 310 and 20-shot setting), observe marked increase with the addition of our classifier which uses the super-class information and the super-grape based on spectral measures to guide CGAT towards improving the class separation of the graphs during both the training and fine-tuning stages. Using super-classes help in reducing the sample complexity of the large Hypothesis space and makes tuning of the model parameters easier during fine-tuning stage with less samples and few iterations. Negligible differences are observed on ENZYMES dataset since both the number of training classes as well as test classes are low, thus, model performs equally well on removing super-classes. This is because of the latent inter-class representations can still be captured between few classes especially during the fine-tuning phase.
Table 3: Ablation Study: "No-SC" represents classifier C(.) without Coup and "With-SC" represents C(.) with both Coup and CGTT present.
Dataset
10-shot
20-shot
No-SC
With-SC
No-SC
With-SC
Letter-High
71.13
3.64
73.61 3.19
75.23 + 2.48
77.42 + 1.47
TRIANGLES
74.03 3.89
76.49
3.26
76.89 + 2.63
80.14 + 1.88
Reddit-12K
43.76
4.34
45.35
+ 4.06
48.19 + 4.01
50.36 + 3.04
ENZYMES
59.97 = 3.98
59.58
+ 4.32
62.7 + 3.63
62.39 + 3.48
5.4 SENSITIVITY ANALYSIS VARIOUS ATTRIBUTES
Our proposed method contains two crucial attributes. We analyze model by varying: (1) the number super-elasses and (ii) the k-value in super-graph construction. The effect of varying these attributes model accuracy shown in Tables and respectively. For TRIANGLES and Letter-

---

Published as a conference paper at ICLR 2020
Table Model analysis over number of super-classes in 20-shot scenario. There is evaluation for 5 super-classes on ENZYMES since the number of training classes is 4. Default value of parameter k is fixed
Dataset
20-shot
2
3
5
Letter-High
74.43 + 2.61
76.61
1.67
77.51 + 1.49
76.31
+ 1.98
75.05 + 2.29
TRIANGLES
76.43 2.87
79.55
1.91
80.51
1.72
78.91
2.09
78.25 + 2.40
Reddit-12K
48.32 4.09
50.67
+ 2.94
50.10
3.02
49.52 + 4.02
48.33 + 4.08
ENZYMES
62.34 4.11
62.13
4.01
60.16 3.81
59.34 + 3.98
Table 5: Model analysis over number of neighbors (k) in super-graph for 20-shot scenario. Default value for the number of super-classes is fixed 3.
Dataset
20-shot
2
4
6
Heuristic
Letter-High
T7.33 = 1.71
76.61
1.67
75.63
2.49
74.66
2.61
74.35 + 2.48
TRIANGLES
80.77 + 1.57
79.85
1.59
79.45
1.97
78.93 + 2.04
79.42 4 3.16
Reddit-12K
50.48 3.02
46.37
3.03
44.12
2.98
43.88
+ 3.24
44.82 + 2.83
ENZYMES
62.34 4.11
61.42
4
60.23
5.10
59.67
= 4.77
61.07 + 4.68
High datasets, as we increase the number of super-classes, we observe the accuracy improving steadily up to 3 super-classes and then dropping from there onwards. For super-classes less than 3, we observe that the k-NN graph does not respect the class boundaries that are already imposed by the graph spectral measures, thus connecting more arbitrary classes. For Reddit we observe the performance is slightly better using 2 super-classes and for ENZYMES similar performances are observed for both and super-classes as described in the ablation study. On the other hand, increasing the number of super-classes past 3, makes each super-class cluster very sparse with few graph classes within, leading to an underflow information between the graph classes. The same effect is observed for all datasets.
The k-value or the number neighbors of each node belonging to the same connected component in the super-graph (i.e., belonging the same super-class) is another salient parameter upon which hinges the information flow (via message passing) between the graphs the same super-class. We analyze model with k values in the set {2, 4, 8) and commonly used heuristic method, whereby each graph is connected to vb, nearest neighboring graphs based on the Euclidean similar- ity of their feature representations, where b, is the number of samples the mini-batch correspond- We achieve best results with 2-NN graphs per super-class and increasing k beyond it leads to denser graphs with unnecessary connections between classes belonging to the same super-class.
ing to super-classes
CONCLUSION
In this paper, we investigated the problem of few-shot learning on graphs for the graph classification task, We explicitly created a super-graph on the base-labeled graphs and then grouped clustered their associated class labels into super-classes, based on the graph spectral measures attributed to each graph and the LP-Wasserstein distances between them. We found that training our GNN on the super-graph along with the auxiliary super-classes resulted in marked improvement over state- of-the--rt GNNs. promising future work is to propose new GNN models that break away from current neighborhood aggregation schemes to specifically overcome the obstacle posed by few-shot learning on graphs. Our source-code and dataset splits have been made public in an attempt to attract more attention to the context of fhw-shot learning graphs.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM J. Math. Analysis, 43(2))904-925 924, 2011.
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In Proceed- ings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pp. 1027-1035, 2007.
Lars Backstrom and Jure Leskovec. Supervised random walks: Predicting and recommending links in social networks. CoRR, abs/1011.4077 2010. URL
4071
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song. Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wier- stra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Re- lational inductive biases, deep learning, and graph networks. arXiv, 2018. URL https:
7/arxiv. wawpiv..rr./pa//116...1000 0wtp:/11166..21....ooo
Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(1): 47-56, January 2005. ISSN 1367-4803. doi: 10. 1001003bioonffrmaaiichiil000.. URL http:
7/dx. dok. org 10.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Ge- ometric deep learning: going beyond euclidean data. CoRR, abs/1611.08097, 2016. URL
httt:://axxx..org//bb//////
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and lo- cally connected networks graphs. In International Conference Learning Representations (ICLR2014), CBLS, April 2014, 2014.
Duen Horng Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam Wright, and Christos Faloutsos. Polonium: Tera-scale graph mining and inference for malware detection. In SIAM INTERNA- TIONAL CONFERENCE ON DATA MINING (SDM), pp. 131-142, 2011.
Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. closer look few-shot classification. In International Conference Learning Representations, 2019.
URL htttps://oppnreeiieeeee net www.:neee///fiiioooooooooomm
forum? i www.iiikkkkkkkAccccd
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 3844-3852. Curran Associates, Inc., 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aapuru-Gzikk and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2224-2232. Curran Associates, Inc., 2015.
Li Fei-Fei, Rob Fergus, and Pietro Perona. One-shot learning of object categories. IEEE Trans. Pattern Anal. Mach. Intell., 28(4),594-611, April 2006. ISSN 0162-8828. doi: 10. 1091/09/T 2006.79. UtL/htpss: /dttpp:://doi.or//110... 1109//PAMI.II 2006.79
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leamnin for fast adaptation of deep networks. CoRR, abs/1703.033400, 2017. URL. htt.:://aarxiv..rr/bbbb///// 03400
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large- scale optimal transport. In Advances in Neural Information Processing Systems 29, pp. 3440- 3448. 2016.
11

---

Published as a conference paper at ICLR 2020
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Nenworks, 2005., volume 2, pp. 729-7329-47 IEEE, 2005.
Jiao Gu, Bobo Hua, and Shiping Liu. Spectral distances on graphs. Discrete Applied Mathematics, 190-191:56- 74, 2015.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.02216, 2017. URL /tt.tttt:///aaa......//aa/aa///a
02216
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks data. CoRR, N10115066056633 2015. URL /RL//ttt..//rxxx.cc////bb//
networs on graph-structured
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. Jennifer Dy and An- dreas Krause (eds.). Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2186-2195, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http: URLBttp://pzroeeeinnssss mir press/ #88//vvnnoe 8a ht.ml
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL
http:: /ttp:v//rxvv..o owgooo//////.... abs/1412 6980 cite 1412 (1411..6900ommmenl Published as con- ference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. CoRR, Abs/1600.02907, 2016. UtLt:t:: /twp/aa//////aoo////////////aaaa abs 1609. 02907
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. ArXiv, abs/1903. 1135, 2019.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaud- huri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3734-3743, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL URL/ittp:://rrceeedd.gg mmlr. press/ Setsss/99//eeeec.ffe
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. CoRR, 80100660 80. URL htlphttt///axxiv.orrg /bss//a///////aoooooo.ooo... 18C1.07600
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-super learning. In AAAI, 2018b.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. CoRR, abs/1707.05000. 2017. URL httthttpp///iiii wwwpaxiivv...raaaaamm wttg/brs/////o/////////////////t 05005
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. CoRR, abs/1 803.02999, 2018. httphttp:///axiii wttp:aawwwiooo.a//aaaaa///a wwtp://g/abaar...// 02999
Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpps://peeneevee... net/
Forum?id=x_JO-KKO
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell. Meta- with latent embedding optimization. CoRR, hts//8877.0566/ 2018. URL/ttp::/arxxie www. abs 1807 10t0p//19000000
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Trans. Neur. Netw., 20(1):61-80, Jamuary 2009. ISSN 1045- 9227. doi: 10. 0009/TNN.200820055000
URL
http: / dx doi. wrg. 1109//TT.....
2008 2005605
12

---

Published as a conference paper at ICLR 2020
N. Shervashidze, SVN. Vishwanathan, TH. Petri, K. Mehlhom, and KM. Borgwardt. Efficient graphlet kemnels for large graph comparison. In JMLR Workshop and Conference Proceed- ings Volume 5: AISTATS 2009, pp. 488-495, Cambridge, MA, USA, April 2009. Max-Planck- Gesellschaft, MIT Press.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kemels. J. Mach. Learn. Res., 12:2539-2568 Novem- ber 2011. ISSN 1532-4435. URL http: acm. wwt.e/oogggciiiioo.o. 2078187
Petar Velikovi, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li, and Yoshua Ben- gio. Graph attention networks. In International Conference Learning Representations. 2018. URL https:://ppenrevveww wwtpwwwwwwewee.eeeeeeeee.ee.eeee aete:/ooommmiidddoMdoa.
B. Yu. Weisfeiler and A. A. Leman. Reduction of a graph to a canonical form and an algebra arising during this reduction. 1968.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. CoRR, 0oss/1901.00596, 2019.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In International Conference Learn- ing Representations, 2019.
net
By By
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference Learming Representations, 2019. URL https:
//openreview wwt/fnnum/ieeeee ryGeei1GGs6...
Shengzhong Zhang, Ziang Zhou, Zengfeng Huang, and Zhongyu Wei. Few- classification on graphs with structural regularized GCNs, 2019. http://pppe//geenreeieeeeeee//rp
id=rl znki ACCY AcY7
13

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 DATASET DETAILS
We use different datasets namely- Reddit- 12K, ENZYMES, Letter-High and TRIANGLES to per- form exhaustive empirical evaluation of our model on various real-world datasets varying from small average graph size on Letter-Hiigh to large graphs like Reddit-12K, These datasets can down- loaded here The dataset statistics provided in Table 6 while the split statistics are provided in Table
Table 6: Dataset Statistics
Dataset Name
Classes
# Graphs
Avg Nodes
Avg Edges
Reddit-122
11
11929
391.41
456.89
ENZYMES
6
600
32.63
62.14
Letter-High
15
2250
4.67
4.50
TRIANGLES
10
45000
20.85
35.50
Dataset Description: Reddit-12K datasets contains 11929 graphs where each graph corresponds to thread in which each node represents user and each edge represents that one user has responded to a comment from some other user. There are different types of discussion forums corresponding to each of the 11 classes.
ENZYMES is a dataset of protein tertiary structures consisting of 600 enzymes from the BRENDA enzyme database. The dataset contains different graph categories corresponding each different top-level EC enzyme.
TRIANGLES dataset contain 10 different classes where the classes are numbered from 10 corresponding to the number of triangles/3-cliques in each graph of the dataset.
Letter-High dataset contains graphs which represent distorted letter drawings from the english al- phabets A, E, F, H, I, K, L, M, N. T, V. W, X, Y, Z. Each graph is prototype manual construc- tion of the alphabets.
Table 7: Dataset Splits
Dataset Name
Train Classes
# Test Classes
# Training Graphs
# Validation Graphs
# Tess Graphs
Reddit-12K
7
4
566
141
404
ENZYMES
4
2
320
80
200
Letter-High TRIANGLES
11
4
1330
320
600
3
1126
271
603
The validation graphs are used to assess model performance on training classes itself to check over- fitting well for grid-search over hyperparameters. The actual train-testing class splits used for this paper are provided with the code. Since the TRIANGLES dataset has a large number of sam- ples, this makes it infeasible sample 200 graphs from each class, making the total sample size 2000. Similarly we downsample the number of graphs from 19929 to 1111 (nearly 101 graphs per class). Downsampling is per- formed for Reddit-1 12K given extremely large graph sizes which makes the graph kernels as well as some deep learning baselines extremely slow.
many baselines including DL and non-DL methods. Hence,
14

---

Published as a conference paper at ICLR 2020
A.2 BASELINE DETAILS
This section details the implementation of the baseline methods. Since, DL-based methods GIN, CapsGNN and DIFFPOOL have not been previously run these datasets, we select the crucial hyper- ppeer-paraeeters.. such as number of layers heuristically based on the results of standard graph classification datasets the best performing variants of these models. For these three methods take the novel layers proposed in the corresponding papers as their feature extractors, while down- stream MLP layers are chosen as the classifier. The training and evaluation strategies similar to our model, i.e., the models are first trained in an end-to-end fashion on the training dataset Gn until convergence with learning rate decay on loss plateau and then the classifier layers are fine-tuned over NN, keeping the parameters of the feature extractor layers fixed.
For the unsupervised models- WL subtree kemel, Graphlet Count kernel, AWE and Graph2Vec, the evaluation is done using k-NN search to assess the clustering quality of these models in our few-shot scenario. We refrain from using high-level classifier models such as SVM or MLPs, since training these classifiers on few-shot regime will not properly assess the abilities of these models to cluster together graphs of similar class labels. We empirically found that using high level classifiers resulted in higher deviations and lower mean accuracies. We choose the hyper-parameters for these models using grid grid-search, since they are significantly faster and each one of these models have few highly sensitive parameters which affect the model significantly. For these models, we perform grid search for selection of & in the h--N algorithm from the set {1, 2, 3, 4,5, 5) for the 5-shot scenario, of which k 1 was found to perform the best. For higher shot scenario, the search was performed over the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10), where we again found k 1 to be the best. The validation set is used to check overfitting and hyper-parameter selection the baseline methods.
A.3 OUR MODEL DETAILS
This section provides the implementation details of our proposed model. Since, our feature extractor model is GIN, we maintain similar parameter settings as recommended by their paper. As mentioned in section 4.2 using embeddings from all iterations of the message passing network helps achieve better discriminative power and improved gradient flow, therefore we employ the same strategy in
our feature extractor. The number of super-classes are selected from the set {1, 2, 3, 4, 5) using grid-search. The k-value for construction of super-graph was selected from the set {2, 4, 6, 8). The feature extractor model uses match--nomallzztioon between subsequent message passing layers. We use dropout of 0.5 in the Crup layers. The CGAT layers undergo normalization of inputs between subsequent layers along with dropout of 0.5, however, the normalization mechanism in classifier layers is different from batch-norm. We normalize each feature embedding to have Euclidean norm with value 1. Essentially,
j+1 Xipput
oou
| ll
where xpput is the input of j + 1hth layer of classifier, X is the output of the jth layer. The inputs of the first layer of CGAT also undergo the same transformation over the outputs of the feature extractor model. We train our models with Adam (Kingma & Ba with an initial learning rate of 10-3 for 50 epochs. Each epoch has 10 iterations, where we randomly select a mini-batch from the training data GB. The fine-tuning stage consists of 20 epochs with 10 iterations per epoch. We use a two-layer MLP over the final attention layer of CGTT for classification. The attention layers use multi-heas attention with 2 heads and leaky ReLU slope of 0.1. The embeddings from both the attention heads are concatenated. For 20-shot, we set le to 2, number of super-classes to and batch size 128 on the Letter-Ifigh dataset, while k is and TRIANGLES datasets. The number of super-classes for Reddit are set to 2, for ENZYMES it set and for TRIANGLES are 3. For ENZYMES, there are negligible differences on using and 2 super- classes as shown in table 4 We used Python Optimal Transport (POT) library $ for implementation of the p-th Wasserstein distance.
1+1
and batch size 64 on Reddit, ENZYMES
15

---

Published as a conference paper at ICLR 2020
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 4: Visualization: t-SNE plots of the computed embeddings of test graphs on 20-shot scenario from OurMethod-GAT (left), GIN (middle) and WL Kernel (right) on ENZYMES dataset.
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 5: Visualization: t-SNE plots of the computed embeddings of test graphs on 20-shot scenario from OurMethod-GAT (left), GIN (middle) and WL Kernel (right) Reddit dataset.
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 6: Visualization: t-SNE plots of the computed embeddings of test graphs 20-shot scenario from OurMethod-Gar (left), GIN (middle) and WL Kernel (right) on Letter-High dataset.
A.4 SILHOUETTE SCORES
To assess the clustering abilities of the models we analyze the silhouette scores of the test embed- dings produced by the GAT variant of our method, GIN and WI. Kernel. Silhouette coefficient essentially measures the ratio of intra-class versus inter-class distance. The Silhouette Coefficient is calculated using the mean intra-cluster distance (a) and the mean nearest-cluster distance (b) for each sample. The Silhouette Coefficient for a sample is given by (b-o) mar(a,b) ,where is the distance between a sample and the nearest cluster that the sample is not a part of. The results for mean silhouette coefficient over the test samples averaged over multiple runs are shown in Table g We normalize the embeddings before calculating the silhouette coefficient. We can clearly see that our model creates better clusters with low intra-cluster distance well high inter-cluster distance. Note that the coefficient value for WL remains the same for all scenarios since it computes fixed embeddings attributed to absence of any DI. component.
16

---

Published as a conference paper at ICLR 2020
Table 8: Silhouette coefficients of the test classes for the three dominant models GAT variant of Our Method, GIN and WL. The best scores are highlighted in bold.
Method
Reddit-12K
ENZYMES
Letter-High
TRIANGLES
10-shot
20-shot
20-shot
10-shot
20-sbot
10-sbot
20-shot
GIN
-0,0566
-0.0652
0.0168
0,0432
0.2157
0.2316
0.0373
0.1256
WI. Kernel
0.0626
0.0626
0.0366
0.0366
0.2490
0.2490
0.0186
0.0186
OurMethod-GAT
-0.0553
-0.0589
0.0296
0.1172
0.3494
0.3787
0.3824
0.4508
Table 9: Semi-supervised fine-tuning results for various p values 10-shot and 20-shot scenarios, where "No Semi-Sup" represents the fine-tuning stage without additional labeled samples.
Dataset
10-sho 25
20-shot 25
No Semi-Sup
50
No Somi-Sup
50
Leghr-High
73.21 3.19
74.18 = 2.88 76.36 + 2.59
74.05 = 2.16
76.95 = 1,79
71.79 1.22 81.29 = 198
78.31
TRIANGLES
75.83 2.97
77.8 = 2.04
80.09 1.78
81.87 1.45
Dataset
10-shot
20-shot
Semi-Sup
20
Sup
20
Reddir
45,41 3.79 60.13 + 3.98
88 + 3.32
46.01 2.99
50.34 2.77
50.76 2.52
51.17
ENZYMES
60.87 + 3.24
61.25 # 3.17
62.74 = 3.64
63.10 = 3:47
63.67 # 3.18
A.5 SEMI-SUPERVISED FINE-TUNING
In many real-world learning scenarios, it is quite common to find abundant unlabelled data. Since our model uses a GNN classifier, this makes it possible to use unlabelled data while learning through message passing, where the fine tuning stage of our method is performed in semi-supervised settings.
Essentially, while fine tuning the model, i.e., only training the classifier CGAT on GN, we addi- tionally use more graphs along with Gv. whose labels are unknown. The learning objective for fine tuning stage doesn't change since the gradients are back- bock-propagated from the labeled samples only. In this setting, each node in the attention classifier aggregate information from unlabelled samples as well, thus allowing improved learning of the graphs features in CG We show the results for p values 25 and 50 on Letter-High and TRIANGLES datasets, whereas for values 10 and 20 on Reddit and ENZYMES datasets. The results are shown in Table We observe an increase in the accuracy with increase in number of unlabeled samples during fine-tuning phase.
A.6 ADAPTATION TO ACTIVE-LEARNING
In this section, we show the adaptation of our model highly practical active learning scenario. In many real world applications, we might start with few samples per class, however as the number of samples classify from these classes increase over time, some of these samples can be used by the model to adaptively learn and improve with very less human intervention, since the number of number of samples to queried for theirs label can always be controlled.
To perform active-learning, we first select random subset of size 100 for Letter-High and TRI- ANGLES datasets as well as random subset of size 40 for Reddit and ENZYMES datasets, which we term as Grandom. then fine tune the model on Gv and further evaluate the model on Grandom-
Table 10: Active Learning Results. The value below each shot represents the number samples added to GN for second fine-tuning step, where "No AL" represents the model evaluation without additional labeled samples.
20-shot
No AL
25
No AL
15
Letter-High TRIANGLES
73.34 = 3.37
75.03 + 3:44
76.89 = 2.16
77.06 1: 1.73
78.44 2 1.52
79,28 2: 1.36
Dataset
10-hoo
20-sbot
No
Reddit
45.41 4 3.79
46.88 + 3.14
47.91 4 2.99
50.43
2.66
51.76
2.32
53.07 2.21
ENZYMES
60.13 1. 3.98
61.57 1. 3.48
62.25 1. 3.06
62.74
3.64
63.60
3.30
64.97 1: 3.11
17

---

Published as a conference paper at ICLR 2020
Thereafter, 1 relatively important samples chosen from Grondom and added to GN for another step of fine-tuning. There can be multiple strategies for defining relative importance of a sample. For our purpose, define sample's ss relative importance via its predicted class probability distri- bution. We sort these samples in increasing order the difference between their highest and second highest predicted class probabilities and choose the first samples from this sorted ranking. We call this importance relative, since each sample is evaluated with respect to the set GN and thus, there is transductive flow of information among the samples, hence defining the relative embeddings in the space. Intuitively speaking, we have chosen the samples lying closer to separation boundary with respect GN. The results for various values of I are shown in Table IO, The evaluation done as mentioned earlier on the unseen set Gtr. We observe significant improvement for all the datasets. This shows our model is capable of selecting important samples with respect to the few existing samples and learn actively.
A.7 PERFORMANCE OF MODEL WITH SUPER-CLASS
From table in correspondence to tables | and 2 one can observe that the results obtained by using only 1 super-class which is equivalent removing the super-classes are still better in comparison with many GNN and graph kernel baselines. By removing the super-classes and thus forming the super-graph solely based on k-nearest neighbor heuristic the GAT still learns latent inter class con- nections via information flow better than the GNNs which use MLP as their classifier. The super graph constructed such scenario will have arbitrary connections between classes in the beginning. however the GIN feature extractor learns over time the segregation in the feature space increases leading to better inter as well intra-class connections. Despite this, the performance with super- classes is better this inductive bias allows the model to initiate with better alignment in the feature space. The silhouette score comparison for OurMethod-Ce best performing number of super-classes to GIN and WL clearly indicates the multifold benefits of using GNNs as a classifier via super-graph construction. The t-SNE plots for OurMethod- with only 1 super-class, GIN and WL kernel on the datasets TRIANGLES, Reddit and Letter-High provided in the figures]
with super-class and with the
and respectively.
Table 11: Silhouette coefficients of the test classes for three models GAT variant of Our Method for super-class which is equivalent to not using any super-classes the best performing number of super-classes as well as GIN and WL on 20-shot scenario. For GIN and WL both the sub-columns contain the same values as they don't ion't have any concept of super-classes.
Method
Reddit-12K
ENZYMES
Letter-High
TRIANGLES
J-SC
I-SC
2-SC
I-SC
3-SC
T-SC
3-SC
GIN
-0.0652
-0.0652
0.0432
0.0432
0.2316
0.2316
0,1256
0.1256
WL Kernel
-0.0626
-0.0626
0.0366
0.0366
0.2490
0.2490
0.0186
0.0186
OurMethod
.0.0593
00.5599
0.1172
0.0989
0.3787
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 7: Visualization: t-SNE plots of the computed embeddings of test graphs 20-shot sce- nario from OurMethod-GAT with only I super-class (left), GIN (middle) and WL Kernel (right) on TRIANGLES dataset.
18

---

Published as a conference paper at ICLR 2020
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 8: Visualization: t-SNE plots of the computed embeddings of test graphs on 20-shot scenario from Met with only I super-class (left), GIN (middle) and WL Kernel (right) Reddit dataset.
(a) Our Model
(b) GIN
(c) WL Kernel
Figure 9: Visualization: t-SNE plots of the computed embeddings of test graphs on 20-shot scenario from OurMethod-Gaa GAT with only 1 super-class (left), GIN (middle) and WL Kernel (right) on Letter- High dataset.
19


Reviews:
[{"review_id": "ryxUOGLHcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 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.\n\nThis 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.\n\nI vote for rejecting this submission for the following concerns. \n\n1. 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.\n \n2. 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.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyeJ_2r0tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 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. \n\nIt 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. \n\nThe 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. \n\nIn 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. \n\nUpdate: I am satisfied with author's response and raised my score. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1g3KSyaqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 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).\n\nAt 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.\n\nDuring (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).\n\nDuring 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.\n\nThere'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.\n\nThe 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.\n\nExperiments 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).\n\nI 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.\n\nOne 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.\n\nOverall, I think the paper is worth seeing and discussing at the conference, although it could be improved in various ways.\n\nMinor errors:\n- there appears to be bracket imbalance in eq.6\n- \"Lloyd's\" is misspelled a few times\n\nReviewer's note: I have significant experience in few-shot learning but not in graph neural networks.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

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)