Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification
This addresses the scalability problem for researchers and practitioners using attention-based GNNs on large graphs, though it is incremental as it builds on existing GAT methods.
The paper tackles the high computational burden of attention-based graph neural networks (GNNs) by proposing FastGAT, which uses spectral sparsification to prune graphs, resulting in up to 10x reduction in computational time and memory while maintaining performance.
The attention mechanism has demonstrated superior performance for inference over nodes in graph neural networks (GNNs), however, they result in a high computational burden during both training and inference. We propose FastGAT, a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. This results in a per-epoch time that is almost linear in the number of graph nodes as opposed to quadratic. We theoretically prove that spectral sparsification preserves the features computed by the GAT model, thereby justifying our algorithm. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks under both inductive and transductive settings. FastGAT can dramatically reduce (up to \textbf{10x}) the computational time and memory requirements, allowing the usage of attention based GNNs on large graphs.