Timezone: »

 
Poster
Understanding Oversquashing in GNNs through the Lens of Effective Resistance
Mitchell Black · Zhengchao Wan · Amir Nayyeri · Yusu Wang

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #712
in Poster Session 1 »

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the effective resistance between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use total effective resistance as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

[ PDF]  [ Poster] 

Author Information

Mitchell Black (Oregon State University)
Zhengchao Wan (UCSD)
Amir Nayyeri (Oregon State University)
Yusu Wang (UC San Diego)

More from the Same Authors