Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (25) · 20553-20561
DOI: 10.1609/aaai.v40i25.39191 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Jeongwhan Choi und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Graph Neural Networks (GNNs) have emerged as powerful tools for learning on graph-structured data, but often struggle to balance local and global information. While graph Transformers aim to address this by enabling long-range interactions, they often overlook the inherent locality and efficiency of Message Passing Neural Networks (MPNNs). We propose a new concept called 'fractal nodes', inspired by the fractal structure observed in real-world networks. Our approach is based on the intuition that graph partitioning naturally induces fractal structure, where subgraphs often reflect the connectivity patterns of the full graph. Fractal nodes are designed to coexist with the original nodes and adaptively aggregate subgraph-level feature representations, thereby enforcing feature similarity within each subgraph. We show that fractal nodes alleviate the over-squashing problem by providing direct shortcut connections that enable long-range propagation of subgraph-level representations. Experiment results show that our method improves the expressive power of MPNNs and achieves comparable or better performance to graph Transformers while maintaining the computational efficiency of MPNN by improving the long-range dependencies of MPNN.
Zitieren
APA
Choi, J., Park, S., Park, S., Cho, S., & Park, N. (2026). Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs. Proceedings of the AAAI Conference on Artificial Intelligence, 40(25), 20553-20561. https://doi.org/10.1609/aaai.v40i25.39191
Vancouver
Choi J, Park S, Park S, Cho S, Park N. Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(25):20553-20561. doi:10.1609/aaai.v40i25.39191
BibTeX
@article{Choi2026,
author = {Choi, Jeongwhan and Park, Seungjun and Park, Sumin and Cho, Sung-Bae and Park, Noseong},
title = {Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {25},
pages = {20553--20561},
doi = {10.1609/aaai.v40i25.39191}
}
EUVIMED