Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs

• URL: http://arxiv.org/abs/2511.13010v1
• Date: Mon, 17 Nov 2025 06:11:52 GMT
• Title: Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
• Authors: Jeongwhan Choi, Seungjun Park, Sumin Park, Sung-Bae Cho, Noseong Park,
• Abstract summary: We propose a new concept called fractal nodes, inspired by the fractal structure observed in real-world networks.<n>We show that fractal nodes alleviate the over-squashing problem by providing direct shortcut connections.<n>Experiment results show that our method improves the expressive power of MPNNs and achieves comparable or better performance to graph Transformers.
• Score: 34.8056394030225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Parallelizing Node-Level Explainability in Graph Neural Networks [0.3262230127283452]
  Graph Neural Networks (GNNs) have demonstrated remarkable performance in a wide range of tasks.<n>In node classification, node-level explainability becomes extremely time-consuming as the size of the graph increases.<n>This paper introduces a novel approach to parallelizing node-level explainability in GNNs through graph partitioning.
  arXiv  Detail & Related papers  (2026-01-08T10:39:48Z)
• Probabilistic Graph Rewiring via Virtual Nodes [21.273828055299408]
  Message-passing graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning.<n>MPNNs face challenges such as under-reaching and over-squashing, where limited receptive fields and structural bottlenecks hinder information flow in the graph.<n>Here, we propose implicitly rewired message-passing neural networks (IPR-MPNNs), a novel approach that integrates implicit probabilistic graph rewiring into MPNNs.
  arXiv  Detail & Related papers  (2024-05-27T16:11:49Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Boosting Graph Neural Networks by Injecting Pooling in Message Passing [4.952681349410351]
  We propose a new, adaptable, and powerful MP framework to prevent over-smoothing. Our bilateral-MP estimates a pairwise modular gradient by utilizing the class information of nodes. Experiments on five medium-size benchmark datasets indicate that the bilateral-MP improves performance by alleviating over-smoothing.
  arXiv  Detail & Related papers  (2022-02-08T08:21:20Z)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning. We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
  arXiv  Detail & Related papers  (2021-08-03T17:57:53Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale (GAS) is a framework for scaling arbitrary message-passing GNNs to large graphs. Gas prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations. Gas reaches state-of-the-art performance on large-scale graphs.
  arXiv  Detail & Related papers  (2021-06-10T09:26:56Z)
• Data-Driven Learning of Geometric Scattering Networks [74.3283600072357]
  We propose a new graph neural network (GNN) module based on relaxations of recently proposed geometric scattering transforms. Our learnable geometric scattering (LEGS) module enables adaptive tuning of the wavelets to encourage band-pass features to emerge in learned representations.
  arXiv  Detail & Related papers  (2020-10-06T01:20:27Z)
• Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks [0.0]
  Graph convolutional networks (GCNs) have shown promising results in processing graph data by extracting structure-aware features. Here, we propose to augment conventional GCNs with geometric scattering transforms and residual convolutions. The former enables band-pass filtering of graph signals, thus alleviating the so-called oversmoothing often encountered in GCNs.
  arXiv  Detail & Related papers  (2020-03-18T18:03:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.