PANDA: Expanded Width-Aware Message Passing Beyond Rewiring

Jeongwhan Choi, Sumin Park, Hyowon Wi, Sung-Bae Cho, Noseong Park
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:8740-8761, 2024.

Abstract

Recent research in the field of graph neural network (GNN) has identified a critical issue known as "over-squashing," resulting from the bottleneck phenomenon in graph structures, which impedes the propagation of long-range information. Prior works have proposed a variety of graph rewiring concepts that aim at optimizing the spatial or spectral properties of graphs to promote the signal propagation. However, such approaches inevitably deteriorate the original graph topology, which may lead to a distortion of information flow. To address this, we introduce an expanded width-aware (PANDA) message passing, a new message passing paradigm where nodes with high centrality, a potential source of over-squashing, are selectively expanded in width to encapsulate the growing influx of signals from distant nodes. Experimental results show that our method outperforms existing rewiring methods, suggesting that selectively expanding the hidden state of nodes can be a compelling alternative to graph rewiring for addressing the over-squashing.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-choi24f, title = {{PANDA}: Expanded Width-Aware Message Passing Beyond Rewiring}, author = {Choi, Jeongwhan and Park, Sumin and Wi, Hyowon and Cho, Sung-Bae and Park, Noseong}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {8740--8761}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/choi24f/choi24f.pdf}, url = {https://proceedings.mlr.press/v235/choi24f.html}, abstract = {Recent research in the field of graph neural network (GNN) has identified a critical issue known as "over-squashing," resulting from the bottleneck phenomenon in graph structures, which impedes the propagation of long-range information. Prior works have proposed a variety of graph rewiring concepts that aim at optimizing the spatial or spectral properties of graphs to promote the signal propagation. However, such approaches inevitably deteriorate the original graph topology, which may lead to a distortion of information flow. To address this, we introduce an expanded width-aware (PANDA) message passing, a new message passing paradigm where nodes with high centrality, a potential source of over-squashing, are selectively expanded in width to encapsulate the growing influx of signals from distant nodes. Experimental results show that our method outperforms existing rewiring methods, suggesting that selectively expanding the hidden state of nodes can be a compelling alternative to graph rewiring for addressing the over-squashing.} }
Endnote
%0 Conference Paper %T PANDA: Expanded Width-Aware Message Passing Beyond Rewiring %A Jeongwhan Choi %A Sumin Park %A Hyowon Wi %A Sung-Bae Cho %A Noseong Park %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-choi24f %I PMLR %P 8740--8761 %U https://proceedings.mlr.press/v235/choi24f.html %V 235 %X Recent research in the field of graph neural network (GNN) has identified a critical issue known as "over-squashing," resulting from the bottleneck phenomenon in graph structures, which impedes the propagation of long-range information. Prior works have proposed a variety of graph rewiring concepts that aim at optimizing the spatial or spectral properties of graphs to promote the signal propagation. However, such approaches inevitably deteriorate the original graph topology, which may lead to a distortion of information flow. To address this, we introduce an expanded width-aware (PANDA) message passing, a new message passing paradigm where nodes with high centrality, a potential source of over-squashing, are selectively expanded in width to encapsulate the growing influx of signals from distant nodes. Experimental results show that our method outperforms existing rewiring methods, suggesting that selectively expanding the hidden state of nodes can be a compelling alternative to graph rewiring for addressing the over-squashing.
APA
Choi, J., Park, S., Wi, H., Cho, S. & Park, N.. (2024). PANDA: Expanded Width-Aware Message Passing Beyond Rewiring. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:8740-8761 Available from https://proceedings.mlr.press/v235/choi24f.html.

Related Material