PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Graph Transformers with Spectral Attention

Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, Prudencio Tossou

arXiv:2106.03893v3cs.LG

TL;DR

Graph Transformers face limitations from sparse message passing and the difficulty of defining positions on arbitrary graphs. SAN learns positional encodings from the full Laplacian spectrum and feeds them to a fully connected Transformer. It performs on par or better than state-of-the-art models across multiple benchmarks and outperforms other attention-based models by a large margin.

  • Problem

    Sparse message-passing GNNs have expressive limitations, oversmoothing, and over-squashing, while graph positional encodings face eigenvalue multiplicity and sign ambiguity.

  • Method

    SAN learns node positional encodings from the Laplacian spectrum and combines them with node embeddings before fully connected Graph Transformer attention.

  • Results

    SAN performs on par or better than state-of-the-art models on multiple benchmarks and outperforms other attention-based models by a large margin.

  • Takeaways & Limitations

    Full attention and spectral positional encodings provide a graph Transformer architecture with strong benchmark performance and greater expressive power than standard message passing.

  • Takeaways & Limitations

    The node-wise LPE lacks sign invariance, while the edge-wise LPE resolves this issue at additional computational cost.

Abstract

from arXiv · show

In recent years, the Transformer architecture has proven to be very successful in sequence processing, but its application to other data structures, such as graphs, has remained limited due to the difficulty of properly defining positions. Here, we present the $\textit{Spectral Attention Network}$ (SAN), which uses a learned positional encoding (LPE) that can take advantage of the full Laplacian spectrum to learn the position of each node in a given graph. This LPE is then added to the node features of the graph and passed to a fully-connected Transformer. By leveraging the full spectrum of the Laplacian, our model is theoretically powerful in distinguishing graphs, and can better detect similar sub-structures from their resonance. Further, by fully connecting the graph, the Transformer does not suffer from over-squashing, an information bottleneck of most GNNs, and enables better modeling of physical phenomenons such as heat transfer and electric interaction. When tested empirically on a set of 4 standard datasets, our model performs on par or better than state-of-the-art GNNs, and outperforms any attention-based model by a wide margin, becoming the first fully-connected architecture to perform well on graph benchmarks.

1 Introduction

Graph message passing encodes structure through sparse computation, but its expressive and information-propagation limitations motivate more flexible graph architectures. SAN addresses this by combining learned spectral positional encodings with fully connected Transformer attention.

  • Message-passing GNNs encode graph structure through iterative vector exchanges between connected nodes.
  • Their expressive power is bounded by the Weisfeiler-Lehman isomorphism hierarchy.
  • Repeated local aggregation causes oversmoothing, while increasing computation paths cause over-squashing as model depth grows.
  • Soft inductive biases offer a more flexible alternative to encoding graph structure directly through a restricted computation graph.
  • SAN develops spectral learnable positional encodings, uses full Transformer attention, and is competitive with or exceeds state-of-the-art graph models.

2 Theoretical Motivations

Graph Laplacian eigenfunctions provide spectral positional information and physical interaction measures, but graph-specific ambiguities complicate their use. These motivations support using the spectrum broadly while handling variable eigenvalues, multiplicities, and sign choices.

  • Spectral graph representations: Laplacian eigenfunctions provide graph positional encodings analogous to sine functions in sequences and can represent graph structure through spectral information.
  • Physical interpretations: Eigenvectors paired with eigenvalues support relative-position measures related to electrostatic, diffusion, and biharmonic interactions.
  • Spectral structure: Graph spectra can reveal structural and sub-structural resonance, with higher-frequency eigenvectors often localized in molecular substructures.
  • Graph-specific challenges: Unlike sequences, graphs have variable spectra, so fixed eigenvector ordering can miss distinct structures sharing an eigenvalue.
  • Graph-specific challenges: Repeated eigenvalues create ambiguous eigenspaces because any linear combination of their eigenvectors is valid.
  • Graph-specific challenges: Variable graph sizes make fixed eigenvector budgets inefficient, while sign ambiguity creates 2^k possible sign combinations and makes augmentation intractable for large k.

3 Model Architecture

SAN learns fixed-size positional encodings from graph Laplacian eigenfunctions, then combines them with node embeddings for Graph Transformer processing. Its spectral and fully connected design addresses sign ambiguity, expressive-power limits, over-squashing, and long-range physical interactions, while introducing computational costs.

  • Learned positional encoding: SAN projects graph eigenfunctions into a learned positional encoding that can use up to the entire Laplace spectrum and learn frequency interactions.The LPE is concatenated to node embeddings before they enter the Graph Transformer.
  • LPE Transformer over nodes: For each node, the LPE concatenates the m lowest eigenvalues with their associated eigenvector elements, projects them to dimension k, applies Transformer self-attention, and sum-pools the sequence.The hyperparameter m may be padded when m exceeds the number of nodes; selecting m equal to the dataset’s maximum graph size captures every spectrum.
  • LPE design principles: Pairing normalized eigenvectors with eigenvalues handles variable spectrum length and multiplicities, while random sign flips during training promote invariance to eigenvector sign ambiguity.The node-wise LPE does not intrinsically resolve sign ambiguity; sign-flip augmentation is used during training.
  • LPE Transformer over edges: The edge-wise LPE uses relative, sign-invariant operators from eigenvector differences and products, but for fully connected graphs its complexity reaches O(m^2N^2), or O(N^4) using all eigenfunctions.This approach also increases memory demands and can prevent large batch sizes.
  • Full-graph attention: SAN preserves local connectivity while adding full-graph attention through separate mechanisms for real and added edges, with γ controlling bias toward full-graph attention.Connected and disconnected node pairs use different key, query, and edge projections; attention outputs are clamped for numerical stability.
  • Theoretical and physical properties: Full connectivity removes direct-path over-squashing and improves theoretical expressivity, while the spectrum-based architecture supports modeling long-range physical interactions.With the full eigenfunction set and enough parameters, SAN can distinguish any pair of non-isomorphic graphs, although the required parameter count is unknown and possibly non-polynomial.

4 Experimental Results

The experiments evaluate SAN through ablations and comparisons with established graph models across molecular and synthetic benchmarks. SAN benefits from dataset-dependent attention and positional-encoding choices, performs strongly on synthetic tasks, and remains competitive on molecular tasks.

  • Experimental setup: SAN was evaluated on ZINC, PATTERN, CLUSTER, MolHIV, and MolPCBA using the respective benchmark training protocols.The study first performed ablations, then tuned the best-performing model for comparison with state-of-the-art methods.
  • Attention ablations: Molecular datasets benefit less from full attention, with the best parameter at log γ ∈(−7, −5), whereas PATTERN and CLUSTER favor higher γ.The authors relate this difference to molecular tasks emphasizing local structures and to molecules generally being smaller than SBM graphs.
  • LPE ablations: The node-wise LPE significantly improves molecular-task performance, while its improvement is modest on PATTERN and CLUSTER.The authors attribute the molecular gains to substructure detection and note that PATTERN can require only two eigenvectors for its positional encoding.
  • Comparison to the state-of-the-art: SAN consistently outperforms state-of-the-art models on all synthetic datasets and achieves competitive results on MolPCBA.On MolHIV, SAN has a lower test score than SOTA but a higher validation score of 85.30% than PNA at 84.25% and DGN at 84.70%.
  • Comparison to the state-of-the-art: SAN consistently outperforms attention-based models by a wide margin and is reported as the first fully-connected model to perform well on graph tasks.The comparison includes GCN, GraphSage, GIN, GAT, GatedGCN, PNA, and DGN.

5 Conclusion

The paper concludes that SAN combines Laplacian-spectrum-aware learned positional encodings with a Transformer architecture and performs on par with or better than state-of-the-art methods across benchmarks. Its computational bottleneck remains an important scope boundary, motivating future work on more scalable Transformers.

  • Conclusion: SAN is a Transformer-based graph architecture whose learned positional encodings make it aware of a graph’s Laplace spectrum.The conclusion identifies spectral awareness as the model’s central architectural property.
  • Conclusion: SAN performs on par with or better than state-of-the-art methods on multiple benchmarks and outperforms other attention-based models by a large margin.The conclusion summarizes the reported empirical comparison across benchmark tasks.
  • Limitations and future work: SAN has a computational bottleneck, and future work is proposed on Transformer variants with linear or logarithmic scaling.The authors state that such scaling would enable the theoretically more powerful edge-wise LPE.
  • Societal impact: The model’s computational cost O(m2N + N 2) exceeds standard message passing or convolutional approaches of O(E), with associated environmental impact.The paper also notes limited direct societal impact but identifies possible indirect harms from malicious graph-based applications.

A LPE Transformer Over Edges

The edge-wise LPE represents relative node positions using Laplacian eigenvalues and eigenvectors, processes edges with a Transformer, and produces edge positional encodings for attention. This approach is computationally expensive on fully connected graphs because it scales with the number of edges.

  • A LPE Transformer Over Edges: The edge-wise formulation treats edges as a variable-size batch and eigenvectors as a variable-length sequence for Transformer encoding.This applies a Transformer Encoder separately across graph edges while accommodating graph-dependent dimensions.
  • A LPE Transformer Over Edges: Element-wise products produce vectors invariant to sign permutations of the precomputed eigenvectors.This removes dependence on arbitrary eigenvector sign choices.
  • A LPE Transformer Over Edges: Linear expansion and sum pooling convert the encoded vectors into fixed-size edge positional encodings used to compute attention weights.The resulting edge representations enter the attention mechanism through equation 4.
  • A LPE Transformer Over Edges: O(m^2N^2) complexity for fully connected graphs, or O(N^4) using all eigenfunctions, creates a major computational and memory bottleneck.The N^2 edges make batching expensive, limiting batch sizes and complicating training.
  • A LPE Transformer Over Edges: Edge-wise LPE encodes relative positions from up to m Laplacian eigenvalues and eigenvectors rather than absolute node positions.The construction permits m ≤ N, where N is the number of nodes.

B.1 Benchmarks and datasets

The empirical evaluation uses four standard graph benchmarks spanning molecular regression, synthetic node classification, and real-world molecular classification. These datasets include both balanced structural tasks and challenging molecular classification settings with class imbalance or scaffold-based splits.

  • B.1 Benchmarks and datasets: The benchmark suite comprises ZINC, PATTERN, CLUSTER, and MolHIV.These datasets are standard benchmarks provided under the MIT license.
  • B.1 Benchmarks and datasets: ZINC is a synthetic molecular graph regression task predicting logP − SA.The target subtracts the computed octanol-water partition coefficient from the synthetic accessibility score.
  • B.1 Benchmarks and datasets: CLUSTER is a synthetic node-classification benchmark with six generated communities and one labeled node per community.The task is to classify which nodes belong to the same community.
  • B.1 Benchmarks and datasets: PATTERN is a synthetic two-community node-classification benchmark testing recognition of predetermined subgraphs.Its graphs are generated with Stochastic Block Models.
  • B.1 Benchmarks and datasets: MolHIV is a real-world molecular graph-classification task predicting HIV-replication inhibition under scaffold splitting.The dataset is heavily imbalanced toward negative samples and has reported validation–test de-correlation.
  • B.1 Benchmarks and datasets: MolPCBA is a larger real-world molecular classification benchmark with scaffold splitting and 1.4% positive samples across multiple tasks.Average Precision is used as the evaluation metric.

B.2 Ablation studies

The ablation studies isolate the effects of node LPE and full attention while approximately matching models at 500k parameters where applicable. Training and tuning procedures vary by dataset, with additional tuning for selected evaluations.

  • B.2 Ablation studies: The ablations measure the impact of node LPE and full attention using minimal hyperparameter tuning.Most hyperparameters were inherited from prior work, while parameter-heavy LPE required adjustments.
  • B.2 Ablation studies: Models were adjusted to approximately 500k parameters for fair comparison, including modified Graph Transformer hidden dimensions.The hidden dimensions were changed to equalize model sizes across comparisons.
  • B.2 Ablation studies: Graph Transformer hidden dimensions remained consistent within each dataset experiment.This controls the hidden dimension across models in a given dataset comparison.
  • B.2 Ablation studies: Training used Adam with learning-rate decay initialized from 10^-3 or 10^-4, followed by dataset-specific modifications.The reported changes include learning rates, patience, minimum learning rates, weight decay, and dropout.
  • B.2 Ablation studies: The tuned studies searched dataset-specific Graph Transformer depths, hidden dimensions, readouts, dropout, weight decay, learning rates, and LPE settings.Search breadth differed according to parameter budgets and training time.
  • B.2 Ablation studies: The final optimized parameters were evaluated in 10 experiments with identical seeds.This rerun procedure was reported for the optimized evaluation.

C Expressivity and complexity analysis of graph Transformers

Graph Transformers can be universal when node identifiers or positional encodings are available, but graph positional encoding is nontrivial because graphs lack a canonical node ordering. The paper introduces learning complexity to compare how architectures capture isomorphic graph structure and applies it to LPE.

  • C Expressivity and complexity analysis of graph Transformers: Naively labeling graph nodes can make Transformers theoretically distinguish any graph, rendering the Weisfeiler–Lehman test unsuitable for their expressivity.The paper therefore seeks another way to compare graph-structure understanding.
  • C Expressivity and complexity analysis of graph Transformers: Learning complexity is introduced to compare architectures’ ability to understand the space of isomorphic graphs.The analysis is intended to go beyond the limitations of standard expressivity comparisons.
  • C Expressivity and complexity analysis of graph Transformers: The paper applies learning-complexity analysis to LPE and finds that it captures graph structure more easily than a naive Transformer.This is the paper’s reported theoretical comparison.
  • C Expressivity and complexity analysis of graph Transformers: Prior results establish that Transformers approximate permutation-equivariant sequence functions with sufficient parameters.These universality results motivate studying how positional information changes Transformer expressivity.
  • C Expressivity and complexity analysis of graph Transformers: A Transformer with positional encoding adds a fixed learned encoding E to each input X before applying the Transformer.The paper denotes this operation as g_p(X) = g(X + E).

C.2 Graph Transformers approximate solutions to the graph isomorphism problem

Graph Transformers can approximate permutation-invariant functions that separate non-isomorphic graphs, but this universality is approximate and may require impractical complexity.

  • Graph Transformer universality: Naive node and edge Transformers use universal approximation results to approximate functions that distinguish non-isomorphic graphs.The node Transformer uses identity inputs with padded adjacency positional encodings, while the edge Transformer processes ordered vertex pairs and connectivity indicators.
  • Comparison with message passing: This expressivity exceeds the Weisfeiler-Lehman bound that limits most message-passing graph networks.The WL test cannot distinguish some graphs, whereas the universal approximation argument applies to permutation-invariant graph functions separating isomorphism classes.
  • Limitations: The universality result provides only an approximate solution, so Transformers can still mislabel graphs.The approximation error is nonzero in general, and the theorems do not establish an exact graph-isomorphism solver.
  • Limitations: For fixed error, the node encoding can require exponentially many parameters and computational time in the number of nodes.The stated bound includes a term N(2L/ε)^N^2, although the authors note that this bound may not be tight for specific problems.
  • Limitations: Learning invariance across the N! node-label permutations is itself unlikely to have polynomial complexity in N.The proof assumes that all labelings of an isomorphic graph map to the same output class.

C.3 Expressivity of the node-LPE

The node-LPE uses the Laplacian spectrum to provide graph-aware node representations, supporting universal approximation over bounded graph representations while reducing representation complexity relative to naive encodings.

  • Expressivity of the node-LPE: The node-LPE is designed to generate unique node identifiers that let a Transformer approximate graph-isomorphism solutions.This construction makes the positional encoding itself informative about graph structure.
  • Spectral information: Using only m eigenvalues and eigenspaces cannot distinguish graphs that agree on those components but differ in the remaining N−m spectral components.The authors show that fixing m supports approximate classification of all graphs with N ≤ m.
  • Universality: The LPE Transformer can approximate continuous functions of bounded spectral representations after linear projection and summation over the m spectral dimension.This follows from the stated universality proposition for LPE Transformers.
  • Learning complexity: The LPE representation reduces the label-invariance burden compared with naive node and edge Transformers, which must identify N! representations per graph.With no repeated eigenvalues, node-LPE representations vary by at most 2^N eigenvector sign choices, while edge-LPE representations can be unique with respect to sign choices.
  • Non-isospectral graphs: For non-isospectral graphs, the node-LPE can discriminate using eigenvalues without learning invariance to eigenvector signs or multiplicities.The passage argues this is especially relevant for larger graphs because the ratio of isospectral graphs decreases with graph size.
  • Non-isospectral graphs: Laplacian eigenvalues distinguish the illustrated non-isomorphic, non-isospectral graphs that the 1-WL test cannot distinguish.The example demonstrates the spectral distinction described for the node-LPE’s expressivity.
Loading 2106.03893v3…