Abstract: The higher-order connectivity structure has been largely ignored,which contains a better signature of community compared with the lower-order connectivity structure,and the high-order information causes the inevitable fragmentation problem.To solve those problems,a motif-aware and graph Transformer(MGTrans) for community detection is proposed. Firstly, the maximal complete subgraph in the graph is searched and regarded as a motif,and the original graph is reconstructed with the motif as a unit to capture the motif adjacency matrix.At the same time,mixed-order outer-cut edges encoding is used to obtain the residual edge information of the original graph to solve the fragmentation problem,and position information and edge information on the reconstructed graph are captured through a position encoding matrix and motif short path with weight encoded.Then,the initial features are extracted by a graph transformer.Combing position encoding matrix,edge encoding matrix and initial features through the attention network to get motif embedding matrix for the community detection.Finally,The experimental results on several different datasets show the effectiveness of the MGTrans in improving the community detection performance of state-of-the-art methods and effectiveness for overlapping community detection and multi-community public node detection.

Key words: community detection, graph Transformer, motif, graph encoding