Breaking the Expressive Bottlenecks of Graph Neural Networks
arXiv:2012.07219
Abstract
Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressiveness of graph neural networks (GNNs), showing that the neighborhood aggregation GNNs were at most as powerful as 1-WL test in distinguishing graph structures. There were also improvements proposed in analogy to -WL test (). However, the aggregators in these GNNs are far from injective as required by the WL test, and suffer from weak distinguishing strength, making it become expressive bottlenecks. In this paper, we improve the expressiveness by exploring powerful aggregators. We reformulate aggregation with the corresponding aggregation coefficient matrix, and then systematically analyze the requirements of the aggregation coefficient matrix for building more powerful aggregators and even injective aggregators. It can also be viewed as the strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to a special case of low-rank transformations. We also show the necessity of applying nonlinear units ahead of aggregation, which is different from most aggregation-based GNNs. Based on our theoretical analysis, we develop two GNN layers, ExpandingConv and CombConv. Experimental results show that our models significantly boost performance, especially for large and densely connected graphs.
References in corpus (19)
- Semi-Supervised Classification with Graph Convolutional Networks
- Neural Message Passing for Quantum Chemistry
- Geometric deep learning: going beyond Euclidean data
- Fast Graph Representation Learning with PyTorch Geometric
- Representation Learning on Graphs with Jumping Knowledge Networks
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- DeeperGCN: All You Need to Train Deeper GCNs
- Principal Neighbourhood Aggregation for Graph Nets
- Benchmarking Graph Neural Networks
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
- A Survey on The Expressive Power of Graph Neural Networks
- Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
- Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs
- Relational Pooling for Graph Representations
- Hierarchical Inter-Message Passing for Learning on Molecular Graphs
- Building powerful and equivariant graph neural networks with structural message-passing
- Node Masking: Making Graph Neural Networks Generalize and Scale Better
- Wasserstein Embedding for Graph Learning