SEA: Graph Shell Attention in Graph Neural Networks

Christian M. M. Frey, Yunpu Ma, Matthias Schubert

Introduction

Standard Graph Neural Networks (GNNs) typically rely on a message-passing paradigm where nodes iteratively aggregate information from their immediate neighbors. While effective for capturing local structures, this approach often leads to over-smoothing. As the number of layers ($k$) increases, node representations tend to converge toward a stationary distribution, making them indistinguishable and washing out unique localized features.

This creates a "one-size-fits-all" dilemma: some nodes require deep, long-range information for accurate classification, while others benefit more from immediate local context. SEA (Graph Shell Attention) addresses this by allowing the network to dynamically decide the optimal receptive field for each node.

Methodology: Graph Shell Attention

The core innovation of SEA is the integration of a routing mechanism—inspired by Mixture-of-Experts (MoE) architectures—into a Graph Transformer framework. Instead of a fixed aggregation depth, SEA treats different $k$-hop neighborhood views as specialized "experts."

The SEA architecture featuring a router that assigns nodes to specific graph shell experts.

Key Components

  1. Graph Shells: A "shell" represents a $k$-localized view of a node's neighborhood. The authors propose several expert variants:
  2. SEA-GNN: Experts correspond to different iteration depths.
  3. SEA-AGGREGATED: Experts utilize aggregated values from previous iterations to capture complex dependencies.
  4. SEA-2-HOP: Experts explicitly process 2-hop linkages, bypassing intermediate steps to capture broader context directly.
  5. The Router: For every node, a routing module (a linear layer followed by a softmax) calculates the probability of assignment to a specific expert. The node’s representation is then processed exclusively by the selected "winning" expert.
  6. Transformer Backbone: Experts are constructed using Graph Transformer Layers (GTL), employing multi-headed attention to weigh neighbor importance within the chosen shell.

To prevent "expert collapse"—where the router favors a single expert—the authors utilize an epsilon-greedy strategy during early training to ensure thorough exploration of all shell depths.

Experimental Evaluation

The model was evaluated across three diverse benchmarks:

  • ZINC: A molecular dataset for regression of constrained solubility.
  • ogbg-molhiv: A large-scale challenge to predict HIV replication inhibition.
  • PATTERN: A community detection task based on Stochastic Block Models (SBM).

Results and Discussion

SEA demonstrates that dynamic receptive fields are highly effective. On the ZINC dataset, the SEA-2-HOP variant achieved a Mean Absolute Error (MAE) of 0.159, outperforming standard GNNs. For PATTERN, it reached 86.768% accuracy, surpassing previous state-of-the-art models like SAN.

Performance comparison on the OGBG-MOLHIV dataset, highlighting SEA's parameter efficiency.

One of the most significant findings is SEA's parameter efficiency. As shown in the results for ogbg-molhiv, SEA-AGGREGATED achieved a ROC-AUC of 80.18%, nearly matching the performance of the massive Graphormer-FLAG model (80.51%) while using approximately 99.71% fewer parameters (133K vs. 47M). This highlights SEA's potential for "Green AI" applications where computational resources are limited.

Conclusion

SEA successfully "loosens" the strict message-passing workflow of traditional GNNs. By allowing nodes to choose their neighborhood depth, the model captures multi-scale topological information without the penalty of over-smoothing. Future work may explore heterogeneous hyperparameter settings for different experts, further optimizing the balance between local and global graph views.

Summary updated

BibTeX
@inproceedings{frey2022sea,
  author = {Christian M. M. Frey and Yunpu Ma and Matthias Schubert},
  title = {{SEA: Graph Shell Attention in Graph Neural Networks}},
  booktitle = {ECML/PKDD},
  year = {2022},
  doi = {10.1007/978-3-031-26390-3\_20},
}
Figure