PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer
This work addresses scalability and expressiveness issues in graph neural networks for node-level tasks, offering a practical solution for large-scale graph applications.
The paper tackles the limitation of spectral graph neural networks that use shared polynomial coefficients for all nodes, which restricts flexibility for node-level tasks, and proposes PolyFormer with PolyAttn that learns node-wise filters efficiently, achieving superior performance on both homophilic and heterophilic graphs and scaling to graphs with up to 100 million nodes.
Spectral Graph Neural Networks have demonstrated superior performance in graph representation learning. However, many current methods focus on employing shared polynomial coefficients for all nodes, i.e., learning node-unified filters, which limits the filters' flexibility for node-level tasks. The recent DSF attempts to overcome this limitation by learning node-wise coefficients based on positional encoding. However, the initialization and updating process of the positional encoding are burdensome, hindering scalability on large-scale graphs. In this work, we propose a scalable node-wise filter, PolyAttn. Leveraging the attention mechanism, PolyAttn can directly learn node-wise filters in an efficient manner, offering powerful representation capabilities. Building on PolyAttn, we introduce the whole model, named PolyFormer. In the lens of Graph Transformer models, PolyFormer, which calculates attention scores within nodes, shows great scalability. Moreover, the model captures spectral information, enhancing expressiveness while maintaining efficiency. With these advantages, PolyFormer offers a desirable balance between scalability and expressiveness for node-level tasks. Extensive experiments demonstrate that our proposed methods excel at learning arbitrary node-wise filters, showing superior performance on both homophilic and heterophilic graphs, and handling graphs containing up to 100 million nodes. The code is available at https://github.com/air029/PolyFormer.