Zero-Shot Generalization of GNNs over Distinct Attribute Domains

Yangyi Shen, Beatrice Bevilacqua, Joshua Robinson, Charilaos Kanatsoulis, Jure Leskovec, Bruno Ribeiro

TL;DR

This paper introduces STAGE, a novel method for Graph Neural Networks (GNNs) that enables them to generalize to graphs with entirely different node attribute domains without retraining. STAGE achieves this by encoding node attributes into a common probability-based space, allowing GNNs to learn transferable representations and significantly outperform existing methods in zero-shot generalization tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data. However, a significant limitation is their struggle to generalize to new graphs with different node attribute domains. Imagine training a GNN on product graphs from an appliance store (features like brand, energy rating) and then expecting it to perform well on a smartphone graph dataset (features like processor type, display size) without any further training. This is the "zero-shot generalization" challenge. Existing methods often fail to outperform simpler, structure-only approaches when faced with such domain shifts, primarily because they assume attribute semantics are consistent across graphs. This paper aims to bridge this gap by developing a GNN architecture that can effectively handle and learn from diverse and unseen attribute domains.

Methods

The core innovation is STAGE (Statistical Transfer for Attributed Graph Embeddings). STAGE tackles the domain shift problem by transforming node attributes into a universal, fixed-dimensional embedding space. The key idea is to leverage statistical theory, specifically focusing on the probability distributions of node features.

Here's how it works:

  • Pairwise Probability Descriptors: For each edge $(u, v)$ in a graph, STAGE constructs a representation based on the conditional probabilities of node features $X_u$ and $X_v$. This includes marginal probabilities (e.g., $P(X_i)$) and conditional probabilities (e.g., $P(X_i | X_j)$) for different feature types (continuous or discrete).
  • Edge-Feature Graph: These pairwise probabilities are used to build a fully connected weighted directed graph, where nodes represent features and edges represent their probabilistic relationships.
  • GNN on Edge-Feature Graph: A GNN (specifically, a message-passing neural network) is then applied to this edge-feature graph. This process generates a fixed-dimensional embedding for each edge in the original graph.
  • Base GNN Input: These edge embeddings then replace the original node features as input to a standard GNN (like NBFNet in their experiments). This allows the base GNN to operate on a consistent input representation, regardless of the original attribute domain.

The crucial insight is that by modeling the relationships between features (via probabilities) rather than the raw features themselves, STAGE creates a representation that is invariant to the specific domain or dimensionality of the original attributes.

Datasets

The authors introduce a new benchmark dataset derived from e-commerce user-product interaction data (Kechinov, 2020). This dataset is structured into distinct "graph domains" based on product categories (e.g., smartphones, shoes, refrigerators, desktops, beds).

  • Key Feature: Each category has its own unique set of product features, generated using GPT-4 to mimic realistic product descriptions from 2019. This ensures a significant attribute domain shift between categories.
  • Task: The primary task is link prediction (predicting user-product purchases).
  • Evaluation: They employ a zero-shot evaluation strategy where models are trained on a subset of product categories and tested on unseen categories.

Key Insights and Ideas

  • Probability as a Universal Language: The paper demonstrates that modeling the probabilistic relationships between node features provides a powerful, domain-agnostic way to represent attributes. This is a significant departure from methods that rely on direct feature mapping or textualization.
  • Edge-Centric Representation is Key: By focusing on pairwise feature interactions across edges, STAGE effectively decouples the representation from the specific node features, enabling generalization.
  • Meta-Learning Capability: STAGE shows a clear benefit from being trained on more diverse graph domains, indicating its meta-learning capabilities for adapting to new attribute spaces.
  • Realistic Domain Shifts: The custom e-commerce dataset is crucial for demonstrating the effectiveness of STAGE, as it provides realistic and challenging attribute domain shifts that are often absent in existing benchmarks.

Key Results

  • Superior Zero-Shot Performance: STAGE consistently outperforms several strong baselines (including RAW, GAUSSIAN, STRUCTURAL, LLM, and NORMALIZED) in zero-shot link prediction across various unseen product categories. The performance gains are particularly notable on the smartphone domain.
  • Improved with More Training Data: Figure 2 and subsequent meta-learning experiments (Figures 6-9) show that increasing the number of training graph domains significantly improves STAGE's zero-shot generalization performance.
  • Robustness: The method is shown to be effective across different evaluation metrics like Hits@1, Hits@3, and MRR.

Limitations and Future Work

  • Higher-Order Interactions: The current STAGE formulation focuses on pairwise probabilities. The authors suggest extending this to triple- and higher-order conditional probabilities using hypergraphs for potentially richer representations, though this requires more data.
  • Theoretical Formalization: While the expressivity of the probability-based features is theoretically grounded, a full formalization of their invariance properties across graphs is left for future work.
  • Broader GNN Architectures: The experiments primarily use NBFNet. Future work could explore STAGE's compatibility with a wider range of GNN architectures and tasks (e.g., node and graph-level predictions).
  • More Diverse Domains: Testing STAGE on even more diverse graph domains beyond e-commerce is a natural next step.

Summary updated

Abstract

There are no known graph machine learning methods that can zero-shot generalize across attributed graphs with different node attribute domains. For instance, no method can perform zero-shot link prediction by pretraining on online appliance store datasets (with node attributes such as brand, model, capacity, dimension, has ice maker, energy rating for refrigerators) and zero-shot at test on an electronics store dataset for smartphones (with attributes such as processor type, display type, storage, and battery capacity). In this work, we leverage concepts in statistical theory to design STAGE, a universally applicable approach for encoding node attributes in _any GNN_ that facilitates such generalization. Empirically, we show that STAGE outperforms its natural baselines and can accurately make predictions when presented with completely new feature domains.
BibTeX
@inproceedings{shen2025zero,
  author = {Yangyi Shen and Beatrice Bevilacqua and Joshua Robinson and Charilaos Kanatsoulis and Jure Leskovec and Bruno Ribeiro},
  title = {{Zero-Shot Generalization of GNNs over Distinct Attribute Domains}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=R9iBZen9aY},
}
Figure