Graph Transformers (GTs) address the locality limitation of traditional GNNs, which aggregate only local neighbor information, by leveraging global attention. However, they suffer from two significant issues: neglecting community structures and information over-squeezing. In this paper, we first identify these two problems and propose a Community-Aware Graph Transformer (CoGT) to solve them. CoGT introduces a novel node-community-global hierarchical aggregation framework. This design preserves community-level semantics while reducing the volume of aggregated information, alleviating the over-squeezing problem. CoGT first employs a two-stage positional encoding to identify latent communities and enhance semantic consistency. Then, a hierarchical and parallel transformer computation method based on community representations facilitates global information interaction. Furthermore, we enable community-wise parallel attention computation, improving computational efficiency. Experimental results demonstrate that CoGT outperforms existing methods across multiple real-world datasets.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Community-Aware Graph Transformer: Preserving Community Semantics for Effective Global Aggregation

  • Yutai Duan,
  • Jie Liu,
  • Jianhua Wu,
  • Jialin Liu

摘要

Graph Transformers (GTs) address the locality limitation of traditional GNNs, which aggregate only local neighbor information, by leveraging global attention. However, they suffer from two significant issues: neglecting community structures and information over-squeezing. In this paper, we first identify these two problems and propose a Community-Aware Graph Transformer (CoGT) to solve them. CoGT introduces a novel node-community-global hierarchical aggregation framework. This design preserves community-level semantics while reducing the volume of aggregated information, alleviating the over-squeezing problem. CoGT first employs a two-stage positional encoding to identify latent communities and enhance semantic consistency. Then, a hierarchical and parallel transformer computation method based on community representations facilitates global information interaction. Furthermore, we enable community-wise parallel attention computation, improving computational efficiency. Experimental results demonstrate that CoGT outperforms existing methods across multiple real-world datasets.