PaperlayerView exact revision on arXiv

Source-linked AI summary

Exphormer: Sparse Transformers for Graphs

Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop

arXiv:2303.06147v2cs.LG

TL;DR

Graph transformers offer long-range modeling but remain difficult to scale, while existing sparse mechanisms can underperform on graphs. EXPHORMER combines virtual global nodes, expander graphs, and local neighborhoods in GraphGPS to obtain linear-scale sparse attention. It achieves competitive or state-of-the-art performance across datasets and scales beyond prior graph-transformer settings, with a limitation that direct k-hop attention can become superlinear.

  • Problem

    Graph transformers need to model long-range interactions without the quadratic O(n^2) cost that limits large-graph scalability and without relying on sparse mechanisms designed for sequences.

  • Method

    EXPHORMER replaces dense attention with a sparse interaction graph combining virtual global nodes, constant-degree expander graphs, and local neighborhoods, with O(|V| + |E|) computation.

  • Results

    EXPHORMER outperforms other sparse transformers, often matches or exceeds full transformers with fewer parameters, achieves state-of-the-art results on multiple datasets, and scales beyond 10,000 nodes.

  • Takeaways & Limitations

    EXPHORMER provides a sparse graph-transformer architecture that preserves competitive performance while reducing training parameters and enabling larger-graph experiments.

  • Takeaways & Limitations

    Direct attention over k-hop neighborhoods may introduce a superlinear number of interactions on general graphs.

Abstract

from arXiv · show

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. Code can be found at \url{https://github.com/hamed1375/Exphormer}.

1. Introduction

Graph transformers model long-range interactions but face quadratic-cost scalability and sparse mechanisms designed for sequences can perform poorly on graphs. EXPHORMER addresses this with graph-centric sparse attention and achieves competitive accuracy while scaling further.

  • Global graph-transformer attention models long-range interactions but costs O(|V|^2), making large graphs difficult to fit and process.
  • Existing sparse mechanisms such as BigBird and Performer were designed mainly for sequences, and performed relatively poorly in GraphGPS experiments.
  • EXPHORMER combines global nodes, expander graphs, and local neighborhoods into sparse attention mechanisms with linear computational cost in nodes and edges.
  • The architecture's expanders and global nodes spectrally approximate full attention with few layers and have universal approximation properties.
  • EXPHORMER outperforms other sparse transformers, often matches or exceeds full transformers with fewer parameters, reaches state-of-the-art results, and scales to larger graphs.

2. Related Work

Related work spans message-passing GNNs, graph transformers, sparse sequence-inspired attention, and scalable sampling-based or linear-time graph transformers.

  • Graph Neural Networks (GNNs): GNNs use message passing and are generally limited in expressivity by the 1-Weisfeiler-Lehman isomorphism test.
  • Graph Neural Networks (GNNs): Some methods augment GNNs with node identifiers, random features, positional encodings, structural information, or spectral representations.
  • Graph transformer architectures: Graph transformer work includes architectures that use graph structure for attention, positional encodings, or both, while GraphGPS combines message passing with attention.
  • Scalable graph transformers: Sampling-based and linear-time graph transformers improve scalability, although some operate attention only over sampled mini-batches.
  • Sparse Transformers: Sparse transformers reduce quadratic sequence complexity by restricting attention patterns, but many existing mechanisms were designed for sequences rather than graphs.

3. Sparse Attention on Graphs

EXPHORMER replaces dense graph attention with a sparse interaction graph combining input neighborhoods, expander edges, and virtual global nodes. These components preserve local and long-range interactions with linear-scale computation, while k-hop generalization can become superlinear.

  • Attention mechanism on graphs: A graph attention mechanism represents direct token interactions as edges in a directed graph H, with computation proportional to the number of edges.
  • Attention mechanism on graphs: Dense attention connects every node pair and costs O(n^2), motivating sparse patterns with ideally O(n) edges.
  • Sparse patterns: EXPHORMER is a graph-centric sparse mechanism using expander graphs, global connectors, and local neighborhoods, which may be combined selectively across layers.
  • The EXPHORMER Architecture: Its interaction graph has O(|V| + |E|) computation and combines bidirectional expander, global, and local-neighborhood edges.
  • The EXPHORMER Architecture: Constant-degree expanders create alternative short paths and mixing properties without connecting all node pairs, while virtual nodes provide global connectivity with O(|V|) edges.
  • The EXPHORMER Architecture: Local attention connects each node to immediate neighbors in the input graph, adding O(|E|) interaction edges and preserving topology.
  • The EXPHORMER Architecture: Direct attention over k-hop neighborhoods may introduce a superlinear number of interactions on general graphs.
  • Expander construction: Random permutations generate d-regular near-Ramanujan expanders with high probability, with failed graphs discarded in practice.

4. Theoretical Properties of EXPHORMER

EXPHORMER uses expander graphs and global nodes to approximate dense graph interactions with sparse connectivity. These structures support logarithmic-depth information propagation and universal approximation results.

  • Expander graphs: For a d-regular graph, expansion is characterized by bounding the non-leading adjacency eigenvalues relative to d.An ϵ-expander satisfies max{|λ2|, |λn|} ≤ ϵd.
  • Expander graphs: Expander graphs provide sparse approximations of complete graphs while preserving selected spectral and connectivity properties with only O(n) edges.The paper connects spectral approximation to preservation of cuts and vertex expansion.
  • Mixing properties: Expander random walks mix toward a uniform distribution after logarithmically many steps, enabling information to spread broadly across nodes.This mixing property motivates expander attention for propagating information without dense pairwise connections.
  • Mixing properties: Stacking O_d,ϵ(log n) transformer layers over a d-regular ϵ-expander models all pairwise node interactions.The result addresses indirect interaction rather than requiring every pair to be connected within one sparse layer.
  • Universal approximation: EXPHORMER can approximate every continuous function f : [0, 1]d×|V | →Rd×|V | to arbitrary accuracy using global or suitable expander attention.The paper presents this as a universal approximation property for sparse graph transformers.

5. Experiments

Experiments evaluate EXPHORMER within GraphGPS across diverse graph and node prediction benchmarks. The models generally outperform sparse and dense transformer baselines while improving scalability to graphs exceeding 10,000 nodes.

  • Experimental setup: Experiments cover fifteen benchmark datasets spanning image-based, synthetic, code, molecular, transductive, and long-range graph tasks.EXPHORMER is evaluated for both graph prediction and node prediction.
  • Experimental setup: EXPHORMER replaces GraphGPS’s transformer component while retaining message passing and positional or structural encodings.The experiments also include ablations of EXPHORMER’s attention components.
  • Sparse-attention comparisons: EXPHORMER outperforms BigBird and Performer on all four highlighted datasets and beats dense GPS-Transformer on three while remaining competitive on the fourth.The sparse attention component also improves over an MPNN-only baseline in the reported comparisons.
  • Broad benchmark results: EXPHORMER-based GraphGPS achieves SOTA performance on three of five datasets and remains competitive on the other two, while outperforming dense GraphGPS across all five.The models also outperform the full-transformer SAN model and several MPNN baselines.
  • Efficiency: EXPHORMER often uses fewer parameters than full transformers, including 90,000 versus 340,000 on PATTERN and 280,000 versus 500,000 on CLUSTER.These comparisons are between EXPHORMER and comparable full-transformer GraphGPS models.
  • Scaling to larger graphs: EXPHORMER enables larger-scale training, including graphs with up to 35K nodes and 250K edges and ogbn-arxiv with 169K nodes and 1.1M edges.Standard GraphGPS encounters out-of-memory issues on several larger datasets, while EXPHORMER remains competitive and reaches SOTA accuracy on Computer.

6. Conclusion

EXPHORMER is a sparse graph transformer architecture designed for efficient, scalable graph learning. It uses fewer training parameters, linear memory complexity, and achieves competitive or state-of-the-art empirical performance across diverse datasets.

  • EXPHORMER combines virtual nodes and expander graphs in a sparse graph transformer architecture.Its mathematical properties support the architecture’s suitability for graph learning.
  • EXPHORMER uses fewer training parameters, trains faster, and has memory complexity linear in graph size.These properties support scaling to larger graphs than other Transformer-based methods typically handled.
  • EXPHORMER outperforms other sparse transformers and performs comparably or better than full transformers.
  • Combining EXPHORMER with MPNNs in GraphGPS yields state-of-the-art empirical results on several datasets.

A. Dataset Descriptions

The experiments cover diverse graph datasets spanning image, synthetic community, malware, citation, co-authorship, co-purchase, and molecular domains. These datasets include graph-, node-, and edge-level prediction tasks, with some containing very large graphs or long-range structure.

  • The dataset suite spans image-based, synthetic SBM, code graph, molecular, citation, co-authorship, and co-purchase graphs.The experiments use datasets including CIFAR10, MNIST, PascalVOC-SP, COCO-SP, PATTERN, CLUSTER, MalNet-Tiny, Peptides, ogbn-arxiv, Coauthor, and Amazon variants.
  • Tasks include graph classification, node classification, and edge-level prediction across the benchmark datasets.PCQM-Contact requires ranking edges, while several other datasets use graph- or node-level classification.
  • MalNet-Tiny contains 5,000 malware-related graphs with up to 5,000 nodes each.The task is to classify graphs as benign or one of four malware types.
  • ogbn-arxiv is one directed citation graph with 169,343 nodes and 1,166,243 edges.Nodes represent computer science papers, and node features are 128-dimensional title-and-abstract embeddings.
  • The molecular LRGB datasets have relatively large diameters, averaging 56.99 ± 28.72 for Peptides and 9.86 ± 1.79 for PCQM-Contact.Their average shortest path lengths are 20.89 ± 9.79 and 4.63 ± 0.63, respectively.

B. More Experimental Results

Additional experimental details describe positional and structural encoding choices, expander and virtual-node hyperparameters, and parameter-budget controls for fair comparisons. The appendix provides dataset statistics and hyperparameter tables.

  • EXPHORMER experiments generally follow GraphGPS guidance for optimizer, positional encodings, and structural encodings.Some cases benefited from more layers with smaller dimensions, and ELSLapPE sometimes outperformed LapPE.
  • Large-scale graphs use GCN, while the other experiments use CustomGatedGCN alongside EXPHORMER.
  • Expander degree 6-22 and 1-6 virtual nodes were selected through linear search, depending on graph size.Grid search was not feasible across all hyperparameters.
  • PATTERN and CLUSTER use a 500K parameter budget, while CIFAR10 and MNIST use approximately 100K.These budgets were chosen for fair comparisons with GraphGPS.

B.2. Full Comparison of Attention Mechanisms

EXPHORMER differs from BigBird by using graph neighborhoods for locality and fixed-degree expander graphs for sparse random attention. The comparisons examine attention mechanisms, hyperparameters, and performance across standard, LRGB, and large transductive datasets.

  • Comparison with BigBird: EXPHORMER uses graph-neighborhood attention for locality, whereas BigBird uses sequence-oriented window attention.BigBird’s interaction graph is described as a Cayley graph on Z_n; EXPHORMER uses the input graph structure.
  • Experimental comparisons: The appendix includes hyperparameter tables for LRGB and large transductive graph datasets, alongside attention-mechanism comparisons.
  • Comparison with BigBird: EXPHORMER uses a d-regular expander for random attention, while BigBird uses an Erdős-Rényi graph.
  • Comparison with BigBird: EXPHORMER expander graphs provide both a linear number of edges and guaranteed spectral expansion properties.The passage contrasts this with BigBird’s constant-probability sparse graph, which keeps linear edges but loses expansion properties.
  • Comparison with BigBird: EXPHORMER-based models often substantially outperform BigBird-based equivalents with fewer parameters.
  • Expander analysis: The expander construction is analyzed through spectral expansion properties and bounds for d-regular graphs.The discussion identifies Ramanujan graphs as essentially optimal spectral expanders.
  • Experimental comparisons: Table 10 reports that EXPHORMER with MPNN gives the highest CIFAR10 accuracy, while pure EXPHORMER remains comparable.

C.2. Random Regular Graphs

This section describes random and Hamiltonian-cycle constructions for sparse regular expanders used in EXPHORMER, including their spectral guarantees and practical approximation properties.

  • Standard expander graph construction: Random d-regular graphs are generated from d/2 independent uniformly random permutations and are weakly Ramanujan.Friedman’s result bounds the nonprincipal adjacency eigenvalues by approximately 2√(d−1).
  • Standard expander graph construction: EXPHORMER experiments instantiate expander attention with randomly generated graphs after removing self-loops.This construction is used in the experiments reported in Tables 1 to 5.
  • A simple variant: A simple variant uses one random permutation over d/2 copies of each vertex to generate the expander edge multiset.The construction pairs elements under the permutation and adds both edge directions.
  • A simple variant: The simple variant produces near-Ramanujan graphs most of the time in practice and is used for ablation studies.The ablations cover Tables 10 to 14.
  • Hamiltonian cycle variant: A Hamiltonian-cycle variant samples d/2 independent permutations whose cyclic decompositions each consist of a single cycle.Friedman’s theorem analyzes the resulting graph process.
  • Hamiltonian cycle variant: The Hamiltonian-cycle random process automatically satisfies EXPHORMER’s universal approximation property when augmented with self-loops.The appendix’s experimental comparison reports almost similar results across expander-generation approaches.

D. On Expander Graphs versus Global Connectors

EXPHORMER’s expander graphs and virtual global nodes offer complementary sparse connectivity patterns, with their usefulness and risks depending on graph type and dataset.

  • Graph diameter: Virtual nodes reduce graph diameter to exactly 2, whereas expander graphs provide a probabilistic diameter guarantee of O(log n).The diameter comparison assumes the original graph is not already complete for the virtual-node case.
  • Information Bottleneck: Virtual nodes can create an information bottleneck because many nodes may depend on a shared global sink.Expander graphs introduce multiple paths and rely on local information storage instead.
  • Interference with the local structure: Expander edges can interfere with local structure because the model must distinguish them from original graph edges through edge embeddings.This is especially relevant for structure-dependent datasets such as MalNet-Tiny.
  • Dataset-dependent behavior: Molecular datasets generally benefit from virtual nodes, while expander edges provide little benefit or can hurt performance.The observed pattern reverses for image-based graphs, particularly Pascal-VOC.
  • Dataset-dependent behavior: On Pascal-VOC, expander graphs are highly useful, whereas virtual nodes can cause an information bottleneck.This is the opposite of the reported molecular-dataset pattern.
  • Batching: Virtual nodes complicate GraphSAGE-style batching because every batch includes the whole graph, while expander edges remain compatible with batching techniques.The batching consequence follows from virtual nodes connecting across the graph.

E. Universality of EXPHORMER

This section establishes that EXPHORMER can retain universal approximation under sparse attention, provided its attention graph includes either a virtual global connector or a suitable expander structure.

  • Setup: EXPHORMER uses positional encodings and graph-aware sparse attention to address universality for functions on graphs.Graphs are represented through node or edge inputs tied to the graph structure and invariant under node ordering.
  • Motivation: Dense-transformer universality results do not directly apply to graph transformers because graph attention is not fully pairwise connected.The section motivates a separate universality result for sparse graph attention.
  • Implication: The construction provides universal approximation properties using only O(n) edges.The result is stated for EXPHORMER-based graph transformers under the theorem’s structural assumptions.
  • Theorem E.3: Theorem E.3 assumes self-loops and either a virtual node connected to all graph nodes or an underlying expander containing a Hamiltonian path.Only one of these two conditions is required.
  • Theorem E.3: Under those conditions, a sparse EXPHORMER transformer can universally approximate continuous functions from [0, 1]^(d×n) to R^(d×n).For any 1 < p < ∞ and ε > 0, a network exists with ℓp(f, g) < ε.
  • Proof strategy: The theorem’s virtual-node case follows from a star subgraph and an existing sparse-transformer universal approximation theorem.A virtual node connected to all graph nodes creates the required star structure.
  • Proof strategy: The expander-only case uses self-loops, a Hamiltonian path, and diameter O(log n) to satisfy Yun et al.’s theorem assumptions.This supplies the second proof route when the virtual-node condition is absent.
  • Implication: These universality results imply that some sparse EXPHORMER transformers can solve graph isomorphism problems, without yielding an efficient identification algorithm.The paper explicitly separates representational existence from efficient network discovery.
Loading 2303.06147v2…