Deep Graph Clustering Using Graph Neural Networks and Seed Detection

• Carlos Pereira Lopes Filho UFSCar
• Guilherme Henrique Messias UFSCar
• Sylvia Iasulaitis UFSCar
• Alneu de Andrade Lopes USP
• Alan Demétrius Baria Valejo UFSCar

Resumo

Clustering plays a fundamental role in attributed graphs, which incorporate both topological structure and node attributes represented as feature vectors. Deep clustering methods based on Graph Neural Networks (GNNs) have proven effective in extracting patterns from such data. Most existing approaches use a traditional clustering algorithm to identify representative elements, which are later employed to train a GNN and, finally, the clustering task. However, when selecting representative elements, these clustering algorithms consider only the feature vector of each instance, neglecting topological information. This limitation negatively impacts the GNN learning process. To address this issue, we propose Deep Graph Clustering via Graph Neural Network and Seed Detection (DGCSD), a model consisting of three modules: (1) the seed detection module, which identifies representative nodes; (2) the embedding module, which employs a graph attentional network to capture global topological information; and (3) the self-supervised module, which leverages the representative nodes to guide the clustering task. An advantage of our algorithm is that it integrates both information, the topological structure and node attributes across all modules to identify representative elements. This is the first GNN-based clustering algorithm that incorporates seed detection, establishing a significant reference for future research. The empirical analysis of real-world graphs provides evidence that combining a seed detection algorithm with a GNN model is competitive compared to well-established algorithms.