Research reports

Years: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991

How does over-squashing affect the power of GNNs ?

by F. Di Giovanni and K. Rusch and M. Bronstein and A. Deac and M. Lackenby and S. Mishra and P. Velickovic

(Report number 2023-27)

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.

Keywords: Graph neural networks, Oversquashing, Message passing, expressivity

@Techreport{DRBDLMV23_1064,
  author = {F. Di Giovanni and K. Rusch and M. Bronstein and A. Deac and M. Lackenby and S. Mishra and P. Velickovic},
  title = {How does over-squashing affect the power of GNNs ?},
  institution = {Seminar for Applied Mathematics, ETH Z{\"u}rich},
  number = {2023-27},
  address = {Switzerland},
  url = {https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2023/2023-27.pdf },
  year = {2023}
}

Disclaimer
© Copyright for documents on this server remains with the authors. Copies of these documents made by electronic or mechanical means including information storage and retrieval systems, may only be employed for personal use. The administrators respectfully request that authors inform them when any paper is published to avoid copyright infringement. Note that unauthorised copying of copyright material is illegal and may lead to prosecution. Neither the administrators nor the Seminar for Applied Mathematics (SAM) accept any liability in this respect. The most recent version of a SAM report may differ in formatting and style from published journal version. Do reference the published version if possible (see SAM Publications).