ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment

Tomer Borreda [email protected] · 2024

Read ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment by Tomer Borreda [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01519.txt.

Introduction

Tomer Borreda and co-authors present a faster graph transformer in a paper from two thousand twenty-four, with the head byline adding Daniel Freedman and Or Litany. Graph transformers let distant nodes talk directly, but full attention grows quadratically with graph size. That limits their use on large graphs.

Their design borrows the airline hub-and-spoke idea. Nodes, the spokes, attach to a fixed set of virtual hub nodes at each layer. Each node needs only a few hubs, keeping cost linear even with many hubs. A reassignment trick based on hub similarity avoids pricey matching. Tests on long-range benchmarks beat the base virtual-node method and rivaled top models, while a sparse version matched its dense counterpart.

Catalog record

CREATORTomer Borreda [email protected]
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01519

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment Tomer Borreda [email protected] Abstract We present ReHub, a novel graph transformer architecture that achieves linear complexity through an efficient reassignment technique between nodes and virtual nodes. Graph transformers have become increasingly important in graph learning for their ability to utilize long-range node communication explicitly, addressing limitations such as oversmoothing and oversquashing found in message-passing graph networks. However, their dense attention mechanism scales quadratically with the number of nodes, limiting their applicability to large-scale graphs. ReHub draws inspiration from the airline industry’s hub-and-spoke model, where flights are assigned to optimize operational efficiency. In our approach, graph nodes (spokes) are dynamically reassigned to a fixed number of virtual nodes (hubs) at each model layer. Recent work, Neural Atoms ( Li et al., 2024 ) , has demonstrated impressive and consistent improvements over GNN baselines by utilizing such virtual nodes; their findings suggest that the number of hubs strongly influences performance. However, increasing the number of hubs typically raises complexity, requiring a trade-off to maintain linear complexity. Our key insight is that each node only needs to interact with a small subset of hubs to achieve linear complexity, even when the total number of hubs is large. To leverage all hubs without incurring additional computational costs, we propose a simple yet effective adaptive reassignment technique based on hub-hub similarity scores, eliminating the need for expensive node-hub computations. Our experiments on long-range graph benchmarks indicate a consistent improvement in results over the base method, Neural Atoms, while maintaining a linear complexity instead of O ⁡ ( n 3 / 2 ) O(n^{3/2}) . Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive baselines and consistently ranks among the top performers across various benchmarks. Code is available on our project webpage 1 1 1 https://tomerborreda.github.io/rehub/ . 1 Introduction Learning on graphs is essential in numerous domains, including social networks for influence prediction, biological networks for understanding protein interactions, molecular graphs for predicting chemical properties, knowledge graphs for recommendation systems, and financial networks for fraud detection and risk assessment. Graph neural networks (GNNs) have emerged as powerful tools in these areas, operating via message passing between connected nodes. However, a significant challenge with GNNs is their limited communication range. While stacking message-passing layers can increase the communication distance, it comes at a computational cost and can cause issues such as oversmoothing and oversquashing ( Alon & Yahav, 2020 ; Topping et al., 2021 ) . Inspired by the success of transformers in natural language processing ( Vaswani et al., 2017 ) , graph transformers offer a solution by enabling global node communication through attention mechanisms ( Dwivedi & Bresson, 2020 ; Shehzad et al., 2024 ) . This overcomes the communication bottlenecks of GNNs, but it comes at a significant computational cost. The quadratic complexity of dense attention operations limits the scalability of graph transformers, as even modest-sized graphs can exhaust GPU memory. Several methods have been suggested to reduce the complexity of global attention. For example, GraphGPS ( Rampášek et al., 2022 ) combines sparse attention mechanisms like Performer ( Choromanski et al., 2020 ) or Big Bird ( Zaheer et al., 2020 ) . Originally designed for processing sequences rather than graph structure, these linear-memory transformers induce significant computational time and do not match the performance of dense attention ( Shirzad et al., 2023 ) . Recently, transformer-based graph networks have utilized the addition of virtual global nodes, through which graph nodes communicate to sparsify the attention. By constraining the attention to be between the graph nodes and these virtual nodes, the attention complexity is reduced to the number of nodes times the number of virtual nodes, allowing the overall complexity to be governed by the number of virtual nodes. Exphormer ( Shirzad et al., 2023 ) maintains linear complexity by using a fixed number of virtual nodes, while Neural Atoms ( Li et al., 2024 ) explores both a fixed number and a ratio relative to the number of nodes. An important finding in Neural Atoms is that adding more virtual nodes increases prediction accuracy, creating a trade-off between computational complexity and accuracy. In this work, we introduce ReHub, a novel graph transformer architecture that achieves linear complexity by dynamically reassigning graph nodes to virtual nodes. We are inspired by complex systems where efficient connectivity and adaptability are crucial for optimal performance. A pertinent example is the airline industry, where flights are dynamically assigned to a limited number of major airports (hubs) to optimize operational efficiency. We identify the graph nodes with spokes and the virtual nodes with hubs. The key insight of our approach stems from noting that the transformer’s complexity is driven by spoke-hub attention. Therefore, it is not necessary to reduce the total number of hubs to achieve linear complexity; instead, using a fixed, small number of connected hubs per spoke is sufficient. To effectively utilize all hubs without increasing computational cost, we introduce a simple yet efficient adaptive reassignment mechanism. In order to do so, and yet avoid the costly computation of the entire set of spoke-hub interactions, our reassignment mechanism is based on hub-hub similarity scores, which are cheap to compute. In summary, then, our primary contribution is a novel graph transformer architecture that integrates global attention with an efficient spoke-hub reassignment strategy, significantly enhancing scalability while maintaining performance. Our experiments on long-range graph benchmarks indicate a consistent improvement in results over the base method, Neural Atoms, while keeping a linear complexity instead of O(n^{3/2}) . Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive baselines and consistently ranks among the top performers across various benchmarks. 2 Related work Learning on large graphs Graph learning architectures are a well-established and highly active field of research ( Wu et al., 2020 ) . Common GNNs, such as GCN/GCN2 ( Kipf & Welling, 2016 ; Chen et al., 2020 ) , GAT/GATv2 ( Velickovic et al., 2017 ; Brody et al., 2021 ) , GIN/GINE ( Xu et al., 2018 ; Hu et al., 2019 ) , and GatedGCN ( Bresson & Laurent, 2017 ) , rely on a message-passing architecture that aggregates information. In each layer every graph node updates its representation by aggregating the neighboring nodes. This architecture inherently limits their ability to accumulate information over large distances due to phenomena such as over-smoothing ( Alon & Yahav, 2020 ) , where node representations become indistinguishable, and over-squashing ( Topping et al., 2021 ) , where the capacity to propagate information is restricted by bottlenecks. Consequently, learning on large graphs remains a persistent challenge ( Duan et al., 2022 ) . To address this issue, some methods focus on reducing the memory footprint. One approach involves dividing graphs into mini-batches ( Wu et al., 2024 ) , while another uses only segments of the graph for training ( Cao et al., 2024 ) . Transformer architectures have recently gained popularity for graph-based tasks ( Müller et al., 2023 ) . These methods address the over-smoothing and over-squashing issues by enabling all nodes to interact with each other through attention ( Velickovic et al., 2017 ;

Read the complete text