Design Space for Graph Neural Networks

Jiaxuan You, Rex Ying, Jure Leskovec

TL;DR

This paper introduces a systematic approach to exploring the vast design space of Graph Neural Networks (GNNs) by defining a comprehensive GNN design space and a GNN task space with a similarity metric. This framework allows for efficient discovery of optimal GNN architectures for new tasks and provides valuable guidelines for GNN design, leading to state-of-the-art performance on challenging benchmarks.

What Problem Does This Paper Address?

The field of Graph Neural Networks (GNNs) has seen rapid growth with numerous novel architectures and applications. However, research often focuses on evaluating individual GNN designs (like GCN, GIN, GAT) for specific tasks, rather than understanding the broader design space. This space is a complex combination of various design choices (e.g., number of layers, aggregation functions). Consequently, finding the best GNN for a new task or dataset is a time-consuming and expensive process of re-exploring the entire design space. Furthermore, existing GNN evaluations are often limited to a narrow set of tasks, hindering the development of generalizable GNNs.

Methods

The authors tackle these challenges by proposing a three-pronged approach:

  1. GNN Design Space: They define a general GNN design space encompassing 12 dimensions across intra-layer design (e.g., batch normalization, activation, aggregation), inter-layer design (e.g., layer connectivity, skip connections), and learning configuration (e.g., learning rate, optimizer). This space comprises 315,000 possible GNN designs.
  2. GNN Task Space with Similarity Metric: To address the issue of specialized GNNs and efficient transfer, they introduce a GNN task space. This space quantifies the similarity between different tasks using a metric based on the Kendall rank correlation of anchor model performance across tasks. This allows for identifying tasks with similar GNN design needs.
  3. Efficient Design Space Evaluation: Given the immense size of the combined design and task space (over 10 million combinations), a full grid search is infeasible. The authors propose a controlled random search technique to efficiently distill insights from a large number of model-task combinations. This method involves sampling experiments and analyzing the performance rankings of different design choices.

They also introduce GraphGym, a platform that implements these ideas with modular GNN components, standardized evaluation, and reproducible experiment management.

Datasets

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

  • Synthetic Tasks: 12 node classification tasks and 8 graph classification tasks generated from small-world and scale-free graph families, with varying structural properties and node/graph features.
  • Real-World Tasks: 6 node classification benchmarks and 6 graph classification tasks.
  • New Task Type: Link prediction tasks are also explored in the appendix.

Key Insights and Ideas

  • GNN designs are highly task-specific: The "best" GNN architecture can vary dramatically depending on the task, meaning a model that excels on one task might perform poorly on another.
  • Task similarity is key for transfer learning: The proposed task similarity metric effectively groups tasks that benefit from similar GNN designs, enabling efficient transfer of learned architectures.
  • Systematic exploration beats individual design focus: Moving from studying individual GNN designs to exploring the entire design space yields more robust insights and better-performing models.
  • Batch Normalization is generally beneficial: Adding Batch Normalization consistently improves GNN performance across various tasks.
  • PRELU activation is a strong contender: The authors discovered that PRELU activation functions perform exceptionally well, a finding that was not widely recognized in prior GNN research.
  • SUM aggregation is theoretically and empirically powerful: The study confirms that SUM aggregation is not only theoretically expressive but also empirically successful in GNNs.

Key Results

  • Comprehensive Design Guidelines: The paper provides a set of guidelines for designing well-performing GNNs based on their extensive evaluation.
  • State-of-the-Art Performance: GNN models discovered through their design space achieved state-of-the-art performance on a challenging new task from the Open Graph Benchmark (ogbg-molhiv). For instance, their best model achieved a ROC AUC of 0.792, outperforming the previous SOTA of 0.771.
  • Efficient Transfer: The task similarity metric allows for efficient identification of promising GNN designs for new tasks, requiring only the evaluation of 12 anchor models instead of a full grid search.
  • Significant Design Dimensions: The study identified 7 out of 12 design dimensions that significantly influence GNN performance.

Limitations and Future Work

  • Design Space Expansion: The authors acknowledge that their defined design space is not exhaustive and can be expanded as new design dimensions emerge in GNN research.
  • Computational Cost: While their evaluation method is efficient, exploring the full design space for very large datasets or complex tasks can still be computationally intensive.
  • Generalizability of Task Similarity: The paper demonstrates the effectiveness of the task similarity metric for the studied tasks, but its generalizability to an even wider and more diverse range of future GNN tasks could be further explored.
  • Future Work: The authors suggest that their framework can inspire researchers to propose and understand new design dimensions and new tasks, fostering a more systematic approach to GNN research. They also highlight the potential for their approach to be applied to other machine learning domains.

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, 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 Rex 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