Collaborative Graph Walk for Semi-Supervised Multi-label Node Classification

Uchenna Akujuobi, Yufei Han, Qiannan Zhang, Xiangliang Zhang

Abstract

Multi-Label-Graph-Walk (MLGW) is a novel reinforcement learning framework designed for multi-label node classification in attributed graphs. By deploying label-specific agents that explore the graph guided by a centralized policy, MLGW captures complex label correlations and learns task-specific node representations. Experimental results on large-scale citation networks demonstrate that MLGW significantly outperforms traditional unsupervised embedding methods and state-of-the-art graph neural networks by directly optimizing for the classification task.

Introduction

In real-world networks, such as social media or academic citation graphs, nodes are often associated with multiple labels and rich attributes. Traditional methods for multi-label node classification frequently struggle with three key challenges: capturing intricate label dependencies, optimizing embeddings specifically for the classification task (rather than using task-agnostic unsupervised embeddings), and operating effectively under data scarcity in semi-supervised settings. This paper proposes MLGW, an end-to-end reinforcement learning approach that addresses these issues by treating classification as a sequential decision-making process.

Methodology

MLGW formulates node classification as a Partially Observed Markov Decision Process (POMDP). The framework employs multiple label-specific agents, each tasked with navigating the graph to find informative nodes for its respective label.

Agent Architecture

At each time step $t$, an agent at node $v_t$ uses a Score Network to evaluate neighboring nodes and select the next destination. Simultaneously, a History Network, implemented as a Gated Recurrent Unit (GRU), maintains a summary of the walk's path, ensuring that the agent's state incorporates historical context rather than just the current location.

Architecture of the MLGW framework showing the interaction between the Score Network, History Network, and the graph environment.

Collaborative Policy Learning

To model label correlations, MLGW utilizes a centralized policy inspired by the Distral framework. This global policy acts as a regularizer, encouraging individual label agents to share knowledge while maintaining label-specific nuances. Agents receive a delayed reward ($+1$ for correct classification, $-1$ for incorrect) only at the end of a walk of length $T$, driving them to seek the most discriminative features across the graph.

Experimental Evaluation

The model was evaluated on three major datasets: DBLP (a co-authorship graph), and Delve-M and Delve-R (large-scale citation networks with over 1.2 million nodes). Node attributes were derived from text using Latent Semantic Analysis (LSI), and edge attributes were extracted from citation contexts.

Results

MLGW consistently outperformed baselines such as GraphSAGE and Node2vec across various metrics. On the DBLP dataset, MLGW achieved Micro-F1 scores of 88-89%, surpassing GraphSAGE by 3-4 percentage points. The results on the Delve-M dataset, as shown in the table below, further highlight the model's superior performance in both transductive and inductive settings.

Performance comparison on the Delve-M dataset showing Precision, Recall, and F1 scores for MLGW variants against several baselines.

Discussion and Conclusion

The success of MLGW stems from its ability to perform dynamic feature selection through graph walks and its end-to-end optimization. By directly shaping node representations through classification rewards, the model avoids the pitfalls of task-agnostic embeddings. Furthermore, the use of policies allows the model to generalize to new nodes (inductive learning). Future work may explore adaptive walk lengths to improve computational efficiency and strategies to manage memory constraints in massive graphs.

Summary updated

BibTeX
@inproceedings{akujuobi2019collaborative,
  author = {Uchenna Akujuobi and Yufei Han and Qiannan Zhang and Xiangliang Zhang},
  title = {{Collaborative Graph Walk for Semi-Supervised Multi-label Node Classification}},
  booktitle = {ICDM},
  year = {2019},
  url = {https://openreview.net/forum?id=IUtK6rM70t_},
}
Figure