Few-shot Node Classification with Extremely Weak Supervision

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

This paper, presented at WSDM '23, tackles a critical but often overlooked "cheat" in current machine learning research: the assumption that even if we have few labels for a target task, we have plenty of labels to train on initially.

TL;DR

X-FNC is a new framework for few-shot node classification that works even when the "base" training classes have extremely few labels (as few as 5 per class). It achieves this by using a graph-adapted Poisson Learning module to generate reliable pseudo-labels and an Information Bottleneck optimization strategy to prevent the model from overfitting to noise in sparse data.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful, but they are notoriously "label-hungry." Few-shot node classification (FSNC) was designed to solve this by using meta-learning: a model "learns how to learn" by practicing on many small tasks from "meta-training" classes (which have many labels) so it can generalize to "meta-test" classes (which have very few).

However, the authors point out a major flaw in this setup: in many real-world scenarios—like predicting rare molecular properties or diagnosing emerging diseases—none of the classes have many labels. This is called Extremely Weak Supervision (EWS).

When training labels are this scarce, two things happen:

  1. Under-generalization: The model doesn't see enough examples to understand what defines a class.
  2. Overfitting: With so few "query" nodes to check its work against, the model starts memorizing specific noise or irrelevant features instead of learning generalizable patterns.

Methods

The authors propose X-FNC, which introduces two main innovations to the standard meta-learning pipeline:

1. Poisson Label Propagation (PLP)

To fix the "under-generalization" problem, the model needs more data. X-FNC creates its own by using Poisson Learning. While standard label propagation often struggles with very few seeds, Poisson Learning is more robust.

  • The Twist: The authors adapt this for graphs by building a custom subgraph for every task. This subgraph combines the original graph structure with a new "feature-distance" graph (based on Euclidean distance between node features). This allows the model to propagate labels even to nodes that aren't directly connected but are "feature-wise" similar.

2. Information Bottleneck (IB) Fine-tuning

To fix the "overfitting" problem, the authors turn to the Information Bottleneck principle. The goal of IB is to create a representation that is "maximally informative" about the label but "minimally informative" about the input data.

  • How it works: X-FNC uses two GNNs. One tries to predict the class, while the other acts as a regularizer by trying to reconstruct a "masked" version of the graph. By balancing these, the model learns to ignore "irrelevant information" (like noise in the graph structure) and focus only on the "decisive information" needed for classification.

Datasets

The framework was evaluated on four popular graph benchmarks, modified to simulate the "Extremely Weak Supervision" environment (using only 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 from the Open Graph Benchmark.

Key Insights and Ideas

  • Meta-learning isn't a silver bullet: If your training tasks are "weak," the meta-knowledge the model accumulates is shallow. You must augment the training tasks themselves (via pseudo-labeling) to make meta-learning effective.
  • Structure + Features: Relying solely on the graph's edges for label propagation is risky when labels are sparse. Combining structural adjacency with feature similarity (the $A'$ and $A''$ matrices in the paper) provides a much more stable foundation for pseudo-labeling.
  • Learning to Forget: In low-data regimes, what a model ignores is just as important as what it attends to. The Information Bottleneck acts as a sophisticated filter that prevents the model from "hallucinating" patterns in the noise.

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 higher than the next best baseline, RALE, at 64.7%.
  • Resilience to Scarcity: As the number of labels per class dropped from 20 down to 5, X-FNC showed the smallest performance degradation compared to other methods, proving its robustness to extremely weak supervision.
  • Ablation Success: Removing either the Poisson module or the IB module led to a noticeable drop in performance, confirming that both "more data" and "better filtering" are required to solve the EWS problem.

Limitations and Future Work

  • Graph Density: The authors noted that X-FNC performs slightly better on graphs with higher average node degrees (like DBLP), as this provides more "paths" for the Poisson Label Propagation to work effectively.
  • Computational Overhead: Constructing subgraphs and running dual GNNs for the Information Bottleneck adds complexity. Future work could look into making these modules more efficient for massive-scale graphs.
  • Class Imbalance: The paper assumes a relatively balanced distribution of labels across classes; exploring how X-FNC handles "long-tail" distributions where some classes have 100 labels and others have 2 would be a logical next step.

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},
}

Loading related content...

Figure