Policy-GNN: Aggregation Optimization for Graph Neural Networks

Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, Xia Hu

Introduction

Graph Neural Networks (GNNs) typically operate by aggregating information from a node's neighbors across multiple layers. Standard practice involves setting a fixed number of layers (e.g., a 2-layer GCN) for the entire graph. However, this "one-size-fits-all" approach fails to account for structural diversity—where some nodes require immediate context and others require broader multi-hop information—and often leads to oversmoothing in deeper architectures.

Policy-GNN addresses these issues by formulating the aggregation process as a Markov Decision Process (MDP). Using Deep Reinforcement Learning (DRL), it adaptively determines the optimal number of aggregation iterations (hops) for each individual node, treating GNN depth as a dynamic, per-node decision.

Methodology: The Meta-Policy Framework

Policy-GNN utilizes a Deep Q-Network (DQN) agent as a "meta-policy" controller. This agent observes a node's attributes (State) and decides how many layers of aggregation to perform (Action). The agent is rewarded based on performance improvements on a validation set, using a baseline reward mechanism to stabilize training.

The Policy-GNN framework architecture, illustrating the interaction between the meta-policy agent and the GNN layers.

To maintain computational efficiency, the authors introduced two key mechanisms:

  1. Parameter Sharing: The model initializes a maximum number of GNN layers and stacks them according to the policy's decision, ensuring only one set of weights is trained.
  2. Buffer Mechanism: Nodes requiring the same number of hops are grouped into batches, allowing for efficient GPU utilization rather than processing nodes individually.

Key Insights: Depth as a Local Property

A core finding of this research is that optimal aggregation depth is a local property. Analysis of standard citation benchmarks (Cora, CiteSeer, and PubMed) reveals that while a majority of nodes favor 2-hop aggregation, a significant minority requires deeper context to be correctly classified.

Distribution of optimal aggregation layers across the Cora, CiteSeer, and PubMed datasets.

As shown in the distribution analysis, up to 35% of nodes in the CiteSeer dataset benefit from 3 or more hops. Policy-GNN's ability to "jump" through the graph to find the most informative neighbors allows it to integrate sampling and learning into a single, adaptive loop.

Experimental Results

Policy-GNN was evaluated against traditional GNNs (GCN, GAT), network embeddings (DeepWalk), and automated Neural Architecture Search (NAS) methods.

  • Accuracy Gains: On the CiteSeer dataset, Policy-GNN achieved an accuracy of 89.7%, representing a 12.7% improvement over the next best baseline (Adapt).
  • Convergence: While the RL-based meta-policy requires more iterations to "warm up" compared to static models, it eventually converges to a significantly higher accuracy ceiling.
  • Mitigating Oversmoothing: By allowing nodes to stop aggregation once they have sufficient information, the model naturally avoids the representation convergence typical of deep, fixed-layer GNNs.

Conclusion and Future Work

Policy-GNN demonstrates that local adaptivity in aggregation depth is essential for handling the structural diversity of complex graphs. By moving from static architectures to dynamic strategies, the framework achieves state-of-the-art results while providing a more robust solution to the oversmoothing problem. Future research directions include scaling the RL agent for massive graphs and jointly optimizing both the type of aggregation functions and the depth of iterations.

Summary updated

BibTeX
@inproceedings{lai2020policy,
  author = {Kwei-Herng Lai and Daochen Zha and Kaixiong Zhou and Xia Hu},
  title = {{Policy-GNN: Aggregation Optimization for Graph Neural Networks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=ZEQ_uh3Yk5s},
}
Figure