Relative and Absolute Location Embedding for Few-Shot Node Classification on Graph

Zemin Liu, Yuan Fang, Chenghao Liu, Steven C. H. Hoi

Introduction

Graph Neural Networks (GNNs) have become the standard for node classification tasks. However, their performance typically hinges on the availability of large-scale labeled datasets. In many real-world scenarios—such as identifying emerging research topics or categorizing new products—we face the few-shot node classification problem, where only a handful of labeled examples exist for "novel" classes.

Standard GNNs struggle here because they are inherently local, aggregating information only from immediate neighbors. This locality prevents them from capturing long-range dependencies between a labeled "support" node and an unlabeled "query" node if they are separated by many hops. The RALE (Relative and Absolute Location Embedding) framework addresses this by explicitly modeling these dependencies using structural landmarks called "hub nodes."

Problem Definition

Few-shot node classification on graphs involves learning from a set of "base classes" with abundant labels to generalize to "novel classes" with very few labels. This is typically structured as a series of meta-learning tasks, each containing a support set (labeled examples) and a query set (unlabeled examples to be classified).

Overview of base and novel classes on a graph and the corresponding few-shot classification tasks.

As shown in the figure above, the challenge lies in bridging the gap between nodes that may be structurally distant but belong to the same class. Existing meta-learning approaches often treat nodes as independent samples, failing to leverage the global connectivity of the graph. RALE aims to create a "transferable prior" that aligns these dependencies across different tasks.

Methodology: The RALE Framework

The core innovation of RALE is the use of Hub Nodes—nodes with high centrality (e.g., high PageRank scores)—to act as structural anchors. By routing information through these hubs, the model can efficiently capture long-range relationships without the computational explosion or "over-smoothing" issues associated with very deep GNNs.

Dual Location Embeddings

RALE employs two types of location-aware embeddings:

  1. Relative Location (RL) Embedding: This captures how a query node relates to the specific labeled support nodes within a given task. Instead of simple random walks, RALE samples paths that pass through hubs, creating "bridges" between distant nodes.
  2. Absolute Location (AL) Embedding: To ensure consistency across different meta-training tasks, every node is assigned an absolute location relative to a global set of hubs. This provides a stable coordinate system for the entire graph.
The RALE architecture, detailing path construction through hub nodes and the dual-encoder meta-learning pipeline.

Model Architecture

As illustrated in the pipeline above, RALE utilizes a dual-encoder system:

  • Graph Encoder: A standard GNN (such as GraphSAGE) captures local neighborhood context.
  • Path Encoder: An RNN or Self-Attention module processes the sequences of nodes along the paths to the hubs, transforming structural sequences into vector embeddings.

These embeddings are then fed into a classifier within a Model-Agnostic Meta-Learning (MAML) framework. This allows the model to learn a set of initial parameters that can be rapidly adapted to new tasks with minimal labeled data.

Experimental Evaluation

The framework was evaluated on three diverse datasets: Amazon (co-purchasing), Email (communication), and Reddit (social interactions). The classes were strictly split into base and novel sets to test true few-shot generalization.

Key Results

RALE consistently outperformed state-of-the-art baselines like GCN, GAT, and Meta-GNN:

  • Significant Performance Gains: On the Email dataset (5-shot), RALE achieved 65.46% accuracy, an 11.4% improvement over the best baseline.
  • Robustness in 1-Shot Scenarios: Even with only one labeled example, RALE showed strong performance, notably improving accuracy on the Reddit dataset by nearly 5% over Meta-GNN.
  • Ablation Studies: Experiments confirmed that both RL and AL are critical; RL captures task-specific nuances, while AL allows the model to align different tasks within the global graph structure.

Conclusion

RALE demonstrates that explicitly modeling graph structure through hub-based location embeddings significantly improves few-shot node classification. By treating hubs as a structural backbone, the model overcomes the locality constraints of traditional GNNs. Future work may explore dynamic graph environments where hub positions change over time and investigate more lightweight path representation methods to reduce computational overhead.

Summary updated

Abstract

Node classification is an important problem on graphs. While recent advances in graph neural networks achieve promising performance, they require abundant labeled nodes for training. However, in many practical scenarios, there often exist novel classes in which only one or a few labeled nodes are available as supervision, known as few-shot node classification. Although meta-learning has been widely used in vision and language domains to address few-shot learning, its adoption on graphs has been limited. In particular, graph nodes in a few-shot task are not independent and relate to each other. To deal with this, we propose a novel model called Relative and Absolute Location Embedding (RALE) hinged on the concept of hub nodes. Specifically, RALE captures the task-level dependency by assigning each node a relative location within a task, as well as the graph-level dependency by assigning each node an absolute location on the graph to further align different tasks toward learning a transferable prior. Finally, extensive experiments on three public datasets demonstrate the state-of-the-art performance of RALE.
BibTeX
@inproceedings{liu2021relative,
  author = {Zemin Liu and Yuan Fang and Chenghao Liu and Steven C. H. Hoi},
  title = {{Relative and Absolute Location Embedding for Few-Shot Node Classification on Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16551},
}
Figure