Understanding Oversquashing in GNNs through the Lens of Effective Resistance

Mitchell Black, Zhengchao Wan, Amir Nayyeri, Yusu Wang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2528-2547, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-black23a, title = {Understanding Oversquashing in {GNN}s through the Lens of Effective Resistance}, author = {Black, Mitchell and Wan, Zhengchao and Nayyeri, Amir and Wang, Yusu}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2528--2547}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/black23a/black23a.pdf}, url = {https://proceedings.mlr.press/v202/black23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Understanding Oversquashing in GNNs through the Lens of Effective Resistance %A Mitchell Black %A Zhengchao Wan %A Amir Nayyeri %A Yusu Wang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-black23a %I PMLR %P 2528--2547 %U https://proceedings.mlr.press/v202/black23a.html %V 202 %X 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.
APA
Black, M., Wan, Z., Nayyeri, A. & Wang, Y.. (2023). Understanding Oversquashing in GNNs through the Lens of Effective Resistance. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2528-2547 Available from https://proceedings.mlr.press/v202/black23a.html.

Related Material