How does over-squashing affect the power of GNNs?
METADATA ONLY
Loading...
Author / Producer
Date
2023-06
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). Given their widespread use, understanding the expressive power of MPNNs is a key question. However, existing results typically consider settings with uninformative node features. In this paper, we provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We do so by measuring the level of \emph{pairwise interactions} between nodes that MPNNs allow for. This measure provides a novel quantitative characterization of the so-called over-squashing effect, which is observed to occur when a large volume of messages is aggregated into fixed-size vectors. Using our measure, we prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending on properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that \emph{over-squashing hinders the expressive power of MPNNs}. We validate our theoretical findings through extensive controlled experiments and ablation studies.
Permanent link
Publication status
published
Editor
Book title
Journal / series
Volume
2023-27
Pages / Article No.
Publisher
Seminar for Applied Mathematics, ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03851 - Mishra, Siddhartha / Mishra, Siddhartha
Notes
Funding
Related publications and datasets
Is previous version of: