Few-Shot Learning on Graphs

1 Introduction

Many real-world systems can be modeled as graphs, representing nodes (entities) interconnected by edges (relations) as well as attributes in nodes and edges. Traditional graph mining algorithms usually require both domain understanding and exploratory search when doing feature engineering of a specific task. Accordingly, graph representation learning techniques (GRL) [Zhang et al., 2020c], e.g., graph neural networks, have been proposed to automatically generate graph representation for various downstream applications across different domains, such as social/information systems [Perozzi et al., 2014; Grover and Leskovec, 2016; Kipf and Welling, 2017], bioinformatics/cheminformatics [Jin et al., 2017; Hao et al., 2020], and recommender systems [Ying et al., 2018a; Fan et al., 2019].

Developing a powerful supervised GRL model for a specific downstream task often requires abundant annotated samples. However, lacking labeled data is common in real situations due to the expensive labeling cost [Ding et al., 2022]. For example, molecular property testing for therapeutic activity spends a lot of money on human-laboring and experimental resource [Guo et al., 2021]; recommender systems face cold-start problem for new users (items) coming to the system [Lu et al., 2020]. This calls for a new GRL paradigm that can effectively learn graph representation for various graph mining tasks with the limited labeled data constraint. Fortunately, few-shot learning (FSL) [Wang et al., 2020b] has emerged to alleviate the dependence on labeled data and learn effective data representation for image/vision [Vinyals et al., 2016; Snell et al., 2017], language/text [Yu et al., 2018; Hu et al., 2019], and robotics [Finn et al., 2017; Duan et al., 2017], using a small amount of labels.

Therefore, few-shot learning on graphs (FSLG), which generally combines the advantages of GRL and FSL, has become a promising research topic and attracted increasing attention from the AI community. Consequently, there have been many FSLG studies that span a variety of methods and applications in recent years. In this paper, we provide a comprehensive and systematic review of FSLG. Figure 1 illustrates the framework of this survey. To be specific, we first analyze the key challenges of FSLG. Then we present FSLG bases consisting of two collaborative machine learning techniques: graph representation learning and few-shot learning, and introduce three typical FSLG problems. Next, we summarize existing FSLG methods and applications that are categorized into three parts corresponding to three typical graph mining tasks at different granularity levels: node-level FSL, edge-level FSL, and graph-level FSL. For each part, we cover two major lines of work: metric-based methods and optimization-based methods, and further discuss related applications. We also provide a comprehensive summary table that lists the representative FSLG work with their opensource codes/datasets. Finally, we discuss open problems and pressing issues as future research directions of FSLG. To summarize, our contributions of this work are:

• We analyze the key challenges of FSLG from perspectives of problem, methodology, and applications.
• We comprehensively survey existing studies of FSLG by systematically categorizing them into three parts according to different granularity levels of graph mining tasks.
• We discuss some future research directions of FSLG, which may shed light on the development of the AI community.

2 FSLGChallenges and Bases

FSLG, as a new and promising research topic in the AI community, is non-trivial and faces the following key challenges:

• The uniqueness of FSLG problem. Unlike the general GRL problem, FSLG faces the challenge of limited labels. Besides, FSLG is different from FSL on image or text as graph lies in a non-Euclidean space and has more complex characteristics. Therefore, the uniqueness of FSLG problem requires handling both graph data complexity (e.g., irregularity, heterogeneity) and few-shot task difficulty (e.g., task diversity, inductive bias).
• The complexity of methodology. Before FSLG emerges, there are extensive studies targeting GRL and FSL challenges independently while none of them are able to address both of them jointly. Thus, it is essential yet difficult to develop FSLG methods that consist of both GRL and FSL modules, and combine them for solving the FSLG problem in a collaborative and effective manner.
• The diversity of graph mining applications. Graph mining tasks regarding different applications are diverse, ranging from node-level to edge-level to graph-level tasks. They require different settings, objectives, constraints, and domain knowledge. Hence, it is not easy to develop a customized FSLG method for the target application.

FSLG methods and applications reviewed in Section 3 aim to tackle at least one of the above three challenges. In the following of this section, we introduce FSLG bases that include two learning techniques collaboratively used in FSLG, and three FSLG problems that share the same setting.

2.1 Graph Representation Learning

The purpose of graph representation learning (GRL) [Zhang et al., 2020c] is to automate the discovery of meaningful vector representation of nodes, edges, or the whole graph for various downstream graph mining applications. Existing GRL

approaches generally fall into three groups: (1) network embedding models [Perozzi et al., 2014; Grover and Leskovec, 2016; Dong et al., 2017] that capture graph structure information by preserving proximities among contextual nodes; (2) graph neural networks (GNNs) [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Zhang et al., 2019] that learn node embedding by aggregating neighbors' feature information; and (3) knowledge graph embedding methods [Bordes et al., 2013; Socher et al., 2013; Dettmers et al., 2018] that construct graph as a collection of fact triplets and learn node and edge (a.k.a. entity and relation) embedding through modeling the acceptability score of each fact triplet.

GNNs, as the current state-of-the-art in GRL, are most commonly utilized to build the GRL backbone of a FSLG method. Specifically, a graph is represented as G = (V,E,X), where V is the set of nodes, E ⊆ V ×V is the set of edges, and X is the set of node (and edge) attributes. GNNs learn node embedding via message-passing framework:

where h(l) v denotes embedding of node v at l-th GNN layer; Nv is the neighbor set of node v; AGG(·) and COM(·) are neighbor aggregation and combination functions, respectively; h(0) v is initializedwith node attributeXv. Furthermore, the whole graph embedding can be computed as:

where the READOUT function can be a simple permutation invariant function such as summation or a more sophisticated graph-level pooling function [Ying et al., 2018b].

2.2 Few-Shot Learning

Few-shot learning (FSL) [Wang et al., 2020b] aims to learn generalized experiences from existing tasks to form transferable prior knowledge for new tasks with limited labeled data. It commonly adopts a meta-learning framework [Hospedales et al., 2020] which performs episodic learning to train and optimize the model. Specifically, given a set of tasks T and their data, in the meta-training phase, the objective is to learn parameters θ∗ that work effectively across all tasks in T :

where p(T ) denotes task distribution; DTi is the data of task Ti; L is the loss function for a downstream application. In the meta-testing phase, θ∗ is taken as the initialized parameters (meta-knowledge) that are further quickly adapted to a new task Tj :

Note that, DTj only contains limited labeled data. Notable FSL methods used in FSLG models generally fall into two categories: (1) metric-based methods [Vinyals et al., 2016; Snell et al., 2017; Sung et al., 2018] that learn task-specific similarity metric between query data and support set data; and (2) optimization-based methods [Ravi and Larochelle, 2016; Finn et al., 2017; Finn et al., 2018] that learn well initialized base-learner which can quickly adapt to a new few-shot task with gradient computation.

2.3 FSLG Problems

Different FSLG problems share the same setting of FSL. In specific, let C denote the entire classes set of the whole dataset, which can be further divided into two categories: base classes set Cbase of the training data and new (novel) classes set Cnovel of the testing data, where C = Cbase∪Cnovel and Cbase ∩ Cnovel = ∅. Generally, the number of labels is abundant in Cbase while scarce in Cnovel. Here, we introduce three typical FSLG problems corresponding to three graph mining tasks.

Problem 1. Few-Shot Node Classification. Given a graph, the problem is to develop a machine learning model such that after training on labeled nodes in Cbase, the model can accurately predict labels for nodes (query set) in Cnovel with only a limited number of labeled nodes (support set).

Problem 2. Few-Shot Relation Prediction. Given a graph, the problem is to develop a machine learning model such that after training on node pairs of relations in Cbase, the model can accurately predict unknown node pairs for relations (query set) in Cnovel with only a limited number of known node pairs (support set).

Problem 3. Few-Shot Graph Classification. Given a set of graphs, the problem is to develop a machine learning model such that after training on labeled graphs in Cbase, the model can accurately predict labels for graphs (query set) in Cnovel with only a limited number of labeled graphs (support set).

The FSL setting is applied to different FSLG problems by setting the class meaning. Specifically, each class corresponds to a node label for the node classification problem, a relation type for the relation prediction problem, and a graph label for the graph classification problem. Note that, if the support set contains exactly K nodes for each of N classes from Cnovel and the query set is sampled from these N classes, the problem is called N-way K-shot problem. Besides the above three typical problems, there are other FSLG problems, such as few-shot anomaly detection and few-shot recommendation on graphs.

3 FSLGMethods and Applications

In general, FSLG combines the strengths of GRL (Section 2.1) and FSL (Section 2.2) together for various applications. In this section, we comprehensively review current methods and applications of FSLG by systematically categorizing them into three parts corresponding to three problems in Section 2.3: node-level FSL, edge-level FSL, and graphlevel FSL. Note that, most of FSLG methods adopt two typical FSL techniques: metric-based methods and optimizationbased methods. Accordingly, methods of each part are summarized into two groups, depending on which FSL technique they rely on, followed by the discussion of related applications. At the end, a list of representative FSLG studies with their open-source codes/datasets are shown in Table 1.

3.1 Node-level FSL

Node is the fundamental unit of which graphs are formed. Node-level learning not only facilitates a variety of nodebased applications (e.g., node classification and anomaly detection), but also lays the groundwork for further edge-level and graph-level applications. However, it is often difficult to collect node labels in real practice. For example, obtaining function labels for proteins in the interactome (i.e., proteinprotein network) is a time and labor-consuming task even for experienced experts [Wang et al., 2020a]; a significant number of research venues (labels) in DBLP data (i.e., academic network) have few labeled publications [Ding et al., 2020]. In light of this, there have been many methods proposed to solve node-level problems with limited labeled data. We review existing studies of node-level FSL in this part.

Metric-based Method. Basically, Metric-based Node-level FSL (MN-FSL) adopts the idea of Prototypical Network (ProNet) [Snell et al., 2017] which is a simple yet effective FSL framework. Specifically, MN-FSL first applies a GNN encoder to learn node embedding, and then generates the prototype of each node class by computing the mean of support nodes' embeddings. Finally, MN-FSL classifies query nodes by calculating their Euclidean distances of embeddings to different class prototypes. By incorporating node embedding generated by GNN into ProNet, MN-FSL is able to tackle the challenges of few-shot node classification problem. Built on the basic model, a number of variants of MN-FSL have been proposed. Specifically, GFL [Yao et al., 2020] designs graph-structured prototype to capture the relation structure of support samples, which is further tailored by a graph representation gate to include the whole graph information. Considering the fact that each node has a different significance in graph, GPN [Ding et al., 2020] introduces node importance with self-attention mechanism, then computes the weighted summation of support nodes' embeddings as the refined prototype of each class. In addition, MetaTNE [Lan et al., 2020] leverages an embedding transformation function to map the task-agnostic node representation to the task-specific ones, exploiting the complex and multifaceted relationships between nodes. More recently, HAG-Meta [Tan et al., 2021] leverages both node-level attention and task-level attention to improve class prototype computation, which is further trained by an incremental learning paradigm.

Optimization-based Method. In general, Optimizationbased Node-level FSL (ON-FSL) is developed based on model-agnostic meta-learning (MAML) [Finn et al., 2017]. To be specific, ON-FSL utilizes a GNN encoder to learn node embedding for node classification. In the optimization stage, ON-FSL first updates task-specific parameters for each node class, and then accumulates all task-specific classification losses to update task-agnostic parameters. Finally, the optimized task-agnostic parameters shared by base classes are further quickly adapted to predict labels of nodes in new classes by gradient updates over a few labeled nodes. By optimizing GNN with MAML, ON-FSL learns prior experiences (meta-knowledge) across base classes for fast adaption over new classes and addresses the challenge of few-shot node classification problem. In particular, Meta-GNN [Zhou et al., 2019] is the first work that combines GNN and MAML for node classification. Since then, there have been some improved work. Considering that feature distribution may vary across different sampled tasks, AMM-GNN [Wang et al., 2020a] introduces an attribute-level attention mechanism to better capture the unique property of each meta-learning task. In addition, G-META [Huang and Zitnik, 2020] theoretically justifies that the evidence for a prediction can be found in the local subgraph surrounding the target node and leverages subgraph to learn node embedding. It further combines both ProNet and MAML for model optimization. Moreover, RALE [Liu et al., 2021a] captures both task-level and graphlevel dependencies to improve meta-knowledge transfer process by assigning node locations on the graph.

In addition to the above mentioned work, there are some other studies [Zhao et al., 2021; Zhuang et al., 2021; Liu et al., 2021b; Zhang et al., 2022a] related to node-level FSL. For example, HG-Meta [Zhang et al., 2022a] proposes to address few-shot node classification on heterogeneous graphs by modeling both graph structure heterogeneity and task diversity. In addition, unlike the aforementioned work that focus on predicting labels of nodes in new classes using few labeled samples, models that target classifying nodes with few links (tail nodes) have also been developed [Liu et al., 2021b]. Application. Besides node classification on various types of graphs (e.g., social network, academic graph, and biological network), node-level FSL has been applied to some other applications. Due to the scarcity of outlier data, it is natural to develop FSLG methods to detect anomalies on graphs. In particular, Meta-GDN [Ding et al., 2021] detects network anomaly through the FSL framework augmented with a graph deviation network. Furthermore, FSLG models that incorporate domain knowledge to solve domain-specific anomaly detection problems have also been proposed. For example, Meta-AHIN [Qian et al., 2021a] incorporates malwarerelated attributes and information into GNN and MAML for malicious repository detection on social coding platforms (e.g., Github). Similarly, MetaHG [Qian et al., 2021b] leverages drug-related features and knowledge to the joint model of GNN and MAML for illicit drug trafficker detection on social media (e.g., Instagram).

3.2 Edge-level FSL

Edges explicitly interconnect nodes on a graph and many applications such as relation prediction and recommendation are relied on edge-level graph learning. However, scarcity issue of relation is prevalent in different real situations: a large portion of semantic relations only appear a few times in knowledge bases [Xiong et al., 2018]; E-commerce online platforms face cold-start problem from both user and item sides [Lu et al., 2020]; relationships in biological interaction networks can be noisy and sparse [Bose et al., 2019]. Therefore, researchers have been motivated to propose extensive work to solve edge-level problems with limited labels, as summarized below.

Metric-based Method. In general, existing Metric-based Edge-level FSL (ME-FSL) models rely on on either Matching Network (MatchNet) [Vinyals et al., 2016] - a popular framework of FSL, or Translation Network (TransNet) - a typical knowledge graph embedding method [Bordes et al., 2013]. For ME-FSL built on MatchNet, it first applies a GNN encoder to learn node (entity) embedding, then computes aggregated embedding of each relation by aggregating embeddings of node pairs in reference data (support set). Finally, the matching score between embeddings of relation and query data is used to determine the acceptability of each query sample. Based on this idea, GMatching [Xiong et al., 2018] is firstly proposed to solve one-shot relation prediction problem on knowledge graphs. Later, FSRL [Zhang et al., 2020a] extends GMatching to few-shot scenario by attentively aggregating all support samples of each relation and improving node embedding formulation with a heterogeneous neighbor aggregator. FAAN [Sheng et al., 2020] obtains further improvement over FSRL by designing an adaptive attentional network to learn adaptive node and reference representations. Furthermore, GEN [Baek et al., 2020] investigates a more challenging out-of-graph scenario for relation prediction between unseen nodes or between seen and unseen nodes. More recently, REFORM [Wang et al., 2021a] designs an error mitigation module to alleviate the negative impact of errors incorporated into knowledge graph construction. For ME-FSL built on TransNet, it first computes relation meta by aggregating embeddings of support node pairs, and then leverages the relation meta to model correlation of query pairs using the objective loss of TransE [Bordes et al., 2013]. Two recent models that adopt this idea are MetaR [Chen et al., 2019] and GANA [Niu et al., 2021]. MetaR computes relation meta by averaging all node pair-specific relation meta and performs rapid update on it for relation prediction on knowledge graphs. Furthermore, GANA extends MetaR by refining node embedding and relation meta computation with an attention mechanism and a LSTM aggregator, respectively. In summary, by incorporating node embedding encoded by GNN into MatchNet or TransNet, ME-FSL is able to address the challenges of few-shot relation prediction problem.

Optimization-based Method. Similar to ON-FSL, Optimization-based Edge-level FSL (OE-FSL) relies on MAML for model optimization. In other words, OE-FSL tackles the challenge of few-shot relation prediction problem by optimizing GNN with MAML. In particular, MetaKGR [Lv et al., 2019] is the first work for few-shot multihop relation prediction on knowledge graphs. Specifically, Meta-KGR introduces a reinforcement learning framework to model multi-hop reasoning process, where the search path is encoded by a recurrent neural network. It then adopts MAML to learn effective meta parameters from high-frequency relations that could quickly adapt to few-shot relations. Later, FIRE [Zhang et al., 2020a] extends Meta-KGR with a heterogeneous neighbor aggregator and a search space pruning strategy. More recently, ADK-KG [Zhang et al., 2022b] further improves FIRE by enhancing neighbor aggregator with node text content and augmenting MAML with task weight.

In addition to the studies discussed above, there have been considerable advances [Mirtaheri et al., 2021; Qin et al., 2020; Jambor et al., 2021; Jiang et al., 2021] related to edgelevel FSL. For example, ZSGAN [Qin et al., 2020] studies zero-shot relation prediction by establishing the connection between text and knowledge graph with generative adversarial networks. Unlike node pair matching, P-INT [Xu et al., 2021] calculates the interactions of paths for relation prediction on knowledge graphs. Moreover, a recent study [Jambor et al., 2021] explores the limits of existing models for fewshot link prediction on knowledge graphs.

Application. Edge-level FSL methods have been applied to Note: [1] [Yao et al., 2020]; [2] [Ding et al., 2020]; [3] [Lan et al., 2020]; [4] [Zhou et al., 2019]; [5] [Huang and Zitnik, 2020]; [6] [Liu et al., 2021a]; [7] [Ding et al., 2021]; [8] [Qian et al., 2021b]; [9] [Xiong et al., 2018]; [10] [Zhang et al., 2020a]; [11] [Sheng et al., 2020]; [12] [Baek et al., 2020]; [13] [Wang et al., 2021a]; [14] [Chen et al., 2019]; [15] [Niu et al., 2021]; [16] [Lv et al., 2019]; [17] [Zhang et al., 2020b];[18] [Zhang et al., 2022b]; [19] [Chauhan et al., 2019];[20] [Ma et al., 2020]; [21] [Guo et al., 2021];[22] [Wang et al., 2021b].

Table 1: A list of representative FSLG methods with open-source code/data.

not only relation prediction problems on knowledge graphs, but also many other applications. For example, MetaGraph [Bose et al., 2019] investigates few-shot link prediction on different networks (e.g., biological network). SEATLE [Li et al., 2020] and MetaHIN [Lu et al., 2020] aim to tackle cold-start recommendation problems over graphs.

3.3 Graph-level FSL

Besides node-level and edge-level mining, graph-level learning is also significant to some application domains, such as bioinformatics and social network. Similar to the former two problems, the generation of labeled graph samples also involves scarcity and difficulty issues. For example, the collection of molecular graph labels for therapeutic activity often costs much money and resource [Guo et al., 2021]; some communities in social network (e.g., Reddit) only have a small number of sub-communities. In light of this, some studies have been proposed recently for solving graph-level problems with small labeled data. In this part, we summarize the latest development of graph-level FSLG.

Metric-based Method. Similar to MN-FSL, Metric-based Graph-level FSL (MG-FSL) focuses on computing distance between graph class prototype and query graph to predict labels of query graphs. That is, MG-FSL addresses the challenges of few-shot graph classification problem by combing graph-level GNN with ProNet. In particular, SuperClass [Chauhan et al., 2019] is the first work of MG-FSL for few-shot graph classification. Specifically, unlike the general ProNet which computes the average of support samples' embedding as class prototype, SuperClass employs a graphlevel GNN (i.e., GIN [Xu et al., 2018]) to learn graph embedding, and then clusters graphs into different super-classes by computing prototype graphs from each class, followed by clustering the prototype graphs based on their spectral properties. Finally, the model is optimized using joint classification losses of both graph labels and super-class labels. More recently, different from the typical few-shot graph classification task performed on single domain data, MVG-Meta [Hassani, 2022] develops a multi-view enhanced GIN to learn graph embedding for cross-domain few-shot graph classification, i.e., transferring meta-knowledge learned from one domain to another domain.

Optimization-based Method. Similar to ON-FSL and OEFSL, Optimization-based Graph-level FSL (OG-FSL) leverages MAML to optimize few-shot graph classification model. In this way, OG-FSL is able to solve the challenges of fewshot graph classification problem. There are several studies of OG-FSL. Specifically, AS-MAML [Ma et al., 2020] generates graph embedding by concatenating mean and maxpooling of all node embeddings encoded by GNN, and further leverages a reinforcement learning-based controller to adaptively control MAML for model optimization. More recently, Meta-MGNN [Guo et al., 2021] and Pre-PAR [Wang et al., 2021b] have been proposed to solve molecular property prediction problem (i.e., molecular graph classification). MetaMGNN takes each molecule as a graph and learns its embedding with graph-level GNN. It further introduces task weight to make MAML be aware of molecular property differences for better model optimization. Furthermore, Pre-PAR improves Meta-MGNN by modeling relational structure among different molecular properties, such that the limited labels can be effectively propagated among similar molecules.

Application. As discussed above, besides general graph classification on different types of graphs (e.g., social network and biological network), existing graph-level FSL models have been applied to some other applications, such as molecular property prediction.

4 FSLG Future Research Directions

FSLG is an emerging and fast-developing research topic. Although substantial progresses have been achieved, many challenges still remain. This opens up a number of avenues for future research directions. In this section, we identify and briefly discuss some of them.

• Generalization and transferability. Most of FSLG models excessively rely on labeled data and attempt to inherit a strong inductive bias for new tasks in the test phase. However, a distribution shift often exists between non-overlapping meta-training data and meta-testing data. Without supervision signals from ground-truth labels, the model may not learn an effective GNN for new classes of test data. This gap limits generalization and transferability of the meta-trained GNN. Fortunately, contrastive learning [Chen et al., 2020; You et al., 2020] has emerged to alleviate the dependence on labeled data and learn labelirrelevant but transferable representation from unsupervised pretext tasks. Therefore, we may leverage contrastive learning to improve the generalization and transferability capability of current FSLG methods.
• Explainability. The previous FSLG studies target developing better models in performance while none of them

has thought about model explanation. However, developing FSLG models with explainability is essential to improve model reliability and end-user trust. For example, it is worth investigating and explaining which part of FSLG (e.g., GNN, meta-training, or meta-adaptation) is more significant to model performance, such that we can have a better guide for model design. In addition, we can develop information-based method [Guan et al., 2019] to quantitatively explain FSLG model's capability.

• Graph models for FSLG. Though FSLG has been widely studied for certain types of graphs (e.g., plain graphs, attributed graphs), many other types of graphs such as signed graphs, multiplex graphs remain largely understudied in this filed. Meanwhile, the underlying GNN models adopted by existing FSLG work commonly follow the homophily principle, which cannot naturally adapt to heterophily graphs, where connected nodes are dissimilar. Hence, how to design principled graph models for graphs with different properties is also a promising research direction in the field of FSLG.
• Theoretical analysis of FSLG. A recent work [Jambor et al., 2021] has empirically explored the limits of existing FSLG methods in relation prediction over knowledge graphs and challenged the implicit assumptions and inductive biases of prior work. To take a step further and unveil the profound foundation, theoretical analysis of FSLG, which has not been explored before, is necessary and important for us to better understand FSLG methods. In particular, a number of recent work [Cao et al., 2019; Du et al., 2020; Tripuraneni et al., 2021] related to FSL theory could serve as bases for this research direction.
• Broader applications. As discussed in this work, FSLG have been applied to not only general graph mining tasks at different granularity levels on various types of graphs but also some domain-specific applications (e.g., malware detection, illicit drug trafficker detection). Besides these studies, it is worth exploring the potential of FSLG to other application domains [Mandal et al., 2022], such as healthcare and social good. For example, we may develop FSLG model to capture patients' drug refill behavior (in which labels are limited) over prescription dispensing and refill data (modeled as graph), thus further performing early intervention of patients' abnormal behavior (e.g., opioid overdose), which is essential to their health.

5 Conclusion

As two popular research topics in the AI community, graph representation learning and few-shot learning have laid the groundwork for a new promising research direction: few-shot learning on graphs (FSLG), which has significance to various application domains. In this work, we first introduce major challenges and bases of FSLG. Then we comprehensively review existing studies of FSLG by systematically categorizing them into three parts for node-level, edge-level, and graphlevel problems, respectively. Finally, we discuss several critical issues that should be solved and share our thoughts of future directions. We hope this review will serve as a useful reference for researchers and advance future work of FSLG.