From Local Structures to Size Generalization in Graph Neural Networks
arXiv:2010.08853
Abstract
Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.
arXiv commentCamera ready version for ICML 2021
References in corpus (36)
- Emergence of scaling in random networks
- Semi-Supervised Classification with Graph Convolutional Networks
- Neural Message Passing for Quantum Chemistry
- Spectral Networks and Locally Connected Networks on Graphs
- Fast Graph Representation Learning with PyTorch Geometric
- Learning Combinatorial Optimization Algorithms over Graphs
- Variational Graph Auto-Encoders
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Learning to Simulate Complex Physics with Graph Networks
- How Powerful are Graph Neural Networks?
- Preferential attachment in the growth of social networks: the case of Wikipedia
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
- TUDataset: A collection of benchmark datasets for learning with graphs
- Principal Neighbourhood Aggregation for Graph Nets
- Benchmarking Graph Neural Networks
- PairNorm: Tackling Oversmoothing in GNNs
- Preferential attachment in the protein network evolution
- An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
- Unsupervised Domain Adaptation through Self-Supervision
- Measuring abstract reasoning in neural networks
- Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
- Self-supervised Learning on Graphs: Deep Insights and New Direction
- How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
- When Does Self-Supervision Help Graph Convolutional Networks?
- Generalization and Representational Limits of Graph Neural Networks
- Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
- Learning the Travelling Salesperson Problem Requires Rethinking Generalization
- Self-Supervised Learning for Domain Adaptation on Point-Clouds
- Can Graph Neural Networks Count Substructures?
- What graph neural networks cannot learn: depth vs width
- Keep It Simple: Graph Autoencoders Without Graph Convolutional Networks
- Evaluating Logical Generalization in Graph Neural Networks
- A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
- Global Attention Improves Graph Networks Generalization
- Molecule Property Prediction and Classification with Graph Hypernetworks
- Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks