Network Embedding With Completely-Imbalanced Labels

Zheng Wang, Xiaojun Ye, Chaokun Wang, Jian Cui, Philip S. Yu

Abstract

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data and has shown promising performance. However, existing semi-supervised methods would get unappealing results in the completely-imbalanced label setting where some classes have no labeled nodes at all. To alleviate this, we propose two novel semi-supervised network embedding methods. The first one is a shallow method named RSDNE. Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. The other method is RECT which is a new class of graph neural networks. Different from RSDNE, to benefit from the completely-imbalanced labels, RECT explores the class-semantic knowledge. This enables RECT to handle networks with node features and multi-label setting. Experimental results on several real-world datasets demonstrate the superiority of the proposed methods.

The Challenge of Completely-Imbalanced Labels

Network embedding aims to map the nodes of a graph into a low-dimensional vector space so that the graph's structural properties are preserved. Semi-supervised network embedding uses a small amount of labeled node data to make these embeddings more discriminative, which is highly effective for downstream tasks like node classification.

However, existing methods rely on a crucial assumption: the labeled data must cover all classes. In the real world, labels are expensive and hard to gather. You might easily end up in a completely-imbalanced label setting, where some classes have absolutely zero labeled nodes.

The completely-imbalanced label setting: Class 3 has no labeled nodes in the input, but the goal is to learn discriminative embeddings that still separate it in the output space.

When traditional semi-supervised methods encounter this, they overfit to the "seen" classes. They aggressively pull nodes of the same seen classes together and push different classes apart. Consequently, nodes belonging to the "unseen" classes get collateral damage—they are either ignored or actively pushed into the wrong clusters, leading to poor classification performance.

Proposed Methods: RSDNE and RECT

To tackle this, the authors propose two distinct approaches: one shallow and one deep.

1. RSDNE (Relaxed Similarity and Dissimilarity Network Embedding)

Traditional methods enforce strict intra-class similarity and inter-class dissimilarity. RSDNE relaxes these constraints to prevent ruining the embedding space for unseen classes:

  • Relaxed Intra-class Similarity: Instead of forcing all same-labeled nodes to a single point, RSDNE only requires a labeled node to be close to $k$ of its same-class neighbors. This allows the class to form a flexible topological manifold rather than a rigid cluster.
  • Relaxed Inter-class Dissimilarity: Instead of actively pushing different classes apart, RSDNE simply removes the known edges between nodes with different labels during the training process.

2. RECT (RElaxed GCN NeTwork)

To leverage node features and handle multi-label scenarios, the authors propose RECT. RECT is inspired by Zero-Shot Learning (ZSL). Instead of training a Graph Convolutional Network (GCN) to predict one-hot class labels, RECT trains the network to predict class-semantic descriptions. It automatically generates a "semantic vector" for each seen class by summarizing the original features of its labeled nodes.

A comparison of standard unsupervised network embedding (preserving edges) and semi-supervised embedding (preserving edges and labels).

Because unseen classes share underlying feature vocabulary with seen classes, the model can successfully place unseen nodes into meaningful areas of the embedding space. This allows knowledge transfer to unseen classes completely automatically.

Key Insights and Results

  • Strict constraints hurt unseen classes: Forcing strict clustering on seen classes distorts the underlying graph topology. By relaxing these constraints, the model preserves the natural structure of the unseen classes much better.
  • Manifolds over spherical clusters: Allowing same-class nodes to form a local manifold rather than a tight spherical cluster is a highly effective regularization technique when label information is incomplete.
  • Massive gains on unseen classes: In the completely-imbalanced setting, RECT drastically outperforms standard semi-supervised GNNs. For example, on the Citeseer dataset, RECT outperformed GCN and APPNP by roughly 20% to 300% relatively in Micro-F1 scores.
  • Clearer visual clusters: t-SNE visualizations show that while traditional methods mix unseen classes together, both RSDNE and RECT successfully keep unseen classes separated and clustered meaningfully.

Conclusion

By moving away from rigid classification boundaries and toward semantic and manifold-based representations, RSDNE and RECT bridge the gap between semi-supervised learning and zero-shot generalization in graph data. Future work includes extending these techniques to more complex structures like heterogeneous and signed graphs.

Summary updated

Abstract

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data, and has shown promising performance. However, existing semi-supervised methods would get unappealing results in the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">completely-imbalanced</i> label setting where some classes have no labeled nodes at all. To alleviate this, we propose two novel semi-supervised network embedding methods. The first one is a shallow method named RSDNE. Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. The other method is RECT which is a new class of graph neural networks. Different from RSDNE, to benefit from the completely-imbalanced labels, RECT explores the class-semantic knowledge. This enables RECT to handle networks with node features and multi-label setting. Experimental results on several real-world datasets demonstrate the superiority of the proposed methods.
BibTeX
@article{wang2020network,
  author = {Zheng Wang and Xiaojun Ye and Chaokun Wang and Jian Cui and Philip S. Yu},
  title = {{Network Embedding With Completely-Imbalanced Labels}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2020},
  url = {https://openreview.net/forum?id=ghFilNFJLwf},
}
Figure