Balancing Memory Efficiency and Accuracy in Spectral-Based Graph Transformers

The transformer architecture has been a significant driving force behind advancements in deep learning, yet transformer-based models for graph representation learning have not caught up to mainstream Graph Neural Network (GNN) variants. A major limitation is the large O(𝑛2) memory consumption of graph transformers, where 𝑛 is the number of nodes. Therefore, we develop a memory-efficient graph transformer for node classification, capable of handling graphs with thousands of nodes while maintaining accuracy. Specifically, we reduce the memory use in the attention mechanism and add a random-walk positional encoding to improve upon the SAN graph transformer architecture. We evaluate our model on standard node classification benchmarks: Cora, Citeseer, and Chameleon. Unlike SAN, which runs out of memory, our memory-efficient graph transformer can be run on these benchmarks. Compared with landmark GNN models GCN and GAT, our graph transformer requires 27.92% less memory while being competitive in accuracy.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Ho, Kelly

Advisor dc:contributor.advisor

• Arvind

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/152648

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/152648