Reinforcement learning improves tracking evolving communities in graphs
DISRL: Dual-Scale Incremental Semi-Supervised Reinforcement Learning for Dynamic Community Tracking
Machine Learning
Summary
Tracking how groups of connected people or items change over time is hard when labels about these groups are old or sparse. The authors propose a new method that learns in two steps: quickly adapting within short periods and slowly updating over the long term. This helps reduce errors that build up when trying to track evolving communities across many time steps. They also created a new dataset to test their method, which performed better than existing approaches.
What this means in practice
- •For social network analysts: Track and update changing groups of users over time in social media platforms despite limited direct labels.
- •For cybersecurity teams: Monitor evolving clusters of malicious activity or entities in network traffic to detect threats faster and more reliably.
Authors
Tianming Zhang, Jinxu Wang, Yixuan Zhang, Zhengyi Yang, Chenyu Hou, Bin Cao, Jing Fan
Abstract
Dynamic local community detection tracks the evolving community of designated seed nodes across graph snapshots. However, it faces two critical challenges: temporal supervision uncertainty, where sparse and outdated labels fail to provide seed-specific guidance under topology changes, and unbounded error cascades, where sequential policy transfer accumulates exploration errors over long horizons. To address these challenges, we propose DISRL, a Dual-scale Incremental Semi-supervised Reinforcement Learning framework. DISRL introduces a supervision construction module that dynamically generates seed-specific guidance from sparse known communities, and a dual-scale community exploration module that stabilizes policy evolution by decoupling short-term adaptation within temporal windows from long-term parameter consolidation across windows. Furthermore, we construct a dynamic graph benchmark with diverse community evolution scenarios. Extensive experiments demonstrate that DISRL consistently outperforms state-of-the-art baselines under various dynamic settings.