Exploration Degree Bias: The Hidden Influence of Node Degree in Graph Neural Network-Based Reinforcement Learning

Graph Neural Networks (GNNs) have demonstrated remarkable performance in tasks involving graph-structured data, but they also exhibit biases linked to node degrees. This paper explores a specific manifestation of such bias, termed Exploration Degree Bias (EDB), in the context of Reinforcement Learning (RL). We show that EDB arises from the inherent design of GNNs, where nodes with high or low degrees disproportionately influence output logits used for decision-making. This phenomenon impacts exploration in RL, skewing it away from mid-degree nodes, potentially hindering the discovery of optimal policies. We provide a systematic investigation of EDB across widely used GNN architectures-GCN, GraphSAGE, GAT, and GIN-by quantifying correlations between node degrees and logits. Our findings reveal that EDB varies by architecture and graph configuration, with GCN and GIN exhibiting the strongest biases. Moreover, analysis of DQN and PPO RL agents illustrates how EDB can distort exploration patterns, with DQN exhibiting EDB under low exploration rates and PPO showing a partial ability to counteract these effects through its probabilistic sampling mechanism. Our contributions include defining and quantifying EDB, providing experimental insights into its existence and variability, and analyzing its implications for RL. These findings underscore the need to address degree-related biases in GNNs to enhance RL performance on graph-based tasks.