融合模体感知和图Transformer编码的社区检测

Community detection by fusion of motif-aware and graph Transformer encoding

针对已有社区检测方法存在忽略高阶结构信息,且在信息引入过程中极易产生碎片的问题,提出了一种融合模体感知和图Transformer编码的社区检测方法。首先,将原图中的极大完全子图视为模体,并以模体为顶点对原图进行重构,捕获模体邻接矩阵。同时,使用混阶外切边编码获取原图的残留边信息,解决碎片问题,利用位置编码和内权边编码捕获重构图上的位置信息和边信息。其次,使用图Transformer提取原图携带的初始特征,再对编码所得的位置信息和边信息及初始特征进行融合,获得模体嵌入矩阵,实现社区检测。最后,在几个不同数据集上的实验结果表明,所提方法可以有效提高社区检测的性能,而且,对重叠社区检测和多社区公共顶点检测也是有效的。

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.