Nested Graph Neural Networks

Abstract

Graph neural network (GNN)'s success in graph classification is closely related to the Weisfeiler-Lehman (1-WL) algorithm. By iteratively aggregating neighboring node features to a center node, both 1-WL and GNN obtain a node representation that encodes a rooted subtree around the center node. These rooted subtree representations are then pooled into a single representation to represent the whole graph. However, rooted subtrees are of limited expressiveness to represent a non-tree graph. To address it, we propose Nested Graph Neural Networks (NGNNs). NGNN represents a graph with rooted subgraphs instead of rooted subtrees, so that two graphs sharing many identical subgraphs (rather than subtrees) tend to have similar representations. The key is to make each node representation encode a subgraph around it more than a subtree. To achieve this, NGNN extracts a local subgraph around each node and applies a base GNN to each subgraph to learn a subgraph representation. The whole-graph representation is then obtained by pooling these subgraph representations. We provide a rigorous theoretical analysis showing that NGNN is strictly more powerful than 1-WL. In particular, we proved that NGNN can discriminate almost all r-regular graphs, where 1-WL always fails. Moreover, unlike other more powerful GNNs, NGNN only introduces a constant-factor higher time complexity than standard GNNs. NGNN is a plug-and-play framework that can be combined with various base GNNs. We test NGNN with different base GNNs on several benchmark datasets. NGNN uniformly improves their performance and shows highly competitive performance on all datasets.

arXiv commentAccepted to NeurIPS 2021

References in corpus (13)

• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Fast Graph Representation Learning with PyTorch Geometric
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• DeeperGCN: All You Need to Train Deeper GCNs
• Invariant and Equivariant Graph Networks
• Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings
• Natural Graph Networks
• Building powerful and equivariant graph neural networks with structural message-passing
• Deep Graph Neural Networks with Shallow Subgraph Samplers
• Graph convolutions that can finally model local structure

Cited by in corpus (5)

• A Comprehensive Survey on Deep Graph Representation Learning
• A Network Science perspective of Graph Convolutional Networks: A survey
• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information
• Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormer
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings