Graph Actor-Critic: Communication-Aware Message Passing in Graph Neural Networks

Graph neural networks (GNNs) have shown remarkable success on homophilic graphs, where connected nodes tend to share similar features or labels. However, their performance degrades significantly on heterophilic graphs, where connected nodes often have different characteristics. In this work, we propose a novel reinforcement learning (RL) framework for adaptive graph rewiring that learns to dynamically modify graph structure to improve GNN performance on heterophilic graphs. We formulate graph rewiring as a Markov Decision Process (MDP) where an RL agent learns to select actions that optimize a reward function that encourages diverse node representations, thereby minimizing oversmoothing, all without requiring labeled data. We evaluate our method on diverse graph datasets and show that our RL-based rewiring approach, Graph Actor-Critic (GAC), significantly outperforms standard GNNs and existing rewiring methods on heterophilic graphs, while maintaining competitive performance on homophilic graphs.