Learning Discrete Adaptive Receptive Fields for Graph Convolutional Networks

Xiaojun Ma, Ziyao Li, Lingjun Xu, Guojie Song, Yi Li, Chuan ShiOpenReview 2020 · OpenReview

TL;DR

This paper introduces Adaptive Receptive Fields (ARFs) for Graph Convolutional Networks (GCNs) to overcome the "over-smoothing" problem of attention mechanisms in large neighborhoods. By learning to discretely select important nodes for convolution, their proposed GRARF model achieves state-of-the-art performance and demonstrates improved robustness to noisy graph data.

What Problem Does This Paper Address?

Graph Convolutional Networks (GCNs) are powerful tools for learning from graph-structured data. A core operation in GCNs is the "convolution," which aggregates information from a node's neighbors. Traditionally, this aggregation involves either treating all neighbors equally or using attention mechanisms to weigh their importance. While attention (like in Graph Attention Networks or GATs) helps GCNs focus on more relevant neighbors, the authors identify a critical issue: in large neighborhoods, these attention weights tend to become "over-smoothed," meaning they all approach zero. This makes it difficult for the model to distinguish truly important nodes from less relevant ones or even noise. Furthermore, standard GCNs typically only consider one-hop neighbors, requiring deep networks to capture long-range dependencies, which can be computationally expensive and lead to further information loss.

Methods

The paper proposes Adaptive Receptive Fields (ARFs) as a novel approach to address these limitations. Instead of using soft attention weights, ARFs discretely select a subset of nodes from multi-hop neighborhoods to form the receptive field for a central node. This discrete selection is key to avoiding the over-smoothing problem.

To learn how to construct these ARFs effectively, the authors introduce GRARF (GCN with Reinforced Adaptive Receptive Fields). GRARF frames the ARF construction process as a Markov Decision Process (MDP). A constructor (an RL agent, specifically using a Deep Q-Learning (DQN) approach) learns an optimal policy for selecting nodes to add to the ARF. The process involves a two-stage action: first selecting a "contact node" within the current ARF, and then selecting a neighbor of that contact node to add to the ARF. The reward for the constructor is derived from the performance of a separate evaluator (a GCN model) that uses the constructed ARF for a downstream task (like node classification). This allows the constructor to learn to build ARFs that lead to better GCN performance. Reward shaping is used to guide the learning process by incorporating heuristics about node importance (degree, feature similarity).

Datasets

GRARF is evaluated on several public, real-world datasets:

  • Citation Networks: Cora, Citeseer, Pubmed (transductive node classification)
  • Social Network: Github (transductive node classification)
  • Protein-Protein Interaction: PPI (inductive node classification)

The paper also introduces two custom experimental setups on the Cora dataset to specifically test the models' robustness to noise and ability to capture long-distance dependencies.

Key Insights and Ideas

  • The "Over-Smoothing" of Soft Attention: The paper provides a theoretical proof (Proposition 1) demonstrating that soft attention weights in GCNs tend to converge to zero as neighborhood sizes increase. This is a fundamental limitation for distinguishing important nodes in large graphs.
  • Discrete Selection as a Solution: By discretely selecting nodes for the receptive field, ARFs bypass the over-smoothing issue inherent in continuous attention weights. This allows for more precise focus on critical contexts.
  • Reinforcement Learning for ARF Construction: Framing ARF construction as an RL problem allows the model to learn complex, data-driven strategies for selecting nodes, rather than relying on fixed heuristics. This is crucial for adapting to different graph structures and tasks.
  • Robustness to Noise: The experimental results strongly suggest that ARFs are significantly more robust to noisy nodes in the graph compared to traditional GCNs and GATs. This is because the ARF constructor learns to filter out irrelevant or noisy neighbors.
  • Efficient Long-Distance Dependency Capture: ARFs can incorporate nodes from multiple hops away, enabling GCNs to capture long-distance dependencies without needing excessively deep architectures.

Key Results

  • State-of-the-Art Performance: GRARF achieves competitive or improved performance on node classification tasks across various datasets, particularly excelling on graphs with larger neighborhoods.
  • Robustness to Noise: In designed experiments with added noise, GRARF's performance degrades much less than vanilla GCNs and GATs, demonstrating its ability to ignore noisy nodes. For instance, in the denoising experiment with a noise ratio of 1, GATs and GCNs dropped significantly below the raw baseline, while GRARF's performance only dropped marginally.
  • Improved Long-Distance Dependency Capture: The LDD experiment also showed GRARF's advantage in capturing information from distant nodes, outperforming baselines that struggle with stretched dependencies.

Limitations and Future Work

  • Simplified ARF Structure: The current ARF definition treats the selected nodes as a set, largely ignoring their underlying graph structure within the ARF. Future work could explore learning optimal convolutional structures on the constructed ARFs.
  • RL Approximation: Finding faster approximations for the RL training process is an area for future research.
  • Global Information for Constructor: The current constructor primarily observes local neighborhoods. Providing it with more global-level information could potentially lead to even better ARF construction.

Summary updated

Abstract

Different nodes in a graph neighborhood generally yield different importance. In previous work of Graph Convolutional Networks (GCNs), such differences are typically modeled with attention mechanisms. However, as we prove in our paper, soft attention weights suffer from over-smoothness in large neighborhoods. To address this weakness, we introduce a novel framework of conducting graph convolutions, where nodes are discretely selected among multi-hop neighborhoods to construct adaptive receptive fields (ARFs). ARFs enable GCNs to get rid of the over-smoothness of soft attention weights, as well as to efficiently explore long-distance dependencies in graphs. We further propose GRARF (GCN with Reinforced Adaptive Receptive Fields) as an instance, where an optimal policy of constructing ARFs is learned with reinforcement learning. GRARF achieves or matches state-of-the-art performances on public datasets from different domains. Our further analysis corroborates that GRARF is more robust than attention models against neighborhood noises.
BibTeX
@misc{ma2020learning,
  author = {Xiaojun Ma and Ziyao Li and Lingjun Xu and Guojie Song and Yi Li and Chuan Shi},
  title = {{Learning Discrete Adaptive Receptive Fields for Graph Convolutional Networks}},
  year = {2020},
  url = {https://openreview.net/forum?id=pHkBwAaZ3UK},
  howpublished = {OpenReview},
}
Figure