Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification

Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.

Authors

• Zijie Zhou University of Macau
• Zhaoqi Lu University of Macau The Hong Kong Polytechnic University Guangdong Institute of Intelligent Science and Technology, China
• Xuekai Wei University of Macau
• Rongqin Chen University of Macau
• Shenghui Zhang University of Macau
• Pak Lon Ip University of Macau
• Leong Hou U University of Macau

Keywords

No keywords are indexed for this paper.