Semi-supervised Graph Embedding for Multi-label Graph Node Classification

Kaisheng Gao, Jing Zhang, Cangqi Zhou

Introduction

Multi-label classification in graphs is a pervasive challenge where nodes—such as social media users, proteins, or movies—belong to multiple categories simultaneously. While Graph Convolutional Networks (GCNs) have revolutionized node classification, they often struggle in multi-label settings. Standard GCNs typically treat labels as independent outputs via a sigmoid layer and cross-entropy loss. This approach ignores rich "label-label correlations" (e.g., a 'Western' movie is often also 'Adventure') and "node-label correlations." Furthermore, deep GCNs suffer from over-smoothing, where node features become indistinguishable, making it difficult to separate nodes with overlapping but distinct label sets.

The ML-GCN Framework

To address these limitations, the authors introduce ML-GCN, a framework that embeds both nodes and labels into a shared low-dimensional vector space. This allows the model to explicitly measure and optimize the relationships between nodes and labels using vector distance.

ML-GCN Architecture

The core innovation lies in a Relaxed Skip-gram Model. Borrowing from Natural Language Processing (Word2Vec), the model treats a node and its associated labels as a "sentence." As shown in the pairing process, the model uses negative sampling to maximize the probability that a node appears near its ground-truth labels in the embedding space.

Skip-gram Node-Label Pairing

The training objective is a hybrid loss function designed to preserve structural information and counteract over-smoothing:

  • Cross-entropy loss: For standard prediction accuracy.
  • Node-label loss: Ensures node embeddings are proximal to their corresponding label embeddings.
  • Label-label loss: Ensures labels that frequently co-occur have similar embeddings.

Experimental Evaluation

The model was evaluated on three diverse multi-label datasets: Facebook (social circles), Yeast (protein functions), and Movie (genres). ML-GCN consistently outperformed standard baselines, including MLP, DeepWalk, and the original GCN.

On the Yeast and Movie datasets—which exhibit strong label correlations—ML-GCN improved the Micro-F1 score by approximately 3 percentage points over standard GCN. Ablation studies confirmed that modeling label-label correlations is a primary driver of this performance. Furthermore, the performance gap between ML-GCN and standard GCN widened as the training set size increased, suggesting the model is more robust at extracting complex patterns from available data.

Discussion and Future Work

By elevating labels to "first-class citizens" with their own learnable vector representations, ML-GCN explicitly learns the topology of the label space. This acts as a powerful regularizer, preventing the GCN from smoothing nodes into a generic, indistinguishable state.

Future work could involve incorporating node content (such as text descriptions or metadata) into the embedding process to further improve accuracy. Additionally, while negative sampling aids efficiency, the scalability of the label-label correlation matrix in "extreme" multi-label settings with thousands of classes remains an area for further optimization.

Summary updated

BibTeX
@inproceedings{gao2019semi,
  author = {Kaisheng Gao and Jing Zhang and Cangqi Zhou},
  title = {{Semi-supervised Graph Embedding for Multi-label Graph Node Classification}},
  booktitle = {WISE},
  year = {2019},
  doi = {10.1007/978-3-030-34223-4\_35},
}
Figure