Few-Shot Learning with Graph Neural Networks

Introduction

Supervised end-to-end learning has been extremely successful in computer vision, speech, or machine translation tasks, thanks to improvements in optimization technology, larger datasets and streamlined designs of deep convolutional or recurrent architectures. Despite these successes, this learning setup does not cover many aspects where learning is nonetheless possible and desirable.

One such instance is the ability to learn from few examples, in the so-called few-shot learning tasks. Rather than relying on regularization to compensate for the lack of data, researchers have explored ways to leverage a distribution of similar tasks, inspired by human learning Lake et al. (2015). This defines a new supervised learning setup (also called ‘meta-learning’) in which the input-output pairs are no longer given by iid samples of images and their associated labels, but by iid samples of collections of images and their associated label similarity.

A recent and highly-successful research program has exploited this meta-learning paradigm on the few-shot image classification task Lake et al. (2015); Koch et al. (2015); Vinyals et al. (2016); Mishra et al. (2017); Snell et al. (2017). In essence, these works learn a contextual, task-specific similarity measure, that first embeds input images using a CNN, and then learns how to combine the embedded images in the collection to propagate the label information towards the target image.

In particular, Vinyals et al. (2016) cast the few-shot learning problem as a supervised classification task mapping a support set of images into the desired label, and developed an end-to-end architecture accepting those support sets as input via attention mechanisms. In this work, we build upon this line of work, and argue that this task is naturally expressed as a supervised interpolation problem on a graph, where nodes are associated with the images in the collection, and edges are given by a trainable similarity kernels. Leveraging recent progress on representation learning for graph-structured data Bronstein et al. (2017); Gilmer et al. (2017), we thus propose a simple graph-based few-shot learning model that implements a task-driven message passing algorithm. The resulting architecture is trained end-to-end, captures the invariances of the task, such as permutations within the input collections, and offers a good tradeoff between simplicity, generality, performance and sample complexity.

Besides few-shot learning, a related task is the ability to learn from a mixture of labeled and unlabeled examples — semi-supervised learning, as well as active learning, in which the learner has the option to request those missing labels that will be most helpful for the prediction task. Our graph-based architecture is naturally extended to these setups with minimal changes in the training design. We validate experimentally the model on few-shot image classification, matching state-of-the-art performance with considerably fewer parameters, and demonstrate applications to semi-supervised and active learning setups.

Our contributions are summarized as follows:

We cast few-shot learning as a supervised message passing task which is trained end-to-end using graph neural networks.

We match state-of-the-art performance on Omniglot and Mini-Imagenet tasks with fewer parameters.

We extend the model in the semi-supervised and active learning regimes.

The rest of the paper is structured as follows. Section 2 describes related work, Sections 3, 4 and 5 present the problem setup, our graph neural network model and the training, and Section 6 reports numerical experiments.

Related Work

One-shot learning was first introduced by Fei-Fei et al. (2006), they assumed that currently learned classes can help to make predictions on new ones when just one or few labels are available. More recently, Lake et al. (2015) presented a Hierarchical Bayesian model that reached human level error on few-shot learning alphabet recongition tasks.

Since then, great progress has been done in one-shot learning. Koch et al. (2015) presented a deep-learning model based on computing the pair-wise distance between samples using Siamese Networks, then, this learned distance can be used to solve one-shot problems by k-nearest neighbors classification. Vinyals et al. (2016) Presented an end-to-end trainable k-nearest neighbors using the cosine distance, they also introduced a contextual mechanism using an attention LSTM model that takes into account all the samples of the subset $\mathcal{T}$ when computing the pair-wise distance between samples. Snell et al. (2017) extended the work from Vinyals et al. (2016), by using euclidean distance instead of cosine which provided significant improvements, they also build a prototype representation of each class for the few-shot learning scenario. Mehrotra & Dukkipati (2017) trained a deep residual network together with a generative model to approximate the pair-wise distance between samples.

A new line of meta-learners for one-shot learning is rising lately: Ravi & Larochelle (2016) introduced a meta-learning method where an LSTM updates the weights of a classifier for a given episode. Munkhdalai & Yu (2017) also presented a meta-learning architecture that learns meta-level knowledge across tasks, and it changes its inductive bias via fast parametrization. Finn et al. (2017) is using a model agnostic meta-learner based on gradient descent, the goal is to train a classification model such that given a new task, a small amount of gradient steps with few data will be enough to generalize. Lately, Mishra et al. (2017) used Temporal Convolutions which are deep recurrent networks based on dilated convolutions, this method also exploits contextual information from the subset $\mathcal{T}$ providing very good results.

Another related area of research concerns deep learning architectures on graph-structured data. The GNN was first proposed in Gori et al. (2005); Scarselli et al. (2009), as a trainable recurrent message-passing whose fixed points could be adjusted discriminatively. Subsequent works Li et al. (2015); Sukhbaatar et al. (2016) have relaxed the model by untying the recurrent layer weights and proposed several nonlinear updates through gating mechanisms. Graph neural networks are in fact natural generalizations of convolutional networks to non-Euclidean graphs. Bruna et al. (2013); Henaff et al. (2015) proposed to learn smooth spectral multipliers of the graph Laplacian, albeit with high computational cost, and Defferrard et al. (2016); Kipf & Welling (2016) resolved the computational bottleneck by learning polynomials of the graph Laplacian, thus avoiding the computation of eigenvectors and completing the connection with GNNs. In particular, Kipf & Welling (2016) was the first to propose the use of GNNs on semi-supervised classification problems. We refer the reader to Bronstein et al. (2017) for an exhaustive literature review on the topic. GNNs and the analogous Neural Message Passing Models are finding application in many different domains. Battaglia et al. (2016); Chang et al. (2016) develop graph interaction networks that learn pairwise particle interactions and apply them to discrete particle physical dynamics. Duvenaud et al. (2015); Kearnes et al. (2016) study molecular fingerprints using variants of the GNN architecture, and Gilmer et al. (2017) further develop the model by combining it with set representations Vinyals et al. (2015), showing state-of-the-art results on molecular prediction.

Problem Set-up

We describe first the general setup and notations, and then particularize it to the case of few-shot learning, semi-supervised learning and active learning.

We consider input-output pairs $(\mathcal{T}_{i},Y_{i})_{i}$ drawn iid from a distribution $P$ of partially-labeled image collections

using the model $\Phi(\mathcal{T};\Theta)=p(Y~{}|~{}\mathcal{T})$ specified in Section 4 and $\mathcal{R}$ is a standard regularization objective.

When $r=0$, $t=1$ and $s=qK$, there is a single image in the collection with unknown label. If moreover each label appears exactly $q$ times, this setting is referred as the $q$-shot, $K$-way learning.

Model

This section presents our approach, based on a simple end-to-end graph neural network architecture. We first explain how the input context is mapped into a graphical representation, then detail the architecture, and next show how this model generalizes a number of previously published few-shot learning architectures.

The input $\mathcal{T}$ contains a collection of images, both labeled and unlabeled. The goal of few-shot learning is to propagate label information from labeled samples towards the unlabeled query image. This propagation of information can be formalized as a posterior inference over a graphical model determined by the input images and labels.

Following several recent works that cast posterior inference using message passing with neural networks defined over graphs Scarselli et al. (2009); Duvenaud et al. (2015); Gilmer et al. (2017), we associate $\mathcal{T}$ with a fully-connected graph $G_{\mathcal{T}}=(V,E)$ where nodes $v_{a}\in V$ correspond to the images present in $\mathcal{T}$ (both labeled and unlabeled). In this context, the setup does not specify a fixed similarity $e_{a,a^{\prime}}$ between images $x_{a}$ and $x_{a^{\prime}}$, suggesting an approach where this similarity measure is learnt in a discriminative fashion with a parametric model similarly as in Gilmer et al. (2017), such as a siamese neural architecture. This framework is closely related to the set representation from Vinyals et al. (2016), but extends the inference mechanism using the graph neural network formalism that we detail next.

2 Graph Neural Networks

Graph Neural Networks, introduced in Gori et al. (2005); Scarselli et al. (2009) and further simplified in Li et al. (2015); Duvenaud et al. (2015); Sukhbaatar et al. (2016) are neural networks based on local operators of a graph $G=(V,E)$, offering a powerful balance between expressivity and sample complexity; see Bronstein et al. (2017) for a recent survey on models and applications of deep learning on graphs.

where $\varphi$ is a symmetric function parametrized with e.g. a neural network. In this work, we consider a Multilayer Perceptron stacked after the absolute difference between two vector nodes. See eq. 4:

In general graphs, the network depth is chosen to be of the order of the graph diameter, so that all nodes obtain information from the entire graph. In our context, however, since the graph is densely connected, the depth is interpreted simply as giving the model more expressive power.

The input collection $\mathcal{T}$ is mapped into node features as follows. For images $x_{i}\in\mathcal{T}$ with known label $l_{i}$, the one-hot encoding of the label is concatenated with the embedding features of the image at the input of the GNN.

3 Relationship with Existing Models

The graph neural network formulation of few-shot learning generalizes a number of recent models proposed in the literature.

Siamese Networks Koch et al. (2015) can be interpreted as a single layer message-passing iteration of our model, and using the same initial node embedding (5) ${\bf x}_{i}^{(0)}=(\phi(x_{i}),h_{i})$ , using a non-trainable edge feature

with $u$ selecting the label field from ${\bf x}$. In this model, the learning is reduced to learning image embeddings $\phi(x_{i})$ whose euclidean metric is consistent with the label similarities.

Prototypical networks Snell et al. (2017) evolve Siamese networks by aggregating information within each cluster determined by nodes with the same label. This operation can also be accomplished with a gnn as follows. we consider

where $q$ is the number of examples per class, and

Training

We describe next how to train the parameters of the GNN in the different setups we consider: few-shot learning, semi-supervised learning and active learning.

In this setup, the model is asked only to predict the label $Y$ corresponding to the image to classify $\bar{x}\in\mathcal{T}$, associated with node $*$ in the graph. The final layer of the GNN is thus a softmax mapping the node features to the $K$-simplex. We then consider the Cross-entropy loss evaluated at node $*$:

2 Active Learning

The label of the queried vector $h(l_{i^{*}})$ is obtained, scaled by the weight $w\in(0,1)$. This value is then summed to the current representation ${\bf x}^{(1)}_{i^{*}}$, since we are using dense connections in our GNN model we can sum this $w\cdot h(l_{i^{*}})$ value directly to where the uniform label distribution was concatenated

After the label has been summed to the current node, the information is forward propagated. This attention part is trained end-to-end with the rest of the network by backpropagating the loss from the output of the GNN.

Experiments

For the few-shot, semi-supervised and active learning experiments we used the Omniglot dataset presented by Lake et al. (2015) and Mini-Imagenet dataset introduced by Vinyals et al. (2016) which is a small version of ILSVRC-12 Krizhevsky et al. (2012). All experiments are based on the $q$-shot, $K$-way setting. For all experiments we used the same values $q$-shot and $K$-way for both training and testing. Code available at: https://github.com/vgsatorras/few-shot-gnn

Omniglot is a dataset of 1623 characters from 50 different alphabets, each character/class has been drawn by 20 different people. Following Vinyals et al. (2016) implementation we split the dataset into 1200 classes for training and the remaining 423 for testing. We augmented the dataset by multiples of 90 degrees as proposed by Santoro et al. (2016).

Inspired by the embedding architecture from Vinyals et al. (2016), following Mishra et al. (2017), a CNN was used as an embedding $\phi$ function consisting of four stacked blocks of $\{$3$\times$3-convolutional layer with 64 filters, batch-normalization, 2$\times$2 max-pooling, leaky-relu} the output is passed through a fully connected layer resulting in a 64-dimensional embedding. For the GNN we used 3 blocks each of them composed by 1) a module that computes the adjacency matrix and 2) a graph convolutional layer. A more detailed description of each block can be found at Figure 3.

1.2 Mini-Imagenet

Mini-Imagenet is a more challenging dataset for one-shot learning proposed by Vinyals et al. (2016) derived from the original ILSVRC-12 dataset Krizhevsky et al. (2012). It consists of 84$\times$84 RGB images from 100 different classes with 600 samples per class. It was created with the purpose of increasing the complexity for one-shot tasks while keeping the simplicity of a light size dataset, that makes it suitable for fast prototyping. We used the splits proposed by Ravi & Larochelle (2016) of 64 classes for training, 16 for validation and 20 for testing. Using 64 classes for training, and the 16 validation classes only for early stopping and parameter tuning.

The embedding architecture used for Mini-Imagenet is formed by 4 convolutional layers followed by a fully-connected layer resulting in a 128 dimensional embedding. This light architecture is useful for fast prototyping: 1$\times\{$3$\times$3-conv. layer (64 filters), batch normalization, max pool$(2,2)$, leaky relu$\}$, 1$\times\{$3$\times$3-conv. layer (96 filters), batch normalization, max pool$(2,2)$, leaky relu$\}$, 1$\times\{$3$\times$3-conv. layer (128 filters), batch normalization, max pool$(2,2)$, leaky relu, dropout$(0.5)\}$, 1$\times\{$3$\times$3-conv. layer (256 filters), batch normalization, max pool$(2,2)$, leaky relu, dropout$(0.5)\}$, 1$\times\{$ fc-layer (128 filters), batch normalization$\}$. The two dropout layers are useful to avoid overfitting the GNN in Mini-Imagenet dataset. The GNN architecture is similar than for Omniglot, it is formed by 3 blocks, each block is described at Figure 3.

2 Few-Shot

Few-shot learning experiments for Omniglot and Mini-Imagenet are presented at Table 1 and Table 2 respectively.

We evaluate our model by performing different q-shot, K-way experiments on both datasets. For every few-shot task $\mathcal{T}$, we sample K random classes from the dataset, and from each class we sample q random samples. An extra sample to classify is chosen from one of that K classes.

Omniglot: The GNN method is providing competitive results while still remaining simpler than other methods. State of the art results are reached in the 5-Way and 20-way 1-shot experiments. In the 20-Way 1-shot setting the GNN is providing slightly better results than Munkhdalai & Yu (2017) while still being a more simple approach. The TCML approach from Mishra et al. (2017) is in the same confidence interval for 3 out of 4 experiments, but it is slightly better for the 20-Way 5-shot, although the number of parameters is reduced from $\sim$5M (TCML) to $\sim$300K (3 layers GNN).

At Mini-Imagenet table we are also presenting a baseline ”Our metric learning + KNN” where no information has been aggregated among nodes, it is a K-nearest neighbors applied on top of the pair-wise learnable metric $\varphi_{\theta}(\textbf{x}^{(0)}_{i},\textbf{x}^{(0)}_{j})$ and trained end-to-end, this learnable metric is competitive by itself compared to other state of the art methods. Even so, a significant improvement (from 64.02% to 66.41%) can be seen for the 5-shot 5-Way Mini-Imagenet setting when aggregating information among nodes by using the full GNN architecture. A variety of embedding functions $\phi$ are used among the different papers for Mini-Imagenet experiments, in our case we are using a simple network of 4 conv. layers followed by a fully connected layer (Section 6.1.2) which served us to compare between Our GNN and Our metric learning + KNN and it is useful for fast prototyping. More complex embeddings have proven to produce better results, at Mishra et al. (2017) a deep residual network is used as embedding network $\phi$ increasing the accuracy considerably. Regarding the TCML architecture in Mini-Imagenet, the number of parameters is reduced from $\sim$11M (TCML) to $\sim$400K (3 layers GNN).

3 Semi-Supervised

Semi-supervised experiments are performed on the 5-way 5-shot setting. Different results are presented when 20% and 40% of the samples are labeled. The labeled samples are balanced among classes in all experiments, in other words, all the classes have the same amount of labeled and unlabeled samples.

Two strategies can be seen at Tables 3 and 4. ”GNN - Trained only with labeled” is equivalent to the supervised few-shot setting, for example, in the 5-Way 5-shot 20%-labeled setting, this method is equivalent to the 5-way 1-shot learning setting since it is ignoring the unlabeled samples. ”GNN - Semi supervised” is the actual semi-supervised method, for example, in the 5-Way 5-shot 20%-labeled setting, the GNN receives as input 1 labeled sample per class and 4 unlabeled samples per class.

Omniglot results are presented at Table 3, for this scenario we observe that the accuracy improvement is similar when adding images than when adding labels. The GNN is able to extract information from the input distribution of unlabeled samples such that only using 20% of the labels in a 5-shot semi-supervised environment we get same results as in the 40% supervised setting.

In Mini-Imagenet experiments, Table 4, we also notice an improvement when using semi-supervised data although it is not as significant as in Omniglot. The distribution of Mini-Imagenet images is more complex than for Omniglot. In spite of it, the GNN manages to improve by $\sim$2% in the 20% and 40% settings.

4 Active Learning

We performed Active Learning experiments on the 5-Way 5-shot set-up when 20% of the samples are labeled. In this scenario our network will query for the label of one sample from the unlabeled ones. The results are compared with the Random baseline where the network chooses a random sample to be labeled instead of one that maximally reduces the loss of the classification task $\mathcal{T}$.

Results are shown at Table 5. The results of the GNN-Random criterion are close to the Semi-supervised results for 20%-labeled samples from Tables 3 and 4. It means that selecting one random label practically does not improve the accuracy at all. When using the GNN-AL learned criterion, we notice an improvement of $\sim\text{3.4\%}$ for Mini-Imagenet, it means that the GNN manages to correctly choose a more informative sample than a random one. In Omniglot the improvement is smaller since the accuracy is almost saturated and the improving margin is less.

Conclusions

This paper explored graph neural representations for few-shot, semi-supervised and active learning. From the meta-learning perspective, these tasks become supervised learning problems where the input is given by a collection or set of elements, whose relational structure can be leveraged with neural message passing models. In particular, stacked node and edge features generalize the contextual similarity learning underpinning previous few-shot learning models.

The graph formulation is helpful to unify several training setups (few-shot, active, semi-supervised) under the same framework, a necessary step towards the goal of having a single learner which is able to operate simultaneously in different regimes (stream of labels with few examples per class, or stream of examples with few labels). This general goal requires scaling up graph models to millions of nodes, motivating graph hierarchical and coarsening approaches Defferrard et al. (2016).

Another future direction is to generalize the scope of Active Learning, to include e.g. the ability to ask questions Rothe et al. (2017), or in reinforcement learning setups, where few-shot learning is critical to adapt to non-stationary environments.

This work was partly supported by Samsung Electronics (Improving Deep Learning using Latent Structure).

References

Appendix