Semi-supervised Community Detection in Dynamic Graphs

Semi-supervised approaches to Community Detection (CD) in graphs aim to detect communities closely related to a few labeled ones. State-of-the-art semi-supervised algorithms adopt a three-step process, which entails (1) Generating candidate communities based solely on the network structure; (2) Selecting the candidates that are most similar to the labeled communities; (3) Refining the selected communities shortlisted at Step (2). However, existing approaches are unsuited to handle the dynamics in labeled communities and their relations with time-varying graph structures. In this work, we formulate the new task of semi-supervised CD from dynamic graphs, which is relevant to real-world time-evolving scenarios. To avoid executing the previous pipeline independently at every time step and potentially missing relevant temporal community-level relations, we envisage a new approach relying on time-aware strategies for both dynamic graph embedding and community selection and refinement. We leverage a latent graph representation incorporating node-and subgraph-level temporal relations neglected by static approaches. Then, supervised community refinements are propagated across consecutive time steps to capture time-evolving trends. After adapting static CD models to the dynamic scenario, we conduct extensive comparisons of the methods on datasets with varying characteristics in the novel task of dynamic semi-supervised CD. The proposed approach shows remarkable improvements in low-modularity and low-stability dynamic graphs.