[style=chinese]

[style=chinese]

[1] [cor1]Corresponding author. National University of Singapore, Singapore.
Email address<EMAIL_ADDRESS>
[style=chinese] [style=chinese] [style=chinese]

# Structure-Enhanced Meta-Learning For Few-Shot Graph Classification

Shunyu Jiang  Fuli Feng  Weijian Chen  Xiang Li  Xiangnan He  University of
Science and Technology of China, Hefei,Anhui, 230027, China  National
University of Singapore, 119077, Singapore  University of Hong Kong

###### Abstract

Graph classification is a highly impactful task that plays a crucial role in a
myriad of real-world applications such as molecular property prediction and
protein function prediction. Aiming to handle the new classes with limited
labeled graphs, few-shot graph classification has become a bridge of existing
graph classification solutions and practical usage. This work explores the
potential of metric-based meta-learning for solving few-shot graph
classification. We highlight the importance of considering structural
characteristics in the solution and propose a novel framework which explicitly
considers global structure and local structure of the input graph. An
implementation upon GIN, named SMF-GIN, is tested on two datasets, Chembl and
TRIANGLES, where extensive experiments validate the effectiveness of the
proposed method. The Chembl is constructed to fill in the gap of lacking
large-scale benchmark for few-shot graph classification evaluation, which is
released together with the implementation of SMF-GIN at:
https://github.com/jiangshunyu/SMF-GIN.

###### keywords:

Graph Neural Network Graph Structure Few-shot Graph Classification

##  1 Introduction

Graphs are widely used to represent relation data in plenty of real-world
applications such as social networks [20], chemical molecules [9], and
biological proteins [8], due to their strong capability of modeling
relationships and structure. A surge of attention has been focused on graph-
based analytical tasks, including graph classification such as predicting the
chemical properties of molecules [9]. The existing graph classification
solutions largely follow supervised learning where sufficient labeled graphs
are required for each class [24]. Despite the success on well-labeled classes,
many real-world scenarios are faced with few-shot classes where only limited
labeled graphs are available due to the high cost of labeling [2] or the
occurrence of new classes [28]. For instance, in chemical-pharmaceutical
industry, the requirement of predicting new molecule properties keeps
occurring, e.g., predicting the inhibition against COVID-19, where the labeled
molecules are very limited. To address this dilemma, it is imperative to shift
the attention to few-shot graph classification.

As a few-shot classification task, a natural way is extending existing meta-
learning solutions for conventional few-shot tasks such as image
classification [5] to graphs by additionally considering the graph structure.
Indeed, the vanilla model-agnostic gradient-based meta-learning (MAML) [6] has
been extended to graph classification [14] by utilizing graph neural network
(GNN) as the back-bone model. The key idea is to learn a GNN initialization
that can be well generalized and fast adapted to new classes with the
generalization performance as the supervision, which simply counts on the GNN
to encode graph structure. In addition to the prevalence of gradient-based
methods like MAML in meta-learning, there are also works that demonstrate the
effectiveness of metric-based meta-learning [11] in conventional few-shot
classification. Its target is to learn sample representation and distance
measure that can be generalized to the new classes where the prediction is
made according to the distance to the labeled samples. Along this line,
Chauhan et al. propose a graph distance measure in the spectral domain, which
validates the merit of considering graph structure. However, the measure in
spectral domain might not well utilize the graph structure, making it
inflexible and hard to be adjusted according to the graph properties.
Therefore, it is worthwhile exploring meta-learning for few-shot graph
classification with explicit consideration of graph structure, which has
received relatively little scrutiny.

Figure 1: An illustration of molecule graph.

We argue that the structural information of graph data consists of two parts,
namely local structure and global structure. On the one hand, some attributes
of a graph depend on the substructure of the graph, that is, the local
structure plays a decisive role in predicting the graph’s attribute class. For
example, as shown in Figure 1(a), the structures of $Na_{2}CO_{3}$ and
$K_{2}CO_{3}$ both contain carbonate groups (i.e., $CO_{3}$), making them
exhibit similar characteristics such as the weak alkalinity when dissolved in
water. As such, the local structure should be well represented when measuring
the distance of graphs. On the other hand, as GNN has become a default choice
for extracting graph representations, the global structure of a graph also
affects whether the distance calculated from the representations can be well
generalized. As shown in Figure 1(b), the graph representation at deep layers
will be over-smoothing for $C_{6}H_{6}$ with small diameters [3], while for
$C_{6}H_{12}$ with large diameters, the graph representation at shallow layer
will be insufficient for describing the overall graph [13]. As the graphs in
new classes may have distinct global structure and local structure, it is even
more challenging to model them both effectively.

In this work, we propose a metric-based meta-learning framework for few-shot
graph classification that explicitly considers the structure characteristics
of graph data when calculating graph representation. In this framework, a
multi-layer GNN is employed to encode the input graph where different layers
capture the information at different granularities. To better account for the
global structure, instead of simply aggregating (e.g., concatenating) the
representations from different GNN layers, we devise an adaptive aggregation
module that assigns weights for different layers in a graph-specific manner.
As to the local structure, the framework further extracts the representations
of representative substructures (e.g., the scaffold [23] of molecular) which
are adaptively fused into the overall graph representation. In this way, the
framework can achieve more accurate distance metric to enhance the graph
classification on new classes. Moreover, the framework is transparent,
shedding light on how the global structure and local structure effect the
classification.

In particular, we implement the proposed framework over a state-of-the-art
model for graph classification, Graph Isomorphism Network (GIN) [24]. We
evaluate our solution, named SMF-GIN, over the existing datasets of few-shot
graph classification such as TRIANGLES [2]. However, the existing datasets not
only contain few classes but are also small in size, making it difficult to
truly validate the performance of the model. To facilitate the research and
evaluation of the few-shot graph classification task, we extract a large-scale
multi-class graph classification dataset in the Chembl chemical molecule
database [23], named Chembl, which is believed to be a general benchmark
dataset. Extensive experiments on TRIANGLES and Chembl validate the
effectiveness and rationality of the proposed method.

The main contributions of our work are as follows:

  * •

Proposing a metric-based meta-learning solution for the few-shot graph
classification task, which explicitly encodes the local structure and global
structure of a graph.

  * •

Constructing a general large-scale multi-class benchmark dataset to facilitate
future research on few-shot graph classification.

  * •

Conducting extensive experiments on two datasets to justify the effectiveness
of our design.

##  2 Method

In this section, we first describe the problem setup (Section 2.1) followed by
the introduction of the proposed framework (Section 2.2). Lastly, we detail
the consideration of graph local structure and global structure.

###  2.1 Problem Setup

First of all, we define the problem of the few-shot graph classification,
where a set of graphs
$\\{\mathcal{G}_{1},\mathcal{G}_{2},\cdots,\mathcal{G}_{m}\\}$ and their
labels $\\{\mathbf{y}_{1},\mathbf{y}_{2},\cdots,\mathbf{y}_{m}\\}$ are given.
Each graph $\mathcal{G}_{i}=(\mathbf{A}_{i},\mathbf{X}_{i})$ is described by
an adjacency matrix $\mathbf{A}_{i}\in\mathbb{R}^{m_{i}\times m_{i}}$ and a
node feature matrix $\mathbf{X}_{i}\in\mathbb{R}^{m_{i}\times d}$, where
${m}_{i}$ denotes the number of nodes in $\mathcal{G}_{i}$ and $d$ is the
dimension of node feature. Then, according to label $\mathbf{y}$, we split $G$
into $\\{(G^{train},\mathbf{y}^{train})\\}$ and
$\\{(G^{test},\mathbf{y}^{test})\\}$ as train set and test set respectively.
Notice that $\mathbf{y}^{train}$ and $\mathbf{y}^{test}$ must have no common
classes. The target is to learn a classifier from
$\\{(G^{train},\mathbf{y}^{train})\\}$ (i.e., meta-train), that can be
generalized to making prediction for classes in $\mathbf{y}^{test}$ given only
a few labeled graphs (i.e., meta-test).

In the meta-train and meta-test phases, we utilize the episodic method of task
learning [6] in the conventional few-shot learning. Taking the meta-train
phase as an example, we randomly sample meta-tasks, which contain a support
set $D_{sup}=\\{(G_{sup},\mathbf{y}_{sup})\\}$ and a query set
$D_{qry}=\\{(G_{qry},\mathbf{y}_{qry})\\}$. Given labeled support data, our
goal is predicting the labels of query data. Generally, there are $N$ classes
in the support set, and each class has $K$ samples. This is the $N$-way
$K$-shot graph classification problem we aim to solve. For each meta-task, its
support set and query set have the same classes, but the number of samples in
each class is not necessarily the same.

###  2.2 The Proposed Framework

Inspired by the metric-based meta-learning method in the field of computer
vision [22], the framework (see Figure 2) learns a GNN as an encoder to
project a graph (i.e., $\mathcal{G}_{i}$) into a latent representation
$\mathbf{h}_{i}=f(\mathcal{G}_{i}|\theta)$, and makes prediction based on the
nearest neighbor principle by calculating distance between the query graph and
the graphs in the support set according to their latent representations. For a
$N$-way $K$-shot meta-task, by feeding the support set
$D_{sup}=\\{(G_{sup},\mathbf{y}_{sup})\\}$ through the encoder, we obtain
their latent representations,
$\mathbf{h}_{G_{sup}}^{i,n}(i\in[1,K],n\in[1,N])$. From the representations of
the graphs in each class, we obtain a class centroid $\mathbf{c}_{n}$, which
is formulated as:

$\mathbf{c}_{n}=\frac{1}{K}\sum_{i=1}^{K}\mathbf{h}_{G_{sup}}^{i,n}.$ (1)

Similarly, we extract the representation of query graphs,
$\mathbf{h}_{G_{qry}}^{i}$($i\in[1,Q]$, where Q is the number of query set) of
all samples.

##### Meta-train.

We measure the distance between the the query graph and each class centroid.
The nearest neighbor classification method is utilized to predict the label of
each query graph:

$\begin{split}\hat{y}_{qry}^{i}=\operatorname*{argmin}_{n}d\left(\mathbf{c}_{n},\mathbf{h}_{G_{qry}}^{i}\right),\end{split}$
(2)

where $d(\cdot)$ is a distance metric such as the Euclidean distance. The
parameters of the encoder are learned by optimizing a classification loss over
the query graphs, which is:

$\operatorname*{argmin}_{\theta}\sum_{i}\mathcal{L}\left(\hat{y}_{qry}^{i},y_{qry}^{i}\right),$
(3)

where $y_{qry}^{i}$ is the label of the query graph $i$ and $\mathcal{L}$ is
selected to be the widely used cross-entropy loss.

Figure 2: Illustration of metric-based meta-learning for few-shot graph
classification.

##### Meta-test.

Given a graph $\mathcal{G}_{i}$ from a meta-task in the meta-test phase,
instead of a direct usage of the extracted representation
$\mathbf{h}_{i}=f(\mathcal{G}_{i}|\theta)$. We consider a representation
transformation to facilitate the generalization to new classes by centering
and scaling, inspired by the superior performance of SimpleShot [22]. 1)
Centering. As the encoder is trained over graphs from the training graphs, it
may induce some bias into the representation of graphs from unseen classes.
Therefore, we subtract the mean representation over all graphs occurred in
meta-train to mitigate such representation drift. Formally,

$\bar{\mathbf{h}}_{i}=f\left(\mathcal{G}_{i}|\theta\right)-\frac{1}{|\mathcal{G}_{train}|}\sum_{\mathcal{G}_{j}\in\mathcal{G}_{train}}f(\mathcal{G}_{j}|\theta).$
(4)

2) Scaling. We further conduct L2-normalization over $\bar{\mathbf{h}}_{i}$ so
that the range of distance across different classes is close to each other.
That is, we use
$\hat{\mathbf{h}}_{i}\leftarrow\frac{\bar{\mathbf{h}}_{i}}{\|\bar{\mathbf{h}}_{i}\|_{2}}$
to calculate class centroid and graph distance in meta-test.

In particular, we choose GIN as the backbone of the encoder, which is one of
the state-of-the-art models for graph classification. Upon the GIN model, we
then detail our design for considering global structure and local structure
when learn the latent representation $\mathbf{h}_{i}$. It should be noted that
the schema can also be applied to other GNN graph classification models such
as DiffPool [26]. In the following, the omit the subscript for the briefness
of the notations.

###  2.3 Global structure and Local structure

As shown in Figure 3, we devise two modules upon GIN to encode the global
structure and local structure and enhance the graph representation.

(a) Considering global structure in the GIN encoder. (b) Considering local
structure in the GIN encoder.

Figure 3: The consideration of graph local structure and global structure in
the GIN encoder.

####  2.3.1 Global structure

Generally, if there are $l$ layers in GIN, each node will aggregate $l$-hop
neighbors, and the graph representation at each layer
$\\{\mathbf{h}^{1},\mathbf{h}^{2},\cdots,\mathbf{h}^{l}\\}$ are realized by a
READOUT function such as average pooling, which aggregates the node
representations. By concatenating the representation at each layer, we obtain
the entire graph representation. Formally,

$\displaystyle\mathbf{h}_{\mathcal{G}}=con(\mathbf{h}^{1},\mathbf{h}^{2},\cdots,\mathbf{h}^{l}).$
(5)

Intuitively, for graphs with different global structure, the representation at
different layers should be highlighted differently rather than simply treated
equally. For instance, the representation of $\mathbf{h}_{\mathcal{G}}$ should
highlight the representation from shallow layers to avoid the impact of over-
smoothing. In order to make full use of the global structure, we use a global
structure attention to learn $\\{w_{1},w_{2},\cdots,w_{l}\\}$ to model the
importance of different layers:

$\mathbf{h}_{\mathcal{G}}=con\left(w_{1}\times\mathbf{h}^{1},w_{2}\times\mathbf{h}^{2},\cdots,w_{l}\times\mathbf{h}^{l}\right).$
(6)

In this way, the representation from a layer adaptively contributes to the
representation of different graphs. In Section 2.3.3, we detail the
implementation of the global structure attention. Note that we follow the
previous GNN models for graph classification, which typically uses
concatenation to aggregate the representations across difference layers.

####  2.3.2 Local structure

We believe that the attribute characteristics of graph data depend on the
substructure characteristics. In other words, the local substructure in the
graph plays a decisive role in the label prediction of the entire graph. In
many domains, the crucial substructure can be recognized according to domain
knowledge such as the scaffold of molecular111In case such domain knowledge is
not available, we simply divide the entire graph into two substructures..

Let
$\mathcal{G}_{subs}=\left\\{\mathcal{S}_{1},\cdots,\mathcal{S}_{n}\right\\}$
denote the crucial substructures extracted from graph $\mathcal{G}$. For each
substructure, e.g., $\mathcal{S}_{1}$, we use the same GIN encoder to
calculate its latent representation at each layer and obtain the substructure
representation $\mathbf{h}_{\mathcal{S}_{1}}$ according to Equation 6222Note
that we can also calculate the representation according to Equation 5 if
ignoring the global structure attention.. Considering that substructure can
contribute unequally to the prediction of different graphs, we devise a local
structure attention to model the weight of substructure and obtain the final
representation of the graph $\mathbf{h}$. Formally,

$\mathbf{h}=r_{0}\times\mathbf{h}_{\mathcal{G}}+r_{1}\times\mathbf{h}_{\mathcal{S}_{1}},\cdots,r_{n}\times\mathbf{h}_{\mathcal{S}_{n}},$
(7)

$\\{r_{0},r_{1},\cdots,r_{n}\\}$ is calculated by an attention model (see
Section 2.3.3). If not otherwise specified, we aggregate the entire graph
representation $\mathbf{h}_{\mathcal{G}}$ and the substructure representations
through mean-pooling, which is a common setting in the previous usage of
attention model [26] and is sufficient for distilling the important signals
for making classification (see detailed results in Section 3.3.4).

####  2.3.3 Attention models

For both the global structure attention and the local structure attention, the
target is to learn a group of weights (i.e., $w$ and $r$) with a set of
representations as inputs, and aggregate the representations according to the
learned weights. Considering that graphs changes dramatically across different
domains, we try five different attention models to calculate the weights.
Without loss of generality, we elaborate the attention models with the global
structure attention as an example where the inputs are
$\mathcal{H}=\\{\mathbf{h}^{1},\mathbf{h}^{2},\cdots,\mathbf{h}^{l}\\}$.

##### Learned-weight.

A straightforward implementation is treating the target weights as additional
model parameters directly which are updated as normal parameters during model
training. Formally, we introduce a learnable weight vector
$\mathbf{w}=[w_{1},w_{2},\cdots,w_{l}]$. As the weights are shared across
different graphs, this method is suitable for scenarios where the global
structure properties are consistent across graphs, especially the ones without
enough labeled data since the minimal number of additional model parameters.

##### Vanilla attention.

Inspired by the success of the vanilla attention model [4], it can be a better
choice for implementing our attentions, which is formulated as:

$\begin{split}w_{j}=\frac{\exp(e_{j})}{\sum_{k\leq|\mathcal{H}|}\exp(e_{k})},~{}\text{where}~{}e_{j}=\mathbf{c}^{T}tanh(\mathbf{W}\mathbf{h}^{j}+\mathbf{b}),\end{split}$
(8)

where $\mathbf{c}$, $\mathbf{W}$, and $\mathbf{b}$ are model parameters to be
learned.

##### Self-attention.

Furthermore, to distinguish the different impact among representations, we
further referenced the multi-head self-attention mechanism [18]. We follow the
standard implementation of multi-head self-attention [18] where the input
representations are fed into the model as a sequence. Note that the learned
weights have been absorbed into the output representations.

##### MLP.

Similarly, we can embed the weight into a Multi-Layer Perceptron (MLP) to
learn the aggregation of the input representations, which is formulated as:

$\mathbf{h}^{(k)}={\rm
ReLU}\big{(}\mathbf{W}^{(k-1)}\mathbf{h}^{(k-1)}+\mathbf{b}^{(k-1)}\big{)},$
(9)

where $k$ is the number of MLP layers, $\mathbf{h}^{(0)}=con(\mathcal{H})$ is
a concatenation of the input representations, and $\mathbf{h}^{(k)}$ denote
the output representation.

##### Transformer.

To further enhance the representation ability, we can also implement the
attentions by a Transformer layer, which is combination of multi-head self-
attention and MLP. We refer the original paper [18] for the detailed
formulation of a Transformer layer.

####  2.3.4 Our framework and variants

On the basis of these five different calculation methods, we consider the
characteristics of both global structure and local structure, and implement
our framework with global structure attention and local structure attention
simultaneously, named SMF-GIN. In particular, SMF-GIN first calculates the
representation of the entire graph and each substructure according to Equation
6, and then calculates the final representation for making classification
according to Equation 7.

Moreover, we also study three variants of SMF-GIN:

  * •

SMF-GIN-$G$, which only includes global structure attention, i.e., taking the
output of Equation 6 as the final representation.

  * •

SMF-GIN-$L$, which only considers the characteristics of local structure. As
compared to SMF-GIN, SMF-GIN-$L$ calculates the representation of the entire
graph and each substructure according to Equation 5.

  * •

SMF-GIN-$E$. Lastly, we ensemble SMF-GIN-$G$ and SMF-GIN-$L$, named SMF-
GIN-$E$, through a voting mechanism. In the meta-test phase, SMF-GIN-$E$
averagely aggregates the prediction of a query graph (i.e., distance to each
class centroid) from SMF-GIN-$G$ and SMF-GIN-$L$.

##  3 Experiments

In this section, we will introduce experiment datasets, baselines and details
of our methods for implementation. In our experiments, we focus on four
research questions: (1) Could our framework SMF-GIN, considering the
characteristics of both global structure and local structure, achieve better
results? (2) To what extent, the consideration of global structure and local
structure improve the classification results? (3) What are the specific
performances of different attention models in SMF-GIN-$G$ and SMF-GIN-$L$? (4)
What is the impact of hyper-parameters on SMF-GIN-$G$ and SMF-GIN-$L$? In
response to these four questions, we conduct experiments and answer these
questions in the analysis of experimental results.

###  3.1 Experiment Settings

##### Datasets.

We conduct experiments on two datasets: the multi-class Chembl dataset and
public dataset TRIANGLES. Detailed information about these two datasets
illustrated in the Table 1.

Chembl. In order to promote the few-shot graph classification investigation
and evaluation, we constructed a general large-scale multi-class graph
classification benchmark dataset from the Chembl chemical molecule database
[23], which contains approximately 1.88 million molecules and 12,482 molecular
targets. Specifically, select the target type as protein, the target
confidence score is higher than 0, and each molecule contains only one target.
For better training, select the target with more than 500 corresponding
molecules. Take the final 273 molecular targets as the categories of our
dataset, and randomly select 500 samples from each category as the final
Chembl dataset, a total of 136500 molecules.

TRIANGLES. This dataset contains ten different graph classes numbered from 1
to 10, corresponding to the number of triangles in each graph in the dataset.
Each class of this dataset contains 201 graphs, for a total of 2010 graphs.

Table 1: Datasets statistics and splits.

Dataset Name | #Classes | #Classes Per Graph
---|---|---
#Train | #Validation | #Test
Chembl | 219 | 27 | 27 | 500
TRIANGLES | 6 | - | 4 | 201

##### Baselines

For the N-way K-shot graph classification task, we utilize 5 state-of-the-art
baseline methods to compare with our methods: Pre-GNN, GIN, MAML, Supclass and
SimpleShot. Detailed information about these 5 types of baselines is included:

  * •

Pre-GNN [9]: This method pre-trains the expressive GNN of a single node and an
entire graph so that GNN can learn useful local and global representations at
the same time. We utilized three pre-trained models: Pre-context, Pre-masking,
and Pre-infomax. In the test phase, N-way K-shot tasks were used to fine-tune
these three pre-trained models.

  * •

GIN [24]: This baseline method, follows a neighborhood aggregation strategy,
where we iteratively update the representation of a node by aggregating
representations of its neighbors. In the training phase, we utilize all
categories’ train set graphs to train the encoder and classification layer. In
the test phase, we discard the trained classification layer and retain the
encoder. Then use the N-way K-shot task to fine-tune the encoder and the new
classification layer.

  * •

MAML [14]: We apply gradient-based meta-learning method [6] to GNNs model.
More specifically, we leverage GIN [24] as the graph encoder backbone and
meta-learning as a training paradigm to capture task-specific knowledge
rapidly in the graph classification tasks and transfer them to new tasks.

  * •

Supclass [2]: This method was proposed based method customized for the few-
shot graph classification. On the training stage, they compute prototype
graphs from each class, then they cluster the prototype graphs to produce
superclasses. After that, they predict the origin class and superclass of each
graph. On the test stage, they only update the classifier based on the
classification of origin classes.

  * •

SimpleShot [22]: We apply the metric-based meta-learning method to the GNNs
model without considering graph structure characteristics. Specifically, we
utilize GIN as the encoder to find the class representation in support set,
and then build a metric space shared with the query set. Perform
transformation on the graph representation, and finally utilize the nearest
neighbor principle for N-way K-shot classification.

Table 2: Accuracies with a standard deviation of baseline methods and our
framework. We tested 1000 and 500 N-way-K-shot tasks on Chembl and TRIANGLES
respectively. The bold black numbers denote the best results we get.

Methods | Chembl | TRIANGLES
---|---|---
5-way 5-shot | 3-way 5-shot
Pre-context | $45.75\pm 0.61$ | -
Pre-masking | $45.95\pm 0.62$ | -
Pre-infomax | $44.09\pm 0.60$ | -
GIN | $64.85\pm 0.57$ | $65.31\pm 0.98$
MAML | $61.69\pm 0.57$ | $72.29\pm 0.97$
Supclass | $59.17\pm 0.56$ | $71.43\pm 0.93$
SimpleShot |  $73.08\pm 0.5$4 | $75.56\pm 0.86$
SMF-GIN-$G$ | $74.37\pm 0.54$ | $78.16\pm 0.74$
SMF-GIN-$L$ | $74.10\pm 0.54$ | $78.27\pm 0.82$
SMF-GIN | $71.12\pm 0.56$ | $75.57\pm 0.85$
SMF-GIN-$E$(self) | $74.36\pm 0.55$ | $79.06\pm 0.76$
SMF-GIN-$E$(best) | 75.27$\pm$0.53 | 79.85$\pm$0.73

##### Experimental implementation details.

On account of the number of categories between the chembl dataset and the
TRIANGLES dataset is too different, we perform 5-way 5-shot classification
task on the Chembl dataset and 3-way 5-shot classification task on the
TRIANGLES dataset, where the number of samples in each class in the query set
is 15. The split of the train set, validation set and test set is illustrated
in Table 1. We utilize the 5-layer GIN model as the encoder (each layer
contains 2 layers of MLP). Among them, we CONCAT the graph representation in
the last 4 layers as the real graph representation, because the first layer is
the original node feature. We set the dimension of the hidden layer to 64 and
the learning rate to 0.001. During the training process, a total of 700
iterations are performed, and validation is performed every 20 epochs. The
model with the best verification results is selected for testing to obtain the
final classification result. We implement the proposed solution on Pre-
GNN333https://github.com/snap-stanford/pretrain-gnns. through PyTorch 1.0.1.
As to the substructure, we adopt the scaffold of the molecular in the Chembl
dataset, and a random split of the graph in the TRIANGLES dataset.

###  3.2 Analysis of results

Our experimental results are illustrated in Table 2. Pre-GNN is not suitable
for the TRIANGLES dataset, because this model is designed to process chemical
molecule and biological protein graph so that it could only process the Chembl
dataset. We can observe that three methods of Pre-GNN perform badly on the
N-way K-shot classification task. Here, we believe that there is a great
difference between the dataset used in Pre-GNN and the graph structure of the
dataset we finally test, so even fine-tuning the model on the N-way K-shot
task has not achieved good results.

Regarding the utilization of MAML in GNN to solve the few-shot graph
classification task, in the Chembl dataset, MAML is not as effective as simply
using GIN, while in the TRIANGLES dataset, the result is just the opposite.
The reason for this phenomenon is the different structure of the graphs, the
differences between the Chembl dataset categories are large, whereas the
TRIANGLES dataset represents only the number of triangles in the graph, with a
small structural difference. This is consistent with the general
interpretation of MAML: the generalization ability is poor when there are
large differences in sample data. In both Chembl and TRIANGLES datasets, the
performance of MAML is higher than Supclass, which is also consistent with the
result in [14].

In all models, without considering structural characteristics, the best
performance is SimpleShot, the application of the metric-based meta-learning
method to the GNNs model. It can be seen that it is effective to share a
metric space between the graph data for N-way K-shot classification task. For
our framework: SMF-GIN, the performance is superior to that of baselines
except SimpleShot because package the characteristics of both global structure
and local structure into an end-to-end solution would interfere with the
training process. Therefore, the answer to our first question is yes.

For the second question, we also implement SMF-GIN variants: SMF-GIN-$G$ and
SMF-GIN-$L$, which includes global structure attention and local structure
attention, respectively. we can make the following observation: compared with
the baseline and SMF-GIN, SMF-GIN-$G$ and SMF-GIN-$L$ both achieve better
performance, which shows that it is easier to capture graph structural
characteristics when considering local structure or global structure
separately.

At the end of the previous section, we ensemble SMF-GIN-$G$ and SMF-GIN-$L$,
named SMF-GIN-$E$ through a voting mechanism. Here we consider two ways of
aggregating: SMF-GIN-$E$(self) and SMF-GIN-$E$(best). In particularly, SMF-
GIN-$E$(self) refers to the results of using Self-attention mechanism in both
SMF-GIN-$G$ and SMF-GIN-$L$, while SMF-GIN-$E$(best) refers to the results of
adopting the optimal method in both SMF-GIN-$G$ and SMF-GIN-$L$. As shown in
Table 2, SMF-GIN-$E$(best) gets the best result and SMF-GIN-$E$(self) gets the
second best result. This shows that it is important to make full use of the
specific structure of graph in the few-shot graph classification task.

Figure 4: Impact of five attention models in SMF-GIN-$G$ and SMF-GIN-$L$.

###  3.3 Research on attention models and hyper-parameters

In the previous section, we put forward five different attention models to
both the global structure attention and the local structure attention. In this
section, we take the TRIANGLES dataset as an example and compare the
performance difference of five attention models on SMF-GIN-$G$ and SMF-GIN-$L$
through experiments. For the self-attention mechanism, we have studied the
influence of some hyper-parameters and pooling strategies on the final result.

####  3.3.1 Five attention models

As illustrated in Figure 4, we can see the performance of these different
attention models on SMF-GIN-$G$ and SMF-GIN-$L$.

In SMF-GIN-$G$, the vanilla attention omits the interactions across different
layers’ representation, so the generalization ability for each layer
representation is relatively poor. Simply using learned-weight or MLP layers
to accommodate each layer’s representation is not as effective as self-
attention and Transformer mechanisms. Because shallow representation (e.g., at
the first layer) and deep representation (e.g., at the last layer) have
different importance for different graphs, and self-attention and Transformer
mechanisms can further enhance the representation ability and distinguish the
different impact among representations well.

In SMF-GIN-$L$, due to the poor generalization ability of the vanilla
attention mechanism for representations of the entire graph and substructures,
the result is far lower than the other attention models, and its performance
cannot be illustrated in Figure 4. Simply using learned-weight is difficult to
fit different substructures, more parameters are conducive to the entire graph
and substructures’ representation in SMF-GIN-$L$, so that the effectiveness of
MLP method is higher than self-attention and Transformer mechanisms.

####  3.3.2 The effect of layer depth

As illustrated in Figure 5, we compare layer=1 and layer=2 in self-attention
mechanism on head=$\\{1,2\\}$ in SMF-GIN-$G$ and SMF-GIN-$L$ respectively.
According to Figure 5, we observe that the effect of layer depth on model
performance is the same in SMF-GIN-$G$ and SMF-GIN-$L$, When layer=1, the
performance both are higher than layer=2 whether the head number is $1$ or
$2$. The reason is that in the self-attention mechanism, representations of
the entire graph and substructures and the encoder each layer representations
needn’t deep aggregation, and shallow layer can be expressed well.

(a) SMF-GIN-$G$ (b) SMF-GIN-$L$

Figure 5: Impact of layer depth in (a) SMF-GIN-$G$ and (b) SMF-GIN-$L$. Figure
6: Impact of head numbers in SMF-GIN-$G$ and SMF-GIN-$L$.

####  3.3.3 The effect of head numbers

Comparing the impact of layer depth on performance in Figure 5, we found that
when the head numbers increases, performance in SMF-GIN-$G$ and SMF-GIN-$L$ is
greatly improved. Therefore, we fixed layer=1, tried to change head numbers,
and observed its performance trend. As illustrated in Figure 6, with the
increase of head numbers, there is the same change trend in SMF-GIN-$G$ and
SMF-GIN-$L$, and the performance reaches its peak when head=2. Overall, when
head$\leq$8, the fluctuation of SMF-GIN-$G$ is larger than SMF-GIN-$L$,
indicating the different layers’ representation in SMF-GIN-$G$ are more
sensitive to head numbers. When head$>$8, the performance drops slowly,
indicating that larger head numbers are harmful to this model.

####  3.3.4 Impact of pooling strategies

Recall that we take mean-pooling as a default choice to aggregate the entire
graph representation and substructure representations (c.f., Equation 7). We
then investigate the impact of different pooling strategies on the final
prediction results. We fix previously analyzed hyper-parameters as the best
choice, that is $\\{layer=1,head=2\\}$, and selected max-pooling, mean-pooling
and first-pooling, where first-pooling represents the first dimension of the
output directly, that’s the entire graph’s representation
$\mathbf{h}_{\mathcal{G}}$. As illustrated in Figure 7, we can see that max-
pooling has the best performance, mean-pooling is the second, and first-
pooling is the worst. Because max-pooling is more like making the best feature
selection compared to others, selecting the representation with higher
classification recognition, providing non-linearity and the highest
performance naturally.

Figure 7: Impact of Pooling strategies in SMF-GIN-$L$.

##  4 Related Work

In this section, we briefly introduce the relevant research lines of our work:
graph classification, few-shot learning and graph few-shot learning.

###  4.1 Graph classification

Graph Neural Networks (GNNs) were first introduced in [7]. This algorithm
follows the neighborhood aggregation framework, computes the representation
vector of the node by the recursive aggregation and transformation of adjacent
nodes feature vector. As the main branch in recent years, GNNs have been
successfully applied to graph classification. [10] proposed Graph
Convolutional Neural Network (GCN) and achieved inspiring results based on
feature aggregation from neighborhood nodes. [19] introduced attention
mechanism for graph convolutional operations (GAT). [26] proposed DIFFPOOL, a
differentiable graph pooling module that can generate hierarchical
representations of graphs and can be combined with various graph neural
network architectures in an end-to-end fashion. [24] developed a simple Graph
Isomorphism Network (GIN) that is provably the most expressive among the class
of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test.

When these graph classification methods encounter novel classes, the existing
GNNs models always need to re-learn their parameters to incorporate the new
information, and if there are few samples of data in each new class, the
performance of the GNNs model will suffer a catastrophic decline. However, our
framework uses a metric-based meta-learning method with GIN as the model, it
can achieve good results when there are few novel class data samples.

###  4.2 Few-shot learning

Few-shot learning in the computer vision community was first introduced by
[12]. Its goal is to generalize a model to a new task rapidly with only a
small number of samples after learning a large amount of data with a certain
category. Various learning algorithms have been proposed in the image domain,
and recent related works can be classified into two categories: gradient-based
methods and metric-based methods.

##### Gradient-based methods

These methods aim to learn a better initialization of model parameters that
can be updated by a few gradient steps in future tasks to fast adapt to new
tasks [6] [17], or train parameter generator for task-specific classifier
[15].

##### Metric-based methods

The purpose of these methods is to learn a metric space from the training
task. When a new task appears, this metric space is shared with the new task
[21] [16].

These methods have achieved inspiring results in image classification tasks,
but they have not been well explored in graph data. In contrast, our framework
adopts the metric-based method and performs well in the graph classification
task.

###  4.3 Graph few-shot learning

Based on this challenge, recently many scholars have carried out researches on
few-shot learning in graph data. [27] solved the sparsity problem by adding
regularization in the loss function of the graph neural network in the few-
shot node classification task. [25] proposed a graph few-shot learning (GFL)
algorithm based on the prior knowledge of auxiliary graphs, which transferred
the knowledge learned from the auxiliary graphs to the new target graphs to
improve the effectiveness of semi-supervised node classification. [1] adopted
the traditional meta-learning method to optimize the shared parameter
initialization of the local link prediction model. Currently, these few-shot
learning methods are widely used in node classification and link prediction
tasks, but not suitable for graph classification tasks. [14] adopted gradient-
based meta-learning methods to deal with the few-shot graph classification
task, updated the initialization parameters of the model according to the
different meta-task in order to fast adapt to new tasks. [2] proposes a graph
distance measure in the spectral domain, which validates the merit of
considering graph structure.

However, these methods focus on algorithms and models without utilizing the
characteristics of graph data structure well. In order to make up for this
shortcoming, we put forward our framework under the premise of considering the
structure of graph data explicitly.

##  5 Conclusion and Future Works

This paper highlights the structure-enhanced meta-learning for few-shot graph
classification. We proposed a framework, named SMF-GIN, for the N-way K-shot
graph classification problem. It uses the GIN as an encoder to learn graph
representations, where two attention mechanisms are designed to encode the
global structure and local-structure. Five attention models are tested under
the proposed framework. Extensive experimental analysis shows that for few-
shot learning on the graph, it is more important to make full use of the
structural characteristics of graphs. Meanwhile, a large-scale benchmark
dataset is released to facilitate future research. In the future, we will
explore the consideration of more properties of graph structure in the few-
shot setting. In addition, we will test different backbone models such as
DiffPool [26] and GAT [19]. Furthermore, we will investigate more distance
measures for graphs.

## Acknowledgments

This work is supported by the National Key Research and Development Program of
China (2020AAA0106000) and National Natural Science Foundation of China
(U19A2079).

## References

  * Bose et al. [2019] Bose, A.J., Jain, A., Molino, P., Hamilton, W.L., 2019\.  Meta-graph: Few shot link prediction via meta learning.  CoRR URL: http://arxiv.org/abs/1912.09867, arXiv:1912.09867.
  * Chauhan et al. [2020] Chauhan, J., Nathani, D., Kaul, M., 2020.  Few-shot learning on graphs via super-classes based on graph spectral measures .
  * Chen et al. [2020] Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., Sun, X., 2020.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view, in: AAAI, pp. 3438--3445.
  * Chen et al. [2019] Chen, W., Gu, Y., Ren, Z., He, X., Xie, H., Guo, T., Yin, D., Zhang, Y., 2019.  Semi-supervised user profiling with heterogeneous graph attention networks., in: IJCAI, pp. 2116--2122.
  * Dhillon et al. [2020] Dhillon, G.S., Chaudhari, P., Ravichandran, A., Soatto, S., 2020\.  A baseline for few-shot image classification, in: ICLR.
  * Finn et al. [2017] Finn, C., Abbeel, P., Levine, S., 2017.  Model-agnostic meta-learning for fast adaptation of deep networks, in: ICML, pp. 1126--1135.
  * Gori et al. [2005] Gori, M., Monfardini, G., Scarselli, F., 2005.  A new model for learning in graph domains, in: Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., IEEE.
  * Hamilton et al. [2017] Hamilton, W.L., Ying, Z., Leskovec, J., 2017.  Inductive representation learning on large graphs, in: NeurIPS, pp. 1024--1034.
  * Hu et al. [2020] Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V.S., Leskovec, J., 2020\.  Strategies for pre-training graph neural networks, in: ICLR.
  * Kipf and Welling [2017] Kipf, T.N., Welling, M., 2017\.  Semi-supervised classification with graph convolutional networks, in: ICLR.
  * Koch et al. [2015] Koch, G., Zemel, R., Salakhutdinov, R., 2015.  Siamese neural networks for one-shot image recognition, in: ICML.
  * Li et al. [2006] Li, F., Fergus, R., Perona, P., 2006.  One-shot learning of object categories.  IEEE Trans. Pattern Anal. Mach. Intell. 28, 594--611.  URL: https://doi.org/10.1109/TPAMI.2006.79, doi:10.1109/TPAMI.2006.79.
  * Li et al. [2019] Li, G., Müller, M., Thabet, A.K., Ghanem, B., 2019\.  Deepgcns: Can gcns go as deep as cnns?, in: 2019 IEEE/CVF, IEEE. pp. 9266--9275.
  * Ma et al. [2020] Ma, N., Bu, J., Yang, J., Zhang, Z., Yao, C., Yu, Z., 2020.  Few-shot graph classification with model agnostic meta-learning.  CoRR .
  * Rusu et al. [2019] Rusu, A.A., Rao, D., Sygnowski, J., Vinyals, O., Pascanu, R., Osindero, S., Hadsell, R., 2019.  Meta-learning with latent embedding optimization, in: ICLR.
  * Snell et al. [2017] Snell, J., Swersky, K., Zemel, R.S., 2017.  Prototypical networks for few-shot learning, in: NeurIPS, pp. 4077--4087.
  * Sun et al. [2019] Sun, Q., Liu, Y., Chua, T., Schiele, B., 2019.  Meta-transfer learning for few-shot learning, in: CVPR, pp. 403--412.
  * Vaswani et al. [2017] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I., 2017\.  Attention is all you need, in: NeurIPS, pp. 5998--6008.
  * Velickovic et al. [2017] Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y., 2017\.  Graph attention networks.  CoRR URL: http://arxiv.org/abs/1710.10903.
  * Velickovic et al. [2019] Velickovic, P., Fedus, W., Hamilton, W.L., Liò, P., Bengio, Y., Hjelm, R.D., 2019\.  Deep graph infomax, in: ICLR.
  * Vinyals et al. [2016] Vinyals, O., Blundell, C., Lillicrap, T., Kavukcuoglu, K., Wierstra, D., 2016.  Matching networks for one shot learning, in: NeurIPS, pp. 3630--3638.
  * Wang et al. [2019] Wang, Y., Chao, W., Weinberger, K.Q., van der Maaten, L., 2019\.  Simpleshot: Revisiting nearest-neighbor classification for few-shot learning.  CoRR .
  * Wu et al. [2017] Wu, Z., Ramsundar, B., Feinberg, E.N., Gomes, J., Geniesse, C., Pappu, A.S., Leswing, K., Pande, V.S., 2017\.  Moleculenet: A benchmark for molecular machine learning.  CoRR arXiv:1703.00564.
  * Xu et al. [2019] Xu, K., Hu, W., Leskovec, J., Jegelka, S., 2019.  How powerful are graph neural networks?, in: ICLR.
  * Yao et al. [2020] Yao, H., Zhang, C., Wei, Y., Jiang, M., Wang, S., Huang, J., Chawla, N.V., Li, Z., 2020.  Graph few-shot learning via knowledge transfer, in: AAAI, pp. 6656--6663.
  * Ying et al. [2018] Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W.L., Leskovec, J., 2018.  Hierarchical graph representation learning with differentiable pooling, in: NeurIPS, pp. 4805--4815.
  * Zhang et al. [2018] Zhang, S., Zhou, Z., Huang, Z., Wei, Z., 2018.  Few-shot classification on graphs with structural regularized gcns .
  * Zhou et al. [2019] Zhou, F., Cao, C., Zhang, K., Trajcevski, G., Zhong, T., Geng, J., 2019.  Meta-gnn: On few-shot node classification in graph meta-learning, in: CIKM, pp. 2357--2360.