Abstract
Zero-shot Graph Embedding (ZGE) is critical for handling emerging node categories in dynamic networks. This paper demystifies RECT, a state-of-the-art ZGE method, by revealing its function as a prototypical network using class mean features. To enhance performance in data-scarce environments, we introduce two label expansion strategies that generate pseudo-labels for both seen and unseen classes. Our approach significantly improves embedding quality and classification accuracy across standard citation benchmarks.
Introduction
In real-world graph scenarios, such as social networks or citation webs, new categories of nodes emerge constantly. Zero-shot Graph Embedding (ZGE) aims to learn meaningful vector representations for nodes belonging to "unseen" classes—categories that had zero labeled examples during the training phase. While the RECT method has shown promise, it has largely remained a "black box" with high data requirements. Furthermore, its reliance on semantic spaces to bridge seen and unseen classes often lacks the discriminative power found in traditional supervised learning.
Methodology
We first show that the supervised component of RECT (RECT-L) is essentially a Nearest Class Mean (NCM) classifier implemented via a Graph Neural Network (GNN). It represents a class prototype as the average feature vector of its members. Building on this insight, we propose two Label Expansion strategies:
- Seen Label Expansion (Ours$_{SL}$): A self-training approach where an initial model predicts semantic descriptions for unlabeled nodes. The "most certain" nodes (those closest to class means) are added to the training set of seen classes.
- Seen and Unseen Label Expansion (Ours$_{SUL}$): This strategy employs K-means clustering on initial embeddings to capture discriminative information for all classes, including unseen ones. Cluster centers act as prototypes to expand the labeled set across the entire graph.
By combining these strategies (Ours$_{SL-SUL}$), the model gains a richer view of the graph's structure and category diversity before the final embedding phase.
Experimental Results
Performance in Low-Data Regimes
The proposed expansion strategies consistently outperform the original RECT-L and other competitive baselines like DeepWalk, GCN, and RSDNE. The gains are particularly pronounced in scenarios with very few labels. For instance, on the Citeseer dataset with only a 1% label rate, our SUL method achieves a Micro-F1 score of 0.5343, a significant improvement over RECT-L's 0.4506.
Robustness to Unseen Classes
A key requirement for ZGE is maintaining performance as the number of available "seen" classes decreases. Our methods demonstrate high robustness in these challenging settings. Even as the number of seen classes is reduced, the label expansion strategies help recover the discriminative power typically lost in purely semantic transfers.
Key Insights
- Prototypical Nature: RECT generalizes to unseen classes because it maps nodes to a semantic space where a class is defined by a mean feature vector, focusing on feature similarity rather than label memorization.
- Clustering as a Proxy: Clustering in the embedding space can reveal the existence of unseen classes even without explicit labels. Treating these clusters as pseudo-classes allows the model to learn category boundaries effectively.
- Automatic Estimation: Using the Silhouette Coefficient to estimate the number of clusters (Ours$_{SUL*}$) performs nearly as well as knowing the true number of classes, making the approach highly practical for real-world applications where the total number of categories may be unknown.
Conclusion
By demystifying the underlying mechanisms of RECT and introducing targeted label expansion strategies, we provide a more transparent and effective framework for zero-shot graph embedding. These methods successfully bridge the gap between semantic knowledge transfer and discriminative learning, particularly when labeled data is scarce.
Summary updated