A Hierarchy of Graph Neural Networks Based on Learnable Local Features

Abstract

Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we propose a hierarchy of GNNs based on their aggregation regions. We derive theoretical results about the discriminative power and feature representation capabilities of each class. Then, we show how this framework can be utilized to systematically construct arbitrarily powerful GNNs. As an example, we construct a simple architecture that exceeds the expressiveness of the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theory on both synthetic and real-world benchmarks, and demonstrate our example's theoretical power translates to strong results on node classification, graph classification, and graph regression tasks.

References in corpus (8)

• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Graph Neural Networks: A Review of Methods and Applications
• Simplifying Graph Convolutional Networks
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Graph Capsule Convolutional Neural Networks
• RetGK: Graph Kernels based on Return Probabilities of Random Walks

Cited by in corpus (4)

• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Graph Neural Networks with Local Graph Parameters
• AMR Parsing with Action-Pointer Transformer
• Structure-aware Fine-tuning of Sequence-to-sequence Transformers for Transition-based AMR Parsing