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.
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.
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