Few-shot Node Classification with Extremely Weak Supervision

Song Wang, Yushun Dong, Kaize Ding, Chen Chen, Jundong Li

Abstract

Few-shot node classification aims at classifying nodes with limited labeled nodes as references. Recent methods typically learn from classes with abundant labeled nodes (meta-training classes) and generalize to classes with limited labeled nodes (meta-test classes). However, on real-world graphs, obtaining abundant labeled nodes for many classes is difficult. In practice, each meta-training class may only consist of several labeled nodes, a problem known as extremely weak supervision (EWS). This leads to a larger generalization gap and suboptimal performance. To tackle this, we propose X-FNC, a principled framework that accumulates meta-knowledge across tasks with extremely weak supervision. We introduce two modules to obtain pseudo-labeled nodes as extra references and effectively learn from limited supervision. Extensive experiments on four datasets validate the superiority of X-FNC compared to state-of-the-art baselines.

Introduction

Graph Neural Networks (GNNs) are powerful but typically require significant labeled data. Few-shot node classification (FSNC) addresses this via meta-learning, where a model "learns how to learn" by practicing on many small tasks. However, standard FSNC assumes that while target classes are sparse, the initial training classes are label-rich. In many real-world scenarios—such as rare molecular property prediction or emerging disease diagnosis—this assumption fails. This condition, termed Extremely Weak Supervision (EWS), leads to two primary challenges:

  1. Under-generalization: The model lacks sufficient examples to capture class definitions.
  2. Overfitting: With extremely few query nodes, the model tends to memorize noise or irrelevant features rather than generalizable patterns.

Methodology

The X-FNC framework introduces two primary innovations to the standard meta-learning pipeline to address the challenges of EWS.

Poisson Label Propagation (PLP)

To mitigate under-generalization, X-FNC augments the available data using a graph-adapted Poisson Learning module. While standard label propagation struggles with very few seeds, Poisson Learning is more robust in low-label regimes.

The authors adapt this for graphs by constructing a custom subgraph for every task. This subgraph integrates the original graph structure with a "feature-distance" graph based on Euclidean distance between node features. This dual-graph approach allows the model to propagate labels to nodes that are feature-wise similar even if they lack direct structural connections.

The X-FNC pipeline for augmenting meta-tasks via Poisson Learning to address data scarcity.

Information Bottleneck (IB) Fine-tuning

To address overfitting, X-FNC employs the Information Bottleneck (IB) principle. The objective is to create a representation that is maximally informative about the label while being minimally informative about the input data, effectively filtering out noise.

X-FNC implements this using two GNNs: one optimized for classification and another acting as a regularizer by reconstructing a masked version of the graph. By balancing these objectives, the model learns to ignore irrelevant structural noise and focus on the decisive information required for classification.

The Information Bottleneck optimization strategy in X-FNC using dual GNNs to prevent overfitting.

Experimental Evaluation

Datasets

The framework was evaluated on four popular graph benchmarks modified to simulate EWS environments (5, 10, or 20 labels per training class):

  • Amazon-E: A product network.
  • DBLP: A citation network.
  • Cora-full: A classic research paper dataset.
  • ogbn-arxiv: A large-scale citation network.

Key Results

X-FNC consistently outperformed state-of-the-art baselines like G-Meta, GPN, and RALE across all datasets.

  • Accuracy Gains: On the DBLP dataset (5-way 3-shot setting with only 5 labels per class), X-FNC achieved 70.1% accuracy, significantly outperforming the next best baseline (RALE at 64.7%).
  • Robustness: X-FNC showed the smallest performance degradation as the number of labels per class decreased from 20 to 5.
  • Ablation Studies: Removing either the Poisson module or the IB module led to a noticeable drop in performance, confirming that both data augmentation and noise filtering are essential for solving the EWS problem.

Discussion and Conclusion

X-FNC demonstrates that meta-learning alone is insufficient when training tasks are weakly supervised. Effective meta-knowledge accumulation requires augmenting training tasks via pseudo-labeling and employing sophisticated filtering mechanisms like the Information Bottleneck to prevent overfitting to sparse, noisy data.

Future work may address the computational overhead of dual GNNs and subgraph construction for massive-scale graphs, as well as the performance of X-FNC on graphs with lower average node degrees or significant class imbalance.

Summary updated

Abstract

Few-shot node classification aims at classifying nodes with limited labeled nodes as references. Recent few-shot node classification methods typically learn from classes with abundant labeled nodes (i.e., meta-training classes) and then generalize to classes with limited labeled nodes (i.e., meta-test classes). Nevertheless, on real-world graphs, it is usually difficult to obtain abundant labeled nodes for many classes. In practice, each meta-training class can only consist of several labeled nodes, known as the extremely weak supervision problem. In few-shot node classification, with extremely limited labeled nodes for meta-training, the generalization gap between meta-training and meta-test will become larger and thus lead to suboptimal performance. To tackle this issue, we study a novel problem of few-shot node classification with extremely weak supervision and propose a principled framework X-FNC under the prevalent meta-learning framework. Specifically, our goal is to accumulate meta-knowledge across different meta-training tasks with extremely weak supervision and generalize such knowledge to meta-test tasks. To address the challenges resulting from extremely scarce labeled nodes, we propose two essential modules to obtain pseudo-labeled nodes as extra references and effectively learn from extremely limited supervision information. We further conduct extensive experiments on four node classification datasets with extremely weak supervision to validate the superiority of our framework compared to the state-of-the-art baselines.
BibTeX
@inproceedings{wang2023few,
  author = {Song Wang and Yushun Dong and Kaize Ding and Chen Chen and Jundong Li},
  title = {{Few-shot Node Classification with Extremely Weak Supervision}},
  booktitle = {WSDM},
  year = {2023},
  doi = {10.1145/3539597.3570435},
}
Figure