TL;DR
This paper provides a significant theoretical advancement for understanding how Graph Neural Networks (GNNs) generalize, both when data comes from the same distribution (in-distribution) and when it differs (out-of-distribution). They achieve tighter bounds for in-distribution generalization by reducing a dependency on node degree and offer new theoretical guarantees for out-of-distribution size generalization, showing GNNs can handle graphs of varying sizes effectively under certain conditions.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are incredibly powerful for learning from graph-structured data, which naturally varies in size (number of nodes and edges). However, our theoretical understanding of why GNNs generalize well, especially when faced with data that differs from what they were trained on (out-of-distribution or OOD generalization), has lagged behind their empirical success. Specifically, existing theoretical bounds for in-distribution generalization often have dependencies on graph properties like node degree that are overly pessimistic. For OOD generalization, particularly concerning variations in graph size, there's a lack of rigorous guarantees. This paper aims to bridge this gap by providing improved theoretical bounds for both scenarios.
Methods
The authors tackle two main areas:
- In-Distribution Generalization: They improve upon existing PAC-Bayes generalization bounds for GNNs. The key innovation is reducing an exponential dependency on the maximum node degree in the bound to a linear one. This is achieved through a more refined mathematical analysis of the GNN's internal representations and their perturbation.
- Out-of-Distribution (OOD) Size Generalization: They leverage tools from spectral graph theory to provide rigorous guarantees for GNNs when training and testing graphs have different numbers of nodes and edges. Their approach involves sampling subgraphs via random walks from a single large underlying graph, which is a more realistic OOD setting than assuming specific generative models. They identify conditions under which GNNs can effectively generalize to larger graphs.
Datasets
The paper uses a combination of datasets for empirical validation:
- Synthetic Datasets: Erdos-Renyi (ER) and Stochastic Block Models (SBM) are used for in-distribution experiments. For OOD experiments, they generate synthetic graphs using a modified Stochastic Block Model (CSBM) to control homophily and graph size.
- Real-world Datasets: IMDB-BINARY, IMDB-MULTI, COLLAB, and PROTEINS are used for in-distribution experiments. For OOD experiments, they use Twitch streamer data.
Key Insights and Ideas
- Tighter Bounds for In-Distribution Generalization: The reduction of the node degree dependency from exponential to linear is a significant theoretical improvement, making the bounds more practical and less pessimistic, especially for graphs with high-degree nodes.
- Random Walks for OOD Generalization: Using random walks to sample subgraphs from a large underlying graph provides a more natural and theoretically tractable way to model OOD size generalization compared to relying on predefined generative models.
- Homophily Matters for Size Generalization: The experiments suggest that homophily (the tendency for similar nodes to connect) plays a crucial role in enabling effective size generalization. Non-homophilic graphs show a larger drop in performance when generalizing to different sizes.
- GNNs Can Be Robust to Size Changes: Under the conditions derived by the theory, GNNs demonstrate strong size generalization, with OOD test accuracy often comparable to or even better than in-distribution accuracy on smaller subgraphs.
Key Results
- In-Distribution: The paper reports significant improvements in numerical calculations of generalization gaps, reducing them by several orders of magnitude compared to previous state-of-the-art PAC-Bayes bounds. This improvement is more pronounced with increased GNN depth.
- Out-of-Distribution:
- The theoretical framework identifies conditions (related to random walk length and graph properties) under which size generalization is guaranteed.
- Empirical results on synthetic and real-world graphs show that GNNs achieve comparable or better OOD test accuracy on larger subgraphs when the theoretical conditions are met.
- Even when theoretical constraints are violated (e.g., non-d-regular graphs), GNNs still exhibit surprisingly effective size generalization, suggesting the theory provides a useful, albeit not exhaustive, understanding.
Limitations and Future Work
- Limitations:
- The theoretical bounds for OOD generalization still rely on certain assumptions, such as the graph being d-regular, which are not always met in real-world scenarios.
- The derived upper bounds for M (related to random walk length for OOD generalization) were sometimes too small for practical experimental use on real-world datasets, necessitating the use of fixed N and M values.
- Future Work:
- Lowering dependencies on other variables in in-distribution bounds, such as the spectral norm of weights.
- Generalizing in-distribution results to other tasks like node classification.
- Expanding the OOD theory to non-d-regular graphs and exploring other OOD settings beyond size generalization.
- Investigating why GNNs perform well even when theoretical assumptions are violated.
Summary updated