Active Few-Shot Learning for Vertex Classification Starting from an Unlabeled Dataset

--Despite the ample availability of graph data, obtaining vertex labels is a tedious and expensive task. Therefore, it is desirable to learn from a few labeled vertices only. Existing few-shot learners assume a class oracle, which provides labeled vertices for a desired class. However, such an oracle is not available in a real-world setting, i. e., when drawing a vertex for labeling it is unknown to which class the vertex belongs. Few-shot learners are often combined with prototypical networks, while classical semi-supervised vertex classification uses discriminative models, e. g., Graph Convolutional Networks (GCNs). In this paper, we train our models by iteratively prompting a human annotator with vertices to annotate. We perform three experiments where we continually relax our assumptions. First, we assume a class oracle, i. e., the human annotator is provided with an equal number of vertices to label for each class. In the subsequent experiment, "Unbalanced Sampling," we replace the class oracle with k - medoids clustering and draw vertices to label from the clusters. In the last experiment, the "Unknown Number of Classes," we no longer assumed we knew the number and distribution of classes. Our results show that prototypical models outperform discriminative models in all experiments when fewer than 20 samples per class are available. While dropping the assumption of the class oracle for the "Unbalanced Sampling" experiment reduces the performance of the GCN by 9%, the prototypical network loses only 1% on average. For the "Unknown Number of Classes" experiment, the average performance for both models decreased further by 1%. I NTRODUCTION In many fields, data is organized as networks or graphs, where vertices are connected by links. For example, in citation networks, a link exists between two vertices if one paper cites another. In social networks, people represent vertices, and links are formed based on relationships or shared interests. While collecting such graphs is often inexpensive, obtaining labels for vertices from human annotators is tedious and expensive.