Design Space for Graph Neural Networks

Jiaxuan You, Zhitao Ying, Jure Leskovec

TL;DR

This paper tackles the challenge of navigating the vast design space of Graph Neural Networks (GNNs) by proposing a systematic approach that considers both GNN architectures and task similarities. They introduce a comprehensive GNN design space and a novel task similarity metric, enabling efficient discovery of optimal GNNs for new tasks and providing valuable design guidelines.

What Problem Does This Paper Address?

The field of Graph Neural Networks (GNNs) is rapidly advancing, with new architectures and applications emerging constantly. However, research often focuses on evaluating individual GNN designs (like GCN, GIN, GAT) rather than exploring the broader "design space" – the combinatorial possibilities of different architectural choices (e.g., number of layers, aggregation functions). This makes it difficult to quickly find the best GNN for a novel task or dataset, as re-evaluating the entire design space for each new problem is prohibitively expensive. Furthermore, current GNN evaluations are often limited to a small set of benchmark tasks, hindering the understanding of how designs generalize.

Methods

The authors propose a three-pronged approach:

  1. General GNN Design Space: They define a comprehensive design space encompassing 12 dimensions across intra-layer design (e.g., batch normalization, activation functions, aggregation), inter-layer design (e.g., layer connectivity, number of layers), and learning configuration (e.g., batch size, learning rate). This space comprises over 315,000 possible GNN designs.
  2. GNN Task Space with Similarity Metric: To address the issue of task-specific designs, they introduce a quantitative metric to measure the similarity between different tasks. This metric relies on evaluating a fixed set of "anchor models" across tasks and computing the Kendall rank correlation of their performance. This allows for transferring successful designs from similar tasks.
  3. Efficient Design Space Evaluation: Given the immense number of model-task combinations (over 10 million), a full grid search is infeasible. They develop a "controlled random search" technique to efficiently distill insights from this vast space. This involves sampling experiments, ranking design choices within specific dimensions, and analyzing the distribution of these rankings to understand the general utility of different design elements. They also introduce GraphGym, a platform to facilitate this exploration with modular implementations and standardized evaluation.

Datasets

The paper utilizes a collection of 32 diverse GNN tasks/datasets for evaluation, including:

  • Synthetic Tasks: 12 node classification and 8 graph classification tasks generated from small-world and scale-free graph models, with varying node features and labels.
  • Real-world Tasks: 6 node classification benchmarks and 6 graph classification tasks.

They also mention using the Open Graph Benchmark (OGB) dataset, specifically ogbg-molhiv, for a challenging case study.

Key Insights and Ideas

  • Design Space is Crucial: Focusing on individual GNN designs is insufficient; understanding the broader design space is key to unlocking better performance and generalization.
  • Task Similarity Matters: The best GNN architecture is highly task-dependent. A task similarity metric is essential for transferring knowledge and avoiding redundant effort when tackling new problems.
  • General Design Guidelines Emerge: Despite task-specific variations, their systematic evaluation reveals general principles for designing effective GNNs (e.g., the utility of Batch Normalization, the surprising effectiveness of PRELU activation, and the theoretical expressiveness of SUM aggregation).
  • Novelty in Activation Functions: The paper highlights PRELU as a surprisingly effective activation function for GNNs, a finding not widely explored in prior work.
  • Transferability is Real: The task similarity metric effectively predicts how well a GNN design will transfer to a new task, enabling efficient model selection.

Key Results

  • Comprehensive Design Guidelines: The paper provides a set of guidelines for designing well-performing GNNs based on their extensive analysis.
  • Task-Specific Designs Vary: The optimal GNN designs differ significantly across tasks, underscoring the need for their task space approach.
  • Successful Transfer Learning: Their task similarity metric allows for efficient transfer of best designs across similar tasks, saving significant computational resources compared to grid search.
  • State-of-the-Art Performance: Models discovered using their design space achieve state-of-the-art performance on a challenging new task from the Open Graph Benchmark (ogbg-molhiv). For instance, their best GNN model achieved an ROC AUC of 0.792, outperforming the previous SOTA of 0.771.
  • Efficiency Gains: Their controlled random search technique reduces the number of experiments by over 1,000 times compared to a full grid search.

Limitations and Future Work

  • Expanding the Design Space: The authors acknowledge that their design space can be expanded as new design dimensions emerge in state-of-the-art models.
  • Task Space Generalization: While they collected 32 diverse tasks, the approach is general and can be applied to any novel GNN task. Future work could involve applying this to even larger and more diverse sets of tasks.
  • Computational Cost: While their method significantly reduces computational cost, evaluating the full design space across many tasks still requires substantial resources.
  • Focus on Message Passing GNNs: Their work primarily focuses on message-passing GNNs due to their proven performance. Future work could explore other GNN paradigms.

Summary updated

Abstract

The rapid evolution of Graph Neural Networks (GNNs) has led to a growing number of new architectures as well as novel applications. However, current research focuses on proposing and evaluating specific architectural designs of GNNs, such as GCN, GIN, or GAT, as opposed to studying the more general design space of GNNs that consists of a Cartesian product of different design dimensions, such as the number of layers or the type of the aggregation function. Additionally, GNN designs are often specialized to a single task, yet few efforts have been made to understand how to quickly find the best GNN design for a novel task or a novel dataset. Here we define and systematically study the architectural design space for GNNs which consists of 315,000 different designs over 32 different predictive tasks. Our approach features three key innovations: (1) A general GNN design space; (2) a GNN task space with a similarity metric, so that for a given novel task/dataset, we can quickly identify/transfer the best performing architecture; (3) an efficient and effective design space evaluation method which allows insights to be distilled from a huge number of model-task combinations. Our key results include: (1) A comprehensive set of guidelines for designing well-performing GNNs; (2) while best GNN designs for different tasks vary significantly, the GNN task space allows for transferring the best designs across different tasks; (3) models discovered using our design space achieve state-of-the-art performance. Overall, our work offers a principled and scalable approach to transition from studying individual GNN designs for specific tasks, to systematically studying the GNN design space and the task space. Finally, we release GraphGym, a powerful platform for exploring different GNN designs and tasks. GraphGym features modularized GNN implementation, standardized GNN evaluation, and reproducible and scalable experiment management.
BibTeX
@inproceedings{you2020design,
  author = {Jiaxuan You and Zhitao Ying and Jure Leskovec},
  title = {{Design Space for Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=ug9liLyfK-},
}
Figure