Exphormer: Sparse Transformers for Graphs

Hamed ShirzadAmeya VelingkerBalaji VenkatachalamDanica J. SutherlandAli Kemal Sinop

article2023ICML210 citations

Proposes a scalable graph transformer framework that uses expander graphs and virtual global nodes to achieve linear complexity while preserving the expressive power and theoretical guarantees of dense global attention.

Listen

Graph transformers are a powerful class of machine learning models for analyzing interconnected networks, such as molecules, social systems, and citation webs. While traditional graph neural networks often struggle to capture long-range relationships, standard dense graph transformers can capture these dependencies but suffer from quadratic computational and memory scaling. This quadratic bottleneck makes standard transformers prohibitively expensive or impossible to run on large graphs or with standard batch sizes. Previous sparse transformer alternatives, mostly adapted from natural language processing, frequently degrade predictive accuracy and still incur substantial computational overhead on graph data.

The article introduces and evaluates Exphormer, a graph-centric sparse attention framework designed to scale graph transformers to large networks while matching or exceeding the accuracy of dense models and local message-passing networks. Exphormer achieves linear computational and memory complexity relative to the number of nodes and edges by combining three complementary connectivity patterns: local neighborhoods from the input graph, random expander graphs of constant degree that facilitate rapid global information mixing, and virtual global connector nodes that serve as global storage sinks.

The authors conducted comprehensive empirical evaluations across 15 benchmark datasets encompassing image-derived graphs, synthetic community detection benchmarks, malware call graphs, molecular properties, and large citation and co-purchasing networks with up to 169,000 nodes and 1.1 million edges. The primary findings establish that Exphormer consistently outperforms existing sparse attention mechanisms, such as BigBird and Performer, across all evaluated tasks. Furthermore, Exphormer matches or beats dense graph transformers while using substantially fewer parameters (for instance, utilizing 90,000 parameters versus 340,000 on the Pattern dataset) and enabling much larger training batch sizes (such as scaling to a batch size of 256 on the MalNet-Tiny dataset where dense models ran out of memory at a batch size of 16). Exphormer achieved state-of-the-art results on several long-range graph benchmarks and scaled effectively to large graphs where standard transformers failed completely due to memory limits.

These findings demonstrate that organizations can deploy highly accurate, long-range graph transformer architectures at a fraction of the computational and hardware expense previously required. By reducing memory constraints from quadratic to linear, Exphormer mitigates hardware risks, shortens training runtimes, and extends state-of-the-art transformer modeling to large enterprise-scale graphs that were previously intractable. Additionally, theoretical analyses confirm that Exphormer retains spectral approximation and universal function approximation capabilities.

Practitioners implementing Exphormer should tailor the architecture to the specific graph domain, as ablation experiments indicate domain-dependent trade-offs: molecular tasks benefit heavily from virtual global nodes, whereas image-derived graphs benefit more from expander graph connections to avoid global information bottlenecks. While the empirical results are robust across diverse public benchmarks, the authors note that hyperparameter tuning over expander degrees and virtual node counts is necessary, and finding optimal network parameters for specific graph isomorphism tasks remains a theoretical rather than guaranteed algorithmic capability.

Alberta Machine Intelligence Institute Google University of British Columbia encoder-decoder sparse approximations bipartite graphs Exphormer scalable graph transformers sparse transformers

arXiv: 2303.06147 hamed1375/Exphormer

Paper: Recipe for a General, Powerful, Scalable Graph Transformer, Ladislav Rampásek et al. (2022). This paper establishes the GraphGPS blueprint combining local message passing with linear global attention, which Exphormer directly adopts and accelerates using expander graphs.
Paper: Big Bird: Transformers for Longer Sequences, Manzil Zaheer et al. (2020). This foundational work introduces sparse attention patterns utilizing global tokens, local windows, and expander/random graph mechanisms that motivate Exphormer's architectural design on graphs.
Paper: Do Transformers Really Perform Badly for Graph Representation?, Chengxuan Ying et al. (2021). This paper introduces Graphormer and demonstrates how structural and positional encodings enable Transformers to capture graph-structured inductive biases effectively.
Paper: Rethinking Attention with Performers, Krzysztof Choromanski et al. (2021). This work establishes linear-complexity attention approximations that provide foundational context for scalable transformer attention mechanisms.
Paper: Your Transformer May Not be as Powerful as You Expect, Shengjie Luo et al. (2022). This paper analyzes the expressive power and theoretical limits of relative positional encodings in Transformer architectures, underpinning theoretical considerations in graph transformers.

Paper: A Generalization of ViT/MLP-Mixer to Graphs, Xiaoxin He et al. (2023). This paper extends efficient, scalable graph representation learning by generalizing vision transformers and MLP-Mixer architectures with linear complexity via graph patching.
Paper: Specformer: Spectral Graph Neural Networks Meet Transformers, Deyu Bo et al. (2023). This work investigates transformers operating directly across the graph spectral domain to capture global context and overcome spatial limitations.
Paper: On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology, Francesco Di Giovanni et al. (2023). This work analyzes over-squashing and topological bottlenecks in message-passing architectures, providing deep theoretical foundations for why sparse global attention models like Exphormer are essential.

Cover for Exphormer: Sparse Transformers for Graphs

Abstract

Graph transformers have emerged as a promising architecture for a variety of graph learning and representation tasks. Despite their successes, though, it remains challenging to scale graph transformers to large graphs while maintaining accuracy competitive with message-passing networks. In this paper, we introduce EXPHORMER, a framework for building powerful and scalable graph transformers. EXPHORMER consists of a sparse attention mechanism based on two mechanisms: virtual global nodes and expander graphs, whose mathematical characteristics, such as spectral expansion, pseudorandomness, and sparsity, yield graph transformers with complexity only linear in the size of the graph, while allowing us to prove desirable theoretical properties of the resulting transformer models. We show that incorporating EXPHORMER into the recently-proposed GraphGPS framework produces models with competitive empirical results on a wide variety of graph datasets, including state-of-the-art results on three datasets. We also show that EXPHORMER can scale to datasets on larger graphs than shown in previous graph transformer architectures. Codes can be found at https://github.com/hamed1375/Exphormer.

Topics

encoder-decoder sparse approximations bipartite graphs

Keywords

Exphormer scalable graph transformers sparse transformers expander graphs transductive graph datasets GraphGPS structural encodings molecular graphs

1. Introduction
2. Related Work
3. Sparse Attention on Graphs
3.1. Attention mechanism on graphs
3.2. The EXPHORMER Architecture
4. Theoretical Properties of EXPHORMER
4.1. Expander Graphs Approximate Complete Graphs
4.1.1. SPECTRAL PROPERTIES
4.1.2. MIXING PROPERTIES
4.2. Universal Approximability of EXPHORMER Models
5. Experiments
5.1. Comparison to Sparse Attention Mechanisms
5.2. Benchmarking GNNs Datasets
5.3. Long-Range Graph Benchmark
5.4. Scaling to Larger Graphs
5.5. Ablation Studies
6. Conclusion
Acknowledgements
References
A. Dataset Descriptions
B. More Experimental Results
B.1. Hyperparameters
B.2. Full Comparison of Attention Mechanisms
C. Details of Expander Graph Construction
C.1. Ramanujan Graphs
C.2. Random Regular Graphs
D. On Expander Graphs versus Global Connectors
E. Universality of EXPHORMER

Knowls

Knowl 1 — EXPHORMER Sparse Attention Architecture for Graphs
model/method
EXPHORMER is a sparse graph transformer architecture that scales linearly with the size of an underlying input graph $G = (V, E)$ . While standard dense graph transformers compute attention across all $|V|^2$ node pairs, EXPHORMER constructs a sparse undirected interaction graph $H = (V_H, E_H)$ by combining three distinct edge mechanisms:
1. Local Neighborhood Attention: Includes all original input graph edges $E$ and their reverse directions ( $O(|E|)$ interaction edges). This captures local topology and graph connectivity.
2. Expander Graph Attention: Introduces edges from a $d$ -regular expander graph overlay constructed on vertex set $V$ for a small constant degree $d$ ( $O(|V|)$ interaction edges). These expander edges provide small graph diameter ( $O(\log |V|)$ ), rapid random walk mixing, and spectral approximation of the complete graph without creating communication bottlenecks.
3. Virtual Global Nodes Attention: Adds a small constant number $k$ of virtual nodes to the interaction graph ( $|V_H| = |V| + k$ ), where each virtual node connects bidirectionally to every original graph node in $V$ ( $O(k|V|) = O(|V|)$ interaction edges). These act as global storage sinks and information broadcasters.
The combined interaction graph $H$ has $|E_H| = O(|V| + |E|)$ total edges, guaranteeing that self-attention computations scale with linear time and memory complexity in the graph size. EXPHORMER uses a unified multi-head attention mechanism with shared projection matrices across edge types, while distinguishing edge categories through distinct learnable edge feature embeddings.
Knowl 2 — Generalized Graph Attention Mechanism with Edge Features
equation
For an interaction graph $H = (V_H, E_H)$ defined over node embeddings $X = (x_1, x_2, \dots, x_n) \in \mathbb{R}^{d \times n}$ , the dot-product attention aggregation for node $i$ across $h$ attention heads with head dimension $m$ (where $d$ is embedding dimension) is defined by:

$\mathrm{ATTN}_H(X)_{:, i} = x_i + \sum_{j=1}^h W_O^j W_V^j X_{\mathcal{N}_H(i)} \cdot \sigma\left( \left( W_E^j E_{\mathcal{N}_H(i)} \odot W_K^j X_{\mathcal{N}_H(i)} \right)^T \left( W_Q^j x_i \right) \right)$

where:
- $\mathcal{N}_H(i)$ denotes the set of neighbors of node $i$ in interaction graph $H$ ,
- $X_{\mathcal{N}_H(i)} \in \mathbb{R}^{d \times |\mathcal{N}_H(i)|}$ is the matrix formed by selecting the embedding columns of neighbors of $i$ ,
- $E_{\mathcal{N}_H(i)} \in \mathbb{R}^{d_E \times |\mathcal{N}_H(i)|}$ contains $d_E$ -dimensional edge features for edges connected to node $i$ (dataset edge features for local edges, and learnable embeddings for expander and virtual node edges),
- $W_Q^j, W_K^j, W_V^j \in \mathbb{R}^{m \times d}$ , $W_O^j \in \mathbb{R}^{d \times m}$ , and $W_E^j \in \mathbb{R}^{m \times d_E}$ are query, key, value, output, and edge projection matrices for attention head $j$ ,
- $\odot$ denotes element-wise (Hadamard) multiplication, and $\sigma(\cdot)$ is the column-wise softmax function.
Each attention layer is followed by a feedforward network:

$\mathrm{FF}(X) = \mathrm{ATTN}_H(X) + W_2 \cdot \mathrm{ReLU}\left( W_1 \cdot \mathrm{ATTN}_H(X) + b_1 \mathbf{1}_n^T \right) + b_2 \mathbf{1}_n^T$

where $W_1 \in \mathbb{R}^{r \times d}$ , $W_2 \in \mathbb{R}^{d \times r}$ , $b_1 \in \mathbb{R}^r$ , $b_2 \in \mathbb{R}^d$ , and $\mathbf{1}_n \in \mathbb{R}^n$ is the all-ones vector. The number of inner products computed per layer equals $|E_H| = O(|V| + |E|)$ .
Knowl 3 — Random Regular Expander Graph Generation for Sparse Attention
algorithm
EXPHORMER generates a random $d$ -regular expander overlay graph $G' = (V, E')$ on vertex set $V = \{1, 2, \dots, n\}$ for an even degree $d \ge 2$ by sampling independent uniform permutations. With probability $1 - O(n^{-\Omega(\sqrt{d})})$ , the generated graph is weakly-Ramanujan.
Input: Vertex set $V = \{1, 2, \dots, n\}$ , even degree parameter $d \ge 2$ , spectral threshold parameter $\epsilon > 0$
Output: Edge set $E'$ of a $d$ -regular near-Ramanujan expander graph $G' = (V, E')$
$E' \leftarrow \emptyset$
for $j = 1$ to $d/2$ do
     $\pi_j \leftarrow$ uniformly random permutation of $V$
    for each $i \in V$ do
         $E' \leftarrow E' \cup \{(i, \pi_j(i)), (i, \pi_j^{-1}(i))\}$
    end for
end for
Remove all self-loops from $E'$
Compute eigenvalues of adjacency matrix $A_{G'}: d = \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d$
$\lambda_{\text{max}} \leftarrow \max(|\lambda_2|, |\lambda_n|)$
if $\lambda_{\text{max}} > 2\sqrt{d - 1} + \epsilon$ then
    Restart and resample permutations
end if
return $E'$
A common variant samples a single random permutation $\pi$ over $nd/2$ elements formed by taking $d/2$ copies of each vertex in $V$ , while another variant samples independent Hamiltonian cycles on $V$ .
Knowl 4 — Spectral Approximation and Information Mixing of Expander Graph Attention
theoretical result
Let $G = (V, E)$ be an undirected $d$ -regular graph on $n$ vertices with adjacency matrix $A_G$ having real eigenvalues $d = \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d$ . $G$ is an $\epsilon$ -expander if $\max\{|\lambda_2|, |\lambda_n|\} \le \epsilon d$ .
1. Spectral Approximation of Complete Graphs: The Laplacian $L_G = d I_n - A_G$ of a $d$ -regular $\epsilon$ -expander spectrally approximates the Laplacian $L_{K_n} = n I_n - J_n$ of the complete graph $K_n$ on $n$ vertices:
$(1 - \epsilon)\frac{1}{n} L_{K_n} \preceq \frac{1}{d} L_G \preceq (1 + \epsilon)\frac{1}{n} L_{K_n}$

where $A \preceq B$ indicates that $B - A$ is positive semi-definite. Consequently, a sparse expander attention pattern with $O(n)$ edges preserves cut structures and spectral properties of full dense attention ( $O(n^2)$ edges).
1. Random Walk Mixing: For any initial vertex distribution $\pi^{(0)}: V \to \mathbb{R}^+$ and error parameter $\delta > 0$ , the random walk distribution $\pi^{(t)} = (D_G^{-1} A_G)^t \pi^{(0)}$ satisfies:
$\left\| \pi^{(t)} - \frac{1}{n}\mathbf{1} \right\|_1 \le \delta \quad \text{for all } t \ge \frac{1}{2(1-\epsilon)} \log\left( \frac{n}{\delta^2} \right)$
1. Graph Diameter and Layer Stacking: The expander graph diameter satisfies $\mathrm{diam}(G) = O_{d,\epsilon}(\log n)$ . Therefore, stacking $O_{d,\epsilon}(\log n)$ sparse transformer layers enables pairwise information propagation between every pair of nodes.
Knowl 5 — Universal Function Approximation of EXPHORMER
theoretical result
Let $H$ be the interaction graph of a sparse EXPHORMER model on $n$ graph nodes (and optional virtual nodes). If $H$ contains self-loops and satisfies either of the following conditions:
1. $H$ contains at least one node connected to all $n$ graph nodes (e.g., at least one virtual global connector node), or
2. $H$ uses expander graph attention augmented by a Hamiltonian path,
then a sparse transformer network $g$ using attention graph $H$ and trainable positional encodings can universally approximate any continuous sequence-to-sequence function on a compact domain.

Formally, for any continuous function $f: [0, 1]^{d \times n} \to \mathbb{R}^{d \times n}$ , any $1 < p < \infty$ , and any precision $\epsilon > 0$ , there exists a sparse transformer network $g$ with attention pattern $H$ such that:

$\ell^p(f, g) = \left( \int_{[0, 1]^{d \times n}} \|f(X) - g(X)\|_p^p \, dX \right)^{1/p} < \epsilon$

Thus, EXPHORMER achieves universal approximation using only $O(n)$ edges per layer without requiring full $O(n^2)$ connectivity.

Knowl 6 — Comparison of Attention Mechanisms within the GraphGPS Framework

data/table

Evaluation of different attention mechanisms incorporated alongside message passing inside the GraphGPS framework demonstrates that EXPHORMER outperforms sequence-based sparse transformers (BigBird, Performer) and message passing alone (GPS MPNN-only), while matching or exceeding the accuracy of full dense transformers (GPS-Transformer).

Model / Dataset	CIFAR10	MalNet-Tiny	PascalVOC-SP	Peptides-Func
	Accuracy $\uparrow$	Accuracy $\uparrow$	F1 score $\uparrow$	AP $\uparrow$
GPS (MPNN-only)	$69.948 \pm 0.499$	$92.23 \pm 0.65$	$0.3016 \pm 0.0031$	$0.6159 \pm 0.0048$
GPS-BigBird	$70.480 \pm 0.106$	$92.34 \pm 0.34$	$0.2762 \pm 0.0069$	$0.5854 \pm 0.0079$
GPS-Performer	$70.670 \pm 0.338$	$92.64 \pm 0.78$	$0.3724 \pm 0.0131$	$0.6475 \pm 0.0056$
GPS-Transformer	$72.305 \pm 0.344$	$93.50 \pm 0.41$	$0.3736 \pm 0.0158$	$\mathbf{0.6535 \pm 0.0041}$
EXPHORMER	$\mathbf{74.69 \pm 0.125}$	$\mathbf{94.02 \pm 0.21}$	$\mathbf{0.3975 \pm 0.0037}$	$0.6527 \pm 0.0043$

EXPHORMER outperforms BigBird and Performer across all four datasets, and beats full dense attention on CIFAR10 (+2.38%), MalNet-Tiny (+0.52%), and PascalVOC-SP (+0.0239 F1 score).

Knowl 7 — Performance of EXPHORMER on Benchmarking GNN Datasets

data/table

Performance of EXPHORMER combined with message passing against standard GNN and transformer baselines on five graph benchmarks (CIFAR10, MalNet-Tiny, MNIST, CLUSTER, PATTERN):

Model	CIFAR10	MalNet-Tiny	MNIST	CLUSTER	PATTERN
	Accuracy $\uparrow$	Accuracy $\uparrow$	Accuracy $\uparrow$	Accuracy $\uparrow$	Accuracy $\uparrow$
GCN	$55.71 \pm 0.381$	$81.0$	$90.71 \pm 0.218$	$68.50 \pm 0.976$	$71.89 \pm 0.334$
GIN	$55.26 \pm 1.527$	$88.98 \pm 0.557$	$96.49 \pm 0.252$	$64.72 \pm 1.553$	$85.39 \pm 0.136$
GAT	$64.22 \pm 0.455$	$92.1 \pm 0.242$	$95.54 \pm 0.205$	$70.59 \pm 0.447$	$78.27 \pm 0.186$
GatedGCN	$67.31 \pm 0.311$	$92.23 \pm 0.65$	$97.34 \pm 0.143$	$73.84 \pm 0.326$	$85.57 \pm 0.088$
PNA	$70.35 \pm 0.63$	–	$97.94 \pm 0.12$	–	–
DGN	$72.84 \pm 0.417$	–	–	–	$86.68 \pm 0.034$
CRaWl	$69.01 \pm 0.259$	–	$97.94 \pm 0.050$	–	–
GIN-AK+	$72.19 \pm 0.13$	–	–	–	$\mathbf{86.85 \pm 0.057}$
SAN	–	–	–	$76.69 \pm 0.65$	$86.58 \pm 0.037$
K-Subgraph SAT	–	–	–	$77.86 \pm 0.104$	$\mathbf{86.85 \pm 0.037}$
EGT	$68.70 \pm 0.409$	–	$98.17 \pm 0.087$	$\mathbf{79.23 \pm 0.348}$	$86.82 \pm 0.020$
GraphGPS	$72.30 \pm 0.356$	$93.50 \pm 0.41$	$98.05 \pm 0.126$	$78.02 \pm 0.180$	$86.69 \pm 0.059$
EXPHORMER	$\mathbf{74.69 \pm 0.125}$	$\mathbf{94.02 \pm 0.209}$	$\mathbf{98.55 \pm 0.039}$	$78.07 \pm 0.037$	$86.74 \pm 0.015$

EXPHORMER achieves state-of-the-art results on CIFAR10 ( $74.69\%$ ), MalNet-Tiny ( $94.02\%$ ), and MNIST ( $98.55\%$ ). Furthermore, on PATTERN and CLUSTER, EXPHORMER achieves performance comparable to dense GraphGPS while requiring substantially fewer parameters (91k vs. 340k parameters on PATTERN; 283k vs. 500k parameters on CLUSTER).

Knowl 8 — Performance on Long-Range Graph Benchmark Datasets

data/table

Empirical evaluation on the Long-Range Graph Benchmark (LRGB) evaluates model capacity to capture long-range interactions in graph structures.

Model	PascalVOC-SP	COCO-SP	Peptides-Func	Peptides-Struct	PCQM-Contact
	F1 score $\uparrow$	F1 score $\uparrow$	AP $\uparrow$	MAE $\downarrow$	MRR $\uparrow$
GCN	$0.1268 \pm 0.0060$	$0.0841 \pm 0.0010$	$0.5930 \pm 0.0023$	$0.3496 \pm 0.0013$	$0.3234 \pm 0.0006$
GINE	$0.1265 \pm 0.0076$	$0.1339 \pm 0.0044$	$0.5498 \pm 0.0079$	$0.3547 \pm 0.0045$	$0.3180 \pm 0.0027$
GatedGCN	$0.2873 \pm 0.0219$	$0.2641 \pm 0.0045$	$0.5864 \pm 0.0077$	$0.3420 \pm 0.0013$	$0.3218 \pm 0.0011$
GatedGCN+RWSE	$0.2860 \pm 0.0085$	$0.2574 \pm 0.0034$	$0.6069 \pm 0.0035$	$0.3357 \pm 0.0006$	$0.3242 \pm 0.0008$
Transformer+LapPE	$0.2694 \pm 0.0098$	$0.2618 \pm 0.0031$	$0.6326 \pm 0.0126$	$0.2529 \pm 0.0016$	$0.3174 \pm 0.0020$
SAN+LapPE	$0.3230 \pm 0.0039$	$0.2592 \pm 0.0158$	$0.6384 \pm 0.0121$	$0.2683 \pm 0.0043$	$0.3350 \pm 0.0003$
SAN+RWSE	$0.3216 \pm 0.0027$	$0.2434 \pm 0.0156$	$0.6439 \pm 0.0075$	$0.2545 \pm 0.0012$	$0.3341 \pm 0.0006$
GraphGPS	$0.3748 \pm 0.0109$	$0.3412 \pm 0.0044$	$\mathbf{0.6535 \pm 0.0041}$	$0.2500 \pm 0.0005$	$0.3337 \pm 0.0006$
EXPHORMER	$\mathbf{0.3975 \pm 0.0037}$	$\mathbf{0.3455 \pm 0.0009}$	$0.6527 \pm 0.0043$	$\mathbf{0.2481 \pm 0.0007}$	$\mathbf{0.3637 \pm 0.0020}$

EXPHORMER outperforms full dense GraphGPS on three of the five LRGB benchmarks (PascalVOC-SP, COCO-SP, Peptides-Struct) and achieves a substantial improvement on PCQM-Contact (MRR $0.3637$ vs. $0.3337$ ), while maintaining competitive performance on Peptides-Func.

Knowl 9 — Scalability to Large Transductive Graphs
empirical result
Dense graph transformers exhibit quadratic memory complexity $O(|V|^2)$ and fail due to Out-Of-Memory (OOM) errors on graphs with thousands to hundreds of thousands of nodes. EXPHORMER scales to large transductive graphs with up to $169\text{K}$ nodes and $1.1\text{M}$ edges while maintaining high classification accuracy:
- ogbn-arxiv (169,343 nodes, 1,166,243 edges): Dense transformers and dense GraphGPS run out of memory on a 40GB NVIDIA A100 GPU. EXPHORMER with expander edges trains at 1.72s/epoch and reaches $72.44 \pm 0.28\%$ accuracy, outperforming GCN ( $71.35 \pm 0.31\%$ , 0.21s/epoch), GCN+BigBird ( $71.16 \pm 0.19\%$ , 17.85s/epoch), and GCN+Performer ( $70.92 \pm 0.04\%$ , 5.77s/epoch).
- Amazon Computer (13,381 nodes, 245,778 edges): Dense GraphGPS runs out of memory; EXPHORMER achieves $91.59 \pm 0.31\%$ , outperforming NAGphormer ( $91.22 \pm 0.14\%$ ) and SAN ( $89.83 \pm 0.16\%$ ).
- Amazon Photo (7,487 nodes, 119,043 edges): EXPHORMER achieves $95.27 \pm 0.42\%$ , competitive with NAGphormer ( $95.49 \pm 0.11\%$ ) and GraphGPS ( $95.06 \pm 0.13\%$ ).
- Coauthor CS (18,333 nodes, 81,894 edges): EXPHORMER achieves $95.77 \pm 0.15\%$ , outperforming GraphGPS ( $93.93 \pm 0.12\%$ ).
- Coauthor Physics (34,493 nodes, 247,962 edges): SAN and GraphGPS run out of memory; EXPHORMER achieves $97.16 \pm 0.13\%$ .
- Batch Size Scaling: On MalNet-Tiny (graphs up to 5,000 nodes), dense GraphGPS runs out of memory at batch size 16 on a 40GB GPU, whereas EXPHORMER trains at batch size 256.
Knowl 10 — Inductive Bias Trade-offs between Expander Edges and Virtual Global Nodes
limitation
The effectiveness of expander edges versus virtual global nodes in sparse graph transformers depends on graph modality and connectivity structure:
1. Information Bottlenecks vs. Dispersed Paths: Virtual global nodes reduce graph diameter to 2 but can become severe information bottlenecks when many nodes transmit disparate signals simultaneously. In contrast, expander graphs reduce diameter to $O(\log n)$ via many alternative short paths, avoiding single-node bottlenecks.
2. Interference with Local Graph Topology: Virtual nodes add dedicated nodes with distinct connections. In contrast, expander edges overlay directly onto graph vertices; when structural topology is critical and node/edge features are uninformative (such as in MalNet-Tiny call graphs), expander edges can interfere with the propagation of genuine structural signals.
3. Modality Preferences:
  - Molecular Graphs (e.g., Peptides-Func, Peptides-Struct, PCQM-Contact): Virtual global nodes consistently yield significant performance gains, whereas expander edges provide little benefit or can degrade accuracy.
  - Image-based Superpixel Graphs (e.g., PascalVOC-SP, COCO-SP): Expander graph attention provides major accuracy gains, whereas virtual nodes degrade performance due to information bottlenecks.
4. Mini-batching Compatibility: Virtual global nodes connect to all nodes, complicating neighborhood sampling algorithms (such as GraphSAGE) by pulling the entire graph into each batch, whereas expander graph edges support sub-graph batching.

Coverage note — None was omitted; all key theoretical theorems, sparse attention formulations, expander generation algorithms, and comprehensive benchmark results from both the main paper and relevant appendices are covered.

References

1.OGB leaderboard for arxiv dataset. https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv. Accessed: 2023-01-26.
2.Alon, N. Explicit expanders of every degree and size. Combinatorics, 41(4):447–463, 2021.
3.Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
4.Beaini, D., Passaro, S., Létourneau, V., Hamilton, W., Corso, G., and Liò, P. Directional graph networks. In International Conference on Machine Learning (ICML), pp. 748–758. PMLR, 2021.
5.Bo, D., Shi, C., Wang, L., and Liao, R. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.01028, 2023.
6.Bodnar, C., Frasca, F., Otter, N., Wang, Y. G., Liò, P., Montufar, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34, 2021.
7.Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252, 2020.
8.Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017.
9.Chen, D., O’Bray, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. arXiv:2202.03036, 2022a.
10.Chen, J., Gao, K., Li, G., and He, K. Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. CoRR, abs/2206.04910, 2022b.
11.Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. In ICLR, 2021.
12.Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
13.Deac, A., Lackenby, M., and Veličković, P. Expander graph propagation. In Learning on Graphs 2022, 2022. URL https://arxiv.org/abs/2210.02997.
14.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844–3852, 2016.
15.Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. CoRR, abs/2012.09699, 2020.
16.Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020. URL https://arxiv.org/abs/2003.00982.
17.Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875, 2021.
18.Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. CoRR, abs/2206.08164, 2022.
19.Fey, M., Yuen, J.-G., and Weichert, F. Hierarchical intermessage passing for learning on molecular graphs. arXiv preprint arXiv:2006.12179, 2020.
20.Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. In Vanschoren, J. and Yeung, S. (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, 2021.
21.Friedman, J. A proof of Alon’s second eigenvalue conjecture. In Larmore, L. L. and Goemans, M. X. (eds.), Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pp. 720–724. ACM, 2003.
22.Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025–1035, 2017.
23.Hoory, S., Linial, N., and Wigderson, A. Expander graphs and their applications. Bull. Amer. Math. Soc., 43(04):439–562, August 2006. ISSN 0273-0979.
24.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
25.Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. OGB-LSC: A large-scale challenge for machine learning on graphs. CoRR, abs/2103.09430, 2021.
26.Hussain, M. S., Zaki, M. J., and Subramanian, D. Edge-augmented graph transformers: Global self-attention is enough for graphs. arXiv preprint arXiv:2108.03348, 2021.
27.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
28.Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.03893, 2021.
29.Lubotzky, A., Phillips, R., and Sarnak, P. Ramanujan graphs. Comb., 8(3):261–277, 1988.
30.Luo, Y., Luo, G., Yan, K., and Chen, A. Inferring from references with differences for semi-supervised node classification on graphs. Mathematics, 10(8), 2022. ISSN 2227-7390. doi: 10.3390/math10081262. URL https://www.mdpi.com/2227-7390/10/8/1262.
31.Margulis, G. A. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988. ISSN 0555-2923.
32.Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667, 2021.
33.Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602–4609, 2019.
34.Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663–4673. PMLR, 2019.
35.Namata, G. M., London, B., Getoor, L., and Huang, B. Query-driven active surveying for collective classification. In Workshop on Mining and Learning with Graphs, 2012. URL http://linqs.cs.umd.edu/basilic/web/Publications/2012/namata:mlg12-wkshp/namata-mlg12.pdf.
36.Oono, K. and Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
37.Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., and Tang, J. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 459–467, 2018.
38.Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. CoRR, abs/2205.12454, 2022.
39.Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333–341. SIAM, 2021.
40.Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. CoRR, abs/1811.05868, 2018.
41.Spielman, D. A. Spectral and algebraic graph theory, 2019. URL http://cs-www.cs.yale.edu/homes/spielman/sagt. Version dated December 19, 2019.
42.Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. Efficient transformers: A survey. CoRR, abs/2009.06732, 2020. URL https://arxiv.org/abs/2009.06732.
43.Toenshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Graph learning with 1d convolutions on random walks. arXiv:2102.08786, 2021.
44.Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
45.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998–6008, 2017.
46.Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
47.Wu, Q., Zhao, W., Li, Z., Wipf, D. P., and Yan, J. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387–27401, 2022.
48.Wu, Q., Yang, C., Zhao, W., He, Y., Wipf, D., and Yan, J. Difformer: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09474, 2023.
49.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
50.Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform bad for graph representation? ArXiv, abs/2106.05234, 2021.
51.Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are transformers universal approximators of sequence-to-sequence functions? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020a.
52.Yun, C., Chang, Y., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. O(n) connections are expressive enough: Universal approximability of sparse transformers. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020b.
53.Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontañón, S., Pham, P., Ravula, A., Wang, Q., Yang, L., and Ahmed, A. Big bird: Transformers for longer sequences. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), NeurIPS, 2020.
54.Zhang, J., Zhang, H., Xia, C., and Sun, L. Graph-bert: Only attention is needed for learning graph representations. CoRR, abs/2001.05140, 2020.
55.Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., and Ye, Y. Gophormer: Ego-graph transformer for node classification. CoRR, abs/2110.13094, 2021.
56.Zhao, J., Qu, M., Li, C., Yan, H., Liu, Q., Li, R., Xie, X., and Tang, J. Learning on large-scale text-attributed graphs via variational inference, 2022a. URL https://arxiv.org/abs/2210.14709.
57.Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022b.

Citation

MLA

Shirzad, H., et al. “Exphormer: Sparse Transformers for Graphs”. International Conference on Machine Learning, vol. 202, 2023, pp. 31613–32, https://proceedings.mlr.press/v202/shirzad23a.html.

APA

Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., & Sinop, A. K. (2023). Exphormer: Sparse Transformers for Graphs. International Conference on Machine Learning, 202, 31613–31632. https://proceedings.mlr.press/v202/shirzad23a.html

Chicago

Shirzad, H., A. Velingker, B. Venkatachalam, D. J. Sutherland, and A. K. Sinop. 2023. “Exphormer: Sparse Transformers for Graphs”. International Conference on Machine Learning 202: 31613–32. https://proceedings.mlr.press/v202/shirzad23a.html.

Harvard

Shirzad, H. et al. (2023) “Exphormer: Sparse Transformers for Graphs”, International Conference on Machine Learning. PMLR, pp. 31613–31632. Available at: https://proceedings.mlr.press/v202/shirzad23a.html.

Vancouver

1. Shirzad H, Velingker A, Venkatachalam B, Sutherland DJ, Sinop AK (2023) Exphormer: Sparse Transformers for Graphs. In: International Conference on Machine Learning. PMLR, pp 31613–31632

BibTeX

@InProceedings{pmlr-v202-shirzad23a,
  title = 	 {Exphormer: Sparse Transformers for Graphs},
  author =       {Shirzad, Hamed and Velingker, Ameya and Venkatachalam, Balaji and Sutherland, Danica J. and Sinop, Ali Kemal},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {31613--31632},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/shirzad23a/shirzad23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/shirzad23a.html},
  abstract = 	 {Graph transformers have emerged as a promising architecture for a variety of graph learning and representation tasks. Despite their successes, though, it remains challenging to scale graph transformers to large graphs while maintaining accuracy competitive with message-passing networks. In this paper, we introduce Exphormer, a framework for building powerful and scalable graph transformers. Exphormer consists of a sparse attention mechanism based on two mechanisms: virtual global nodes and expander graphs, whose mathematical characteristics, such as spectral expansion, pseduorandomness, and sparsity, yield graph transformers with complexity only linear in the size of the graph, while allowing us to prove desirable theoretical properties of the resulting transformer models. We show that incorporating Exphormer into the recently-proposed GraphGPS framework produces models with competitive empirical results on a wide variety of graph datasets, including state-of-the-art results on three datasets. We also show that Exphormer can scale to datasets on larger graphs than shown in previous graph transformer architectures.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Exphormer: Sparse Transformers for Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — EXPHORMER Sparse Attention Architecture for Graphs

Knowl 2 — Generalized Graph Attention Mechanism with Edge Features

Knowl 3 — Random Regular Expander Graph Generation for Sparse Attention

Knowl 4 — Spectral Approximation and Information Mixing of Expander Graph Attention

Knowl 5 — Universal Function Approximation of EXPHORMER

Knowl 6 — Comparison of Attention Mechanisms within the GraphGPS Framework

Knowl 7 — Performance of EXPHORMER on Benchmarking GNN Datasets

Knowl 8 — Performance on Long-Range Graph Benchmark Datasets

Knowl 9 — Scalability to Large Transductive Graphs

Knowl 10 — Inductive Bias Trade-offs between Expander Edges and Virtual Global Nodes

References

Citation

BibTeX

Source Code

Access the Paper