SEA: Graph Shell Attention in Graph Neural Networks

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

TL;DR

SEA (Graph Shell Attention) introduces a routing mechanism to Graph Neural Networks (GNNs) that allows individual nodes to "choose" which neighborhood depth (or "shell") is most informative for their representation. By treating different $k$-hop neighborhood views as specialized experts, the model effectively combats the common "over-smoothing" problem while achieving state-of-the-art performance with significantly fewer parameters than massive graph transformers.

What Problem Does This Paper Address?

Standard GNNs rely on a message-passing paradigm where nodes iteratively aggregate information from their neighbors. While this captures local structure, it suffers from over-smoothing: as you increase the number of layers ($k$), node representations tend to converge toward a stationary distribution, eventually becoming indistinguishable from one another.

This creates a "one-size-fits-all" dilemma. Some nodes might need deep, long-range information to be classified correctly, while others only need immediate local context. Forcing every node through the same fixed number of iterations washes out the unique localized information. The authors aim to "loosen" this strict workflow by allowing the network to dynamically decide the receptive field for each node.

Methods

The authors propose SEA, which integrates a routing heuristic (inspired by the "Mixture-of-Experts" or MoE approach) into a Graph Transformer architecture.

  1. Graph Shells: A "shell" is essentially a $k$-localized view of a node's neighborhood. The authors define different experts that process these shells in various ways:
  2. SEA-GNN: Experts correspond to different iteration depths of a standard GNN.
  3. SEA-AGGREGATED: Experts use aggregated values from previous iterations to capture more complex dependencies.
  4. SEA-2-HOP: Experts explicitly look at 2-hop linkages, bypassing the intermediate 1-hop step to capture broader context directly.
  5. The Router: For every node, a routing module (a simple linear layer followed by a softmax) calculates the probability of assigning that node to a specific expert. The node’s representation is then computed solely by the "winning" expert.
  6. Transformer Backbone: The experts themselves are built using Graph Transformer Layers (GTL), which use multi-headed attention to weigh the importance of different neighbors within the chosen shell.

Datasets

The model was evaluated on three distinct benchmark datasets:

  • ZINC: A popular molecular dataset where the task is to regress a property called "constrained solubility."
  • ogbg-molhiv: A large-scale molecular dataset from the Open Graph Benchmark where the goal is to predict whether a molecule inhibits HIV replication.
  • PATTERN: A dataset generated via Stochastic Block Models (SBM) used for node-level classification into different communities.

Key Insights and Ideas

  • Dynamic Receptive Fields: The core "aha" moment is that not all nodes in a graph require the same "depth" of field. By routing nodes to experts specializing in different shell depths, the model can simultaneously capture short-term and long-term dependencies without the risk of over-smoothing the entire graph.
  • Combating "Expert Collapsing": A common issue in MoE models is that the router might get stuck picking the same expert for every input. The authors implemented an epsilon-greedy strategy (similar to Reinforcement Learning) during early training to ensure all experts are explored before the model converges.
  • Parameter Efficiency (Green AI): One of the most striking findings is that SEA can match or beat massive models like Graphormer while using a fraction of the parameters. For example, on the molhiv dataset, SEA achieved competitive results while using 99.71% fewer parameters than the best-reported Graphormer model.

Key Results

  • ZINC: The SEA-2-HOP variant achieved a Mean Absolute Error (MAE) of 0.159, significantly outperforming vanilla GNNs and performing competitively with much larger transformer-based models.
  • ogbg-molhiv: The SEA-AGGREGATED model reached a ROC-AUC of 80.18%, placing it among the top-performing models while remaining highly efficient.
  • PATTERN: The SEA-2-HOP model achieved 86.768% accuracy, beating the previous state-of-the-art (SAN) and demonstrating that $k$-hop information is crucial for community detection tasks.
  • Specialization: Visualization of expert distribution showed that for molecular data, nodes are widely distributed across different experts, confirming that different atoms/bonds require different topological "views" to be represented accurately.

Limitations and Future Work

  • Complexity of Routing: While the model is parameter-efficient, the routing mechanism adds a layer of architectural complexity and requires careful tuning (like the epsilon-decay) to avoid expert collapse.
  • Fixed Hyperparameters: Currently, all experts share the same general hyperparameter settings (like embedding size). The authors suggest that future work could involve using different hyperparameters for different shells (e.g., smaller embeddings for local shells and larger ones for global shells).
  • Scaling: While tested on standard benchmarks, the performance of the routing mechanism on extremely large, dense social networks (where over-smoothing is most rampant) remains an open area for exploration.

Summary updated

Abstract

A common problem in Graph Neural Networks (GNNs) is known as over-smoothing. By increasing the number of iterations within the message-passing of GNNs, the nodes’ representations of the input graph align and become indiscernible. The latest models employing attention mechanisms with Graph Transformer Layers (GTLs) are still restricted to the layer-wise computational workflow of a GNN that are not beyond preventing such effects. In our work, we relax the GNN architecture by means of implementing a routing heuristic. Specifically, the nodes’ representations are routed to dedicated experts. Each expert calculates the representations according to their respective GNN workflow. The definitions of distinguishable GNNs result from k-localized views starting from the central node. We call this procedure Graph Sh ell Attention (SEA), where experts process different subgraphs in a transformer-motivated fashion. Intuitively, by increasing the number of experts, the models gain in expressiveness such that a node’s representation is solely based on nodes that are located within the receptive field of an expert. We evaluate our architecture on various benchmark datasets showing competitive results while drastically reducing the number of parameters compared to state-of-the-art models.
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