# Exphormer: Scaling transformers for graph-structured data

DevFeed: [Exphormer: Scaling transformers for graph-structured data](<https://devfeed.tech/articles/exphormer-scaling-transformers-for-graph-structured-data-28542.md>)

Original publisher: [Read original article](<http://blog.research.google/2024/01/exphormer-scaling-transformers-for.html>)

Author: Google AI (noreply@blogger.com)

Published: 2024-01-23T22:27:00Z

Content type: article

Language: en

Sources: [Google Research](<https://devfeed.tech/sources/google-research.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Transformers](<https://devfeed.tech/topics/transformers.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Natural language processing](<https://devfeed.tech/topics/nlp.md>)

Tags: [deep-learning](<https://devfeed.tech/tags/deep-learning.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [icml](<https://devfeed.tech/tags/icml.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [theory](<https://devfeed.tech/tags/theory.md>), [transformers](<https://devfeed.tech/tags/transformers.md>)

## AI overview

This article explains the scalability challenges of graph transformers, whose complete attention graphs create quadratic computational and memory costs. It introduces Exphormer, a sparse attention framework designed for graph data that uses expander graphs from spectral graph theory.

## Source excerpt

Posted by Ameya Velingker, Research Scientist, Google Research, and Balaji Venkatachalam, Software Engineer, Google Graphs, in which objects and their relations are represented as nodes (or vertices) and edges (or links) between pairs of nodes, are ubiquitous in computing and machine learning (ML). For example, social networks, road networks, and molecular structure and interactions are all domains in which underlying datasets have a natural graph structure. ML can be used to learn the properties of nodes, edges, or entire graphs. A common approach to learning on graphs are graph neural networks (GNNs), which operate on graph data by applying an optimizable transformation on node, edge, and global attributes. The most typical class of GNNs operates via a message-passing framework, whereby each layer aggregates the representation of a node with those of its immediate neighbors. Recently, graph transformer models have emerged as a popular alternative to message-passing GNNs. These models build on the success of Transformer architectures in natural language processing (NLP), adapting them to graph-structured data. The attention mechanism in graph transformers can be modeled by an interaction graph, in which edges represent pairs of nodes that attend to each other. Unlike message passing architectures, graph transformers have an interaction graph that is separate from the input graph. The typical interaction graph is a complete graph, which signifies a full attention mechanism that models direct interactions between all pairs of nodes. However, this creates quadratic computational and memory bottlenecks that limit the applicability of graph transformers to datasets on small graphs with at most a few thousand nodes. Making graph transformers scalable has been considered one of the most important research directions in the field (see the first open problem here). A natural remedy is to use a sparse interaction graph with fewer edges. Many sparse and efficient transformers