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

Tomer Borreda, Daniel Freedman, Or Litany

We present ReHub, a novel graph transformer architecture that achieves linear complexity through an efficient reassignment technique between nodes and virtual nodes. Graph transfor…